PaperlayerView exact revision on arXiv

Source-linked AI summary

User-friendly introduction to PAC-Bayes bounds

Pierre Alquier

arXiv:2110.11216v6stat.MLcs.LGmath.ST

TL;DR

PAC-Bayes theory addresses how randomized and aggregated predictors generalize, but an elementary introduction remains needed. This paper introduces PAC bounds and related tools, explains improved and localized formulations, and reports applications ranging from tight certificates to neural networks.

  • Problem

    An elementary introduction to PAC-Bayes theory is needed to explain generalization for randomized and aggregated predictors when the data distribution is unknown.

  • Method

    The paper introduces PAC bounds for randomized and aggregated predictors and develops PAC-Bayes, mutual-information, and localized-bound perspectives.

  • Results

    PAC-Bayes bounds range from vacuous certificates to tight results, including a 0.0279 MNIST bound and state-of-the-art MNIST test error of 0.02.

  • Takeaways & Limitations

    Appropriate PAC-Bayes inequalities can yield 1/n bounds in noiseless settings and support informative neural-network generalization certificates.

  • Takeaways & Limitations

    Some PAC-Bayes bounds cannot be optimized directly over λ because their optimal value depends on the sample size, while joint minimization in λ and ρ may be difficult.

Abstract

from arXiv · show

Aggregated predictors are obtained by making a set of basic predictors vote according to some weights, that is, to some probability distribution. Randomized predictors are obtained by sampling in a set of basic predictors, according to some prescribed probability distribution. Thus, aggregated and randomized predictors have in common that they are not defined by a minimization problem, but by a probability distribution on the set of predictors. In statistical learning theory, there is a set of tools designed to understand the generalization ability of such procedures: PAC-Bayesian or PAC-Bayes bounds. Since the original PAC-Bayes bounds of D. McAllester, these tools have been considerably improved in many directions (we will for example describe a simplified version of the localization technique of O. Catoni that was missed by the community, and later rediscovered as "mutual information bounds"). Very recently, PAC-Bayes bounds received a considerable attention: for example there was workshop on PAC-Bayes at NIPS 2017, "(Almost) 50 Shades of Bayesian Learning: PAC-Bayesian trends and insights", organized by B. Guedj, F. Bach and P. Germain. One of the reason of this recent success is the successful application of these bounds to neural networks by G. Dziugaite and D. Roy. An elementary introduction to PAC-Bayes theory is still missing. This is an attempt to provide such an introduction.

5 Beyond “Bounded Loss” and “i.i.d. Observations”

Section 5 covers PAC-Bayes analysis beyond bounded losses and independent observations, including heavy-tailed, dependent, and other non-i.i.d. settings.

  • 5.1 “Almost” Bounded Losses: The section addresses losses that are only “almost” bounded, including sub-Gaussian and sub-gamma losses.
  • 5.2–5.4: It also treats heavy-tailed losses, dependent observations, and other non-i.i.d. settings.

6 Related Approaches in Statistics and Machine Learning

Section 6 situates PAC-Bayes bounds alongside related approaches in statistics and machine learning, including Bayesian inference, empirical risk minimization, online learning, aggregation, and information theory.

  • Statistics and Machine Learning: The related-approaches section covers Bayesian inference, empirical risk minimization, non-Bayesian estimators, online learning, and aggregation of estimators.
  • Information Theoretic Approaches: It also discusses information-theoretic approaches to PAC-Bayes analysis.

Introduction

The introduction frames supervised learning as choosing predictors from a parameterized set using observed data, then motivates randomized and aggregated predictors and PAC-Bayes bounds. These bounds extend union-bound reasoning to broad parameter spaces while controlling risks associated with data-dependent probability measures.

  • Randomized and Aggregated Predictors: The tutorial replaces single-estimator minimization with weighted voting or sampling from a prescribed distribution over predictors.
  • Machine Learning Foundations: Supervised learning seeks predictors that assign labels to objects, with classification and regression as central examples.
  • Machine Learning Foundations: Predictors are functions parameterized by θ in a set Θ, including linear models and fixed-architecture neural networks.
  • Machine Learning Foundations: Loss functions quantify prediction errors; the tutorial assumes 0 ≤ ℓ ≤ C through Section 4, covering common bounded-loss settings.
  • PAC-Bayes Bounds: PAC-Bayes bounds generalize the union-bound argument to finite or infinite parameter sets and control risks for data-dependent probability measures.
  • Scope and Organization: The notes provide an accessible introduction while acknowledging that ERM beyond finite Θ requires a modified union-bound argument and that presented constants may not be tight.
  • Types of PAC Bounds: Excess-risk or oracle PAC bounds address whether a generalization certificate can improve with more data or reflects the best available predictor set.

First Step in the PAC-Bayes World

PAC-Bayes bounds extend union-bound reasoning to finite or infinite parameter spaces, replacing a single estimator with data-dependent probability measures. The tutorial develops Gibbs posteriors, explicit finite and continuous examples, and applications to aggregated and deterministic predictors.

  • PAC-Bayes framework: Catoni’s bound is introduced to illustrate PAC-Bayes bounds, their use, and variants for randomized and aggregated estimators.The presentation prioritizes accessibility and illustration over immediately selecting the tightest bound.
  • PAC-Bayes framework: PAC-Bayes analysis fixes a prior π and uses Donsker–Varadhan’s variational formula to characterize the Gibbs posterior as a minimizer.The Gibbs posterior is defined as ˆρλ = π−λr, and Corollary 2.3 states that it minimizes the right-hand side of Theorem 2.1.
  • Finite parameter sets: The Gibbs posterior satisfies the same bound as the ERM, although the PAC-Bayes bound can be tighter when empirical risks across parameters are sufficiently similar.The tutorial explicitly distinguishes equality of bounds from equivalence of the resulting procedures.
  • Finite parameter sets: For finite Θ with cardinality M, PAC-Bayes bounds recover the ERM’s logarithmic dependence on M under a uniform prior.The explicit finite-case derivation uses π(θ)=1/M and a choice of λ minimizing the resulting bound.
  • Beyond Gibbs posteriors: Choosing λ is more consequential for Gibbs posteriors than for ERM because it changes the estimator itself, and optimizing it may be disallowed when its optimum depends on data or ρ.A non-tight bound can therefore produce a λ with poor practical performance; one example handles the issue by restricting Gaussian means to a bounded set.
  • Continuous parameter sets: For continuous Θ=R^d, Lipschitz losses and Gaussian priors provide PAC-Bayes bounds unavailable from a union-bound argument alone.The example assumes an L-Lipschitz loss and a centered Gaussian prior N(0, σ^2I_d), then restricts the variational optimization to Gaussian distributions.
  • Beyond Gibbs posteriors: PAC-Bayes bounds also cover aggregated predictors for convex losses and can analyze classical estimators, including ERM and some non-Bayesian robust estimators.The tutorial also gives a bound on the risk of a deterministic predictor in an online-learning analysis.

Tight and Non-vacuous PAC-Bayes Bounds

The section develops progressively tighter PAC-Bayes bounds, showing when they become informative, especially for noiseless problems and deep networks. It also highlights practical trade-offs involving optimization, priors, variance, and sample splitting.

  • Vacuous bounds: A basic neural-network example yields a bound of 13.58 with probability at least 95%, which is vacuous because classification risk is already at most 1.Even increasing the sample size to 1,000,000 remains insufficient in this example.
  • Practical trade-offs: Later bounds improve constants, rates, or optimization, but minimizing over λ can be difficult when the posterior depends on λ, and data-dependent-prior approaches commonly use sample splitting.Sample splitting has been criticized because the learned posterior may be extremely close to the prior, making the PAC-Bayes step barely necessary.
  • Variance-sensitive bounds: Variance-sensitive PAC-Bayes-Bernstein bounds can be much tighter when empirical variance is small and can retain the 1/n regime for predictors with zero empirical risk.They may also improve bounds when no perfect predictor exists because empirical variance can be no larger than empirical risk for losses in [0, 1].
  • Deep-network certificates: Dziugaite and Roy obtained the first nonvacuous PAC-Bayes generalization bounds for deep networks on MNIST in 2017, motivating subsequent efforts toward tighter certificates.Pérez-Ortiz et al. later reported a 0.0279 bound on MNIST and found the Thiemann et al. bound tightest across their experiments.

PAC-Bayes Oracle Inequalities and Fast Rates

This section develops oracle PAC-Bayes inequalities in expectation and in probability, relating randomized predictors’ expected risk to the best theoretically possible risk. It also motivates faster rates beyond the usual 1/√n rate.

  • Oracle bounds: Oracle PAC-Bayes bounds characterize predictors relative to the best possible risk, rather than providing a numerical certificate for a specific randomized estimator.The expectation bound gives theoretical near-optimality, while empirical PAC-Bayes inequalities provide numerical certificates.
  • Fast rates: The standard oracle rate is 1/√n, but faster rates can occur when the optimal risk is zero or under additional structure.The section states that 1/√n is impossible in the worst case but can often be improved.
  • Proof strategies: The expectation oracle inequality is derived from an empirical PAC-Bayes inequality, whereas the probability version requires a more complicated proof and has worse constants.The probability result follows from the empirical inequality in probability and a union-bound-based argument.

4.2 Bernstein Assumption and Fast Rates

Bernstein assumptions yield PAC-Bayes oracle inequalities with fast rates by controlling relative losses around a risk minimizer. Theorem 4.3 uses Bernstein’s inequality and can produce a 1/n rate.

  • Motivation: Bernstein assumptions make rates in 1/n possible for PAC-Bayes oracle bounds, extending a phenomenon known for non-Bayesian PAC bounds.The paper emphasizes that this fast-rate result applies beyond the special case of noiseless classification.
  • Examples: In noiseless classification, R(θ∗) = 0 implies Bernstein’s condition with K = 1; for losses in [0, C], the corresponding constant is K = C.The same zero-risk argument extends beyond the 0−1 loss.
  • Theorem 4.3: Theorem 4.3 assumes Bernstein’s condition and chooses λ = n/ max(2K, C) to obtain an oracle PAC-Bayes bound.The proof uses Bernstein’s inequality rather than Hoeffding’s inequality.
  • Oracle versus empirical bounds: The section distinguishes oracle rates from empirical rates: its 1/n oracle inequality does not directly use an empirical inequality.The unknown optimal risk r(θ∗) appears in the proof, so the resulting term is not empirical.
  • Proof strategy: The proof applies Bernstein’s inequality to relative losses ℓ_i(θ∗) −ℓ_i(θ), whose expectation is the negative excess risk.Using relative losses ensures that the Bernstein condition can be invoked.

4.3. APPLICATIONS OF THEOREM 4.3

Applications of Theorem 4.3 show how Bernstein conditions improve PAC-Bayes rates in finite and continuous predictor models. The examples instantiate the theorem with discrete or localized continuous distributions.

  • Gaussian priors: For Gaussian priors on Θ = R^d with an L-Lipschitz loss, Theorem 4.3 is applied with λ = n/ max(2K, C).The example retains the Gaussian prior π = N(0, σ^2I_d) and seeks an appropriate localization parameter s.
  • Uniform priors: For uniform priors on a bounded subset of R^d, the theorem restricts the infimum to uniform distributions on balls B(θ_0, s).The construction chooses θ_0 so that θ∗ lies inside a ball contained in Θ.
  • Uniform priors: The bounded-uniform-prior example reaches its minimum at s = max(2K,C)d.This is the stated minimizing choice for the right-hand side of the bound.

4.3. APPLICATIONS OF THEOREM 4.3

The paper surveys oracle PAC-Bayes applications across statistical models and summarizes how prior complexity determines convergence rates. Bernstein conditions replace square-root rates by faster rates in the listed examples.

  • Applications: Oracle PAC-Bayes inequalities have been applied to model selection, density estimation, ranking, regression, sparse regression, matrix methods, quantum tomography, and deep learning.The examples include both classical statistical problems and modern structured or neural models.
  • Applications: The survey also lists applications to additive non-parametric regression, matrix regression, matrix completion, Gram-matrix estimation, kernel-PCA, and deep learning.These applications span non-parametric, matrix-valued, tensor-related, and neural-network settings.
  • Complexity and rates: The learning rate raten(π) reflects the complexity of Θ under prior π, analogously to complexity-dependent rates in other learning-theory approaches.The paper illustrates this dependence through finite, Gaussian, heavy-tailed, and bounded-uniform priors.
  • Complexity and rates: For a finite uniform predictor class, the rate is in p log(M)/n generally and in log(M)/n under Bernstein condition.The corresponding examples instantiate the general complexity-rate relationship for discrete models.
  • Complexity and rates: For Gaussian priors on R^d, the rate is in [∥θ∗∥2 + d log(n)]/n both generally and under Bernstein condition.The stated expression includes the target parameter norm and model dimension.
  • Complexity and rates: A heavy-tailed multivariate Student prior yields a rate in [log ∥θ∗∥+ d log(n)]/n generally and under Bernstein condition.This is presented as a prior choice proposed for Θ = R^d.

4.4. DIMENSION AND RATE OF CONVERGENCE

This section connects convergence rates to dimension assumptions and prior mass near optimal predictors. Under these conditions, PAC-Bayes bounds can achieve rates controlled by dπ and n.

  • Catoni’s dimension assumption: Catoni’s dimension assumption controls the expected excess risk under the localized prior π−βR through a dimension parameter dπ.The assumption is introduced as a condition on the localized prior and yields bounds for β≥β0=dπ/C.
  • Catoni’s dimension assumption: Under Catoni’s dimension assumption, Theorem 4.4’s prior-mass requirement holds with cπ=dπ/(eC) for β≥dπ/C.
  • Prior mass condition: The prior mass condition requires the prior to assign sufficient probability to predictors whose excess risk is at most r.This condition is classical in Bayesian asymptotics and is formalized through constants c and dπ.
  • Prior mass condition: Under the prior mass condition, Lemma 4.6 gives cπ=dπ/(ec) and β0=dπ/r0 for the assumption used in Theorem 4.4.

4.5 Getting Rid of the log Terms: Catoni’s Localization Trick

Catoni’s localization replaces the prior with a risk-dependent distribution, producing tighter PAC-Bayes bounds. Under Bernstein conditions, this can remove logarithmic factors from convergence rates.

  • Localized bound: Theorem 4.7 applies Bernstein’s condition with λ=n/max(2K,C) to derive a localized PAC-Bayes bound.
  • Rates: The localized bound removes the log(n) terms appearing in the corresponding rates.The text presents this as a striking consequence of the localized construction.
  • Rates: Under Bernstein condition, the localized bound yields a rate in dπ/n.
  • Finite case: For a finite parameter set with uniform prior, Theorem 4.7 specializes to a bound involving the number of predictors and localized risk levels.The finite-case discussion introduces mτ as the number of predictors within excess risk threshold τ.

Beyond “Bounded Loss” and “i.i.d. Observations”

PAC-Bayes inequalities can extend beyond bounded losses and independent observations when suitable exponential-moment inequalities are available. Heavy-tailed losses require alternative approaches, with robust transformations recovering bounded-case-like behavior.

  • Generalization beyond standard assumptions: The bounded-loss and i.i.d. assumptions enter the proofs through Hoeffding- or Bernstein-type exponential inequalities.
  • Almost bounded losses: Sub-Gaussian losses provide a PAC-Bayes extension to some unbounded losses under independence.Sub-Gaussian variables have tails that decay at least as fast as Gaussian tails in the stated characterization.
  • Almost bounded losses: Sub-gamma variables include gamma, exponential, Gaussian, and bounded variables, and support Bernstein-type PAC-Bayes analyses.
  • Heavy-tailed losses: Truncation separates a bounded component of the loss from a tail term controlled by tail probabilities.For bounded losses the tail term vanishes once n/λ is sufficiently large, whereas moment-based tail bounds can slow convergence.
  • Heavy-tailed losses: Variance-only PAC-Bayes bounds for heavy-tailed losses replace KL divergence with other divergences but can have worse δ-dependence and slow rates.
  • Robust methods: Robust loss transformations can produce heavy-tailed bounds similar to bounded-case bounds without slower rates.The cited result retains favorable δ-dependence and uses KL(ρ∥π) rather than χ2(ρ∥π), subject to a restriction on δ.

Learning Theory

This section relates PAC-Bayes bounds to Bayesian posteriors, variational inference, online learning, and information-theoretic bounds. These connections extend the framework from posterior analysis to tractable approximations and nonstochastic prediction settings.

  • Bayesian inference: A Bayesian posterior can be represented as a Gibbs posterior by taking the loss to be negative log-likelihood.The corresponding empirical risk is the negative log-likelihood.
  • Bayesian inference: Standard PAC-Bayes analysis of Bayesian posteriors is limited because log-likelihoods are rarely bounded.
  • Posterior contraction: PAC-Bayes bounds can combine with prior mass conditions to analyze posterior contraction and related asymptotic behavior.The prior mass condition requires sufficient prior mass near the true parameter or a risk-defined neighborhood.
  • Variational inference: Variational inference restricts the optimization to a tractable family F, generalizes risk beyond negative log-likelihood, and may replace KL by another divergence.
  • Online learning: Online regret bounds typically require assumptions on the loss as a function of the predictor parameter but make no stochastic assumptions on the data.The data need not be independent or linked to a statistical model.
  • Information-theoretic approaches: Mutual-information bounds can be viewed as PAC-Bayes bounds optimized over the prior, while Catoni’s localization approximates the corresponding data-dependent prior through empirical bounds.The decomposition separates mutual information from the divergence between the expected posterior and the reference prior.

Conclusion

The conclusion aims for readers to understand PAC-Bayes bounds, recognize their flexibility across machine-learning contexts and objectives, and pursue further references. It also anticipates an important role for PAC-Bayes and related approaches in deep learning, reinforcement learning, and meta-learning.

  • The authors hope readers gain a better view of what PAC-Bayes bounds are and what can be done with them.
  • The conclusion emphasizes that PAC-Bayes bounds are flexible across contexts and machine-learning objectives.
  • The authors encourage readers to consult references offering tighter bounds and clever applications.
  • The authors believe PAC-Bayes and related approaches will play an important role in deep learning, reinforcement learning, and meta-learning.The conclusion connects this expectation to work by Dziugaite and Roy, Wang et al., Pentina and Lampert, Amit and Meir, and Rothfuss et al.
Loading 2110.11216v6…