2022/05/25 by Saeed Masiha, Saber Salehkaleybar, Masiha, Saeed +7 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and ELM #Model Reduction and Neural Networks #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2205.12856
openalex publication_date 2022/05/25 · openalex created_date 2022/06/13 · openalex updated_date 2026/07/28
We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with 1≤α≤2 which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that the total sample complexity of SCRN in achieving ε-global optimum is O(ε-7/(2α)+1) for 1≤α< 3/2 and \mathcalO(ε-2/(α)) for 3/2≤α≤ 2. SCRN improves the best-known sample complexity of stochastic gradient descent. Even under a weak version of gradient dominance property, which is applicable to policy-based reinforcement learning (RL), SCRN achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the average sample complexity of SCRN can be reduced to O(ε-2) for α=1 using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.