Preprint
Adaptive Bandit Convex Optimization with Heterogeneous Curvature
arXiv (Cornell University)
02/12/2022
DOI: 10.48550/arxiv.2202.06150
Abstract
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 O˜(d3/2T−−√) 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 T3/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.
Details
- Title: Subtitle
- Adaptive Bandit Convex Optimization with Heterogeneous Curvature
- Creators
- Haipeng LuoMengxiao ZhangPeng Zhao
- Resource Type
- Preprint
- Publication Details
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2202.06150
- eISSN
- 2331-8422
- Language
- English
- Date posted
- 02/12/2022
- Academic Unit
- Business Analytics
- Record Identifier
- 9984701828002771
Metrics
1 Record Views