1.6k citations · 3.6k across the 48 of their papers we have counts for
3 papers · 1 filter
Hardness of Online Sleeping Combinatorial Optimization Problems
Satyen Kale, Chansoo Lee, Dávid Pál
We show that several online combinatorial optimization problems that admit efficient no-regret algorithms become computationally hard in the sleeping setting where a subset of acti…
Online Gradient Boosting
Alina Beygelzimer, Elad Hazan, Satyen Kale +1
We extend the theory of boosting for regression problems to the online learning setting. Generalizing from the batch setting for boosting, the notion of a weak learning algorithm i…
Optimal and Adaptive Algorithms for Online Boosting
Alina Beygelzimer, Satyen Kale, Haipeng Luo
We study online boosting, the task of converting any weak online learner into a strong online learner. Based on a novel and natural definition of weak online learnability, we devel…