# The Proximal Robbins-Monro Method

arXiv: https://arxiv.org/abs/1510.00967 · HTML: https://mlsanity.com/paper/1510.00967/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2015.

## Built on by (most cited first, 14 of 14)

- [Forward-backward Gaussian variational inference via JKO in the Bures-Wasserstein Space](https://mlsanity.com/paper/2304.05398/) (2023)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum](https://mlsanity.com/paper/2111.06171/) (2021)
- [Tuning Stochastic Gradient Algorithms for Statistical Inference via Large-Sample Asymptotics](https://mlsanity.com/paper/2207.12395/) (2022)
- [Variance reduction techniques for stochastic proximal point algorithms](https://mlsanity.com/paper/2308.09310/) (2023)
- [Stable Nonconvex-Nonconcave Training via Linear Interpolation](https://mlsanity.com/paper/2310.13459/) (2023)
- [Statistical inference with implicit SGD: proximal Robbins-Monro vs. Polyak-Ruppert](https://mlsanity.com/paper/2206.12663/) (2022)
- [Implicit Updates for Average-Reward Temporal Difference Learning](https://mlsanity.com/paper/2510.06149/) (2025)
- [The Stochastic Proximal Distance Algorithm](https://mlsanity.com/paper/2210.12277/) (2022)
- [A Robbins--Monro Sequence That Can Exploit Prior Information For Faster Convergence](https://mlsanity.com/paper/2401.03206/) (2024)
- [Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers](https://mlsanity.com/paper/2401.15838/) (2024)
- [Tracking the Median of Gradients with a Stochastic Proximal Point Method](https://mlsanity.com/paper/2402.12828/) (2024)
- [Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms](https://mlsanity.com/paper/2602.05489/) (2026)
- [Fast Compute for ML Optimization](https://mlsanity.com/paper/2602.14280/) (2026)

## Abstract (arXiv)

The need for parameter estimation with massive datasets has reinvigorated interest in stochastic optimization and iterative estimation procedures. Stochastic approximations are at the forefront of this recent development as they yield procedures that are simple, general, and fast. However, standard stochastic approximations are often numerically unstable. Deterministic optimization, on the other hand, increasingly uses proximal updates to achieve numerical stability in a principled manner. A theoretical gap has thus emerged. While standard stochastic approximations are subsumed by the framework of Robbins and Monro (1951), there is no such framework for stochastic approximations with proximal updates. In this paper, we conceptualize a proximal version of the classical Robbins-Monro procedure. Our theoretical analysis demonstrates that the proposed procedure has important stability benefits over the classical Robbins-Monro procedure, while it retains the best known convergence rates. Exact implementations of the proximal Robbins-Monro procedure are challenging, but we show that approximate implementations lead to procedures that are easy to implement, and still dominate classical procedures by achieving numerical stability, practically without tradeoffs. Moreover, approximate proximal Robbins-Monro procedures can be applied even when the objective cannot be calculated analytically, and so they generalize stochastic proximal procedures currently in use.