Source-linked AI summary
Tighter PAC-Bayes Bounds Through Coin-Betting
Kyoungseok Jang, Kwang-Sung Jun, Ilja Kuzborskij, Francesco Orabona
TL;DR
Concentration for sample-dependent parameters is challenging because standard concentration arguments rely on independence. The paper uses coin-betting to construct a PAC-Bayes bound that is tighter in numerical comparisons and holds uniformly over sample sizes.
Problem
Classical concentration relies on independence, while learning problems may use parameters that depend on the sample, making concentration for their resulting sample averages the research challenge.
Source: §1 · pp. 1–2Method
The paper derives a PAC-Bayes concentration bound using coin-betting and states it uniformly over sample sizes, data-dependent posteriors, and data-free priors.
Source: §1 · pp. 2–3, §4 · p. 6Results
The bound is numerically tighter than prior approaches, can be relaxed to recover previous inequalities, and yields confidence sequences uniform over sample sizes.
Source: §1 · pp. 2–3Takeaways & Limitations
Its corollaries can be intersected without splitting δ, while retaining time-uniform PAC-Bayes confidence sequences.
Source: §1 · p. 3The upper bound lacks a closed-form minimizer, creating a trade-off between computational complexity and tightness.
Source: §7 · p. 13
Abstract
from arXiv · showhide
We consider the problem of estimating the mean of a sequence of random elements $f(X_1, \theta)$ $, \ldots, $ $f(X_n, \theta)$ where $f$ is a fixed scalar function, $S=(X_1, \ldots, X_n)$ are independent random variables, and $\theta$ is a possibly $S$-dependent parameter. An example of such a problem would be to estimate the generalization error of a neural network trained on $n$ examples where $f$ is a loss function. Classically, this problem is approached through concentration inequalities holding uniformly over compact parameter sets of functions $f$, for example as in Rademacher or VC type analysis. However, in many problems, such inequalities often yield numerically vacuous estimates. Recently, the \emph{PAC-Bayes} framework has been proposed as a better alternative for this class of problems for its ability to often give numerically non-vacuous bounds. In this paper, we show that we can do even better: we show how to refine the proof strategy of the PAC-Bayes bounds and achieve \emph{even tighter} guarantees. Our approach is based on the \emph{coin-betting} framework that derives the numerically tightest known time-uniform concentration inequalities from the regret guarantees of online gambling algorithms. In particular, we derive the first PAC-Bayes concentration inequality based on the coin-betting approach that holds simultaneously for all sample sizes. We demonstrate its tightness showing that by \emph{relaxing} it we obtain a number of previous results in a closed form including Bernoulli-KL and empirical Bernstein inequalities. Finally, we propose an efficient algorithm to numerically calculate confidence sequences from our bound, which often generates nonvacuous confidence bounds even with one sample, unlike the state-of-the-art PAC-Bayes bounds.
1. Introduction
The paper studies concentration for sample-dependent parameters, where classical concentration arguments based on independence do not directly apply. It introduces a coin-betting PAC-Bayes bound that is numerically tighter than prior approaches and holds uniformly over sample sizes.
1. Introduction
- The target is the concentration of a sample average of f(θ, X_i) around its mean when θ may depend on the sample; f can represent a learning loss.In that example, the mean is the statistical risk.Source: §1 · pp. 1–2
- Classical uniform concentration bounds address sample dependence by holding over compact parameter sets, but can be vacuous for overparameterized neural networks.Their capacity terms include VC dimension, metric entropy, or Rademacher complexity.Source: §1 · p. 2
- PAC-Bayes instead considers data-dependent posterior distributions and data-free priors, replacing a capacity term with posterior-to-prior KL divergence.The paper frames its target as a bound uniform over data-dependent posteriors.Source: §1 · p. 2
- Coin-betting yields a PAC-Bayes bound that is numerically tighter than prior approaches and, with its corollaries, supports time-uniform confidence sequences.The bound can be relaxed to recover earlier results; its implications can be intersected without splitting δ.Source: §1 · pp. 2–3
- The new inequality holds with probability at least 1 − δ simultaneously for every sample size, data-dependent posterior, and data-free prior.Its mean-function constraint is convex, making the resulting optimization efficiently solvable in some cases.Source: §1 · p. 3
2. Related Work
The related work traces concentration from online betting regrets and reviews successive PAC-Bayes refinements. The paper positions its result as recovering prior inequalities by relaxation while addressing time-uniform bounds.
Concentration from coin-betting
- Online betting regret guarantees have been used to derive concentration inequalities, building on work connecting online linear algorithm regret to martingale tail bounds.The coin-betting formalism has roots in Ville’s framework and Kelly betting, with links to Universal Portfolio theory.Source: §2 · pp. 3–4
PAC-Bayes
- PAC-Bayes empirical Bernstein bounds are variance-dependent, and the paper recovers Tolstikhin and Seldin’s inequality by relaxing its main result.Sample splitting can make bounds data-dependent; more intricate variance-splitting bounds are among the numerically tightest known, though their problem-dependent nature makes theoretical comparison challenging.Source: §2 · p. 4
- The main proof uses a martingale property of optimal log-wealth, while prior PAC-Bayes martingale methods have relaxed independence or boundedness assumptions.Ville’s inequality has also been used to obtain bounds uniform over sample size.Source: §2 · p. 4
- The paper’s inequality has a different shape from McAllester’s bound and can be relaxed to obtain it; whether a Gibbs predictor is optimal for the new inequality remains open.The paper notes Gibbs predictors may be suboptimal for Eq. (1).Source: §2 · p. 4
3. Definitions
The definitions section fixes notation for positive parts and KL divergence, then formalizes data-dependent distributions as probability kernels.
3. Definitions
- For probability measures P ≪ Q, KL(P, Q) is defined through the log density ratio integrated with respect to P.The section also writes KL(p∥q) for densities with respect to a common σ-finite measure.Source: §3 · p. 5
- A data-dependent distribution is formalized as a probability kernel mapping each sample to a probability measure over Θ.Evaluating such a kernel at S is denoted P_n = P(S).Source: §3 · p. 5
4. Warm-up: From Betting To Concentrations
This section derives concentration inequalities from online betting regret. Lower-bounding wealth yields familiar fixed-time bounds, while retaining wealth and using Ville’s inequality gives tighter time-uniform bounds.
4. Warm-up: From Betting To Concentrations
- A bettor’s wealth is compared with that of a fixed betting fraction, and regret bounds quantify the gap without requiring the betting algorithm to be run.The framework treats coin outcomes as arbitrary, making the setup an online game.Source: §4 · pp. 5–6
- Avoiding a lower bound on wealth preserves a tighter inequality, which can be numerically inverted to obtain a tighter concentration bound.This trades a closed-form expression for numerical inversion.Source: §4 · p. 6
- Because betting wealth is a nonnegative martingale, Ville’s inequality yields a high-probability concentration guarantee that holds uniformly over time.This replaces the Markov-inequality step in the earlier approach.Source: §4 · p. 6
- The implicit bound gives upper and lower bounds on the mean by solving a one-dimensional quasi-convex condition, and is a tight version of empirical Bernstein concentration for bounded variables.The passage compares this relationship to the KL-divergence bound as an implicit, tight version of Bernstein concentration for Bernoulli variables.Source: §4 · p. 6
5. Main Results
Theorem 1 gives a PAC-Bayes confidence sequence for data-dependent posteriors, holding simultaneously across sample sizes. Its relaxations recover established PAC-Bayes inequalities, and the paper describes a convex procedure for computing confidence intervals from the bound.
5. Main Results
- Theorem 1 bounds data-dependent posteriors simultaneously across sample sizes with high probability, extending the concentration analysis to the PAC-Bayes setting.The parameter is a data-dependent distribution over Θ, while the prior is independent of the sample.Source: §5 · p. 7
- Relaxing Theorem 1 recovers McAllester’s inequality up to constants and extends it to hold uniformly for all sample sizes.The result is stated for all priors and data-dependent distributions.Source: §5 · pp. 7–8
- The relaxed Bernoulli-KL bound matches Maurer’s inequality up to a constant inside a logarithmic factor, while a further relaxation is reported tighter.The tighter comparison is confirmed numerically in Section 6.Source: §5 · p. 8
- Relaxing Theorem 1 recovers the PAC-Bayes empirical Bernstein result up to constants through a simpler proof.The inequality is fully empirical and non-vacuous when Cn,δ ≤ n/2.Source: §5 · p. 8
5.1. How to compute confidence intervals from Eq. (4) numerically
- The confidence-interval optimization is convex and gives valid bounds because Theorem 1 holds for every data-dependent posterior.The optimization is over means in the class of means of the given distribution.Source: §5.1 · p. 9
5.1.1. MONTE CARLO APPROXIMATION OF THE INTEGRAL
- For continuous or prohibitively large parameter spaces, Monte Carlo approximation can estimate the integrals needed to compute the intervals.Finite parameter spaces instead permit replacing integrals with summations.Source: §5.1.1 · p. 9
- Monte Carlo constraints are expected to loosen with small m; finite raw second moment suggests m = n^2 as a reasonable choice, while infinite moment makes estimation infeasible.The sample average converges asymptotically when n is of order o(m).Source: §5.1.1 · p. 10
5.2. Proof of Theorem 1
- The proof uses a betting algorithm’s wealth and regret bounds, then applies Ville’s inequality and a change-of-measure inequality to control all posteriors.The prior’s independence from the sample supports the change-of-measure step.Source: §5.2 · pp. 10–11
6. Experiments
In two synthetic settings, the proposed confidence intervals are consistently tighter than the PAC-Bayes baselines. The guarantee and KL-ver hold uniformly over time, unlike the fixed-sample baseline guarantees.
6. Experiments
- The proposed confidence intervals are consistently tighter than the baselines in both synthetic experiments, with the guarantee holding uniformly over time.KL-ver also holds uniformly over time; the baselines hold for a fixed number of samples.Source: Figure 2 · p. 12, §6 · pp. 12–13
- Experiments compare Proposition 7 with PAC-Bayes baselines and KL-ver across two synthetic environments, averaging bounds over 20 repetitions per sample size.Sample sizes range over n ∈ {2^c : c = 1, …, 15}.Source: §6 · p. 12
- KL-ver replaces the log-wealth term with n · KL(μ̂θ, μθ), making it looser than the proposed method but tighter than Maurer’s bound.It matches the proposed bound in the Bernoulli case and is worse than it but very close to Maurer’s bound in the Binomial case.Source: §6 · pp. 12–13
- The Bernoulli experiment uses Xi ∼ Bernoulli(1/2), while the Binomial experiment uses Xi ∼ N(0, 1) and a transformed error-function predictor.The prior and posterior distributions differ between the two settings.Source: §6 · p. 12
7. Conclusions, limitations, and future work
The paper presents a coin-betting-based PAC-Bayes bound that implies previous results and is tighter in numerical simulations. Its upper bound lacks a closed-form minimizer, leaving computational complexity and tightness in trade-off.
7. Conclusions, limitations, and future work
- The coin-betting-based PAC-Bayes upper bound implies previous PAC-Bayes results and is tighter in numerical simulations.The authors identify further characterization of the trade-off as future work.Source: §7 · p. 13
- The upper bound lacks a closed-form minimizer such as the Gibbs measure, creating a trade-off between computational complexity and tightness.The authors propose characterizing this trade-off, potentially through its Pareto frontier.Source: §7 · p. 13
A.1. Proof of Proposition 2
The appendix proves McAllester’s inequality using Theorem 1 and establishes the proposition used for the Bernoulli-KL result. The latter proposition attains equality for Bernoulli-valued observations.
A.1. Proof of Proposition 2
- The proof of McAllester’s inequality applies Theorem 1 after bounding the relevant interval using μθ ∈ [0, 1].The proof then concludes the proposition.Source: §A.1 · p. 17
A.2. Proof of Proposition 3
- Proposition 11 gives an inequality for observations in [0, 1], and equality holds when the observations are Bernoulli-valued.The proposition defines the empirical mean and the common expectation of the observations.Source: §A.2 · p. 18
- Combining Proposition 11 with Theorem 1 yields a high-probability result simultaneously for all sample sizes and data-dependent distributions.The proof uses exchange of summation and integration and the log-sum inequality.Source: §A.2 · p. 18
A.3. Proof of Proposition 4
The appendix proves Proposition 4 through a relaxation argument and supporting inequalities, then establishes convexity and block-based concentration results used in later propositions.
A.3. Proof of Proposition 4
- The Proposition 4 proof follows Orabona and Jun (2021, Theorem 6), applying a lower bound, Jensen’s inequality, a lemma, and Theorem 1 before solving for the bound.It sets ϵθ = µθ −ˆµθ, with ϵθ + ˆµθ ∈[0, 1].Source: §A.3 · pp. 18–19
A.4. Proof of Lemma 6
- The Lemma 6 proof establishes that f is a maximum of convex functions, concluding its convexity.It uses the range of g(b, c) and a lower bound on (x + z)² to support the argument.Source: §A.4 · pp. 19–20
A.5. Proof of Proposition 8
- For Proposition 8, non-negativity and Markov’s inequality are applied blockwise, and block independence yields a probability bound for at least one block.The proof notes that e can be replaced by any C > 1, giving probability 1 − C^-K.Source: §A.5 · p. 20
A.6. Proof of Proposition 7
- Proposition 7’s proof combines concentration events with a union bound to establish µ* ≤ MU with probability at least 1 − 3δ; the lower-bound proof is symmetric.The argument uses a KL-divergence concentration inequality and Proposition 8.Source: §A.6 · p. 21
Appendix B. Monte Carlo experiment
The appendix evaluates Algorithm 1 against Maurer’s bound using Monte Carlo approximation. Algorithm 1 outperforms Maurer’s bound with sufficient Monte Carlo samples, including as the number of data samples increases.
Appendix B. Monte Carlo experiment
- For Figure 3, n = 32 and m ranges over powers of two; for Figure 4, n ranges over powers of two and m = 256, with K = 4 and C = 2.1147.The Figure 3 m values are 2^c for c = 1,…,10; Figure 4 uses n = 2^c for c = 1,…,4.Source: Appendix B · p. 21
- The experiment uses prior P0 = N(0, 1), posterior Pn = N(0, 0.25), and i.i.d. samples drawn from N(0, 1).Source: Appendix B · p. 22
- To compare fairly, Maurer’s bound uses M = m · K Monte Carlo samples when Algorithm 1 uses m samples per group across K groups.Algorithm 2 describes the numerical computation of Maurer’s bound.Source: Appendix B · p. 22
- Proposition 13 gives a confidence width for Monte Carlo error, while Maurer’s bound is computed using the interval endpoints when only an interval for the posterior mean is available.The appendix says the KL property means only the two endpoints need to be checked.Source: Appendix B · pp. 22–23
- Algorithm 1 outperforms Maurer’s bound with sufficient Monte Carlo samples and continues to do so as the number of data samples increases (Figures 3–4).Figures 3 and 4 plot confidence width against Monte Carlo samples and number of samples, respectively.Source: Appendix B · p. 23, Figure 3 · p. 23, Figure 4 · p. 23