Technical Report ERGO 10-005

On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex optimization
Coralia Cartis, Nicholas I. M. Gould and Philippe L. Toint


The (optimal) function/gradient evaluations worst-case complexity analysis available for the Adaptive Regularizations algorithms with Cubics (ARC) for nonconvex smooth unconstrained optimization is extended to finite-difference versions of this algorithm, yielding complexity bounds for first-order and derivative free methods applied on the same problem class. A comparison with the results obtained for derivative-free methods by Vicente (2010) is also discussed, giving some theoretical insight on the relative merits of various methods in this popular class of algorithms.


Oracle complexity, worst-case analysis, finite-differences, first-order methods, derivative free optimization, nonconvex optimization




Written: 18 October 2010


Published in SIAM Journal on Optimization.