Zero-Order Methods: Global Rates and Randomness

Luís Nunes Vicente^*

In some derivative-free methods, it is possible to develop worst case complexity bounds in terms of the number of iterations or function evaluations to reach some level of stationarity. Such global rates complement existing analyses of global convergence by providing additional insight and comparisons.\newline We show that the broad class of direct-search methods of directional type, based on imposing sufficient decrease to accept new iterates, exhibits the same global rates or worst case complexity bounds of the gradient method for the unconstrained minimization of a smooth function, both in the nonconvex and convex cases. A smoothing direct search approach is also discussed capable of deliver a global rate in the nonsmooth nonconvex setting.\newline We will also present some recent interesting discoveries in probabilistic direct-search methods where polling does not rely necessarily on positive spanning sets and global rates are developed for certain positive probability. At this point we will connect to the other broad class of derivative-free methods based on modeling and trust regions.\newline This is joint work with M. Dodangeh, R. Garmanjani, S. Gratton, C. Royer, and Z. Zhang.

Mathematics Subject Classification:

Keywords:

Plenary Lecture