On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities.
Alexander RakhlinKarthik SridharanPublished in: COLT (2017)
Keyphrases
- regret bounds
- confidence bounds
- lower bound
- randomized algorithms
- worst case
- upper bound
- online learning
- sufficient conditions
- linear regression
- risk bounds
- linear inequalities
- upper and lower bounds
- expert advice
- vc dimension
- equivalence relation
- error bounds
- lower and upper bounds
- heavy tailed
- randomized algorithm
- change detection
- loss bounds
- cutting plane algorithm
- reinforcement learning
- datalog programs
- average case
- data dependent
- branch and bound
- loss function