A fully stochastic second-order trust region method. (4th May 2022)

• Record Type: Journal Article
• Authors: Curtis, Frank E.; Shi, Rui
• Is Part Of: Optimization methods and software. Volume 37:Number 3(2022)
• Page Start: 844
• Page End: 877
• Publication Date: 2022-05-04
• Subjects: Stochastic optimization -- finite-sum optimization -- stochastic Newton methods -- trust region methods -- machine learning -- deep neural networks -- time series forecasting; 90C15 -- 90C26 -- 90C30 -- 49M15 -- 65K05; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1852403
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: A stochastic second-order trust region method is proposed, which can be viewed as an extension of the trust-region-ish (TRish) algorithm proposed by Curtis et al. [ A stochastic trust region algorithm based on careful step normalization. INFORMS J. Optim. 1(3) 200–220, 2019]. In each iteration, a search direction is computed by (approximately) solving a subproblem defined by stochastic gradient and Hessian estimates. The algorithm has convergence guarantees in the fully stochastic regime, i.e. when each stochastic gradient is merely an unbiased estimate of the gradient with bounded variance and the stochastic Hessian estimates are bounded. This framework covers a variety of implementations, such as when the stochastic Hessians are defined by sampled second-order derivatives or diagonal matrices, such as in RMSprop, Adagrad, Adam and other popular algorithms. The proposed algorithm has a worst-case complexity guarantee in the nearly deterministic regime, i.e. when the stochastic gradients and Hessians are close in expectation to the true gradients and Hessians. The results of numerical experiments for training CNNs for image classification and an RNN for time series forecasting are presented. These results show that the algorithm can outperform a stochastic gradient and first-order TRish algorithm.