Abstract
We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a self-concordant, composite, strongly convex objective function. Our method is based on performing an approximate Newton step using a random projection of the Hessian. Our first contribution is to show that, at each iteration, the embedding dimension (or sketch size) can be as small as the effective dimension of the Hessian matrix. Leveraging this novel fundamental result, we design an algorithm with a sketch size proportional to the effective dimension and which exhibits a quadratic rate of convergence. This result dramatically improves on the classical linear-quadratic convergence rates of state-of-the-art sub-sampled Newton methods. However, in most practical cases, the effective dimension is not known beforehand, and this raises the question of how to pick a sketch size as small as the effective dimension while preserving a quadratic convergence rate. Our second and main contribution is thus to propose an adaptive sketch size algorithm with quadratic convergence rate and which does not require prior knowledge or estimation of the effective dimension: at each iteration, it starts with a small sketch size, and increases it until quadratic progress is achieved. Importantly, we show that the embedding dimension remains proportional to the effective dimension throughout the entire path and that our method achieves state-of-the-art computational complexity for solving convex optimization programs with a strongly convex component.
Introduction
In large-scale machine learning, practitioners often face a trade-off between first-order and second-order optimization methods. First-order methods, such as Gradient Descent (GD) and its accelerated variants like Katyusha, are computationally inexpensive per iteration but require many iterations to converge. Second-order methods, like Newton’s Method, offer rapid quadratic convergence but are computationally prohibitive for high-dimensional data, scaling at $O(nd^2)$ due to the necessity of calculating and inverting a massive Hessian matrix.
Previous attempts to mitigate this cost used "Newton Sketching"—applying random projections to compress the Hessian. However, these methods typically required a sketch size proportional to the full dimension ($d$), which remains expensive when $d$ is large. This paper addresses two critical questions: can we make the sketch size proportional to the effective dimension ($d_\mu$), and can we determine this optimal size automatically during optimization?
Methods
The authors propose the Adaptive Newton Sketch (NS-ada), which dynamically adjusts the degree of random compression based on the problem's effective dimension. The algorithm utilizes two main strategies:
- Effective Dimension Sketching: The authors prove that the complexity of second-order optimization is governed by the effective dimensionality of the Hessian ($d_\mu$), which is often much smaller than the ambient dimension $d$ in real-world datasets. This explains why sketching is highly effective on redundant or correlated data.
- Adaptive Doubling Trick: Since $d_\mu$ is rarely known a priori, the algorithm starts with a minimal sketch size. At each iteration, it checks if the approximate Newton step provides sufficient "progress" (measured by the Newton decrement). If progress is too slow, it doubles the sketch size and retries. This allows the algorithm to "discover" the effective dimension on the fly.
The theoretical framework relies on self-concordant functions (e.g., logistic regression and log-barrier functions), enabling robust convergence guarantees without manual step-size tuning.
Key Results and Complexity
The Adaptive Newton Sketch achieves the per-iteration speed of first-order methods combined with the rapid quadratic convergence of Newton's method. As summarized in the table below, NS-ada achieves state-of-the-art computational complexity, scaling linearly with the data size $nd$ while maintaining a sketch size proportional to the effective dimension.
Empirical tests on standard large-scale datasets (e.g., MNIST, RCV1, epsilon, and realsim) showed that NS-ada reached high-precision solutions (relative error $< 10^{-6}$) significantly faster than state-of-the-art first-order methods like Katyusha or SVRG. Furthermore, because its memory requirements scale with $d_\mu$ rather than $d$, the algorithm is significantly more memory-efficient than standard Newton methods.
Conclusion
The Adaptive Newton Sketch provides a practical solution for high-dimensional convex optimization by adaptively leveraging the effective dimensionality of the problem. By achieving linear-time complexity per iteration alongside quadratic convergence, it bridges the gap between first- and second-order methods. Future research directions include extending these adaptive sketching techniques to non-convex optimization problems, such as those encountered in deep learning, and further optimizing the accessibility of the Hessian square root for complex objective functions.
Summary updated