2024/06/24 by Jim Zhao, Zhao, Jim, Aurélien Lucchi +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2406.16666
openalex publication_date 2024/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(ε-3/2) of the cubic regularization (CR) rate. Additionally, we propose an adaptive sampling scheme ensuring exact convergence rate of O(ε-3/2, ε-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.