Source-linked AI summary
Convergence rates for the RMSprop optimizer with full control of the hyperparameters
Steffen Dereich, Arnulf Jentzen
TL;DR
Uniformly bounded error estimates near critical hyperparameter regimes remain open even for strongly convex stochastic optimization. This work essentially solves that problem for RMSprop using inverse moment bounds, obtaining a stopped objective bound with controlled initialization, approximation, and memory terms.
Problem
Uniformly bounded error constants for adaptive optimizers near critical hyperparameter regimes remain an open problem, including strongly convex stochastic optimization.
Method
The analysis uses suitable inverse moment bounds for RMSprop’s second moment process to control the stopped objective evaluation.
Results
The bound consists of an initialization term decaying exponentially in training time, a stochastic approximation remainder of order γ_n, and a memory error of order (1 − β)^2.
Takeaways & Limitations
The error constants are uniformly controlled over admissible step sizes, β, and ε ∈ [0,1], including the unregularized case ε = 0.
Takeaways & Limitations
The estimate applies only on the event {τ ≥ n}, until the optimization process leaves the measurable set V; inverse moment bounds may also fail before second-moment components become non-degenerate.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper addresses the open problem of obtaining RMSprop error estimates whose constants remain uniformly bounded across critical hyperparameter regimes. It proves non-asymptotic bounds combining initialization, stochastic approximation, and memory errors, supported by inverse-moment estimates for RMSprop’s second-moment process.
- Motivation: Adaptive optimizers such as RMSprop, Adam, and AdamW use step sizes, regularization ε, and second-moment decay β as key hyperparameters.Adam and AdamW’s adaptivity components essentially coincide with RMSprop; ε prevents division by zero, while β controls the weight assigned to recent stochastic gradients.
- Research gap: Uniformly bounded error constants near critical hyperparameter values remain an open problem even for strongly convex stochastic optimization.The relevant regimes include ε close to zero and β close to one.
- Main result: The main result bounds the expected stopped objective evaluation by an exponentially decaying initialization term, a stochastic approximation remainder of order γ_n, and a memory error of order (1 − β)^2.The estimate controls the squared mean-square strong optimization error in the strongly convex case.
- Error terms: The stochastic approximation term C0γ_n is the usual standard-SGD error and is described as optimal and unimprovable.The memory-error power two is also suggested by numerical and analytical considerations for Adam.
- Scope: The stated error estimate is restricted to the event that the stopping time has not occurred, so it applies only while the process remains inside the measurable set V.The paper discusses sufficiently large compact balls and cites prior results establishing a priori bounds for related adaptive methods.
- Proof strategy: The proof introduces inverse-moment bounds for RMSprop’s second-moment process and combines post-startup estimates with an early-stage argument to obtain a recursion valid from the first step.Inverse-moment bounds cannot generally hold before a component reaches a sufficiently large non-degenerate level.
2. The abstract recursion estimate in Proposition 2.1
Proposition 2.1 derives a stopped one-step recursion for the objective by separating drift, covariance, and quadratic contributions. Smoothness, conditional covariance decomposition, and bounds on the RMSprop denominator reduce the analysis to controlling these terms.
- 2. The abstract recursion estimate in Proposition 2.1: The proposition reduces the stopped objective analysis to a scalar recursion by separating coercive drift, covariance correction, and quadratic Taylor terms.The recursion is obtained from a smoothness inequality and controls the three contributions separately.
- 2. The abstract recursion estimate in Proposition 2.1: When ε = 0, inverse factors and conditional covariances are evaluated on the stopped intersection with G_n,i and extended by zero outside it.This convention keeps the proposition well-defined in the unregularized case.
- 2. The abstract recursion estimate in Proposition 2.1: The recursion applies on the event {τ ≥ n}, where the process remains in V and θ_n−1 therefore satisfies the local assumptions.The stopping time τ is the first exit time from V after the relevant starting index.
- 2. The abstract recursion estimate in Proposition 2.1: Conditional covariance decomposition uses the predictable events G_n,i and the conditional mean identity E[X^(i)(θ_n−1,U_n)∣F_n−1] = f_X^(i)(θ_n−1).These identities connect the innovation coordinates to the objective-gradient structure inside the stopped recursion.
- 2. The abstract recursion estimate in Proposition 2.1: The covariance term is bounded with Cauchy–Schwarz and a β-dependent factor, while the lower Łojasiewicz bound controls the denominator-related contribution.The proof then combines the drift, covariance, and quadratic estimates using Young’s inequality.
3. Analysis of the property in item (iii) of Proposition 2.1
This section establishes inverse-moment control for RMSprop’s second-moment process, then uses it to bound the covariance contribution in Proposition 2.1. The proof combines startup-time decomposition, conditional Laplace estimates, and negative-moment bounds.
- 3. Analysis of the property in item (iii) of Proposition 2.1: The analysis separates the initial regime from the asymptotic 1 − β regime through a β-dependent quotient involving the second-moment process.This distinction is needed because inverse-moment bounds may only hold after a coordinatewise startup time.
- 3. Analysis of the property in item (iii) of Proposition 2.1: The covariance correction is bounded by a conditional third moment of the innovation multiplied by a negative third moment of the preceding second-moment coordinate.A coordinatewise Lipschitz argument produces this structure before applying the inverse-moment estimates.
- 3. Analysis of the property in item (iii) of Proposition 2.1: For n ≤ (1 − β)^−1, the quotient (1 − β)/(1 − β^n) is bounded by 2/n, while for later n it is controlled by a constant multiple of 1 − β.These elementary bounds explain the transition from startup behavior to the asymptotic memory scale.
- 3. Analysis of the property in item (iii) of Proposition 2.1: (c,q)-regular innovations yield conditional exponential-moment estimates for stopped second-moment coordinates, which are converted into arbitrary negative-moment bounds.The resulting estimates support control of inverse factors after the corresponding startup time.
- 3. Analysis of the property in item (iii) of Proposition 2.1: The coordinatewise startup time σ(i) records when the i-th second-moment component becomes sufficiently large for inverse-moment estimates to apply.The proof decomposes according to the hitting time and treats the cases σ(i) = m and σ(i) < n separately.
5. Technical estimates for the property in item (ii) of Proposition 2.1
The section controls the quadratic Taylor remainder by exploiting the monotonicity of an inverse squared conditioner. Conditional covariance is nonpositive, allowing factor separation and coordinatewise estimates under negative-moment conditions.
- Covariance control: The inverse squared conditioner decreases with the current squared innovation, yielding a nonpositive conditional covariance.The covariance identity is established by comparing conditionally independent copies and applying monotonicity.
- Coordinatewise estimate: Conditional second-moment and negative first-moment bounds for the innovation provide the required coordinatewise estimate.These bounds are combined after separating the covariance-controlled factors.
- Covariance extension: Conditional monotone convergence extends the covariance argument from bounded decreasing approximations to the full extended-valued function.The approximating functions are bounded and decreasing, and the covariance is considered where it is well-defined.
- Handling ε = 0: For ε = 0, inverse factors and conditional covariances are evaluated on the event where the relevant second-moment coordinate is positive and extended by zero otherwise.The negative-moment assumption ensures positivity on the active event.
6. Initialisation estimates
The initialization analysis estimates how quickly each conditioner coordinate reaches the regime where negative moments are available. Lower-tail bounds are iterated over memory-scale blocks, producing an exponential startup failure bound uniform in β.
- Block iteration: Startup-time failure probabilities decay geometrically across blocks of length comparable to (1 − β)^−1.The induction yields P(τ̄ ≥ t_j, σ(i) > t_j) ≤ η^j.
- Tail estimates: Conditional Laplace-transform bounds are converted into lower-tail estimates using exponential Chebyshev inequalities.The estimates are applied conditionally after shifting the exit time to each block.
- Initialization conclusion: The resulting bound controls the probability that a coordinate has not started before the process exits the prescribed region.This is the event P(τ̄ ≥ n, σ(i) > n), bounded by η^j at block endpoints.
7. Combining the estimates before and after the coordinate startup times
The section combines late-regime moment estimates with early-regime self-normalization and startup-tail bounds. These ingredients yield a Lyapunov recursion whose iteration gives the main non-asymptotic error estimate with constants uniform in β and ε.
- Regime decomposition: Late coordinates use negative-moment, covariance, and quadratic estimates, while early coordinates use direct self-normalization and startup-tail control.The split is made according to whether each coordinate’s startup time has occurred.
- Recursion iteration: Iterating the scalar recursion yields an exponentially decaying initialization term together with the remaining error terms for every gradient step.The iteration starts at time 1 and uses 1 − x ≤ e^−x.
- Uniform hyperparameter control: Theorem 1.1 specializes the general estimate to ε ∈ [0,1], with constants independent of ε and uniformly controlled over admissible β and step-size sequences.The proof explicitly tracks the dependence of the constants and derives the stated estimate for n ≥ 2, with n = 1 handled directly.
- Explicit constants: The error constants C0 and C1 have exact representations and explicit upper bounds in terms of the theorem’s model and regularity parameters.The paper states that these constants can be explicitly specified and estimated from above.
8. Criteria and examples for regular minibatch innovations
The paper gives criteria for verifying regularity of minibatch innovations and applies them to strongly convex coordinate gradients, risk-sensitive exponential tilting, and compactly supported nonlinear regression. These results provide the assumptions needed by the RMSprop error theorem in concrete settings.
- Regularity criterion: A small-ball criterion converts lower bounds on innovation probabilities into (c,q)-regularity.Lemma 8.1 supplies the regularity constants from the small-ball estimate.
- Strongly convex gradients: Strong convexity, an upper density bound, and bounded support yield regularity for minibatch innovations with strongly convex coordinate gradients.The bounded-support condition controls boundary layers that an upper density bound alone does not uniformly control.
- Theorem assumptions: Uniformly bounded coordinate derivatives additionally verify the boundedness assumption required by Theorem 1.1.This implication is stated for the strongly convex coordinate-gradient construction.
- Risk-sensitive example: Risk-sensitive exponential tilting satisfies the criterion because its coordinate gradients are strongly convex in the data variable and uniformly bounded on compact sets.The resulting optimizer parameters depend on Laplace transforms of the random energies rather than only on one fixed moment.
- Nonlinear regression: For compactly supported nonlinear regression, negative-moment and reverse Hölder arguments provide regularity and boundedness of the innovation.Scaling the innovation changes the regularity parameters and doubles the uniform bound.
- Application scope: The resulting constants in the nonlinear-regression application can be chosen independent of the initial point, step-size sequence, β, and ε.The conclusion applies Theorem 1.1 once the regularity and boundedness conditions are verified.