Convergence of projected stochastic approximation algorithm

2025/01/14 by Michał Borowski, Borowski, Michał, Błażej Miasojedow +1 · 1 citation
Computer Science · #FOS: Mathematics #Neural Networks and Applications #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2501.08256

openalex publication_date 2025/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the Robbins-Monro stochastic approximation algorithm with projections on a hyperrectangle and prove its convergence. This work fills a gap in the convergence proof of the classic book by Kushner and Yin. Using the ODE method, we show that the algorithm converges to stationary points of a related projected ODE. Our results provide a better theoretical foundation for stochastic optimization techniques, including stochastic gradient descent and its proximal version. These results extend the algorithm's applicability and relax some assumptions of previous research.

Cited by

• Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential

Related

• Asymptotic Behaviors and Phase Transitions in Projected Stochastic Approximation: A Jump Diffusion Approach
• Riemannian stochastic approximation algorithms
• Exponential Concentration in Stochastic Approximation
• Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes
• Delayed supermartingale convergence lemmas for stochastic approximation with Nesterov momentum