Online Learning via Sequential Complexities
We consider the problem of sequential prediction and provide tools to study the minimax value of the associated game. Classical statistical learning theory provides several useful complexity measures to study learning with i.i.d. data. Our proposed sequential complexities can be seen as extensions of these measures to the sequential setting. The developed theory is shown to yield precise learning guarantees for the problem of sequential prediction. In particular, we show necessary and sufficient conditions for online learnability in the setting of supervised learning. Several examples show the utility of our framework: we can establish learnability without having to exhibit an explicit online learning algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryPredictionSimilar Papers 제목 키워드 기반
Majorizing Measures, Sequential Complexities, and Online Learning
We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. We relate majorizing measures to the notion of fractional covering numbers, which we show to be dom…
Online Nonparametric Regression with General Loss Functions
This paper establishes minimax rates for online regression with arbitrary classes of functions and general losses. We show that below a certain threshold for the complexity of the function class, the minimax rates depend…
regressionOn Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
We study an equivalence of (i) deterministic pathwise statements appearing in the online learning literature (termed \emph{regret bounds}), (ii) high-probability tail bounds for the supremum of a collection of martingale…
Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts
We analyze the problem of sequential probability assignment for binary outcomes with side information and logarithmic loss, where regret---or, redundancy---is measured with respect to a (possibly infinite) class of exper…
An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives
In this paper, we propose a practical online method for solving a class of distributionally robust optimization (DRO) with non-convex objectives, which has important applications in machine learning for improving the rob…