Fast rates in statistical and online learning

1. Introduction

• The central condition’s strongest form allows O(1/n) rates for proper learners, while weaker forms allow intermediate rates down to O(1/√n).The paper assumes function classes with at most logarithmic universal metric entropy, including finite, VC, and VC-type classes.Source: §1 · pp. 2–3
• For stochastic online learning, stochastic mixability generalizes classical mixability and characterizes when fast rates hold in the worst case over the specified distribution class.When that class contains all distributions on the domain, stochastic mixability is equivalent to classical mixability.Source: §1 · p. 3
• The central condition and stochastic mixability subsume many existing fast-rate conditions and are equivalent under surprisingly weak conditions.The unified conditions are one-sided and parametrization independent; the paper also notes unresolved issues for some unbounded-loss settings with polynomial tails.Source: §1 · p. 3

1.1 Why Read This Paper? Our Most Important Results

• For bounded losses, the central condition generalizes the Bernstein condition, which generalizes the Tsybakov margin condition, and directly yields fast-rate proofs.The paper contrasts its one-sided condition with Bernstein’s two-sided condition, noting unresolved equivalences for some unbounded losses with polynomial tails.Source: §1 · p. 3, §1.1 · p. 4
• For convex F, strong centrality and strong stochastic mixability are equivalent under weak conditions, connecting fast rates for proper learners with those for online learning.The paper frames the two conditions through different interpretations: an exponential-moment property versus existence of a substitution function.Source: §1.1 · p. 4
• Under bounded losses, the strong central condition gives ERM O(1/n) rates and the v-central condition gives intermediate rates; some unbounded-loss problems also have fast rates when Bernstein fails.The authors conjecture that a weak additional condition could make sublinear v-centrality imply sublinear rates, identifying this as future work.Source: §1.1 · pp. 4–5
• Under mild conditions, the central condition is equivalent to pseudoprobability convexity, which gives it a geometric and data-compression interpretation.For bounded losses and general v, pseudoprobability convexity implies a form of unique minimizers.Source: §1.1 · p. 5
• When the risk minimizer in F also minimizes risk over its convex hull, strong stochastic mixability implies strong centrality, so proper ERM can match online O(1/n) rates under bounded losses.The authors conjecture the same implication for unbounded losses.Source: §1.1 · p. 5

2.1 Decision problems and Risk

• The framework measures predictors by risk and allows decisions in or beyond the hypothesis space, with results applying to misspecified models as well as well-specified ones.Proper algorithms output hypotheses in the model; improper algorithms may predict outside it. The setup assumes a finite-risk model predictor exists and, for the overview, that minimal risk is attained.Source: §2.1 · pp. 7–8

2.2 Main Concept: The Central Condition

• The central condition controls excess-loss moments; for bounded losses it yields fast rates, and it encompasses classification, log-loss density estimation, and finite-class learning motivations.For unbounded losses, stronger assumptions may be needed for fast rates in the risk sense; prior log-loss results also rely on the central condition.Source: §2.2 · pp. 9–10

2.3 Overview of the Paper

• Under Assumption A, the central and pseudoprobability-convexity conditions are equivalent, with frequentist deviation-probability and pseudo-Bayesian convexity interpretations.The pseudoprobabilities are defined as e^-ℓf(Z); the condition also motivates a pseudo-data-compression interpretation.Source: §2.3 · p. 10
• Stochastic mixability supports fast online rates without bounded-loss restrictions and implies the central and pseudoprobability-convexity conditions under relative well-specification.Conversely, the central condition implies the predictor condition, then stochastic mixability, under a minimax identity; together these establish equivalences under stated restrictions.Source: §2.3 · pp. 11–12
• The v-central condition generalizes fixed-η fast rates and, for bounded losses, is equivalent to a generalized Bernstein condition that generalizes Tsybakov’s margin condition.Its rates are of order w(C/n), where w inverts x ↦ xv(x); for unbounded losses, central and Bernstein conditions need not be equivalent, and v-stochastic mixability can differ from v-centrality.Source: §2.3 · pp. 12–13
• The overview asks whether stochastic mixability transfers from unconditional actions to conditional predictors, answering yes with qualification: the decision set may need to be large unless further assumptions apply.For predictors mapping features to actions, the required decision set may be as large as A^X, but additional assumptions can keep it manageable.Source: §2.3 · p. 13
• Theorem 7.6 gives a direct fast-rates proof for bounded losses over finite classes by establishing one-sided concentration of empirical excess loss at a scale related to its excess loss.The concentration argument uses the Cramér-Chernoff method and an upper bound on the cumulant generating function of negative excess loss.Source: §2.3 · p. 14
• When the absolute excess loss is bounded by 1, its cumulant generating function is 0 at −η, and its mean µ is positive, the central condition bounds the cumulant generating function at −η/2 by a universal constant times −ηµ.Source: §2.3 · p. 14
• A careful localization argument extends the finite-class fast-rates result to VC-type classes in Theorem 7.7.Source: §2.3 · p. 14

3.1 The Central and Pseudoprobability Convexity Conditions in General

• The central condition extends to cases without a fixed comparator by allowing a comparator sequence that satisfies the condition in the limit.The general definition uses a function mapping each data-generating distribution P to a comparator in F.Source: §3.1 · p. 14
• Under Assumption A, weak PPC implies strong PPC and makes the risk-minimizing predictor essentially unique up to almost-sure equality of losses.The reverse implication from PPC to the central condition requires Assumption A or bounded loss.Source: §3.1 · p. 15, §3.2 · p. 18
• For squared loss, the central condition holds for Gaussian mean estimation with η ≤ 1 and for subgaussian means with η ≤ 1/σ^2.The regression example yields a 1/σ^2-central condition when the model contains the true regression function; the authors also note a misspecified case under a compactness restriction.Source: §3.1 · pp. 16–17
• In the Bernoulli 0/1-loss example, a positive margin δ permits some η > 0, but the largest valid η shrinks to zero as δ approaches zero.At δ = 0, equal-risk predictors violate the uniqueness consequence of PPC.Source: §3.1 · pp. 17–18

3.2 Equivalence of Central and Pseudoprobability Convexity Conditions

• Under Assumption A, the weak and strong central and PPC conditions are equivalent; without it, bounded loss suffices for the reverse implication.The central condition implies PPC without additional assumptions.Source: §3.2 · pp. 18–19

3.3 Interpretation as Convexity of the Set of Pseudoprobabilities and a Bayesian Interpretation

• PPC expresses directional convexity: mixtures of model elements need not be globally in the model, but cannot outperform its best element relative to P.For log loss, the Bayesian predictive distribution is a mixture, so the condition rules out its being strictly better than the best single model element in expected log loss or KL-divergence.Source: §3.3 · pp. 20, 22
• For log loss, the central and PPC conditions are equivalent, and the Bayes-MDL condition can support convergence to the KL-best model element under misspecification.The section identifies this as the condition implicitly used in several Bayesian and MDL convergence proofs.Source: §3.3 · pp. 20–21

4.2.1 Generalization of Vovk’s Mixability and Fast Rates for Stochastic Prediction with Expert Advice

• Vovk’s mixability implies strong stochastic mixability, but 0/1 loss can satisfy the central condition without satisfying stochastic mixability.For the stated 0/1-loss problem, no η > 0 gives stochastic mixability, whereas δ > 0 allows the η-central condition for some η > 0.Source: §4.2.1 · pp. 23–24
• Stochastic mixability implies fast expected regret in stochastic prediction with expert advice, even when losses are unbounded, but online-to-batch conversion alone need not yield fast rates in probability.An example has O(1/n) expected risk but only ≍1/√n risk in probability after conversion.Source: §4.2.1 · p. 24, §4.3.3 · p. 29

4.2.2 Special Case: Stochastic Exp-concavity

• Stochastic exp-concavity is stochastic mixability with the mean as substitution function; unlike mixability generally, exp-concavity depends on the parametrization.The JRT-II condition implies strong stochastic exp-concavity when Fd ⊇ co(F).Source: §4.2.2 · p. 25, §4.2.3 · p. 26

4.2.4 Relation to Audibert’s Condition

• A special case of Audibert’s variance inequality is equivalent to strong stochastic mixability.Source: §4.2.4 · p. 26

4.3.2 Predictor Implies Stochastic Mixability

• The predictor condition implies stochastic mixability without additional assumptions.The implication preserves η and the ε tolerance, including for the strong versions.Source: §4.3.2 · p. 27

4.3.3 Stochastic Mixability Implies Pseudoprobability Convexity

• Under weak Assumption B, stochastic mixability implies pseudoprobability convexity up to any δ > ε; with Assumption A and strong mixability, it implies strong pseudoprobability convexity.When Fd = co(F), this extends the relevant convexity condition from pseudoprobabilities to F itself when F is convex in the direction facing P.Source: §4.3.3 · pp. 28–29

4.3.4 The Central Condition Implies the Predictor Condition

• Under a minimax assumption, the central condition implies the predictor condition, with the exact implication depending on the relation between F and Fd and on Assumption B.For F = Fd, a central condition up to ε yields the predictor condition up to any δ > ε; another result applies when F ⊇ Fd and strong Assumption B holds.Source: §4.3.4 · p. 30
• Under a minimax assumption, the central condition implies the predictor condition; together with the reverse links, this connects statistical and online fast-rate conditions under appropriate assumptions.The implication holds with Fd = F when the central condition holds; a second version uses strong Assumption B and F ⊇ Fd.Source: §4 · p. 22, §4.3.4 · p. 30
• Under Assumption D for every Π, the weak η-central condition implies the weak η-predictor condition when F = Fd or strong Assumption B holds with F ⊃ Fd.Assumption D requires a Polish outcome space, continuous nonnegative losses, convexity conditions, and convex tight P, plus a closure or total-boundedness and equicontinuity alternative.Source: §4.3.4 · pp. 32–33
• For logarithmic loss, Assumption D yields 1-stochastic mixability under convexity, tightness, and a positive density lower bound, although mixability also holds without those restrictions.The example notes that Assumption D is not straightforward to verify when the lower bound is zero.Source: §4.3.4 · p. 33
• For 0/1 loss, the η-central condition can hold while η-stochastic mixability fails, with nonconvexity of F = Fd causing Assumption D to fail.Source: §4.3.4 · p. 33
• For squared loss on restricted Z = F = Fd = [−B, B], Assumption D holds and classical η-mixability at η = 1/B^2 leads through the theorem to the weak η-predictor condition.Source: §4.3.4 · p. 34
• For squared loss on Z = R with convex mixtures of unit-variance normals whose means lie in [−M, M], η-centrality holds for η ≤ 1/(1 + M^2), and Assumption D yields the weak predictor condition.Even with F = R, the implication follows by using Fd = [−B, B] for B ≥ M and the strong version of Assumption B; the authors note classical mixability analysis does not apply to this unbounded-domain case.Source: §4.3.4 · pp. 34–35

5.1 The v-Conditions and the Bernstein Condition

• For bounded losses under Assumption A, generalized Bernstein, v-central, and v-PPC conditions are essentially equivalent when v(x)u(x)=c x near zero.In particular, the (1, B)-Bernstein condition and η-central condition are equivalent for η=c/B, up to the distinction between second moment and variance.Source: §5.1 · pp. 36–37
• Under the v-central condition, rates are O(w(1/n)); v(ε)=ε^(1−β) yields O(n^(−1/(2−β))), while constant v yields O(1/n).Here w is the inverse of x ↦ x v(x); a v linear near zero gives only the standard O(1/√n) slow rate.Source: §5.1 · p. 38

5.2 Bernstein vs. Central Condition for Unbounded Losses - Two-sided vs. One-sided Conditions

• For unbounded losses, one-sided centrality can hold with fast ERM rates when Bernstein fails, while polynomial tails can permit u-Bernstein but rule out every allowed v-central condition.The section also notes that v-PPC and v-stochastic mixability do not require exponential tails, leaving open whether u-Bernstein implies v-stochastic mixability with u(x)·v(x) ≍ x.Source: §5.2 · pp. 39–41

5.3 v-Stochastic Mixability and the JRT Conditions

• The JRT-I condition of Juditsky et al. (2008) implies v-stochastic exp-concavity; in their regression example, v(ε)=O(ε^(2/s)) and the resulting rate matches the minimax rate.Their example assumes finite F, uniformly bounded predictors, and a finite s-th moment for the response.Source: §5.3 · p. 42

5.4 The v-Central Condition and Existence of Unique Risk-Minimizers

• For bounded losses under Assumption A, nontrivial v-centrality is equivalent to essential uniqueness of the risk minimizer; trivial-only v-centrality corresponds to essential non-uniqueness.Essential uniqueness means predictors whose risks approach the minimum also have loss differences from the minimizer whose variance approaches zero.Source: §5.4 · p. 43
• For some ε > 0, (ℓ, {P}, Fε) fails the η-central condition for every η > 0.The proof links failure of a u-Bernstein condition with u(x) tending to zero to essential non-uniqueness, then uses a sequence of hypotheses with variance bounded below and risks approaching the optimum to show central-condition failure.Source: §5.4 · p. 43
• Under the stated v-condition, the v-PPC condition yields a u-Bernstein condition with u(x) tending to zero, which implies that f* is essentially unique.The proof then uses the Bernstein condition to show that, for every ε > 0, sufficiently high-variance hypotheses have risk gap bounded away from zero.Source: §5.4 · p. 43
• For every ε > 0, the class containing f* and hypotheses with variance at least ε satisfies an η-central condition for some η > 0.The proof obtains this by placing the variance-threshold set inside a set of hypotheses whose risk gap is at least some δ > 0.Source: §5.4 · p. 43

6. From Fast Rates for Actions to Fast Rates for Functions

• Stochastic mixability transfers to the conditional setting when the induced substitution function is measurable and belongs to the conditional decision set.The construction applies the unconditional substitution function separately at each feature value.Source: §6 · p. 44
• More generally, stochastic exp-concavity transfers when the conditional decision set contains the convex hull of the conditional model.In this case, stochastic exp-concavity also holds in the conditional setting up to the same ε.Source: §6 · p. 44
• For squared loss on a bounded domain, exp-concavity transfers to conditional regression when the decision set contains the convex hull of the regression model, even if the model is misspecified.If the model is also convex and satisfies Assumption A, the decision set may equal the model, recovering the setting of Lee et al. (1998).Source: §6 · p. 45
• For stochastic exp-concavity, the conditional central condition can follow when the conditional model is convex, rather than containing all measurable functions.This stronger conclusion is illustrated by the squared-loss example.Source: §6 · p. 45

7.3 Fast Rates

• Under bounded losses, the strong central condition gives an exact oracle inequality with an O(1/n) fast rate for finite classes and extends to VC-type classes.The direct argument improves constants and dependence on the loss upper bound compared with routes through the Bernstein condition.Source: §7 · p. 46, §7.3 · pp. 49–50

7. The Central Condition Implies Fast Rates

• The proof bounds the probability that ERM selects a high-excess-risk function by controlling the cumulant generating function of negative excess loss.It uses the Cramér-Chernoff method and formulates the CGF bound as a general moment problem.Source: §7 · p. 46

7.1 The Strong Central Condition and ERM

• The analysis assumes a fixed distribution, bounded losses, and a strong η-central condition; the excess loss is measured relative to an F-optimal predictor.The section considers losses in [0, V].Source: §7.1 · p. 46

7.2 Semi-infinite Linear Programming and the General Moment Problem

• The CGF bound is obtained by maximizing over excess-loss random variables satisfying the stated constraints, using a semi-infinite linear program from the general moment problem.The approach first treats a canonical bounded range and then extends to general bounded loss ranges.Source: §7.2 · p. 47

7.3 Fast Rates

• The central condition also yields intermediate rates for finite classes when v is nonconstant, rather than only the O(1/n) rate associated with constant v.The rate is expressed through the inverse of x ↦ xv(x).Source: §7.3 · p. 50

• The paper identifies the central condition and stochastic mixability as two main fast-rate conditions that subsume many earlier conditions, with sufficient assumptions making four conditions equivalent.Source: §8 · p. 51
• For fixed η > 0, most implications hold under weak assumptions, including for unbounded losses, but central ⇒ predictor requires tightness and convexity of P.An example shows that this implication can sometimes hold even when P is neither tight nor convex.Source: §8 · p. 51
• Theorem 4.17 requires a convex decision set, which excludes ordinary 0/1 and classification losses; a randomized absolute-loss extension has a convex decision set.The extension interprets the loss as the expected 0/1 loss under a randomized decision.Source: §8 · p. 51
• For bounded losses, the four v-conditions imply each other up to constant factors, but for unbounded losses v-stochastic mixability and v-PPC may hold while v-central fails.The cited examples involve decision problems with polynomial rather than exponential loss tails.Source: §8 · p. 51
• For bounded losses, central-condition fast rates are linked to unique risk minimizers, while the corresponding connection for unbounded losses remains open.The discussion also questions whether the η-central condition can be too strong when minimizers are nonunique.Source: §8 · p. 52
• The paper proves that stochastic mixability yields fast rates without further conditions, but establishes central-condition fast rates only for bounded losses.For unbounded log-loss, it reports weaker rates in terms of Rényi and squared Hellinger distance; standard rates may require additional moment conditions.Source: §8 · p. 52
• The paper uses “fast” to mean rates of order 1/n, but whether its condition-based algorithms attain minimax-optimal rates remains unresolved.The discussion singles out minimax analysis over all proper learning algorithms as unexplored.Source: §8 · p. 52

• Under Assumption A, the proof chooses an optimal f* for each P and tests pseudoprobability convexity on mixtures of f* and an arbitrary f to derive the strong η-central condition.Convexity of the negative logarithm makes the mixture objective convex, and its minimum at λ = 0 yields a nonnegative right derivative.Source: §A.1 · pp. 53–54
• For bounded loss, the proof first obtains an approximate central-condition bound from pseudoprobability convexity, then uses λ = √γ and a sufficiently small γ to conclude the condition for any ε > 0.The proof handles the two cases separately, beginning with the bounded-loss case after treating Assumption A.Source: §A.1 · p. 54

• The proof invokes a minimax theorem for convex, tight, weakly closed distribution sets and bounded-above upper-semicontinuous losses.Source: §A.2 · p. 55
• Because ξ may be unbounded above, the proof truncates it at b, applies the minimax result to the continuous truncation, and then controls the truncation error.Continuity in z follows from continuity of the losses and dominated convergence; the proof seeks a b making the error at most ε.Source: §A.2 · p. 55
• Uniform integrability controls the tail uniformly, while compact sets and finite nets approximate the decision set under uniform equicontinuity.Convexity of e^(ηℓ_f(z)) and Jensen’s inequality compare the loss at the mean decision with the average loss.Source: §A.2 · p. 56

• The u-Bernstein condition yields the central-condition bound by applying a variance-based exponential-moment inequality to the excess loss.The proof sets X = ℓ_f(Z) − ℓ_f*(Z), uses η = v(ε), and treats ε = 0 separately.Source: §A.3 · pp. 56–57
• The v-PPC condition yields the Bernstein bound by testing it on an equal-mass mixture of an optimal f* and an arbitrary f, then taking expectations over Z.For each fixed z, the proof defines a mixture-based quantity ε_z and uses the PPC inequality to bound its expectation by ε.Source: §A.3 · p. 57

Var

• For ε equal to the expected excess loss, the result follows when η = u(ε) > 0 and η = v(ε).The passage sets ε = E[ℓ_f(Z) − ℓ_f*(Z)] ≥ 0 and substitutes these values into the bound.Source: Var · p. 58
• When η = 0, ε must be zero, and the argument instead bounds the left-hand side by an infimum over ε > 0.The infimum uses the expression 4ε/(κ(−2ab)v(ε)).Source: Var · p. 58

A.4 Proofs for Section 7

• A bounded random variable with positive mean can be modified downward to keep its mean arbitrarily close while making its exponential moment equal 1 at arbitrarily large η.The lemma assumes support on [−V, V] and limη→∞ E[exp(−ηZ)] < 1.Source: §A.4 · p. 58
• The construction couples the original distribution P to Qε so that Z′ ≤ Z almost surely, then chooses ε small and η large to obtain the target mean and exponential moment.The construction defines A := [µ, V] and A− := [−V, −µ].Source: §A.4 · pp. 58–59
• The convex hull W of g([−1, 1]) comprises the exponential curve, its endpoint chord, and the region between them; membership of k in W is equivalent to condition (53).Strict condition (53) characterizes membership in the interior of W.Source: §A.4 · p. 59
• For Theorem 7.3, Kemperman’s theorem yields an inequality required for all s ∈ [−1, 1], which is reparameterized as u(s) ≥ 0.The proof restricts the choice so the inequality is tight at s = 0, then changes variables to c1 and c2.Source: §A.4 · pp. 59–60

A.4.1 Constraints from the Local Minimum at 0

• Because u(0) = 0, a local minimum at zero requires its first and second derivatives to satisfy the stated constraints.Otherwise, for some small ε > 0, u(ε) or u(−ε) would be negative.Source: §A.4.1 · p. 60
• The proof then eliminates c1 from u(s) using the derivative constraints.The passage notes that η scaling is used to pursue an η-dependent rate.Source: §A.4.1 · p. 60

A.4.2 The Other Minima of u

• The derivative u′(s) has at most two roots, reducing the check of u(s) ≥ 0 to its minima and interval endpoints.The proof uses y = e^(ηs/2) to obtain a quadratic equation in y.Source: §A.4.2 · p. 61
• On [0, 1], u is nonnegative when it is nondecreasing; on [−1, 0], the proof requires u(−1) ≥ 0.The argument identifies the relevant turning point on the negative interval.Source: §A.4.2 · p. 61
• The proof uses κ(x) = (e^x − x − 1)/x^2 increasing in x to ensure c2 ≥ 1/4..Source: §A.4.2 · p. 61
• For η ≤ 1, the constraint is evaluated at η = 1, and nonnegativity is verified through g(η) and its positive derivative.The proof states g(0) = 0 and g′(η) > 0.Source: §A.4.2 · p. 61
• For η > 1, the proof imposes a condition that ensures nonnegativity across that range.The condition is derived for all η > 1.Source: §A.4.2 · p. 62
• The proof evaluates the relevant bound at η = 1 and as η → ∞ to select its minimum.It notes the derivative’s sign changes: positive at η = 1 and negative for sufficiently large η.Source: §A.4.2 · p. 62

A.4.3 Putting it All Together

• For the extremal case, two perturbations redistribute mass removed from negative outcomes; strict convexity then makes one perturbation’s mixability parameter smaller.This shows the first perturbed variable is not extremal, allowing Theorem 7.3 to be applied to its excess loss.Source: §A.4.3 · p. 63
• Rescaling bounded random variables preserves the constraints and shows that the maximal exponential moments bX and bY are equal.The proof compares variables on [−V, V] and [−1, 1] by scaling one by 1/V and the other by V.Source: §A.4.3 · p. 64
• Hyper-concentrated excess losses can be replaced by dominated losses with means arbitrarily close and finite, arbitrarily large mixability parameters, preserving the ERM comparison.The replacement loss is no greater almost surely, so its empirical risk is no greater.Source: §A.4.3 · p. 64
• Combining an individual probability bound with a union bound yields a high-probability guarantee that ERM excludes hypotheses above a derived excess-risk threshold.The stated probability is at least 1 − δ; the threshold expression is incomplete in these passages.Source: §A.4.3 · pp. 62, 64