The problem of stochastic convex optimization with bandit feedback (in the learning community) or without knowledge of gradients (in the optimization community) has received much attention in recent years, in the form of algorithms and performance upper bounds. However, much less is known about the inherent complexity of these problems, and there are few lower bounds in the literature, especially for nonlinear functions. In this paper, we investigate the attainable error/regret in the bandit and derivative-free settings, as a function of the dimension d and the available number of queries T. We provide a precise characterization of the attainable performance for strongly-convex and smooth functions, as well as non-trivial lower bounds for more general problems. Also, we prove that in both the bandit and derivative-free setting, the required number of queries must scale at least quadratically with the dimension. Finally, we show that on the natural class of quadratic functions, it is possible to obtain a "fast" O(1/T) error rate, under mild assumptions, even without having access to gradients. To the best of our knowledge, this is the first such rate in a derivative-free stochastic setting, and holds despite previous results which seem to imply the contrary.

本文探讨了在带有巴氏反馈或者没有梯度知识下的凸随机优化问题。我们通过精确表征强凸平滑函数的性能以及非凸平滑函数的性能下界，证明了在这两种情况下，所需的查询次数至少要实现二次比例尺度关系。我们同时还发现对于二次函数，即使在没有梯度信息的情况下，也可以在平方次的询问内实现 O(1/T) 的误差率。此结果是在派生式随机情况下的首次结果，并且在之前暗示相反的情况下，依然成立。

探讨赌博机和无导数随机凸优化的复杂性