Timezone: »
Talk
Efficient Regret Minimization in Non-Convex Games
Elad Hazan · Karan Singh · Cyril Zhang
We consider regret minimization in repeated games with non-convex loss functions. Minimizing the standard notion of regret is computationally intractable. Thus, we define a natural notion of regret which permits efficient optimization and generalizes offline guarantees for convergence to an approximate local optimum. We give gradient-based methods that achieve optimal regret, which in turn guarantee convergence to equilibrium in this framework.
Author Information
Elad Hazan (Princeton University)
Karan Singh (Princeton University)
Cyril Zhang (Princeton University)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: Efficient Regret Minimization in Non-Convex Games »
Mon. Aug 7th 08:30 AM -- 12:00 PM Room Gallery #45
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: Boosting for Online Convex Optimization »
Elad Hazan · Karan Singh -
2021 Spotlight: Boosting for Online Convex Optimization »
Elad Hazan · Karan Singh -
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 Tutorial: Online and non-stochastic control »
Elad Hazan · Karan Singh -
2021 : Online and non-stochastic control »
Elad Hazan -
2020 Poster: Calibration, Entropy Rates, and Memory in Language Models »
Mark Braverman · Xinyi Chen · Sham Kakade · Karthik Narasimhan · Cyril Zhang · Yi Zhang -
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: The Price of Differential Privacy For Online Learning »
Naman Agarwal · Karan Singh -
2017 Talk: The Price of Differential Privacy For Online Learning »
Naman Agarwal · Karan Singh