Curvature-Exploiting Acceleration of Elastic Net Computations
arXiv:1901.08523
Abstract
This paper introduces an efficient second-order method for solving the elastic net problem. Its key innovation is a computationally efficient technique for injecting curvature information in the optimization process which admits a strong theoretical performance guarantee. In particular, we show improved run time over popular first-order methods and quantify the speed-up in terms of statistical measures of the data matrix. The improved time complexity is the result of an extensive exploitation of the problem structure and a careful combination of second-order information, variance reduction techniques, and momentum acceleration. Beside theoretical speed-up, experimental results demonstrate great practical performance benefits of curvature information, especially for ill-conditioned data sets.
arXiv comment34 pages, 2 figures
References in corpus (8)
- Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
- A Universal Catalyst for First-Order Optimization
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- Random design analysis of ridge regression
- Sub-sampled Newton Methods with Non-uniform Sampling
- Sub-Sampled Newton Methods I: Globally Convergent Algorithms
- An inexact subsampled proximal Newton-type method for large-scale machine learning
- Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations