Cubic regularized subspace Newton for non-convex optimization
<|reference_start|>Cubic regularized subspace Newton for non-convex optimization: This paper addresses the optimization problem of minimizing non-convex continuous functions, which is relevant in the context of high-dimensional machine learning applications characterized by over-parametrization. We analyze a randomized coordinate second-order method named SSCN which can be interpreted as applying cubic regularization in random subspaces. This approach effectively reduces the computational complexity associated with utilizing second-order information, rendering it applicable in higher-dimensional scenarios. Theoretically, we establish convergence guarantees for non-convex functions, with interpolating rates for arbitrary subspace sizes and allowing inexact curvature estimation. When increasing subspace size, our complexity matches $\mathcal{O}(\epsilon^{-3/2})$ of the cubic regularization (CR) rate. Additionally, we propose an adaptive sampling scheme ensuring exact convergence rate of $\mathcal{O}(\epsilon^{-3/2}, \epsilon^{-3})$ to a second-order stationary point, even without sampling all coordinates. Experimental results demonstrate substantial speed-ups achieved by SSCN compared to conventional first-order methods.<|reference_end|>
@article{zhao2024cubic,
    title={Cubic regularized subspace Newton for non-convex optimization},
    author={Jim Zhao, Aurelien Lucchi, Nikita Doikov},
    journal={arXiv preprint arXiv:2406.16666},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.16666},
    primaryClass={cs.LG cs.NA math.NA math.OC}
}