A Combinatorial Characterization of Supervised Online Learnability
We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. No characterization of online learnability is known at this level of generality. We give a new scale-sensitive combinatorial dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability. In addition, we show that the sequential minimax dimension subsumes most existing combinatorial dimensions in online learning theory.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryregressionSimilar Papers 제목 키워드 기반
Online Learning: Random Averages, Combinatorial Parameters, and Learnability
We develop a theory of online learning by defining several complexity measures. Among them are analogues of Rademacher complexity, covering numbers and fat-shattering dimension from statistical learning theory. Relations…
Learning TheoryOptimal Learners for Realizable Regression: PAC Learning and Online Learning
In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had established the sufficiency of finiteness of th…
PAC learningregressionInference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds
In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had established the sufficiency of finiteness of th…
Gaussian ProcessesPAC learningregressionInference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds
In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had established the sufficiency of finiteness of th…
Gaussian ProcessesPAC learningregressionCharacterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness
Understanding minimal assumptions that enable learning and generalization is perhaps the central question of learning theory. Several celebrated results in statistical learning theory, such as the VC theorem and Littlest…
Decision Making