Stable Robbins-Monro approximations through stochastic proximal updates

Panos Toulis, Thibaut Horel, Edoardo M. Airoldi

In the world of machine learning and large-scale statistics, Stochastic Gradient Descent (SGD) is the undisputed king. However, even kings have weaknesses. If you've ever spent hours "babysitting" a model—tweaking the learning rate because the loss suddenly exploded—you’ve encountered the fundamental instability of the Robbins-Monro framework.

A new paper by Panos Toulis, Thibaut Horel, and Edoardo M. Airoldi titled "Stable Robbins-Monro approximations through stochastic proximal updates" introduces a clever way to build a "safety net" into these iterative procedures. By borrowing ideas from proximal optimization, they’ve created a version of stochastic approximation that is remarkably difficult to break.

The Landscape of Stochastic Approximation

Most iterative estimation methods rely on the Robbins-Monro (1951) framework. In plain English: to find a parameter $\theta$, you take your current guess, calculate a noisy update (like a gradient), multiply it by a learning rate ($\gamma_n$), and move. The problem is the learning rate. If $\gamma_n$ is too small, the model converges at a snail's pace. If it’s even slightly too large, the updates can overshoot wildly, leading to numerical divergence.

Taxonomy of stochastic approximation methods based on objective function knowledge and update type.

As shown in the table above, while "proximal" (implicit) methods exist to stabilize deterministic optimization for analytically known objectives, there hasn't been a general way to apply this stability to the broader world of stochastic approximation—especially when we don't have a neat analytical formula for our objective function.

Implicit Stochastic Approximation (ISA)

The authors propose Implicit Stochastic Approximation (ISA) to bridge this gap. The core idea is to move from an "explicit" update (where the next step is a simple function of the current step) to an "implicit" update. In this framework, the new estimate $\theta_n$ is defined by a fixed-point equation: it depends on a noisy observation evaluated at an intermediate point $\theta_n^+$.

This acts as a Stochastic Proximal Link, essentially "shrinking" the update and pulling the estimate back if it tries to jump too far. This "pull-back" effect is crucial for stability. For example, in quantile estimation, if a standard Robbins-Monro update overshoots, it can get "stuck" in a region where the gradient is nearly zero. The implicit update naturally prevents these catastrophic overshoots.

Handling Unknown Objectives: Nested Procedures

A major contribution of this paper is the Nested Stochastic Approximation. If you don't know the analytical form of your objective (e.g., you're doing quantile estimation), you can't solve the implicit equation directly. The authors show you can run a second, smaller Robbins-Monro loop inside each main iteration to approximate the stable update. While this adds some computational overhead, it allows the method to be applied to "black-box" scenarios where only noisy samples are available.

Key Results and Stability

The authors demonstrate that ISA provides stability without trade-offs. Usually, making an algorithm more stable makes it slower. However, the authors prove that ISA has the same asymptotic normality as Robbins-Monro. You get the safety of the proximal update for "free" in terms of long-term convergence speed.

In practical tests like quantile estimation, the classic Robbins-Monro method failed spectacularly when the learning rate was high, overshooting the target and getting stuck at extreme values. In contrast, the proposed Nested ISA remained stable and accurate across the entire range of tested learning rates. Furthermore, new non-asymptotic bounds show that ISA "forgets" its initial conditions exponentially fast, whereas standard RM can be dominated by initial errors for a long time if the learning rate is misspecified.

Conclusion

By successfully bridging the gap between root-finding (the statistical view of RM) and proximal operators (the optimization view), this research provides a robust framework for large-scale estimation. While the nested version introduces some computational cost, the gain in numerical robustness makes it a powerful tool for practitioners who cannot afford to manually tune learning rates for every new dataset.

Summary updated

Abstract

The need for parameter estimation with massive data has reinvigorated interest in iterative estimation procedures. Stochastic approximations, such as stochastic gradient descent, are at the forefront of this recent development because they yield simple, generic, and extremely fast iterative estimation procedures. Such stochastic approximations, however, are often numerically unstable. As a consequence, current practice has turned to proximal operators, which can induce stable parameter updates within iterations. While the majority of classical iterative estimation procedures are subsumed by the framework of Robbins and Monro (1951), there is no such generalization for stochastic approximations with proximal updates. In this paper, we conceptualize a general stochastic approximation method with proximal updates. This method can be applied even in situations where the analytical form of the objective is not known, and so it generalizes many stochastic gradient procedures with proximal operators currently in use. Our theoretical analysis indicates that the proposed method has important stability benefits over the classical stochastic approximation method. Exact instantiations of the proposed method are challenging, but we show that approximate instantiations lead to procedures that are easy to implement, and still dominate classical procedures by achieving numerical stability without tradeoffs. This last advantage is akin to that seen in deterministic proximal optimization, where the framework is typically impossible to instantiate exactly, but where approximate instantiations lead to new optimization procedures that dominate classical ones.
BibTeX
@article{toulis2020stable,
  author = {Panos Toulis and Thibaut Horel and Edoardo M. Airoldi},
  title = {{Stable Robbins-Monro approximations through stochastic proximal updates}},
  journal = {Journal of the Royal Statistical Society Series B (Statistical Methodology)},
  year = {2020},
  doi = {10.1111/rssb.12405},
}
Figure