Adaptive Bandit Convex Optimization with Heterogeneous Curvature
This addresses a limitation in online learning for convex optimization by handling heterogeneous settings, offering potential improvements in regret bounds for applications like adaptive control or resource allocation, though it is incremental as it extends prior frameworks to bandit feedback.
The paper tackles the problem of adversarial bandit convex optimization with heterogeneous curvature, where each loss function has its own curvature revealed only after decisions, and develops an efficient algorithm that adapts to curvature on the fly, achieving results like $\widetilde{O}(d^{3/2}\sqrt{T})$ regret even when many functions are not strongly convex.
We consider the problem of adversarial bandit convex optimization, that is, online learning over a sequence of arbitrary convex loss functions with only one function evaluation for each of them. While all previous works assume known and homogeneous curvature on these loss functions, we study a heterogeneous setting where each function has its own curvature that is only revealed after the learner makes a decision. We develop an efficient algorithm that is able to adapt to the curvature on the fly. Specifically, our algorithm not only recovers or \emph{even improves} existing results for several homogeneous settings, but also leads to surprising results for some heterogeneous settings -- for example, while Hazan and Levy (2014) showed that $\widetilde{O}(d^{3/2}\sqrt{T})$ regret is achievable for a sequence of $T$ smooth and strongly convex $d$-dimensional functions, our algorithm reveals that the same is achievable even if $T^{3/4}$ of them are not strongly convex, and sometimes even if a constant fraction of them are not strongly convex. Our approach is inspired by the framework of Bartlett et al. (2007) who studied a similar heterogeneous setting but with stronger gradient feedback. Extending their framework to the bandit feedback setting requires novel ideas such as lifting the feasible domain and using a logarithmically homogeneous self-concordant barrier regularizer.