Online Learning via Sequential Complexities

1. Introduction

• The model is a repeated game in which a learner chooses a decision, an adversary chooses an outcome, and the learner incurs loss each round.Regret is the difference between cumulative loss and the loss of the best fixed decision; online learnability requires sublinear regret against any adversary strategy.Source: §1 · pp. 1–2
• Analyzing a particular online algorithm may not establish whether it is optimal or reveal the problem’s inherent complexity.Source: §1 · p. 2
• The framework defines the game’s minimax value and develops sequential analogues of combinatorial dimensions, covering numbers, and Rademacher complexities.It also provides results relating these complexity measures.Source: §1 · p. 2
• The approach guarantees the existence of a good online algorithm but does not explicitly produce one.The paper notes that later work showed the minimax viewpoint can also lead to constructive algorithms (Rakhlin et al., 2012).Source: §1 · p. 2

2. Minimax Value and Online Learnability

• The game allows randomized learner decisions and an adaptive adversary that chooses each outcome using the history of prior moves.The setup assumes the decision set lies in a separable metric space and the associated probability-measure set is weakly compact.Source: §2 · p. 3
• The minimax theorem exchanges the learner’s and adversary’s infimum and supremum, giving a dual formulation that is easier to analyze.The stated conditions include weak compactness of the learner’s strategy set and lower semi-continuity of the loss.Source: §2 · p. 3
• Online learnability is reduced to studying the minimax value of the game.The paper focuses on how this value depends on the function class, with the outcome space and loss sometimes implicit.Source: §2 · pp. 3–4
• The paper’s expected-regret notion uses a separate finite-horizon game for each T, unlike Hannan consistency’s infinite game and almost-sure convergence.The authors note that their techniques can also yield Hannan consistency for a slightly different game (Rakhlin et al., 2011).Source: §2 · p. 3
• The framework also covers improper learning, where learner decisions may come from a larger set than the class used for the best-in-hindsight comparison.Prediction with side information is given as an example.Source: §2 · p. 4

3. Sequential Complexities

• Binary trees capture sequential dependence by letting each round’s instance label depend on the preceding path.A path is encoded by ±1 choices, with +1 indicating right and −1 indicating left.Source: §3 · p. 4
• Sequential Rademacher complexity controls uniform martingale deviations, and a matching lower bound yields an if-and-only-if condition for a uniform martingale Law of Large Numbers.That law holds for a class G exactly when RT(G) tends to zero.Source: §3 · p. 5
• The paper presents sequential analogues of classical complexity measures as tools for necessary and sufficient conditions for online learnability.The framework is described as paralleling statistical learning theory.Source: §3 · p. 5
• Sequential covering numbers measure the size of an α-cover of a function class on a labeled tree, with maximal covering number taken over depth-T trees.The paper presents these as effective-size analogues of classical covering numbers.Source: §3 · p. 5
• Sequential Littlestone and fat-shattering dimensions replace tuples of points with trees; restricting each tree level to one repeated value recovers the classical notions.These sequential combinatorial parameters control the growth of sequential covering numbers.Source: §3 · p. 6

4. Structural Properties

• Sequential Rademacher complexity has useful properties for establishing online learnability of complex classes even when no explicit learning algorithms are available.Source: §4 · p. 7
• The paper gives basic properties of sequential Rademacher complexity that match classical Rademacher complexity properties.For example, adding the same function to every class member leaves the complexity unchanged.Source: §4 · p. 7
• A key composition bound controls the complexity of a Cartesian product of function classes passed through a Lipschitz mapping using the complexities of the individual classes.The stated setup assumes each component complexity is at least 1/T.Source: §4 · p. 7
• Whether the extra poly-logarithmic factors in T can be removed from the sequential contraction results remains open.The paper contrasts this with the classical Lipschitz contraction property, which has no such factors; its later supervised-learning theorem avoids the extra factor under convex Lipschitz loss.Source: §4 · p. 8

5. Main Results

• Theorem 7 upper-bounds minimax value through the expected supremum of a martingale-difference process, which sequential Rademacher complexity further controls.The supremum is taken over distributions on sequences of outcomes.Source: §5 · p. 8

5.1 Supervised Learning

• For convex L-Lipschitz losses, the minimax value is bounded by 2L times sequential Rademacher complexity by removing the loss during symmetrization.The generic sequential-complexity contraction would introduce an extraneous logarithmic factor.Source: §5.1 · p. 9
• Online learnability in supervised learning is equivalent to finite fat-shattering dimension at every scale, and the game value and two sequential complexities agree within O(log^3/2 T).The three quantities are the supervised game value, sequential Rademacher complexity, and integrated complexity.Source: §5.1 · pp. 9–10
• The paper recovers the binary-classification bounds of Ben-David et al. (2009) non-constructively through combinatorial and covering-number arguments.Source: §5.1 · p. 10

5.2 Online Convex Optimization

• For online convex optimization, the convex-adversary game value equals the linear-adversary value, and strongly convex regularizers recover online gradient descent guarantees.The reduction is used because directly bounding the sequential complexity can give no non-trivial bound in high- or infinite-dimensional spaces.Source: §5.2 · pp. 11–12

6.1 Neural Networks

• The sequential Rademacher complexity bounds for multilayer neural networks establish their learnability online, but the guarantee is non-constructive.The authors also note that computationally efficient methods attaining these bounds are unclear.Source: §6.1 · pp. 12–13

6.2 Margin Based Regret

• For general function classes, margin-based regret is controlled by sequential Rademacher complexity divided by the margin, up to polylogarithmic factors, without direct dependence on input dimension.The strategy need not know the margin value.Source: §6.2 · pp. 13–14

6.3 Decision Trees

• For decision trees of depth at most d, a randomized strategy has a regret bound involving the base class complexity and correctly classified instances reaching leaves of a comparator tree.The number of correctly classified instances reaching a leaf is denoted C(l); whether the guarantee is computationally feasible remains unclear.Source: §6.3 · p. 14

6.4 Transductive Learning

• For fixed finite X, batch learnability implies online transductive learnability; with VC dimension d and n≤T, the game-value bound matches Kakade and Kalai (2006) up to a constant factor.Source: §6.4 · p. 15

6.5 Isotron

• The idealized single-index-model class is online learnable in improper supervised learning, including for Lipschitz functions that need not be non-decreasing.It remains unclear whether a computationally efficient method attains the guarantee.Source: §6.5 · pp. 15–16

6.6 Prediction of Individual Sequences with Static Experts

• For binary prediction with static experts, the analysis recovers the Cesa-Bianchi and Lugosi (1999) bound and notes that its symmetrization factor of 2 is unnecessary in this scenario.Source: §6.6 · pp. 16–17

• Minimax-based upper bounds establish algorithm existence but discard the dual strategy needed to identify a primal prediction strategy; later work develops a feasible recipe from these techniques.Rakhlin et al. (2012) use minimax reasoning over future rounds and a relaxation approach to derive prediction methods.Source: §7 · p. 17

• The von Neumann-Fan minimax theorem applies under convexity, compactness, and continuity or lower-semicontinuity conditions on the strategy sets and payoff.Source: Appendix A · p. 17
• For the repeated game, the payoff is bilinear in the learner's and adversary's mixed strategies, and weak compactness of the learner's strategy set with continuous loss suffices.Source: Appendix A · p. 18
• When the decision space is noncompact, uniform tightness can be established using a continuous function controlling the norms of strategies; for compact F, tightness holds directly.Source: Appendix A · p. 18

Theorem 1

• Repeated applications of the minimax theorem move expectations and infima through the sequential game, proving the stated minimax identity.The proof repeats this step from round T down to round 1.Source: Appendix B · pp. 18–19

Lemma 4 and Corollary 6

• Lipschitz composition transfers covers of component classes to the composed class, with the resulting bound requiring RT(Gj) ≥ 1/T for each j.Centering the composed function values preserves cover size and places them in [−1,1]; extending a binary function by a 1-Lipschitz map yields the stated corollary.Source: Appendix B · pp. 19–21

Theorems 7 and 8

• The regret-bound proofs use conditional expectations and convexity to replace infima with learner choices and reduce Lipschitz losses to a symmetrized tree-based expression.For convex losses, the proof passes through subgradients and uses the minimax theorem before constructing an instance tree.Source: Appendix B · pp. 22–24

Proposition 9

• The minimax value of the supervised game is lower-bounded by the sequential Rademacher complexity.The lower bound follows by choosing instances along an arbitrary instance tree and labels as i.i.d. Rademacher variables.Source: Appendix B · p. 24

Theorem 10

• Finite fat-shattering dimension at every positive scale is necessary and sufficient for online learnability in supervised learning.The proof uses lower and upper bounds on the sequential Rademacher complexity to establish the two directions.Source: Appendix B · pp. 24–25

Lemma 13

• For convex and linear adversary classes, randomized player strategies are no better than deterministic strategies, so the minimax values coincide.Jensen’s inequality gives a deterministic strategy no worse than a randomized one, and the proof extends the convex-set argument to linear functions.Source: Appendix B · p. 25

Proposition 15

• The vector-class complexity proof bounds the class through contraction and coordinate-wise instance trees.It treats each coordinate of an instance vector as a real-valued tree and combines the coordinate bounds.Source: Appendix B · p. 26

Propositions 16 and 17

• For any given γ, the randomized-strategy bound is extended by discretizing γ as γ_i = 1/2^i and using the corresponding randomized strategies as experts in a countable experts algorithm.Source: Appendix B · p. 27

Appendix B. Proofs

• The non-decreasing 1-Lipschitz class has entropy at most 2/α, all 1-Lipschitz functions have entropy c0/α, and the linear class has fatα ≤ 32/α^2 for α > 4, independent of ambient dimension.The linear-class bound follows using Proposition 14 and the lower bound of Proposition 9.Source: Appendix B · p. 29
• An ℓ∞ cover of the composed class is constructed by composing the covers of F and G; the 1-Lipschitz property controls approximation error.The argument covers G○F on a fixed tree using an α-cover of F and an α-cover of G.Source: Appendix B · p. 29
• The supervised-learning game value is bounded by O(...), via Theorem 8 and a sequential Rademacher complexity bound for the composed class.The supplied passages truncate the rate expression after O(, so its full form cannot be reported.Source: Appendix B · p. 29

Appendix C. Exponentially Weighted Average (EWA) Algorithm on Countable Experts

• The countable-expert result follows a proof closely modeled on the finite case and is included because Propositions 16 and 17 need it.The cited finite-case example is Cesa-Bianchi and Lugosi (2006, Theorem 2.2).Source: Appendix C · p. 29
• Each expert supplies a round-t prediction in F, with F ⊆ [0,1]^X; the forecaster requires access to the experts and initial weights summing to one.The algorithm randomly picks an expert according to its current weight and updates weights for each expert.Source: Appendix C · pp. 29–30
• With η = T^-1/2, Proposition 20 gives the forecaster a regret bound for every expert i ∈ N.The supplied passage does not state the bound's formula.Source: Appendix C · p. 30