2024/10/16 by Yü Liu, Weibin Peng, Liu, Yu +5
Computer Science · Engineering · Mathematics · #Advanced Image Processing Techniques #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2410.22357
openalex publication_date 2024/10/16 · openalex created_date 2024/11/14 · openalex updated_date 2026/07/28
This paper studies stochastic minimization of a finite-sum loss F (x) = (1)/(N) ∑ξ=1N f(x;ξ) . In many real-world scenarios, the Hessian matrix of such objectives exhibits a low-rank structure on a batch of data. At the same time, zeroth-order optimization has gained prominence in important applications such as fine-tuning large language models. Drawing on these observations, we propose a novel stochastic zeroth-order cubic Newton method that leverages the low-rank Hessian structure via a matrix recovery-based estimation technique. Our method circumvents restrictive incoherence assumptions, enabling accurate Hessian approximation through finite-difference queries. Theoretically, we establish that for most real-world problems in ℝn, O(\fracnη(7)/(2))+\widetildeO(\fracn2 η(5)/(2)) function evaluations suffice to attain a second-order η-stationary point with high probability. This represents a significant improvement in dimensional dependence over existing methods. This improvement is mostly due to a new Hessian estimator that achieves superior sample complexity; This new Hessian estimation method might be of separate interest. Numerical experiments on matrix recovery and machine learning tasks validate the efficacy and scalability of our approach.