Research map / Learning theory and algorithms / Kernels and regression theory
Generalization of Hamiltonian algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves generalization bounds for stochastic Hamiltonian learning algorithms (Gibbs, randomized stable algorithms, data-dependent-prior PAC-Bayes) by bounding the log-moment generating function of the generalization gap via concentration of the log-density.
Problem
Generalization guarantees with high probability over both the sample and a single hypothesis drawn from a stochastic learning algorithm, including Gibbs posteriors and PAC-Bayes bounds with data-dependent priors.
Approach
Write the stochastic algorithm's density as exp(Hamiltonian)/partition function relative to an a-priori measure; bound the exponential moment of the generalization gap by showing the Hamiltonian (and its log-partition function) concentrates via bounded differences or subgaussianity, then apply Markov's inequality.
Key results
- For the Gibbs algorithm with bounded losses in [0,1], the bound gives Delta <= beta/n + sqrt(ln(1/delta)/(2n)) with probability 1-delta, removing log factors relative to prior Gibbs bounds.
- For Gaussian randomization of stable algorithms, the paper proves Delta <= sqrt(((3/sigma^2) V(A) + ln(1/delta))/n), with V(A) the variance of the algorithm output.
- A PAC-Bayes bound with data-dependent Gaussian prior centered at A(X) gives E_P[kl] <= (2KL(P,Q_X) + (6/sigma^2)V(A) + ln(2 sqrt n) + 2 ln(1/delta))/n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Hamiltonian method for the Gibbs algorithm instead of the cited prior bound | Gibbs algorithm with bounded losses · Gibbs algorithm, bounded losses | generalization gap upper bound: \frac{4\beta }{n}+\frac{2+\ln ( (1+\sqrt{e})/\delta ) }{\sqrt{n}} -> \frac{\beta }{n}+\sqrt{\frac{\ln (1/\delta ) }{2n}} | Helped |
| Use the Gaussian-randomization bound based on algorithm variance instead of the cited stability-based PAC-Bayesian bound | Gaussian randomization of stable algorithms · Gaussian randomization of stable algorithms | expected KL generalization bound | Mixed |
| Use the disintegrated Gaussian-randomization bound | Gaussian randomization of stable algorithms · Gaussian randomization of stable algorithms | generalization gap upper bound | Helped |
Limitations
- Bounds for the Gibbs algorithm in the regime beta > n are not obtained; the authors say the method is unlikely to apply without strong assumptions.
- Constants increase when combining Hoelder/Cauchy-Schwarz to separate the contributions of F and H_Q.
- Results are stated for iid data; non-iid (Markov) extension is only proposed as future work.
Experimental setup
Metrics: generalization gap bound kl divergence bound log-moment generating function bound
Baselines: Rivasplata Gaussian PAC-Bayes bound Catoni Gibbs bounds kl-based Gibbs bounds
Builds on: PAC-Bayes theorem McDiarmid inequality Catoni PAC-Bayes Bernstein inequality
Closest papers by meaning
- A unified framework for information-theoretic generalization bounds (NeurIPS 2023 · similarity 0.87)
- Sharper Bounds for Uniformly Stable Algorithms with Stationary Mixing Process (ICLR 2023 · similarity 0.87)
- Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.86)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.85)
- Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure (AAAI 2024 · similarity 0.85)
- A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.