Trading Off Resource Budgets for Improved Regret Bounds
This work addresses online learning with budget constraints for researchers and practitioners, offering incremental improvements by adapting existing techniques to new settings.
The paper tackles the problem of adversarial online learning where selecting multiple arms incurs the minimum cost, proposing the FPML algorithm that achieves expected regret O(T^(1/(B+1)) * ln(N)^(B/(B+1))) relative to the single best arm, introducing a trade-off between budget B and regret. It applies this to generalize online submodular maximization algorithms, empirically tests on hyperparameter optimization, and develops new linear programming algorithms with fewer oracle calls.
In this work we consider a variant of adversarial online learning where in each round one picks $B$ out of $N$ arms and incurs cost equal to the $\textit{minimum}$ of the costs of each arm chosen. We propose an algorithm called Follow the Perturbed Multiple Leaders (FPML) for this problem, which we show (by adapting the techniques of Kalai and Vempala [2005]) achieves expected regret $\mathcal{O}(T^{\frac{1}{B+1}}\ln(N)^{\frac{B}{B+1}})$ over time horizon $T$ relative to the $\textit{single}$ best arm in hindsight. This introduces a trade-off between the budget $B$ and the single-best-arm regret, and we proceed to investigate several applications of this trade-off. First, we observe that algorithms which use standard regret minimizers as subroutines can sometimes be adapted by replacing these subroutines with FPML, and we use this to generalize existing algorithms for Online Submodular Function Maximization [Streeter and Golovin, 2008] in both the full feedback and semi-bandit feedback settings. Next, we empirically evaluate our new algorithms on an online black-box hyperparameter optimization problem. Finally, we show how FPML can lead to new algorithms for Linear Programming which require stronger oracles at the benefit of fewer oracle calls.