New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization. (2nd September 2021)

• Record Type: Journal Article
• Authors: Pătraşcu, Andrei
• Is Part Of: Optimization. Volume 70:Number 9(2021)
• Page Start: 1891
• Page End: 1919
• Publication Date: 2021-09-02
• Subjects: Stochastic proximal point -- stochastic alternating projections -- quadratic growth -- linear convergence -- sublinear convergence rate; 90C25 Convex programming -- 90C15 Stochastic programming; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1761364
• Languages: English
• ISSNs: 0233-1934

Abstract

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 O 1 k 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.