Source-linked AI summary
Online-to-PAC Conversions: Generalization Bounds via Regret Analysis
Gábor Lugosi, Gergely Neu
TL;DR
Generalization bounds seek to control the gap between training and test risk. This paper turns online regret analysis into bounds on a statistical learning algorithm’s generalization error, and recovers established guarantees while deriving extensions. The approach’s applications include bounds with data-dependent choices, though sharper control for sample-selected online learners can require nontrivial martingale analysis.
Problem
Statistical learning seeks bounds on the gap between empirical and test risk, the quantity used to measure an algorithm’s generalization error.
Source: §1 · p. 1Method
The framework constructs an online game whose comparator repeatedly uses the statistical algorithm’s output, making comparator cost equal to that algorithm’s generalization error.
Source: §1 · p. 2Results
The framework recovers classical PAC-Bayesian bounds and derives new extensions, including data-dependent fast-rate and parameter-free bounds.
Source: §1 · p. 3Takeaways & Limitations
Regret analysis offers an alternative to traditional combinatorial generalization-bound techniques and may open research directions in convex analysis and optimization.
Source: §5 · p. 21Sharper bounds for a sample-selected online learner can require nontrivial control of its martingale term; the paper leaves this further study open.
Source: §2 · p. 7
Abstract
from arXiv · showhide
We present a new framework for deriving bounds on the generalization bound of statistical learning algorithms from the perspective of online learning. Specifically, we construct an online learning game called the "generalization game", where an online learner is trying to compete with a fixed statistical learning algorithm in predicting the sequence of generalization gaps on a training set of i.i.d. data points. We establish a connection between the online and statistical learning setting by showing that the existence of an online learning algorithm with bounded regret in this game implies a bound on the generalization error of the statistical learning algorithm, up to a martingale concentration term that is independent of the complexity of the statistical learning method. This technique allows us to recover several standard generalization bounds including a range of PAC-Bayesian and information-theoretic guarantees, as well as generalizations thereof.
1. Introduction
The paper studies generalization error—the gap between test and training risk—and introduces an online-to-PAC framework that bounds it through regret analysis. The framework targets algorithm-dependent guarantees and recovers classical bounds while extending them to several settings.
1. Introduction
- Generalization error is the gap between test and training risk, a distinct target from excess risk that measures overfitting.The paper notes that low generalization error implies low excess risk when an algorithm fits the data nearly perfectly, and high-probability upper bounds can yield population-risk confidence intervals.Source: §1 · pp. 1, 3, 4
- The framework converts bounded regret in a generalization game into a bound on a statistical learning algorithm’s generalization error, without requiring implementation of the online learner.The comparator repeatedly plays the statistical algorithm’s output, making its accumulated cost equal to the generalization error.Source: §1 · p. 2
- The framework gives bounds uniformly over hypothesis distributions, paralleling PAC-Bayesian guarantees, and can also cover deterministic-output algorithms.Some results use Wasserstein distance, which can be bounded for degenerate prior and posterior distributions.Source: §1 · pp. 2–3
- Earlier online-learning approaches often bounded suprema as loose proxies, whereas this framework targets a given algorithm’s generalization error rather than a worst-case quantity.The paper also notes that worst-case regret can require bounded classical complexity and optimization over function spaces, which may be computationally intractable.Source: §1 · pp. 2–3
- The framework recovers McAllester’s classical PAC-Bayesian bound and derives data-dependent fast-rate bounds, a parameter-free bound, and extensions using strongly convex regularizers.It also gives empirical optimistic-FTRL bounds, a Wasserstein-2 and Sobolev-norm bound, and extensions allowing data-dependent priors and regularizers.Source: §1 · p. 3
2. Online-to-PAC Conversions
The online-to-PAC conversion constructs a game whose comparator cost is the learning algorithm’s generalization error. Regret bounds in that game therefore yield generalization bounds, with martingale concentration controlling the remaining term.
2. Online-to-PAC Conversions
- The generalization game uses the learning algorithm’s conditional output distribution as comparator, making the comparator’s accumulated cost equal to its generalization error.For deterministic algorithms, that conditional distribution is concentrated on the algorithm’s single output.Source: §2 · pp. 4–5
- Theorem 1 characterizes generalization error through online regret and a martingale term, so any online algorithm with bounded regret yields a generalization bound.The learner’s expected cost is zero each round because the generalization-gap costs have zero expectation for each fixed hypothesis.Source: §2 · pp. 5, 7
- High-probability bounds hold simultaneously for statistical learning algorithms against which the online learner has bounded regret, paralleling PAC-Bayesian uniformity over posteriors.The concentration argument uses the lower tail of a sum of nonnegative random variables; the text notes it need not assume uniformly bounded losses or light tails for that argument.Source: §2 · p. 6
- A finite class of N online learners permits choosing the best regret bound across the class, at the price of an additional term of order (log N)/n.A sharper bound may be possible by balancing regret and martingale terms, but controlling the martingale for a sample-dependent selected learner is nontrivial.Source: §2 · pp. 6–7
- Unlike worst-case-comparator approaches, the conversion directly bounds a given algorithm using an algorithm-specific comparator, avoiding reliance on uniform-convergence-type arguments.The cited comparison identifies Kakade, Sridharan, and Tewari as inspiration but notes their use of a worst-case comparator.Source: §2 · p. 7
- The generalization game is equally hopeless for all online learners: their expected costs are zero, so regret against the algorithm-dependent comparator is tied to generalization error up to martingale fluctuations.Consequently, a sublinear regret bound for one learner implies sublinear regret for the others in this game, up to those fluctuations.Source: §2 · pp. 7–8
3. Applications
This section applies the online-to-PAC framework to classical PAC-Bayesian bounds and guarantees from follow-the-regularized-leader methods. It also derives simultaneous generalization guarantees using smoothed relative-entropy regularization, including an explicit specialization based on a Wasserstein bound.
3.1.1. A VANILLA PAC-BAYES BOUND
- The vanilla multiplicative-weights result essentially recovers McAllester’s original PAC-Bayes bound.The fixed-learning-rate bound motivates a covered range of learning rates to address the data dependence involved in optimizing the rate.Source: §3.1.1 · p. 9
3.1.2. A PARAMETER-FREE BOUND
- Parameter-free online learning yields a PAC-Bayesian bound without logarithmic factors of n, a property the authors note is otherwise known only for countable classes.They derive it using a parameter-free regret guarantee, avoiding the learning-rate overhead of aggregating parametric bounds.Source: §3.1.2 · p. 10
3.1.3. A DATA-DEPENDENT BOUND
- The data-dependent PAC-Bayes bound uses a skewed cost surrogate to tighten martingale control and can achieve a 1/n fast rate when training error is zero.The authors note that the technique can also yield fast rates for other algorithms.Source: §3.1.3 · pp. 10, 12
3.2.1. STRONGLY CONVEX REGULARIZERS
- Strongly convex FTRL regularizers yield generalization bounds that recover the earlier PAC-Bayesian bounds when the regularizer is relative entropy to the prior.The section gives bounds for both fixed and covered choices of the learning rate.Source: §3.2.1 · pp. 12–13
3.2.2. EMPIRICAL BOUNDS VIA OPTIMISTIC FTRL
- Optimistic FTRL replaces an unobservable generalization-gap norm with the empirically measurable training-loss norm in its bound.The method uses the predictable test-loss component as its guess of the cost; optimistic methods tighten guarantees when the guess is close while retaining FTRL’s worst-case guarantees otherwise.Source: §3.2.2 · p. 13
3.2.3. EXAMPLE: p-NORM REGULARIZATION
- The p-norm regularization bounds are fully empirical, accommodate heavy-tailed losses, and have a slow rate n^-(1−1/q) when p > 2 and only a q-th moment is bounded for q < 2.Their confidence dependence is polylogarithmic in 1/δ; for p ∈ (1, 2], they interpolate toward the standard PAC-Bayes bound as p approaches 1, though the divergence bound worsens near 1. The guarantees require bounded ∥Pn − P1∥p,P1, a condition that becomes more stringent as p increases.Source: §3.2.3 · pp. 14–15
3.2.4. EXAMPLE: SMOOTHED RELATIVE-ENTROPY REGULARIZATION
- Smoothed relative-entropy regularization enables constant Gaussian perturbation levels for a class of smooth functions and keeps divergences bounded under milder support assumptions.The smoothing applies Gaussian noise to distributions before computing relative entropy and total variation.Source: §3.2.4 · p. 15
- Under a uniform second-moment bound σ², Corollary 13 gives a simultaneous high-probability generalization guarantee for all algorithms W_n = A(S_n).It applies for η > 0, γ ≥ 0, any prior P1, and n > 1.Source: §3.2.4 · p. 15
- For infinitely smooth functions with bounded directional derivatives, Lemma 14 upper-bounds the dual norm ∥f∥_{γ,*}, enabling the smooth-loss guarantee.The proof uses successive smoothing.Source: §3.2.4 · p. 16
- With infinitely smooth losses, β_j ≤ β, and γ < 1/d, Corollary 15 gives a simultaneous high-probability bound whose second term is of order ηβ.The authors note that similar PAC-Bayesian guarantees, to their knowledge, require perturbation levels that decay with n, limiting smoothing gains.Source: §3.2.4 · p. 16
- The inequality D_γ(P∥P′) ≤ 1/(2γ²) W₂²(P,P′) yields Corollary 16; when ∥w∥₂ ≤ R, its expected-error bound scales with R, β, d, and n.The corollary assumes infinitely smooth losses with β_j ≤ β and a uniform second-moment bound σ².Source: §3.2.4 · p. 16
- The authors find no directly comparable result; cited Wasserstein-1 guarantees require only bounded first derivatives but may not decrease with n, and removing d-dependence remains open.The cited works are Zhang et al. [87], Wang et al., and Rodríguez-Gálvez et al. [66].Source: §3.2.4 · p. 16
4. Extensions
The extensions introduce conditional online-to-PAC conversion, which lets the online learner use the full supersample, and derive both high-confidence and expected generalization guarantees. They also extend the framework to data-dependent priors and information-theoretic bounds, subject to conditions such as bounded losses.
4.1. Conditional online-to-PAC conversions
- Bounded losses are needed to bound the martingale increments almost surely because the online learner’s cost average is a martingale only conditioned on the entire supersample.The lower-tail term can use the milder condition of bounded second moments, but controlling the martingale average requires bounded losses.Source: §4.1 · pp. 18–19
- The conditional conversion lets the online learner know the full 2n-point supersample, enabling data-dependent learning rates and regularization, including priors that depend on the supersample.These almost exchangeable priors address the fixed-prior limitation shared with standard PAC-Bayes bounds.Source: §4.1 · pp. 17, 19
- The conditional framework recovers PAC-Bayesian guarantees with supersample-dependent priors and, with a special prior and an expectation relaxation, conditional information-theoretic bounds.The paper identifies these as recovering analogous results by Audibert and Steinke and Zakynthinou [75].Source: §4.1 · p. 19
4.2. Bounds on the expected generalization error
- The expected-error conversion yields bounds whose deterministic infimum avoids requiring sophisticated control of suprema of empirical processes.The authors describe this bound as weaker than previously discussed versions while emphasizing this advantage.Source: §4.2 · pp. 19–20
- The expected-error results recover mutual-information bounds of Xu and Raginsky [85], and the framework also extends earlier guarantees, including conditional mutual-information bounds.The paper states that other earlier guarantees can be adjusted analogously.Source: §4.2 · p. 20
5. Conclusion
The paper presents regret analysis as a flexible route to generalization bounds, recovering existing results and making some minor improvements. It also identifies open directions, including extending the framework beyond i.i.d. data and incorporating other concepts used to explain generalization.
5. Conclusion
- The online-to-PAC scheme links online and statistical learning through regret analysis and recovers several state-of-the-art generalization results, with minor improvements.The authors describe these applications as only a short list of what the framework may achieve.Source: §5 · p. 20
- Unlike traditional combinatorial arguments over empirical-process suprema, the approach uses regret analysis and needs only existence of suitable online algorithms, not their implementation.The paper connects this approach to tools from convex analysis and optimization.Source: §5 · p. 21
- The framework may extend beyond i.i.d. data, but stationary-data generalization is proposed as a straightforward adjustment while broader out-of-distribution settings remain open.The authors state that dropping further probabilistic assumptions would require designing appropriate notions of generalization.Source: §5 · p. 21
- Extensions to stability, differential privacy, and margin or noise conditions are left for future work.The paper presents these as concepts its framework may capture, not as established results.Source: §5 · p. 21
A.1. Exponentially weighted averaging
This appendix adapts a classic exponentially weighted average forecaster to bound regret against a comparator over arbitrary cost sequences. Its proof uses a potential function together with variational and concentration inequalities.
A.1. Exponentially weighted averaging
- The exponentially weighted average forecaster’s regret bound adapts classic results of Vovk, Littlestone and Warmuth, and Freund and Schapire.The bound is stated for any sequence of cost functions.Source: §A.1 · p. 27
- For any sequence of cost functions, the forecaster satisfies a regret bound against a comparator.The supplied passage states the scope but does not provide the bound’s expression.Source: §A.1 · p. 27
- The proof studies a potential function, applies the Donsker–Varadhan variational formula, and bounds a term using Hoeffding’s lemma.The paper cites Boucheron et al. for both tools.Source: §A.1 · p. 27
A.2. Optimistic Second-Order EWA
The optimistic second-order EWA method uses guesses of the costs alongside auxiliary and actual update sequences. Its second-order adjustment supports data-dependent, comparator-dependent regret bounds that can help derive fast generalization rates.
A.2. Optimistic Second-Order EWA
- The optimistic EWA method uses a guess of each cost when choosing its action and calculates auxiliary and actual update sequences.The auxiliary sequence includes a second-order adjustment.Source: §A.2 · p. 28
- The second-order adjustment supports fully data-dependent, comparator-dependent regret bounds and eliminates test error from the resulting generalization bounds.The auxiliary update sequence draws on optimistic online learning algorithms.Source: §A.2 · p. 28
- Choosing costs as loss minus expected loss and hints as negative expected loss makes the theorem’s final term negative, helping derive a fast rate.The proof uses an auxiliary cost adjusted by the squared difference between cost and hint.Source: §A.2 · p. 28
A.3. Follow the Regularized Leader
The section develops regret bounds for FTRL and optimistic FTRL using convex potentials and regularizer properties. It states the FTRL result at a level of generality beyond the finite-dimensional settings covered by the proofs the authors know.
A.3. Follow the Regularized Leader
- Under properness and strong convexity, the FTRL update’s minimizer exists and is unique.Existence follows from lower semicontinuity and compactness; strong convexity gives uniqueness.Source: §A.3 · p. 29
- Theorem 24 gives a regret bound for FTRL when the regularizer is strongly convex, for arbitrary sequences of cost functions.The proof uses a potential related to comparator cost and a duality property between the regularizer and its conjugate.Source: §A.3 · pp. 29–30
- The authors state that Theorem 24 extends beyond finite-dimensional vector spaces; they identify Alquier [1] as an exception for the special case of an f-divergence.Their proof follows standard arguments.Source: §A.3 · p. 29
A.3.1. OPTIMISTIC FTRL
- Optimistic FTRL incorporates a sequence of hints into its updates and has a regret guarantee for cost and prediction sequences.The proof bounds potential changes using convexity and the smoothness implied by strong convexity of the regularizer.Source: §A.3.1 · pp. 30–31
A.3.2. THE PROOF OF COROLLARY 12
The corollary proof uses a uniformly convex regularizer to obtain a regret bound, then controls a martingale term with a probability guarantee.
A.3.2. THE PROOF OF COROLLARY 12
- A p-uniformly convex regularizer yields an FTRL regret bound under the weaker convexity condition described in the proof.The passage identifies the choice h(P) = ∥P − P1∥_p^p for p ≥ 2.Source: §A.3.2 · pp. 31–32
- The proof controls the remaining martingale term using a concentration lemma, obtaining a bound that holds with probability at least 1 − δ.The stated probability guarantee applies for any λ > 0.Source: §A.3.2 · p. 32
B.1. Martingale concentration inequalities
This appendix provides concentration bounds for sums of nonnegative random variables, including a heavy-tailed extension and an empirical variant for bounded variables.
B.1. Martingale concentration inequalities
- The appendix presents a concentration inequality for lower tails of sums of nonnegative random variables with bounded second moments.It is used several times in the proofs.Source: §B.1 · p. 32
- An empirical variant of the preceding bound applies when the random variables are supported on [0, 1].The variables are assumed to have finite conditional means.Source: §B.1 · pp. 32–33
- For nonnegative variables with finite conditional means and q-th moments, the appendix gives a probability bound for q ∈ (1, 2].The bound is stated for any λ > 0 and holds with probability at least 1 − δ.Source: §B.1 · p. 33
B.2. Strong-convexity / smoothness duality
This section proves a strong-convexity/smoothness duality result for a function and its Legendre–Fenchel conjugate. The proof bounds differences between conjugate subgradients and relates conjugate-value differences to Bregman divergence.
B.2. Strong-convexity / smoothness duality
- Lemma 29 assumes h is α-strongly convex with respect to ∥·∥ and concerns its Legendre–Fenchel conjugate h*.The supplied lemma statement does not include its full conclusion.Source: §B.2 · p. 34
- α∥P − P′∥² ≤ ⟨P − P′, f − f′⟩ ≤ ∥P − P′∥·∥f − f′∥*, bounding the difference between conjugate subgradients.The proof combines first-order optimality with strong convexity and then applies the dual-norm inequality.Source: §B.2 · p. 34
- The proof expresses h*(f) − h*(f′) using a convex-function mean-value argument along fλ = λf + (1 − λ)f′, citing Hiriart-Urruty and Lemaréchal.It selects subgradients of h* along the segment and then uses the definition of the Bregman divergence to complete the proof.Source: §B.2 · p. 34
B.3. The proof of Lemma 14
The proof uses successive smoothing to control a dual-norm bound. It relates the residual terms to derivatives of the original function and uses Gaussian averaging in that step.
B.3. The proof of Lemma 14
- The proof bounds a dual norm by expanding it into terms involving successively smoothed residuals.The residuals are defined recursively by f₀ = f and fⱼ₊₁ = fⱼ − G*σfⱼ; the displayed expansion includes terms paired with P − P′.Source: §B.3 · p. 35
- Residuals from successive smoothing decay at a rate determined by higher-order derivatives of the original function f.The proof introduces a Gaussian vector ξ distributed as N(0, σ²I) when relating residual norms to derivatives.Source: §B.3 · p. 35
- The proof combines the derivative-related estimate with the previous bound to complete the claim.The passage identifies Hölder’s inequality as the step bounding the dual norm.Source: §B.3 · p. 35
B.4. Wasserstein distance and smoothed relative entropy
This section defines squared Wasserstein-2 distance using couplings and presents a bound on smoothed relative entropy in terms of that distance. The proof uses a coupling of the distributions and the relative entropy between Gaussians with a common covariance.
B.4. Wasserstein distance and smoothed relative entropy
- Squared Wasserstein-2 distance between P and P′ is defined using the infimum over joint distributions on W × W with marginals P and P′.The definition is given for Euclidean distance on Rd; the text refers to Villani for a more general treatment.Source: §B.4 · p. 35
- Lemma 30 bounds the smoothed relative entropy between P and P′ in terms of their squared Wasserstein-2 distance for any σ > 0.The supplied lemma statement does not include the bound’s formula.Source: §B.4 · p. 36
- The proof fixes a coupling, applies Jensen’s inequality and joint convexity of relative entropy, then takes the infimum over couplings.It uses D(N(x, Σ)∥N(y, Σ)) = 1/2 ∥x − y∥²Σ⁻¹ for symmetric positive definite Σ; the proof is largely based on Neu et al. [53].Source: §B.4 · p. 36