Name
Abstract | ||
|---|---|---|
We consider the problem of finding the minimizer of a convex function F : R-d -> R of the form F (w) := Sigma(n)(i=1) f(i) (w) + R (w) where a low-rank factorization of del(2) f(i) (w) is readily available. We consider the regime where n >> d. We propose randomized Newton-type algorithms that exploit non-uniform sub-sampling of {del(2) f(i) (w)}(i=1)(n), as well as inexact updates, as means to reduce the computational complexity, and are applicable to a wide range of problems in machine learning. Two non-uniform sampling distributions based on block norm squares and block partial leverage scores are considered. Under certain assumptions, we show that our algorithms inherit a linear-quadratic convergence rate in w and achieve a lower computational complexity compared to similar existing methods. In addition, we show that our algorithms exhibit more robustness and better dependence on problem specific quantities, such as the condition number. We empirically demonstrate that our methods are at least twice as fast as Newton's methods on several real datasets. |
Year | Venue | Field |
|---|---|---|
2016 | ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016) | Sampling distribution,Discrete mathematics,Combinatorics,Mathematical optimization,Condition number,Convex function,Rate of convergence,Sampling (statistics),Factorization,Mathematics,Nonuniform sampling,Computational complexity theory |
DocType | Volume | ISSN |
Conference | 29 | 1049-5258 |
Citations | PageRank | References |
1 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peng Xu | 1 | 20 | 3.44 |
| Jiyan Yang | 2 | 68 | 7.93 |
| Farbod Roosta-Khorasani | 3 | 102 | 9.25 |
| Ré Christopher | 4 | 3422 | 192.34 |
| Michael W. Mahoney | 5 | 3297 | 218.10 |