Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization

Abstract

A very popular approach for solving stochastic optimization problems is the stochastic gradient descent method (SGD). Although the SGD iteration is computationally cheap and the practical performance of this method may be satisfactory under certain circumstances, there is recent evidence of its convergence difficulties and instability for unappropriate parameters choice. To avoid these drawbacks naturally introduced by the SGD scheme, the stochastic proximal point algorithms have been recently considered in the literature. We introduce a new variant of the stochastic proximal point method (SPP) for solving stochastic convex optimization problems subject to (in)finite intersection of constraints satisfying a linear regularity type condition. For the newly introduced SPP scheme we prove new nonasymptotic convergence results. In particular, for convex and Lipschitz continuous objective functions, we prove nonasymptotic estimates for the rate of convergence in terms of the expected value function gap of order $\mathcal{O}(1/k^{1/2})$, where $k$ is the iteration counter. We also derive better nonasymptotic bounds for the rate of convergence in terms of expected quadratic distance from the iterates to the optimal solution for smooth strongly convex objective functions, which in the best case is of order $\mathcal{O}(1/k)$. Since these convergence rates can be attained by our SPP algorithm only under some natural restrictions on the stepsize, we also introduce a restarting variant of SPP method that overcomes these difficulties and derive the corresponding nonasymptotic convergence rates. Numerical evidence supports the effectiveness of our methods in real-world problems.

References in corpus (5)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Sparse and stable Markowitz portfolios
• Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent
• Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization

Cited by in corpus (5)

• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• The importance of better models in stochastic optimization
• Random minibatch subgradient algorithms for convex problems with functional constraints
• Mini-batch stochastic subgradient for functional constrained optimization
• Robust Implicit Backpropagation