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 stochastic extension of the cubically-regularized Newton method of Nesterov and Polyak (2006), and a 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.
Introduction
Modern machine learning often involves "over-parameterized" models where the dimension $d$ of the optimization problem is so large that standard second-order methods are computationally prohibitive. While first-order methods like Coordinate Descent (CD) are scalable, they often suffer from slow convergence. Conversely, second-order methods like Newton’s method offer fast convergence but are limited by the $O(d^2)$ storage and $O(d^3)$ inversion costs of the Hessian matrix.
To address this, researchers have turned to Subspace Descent, where updates are performed within a small, randomly sampled subspace. However, incorporating second-order curvature information into these randomized steps while maintaining global convergence guarantees has remained a challenge. This paper introduces the Stochastic Subspace Cubic Newton (SSCN) method, which bridges this gap by combining cubic regularization with randomized subspace updates.
The SSCN Algorithm
The core of the proposed approach is to perform a cubically-regularized Newton step within a low-dimensional subspace. The algorithm follows a four-step iterative process:
- Subspace Sampling: At each iteration $k$, a random "thin" matrix $\mathbf{S}$ is sampled from a distribution $\mathcal{D}$. This matrix defines the subspace for the current update.
- Cubic Model Construction: A local approximation of the objective function is built specifically within the sampled subspace, utilizing the subspace gradient and Hessian.
- Cubic Regularization: To ensure stability and global convergence, a cubic term proportional to the Lipschitz constant of the Hessian is added to the model.
- Subproblem Optimization: The update $h^k$ is found by minimizing this cubic model. Since the subspace dimension $\tau$ is typically small, this subproblem is computationally inexpensive.
SSCN is the first method to integrate cubic regularization with arbitrary random subspaces. Furthermore, it supports composite optimization problems involving a smooth loss and a separable non-smooth regularizer.
Theoretical Insights
The paper provides several key theoretical contributions:
- Interpolation Property: The global convergence rate of SSCN acts as a bridge between first and second-order methods. By adjusting the subspace size, the rate interpolates between that of Stochastic Coordinate Descent and the full-space Cubic Newton method.
- Local Convergence: Near the optimum, SSCN's convergence rate matches that of a method with access to a perfect quadratic model of the function at the minimizer. This explains its superior performance in the final stages of optimization compared to first-order methods.
- Subspace Lipschitzness: The authors demonstrate that the "smoothness" of the Hessian within a random subspace can be significantly better (smaller) than the global Lipschitz constant, allowing for larger, more effective steps.
Experimental Results
The authors evaluated SSCN on various LIBSVM datasets (e.g., w1a, a1a, mushrooms, phishing) and synthetic "Soft Maximum" functions. Key findings include:
- Efficiency: The per-iteration cost is $O(n\tau^2 + \tau^3)$, where $n$ is the number of data points and $\tau$ is the subspace dimension. For small $\tau$, this is comparable to first-order methods.
- Performance: SSCN consistently outperformed standard Coordinate Descent. Remarkably, even without explicit Nesterov-style momentum, it remained competitive with Accelerated Coordinate Descent (ACD) in many scenarios.
Conclusion
SSCN offers a scalable and theoretically grounded framework for high-dimensional optimization. While it demonstrates strong performance, future work could explore explicit acceleration techniques to further enhance convergence. Additionally, extending the theory to non-separable regularizers remains an important open problem.
Summary updated