An inexact subsampled proximal Newton-type method for large-scale machine learning
This work addresses efficiency challenges in large-scale ML optimization for problems with non-smooth regularizers, offering a faster alternative to existing stochastic first-order methods, though it is incremental as it builds on recent developments in stochastic methods.
The paper tackles the problem of minimizing regularized finite sums in large-scale machine learning by proposing a fast proximal Newton-type algorithm that achieves an ε-suboptimal point in fewer FLOPS than state-of-the-art methods when n > d, with experimental results showing it outperforms previous algorithms for ℓ1-regularized logistic regression on real datasets.
We propose a fast proximal Newton-type algorithm for minimizing regularized finite sums that returns an $ε$-suboptimal point in $\tilde{\mathcal{O}}(d(n + \sqrt{κd})\log(\frac{1}ε))$ FLOPS, where $n$ is number of samples, $d$ is feature dimension, and $κ$ 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{κn})\log(\frac{1}ε))$ 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.