A Retrospective Approximation Approach for Smooth Stochastic Optimization

David Newton (), Raghu Bollapragada (), Raghu Pasupathy () and Nung Kwan Yip ()
Additional contact information
David Newton: Department of Statistics, Purdue University, West Lafayette, Indiana 47906
Raghu Bollapragada: Department of Mechanical Engineering, The University of Texas at Austin, Austin, Texas 78712
Raghu Pasupathy: Department of Statistics, Purdue University, West Lafayette, Indiana 47906; and Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600036, India
Nung Kwan Yip: Department of Mathematics, Purdue University, West Lafayette, Indiana 47906

Mathematics of Operations Research, 2025, vol. 50, issue 3, 2301-2332

Abstract: Stochastic Gradient (SG) is the de facto iterative technique to solve stochastic optimization (SO) problems with a smooth (nonconvex) objective f and a stochastic first-order oracle. SG’s attractiveness is due in part to its simplicity of executing a single step along the negative subsampled gradient direction to update the incumbent iterate. In this paper, we question SG’s choice of executing a single step as opposed to multiple steps between subsample updates. Our investigation leads naturally to generalizing SG into Retrospective Approximation (RA), where, during each iteration, a “deterministic solver” executes possibly multiple steps on a subsampled deterministic problem and stops when further solving is deemed unnecessary from the standpoint of statistical efficiency. RA thus formalizes what is appealing for implementation—during each iteration, “plug in” a solver—for example, L-BFGS line search or Newton-CG— as is , and solve only to the extent necessary. We develop a complete theory using relative error of the observed gradients as the principal object, demonstrating that almost sure and L 1 consistency of RA are preserved under especially weak conditions when sample sizes are increased at appropriate rates. We also characterize the iteration and oracle complexity (for linear and sublinear solvers) of RA and identify a practical termination criterion leading to optimal complexity rates. To subsume nonconvex f , we present a certain “random central limit theorem” that incorporates the effect of curvature across all first-order critical points, demonstrating that the asymptotic behavior is described by a certain mixture of normals. The message from our numerical experiments is that the ability of RA to incorporate existing second-order deterministic solvers in a strategic manner might be important from the standpoint of dispensing with hyper-parameter tuning.

Keywords: Primary:; 90C99; sample selection; machine learning; stochastic optimization; simulation optimization; sample average approximation; stochastic approximation; retrospective approximation (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0136 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:3:p:2301-2332

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().