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

arXiv: https://arxiv.org/abs/1708.08552 · HTML: https://mlsanity.com/paper/1708.08552/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2017.

## Built on by (most cited first, 1 of 1)

- [Non-PSD Matrix Sketching with Applications to Regression and Optimization](https://mlsanity.com/paper/2106.08544/) (2021)

## Abstract (arXiv)

We propose a fast proximal Newton-type algorithm for minimizing regularized finite sums that returns an ε-suboptimal point in tildeO(d(n + √kappa d)log(frac1ε)) 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 tildeO(d(n + √kappa n)log(frac1ε)) 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 ℓ1-regularized logistic regression on real datasets.