Stability Based Generalization Bounds for Exponential Family Langevin Dynamics

2022-01-09 · Arindam Banerjee, Tiancong Chen, Xinyan Li, Yingxue Zhou

Recent years have seen advances in generalization bounds for noisy stochastic algorithms, especially stochastic gradient Langevin dynamics (SGLD) based on stability (Mou et al., 2018; Li et al., 2020) and information theoretic approaches (Xu and Raginsky, 2017; Negrea et al., 2019; Steinke and Zakynthinou, 2020). In this paper, we unify and substantially generalize stability based generalization bounds and make three technical contributions. First, we bound the generalization error in terms of expected (not uniform) stability which arguably leads to quantitatively sharper bounds. Second, as our main contribution, we introduce Exponential Family Langevin Dynamics (EFLD), a substantial generalization of SGLD, which includes noisy versions of Sign-SGD and quantized SGD as special cases. We establish data-dependent expected stability based generalization bounds for any EFLD algorithm with a O(1/n) sample dependence and dependence on gradient discrepancy rather than the norm of gradients, yielding significantly sharper bounds. Third, we establish optimization guarantees for special cases of EFLD. Further, empirical results on benchmarks illustrate that our bounds are non-vacuous, quantitatively sharper than existing bounds, and behave correctly under noisy labels.

📄 PDF Abstract BibTeX arXiv:2201.03064

Code (0)

등록된 구현이 없습니다.

Tasks

Generalization Bounds

Methods 이 논문이 사용한 방법론

SGD Stochastic Gradient Descent is an iterative optimization technique that uses minibatches of data to form an expectation of the gradient, rather than the full gradient using…

CAM Class activation maps could be used to interpret the prediction decision made by the convolutional neural network (CNN). Image source: [Learning Deep Features for…

Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials

2026-10-01 · Nikolaos Makras, Sotirios Sabanis arxiv

We consider the problem of sampling from Gibbs distributions on matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead…

Time-Independent Information-Theoretic Generalization Bounds for SGLD

2023-11-02 · NeurIPS 2023 11

We provide novel information-theoretic generalization bounds for stochastic gradient Langevin dynamics (SGLD) under the assumptions of smoothness and dissipativity, which are widely used in sampling and non-convex optimi…

Generalization Bounds

An Information-Theoretic Framework for Out-of-Distribution Generalization with Applications to Stochastic Gradient Langevin Dynamics

2024-03-29 · Wenliang Liu, Guanding Yu, Lele Wang, Renjie Liao

We study the Out-of-Distribution (OOD) generalization in machine learning and propose a general framework that establishes information-theoretic generalization bounds. Our framework interpolates freely between Integral P…

Generalization Bounds Out-of-Distribution Generalization

On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning

2019-02-02 · ICLR 2020 1 · Jian Li, Xuanyuan Luo, Mingda Qiao

Generalization error (also known as the out-of-sample error) measures how well the hypothesis learned from training data generalizes to previously unseen data. Proving tight generalization error bounds is a central quest…

Generalization Bounds Learning Theory

Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability

2018-02-18 · Belinda Tzen, Tengyuan Liang, Maxim Raginsky

We study the detailed path-wise behavior of the discrete-time Langevin algorithm for non-convex Empirical Risk Minimization (ERM) through the lens of metastability, adopting some techniques from Berglund and Gentz (2003.…