Introduction
In the realm of convex optimization, practitioners frequently face a stark trade-off between computational cost per iteration and overall convergence speed. First-order methods, such as Gradient Descent, are computationally cheap per step but can take an exceedingly long time to converge, particularly if the optimization landscape is "ill-conditioned" (highly stretched). Conversely, second-order methods, like Newton's Method, offer incredibly fast—often quadratic—convergence. However, they require calculating and inverting the Hessian matrix. For a dataset with $n$ points and $d$ features, this incurs a prohibitive $O(nd^2)$ cost, making it unfeasible for modern large-scale machine learning problems.
Previous attempts to bridge this gap have utilized "sketching"—randomly projecting the Hessian into a lower-dimensional space to accelerate computations. Yet, these methods typically require users to guess the optimal "sketch size" beforehand or settle for slower, linear convergence. This paper introduces the Adaptive Newton Sketch (NS-ada), a randomized optimization algorithm that achieves the "gold standard" quadratic convergence of Newton's method while only requiring linear time relative to the data size. By adaptively adjusting the sketch size to match the problem's underlying complexity, the algorithm eliminates the need for manual tuning or prior knowledge of the Hessian's structure.
Methodology: The Adaptive Newton Sketch
The authors build upon the existing Newton Sketch framework. Instead of computing the full Hessian $H(x)$, the algorithm utilizes an approximation $H_S(x)$ generated by multiplying the Hessian's square root by a random sketching matrix $S$.
The core innovations of this approach include:
- Effective Dimension ($d_\mu$): The researchers demonstrate that the sketch size does not need to scale with the full ambient dimension $d$. Instead, it only needs to scale with the "effective dimension" of the Hessian, which is often significantly smaller in real-world datasets.
- Adaptive Sketching (NS-ada): Because the effective dimension $d_\mu$ is usually unknown in practice, the authors propose an adaptive algorithm. It initializes with a very small sketch size and evaluates whether the resulting update makes "sufficient progress" (measured via the Newton decrement). If progress is insufficient, the algorithm doubles the sketch size and retries.
- Tunable Convergence: The method introduces a parameter $\tau$ that allows users to seamlessly tune their desired convergence rate, ranging from linear to quadratic.
To execute the random projections, the study evaluates the Subsampled Randomized Hadamard Transform (SRHT) for computational speed and the Sparse Johnson-Lindenstrauss Transform (SJLT) for enhanced memory efficiency.
Key Insights and Results
The algorithm was rigorously tested on standard machine learning benchmarks for regularized logistic regression, including image datasets (MNIST), text processing datasets (realsim), and notoriously difficult high-dimensional Kernel Matrices (a8a, w7a) where $n=d$.
Theoretical Guarantees and Complexity
The paper provides a comprehensive theoretical comparison of time complexities against standard baselines.
Several key insights emerge from this theoretical and empirical analysis:
- Effective Dimension is the True Bottleneck: The most surprising finding is that quadratic convergence can be maintained even when the sketch size is much smaller than the ambient dimension $d$, provided it adequately covers the "effective" parts of the Hessian.
- Condition Number Independence: Unlike Gradient Descent or accelerated methods like Katyusha, the Adaptive Newton Sketch's complexity does not depend on the condition number $\kappa$. This makes the algorithm exceptionally robust for "hard," ill-conditioned optimization problems.
- The "Doubling Trick" is Efficient: The computational cost of occasionally failing an update and doubling the sketch size is negligible compared to the massive savings gained from operating at a near-optimal sketch size throughout the optimization path.
- Linear Scaling: For large $n$, the total time complexity scales as $O(nd \cdot \text{polylog}(d_\mu, 1/\delta))$, effectively rendering it a linear-time second-order method.
Empirically, on datasets like realsim, the adaptive method reached high precision significantly faster in terms of CPU time than both standard Newton's method and accelerated gradient methods.
Limitations and Future Directions
While highly effective, the Adaptive Newton Sketch has a few limitations. If the effective dimension $d_\mu$ is actually very close to the full dimension $d$, the adaptive "check-and-double" logic introduces a slight computational overhead compared to using a fixed-size sketch from the start. Additionally, the theoretical guarantees currently rely on the objective function being "self-concordant," a technical property common in many, but not all, convex problems.
Future work may explore extending this adaptive sketching logic to non-convex optimization landscapes or distributed optimization settings, where communication costs—rather than pure computation—serve as the primary bottleneck.
Summary updated