Sub-sampled Newton Methods with Non-uniform Sampling

MaRDI QIDQ6275187arXivFDO

Authors Peng Xu, Jiyan Yang, Farbod Roosta-Khorasani, Christopher Ré, Michael W. Mahoney

Publication date 2 July 2016

Published in arXiv

arXiv classification

math.OCstat.ML

Abstract: We consider the problem of finding the minimizer of a convex function $F:mathbb{R}^{d}ightarrowmathbbR$ of the form $F(w):=su{m}_{i=1}^n{f}_i(w)+R(w)$ where a low-rank factorization of $abl{a}^2{f}_i(w)$ is readily available. We consider the regime where $nggd$. As second-order methods prove to be effective in finding the minimizer to a high-precision, in this work, we propose randomized Newton-type algorithms that exploit extit{non-uniform} sub-sampling of ${abl{a}^2{f}_i(w)}_{i=1}^n$, as well as inexact updates, as means to reduce the computational complexity. Two non-uniform sampling distributions based on {it block norm squares} and {it block partial leverage scores} are considered in order to capture important terms among ${abl{a}^2{f}_i(w)}_{i=1}^n$. We show that at each iteration non-uniformly sampling at most $mathcalO(dlogd)$ terms from ${abl{a}^2{f}_i(w)}_{i=1}^n$ is sufficient to achieve a linear-quadratic convergence rate in $w$ when a suitable initial point is provided. In addition, we show that our algorithms achieve a lower computational complexity and exhibit more robustness and better dependence on problem specific quantities, such as the condition number, compared to similar existing methods, especially the ones based on uniform sampling. Finally, we empirically demonstrate that our methods are at least twice as fast as Newton's methods with ridge logistic regression on several real datasets.

Cited in

(1)

• Computing Lewis Weights to High Precision by Fixed-Point Iteration

This page was built for publication: Sub-sampled Newton Methods with Non-uniform Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6275187)