Analysis of Gradient Descent Methods With Nondiminishing Bounded Errors

Arunselvan Ramaswamy, Shalabh Bhatnagar

Abstract

This paper provides a rigorous analysis of gradient descent (GD) algorithms in environments where gradient errors do not necessarily vanish asymptotically. We present sufficient conditions for both the stability (almost sure boundedness of iterates) and the convergence of GD under bounded, non-diminishing gradient errors. Beyond ensuring stability, we demonstrate that such algorithms converge to a small neighborhood of the minimum set, the size of which is determined by the magnitude of the gradient errors. Notably, our framework also recovers the convergence of GD with vanishing errors as a special case. Our results extend the work of Mangasarian & Solodov, Bertsekas & Tsitsiklis, and Tadic & Doucet by removing additional restrictions on step-sizes, thereby preserving standard learning rates in machine learning applications. We validate these theoretical contributions through an implementation of Simultaneous Perturbation Stochastic Approximations (SPSA) with constant sensitivity parameters.

Introduction

In the idealized theoretical landscape of optimization, Gradient Descent (GD) assumes access to the true gradient of a target function. However, in practical machine learning and complex simulation environments, we frequently encounter noisy or approximate gradients. Traditional convergence proofs for GD typically rely on the assumption that this noise eventually vanishes as the algorithm progresses.

In many real-world applications—such as systems with inherent measurement noise or specific stochastic approximation schemes—errors are persistent and non-diminishing. Previous attempts to analyze these scenarios often imposed restrictive conditions on step-sizes (learning rates) to maintain control over the iterates, which can significantly hinder training speed and practical utility. This paper addresses this gap by providing a framework that guarantees stability and convergence to a neighborhood of the minimum without requiring specialized learning rate schedules.

Theoretical Framework: Viability and Differential Inclusions

To analyze GD with persistent errors, the authors move away from traditional Ordinary Differential Equation (ODE) analysis, opting instead for Viability Theory and Differential Inclusions. This shift allows for a more robust treatment of uncertainty in the gradient update.

Marchaud Maps

Rather than modeling the update as a single deterministic vector, the authors utilize set-valued maps known as Marchaud maps. By treating the gradient plus any bounded error as a "ball" of possible directions, the algorithm's trajectory is modeled as a differential inclusion. This captures the full range of possible behaviors under bounded noise.

Projective Schemes for Stability

Proving stability—ensuring that iterates do not diverge to infinity—is often more complex than proving convergence once boundedness is established. The authors employ a projective scheme using a rescaling technique. This approach demonstrates that if the iterates were to grow toward infinity, the "average" behavior of the system (the fluid limit) would eventually force the iterates back toward the origin, ensuring almost sure boundedness.

Stability and Neighborhood Convergence

The paper establishes two primary theoretical results:

  1. Theorem 1 (Stability): Under general conditions, the iterates of the GD algorithm remain bounded almost surely, even when the gradient error does not go to zero.
  2. Theorem 2 (Convergence): The algorithm is shown to converge to a $\delta$-neighborhood of the minimum set. Crucially, the size of this neighborhood is a direct function of the error bound. If the error were to vanish, the neighborhood would shrink to the minimum set itself, aligning with classical results.

One of the most significant practical insights is the Learning Rate Independence. The stability and convergence guarantees do not require modifications to the standard step-size assumptions (where $\sum \gamma_n = \infty$ and $\sum \gamma_n^2 < \infty$). This ensures that practitioners do not have to sacrifice convergence speed to satisfy the theoretical requirements of the error-prone environment.

Implementation: SPSA with Constant Sensitivity

The utility of this framework is demonstrated through an implementation of Simultaneous Perturbation Stochastic Approximation (SPSA). Standard SPSA requires the sensitivity parameter ($c_n$) to vanish to ensure convergence. However, vanishing parameters can lead to numerical instability.

Using the proposed framework, the authors justify SPSA-C, a variant using a constant sensitivity parameter ($c_n = c$). Their analysis proves that SPSA-C remains stable and converges to a neighborhood of the solution, providing a simpler and more numerically stable alternative for practitioners.

Experimental Results

The authors validated their theory using synthetic experiments on quadratic objective functions ($f(x) = x^T Q x$). By introducing constant noise vectors, they confirmed the "non-diminishing error" theory.

Key experimental findings include:

  • Robustness to Sensitivity: In a 10-dimensional quadratic problem, the log-distance from the origin remained extremely low (between -38 and -34) after 8,000 iterations, even as the sensitivity parameter $c$ was scaled from 0.1 to 10.
  • Error Plateaus: The experiments revealed a "stepped" relationship between error magnitude and convergence. The iterates tend to stay within a specific neighborhood for a range of error values before shifting to a larger neighborhood as the error increases.

Conclusion and Future Work

This work provides a more general and flexible foundation for understanding Gradient Descent in noisy environments. By proving that stability and neighborhood convergence can be maintained without restrictive step-size conditions, the authors bridge the gap between optimization theory and practical stochastic applications.

Future research directions include deriving specific convergence rates for non-diminishing errors (e.g., $O(1/n)$) and extending the experimental validation from quadratic functions to more complex, non-convex landscapes with multiple local minima. Additionally, the authors suggest exploring more complex noise structures, such as the inclusion of martingale noise terms at each iteration.

Summary updated

Abstract

The main aim of this paper is to provide an analysis of gradient descent (GD) algorithms with gradient errors that do not necessarily vanish, asymptotically. In particular, sufficient conditions are presented for both stability (almost sure boundedness of the iterates) and convergence of GD with bounded, (possibly) non-diminishing gradient errors. In addition to ensuring stability, such an algorithm is shown to converge to a small neighborhood of the minimum set, which depends on the gradient errors. It is worth noting that the main result of this paper can be used to show that GD with asymptotically vanishing errors indeed converges to the minimum set. The results presented herein are not only more general when compared to previous results, but our analysis of GD with errors is new to the literature to the best of our knowledge. Our work extends the contributions of Mangasarian &amp; Solodov, Bertsekas &amp; Tsitsiklis and Tadic &amp; Doucet. Using our framework, a simple yet effective implementation of GD using simultaneous perturbation stochastic approximations (SP SA), with constant sensitivity parameters, is presented. Another important improvement over many previous results is that there are no `additional' restrictions imposed on the step-sizes. In machine learning applications where step-sizes are related to learning rates, our assumptions, unlike those of other papers, do not affect these learning rates. Finally, we present experimental results to validate our theory.
BibTeX
@article{ramaswamy2018analysis,
  author = {Arunselvan Ramaswamy and Shalabh Bhatnagar},
  title = {{Analysis of Gradient Descent Methods With Nondiminishing Bounded Errors}},
  journal = {IEEE Trans. Automatic Control},
  year = {2018},
  doi = {10.1109/tac.2017.2744598},
}
Figure