HONES: A Fast and Tuning-free Homotopy Method For Online Newton Step

[edit]

Yuting Ye, Lihua Lei, Cheng Ju ;
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:2008-2017, 2018.

Abstract

In this article, we develop and analyze a homotopy continuation method, referred to as HONES , for solving the sequential generalized projections in Online Newton Step (Hazan et al., 2006b), as well as the generalized problem known as sequential standard quadratic programming. HONES is fast, tuning-free, error-free (up to machine error) and adaptive to the solution sparsity. This is confirmed by both careful theoretical analysis and extensive experiments on both synthetic and real data.

Related Material