A Stochastic Trust Region Method for Non-convex Minimization

2019/03/04 by Shen, Zebang, Zhou, Pan, Fang, Cong +1
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1903.01540

Abstract

We target the problem of finding a local minimum in non-convex finite-sum minimization. Towards this goal, we first prove that the trust region method with inexact gradient and Hessian estimation can achieve a convergence rate of order O(1/k^2/3) as long as those differential estimations are sufficiently accurate. Combining such result with a novel Hessian estimator, we propose the sample-efficient stochastic trust region (STR) algorithm which finds an (ε, √ε)-approximate local minimum within O(√(n)/ε^1.5) stochastic Hessian oracle queries. This improves state-of-the-art result by O(n^1/6). Experiments verify theoretical conclusions and the efficiency of STR.

Related

• A Stochastic Trust Region Algorithm Based on Careful Step Normalization
• An investigation of stochastic trust-region based algorithms for finite-sum minimization
• A stochastic first-order trust-region method with inexact restoration for finite-sum minimization
• Inexact restoration with subsampled trust-region methods for finite-sum\n minimization
• Fully stochastic trust-region methods with Barzilai-Borwein steplengths