Lune

ICLR2025Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. Minibatch Stochastic Approximate Proximal Point MethodsHilal Asi, Karan N. Chadha, Gary Cheng, John C. DuchiNeurIPS 2020 · 22 citations

Related papers

  1. 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
  2. Last Iterate Convergence of Incremental Methods as a Model of ForgettingXufeng Cai, Jelena DiakonikolasICLR 2025
  3. On the Almost Sure Convergence of the Stochastic Three Points AlgorithmTaha el Bakkali el Kadi, Omar SaadiICLR 2025
  4. Convergence Rate of the Last Iterate of Stochastic Proximal AlgorithmsKevin Kurian Thomas Vaidyan, Michael Friedlander, Ahmet AlacaogluICML 2026
  5. A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained OptimizationDigvijay Boob, Qi Deng, Guanghui Lan, Yilin WangNeurIPS 2020 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines