Sketch-and-Project Meets Newton Method: Global O(1/k2) Convergence with Low-Rank Updates

Slavomír Hanzely

Abstract

Second-order optimization methods offer superior convergence properties but are often computationally prohibitive in high-dimensional settings due to the $O(d^3)$ cost of Hessian inversion. This paper introduces Sketchy Global Newton (SGN), a novel "sketch-and-project" method that achieves a fast $O(k^{-2})$ global convergence rate using low-rank updates. By maintaining geometric consistency through local Hessian norms, SGN bridges the gap between the low per-iteration cost of sketching ($O(d\tau^2)$) and the robust global convergence of regularized Newton methods.

Introduction

Modern machine learning frequently involves high-dimensional optimization problems where the number of parameters $d$ can reach millions. While first-order methods like Gradient Descent are scalable, they are sensitive to problem scaling and often require many iterations to converge. Second-order methods, particularly the Newton method, are prized for their affine invariance—their performance is independent of variable rescaling—and their rapid convergence near the solution.

However, the "curse of dimensionality" presents a significant barrier: standard Newton methods require computing and inverting a $d \times d$ Hessian matrix at every step, a task with $O(d^3)$ complexity. To mitigate this, "sketching" techniques project the problem into a lower-dimensional subspace of rank $\tau \ll d$, reducing the cost to $O(d\tau^2)$. Despite this efficiency, previous sketchy methods like Randomized Subspace Newton (RSN) or Stochastic Subspace Cubic Newton (SSCN) typically achieved only a slower $O(k^{-1})$ global convergence rate. SGN addresses this limitation, providing the first low-rank method to reach the $O(k^{-2})$ "gold standard" global rate.

Table 1: Classification of second-order methods by update direction and oracle, highlighting SGN's unique position in achieving $O(k^{-2})$ convergence with low-rank updates.

The Sketchy Global Newton (SGN) Framework

The SGN algorithm unifies three distinct perspectives on optimization:

  1. Sketch-and-Project: The Newton update is projected onto a random subspace.
  2. Subspace Regularized Newton: A cubically regularized Newton subproblem is solved, restricted to a sketched subspace.
  3. Damped Subspace Newton: A Newton step is performed in a subspace using an adaptive damping (step size) factor $\alpha_k$.

The core innovation of SGN lies in its geometric consistency. Previous subspace methods often introduced errors by mixing standard $l_2$ norms with Hessian-based updates, leading to a "norm mismatch" that degraded convergence rates. SGN avoids this by using local Hessian norms to define both the sketching projection and the step-size schedule. This ensures the algorithm remains within the "natural" geometry of the objective function, preserving affine invariance and enabling faster global convergence.

Key Insights and Theoretical Breakthroughs

A major theoretical contribution is the proof that SGN maintains an $O(k^{-2})$ global rate even with the most aggressive sketching—a rank-1 subspace ($\tau=1$). In such cases, the cost per iteration can be as low as $O(1)$ with optimized implementations. Furthermore, the paper demonstrates a three-way equivalence between regularizing, damping, and sketching when performed correctly.

SGN also achieves a local linear convergence rate that is independent of the problem's condition number. This robustness makes it particularly effective for poorly scaled, "difficult" problems where first-order methods typically struggle.

Empirical Evaluation

The authors validated SGN using several benchmark datasets from the LIBSVM library, including mushrooms, phishing, w1a, a1a, a9a, gisette_scale, duke, and madelon. These datasets represent a wide range of dimensionalities and sparsity patterns.

Table 2: Comparison of SGN with existing first- and second-order optimization algorithms across key performance metrics.

In these experiments, SGN demonstrated performance comparable to or better than the previous state-of-the-art (SSCN) and significantly outperformed first-order methods like Coordinate Descent (CD) and Accelerated Coordinate Descent (ACD) in terms of the number of data passes required to reach high-precision solutions.

Limitations and Future Directions

While SGN represents a significant step forward, some challenges remain. The algorithm requires an estimate of the "semi-strong self-concordance" constant ($L_{alg}$), which influences the step size $\alpha_k$. Although the method shows robustness to this parameter, precise estimation is beneficial. Additionally, the current theory relies on specific "unbiased" sketch matrix distributions relative to the local Hessian norm. Developing more practical sampling methods for these distributions and further reducing implementation overhead are key areas for future research.

Summary updated

Abstract

In this paper, we propose the first sketch-and-project Newton method with the fast $O(1/k^2$) global convergence rate for self-concordant functions. Our method, SGN, can be viewed in three ways: i) as a sketch-and-project algorithm projecting updates of the Newton method, ii) as a cubically regularized Newton method in the sketched subspaces, and iii) as a damped Newton method in the sketched subspaces. SGN inherits the best of all three worlds: the cheap iteration costs of the sketch-and-project methods, the state-of-the-art $O(1/k^2)$ global convergence rate of the full-rank Newton-like methods, and the algorithm simplicity of the damped Newton methods. Finally, we demonstrate its comparable empirical performance to the baseline algorithms.
BibTeX
@inproceedings{hanzely2025sketch,
  author = {Slavomír Hanzely},
  title = {{Sketch-and-Project Meets Newton Method: Global O(1/k2) Convergence with Low-Rank Updates}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
}
Figure