CS Paper Radar

Convergence rates for the RMSprop optimizer with full control of the hyperparameters

Steffen Dereich, Arnulf Jentzen

cs.LG math.OCmath.PR ·submitted 2026-08-31 07:37 UTC · v1

Abstract

Popular adaptive stochastic gradient descent (SGD) methods to train artificial intelligence (AI) systems include the RMSprop, the Adam, and the AdamW optimizers, where the adaptivity parts in Adam and AdamW basically just coincide with RMSprop. Such adaptive methods involve several hyperparameters including the regularization parameter $ε$ (which ensures that one does not divide by 0 and is often chosen to be very close to zero such as $10^{-8}$ in PyTorch by default) and the second moment decay parameter $β$ (which is often chosen to be very close to $1$ such as 0.99 (RMSprop) and 0.999 (Adam and AdamW) in PyTorch by default). Despite the high relevance of such methods, it remains an open research problem to provide error estimates for such methods with the error constants being not exploding but uniformly bounded with the respect to the hyperparameters, even in the situation of convex stochastic optimization problems. It is the key contribution of this work to essentially solve this problem for RMSprop. Specifically, we bound the expectation of the stopped evaluation of the objective function at the RMSprop process from above by the sum of an initialization term that decays exponentially in the training time, a stochastic approximation remainder of order $γ_n$, and a memory error of order $( 1 - β)^2$ with the error constants being uniformly controlled over all admissible choices of the step sizes, the second moment decay parameter $β$ and the regularization parameter $ε\in[0,1]$ (also covering $ε=0$). Our non-asymptotic error estimates hold not just for all sufficiently large n but hold for every gradient step $n=1,2,3,...$ with all error constants being explicitly specified. The key innovative new feature in the proof of our analysis are suitable inverse moment bounds for the second moment process in RMSprop.

Closest papers

Nearest neighbours by meaning across the whole index.

Second-Moment Stochastic Approximation Methods

cs.AI math.OCstat.ML ·2026-09-29 ·Tao Jiang, Lin Xiao
theory similarity 0.65
Abstract

Classical stochastic approximation methods rely on estimators of the first moment (mean) of a random regression function. We study methods that employ estimators of both the first and the second moments, which include modern deep-learning optimizers such as Adam and Muon as special cases. We derive second-moment stochastic approximation methods through the lens of optimal preconditioning for solving matrix equations, and develop a two-stage framework for their convergence analysis. The first stage focuses on the analysis of conceptual (impractical) methods that rely on the exact first and second moments. In the second stage, we replace the exact moments with their respective estimators, and invoke Dvoretzky's theorem to show that the resulting practical methods converge almost surely to a neighborhood of the target solution. The size of the neighborhood depends on the biases and variances of the first- and second-moment estimators. We derive concrete bounds for Muon and a spectral variant of Adam that determine the radius of their neighborhood of convergence.

0.17

On the Convergence of Vanilla Adam under Heavy-Tailed Noise and Index Sampling

cs.LG ·2026-11-02 ·Kanata Oowada, Hideaki Iiduka
similarity 0.64
Abstract

Understanding how stochastic gradient noise affects the convergence of Adam is an important problem in stochastic optimization, particularly when the noise exhibits heavy-tailed behavior. In this paper, we investigate the convergence of vanilla Adam in both the expected risk and the empirical risk minimization, focusing on the effects of heavy-tailed noise and its relationship to index sampling. For the expected risk minimization, we establish convergence guarantees under Hölder smoothness and bounded $\mathfrak{p}$-th moment assumptions, allowing stochastic gradient noise with infinite variance. Our analysis provides explicit upper bounds on the expected squared gradient norm and shows that the iteration-dependent convergence term decays more slowly as $\mathfrak{p}$ decreases. For the empirical risk minimization, we establish asymptotic and non-asymptotic convergence guarantees and demonstrate that heavy-tailed population noise can deteriorate convergence bounds through dataset-dependent constants as the dataset size increases. Furthermore, under Lipschitz smoothness, we formulate multistage Adam with practical learning rate schedules and demonstrate that increasing batch sizes can reduce index-sampling noise and improve convergence guarantees and SFO complexity. Numerical experiments support our theoretical findings on the effects of heavy-tailed noise and the computational benefits of increasing batch sizes.

0.07

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.64
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

On the Global Convergence of Stochastic Adam for Physics-Informed Neural Networks

cs.LG math.NAmath.OC ·2026-11-09 ·Yihang Gao
theory similarity 0.64
Abstract

The Adam optimizer is widely used to train neural networks with highly nonlinear and nonconvex objective functions. Remarkably, Adam often drives the empirical training loss nearly to zero. This phenomenon has been partially explained by neural tangent kernel (NTK) analyses of gradient descent (GD) and stochastic gradient descent (SGD). However, analyzing Adam presents additional challenges. Its first-moment momentum couples stochastic gradients across iterations, while its adaptive second-moment preconditioner depends on the same stochastic gradient used in the update. In this paper, we establish linear convergence guarantees for Adam in training sufficiently wide two-layer neural networks with either full-batch or minibatch gradients. For full-batch Adam, we construct a Lyapunov function to control the effect of historical momentum. For minibatch Adam, our analysis builds on an exact virtual-iterate representation, a conditional analysis of the dependence between stochastic gradients and adaptive preconditioners, and uniform concentration bounds for the second-moment estimates. We prove geometric decay of the empirical loss for full-batch Adam and geometric decay in restricted expectation on a high-probability event for minibatch Adam. Beyond regression, we extend our convergence analysis to physics-informed neural networks (PINNs) for solving the Poisson equation, where differential operators and separate sampling of interior and boundary points introduce additional challenges. We establish analogous global convergence guarantees for both deterministic and stochastic Adam under explicit conditions on network width and Adam's parameters, characterizing the effects of minibatch size on convergence. These results help bridge the gap between Adam's empirical success and its theoretical understanding, providing sharper convergence guarantees for PINNs than existing analyses.

0.09

On the Principles Behind Neural Network Optimizers

cs.LG math.OC ·2026-08-17 ·Yushun Zhang
theory similarity 0.63
Abstract

Reliable optimization is central to neural network (NN) training, yet Adam, the default optimizer for modern LLMs, rests on a fragile foundation. This thesis develops a principled grounding for Adam and motivates new designs. First, we revisit Adam's divergence--convergence debate and show the existence of a problem-dependent phase transition: with properly chosen, batch-size-dependent hyperparameters, Adam converges, whereas under small-$β_2$ regimes it can diverge. Second, we investigate why Adam substantially outperforms SGD on Transformers through Hessian structure. We find that the Hessian evolves toward a near-block-diagonal form along training, accompanied by strong block heterogeneity. We prove that this structure makes Adam's diagonal preconditioner effective. We further show that this special Hessian structure originates from consecutive multiplications of large matrix variables, and we provide a rigorous analysis based on random matrix theory. Finally, these insights motivate Adam-mini, a new optimizer that reduces Adam's memory footprint by 50\% while preserving its performance. Our results also have broader implications beyond Adam: they reveal new local structures in matrix-based nonconvex problems, and also help understand and improve recent NN optimizers, such as Muon.

0.09

Loss Landscape Features That Make Adam Stall: Definitions, Estimators, and the Preconditioned Hessian View

cs.LG math.NA ·2026-08-23 ·Rodion Podorozhny
hot direction similarity 0.62
Abstract

Across implicit-neural-representation (INR) architectures and analytic benchmarks we observe that a thoroughly tuned Adam (especially its learning rate (lr), e.g. in a hyperparameter sweep from $lr = 0.05$ to $10^{-8}$) can potentially reach a very low loss even on ill-conditioned loss landscape or converge at a plateau far above the loss attained by second-order methods. This report defines the measured metrics that help determine if Adam can mitigate the ill-conditioning on a given loss landscape. We provide the indicators by which each outcome is determined, that are: the condition number of the Hessian and of the Adam-preconditioned Hessian $D^{-1/2}HD^{-1/2}$ (with the derivation from Adam's update rule), the diagonal mass $ρ$ that distinguishes axis-aligned from cross-coupled ill-conditioning, the negative spectral mass estimated by stochastic Lanczos quadrature, and the gradient energy fractions over curvature bands, including the flat fraction that indicates the Adam stall. A worked out $2\times 2$ example and an illustration show the reasons why a diagonal preconditioning by Adam can remove axis-aligned ill-conditioning by rescaling and why it cannot do the same if the ill-conditioning is cross coupled. In addition, we present a case study of FINER image fitting architecture that goes over the whole loss landscape analysis framework: the fitting architecture description, reasons due to which its landscape stalls Adam at saddles, the measured PSNR values through our tuned baselines to the $120$--$134$\,dB results of the blockwise second order methods, the error maps behind those numbers, and description of the benefits such image fitting accuracy gives in practice.

0.42

High-dimensional limit theorems for adaptive variants of SGD I: Ballistic limits

cs.LG stat.MLmath.PRmath.ST ·2026-11-14 ·Aukosh Jagannath, Varnan Sarangian
theory similarity 0.62
Abstract

We develop the high-dimensional effective dynamics for adaptive, momentum-based variants of Stochastic Gradient Descent (SGD). These effective dynamics are given by a Markov process. They key observation is that the non-Markovianity in the algorithm due to the exponential moving average and preconditioning can be treated using the method of averaging. Our approach applies to a broad class of algorithms including to Adaptive momentum estimation (ADAM), Momentum orthogonalized by Newton-Schultz (MUON), and its variants. It also applies to a broad class of learning tasks, such at tensor PCA, Gaussian projective models, teacher-student networks, and a multi-layer neural network trained on the XOR problem using a hybrid of MUON and ADAM as commonly done in practice. We demonstrate how to this technique can give precise, quantitative comparisons between algorithms. In particular, we find interesting phenomena, such as the cross-over phenomenon where online SGD has better generalization than ADAM early in training until the learning curves cross and ADAM dominates. Furthermore, we prove a version of the Edge of Stability phenomenon. In particular, we introduce an analogue of the infinity Laplacian that sharply characterizes the Edge of Stability.

0.05

Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

cs.LG stat.MLmath.OCmath.ST ·2026-10-31 ·Denis Belomestny, Alexey Naumov, Sergey Samsonov
theory similarity 0.61
Abstract

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent $γ\in(1/2,1)$, a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order $n^{1/2-γ}+n^{γ-1}$ in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of $γ$. The nonlinear bias contributes $n^{1/2-γ}$ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order $n^{-(1-γ)/2}$ for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error $\varepsilon$ on this example takes order $\varepsilon^{-4}$ iterations for the best choice $γ=3/4$. Achieving both Gaussian approximation and relative mean variance-estimation errors at most $\varepsilon$ uniformly over the model class requires at least order $\varepsilon^{-6}$ iterations for every fixed $γ$.

0.28