The Proximal Robbins–Monro Method
Abstract
The need for statistical estimation with large data sets has reinvigorated interest in iterative procedures and stochastic optimization. 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, in contrast, 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 Robbins and Monro (The annals of mathematical statistics, 1951, pp. 400–407), 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 standard procedures by achieving numerical stability, practically without trade-offs. 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 09, 2020
- Source ID
- 10.1111/rssb.12405
Entities
People
- Edoardo Airoldi
- Panos Toulis
- Thibaut Horel
Organizations
- Booth School of Business
- Department of Computer Science, University of Oxford
- Fox School of Business and Management
- Harvard University
- National Science Foundation
- Office of Naval Research
- Temple University
- University of Chicago