OptEMA: Adaptive Exponential Moving Average for Stochastic Optimization with Zero-Noise Optimality

• URL: http://arxiv.org/abs/2603.09923v1
• Date: Tue, 10 Mar 2026 17:19:54 GMT
• Title: OptEMA: Adaptive Exponential Moving Average for Stochastic Optimization with Zero-Noise Optimality
• Abstract summary: We introduce OptEMA and analyze two novel variants: OptEMA-M and OptEMA-V.<n>OptEMA is closed-loop and Lipschitz-free in the sense that its effective stepsizes are trajectory-dependent and do not require the Lipschitz constant for parameterization.<n>Both variants achieve a noise-adaptive convergence rate of $widetildemathcalO(T-1/2+1/2 T-1/4)$ for the average gradient norm, where $$ is the noise level.
• Score: 23.28384210732827
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Exponential Moving Average (EMA) is a cornerstone of widely used optimizers such as Adam. However, existing theoretical analyses of Adam-style methods have notable limitations: their guarantees can remain suboptimal in the zero-noise regime, rely on restrictive boundedness conditions (e.g., bounded gradients or objective gaps), use constant or open-loop stepsizes, or require prior knowledge of Lipschitz constants. To overcome these bottlenecks, we introduce OptEMA and analyze two novel variants: OptEMA-M, which applies an adaptive, decreasing EMA coefficient to the first-order moment with a fixed second-order decay, and OptEMA-V, which swaps these roles. Crucially, OptEMA is closed-loop and Lipschitz-free in the sense that its effective stepsizes are trajectory-dependent and do not require the Lipschitz constant for parameterization. Under standard stochastic gradient descent (SGD) assumptions, namely smoothness, a lower-bounded objective, and unbiased gradients with bounded variance, we establish rigorous convergence guarantees. Both variants achieve a noise-adaptive convergence rate of $\widetilde{\mathcal{O}}(T^{-1/2}+σ^{1/2} T^{-1/4})$ for the average gradient norm, where $σ$ is the noise level. In particular, in the zero-noise regime where $σ=0$, our bounds reduce to the nearly optimal deterministic rate $\widetilde{\mathcal{O}}(T^{-1/2})$ without manual hyperparameter retuning.

Related papers

• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max optimization has attracted increasing attention due to its applications in modern machine learning.<n>We provide a comprehensive theoretical of gradient descent (SGDA)<n>We develop new clipping-free algorithms, i.e., Stoc-GDAM and Stoc-TRmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
  arXiv  Detail & Related papers  (2026-09-05T12:49:28Z)
• Accelerated and Stable Convergence with Anchored Optimistic Method [39.242061448272615]
  We study first-order methods for solving monotone variational inequalities arising in min-max optimization.<n>We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration.
  arXiv  Detail & Related papers  (2026-06-19T15:26:10Z)
• OptMuon: Closed-Loop Orthogonalized Momentum Methods for Stochastic Optimization with Zero-Noise Optimality [23.28384210732827]
  We show that closed-loop scalar momentum.<n>optimization can be combined with Muon-style momentum.<n>optimization while retaining noise adaptivity and zero-noise optimality up to logarithmic factors.<n>These results show that OptMuon-A achieves the noise-rate.<n>(tildemathcal O(T-1/2+1/2T--1/2)) under average smoothness, while OptMuon-I achieves the noise-rate.<n>(tildemathcal O(T-1/2+
  arXiv  Detail & Related papers  (2026-06-07T18:59:24Z)
• Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates [3.083659340977661]
  We propose a variant of the auto-conditioned fast gradient method, referred to as AC-FGM.<n>The proposed method is fully adaptive to the Lipschitz constant, the horizon, and the noise level, enabling both adaptive stepsize selection and adaptive mini-batch sizing without line-search procedures.
  arXiv  Detail & Related papers  (2026-04-07T23:43:48Z)
• Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods [35.76482964927589]
  We analyze the semi-dual formulation of Entropic UOT and demonstrate its suitability for adaptive gradient methods.<n>We show that SGD methods adapt to this local curvature, achieving a convergence rate of $mathcalO(n/varepsilon T)$.<n>For the full batch discrete setting, we derive a nearly tight upper bound on local smoothness depending solely on the gradient step sizes.
  arXiv  Detail & Related papers  (2026-02-11T09:57:30Z)
• RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization [1.3537117504260623]
  Momentum methods, such as Polyak's Heavy Ball, are the standard for training deep networks but suffer from curvature-induced bias in settings.<n>We propose textbfRanSOM, a unified framework that eliminates this bias by replacing deterministic step sizes with randomized steps drawn from distributions with mean $_t$.<n>We instantiate this framework in two algorithms: textbfRanSOM-E for unconstrained optimization and textbfRanSOM-B for constrained optimization.
  arXiv  Detail & Related papers  (2026-02-06T16:09:36Z)
• Optimal High-probability Convergence of Nonlinear SGD under Heavy-tailed Noise via Symmetrization [50.49466204159458]
  We propose two novel estimators based on the idea of noise symmetrization.<n>We provide a sharper analysis and improved rates.<n>Compared to works assuming symmetric noise with moments, we provide a sharper analysis and improved rates.
  arXiv  Detail & Related papers  (2025-07-12T00:31:13Z)
• Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
  We investigate the roles of gradient normalization and clipping in ensuring the convergence of Gradient Descent (SGD) under heavy-tailed noise. Our work provides the first theoretical evidence demonstrating the benefits of gradient normalization in SGD under heavy-tailed noise. We introduce an accelerated SGD variant incorporating gradient normalization and clipping, further enhancing convergence rates under heavy-tailed noise.
  arXiv  Detail & Related papers  (2024-10-21T22:40:42Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  We show that Prospect, a gradient-based algorithm, enjoys linear convergence for smooth regularized losses. We also show that Prospect can converge 2-3$times$ faster than baselines such as gradient-based methods.
  arXiv  Detail & Related papers  (2023-10-21T00:03:54Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization [7.014966911550542]
  We consider the problem of training a deep neural network with nonsmooth regularization to retrieve a sparse sub-structure. We derive a new solver, called SR2, whose convergence and worst-case complexity are established without knowledge or approximation of the gradient's Lipschitz constant. Experiments on network instances trained on CIFAR-10 and CIFAR-100 show that SR2 consistently achieves higher sparsity and accuracy than related methods such as ProxGEN and ProxSGD.
  arXiv  Detail & Related papers  (2022-06-14T00:28:44Z)
• The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance [46.15915820243487]
  We show that AdaGrad-Norm exhibits an order optimal convergence of $mathcalOleft. We show that AdaGrad-Norm exhibits an order optimal convergence of $mathcalOleft.
  arXiv  Detail & Related papers  (2022-02-11T17:37:54Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling.<n>We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

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.