Stochastic Subspace Cubic Newton Method

Filip Hanzely, Nikita Doikov, Yurii E. Nesterov, Peter Richtárik

Introduction

The Stochastic Subspace Cubic Newton (SSCN) method is a novel second-order optimization algorithm designed specifically for high-dimensional problems. By minimizing a cubic upper bound of the objective function within a randomly sampled subspace, SSCN bridges the gap between simple, low-cost coordinate descent and computationally expensive full-space Newton methods. The result is an algorithm that offers superior convergence rates while maintaining manageable per-iteration costs.

The High-Dimensional Optimization Challenge

In modern machine learning, minimizing convex functions in extremely high dimensions (such as in over-parameterized models) presents a significant computational hurdle.

  • First-order methods, like Coordinate Descent (CD), are highly popular because they are computationally cheap per iteration. However, they often require a massive number of iterations to converge.
  • Second-order methods, like Newton’s method, converge much faster—often superlinearly—by utilizing the Hessian matrix. Unfortunately, they are prohibitively expensive in high dimensions because computing and inverting a $d \times d$ Hessian matrix costs $O(d^3)$.

The authors seek a practical middle ground: an algorithm that leverages second-order information to accelerate convergence but restricts its operations to a small "subspace" to keep computational overhead low.

The SSCN Approach

The proposed SSCN algorithm operates through the following steps:

  1. Subspace Sampling: In each iteration, the algorithm samples a small random subspace, defined by a matrix $S$. A common practical example is selecting a random minibatch of coordinates.
  2. Cubic Upper Bound: Instead of minimizing the original function $f$ directly, SSCN constructs a subspace cubic model. This model utilizes the gradient and Hessian restricted to the sampled subspace, combined with a cubic regularization term based on the Lipschitz constant of the subspace Hessian ($M_S$).
  3. Subproblem Optimization: The algorithm finds the step $h$ that minimizes this cubic model. Because the subspace dimension ($\tau$) is much smaller than the full dimension ($d$), solving this subproblem is computationally efficient, scaling at $O(\tau^3)$.
  4. Update: The current parameter estimate is updated strictly along the directions spanned by the subspace: $x^{k+1} = x^k + Sh^k$.

A key theoretical contribution of this work is the formal definition and bounding of $M_S$. The authors demonstrate that the Hessian is often significantly "smoother" when restricted to a subspace, which allows for a tighter upper bound and larger, more effective optimization steps than standard cubic Newton methods.

Key Theoretical Insights

  • Interpolation of Rates: The authors prove that SSCN’s global convergence rate smoothly interpolates between the rate of stochastic Coordinate Descent (when the subspace is a single coordinate) and the rate of Cubic Regularized Newton (when the subspace is the full space).
  • Fast Local Convergence: Near the optimum, SSCN matches the convergence rate of Stochastic Subspace Descent applied to a quadratic function. This represents the "best case" performance for a non-accelerated method in this setting.
  • Subspace Advantage: The "subspace Lipschitz constant" $M_S$ can be up to $(d/\tau)^{3/2}$ times smaller than the global constant $M$. This tighter bound leads to substantially faster progress per iteration.
  • Handling Non-Smoothness: SSCN naturally accommodates composite problems (e.g., minimizing $f(x) + \psi(x)$) provided the non-smooth component $\psi$ is "separable" relative to the sampling distribution.

Experimental Results

The algorithm was rigorously evaluated on several standard binary classification datasets from the LibSVM library (including w1a, a1a, madelon, gisette_scale, a9a, w8a, mushrooms, and phishing), modeled using regularized logistic regression.

SSCN consistently outperformed standard first-order methods in these numerical experiments:

  • Vs. Coordinate Descent: SSCN significantly outperformed uniform CD and was generally superior or equal to CD with importance sampling across all tested datasets.
  • Vs. Accelerated Methods: Remarkably, SSCN was competitive with—and frequently faster than—accelerated coordinate descent (ACD_imp), despite SSCN itself not utilizing Nesterov-style acceleration.
Comparison of SSCN against Coordinate Descent (CD) variants across eight LibSVM datasets. SSCN (red dashed line) consistently demonstrates rapid convergence in relative suboptimality.

The authors also noted that in comparisons against Stochastic Dual Subspace Ascent (SDNA), SSCN consistently achieved better convergence as the subspace dimension $\tau$ increased.

Limitations and Future Directions

While SSCN presents a strong step forward, the authors identify several areas for future research:

  • Acceleration: The current iteration of SSCN is a "plain" method. Incorporating Nesterov’s momentum to create an "Accelerated SSCN" is a primary goal, potentially yielding optimal global and local rates simultaneously.
  • Separability Constraint: The requirement that the non-smooth component $\psi$ be separable is a limitation. Techniques like "control variates" might help relax this constraint in future versions.
  • Subproblem Complexity: Although $O(\tau^3)$ is vastly superior to $O(d^3)$, it still places a practical upper limit on the size of the minibatch/subspace $\tau$ that can be efficiently utilized.
  • Importance Sampling: While the underlying theory supports non-uniform sampling, designing an efficient, practical importance sampling strategy for the local convergence phase remains an open challenge.

Summary updated

Abstract

In this paper, we propose a new randomized second-order optimization algorithm—Stochastic Subspace Cubic Newton (SSCN)—for minimizing a high dimensional convex function $f$. Our method can be seen both as a \emph{stochastic} extension of the cubically-regularized Newton method of Nesterov and Polyak (2006), and a \emph{second-order} enhancement of stochastic subspace descent of Kozak et al. (2019). We prove that as we vary the minibatch size, the global convergence rate of SSCN interpolates between the rate of stochastic coordinate descent (CD) and the rate of cubic regularized Newton, thus giving new insights into the connection between first and second-order methods. Remarkably, the local convergence rate of SSCN matches the rate of stochastic subspace descent applied to the problem of minimizing the quadratic function $\frac12 (x-x^*)^\top \nabla^2f(x^*)(x-x^*)$, where $x^*$ is the minimizer of $f$, and hence depends on the properties of $f$ at the optimum only. Our numerical experiments show that SSCN outperforms non-accelerated first-order CD algorithms while being competitive to their accelerated variants.
BibTeX
@inproceedings{hanzely2020stochastic,
  author = {Filip Hanzely and Nikita Doikov and Yurii E. Nesterov and Peter Richtárik},
  title = {{Stochastic Subspace Cubic Newton Method}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=mojleA8yTE},
}
Figure