Gradient-based learning algorithms with constant-error estimators: stability and convergence

Arunselvan Ramaswamy, Shalabh Bhatnagar

Introduction

In the classical theory of stochastic optimization, Gradient Descent (GD) is guaranteed to converge under the assumption that gradient estimation errors eventually vanish. This requirement often forces practitioners to implement complex learning rate schedules or decay parameters designed to drive noise to zero. However, many real-world applications—ranging from reinforcement learning to queuing systems—operate in environments where noise is persistent and the exact gradient is never truly accessible.

This paper addresses a fundamental gap between theory and practice: What happens to Gradient Descent when gradient errors are bounded but never actually disappear? By utilizing tools from viability theory and differential inclusions, the authors provide a rigorous mathematical foundation for algorithms operating with constant-error estimators, proving that perfection is not a prerequisite for stability or convergence.

Problem Formulation

The authors analyze the standard Gradient Descent recursion:

$$x_{n+1} = x_n - \gamma_n(\nabla f(x_n) + \epsilon_n)$$

In this model, $\epsilon_n$ represents an error term bounded by a constant $\epsilon$. Unlike traditional stochastic approximation, which requires $\epsilon_n \to 0$ as $n \to \infty$, this work assumes the error remains non-zero. The central challenge is determining whether the iterates $x_n$ will diverge to infinity or remain trapped in a meaningful region near the optimal solution.

Theoretical Framework

To analyze this system, the authors move beyond traditional discrete-time analysis, employing viability theory and differential inclusions. Their approach involves three key steps:

  1. Stability (Almost Sure Boundedness): They prove that the iterates do not diverge. By constructing a continuous-time interpolated trajectory of the GD steps and applying a projective scheme, they demonstrate that the trajectory remains contained within a bounded set.
  2. Convergence to a Neighborhood: The authors show that the algorithm tracks the true gradient flow closely enough to eventually enter a "chain recurrent set." Specifically, the iterates converge to a $\delta$-neighborhood of the true minimum, where the size of $\delta$ is directly proportional to the error bound $\epsilon$.
  3. Decoupling Learning Rates: A significant contribution of this framework is that it decouples the error bound from the step-size $\gamma_n$. This allows practitioners to use standard learning rate schedules (where the sum of steps is infinite but the sum of squares is finite) without needing to satisfy the restrictive constraints typically required to force error decay.

Application to SPSA

The theoretical framework provides immediate justification for a common "hack" used in Simultaneous Perturbation Stochastic Approximation (SPSA). SPSA typically requires a perturbation parameter $c_n$ that shrinks to zero to ensure asymptotic convergence. However, shrinking $c_n$ often causes variance to explode in early iterations, leading many practitioners to keep $c$ constant. This paper provides the first formal proof that keeping $c$ constant is mathematically sound, as it simply transforms the problem into a bounded-error GD scenario that converges to a stable neighborhood.

Empirical Results

The authors validated their claims using synthetic simulations on a 10-dimensional quadratic objective function $f(x) = x^T Q x$.

  • Stability: Even with a constant noise vector added at every step, the iterates remained bounded and did not diverge.
  • Error Scaling: The final distance from the true optimum scaled linearly with the size of the noise $\epsilon$. For instance, an error of $\epsilon \approx 0$ resulted in a distance of $0.0003$ from the origin, while a larger error of $\epsilon = 2$ resulted in a distance of $0.1$.
  • SPSA Performance: Simulations confirmed that larger constant perturbation parameters ($c$) led to convergence further from the optimum, precisely as predicted by the neighborhood convergence theory.

Limitations and Future Work

While the paper provides a robust foundation for persistent noise in GD, it notes certain topological limitations. The proof assumes the "chain recurrent set" of the gradient flow aligns with the minimum set; if an objective function contains strange topological features like chain recurrent points outside the minima, the algorithm might converge to those points instead. Additionally, the study focuses on asymptotic behavior and does not yet provide specific convergence rates. Future research may extend this framework to second-order methods like Newton’s method or incorporate martingale noise terms to account for stochastic variance alongside persistent bias.

Summary updated

BibTeX
@article{ramaswamy2018gradient,
  author = {Arunselvan Ramaswamy and Shalabh Bhatnagar},
  title = {{Gradient-based learning algorithms with constant-error estimators: stability and convergence}},
  journal = {IEEE Trans. Automatic Control},
  year = {2018},
  doi = {10.1109/tac.2017.2744598},
}
Figure