Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes

• URL: http://arxiv.org/abs/2505.19087v1
• Date: Sun, 25 May 2025 10:49:09 GMT
• Title: Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes
• Authors: Itamar Harel, Yonathan Wolanowsky, Gal Vardi, Nathan Srebro, Daniel Soudry,
• Abstract summary: We analyze the gap between the training and test errors when training a potentially over-parametrized model.<n>We have no dependence on either training time or reliance on mixing, nor a dependence on dimensionality, gradient norms, or any other properties of the loss or model.
• Score: 43.68309224776421
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We analyze the generalization gap (gap between the training and test errors) when training a potentially over-parametrized model using a Markovian stochastic training algorithm, initialized from some distribution $\theta_0 \sim p_0$. We focus on Langevin dynamics with a positive temperature $\beta^{-1}$, i.e. gradient descent on a training loss $L$ with infinitesimal step size, perturbed with $\beta^{-1}$-variances Gaussian noise, and lightly regularized or bounded. There, we bound the generalization gap, at any time during training, by $\sqrt{(\beta\mathbb{E} L (\theta_0) + \log(1/\delta))/N}$ with probability $1-\delta$ over the dataset, where $N$ is the sample size, and $\mathbb{E} L (\theta_0) =O(1)$ with standard initialization scaling. In contrast to previous guarantees, we have no dependence on either training time or reliance on mixing, nor a dependence on dimensionality, gradient norms, or any other properties of the loss or model. This guarantee follows from a general analysis of any Markov process-based training that has a Gibbs-style stationary distribution. The proof is surprisingly simple, once we observe that the marginal distribution divergence from initialization remains bounded, as implied by a generalized second law of thermodynamics.

Related papers

• Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
  Temporal Difference Learning (TD(0)) is fundamental in reinforcement learning.<n>We provide the first high-probability, finite-sample analysis of vanilla TD(0) on mixing Markov data.
  arXiv  Detail & Related papers  (2025-02-08T22:01:02Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors [12.43000662545423]
  Thompson sampling (TS) is one of the most popular and earliest algorithms to solve multi-armed bandit problems. We consider a variant of TS, named $alpha$-TS, where we use a fractional or $alpha$-posterior instead of the standard posterior distribution.
  arXiv  Detail & Related papers  (2023-09-12T16:15:33Z)
• Generalization Bounds for Gradient Methods via Discrete and Continuous Prior [8.76346911214414]
  We show a new high probability generalization bound of order $O(frac1n + fracL2n2sum_t=1T(gamma_t/varepsilon_t)2)$ for gradient Langevin Dynamics (GLD) We can also obtain new bounds for certain variants of SGD.
  arXiv  Detail & Related papers  (2022-05-27T07:23:01Z)
• An Improved Analysis of Gradient Tracking for Decentralized Machine Learning [34.144764431505486]
  We consider decentralized machine learning over a network where the training data is distributed across $n$ agents. The agent's common goal is to find a model that minimizes the average of all local loss functions. We improve the dependency on $p$ from $mathcalO(p-1)$ to $mathcalO(p-1)$ in the noiseless case.
  arXiv  Detail & Related papers  (2022-02-08T12:58:14Z)
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
  Understanding the implicit bias of Gradient Descent (SGD) is one of the key challenges in deep learning. This paper gives a general framework for such analysis by adapting ideas from Katzenberger (1991). It yields some new results: (1) a global analysis of the implicit bias valid for $eta-2$ steps, in contrast to the local analysis of Blanc et al. ( 2020) that is only valid for $eta-1.6$ steps and (2) allowing arbitrary noise covariance.
  arXiv  Detail & Related papers  (2021-10-13T17:50:46Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  We show that the rate estimate $widetildemathcalO(depsilon-1)$ improves the previously known rates in both of these metrics. In particular, for convex and firstorder smooth potentials, we show that LMC algorithm achieves the rate estimate $widetildemathcalO(depsilon-1)$ which improves the previously known rates in both of these metrics.
  arXiv  Detail & Related papers  (2020-07-22T18:18:28Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.