Do Subsampled Newton Methods Work for High-Dimensional Data?

Xiang Li, Shusen Wang, Zhihua Zhang

Abstract

Subsampled Newton methods approximate Hessian matrices through subsampling techniques to alleviate the per-iteration cost. Previous results require $\Omega(d)$ samples to approximate Hessians, where $d$ is the dimension of data points, making it less practical for high-dimensional data. The situation is deteriorated when $d$ is comparably as large as the number of data points $n$, which requires to take the whole dataset into account, making subsampling not useful. This paper theoretically justifies the effectiveness of subsampled Newton methods on strongly convex empirical risk minimization with high dimensional data. Specifically, we provably require only $\tilde{\Theta}(d_{eff}^\gamma)$ samples for approximating the Hessian matrices, where $d_{eff}^\gamma$ is the $\gamma$-ridge leverage and can be much smaller than $d$ as long as $n\gamma \gg 1$. Our theories work for three types of Newton methods: subsampled Netwon, distributed Newton, and proximal Newton.

Introduction

In the landscape of large-scale machine learning, optimization is typically a choice between two extremes. First-order methods, such as Stochastic Gradient Descent (SGD), are computationally cheap per iteration but often require extensive hyperparameter tuning and many iterations to converge. Second-order methods, like Newton’s method, utilize the Hessian matrix (second derivatives) to achieve rapid convergence. However, the $O(nd^2)$ cost of computing the Hessian makes standard Newton methods impractical for modern datasets where the number of features ($d$) and observations ($n$) are both large.

Subsampled Newton (SSN) methods were developed to bridge this gap by approximating the Hessian using a random subset of data. Despite their empirical success, a significant theoretical hurdle remained: existing proofs suggested that the number of samples ($s$) needed to accurately approximate the Hessian was proportional to the full dimension $d$. In high-dimensional regimes where $d \approx n$, this requirement suggested that subsampling offered no real computational advantage. This paper provides a new theoretical framework that proves SSN methods are highly effective even when the sample size is much smaller than the dimension.

Redefining Complexity: The Effective Dimension

The core innovation of this research is the shift from the raw dimension $d$ to the effective dimension ($d_{eff}^\gamma$). By utilizing $\gamma$-ridge leverage scores, the authors demonstrate that the "information content" of the Hessian is often concentrated in a much lower-dimensional space than the feature count suggests.

In many practical scenarios—especially those involving regularization—the effective dimension is significantly smaller than $d$. The authors prove that the required sample size for Hessian approximation is actually $s = \tilde{\Theta}(d_{eff}^\gamma)$. This result provides the first theoretical justification for why subsampled Newton methods work in high-dimensional settings where $s < d$.

Algorithmic Scope

The paper provides rigorous convergence analysis for three primary algorithmic variations:

  1. Standard Subsampled Newton (SSN): Approximates the Hessian by selecting a random subset of data points at each iteration to compute the search direction.
  2. Distributed Newton (GIANT): Designed for distributed computing environments. Each machine computes a local Newton direction based on its subset of data, and these directions are averaged across the network. The authors show that averaging across $m$ machines further improves sample complexity requirements.
  3. Subsampled Proximal Newton (SSPN): An extension for non-smooth optimization problems, such as those employing $L_1$ regularization (e.g., LASSO), which are ubiquitous in high-dimensional statistics.

Key Insights and Results

  • Sample Complexity: The study establishes that $s = \Theta(d_{eff}^\gamma \log d_{eff}^\gamma)$ samples are sufficient for convergence. This effectively removes the $d$-dependence that previously hindered the theory of second-order methods.
  • Convergence Guarantees: The authors establish global convergence for quadratic losses (such as linear regression) and local fast convergence for non-quadratic, strongly convex losses (such as logistic regression).
  • The Role of Regularization: The ridge parameter $\gamma$ acts as a compressor for the dimension. Stronger regularization reduces the effective dimension, allowing for even smaller Hessian samples without sacrificing convergence speed.
  • Sampling Strategies: While uniform sampling is effective for well-distributed data, the paper highlights that ridge leverage score sampling can provide even more robust guarantees, albeit with higher initial computational costs.

Limitations and Future Directions

While this work provides a major step forward for high-dimensional optimization, it focuses exclusively on strongly convex problems. Extending these results to non-convex landscapes, such as those found in deep learning, remains an open area of research. Additionally, for non-quadratic objectives, the current theory guarantees fast convergence only when the algorithm is already "close" to the optimal solution (local convergence). Future work may focus on establishing global convergence bounds for these more complex objectives and developing more efficient ways to approximate the leverage scores used in the sampling process.

Conclusion

By proving that subsampled Newton methods depend on the effective dimension rather than the raw feature count, this paper reconciles theory with practice. It confirms that second-order methods are not only viable but highly efficient for high-dimensional data analysis, providing a robust alternative to first-order methods for large-scale empirical risk minimization.

Summary updated

Abstract

Subsampled Newton methods approximate Hessian matrices through subsampling techniques to alleviate the per-iteration cost. Previous results require Ω (d) samples to approximate Hessians, where d is the dimension of data points, making it less practical for high-dimensional data. The situation is deteriorated when d is comparably as large as the number of data points n, which requires to take the whole dataset into account, making subsampling not useful. This paper theoretically justifies the effectiveness of subsampled Newton methods on strongly convex empirical risk minimization with high dimensional data. Specifically, we provably require only Θ˜(deffγ) samples for approximating the Hessian matrices, where deffγ is the γ-ridge leverage and can be much smaller than d as long as nγ ≫ 1. Our theories work for three types of Newton methods: subsampled Netwon, distributed Newton, and proximal Newton.
BibTeX
@inproceedings{li2020do,
  author = {Xiang Li and Shusen Wang and Zhihua Zhang},
  title = {{Do Subsampled Newton Methods Work for High-Dimensional Data?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=aIO3zDpvbiK},
}
Figure