mlsanityData to 7 Oct 2026

Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Results

arXiv 2209.05372 ↗First posted 12 Sep 2022math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper, we present a unified and general framework for analyzing the batch updating approach to nonlinear, high-dimensional optimization. The framework encompasses all the currently used batch updating approaches, and is applicable to nonconvex as well as convex functions. Moreover, the framework permits the use of noise-corrupted gradients, as well as first-order approximations to the gradient (sometimes referred to as "gradient-free" approaches). By viewing the analysis of the iterations as a problem in the convergence of stochastic processes, we are able to establish a very general theorem, which includes most known convergence results for zeroth-order and first-order methods. The analysis of "second-order" or momentum-based methods is not a part of this paper, and will be studied elsewhere. However, numerical experiments indicate that momentum-based methods can fail if the true gradient is replaced by its first-order approximation. This requires further theoretical analysis.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 28 of its 60 references that are in the map. First posted on arXiv 12 Sep 2022.

Builds on

28 of 60 references.

References · 28

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2016An overview of gradient descent optimization algorithmscited by 1,021
  4. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 471
  5. 2015Coordinate Descent Algorithmscited by 218
  6. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  7. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  8. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  9. 2017Revisiting Distributed Synchronous SGDcited by 142
  10. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 94
  11. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 80
  12. 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 79
16 more
  1. 2019Convergence rates for the stochastic gradient descent method for non-convex objective functionscited by 66
  2. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 62
  3. 2017Regularizing Deep Neural Networks by Noise: Its Interpretation and Optimizationcited by 56
  4. 2019Zeno++: Robust Fully Asynchronous SGDcited by 53
  5. 2018Convergence and Dynamical Behavior of the ADAM Algorithm for Non-Convex Stochastic Optimizationcited by 47
  6. 2021A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimizationcited by 46
  7. 2020Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Samplingcited by 45
  8. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
  9. 2022On Almost Sure Convergence Rates of Stochastic Gradient Methodscited by 32
  10. 2020On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settingscited by 27
  11. 2013On the Complexity Analysis of Randomized Block-Coordinate Descent Methodscited by 21
  12. 2014Block stochastic gradient iteration for convex and nonconvex optimizationcited by 21
  13. 2018Convergence guarantees for a class of non-convex and non-smooth optimization problemscited by 15
  14. 2020A One-bit, Comparison-Based Gradient Estimatorcited by 15
  15. 2021Convergence of sequences: a surveycited by 10
  16. 2022Convergence of Stochastic Approximation via Martingale and Converse Lyapunov Methodscited by 8

Built on by

Not cited yet.