An inexact subsampled proximal Newton-type method for large-scale machine learning

Abstract

We propose a fast proximal Newton-type algorithm for minimizing regularized finite sums that returns an $\epsilon$-suboptimal point in $\tilde{\mathcal{O}}(d(n+\sqrt{\kappa d})\log (\frac{1}{\epsilon }))$ FLOPS, where $n$ is number of samples, $d$ is feature dimension, and $\kappa$ is the condition number. As long as $n>d$, the proposed method is more efficient than state-of-the-art accelerated stochastic first-order methods for non-smooth regularizers which requires $\tilde{\mathcal{O}}(d(n+\sqrt{\kappa n})\log (\frac{1}{\epsilon }))$ FLOPS. The key idea is to form the subsampled Newton subproblem in a way that preserves the finite sum structure of the objective, thereby allowing us to leverage recent developments in stochastic first-order methods to solve the subproblem. Experimental results verify that the proposed algorithm outperforms previous algorithms for ${\ell }_1$-regularized logistic regression on real datasets.

References in corpus (3)

• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Revisiting Sub-sampled Newton Methods

Cited by in corpus (5)

• An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
• Do Subsampled Newton Methods Work for High-Dimensional Data?
• Curvature-Exploiting Acceleration of Elastic Net Computations
• Proximal Newton Methods for X-Ray Imaging with Non-Smooth Regularization
• Non-PSD Matrix Sketching with Applications to Regression and Optimization