On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
This work addresses foundational theoretical gaps in optimization and machine learning by establishing complexity bounds for bandit and derivative-free problems, which is significant for researchers and practitioners in these fields, though it is incremental in building on prior upper bounds.
The paper tackles the problem of characterizing the inherent complexity of stochastic convex optimization with bandit or derivative-free feedback, providing precise lower bounds on error/regret as a function of dimension and queries, and showing that queries must scale at least quadratically with dimension. It also demonstrates that a fast O(1/T) error rate is achievable on quadratic functions without gradients, which is a novel result in derivative-free stochastic settings.
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, which also imply a non-trivial lower bound for more general problems. Moreover, 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 in terms of T, 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.