Timezone: »
We consider the decision-making framework of online convex optimization with a very large number of experts. This setting is ubiquitous in contextual and reinforcement learning problems, where the size of the policy class renders enumeration and search within the policy class infeasible. Instead, we consider generalizing the methodology of online boosting. We define a weak learning algorithm as a mechanism that guarantees multiplicatively approximate regret against a base class of experts. In this access model, we give an efficient boosting algorithm that guarantees near-optimal regret against the convex hull of the base class. We consider both full and partial (a.k.a. bandit) information feedback models. We also give an analogous efficient boosting algorithm for the i.i.d. statistical setting. Our results simultaneously generalize online boosting and gradient boosting guarantees to contextual learning model, online convex optimization and bandit linear optimization settings.
Author Information
Elad Hazan (Princeton University and Google Brain)
Karan Singh (Microsoft Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Boosting for Online Convex Optimization »
Fri. Jul 23rd 03:35 -- 03:40 AM Room
More from the Same Authors
-
2021 : Robust online control with model misspecification »
Xinyi Chen · Udaya Ghai · Elad Hazan · Alexandre Megretsky -
2021 : A Boosting Approach to Reinforcement Learning »
Nataly Brukhim · Elad Hazan · Karan Singh -
2022 : Non-convex online learning via algorithmic equivalence »
Udaya Ghai · Zhou Lu · Elad Hazan -
2022 Poster: A Regret Minimization Approach to Multi-Agent Control »
Udaya Ghai · Udari Madhuhshani · Naomi Leonard · Elad Hazan -
2022 Spotlight: A Regret Minimization Approach to Multi-Agent Control »
Udaya Ghai · Udari Madhuhshani · Naomi Leonard · Elad Hazan -
2021 Poster: A Regret Minimization Approach to Iterative Learning Control »
Naman Agarwal · Elad Hazan · Anirudha Majumdar · Karan Singh -
2021 Spotlight: A Regret Minimization Approach to Iterative Learning Control »
Naman Agarwal · Elad Hazan · Anirudha Majumdar · Karan Singh -
2021 : Online and non-stochastic control »
Karan Singh -
2021 Tutorial: Online and non-stochastic control »
Elad Hazan · Karan Singh -
2021 : Online and non-stochastic control »
Elad Hazan -
2020 Poster: Boosting for Control of Dynamical Systems »
Naman Agarwal · Nataly Brukhim · Elad Hazan · Zhou Lu -
2019 Poster: Efficient Full-Matrix Adaptive Regularization »
Naman Agarwal · Brian Bullins · Xinyi Chen · Elad Hazan · Karan Singh · Cyril Zhang · Yi Zhang -
2019 Poster: Online Control with Adversarial Disturbances »
Naman Agarwal · Brian Bullins · Elad Hazan · Sham Kakade · Karan Singh -
2019 Oral: Efficient Full-Matrix Adaptive Regularization »
Naman Agarwal · Brian Bullins · Xinyi Chen · Elad Hazan · Karan Singh · Cyril Zhang · Yi Zhang -
2019 Oral: Online Control with Adversarial Disturbances »
Naman Agarwal · Brian Bullins · Elad Hazan · Sham Kakade · Karan Singh -
2019 Poster: Provably Efficient Maximum Entropy Exploration »
Elad Hazan · Sham Kakade · Karan Singh · Abby Van Soest -
2019 Oral: Provably Efficient Maximum Entropy Exploration »
Elad Hazan · Sham Kakade · Karan Singh · Abby Van Soest -
2018 Poster: On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization »
Sanjeev Arora · Nadav Cohen · Elad Hazan -
2018 Oral: On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization »
Sanjeev Arora · Nadav Cohen · Elad Hazan -
2017 Poster: Efficient Regret Minimization in Non-Convex Games »
Elad Hazan · Karan Singh · Cyril Zhang -
2017 Talk: Efficient Regret Minimization in Non-Convex Games »
Elad Hazan · Karan Singh · Cyril Zhang