  


Worstcase evaluation complexity and optimality of secondorder methods for nonconvex smooth optimization
Coralia Cartis(coralia.cartismaths.ox.ac.uk) Abstract: We establish or refute the optimality of inexact secondorder methods for unconstrained nonconvex optimization from the point of view of worstcase evaluation complexity, improving and generalizing the results of Cartis, Gould and Toint (2010,2011). To this aim, we consider a new general class of inexact secondorder algorithms for unconstrained optimization that includes regularization and trustregion variations of Newton's method as well as of their linesearch variants. For each method in this class and arbitrary accuracy threshold epsilon in (0,1), we exhibit a smooth objective function with bounded range, whose gradient is globally Lipschitz continuous and whose Hessian is alphaHolder continuous (for given alpha in [0,1]), for which the method in question takes at least epsilon^{(2+\alpha)/(1+\alpha)}function evaluations to generate a first iterate whose gradient is smaller than $\epsilon$ in norm. Moreover, we also construct another function on which Newton's takes epsilon^{2} evaluations, but whose Hessian is Lipschitz continuous on the path of iterates. These examples provide lower bounds on the worstcase evaluation complexity of methods in our class when applied to smooth problems satisfying the relevant assumptions. Furthermore, for $\alpha=1$, this lower bound is of the same order in $\epsilon$ as the upper bound on the worstcase evaluation complexity of the cubic regularization method and other methods in a class of methods proposed in Curtis, Robinson and Samadi (2017) or in Royer and wright (2017), thus implying that these methods have optimal worstcase evaluation complexity within a wider class of secondorder methods, and that Newton's method is suboptimal. Keywords: evaluation complexity, nonconvex optimization, secondorder methods Category 1: Nonlinear Optimization (Unconstrained Optimization ) Citation: Technical Report, naXys, University of Namur, Namur (Belgium), 2017 Download: [PDF] Entry Submitted: 09/21/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  