Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits
2. července 2022
Řečníci
Julian Zimmert
Řečník · 0 sledujících
Tor Lattimore
Řečník · 1 sledující
O prezentaci
We introduce a modification of follow the regularised leader and combine it with the log determinant potential and suitable loss estimators to prove that the minimax regret for adaptive adversarial linear bandits is at most O(d √(T log(T))) where d is the dimension and T is the number of rounds. By using exponential weights, we improve this bound to O(√(dTlog(kT))) when the action set has size k. These results confirms an old conjecture. We also show that follow the regularized leader with the entropic barrier and suitable loss estimators has regret against an adaptive adversary of at most O(d^2 √(T)log(T)) and can be implement in polynomial time, which improves on the best known bound for an efficient algorithm of O(d^7/2√(T)(log(T))) by Lee et al 2020.We introduce a modification of follow the regularised leader and combine it with the log determinant potential and suitable loss estimators to prove that the minimax regret for adaptive adversarial linear bandits is at most O(d √(T log(T))) where d is the dimension and T is the number of rounds. By using exponential weights, we improve this bound to O(√(dTlog(kT))) when the action set has size k. These results confirms an old conjecture. We also show that follow the regularized leader with the e…
O organizátorovi (COLT)
The conference is held annually since 1988 and has become the leading conference on Learning theory by maintaining a highly selective process for submissions. It is committed in high-quality articles in all theoretical aspects of machine learning and related topics.
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Non-Gaussian Component Analysis via Lattice Basis Reduction
Zhlédnout později
Learning Low Degree Hypergraphs
Zhlédnout později
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
Zhlédnout později
Smoothed Online Learning is as Easy as Statistical Learning
Zhlédnout později
Adam Block, …
Data-driven confidence bands for distributed nonparametric regression
Zhlédnout později
