A Tight Convergence Analysis of Inexact Stochastic Proximal Point Algorithm for Stochastic Composite Optimization Problems
Shulan Zhu, Chenglong Bao, Defeng Sun, Yancheng Yuan
Abstract
The inexact stochastic proximal point algorithm (isPPA) is popular for solving stochastic composite optimization problems with many applications in machine learning. While the convergence theory of the (inexact) PPA has been well established, the known convergence guarantees of isPPA require restrictive assumptions. In this paper, we establish the stability and almost sure convergence of isPPA under mild assumptions, where smoothness and (restrictive) strong convexity of the objective function are not required. Imposing a local Lipschitz condition on component functions and a quadratic growth condition on the objective function, we establish last-iterate iteration complexity bounds of isPPA regarding the distance to the solution set and the Karush-Kuhn-Tucker (KKT) residual. Moreover, we show that the established iteration complexity bounds are tight up to a constant by explicitly analyzing the bounds for the regularized Fréchet mean problem. We further validate the established convergence guarantees of isPPA by numerical experiments.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on1
Related papers
- High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded VarianceAbdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth et al.ICML 2023 · 68 citations
- Last Iterate Convergence of Incremental Methods as a Model of ForgettingXufeng Cai, Jelena DiakonikolasICLR 2025
- On the Almost Sure Convergence of the Stochastic Three Points AlgorithmTaha el Bakkali el Kadi, Omar SaadiICLR 2025
- Convergence Rate of the Last Iterate of Stochastic Proximal AlgorithmsKevin Kurian Thomas Vaidyan, Michael Friedlander, Ahmet AlacaogluICML 2026
- A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained OptimizationDigvijay Boob, Qi Deng, Guanghui Lan, Yilin WangNeurIPS 2020 · 12 citations
