Generalisation under gradient descent via deterministic PAC-Bayes

• URL: http://arxiv.org/abs/2209.02525v4
• Date: Tue, 11 Feb 2025 14:54:12 GMT
• Title: Generalisation under gradient descent via deterministic PAC-Bayes
• Abstract summary: We establish disintegrated PAC-Bayesian generalisation bounds for models trained with descent gradient methods or continuous gradient flows.<n>Our bounds are fully computable, depending on the density of the initial distribution.<n>We show that our framework can be applied to a variety of iterative optimisation algorithms.
• Score: 43.031038074791766
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish disintegrated PAC-Bayesian generalisation bounds for models trained with gradient descent methods or continuous gradient flows. Contrary to standard practice in the PAC-Bayesian setting, our result applies to optimisation algorithms that are deterministic, without requiring any de-randomisation step. Our bounds are fully computable, depending on the density of the initial distribution and the Hessian of the training objective over the trajectory. We show that our framework can be applied to a variety of iterative optimisation algorithms, including stochastic gradient descent (SGD), momentum-based schemes, and damped Hamiltonian dynamics.

Related papers

• On the Role of Batch Size in Stochastic Conditional Gradient Methods [51.97510367368799]
  We study the role of batch size in conditional gradient methods under a $$-Kurdyka-ojasiewicz ($$-KL) condition.<n>Our study reveals a regime-dependent behavior: increasing the batch size initially improves optimization accuracy but, beyond a critical threshold, the benefits and saturate can degrade performance under a fixed token budget.
  arXiv  Detail & Related papers  (2026-03-22T12:23:41Z)
• Tuning-Free Sampling via Optimization on the Space of Probability Measures [14.429970585649945]
  tuning-free sampling algorithms for gradient-based sampling algorithms obtained as time-discretizations of Wasserstein gradient flows.<n>We establish strong theoretical guarantees for our approach. In particular, we recover the convergence rate of optimally tuned versions of these algorithms up to logarithmic factors.<n>Across a variety of tasks, our algorithms achieve similar performance to the optimal performance of existing algorithms, with no need to tune a step size parameter.
  arXiv  Detail & Related papers  (2025-10-29T09:29:39Z)
• A Simulation-Free Deep Learning Approach to Stochastic Optimal Control [12.699529713351287]
  We propose a simulation-free algorithm for the solution of generic problems in optimal control (SOC) Unlike existing methods, our approach does not require the solution of an adjoint problem.
  arXiv  Detail & Related papers  (2024-10-07T16:16:53Z)
• Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
  We propose a novel algorithm for distributed gradient descent (SGD) with compressed gradient communication in the parameter-server framework. Our gradient compression technique, named flattened one-bit gradient descent (FO-SGD), relies on two simple algorithmic ideas.
  arXiv  Detail & Related papers  (2024-05-17T21:17:27Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures [1.9950682531209156]
  This paper presents a novel algorithm that leverages Gradient Descent strategies in conjunction with Random Features to augment the scalability of Conic Particle Gradient Descent (CPGD) We provide rigorous proofs demonstrating the following key findings: (i) The total variation norms of the solution measures along the descent trajectory remain bounded, ensuring stability and preventing undesirable divergence; (ii) We establish a global convergence guarantee with a convergence rate of $mathcalO(log(K)/sqrtK)$ over $K$, showcasing the efficiency and effectiveness of our algorithm; (iii) Additionally, we analyze and establish
  arXiv  Detail & Related papers  (2023-12-10T20:41:43Z)
• Adaptive Step Sizes for Preconditioned Stochastic Gradient Descent [0.3831327965422187]
  This paper proposes a novel approach to adaptive step sizes in gradient descent (SGD) We use quantities that we have identified as numerically traceable -- the Lipschitz constant for gradients and a concept of the local variance in search directions.
  arXiv  Detail & Related papers  (2023-11-28T17:03:56Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem [8.164433158925593]
  We investigate how analytically-based algorithms such as dynamical descent, its persistent gradient, and Langevin landscape descent can be studied. We apply statistical-field theory from statistical trajectories to these algorithms in their full-time limit, with a start, and for large system sizes.
  arXiv  Detail & Related papers  (2021-03-08T17:06:18Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Self-Tuning Stochastic Optimization with Curvature-Aware Gradient Filtering [53.523517926927894]
  We explore the use of exact per-sample Hessian-vector products and gradients to construct self-tuning quadratics. We prove that our model-based procedure converges in noisy gradient setting. This is an interesting step for constructing self-tuning quadratics.
  arXiv  Detail & Related papers  (2020-11-09T22:07:30Z)
• GTAdam: Gradient Tracking with Adaptive Momentum for Distributed Online Optimization [4.103281325880475]
  This paper deals with a network of computing agents aiming to solve an online optimization problem in a distributed fashion, by means of local computation and communication, without any central coordinator. We propose the gradient tracking with adaptive momentum estimation (GTAdam) distributed algorithm, which combines a gradient tracking mechanism with first and second order momentum estimates of the gradient. In these numerical experiments from multi-agent learning, GTAdam outperforms state-of-the-art distributed optimization methods.
  arXiv  Detail & Related papers  (2020-09-03T15:20:21Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)
• Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification [25.898873960635534]
  We analyze in a closed learning dynamics of gradient descent (SGD) for a single-layer neural network classifying a high-dimensional landscape. We define a prototype process for which can be extended to a continuous-dimensional gradient flow. In the full-batch limit, we recover the standard gradient flow.
  arXiv  Detail & Related papers  (2020-06-10T22:49:41Z)

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.