Probabilistic Analysis of Derivative-Free Methods

Clement Royer
Seminar

Numerical optimization has recently faced a change of paradigm, due to the outbreak of randomization within algorithmic frameworks. Motivated by the large-scale setting arising from data treatment, research in optimization has been focusing on economic variants of well-known methods that rely on random elements to improve practical performance, while maintaining convergence guarantees. However, the stochastic features of those algorithms often requires their usual, deterministic analysis to be reconsidered. Probability theory thus plays a key role in obtaining suitable theoretical results.

In this talk, we will focus on recent advances regarding the randomization of derivative-free frameworks. After reviewing the most signi cant developments of such techniques, we will derive a typical analysis in the context of direct-search-type methods. A direct-search instance based on random directions will be introduced, as well as the appropriate probabilistic tools needed for obtaining both convergence results and complexity estimates. We will then detail a practical implementation of the proposed scheme, putting in perspective its theoretical and practical performance. Finally, we will discuss challenging open issues related to second-order probabilistic aspects.