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