Random tilts to find stationary points in stochastic convex optimization
A few complementary results are presented that show that some dimension dependence is necessary, in distinction from standard stochastic optimization and empirical risk minimization, by providing minimax lower bounds scaling as $\sqrt{d/n}$ for d-dimensional problems given $n$ observations.