CS Paper Radar

Exact information accounting for SGD methods

Akshay Balsubramani

cs.LG cs.ITmath.OCstat.ML ·submitted 2026-09-30 17:53 UTC · v1

Abstract

As an alternative to the standard geometric analyses, we give an exact, information-theoretic analysis of stochastic gradient descent (SGD) and its variants. We show that a preconditioned SGD step is the posterior-mean update of a Gaussian Bayes model, and that its one-step regret splits into an intrinsic-time cost and a change in comparator information. The split extends to an identity for the objective itself. Convex convergence, strict-saddle-point escape, the link between flatness and generalization, the standard learning-rate schedules, adaptive optimizers, and the noisy, momentum, heavy-tailed, and gradient-free variants of SGD each correspond to a term or a special case of this identity. We measure its terms on synthetic and real training runs. On real networks it attributes the slack of classical convergence bounds to the terms their derivations drop and separates optimizers that reach the same training loss. That separation follows the number and consistency of their steps. Its relation to which of them generalizes better differs between networks. For gradient-free SGD the identity determines how a curvature preconditioner should enter the update. The sharpness-based generalization certificate it yields, with a data-independent isotropic prior, is vacuous at network scale unless the curvature spectrum is nearly flat across all parameters.

Closest papers

Nearest neighbours by meaning across the whole index.

Convergence of stochastic gradient descent for learning linear neural networks

cs.LG math.OC ·2026-10-20 ·Gabin Maxime Nguegnang, Bubacarr Bah, Holger Rauhut, Ulrich Terstiege
similarity 0.69
Abstract · 30 pages

Stochastic gradient descent (SGD) is the cornerstone of modern deep learning, yet its theoretical convergence properties remain poorly understood in non-convex settings. To address this gap, we study SGD dynamics in deep linear neural networks - simplified models that retain key non-convex characteristics while remaining analytically tractable. Building on recent results for gradient descent, we extend convergence guarantees to SGD under regularized squared loss. We establish almost sure boundedness of SGD iterates. Using the framework of asymptotic pseudotrajectories from stochastic approximation theory, our analysis establishes then, for both deterministic and adaptive step-size choices, convergence of SGD to the set of critical points under mild conditions (without relying on Lipschitz properties or whitened data). To our knowledge, this is the first work providing almost sure convergence guarantees for SGD in deep linear networks, bridging the gap between theoretical optimization and practical stochastic training.

0.19

Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise

cs.LG math.OCmath.PR ·2026-09-10 ·Amartya Mukherjee, Jun Liu
publishedtheoryhot direction similarity 0.69
Abstract

Stochastic gradient descent (SGD) with gradient clipping and additive noise has become a standard technique for training machine learning models, particularly in applications requiring robustness or privacy guarantees. However, clipping introduces a bias in stochastic gradients, while additive noise introduces additional variance, making the long-run behaviour of individual optimization trajectories difficult to characterize. In this work, we prove that SGD with clipping and additive Gaussian noise (SGD-CN) converges almost surely (a.s.) under smoothness and uniformly bounded stochastic-gradient noise assumptions, provided the step sizes satisfy some standard decaying conditions. Our analysis extends to momentum variants such as the stochastic heavy ball and Nesterov's accelerated gradient, where we show that careful energy constructions yield similar guarantees. These results provide stronger theoretical foundations for understanding the pathwise behaviour of clipped stochastic gradient methods and suggest that, despite the bias and noise introduced by clipping and perturbation, the algorithm remains stable in both convex and nonconvex regimes.

0.56

Universal Online Convex Optimization With Delayed Feedback

cs.LG ·2026-10-20 ·Hao Qiu, Andrew Jacobsen, Emmanuel Esposito, Mengxiao Zhang
similarity 0.68
Abstract

We study universal online convex optimization with delayed feedback. We develop a single algorithm that simultaneously adapts to general convex, strongly convex, and exp-concave losses without prior knowledge of the curvature class or parameters. Our regret bounds match the best known dependence on the time horizon $T$ and delays up to doubly logarithmic factors: roughly $\sqrt{T + d_{\mathrm{tot}}}$ for convex losses and $σ_{\max}\log T$ rates with curved losses, where $d_{\mathrm{tot}}$ is the total cumulative delay and $σ_{\max}$ is the maximum number of simultaneously missing observations. Our main technical contribution is a delayed meta-learner with a second-order excess-loss guarantee, which enables curvature-adaptive aggregation of delayed base learners. In addition, our new exp-concave base learner yields a sharper regret bound which improves the state-of-the-art delay dependence by replacing the maximum delay with the potentially much smaller $σ_{\max}$, while retaining the complementary $\sqrt{d_{\mathrm{tot}}}$ dependence.

0.28

Fast rates in Bayesian online learning with approximate posteriors

cs.LG stat.ML ·2026-08-26 ·Ilsang Ohn
theory similarity 0.68
Abstract

Exact Bayes prediction enjoys fast predictive regret guarantees, but exact posterior updating or representation may be too costly for online use. We study when these statistical guarantees are preserved by computational approximations. We show that the cumulative price of posterior approximation can be governed by the interaction between the contraction radius of the exact Gibbs posterior and the Wasserstein distance between the approximate and exact posteriors. Our general theorem shows that whenever exact Bayes prediction achieves a fast regret bound, any approximate posterior method that tracks the exact posterior with sufficient accuracy inherits the same fast regret, up to an additive term determined by the approximation error. Three online learning examples are developed. For linear models with strongly convex regularized losses, a projected Langevin algorithm yields an approximate posterior that achieves logarithmic regret. For an infinite-dimensional canonical exponential family sequence model over a Sobolev ellipsoid, a prior-preserving truncation method attains the minimax predictive regret rate with sublinear memory and constant update cost per observation. For random-design Gaussian process (GP) regression, a sparse variational posterior with inducing variables achieves the same predictive regret rate as the exact GP, but at substantially lower computational cost.

0.25

Generalized Convexity and Smoothness via Conjugate Duality, with Applications to Deep Network Training

cs.LG ·2026-08-10 ·Binchuan Qi
theory similarity 0.68
Abstract

Stochastic gradient descent (SGD) and its variants train deep neural networks (DNNs) effectively in practice, yet classical optimization theory does not fully explain this success: conventional analyses rest on differentiability, convexity, and smoothness, assumptions that DNN objectives routinely violate. We close this gap by generalizing convexity and smoothness, through Legendre functions and convex conjugation, into a unified optimization framework for DNN training. We introduce \(\mathcal{H}(ψ)\)-convexity and \(\mathcal{H}(Ψ)\)-smoothness, a single formalism that encompasses convex and non-convex as well as smooth and non-smooth objectives and reveals a natural duality between generalized convexity and smoothness. Building on these notions, we derive generalized gradient descent (GD) and generalized SGD via convex conjugation. We prove that generalized GD attains an optimal learning rate of exactly \(1\), and we establish rigorous gradient-energy-based convergence rates for both optimizers. We further recast DNN training as a composite optimization problem and show that its convergence hinges on jointly reducing the gradient energy and controlling the extreme eigenvalues of the structure matrix; a model capacity risk quantifies the residual error that no optimizer can remove. Experiments on six datasets (MNIST, Fashion-MNIST, CIFAR-10, CIFAR-100, TREC, and SST-2) and on convolutional, residual, and Transformer architectures, with five loss functions, are consistent with the predicted training dynamics.

0.04

High-Probability Convergence of SGD via Batched Updates

cs.LG math.OCeess.SY ·2026-09-11 ·Feng Zhu, Robert W. Heath, Aritra Mitra
published similarity 0.67
Abstract · To appear at the 65th IEEE Conference on Decision and Control

Stochastic gradient descent (SGD) is the primary workhorse for large-scale optimization. While the average behavior of its iterates, typically characterized by mean-squared error bounds, is well-understood, obtaining high-probability guarantees for the last iterate remains challenging. Prior approaches to this problem have either imposed restrictive assumptions (such as bounded domains or gradients) or relied on complex proofs involving auxiliary sequences. In this work, we propose Batched SGD, a simple variant that partitions online samples into epochs and performs a single update per epoch using a refined, low-variance gradient estimate. Our main contribution demonstrates that this batching mechanism enables a surprisingly simple high-probability analysis that avoids both restrictive assumptions and auxiliary sequences. Under standard smoothness and norm-sub-Gaussian noise assumptions, we establish near-optimal rates for both strongly convex and non-convex objectives. Furthermore, we show that our batching idea extends naturally to federated learning (FL). We provide the first high-probability guarantees for FL, achieving logarithmic communication complexity, linear speedup in the number of agents, and resilience to data heterogeneity.

0.31

Acceleration and its Limits in Gaussian Variational Inference

cs.LG stat.MLmath.OC ·2026-10-14 ·Jaesung R. Park, Uijeong Jang, Yifan Chen
similarity 0.66
Abstract · 52 pages, 9 figures

We study whether the classical momentum-based acceleration that improves the condition-number dependence of gradient descent from $κ$ to $\sqrtκ$ for strongly convex, smooth objectives extends to Gaussian variational inference (GVI) for strongly log-concave, log-smooth target distributions. With exact Gaussian expectations, a convex composite formulation of GVI yields the classical accelerated $\sqrtκ$ convergence rate. However, when only pointwise derivatives are available, we construct a family of strongly log-concave targets for which any randomized algorithm requires $κ^{1-o(1)}$ queries to achieve a fixed objective accuracy, even when the initial objective gap is bounded independently of $κ$. Thus curvature bounds alone cannot guarantee uniform accelerated total-query complexity. We then ask which additional structure permits acceleration and give positive examples: under a Hessian-Lipschitz assumption, variance-reduced stochastic methods yield accelerated guarantees when the Hessian variation is sufficiently small. Finally, experiments on real datasets show substantial empirical speedups from acceleration across a broad range of methods.

0.18

A Simple and Unified Method for Gradient-Variation Regret

cs.LG math.OC ·2026-10-19 ·Hang Yu, Peng Zhao
similarity 0.66
Abstract

Gradient-variation online learning has attracted increasing attention for its connections to game theory and optimization. It has been studied in both non-stationary online learning, which aims to minimize dynamic regret against time-varying comparator sequences, and universal online learning, which seeks to adapt to unknown loss curvature. Prior work obtained gradient-variation bounds using different techniques tailored to each setting. We propose a simple and unified method based on surrogate losses with a quadratic penalty on decision movement, yielding gradient-variation bounds in both settings. For non-stationary online learning, the method induces an optimistic-to-gradient-variation reduction, enabling a broad class of algorithms to match the rate established by Zhao et al. (2024). For universal online learning, it yields a simple algorithm that matches the optimal universal regret bounds of Yan et al. (2024) while relaxing the extended smoothness assumption. Finally, we apply our method to online games and improve on existing guarantees.

0.14