390012 SE PhD-AW: Zero order stochastic optimization revisited (2022S)

We study the problem of finding the minimizer of a function by a sequential exploration of its values, under measurement noise. This problem is known under the name of derivative-free or zero-order stochastic optimization. Classical results in the statistics literature starting from 1950-ies focused on deriving consistent and asymptotically normal procedures and explored the rates of convergence when the number of queries tends to infinity and all other parameters stay fixed. In recent years, zero-order methods re-emerged in the machine learning literature in the context of bandit problems, deep neural networks and other applications. In contrast to the earlier work in statistics, this line of research is interested in non-asymptotic garantees on the performance of the algorithms and understanding the explicit dependency of the bounds on the dimension and other parameters.
In the current course, we provide an introduction to zero-order stochastic optimization under this new perspective and highlight its connection to nonparametric estimation. The main objects of study are approximations of the gradient descent algorithm where the gradient is estimated by randomized procedures involving kernel smoothing. Assuming that the objective function is (strongly) convex and β-Hölder and the noise is adversarial, we obtain non-asymptotic upper bounds both for the optimization error and the cumulative regret of the algorithms. We also establish minimax lower bounds for any sequential search method implying that the suggested algorithms are nearly optimal in a minimax sense in terms of sample complexity and the problem parameters. The approach is extended to several other settings, such as non-convex stochastic optimization, estimation of the minimum value of the function and zero-order distributed stochastic optimization.