We propose a randomized second-order method for optimization known as the
Newton Sketch: it is based on performing an approximate Newton step using a
randomly projected or sub-sampled Hessian. For self-concordant functions, we
prove that the algorithm has super-linear convergence with exponentially high
probability, with convergence and complexity guarantees that are independent of
condition numbers and related problem-dependent quantities. Given a suitable
initialization, similar guarantees also hold for strongly convex and smooth
objectives without self-concordance. When implemented using randomized
projections based on a sub-sampled Hadamard basis, the algorithm typically has
substantially lower complexity than Newton's method. We also describe
extensions of our methods to programs involving convex constraints that are
equipped with self-concordant barriers. We discuss and illustrate applications
to linear programs, quadratic programs with convex constraints, logistic
regression and other generalized linear models, as well as semidefinite
programs.

该研究提出了一种随机化的二阶优化方法 ——Newton Sketch，使用随机投影或子采样 Hessian 实现近似牛顿步。对于自共轭函数，该算法证明具有超线性收敛和指数高概率，与条件数和相关问题独立的收敛和复杂度保证。对于适当的初始化，即使在没有自共轭的情况下，也可以保证类似的保证对于强凸和光滑的目标。我们还描述了将我们的方法扩展到具有自共轭屏障的凸约束程序。我们讨论和说明了其应用于线性程序，带有凸约束的二次程序，逻辑回归和其他广义线性模型以及半定规划的扩展问题。