Optimal rates for first-order stochastic convex optimization under Tsybakov noise condition

Aaditya Ramdas, Aarti Singh

We focus on the problem of minimizing a convex function $f$ over a convex set $S$ given $T$ queries to a stochastic first order oracle. We argue that the complexity of convex minim…