Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

Abstract

We develop a family of accelerated stochastic algorithms that minimize sums of convex functions. Our algorithms improve upon the fastest running time for empirical risk minimization (ERM), and in particular linear least-squares regression, across a wide range of problem settings. To achieve this, we establish a framework based on the classical proximal point algorithm. Namely, we provide several algorithms that reduce the minimization of a strongly convex function to approximate minimizations of regularizations of the function. Using these results, we accelerate recent fast stochastic algorithms in a black-box fashion. Empirically, we demonstrate that the resulting algorithms exhibit notions of stability that are advantageous in practice. Both in theory and in practice, the provided algorithms reap the computational benefits of adding a large strongly convex regularization term, without incurring a corresponding bias to the original problem.

References in corpus (1)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Cited by in corpus (30)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• A Universal Catalyst for First-Order Optimization
• Accelerated Methods for Non-Convex Optimization
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• The proximal point method revisited
• Stochastic, Distributed and Federated Optimization for Machine Learning
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• Accelerating Gradient Boosting Machine
• Accelerating Greedy Coordinate Descent Methods
• Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Leverage Score Sampling for Faster Accelerated Regression and ERM
• Noisy Accelerated Power Method for Eigenproblems with Applications
• Katalyst: Boosting Convex Katayusha for Non-Convex Problems with a Large Condition Number
• Sharper Bounds for Regularized Data Fitting
• Solving Ridge Regression using Sketched Preconditioned SVRG
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
• Accelerated Variance Reduced Block Coordinate Descent
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• An homotopy method for ${\ell }_p$ regression provably beyond self-concordance and in input-sparsity time
• Optimal Sketching Bounds for Exp-concave Stochastic Minimization
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates