Direct-search methods are a class of popular derivative-free algorithms which are based on (polling) directions, typically extracted from positive spanning sets when applied to the minimization of smooth functions. A positive spanning set must have at least $n+1$ vectors, $n$ being the dimension of the variable space. Besides, to ensure the global convergence of these algorithms, the positive spanning sets used throughout the iterations must be uniformly nondegenerate in the sense of having a positive (cosine) measure bounded away from zero.
However, recent numerical results indicated that randomly generating the polling directions without imposing the positive spanning property can improve the performance of these methods, especially when the number of polling directions is chosen considerably less than $n+1$.
In this talk, we analyze direct-search algorithms when the polling directions are probabilistic descent, meaning that with a significantly positive probability at least one of them is of descent type. Almost-sure global convergence is established following an argument known for trust-region methods. The worst-case complexity is addressed by deriving a suitable global rate but now under an appropriate probability. Our analysis helps understand the observed numerical behaviour and links the choice of the number of polling directions to the tradeoff between robustness and efficiency.