Frank Curtis, Lehigh University

Abstract

We posit that the manner in which worst-case complexity is analyzed for algorithms for solving nonconvex optimization problems leads to misleading characterizations of their performance. We propose a new strategy for analyzing complexity that attempts to more closely resemble actual practice. This is done by partitioning the search space into regions based on properties of the objective function and providing complexity bounds by region. (The partitioning is a theoretical tool only. The regions do not need to be known to an algorithm.) Our new characterization strategy offers new perspectives on the performance of well-known first- and second-order methods, and provides guidance for the design of new practical methods. For example, the strategy informs how the trust region radii should be chosen so that a second-order trust region method attains the same complexity as---and outperforms in practice---a cubic regularization approach.