Implicit stochastic approximation

Panos Toulis, Edoardo M. AiroldiarXiv 2015 · arXiv

Abstract

The need to carry out parameter estimation from massive data has reinvigorated interest in iterative estimation methods, in statistics and machine learning. Classic work includes deterministic gradient-based methods, such as quasi-Newton, and stochastic gradient descent and its variants, including adaptive learning rates, acceleration and averaging. Current work increasingly relies on methods that employ proximal operators, leading to updates defined through implicit equations, which need to be solved at each iteration. Such methods are especially attractive in modern problems with massive data because they are numerically stable and converge with minimal assumptions, among other reasons. However, while the majority of existing methods can be subsumed into the gradient-free stochastic approximation framework developed by Robbins and Monro (1951), there is no such framework for methods with implicit updates. Here, we conceptualize a gradient-free implicit stochastic approximation procedure, and develop asymptotic and non-asymptotic theory for it. This new framework provides a theoretical foundation for gradient-based procedures that rely on implicit updates, and opens the door to iterative estimation methods that do not require a gradient, nor a fully known likelihood.

Introduction

Iterative estimation, particularly Stochastic Gradient Descent (SGD) and the broader Robbins–Monro (RM) framework, forms the foundation of modern machine learning. However, these methods often suffer from extreme sensitivity to the learning rate ($\gamma$). A learning rate that is too small leads to agonizingly slow convergence, while one that is slightly too large can cause numerical divergence, especially in models with non-Lipschitz likelihoods such as Poisson regression.

In deterministic optimization, proximal updates offer a solution. These "implicit" updates are famously stable because the next state depends on the gradient at that future state. Until now, a general framework for applying these proximal benefits to stochastic, gradient-free, or "black-box" settings was missing. This work fills that theoretical gap by introducing the Proximal Robbins–Monro (PRM) method.

Methodology

The authors propose the Proximal Robbins–Monro Procedure, which reformulates the standard update $\theta_n = \theta_{n-1} - \gamma_n H(\theta_{n-1}, \xi_n)$ into a proximal version: $$\theta_n = \theta_{n-1} - \gamma_n H(\theta_n^+, \xi_n)$$ where $\theta_n^+$ is a "proximal" point. This implicit structure "pulls" iterates toward the solution, preventing the overshooting common in standard SGD.

Comparison of Classical and Proximal Robbins–Monro frameworks across different observability conditions.

Depending on whether the random component $\xi$ is observable, the paper develops two practical implementations:

  1. Implicit SGD (ISGD): Applicable when $\xi$ is directly observable. This results in an implicit equation that can often be solved efficiently, for instance, via a one-dimensional fixed-point search in Generalized Linear Models.
  2. Proximal Stochastic Fixed-Point (PSFP): Designed for "black-box" settings where the objective function is not analytically available. It employs a nested Robbins–Monro loop to solve the proximal update's characteristic equation.

Experimental Evaluation

The method's performance was evaluated using simulated experiments designed to test numerical stability:

  • Linear Normal Model: A benchmark ($p=6, N=10,000$) to compare Mean Squared Error (MSE) and learning rate sensitivity.
  • Poisson Regression: A challenging non-Lipschitz case where standard SGD is highly prone to divergence.
  • Iterative Quantile Estimation: A classic problem demonstrating how standard methods can get "stuck" when learning rates are misspecified.

Key Insights

The PRM method provides "numerical armor" without sacrificing convergence speed. It maintains the $O(1/n)$ rate of standard RM under strong convexity but is exponentially less sensitive to initial errors and the choice of the initial learning rate ($\gamma_1$).

A critical finding is the avoidance of the "stuck" phenomenon. In quantile estimation, a large learning rate can push standard RM iterates so far into the "flat" region of a distribution that recovery would take an astronomical number of iterations. PRM's backward-forward structure inherently avoids this. Furthermore, even when using the nested PSFP method, the procedure remains more stable than a single-loop classical RM approach.

Results

Theoretical analysis provides the first non-asymptotic error bounds for stochastic proximal points, showing they are asymptotically normal and as efficient as perfectly tuned classical procedures. Empirically, in Poisson regression, while classical SGD diverged for most learning rates above a small threshold, ISGD and the SFP method remained stable across a wide range of specifications. In quantile estimation, PRM iterates remained centered with low variance, whereas classical RM iterates overshot significantly.

Conclusion and Future Work

While PRM offers significant stability gains, some areas remain for future exploration. For objectives that are only convex, the current $O(n^{-1/3})$ rate is slower than the minimax $O(n^{-1/2})$, though Polyak-Ruppert averaging might bridge this gap. Additionally, the nested PSFP method introduces computational overhead, which, while often logarithmic, may be relevant in resource-constrained settings. Finally, extending these stability proofs to non-convex landscapes, such as deep neural networks, is a high-priority direction for future research.

Summary updated

Abstract

The need to carry out parameter estimation from massive data has reinvigorated interest in iterative estimation methods, in statistics and machine learning. Classic work includes deterministic gradient-based methods, such as quasi-Newton, and stochastic gradient descent and its variants, including adaptive learning rates, acceleration and averaging. Current work increasingly relies on methods that employ proximal operators, leading to updates defined through implicit equations, which need to be solved at each iteration. Such methods are especially attractive in modern problems with massive data because they are numerically stable and converge with minimal assumptions, among other reasons. However, while the majority of existing methods can be subsumed into the gradient-free stochastic approximation framework developed by Robbins and Monro (1951), there is no such framework for methods with implicit updates. Here, we conceptualize a gradient-free implicit stochastic approximation procedure, and develop asymptotic and non-asymptotic theory for it. This new framework provides a theoretical foundation for gradient-based procedures that rely on implicit updates, and opens the door to iterative estimation methods that do not require a gradient, nor a fully known likelihood.
BibTeX
@misc{toulis2015implicit,
  author = {Panos Toulis and Edoardo M. Airoldi},
  title = {{Implicit stochastic approximation}},
  year = {2015},
  eprint = {1510.00967},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.00967},
}

Loading related content...

Figure