# Distribution-Dependent Analysis of Gibbs-ERM Principle

arXiv: https://arxiv.org/abs/1902.01846 · HTML: https://mlsanity.com/paper/1902.01846/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2019.

## Built on by (most cited first, 17 of 17)

- [Information Complexity and Generalization Bounds](https://mlsanity.com/paper/2105.01747/) (2021)
- [Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithm](https://mlsanity.com/paper/2111.01635/) (2021)
- [Tighter PAC-Bayes Bounds Through Coin-Betting](https://mlsanity.com/paper/2302.05829/) (2023)
- [A PAC-Bayesian Link Between Generalisation and Flat Minima](https://mlsanity.com/paper/2402.08508/) (2024)
- [Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measures](https://mlsanity.com/paper/2402.13285/) (2024)
- [Learning Algorithm Generalization Error Bounds via Auxiliary Distributions](https://mlsanity.com/paper/2210.00483/) (2022)
- [How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?](https://mlsanity.com/paper/2210.08188/) (2022)
- [Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL information](https://mlsanity.com/paper/2107.13656/) (2021)
- [Information-Theoretic Framework for Understanding Modern Machine-Learning](https://mlsanity.com/paper/2506.07661/) (2025)
- [On the Generalization Error of Meta Learning for the Gibbs Algorithm](https://mlsanity.com/paper/2304.14332/) (2023)
- [Generalization of Hamiltonian algorithms](https://mlsanity.com/paper/2405.14469/) (2024)
- [Generalization of Gibbs and Langevin Monte Carlo Algorithms in the Interpolation Regime](https://mlsanity.com/paper/2510.06028/) (2025)
- [Generalization in Nonlinear Least Squares via Learned Feature Geometry](https://mlsanity.com/paper/2606.08799/) (2026)
- [Generalization of the Gibbs algorithm with high probability at low temperatures](https://mlsanity.com/paper/2502.11071/) (2025)
- [Empirical Risk Minimization with f-Divergence Regularization](https://mlsanity.com/paper/2601.13191/) (2026)
- [On-Average Stability of Multipass Preconditioned SGD and Effective Dimension](https://mlsanity.com/paper/2603.11989/) (2026)
- [Gradient Transformer: Learning to Generate Updates for LLMs](https://mlsanity.com/paper/2605.27591/) (2026)

## Abstract (arXiv)

Gibbs-ERM learning is a natural idealized model of learning with stochastic optimization algorithms (such as Stochastic Gradient Langevin Dynamics and ---to some extent--- Stochastic Gradient Descent), while it also arises in other contexts, including PAC-Bayesian theory, and sampling mechanisms. In this work we study the excess risk suffered by a Gibbs-ERM learner that uses non-convex, regularized empirical risk with the goal to understand the interplay between the data-generating distribution and learning in large hypothesis spaces. Our main results are distribution-dependent upper bounds on several notions of excess risk. We show that, in all cases, the distribution-dependent excess risk is essentially controlled by the effective dimension trleft(boldsymbolHstar (boldsymbolHstar + λ boldsymbolI)-1right) of the problem, where boldsymbolHstar is the Hessian matrix of the risk at a local minimum. This is a well-established notion of effective dimension appearing in several previous works, including the analyses of SGD and ridge regression, but ours is the first work that brings this dimension to the analysis of learning using Gibbs densities. The distribution-dependent view we advocate here improves upon earlier results of Raginsky et al. (2017), and can yield much tighter bounds depending on the interplay between the data-generating distribution and the loss function. The first part of our analysis focuses on the localized excess risk in the vicinity of a fixed local minimizer. This result is then extended to bounds on the global excess risk, by characterizing probabilities of local minima (and their complement) under Gibbs densities, a results which might be of independent interest.