Stochastic Subspace Cubic Newton Method
(2020) Proceedings of Machine Learning Research (PMLR) — Vol. 119, p. 4027-4038 (2020)
Files
CORE_RP_3310.pdf
Open Access - Adobe PDF
- 1.14 MB
Details
- Authors
- 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 where x∗ is the minimizer of f, and hence de- pends on the properties of f at the optimum only. Our numerical experiments show that SSCN outperforms non-accelerated first-order CD algo- rithms while being competitive to their acceler- ated variants.
- Affiliations
Citations
Hanzely, F., Doikov, N., Richtarik, P., & Nesterov, Y. (2020). Stochastic Subspace Cubic Newton Method. Proceedings of Machine Learning Research (PMLR), 119, 4027-4038. https://hdl.handle.net/2078.5/233924 (Original work published 2020)