Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization

Abstract

We extend the Approximate-Proximal Point (aProx) family of model-based methods for solving stochastic convex optimization problems, including stochastic subgradient, proximal point, and bundle methods, to the minibatch and accelerated setting. To do so, we propose specific model-based algorithms and an acceleration scheme for which we provide non-asymptotic convergence guarantees, which are order-optimal in all problem-dependent constants and provide linear speedup in minibatch size, while maintaining the desirable robustness traits (e.g. to stepsize) of the aProx family. Additionally, we show improved convergence rates and matching lower bounds identifying new fundamental constants for "interpolation" problems, whose importance in statistical machine learning is growing; this, for example, gives a parallelization strategy for alternating projections. We corroborate our theoretical results with empirical testing to demonstrate the gains accurate modeling, acceleration, and minibatching provide.

24 pages, 17 figures

References in corpus (7)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• Online Importance Weight Aware Updates
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm

Cited by in corpus (2)

• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum