Sub-sampled Newton methods
成果类型：
Article
署名作者：
Roosta-Khorasani, Farbod; Mahoney, Michael W.
署名单位：
University of Queensland; University of California System; University of California Berkeley; University of California System; University of California Berkeley
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-018-1346-5
发表日期：
2019
页码：
293-326
关键词：
摘要：
For large-scale finite-sum minimization problems, we study non-asymptotic and high-probability global as well as local convergence properties of variants of Newton's method where the Hessian and/or gradients are randomly sub-sampled. For Hessian sub-sampling, using random matrix concentration inequalities, one can sub-sample in a way that second-order information, i.e., curvature, is suitably preserved. For gradient sub-sampling, approximate matrix multiplication results from randomized numerical linear algebra provide a way to construct the sub-sampled gradient which contains as much of the first-order information as possible. While sample sizes all depend on problem specific constants, e.g., condition number, we demonstrate that local convergence rates are problem-independent.