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 (10)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Accelerated Methods for Non-Convex Optimization
• The proximal point method revisited
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Leverage Score Sampling for Faster Accelerated Regression and ERM
• Noisy Accelerated Power Method for Eigenproblems with Applications
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Accelerated Variance Reduced Block Coordinate Descent