New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization

Abstract

Large sectors of the recent optimization literature focused in the last decade on the development of optimal stochastic first-order schemes for constrained convex models under progressively relaxed assumptions. Stochastic proximal point is an iterative scheme born from the adaptation of proximal point algorithm to noisy stochastic optimization, with a resulting iteration related to stochastic alternating projections. Inspired by the scalability of alternating projection methods, we start from the (linear) regularity assumption, typically used in convex feasiblity problems to guarantee the linear convergence of stochastic alternating projection methods, and analyze a general weak linear regularity condition which facilitates convergence rate boosts in stochastic proximal point schemes. Our applications include many non-strongly convex functions classes often used in machine learning and statistics. Moreover, under weak linear regularity assumption we guarantee $\mathcal{O}\left(\frac{1}{k}\right)$ convergence rate for SPP, in terms of the distance to the optimal set, using only projections onto a simple component set. Linear convergence is obtained for interpolation setting, when the optimal set of the expected cost is included into the optimal sets of each functional component.

Keywords:

• Stochastic proximal point
• stochastic alternating projections
• quadratic growth
• linear convergence
• sublinear convergence rate

2010 Mathematics Subject Classifications:

• 90C25 Convex programming
• 90C15 Stochastic programming

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Funding

This work was supported by BRD Groupe Societe Generale through Data Science Research Fellowships of 2019.