A. Gasnikov

Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints

We establish the optimal query complexity of smooth convex quadratic optimization from exact function values. For dimension $d$, smoothness $L$, and minimizer radius $R$, the sharp rate at small relative error is $\Theta(d\min\{d,\sqrt{LR^2/\varepsilon}\})$. The lower bound has no logarithmic loss and holds even for ad...