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

By Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford. 2015

157 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, background): “Related work in this context includes algorithms specifically designed to achieve an accelerated rate of convergence in the stochastic setting [1, 23, 46].”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “Other related work includes algorithms specifically designed to achieve an accelerated rate of convergence in the stochastic setting [1, 19, 10].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “A general method, referred to as Universal Catalyst [53, 37], eﬀectively enables conversion of a number of the algorithms mentioned in the previous sections to their ‘ac-celerated’ variants.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “This open question was partially solved recently by the APPA [16] and Catalyst [25] reductions, both based on an outer-inner loop structure rst proposed by Shalev-Shwartz and Zhang [40].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “A general method, referred to as Universal Catalyst [99, 63], effectively enables conversion of a number of the algorithms mentioned in the previous sections to their ‘accelerated’ variants.”
Accelerating Stochastic Gradient Descent (2017, methodology): “4 Conclusion This paper introduces an accelerated stochastic gradient method, which presents the first improvement in achieving minimax rates faster than averaged SGD (Robbins and Monro, 1951; Ruppert, 1988; Polyak and Juditsky, 1992; Jain et al., 2016)/Streaming SVRG (Frostig et al., 2015b) for the”
Variance Reduction for Matrix Games (2019, methodology): “This gap is to be expected, as it appears in essentially all stochastic methods for linear regression [31, 17, 27, 12, 19, 28, 26, 1].”
Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization (2014, background): “, 2015b; Lan and Zhou, 2015; Allen-Zhu, 2017) or through the proximal-point algorithm (Shalev-Shwartz and Zhang, 2015; Frostig et al., 2015; Lin et al., 2015a).”
Accelerated Methods for Non-Convex Optimization (2016, background): “The estimate sequence ideas of Nesterov [23] and proximal point proofs [20, 31, 9] show how to view accelerated gradient descent as a trade-off between building function lower”
Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives (2015, unknown): “One can apply Catalyst (Lin et al., 2015; Frostig et al., 2015) to further improve its running time when σ is very small.”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, methodology): “Applying the acceleration techniques developed by Frostig et al. (2015) and Lin et al. (2015) to INEXACTDANE, Reddi et al. (2016) further proposed an Accelerated Inexact DanE (AIDE) algorithm that matches the round complexity of DISCO up to a logarithmic factor. Shamir (2016) consider a without-repl”
Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters (2016, methodology): “Recently, variancereduction methods were introduced to improve the running time of SGD [6, 7, 13, 18, 20–22, 24], and accelerated gradient methods were introduced to further improve the running time when the regularization parameter is small [9, 16, 17, 23, 27].”
Distributed Stochastic Variance Reduced Gradient Methods (2015, methodology): “In this section, we use the idea of [13] and [12] to further speed up the DSVRG.”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “s -strongly nonconvex. It is divided into stages. In each stage t, it considers a modied function ft (x ) def= f (x ) + kx x t k2 , and then apply the accelerated SVRG method (e.g. APPA/Catalyst [20, 32]) to minimize ft (x ). Then, it moves to x t+1 which is a suciently accurate minimizer of ft (x”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, methodology): “…2012; Shalev-Shwartz and Zhang, 2012; Johnson and Zhang, 2013; Defazio et al., 2014) and their accelerated variants (Shalev-Shwartz and Zhang, 2013a; Frostig et al., 2015a; Lin et al., 2015; Defazio, 2016; Allen-Zhu, 2016) which offer near linear running time in the number of samples and condition…”
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization (2016, methodology): “…techniques of (Nesterov, 2004) on top of approximate proximal point steps, the main differences compared with (Shalev-Shwartz and Zhang, 2014) and (Frostig et al., 2015) are here we warm start with two groups dual variables (α and β) where (Shalev-Shwartz and Zhang, 2014) warm start only with α…”
Optimal Black-Box Reductions Between Optimization Objectives (2016, background): “Catalyst/APPA [11, 19] turn non-accelerated methods into accelerated ones, which is different from the purpose of this paper.”