Timezone: »
Poster
Online Learning with Switching Costs and Other Adaptive Adversaries
Nicolò Cesa-Bianchi · Ofer Dekel · Ohad Shamir
Sun Dec 08 02:00 PM -- 06:00 PM (PST) @ Harrah's Special Events Center, 2nd Floor
We study the power of different types of adaptive (nonoblivious) adversaries in the setting of prediction with expert advice, under both full-information and bandit feedback. We measure the player's performance using a new notion of regret, also known as policy regret, which better captures the adversary's adaptiveness to the player's behavior. In a setting where losses are allowed to drift, we characterize ---in a nearly complete manner--- the power of adaptive adversaries with bounded memories and switching costs. In particular, we show that with switching costs, the attainable rate with bandit feedback is $T^{2/3}$. Interestingly, this rate is significantly worse than the $\sqrt{T}$ rate attainable with switching costs in the full-information case. Via a novel reduction from experts to bandits, we also show that a bounded memory adversary can force $T^{2/3}$ regret even in the full information case, proving that switching costs are easier to control than bounded memory adversaries. Our lower bounds rely on a new stochastic adversary strategy that generates loss processes with strong dependencies.
Author Information
Nicolò Cesa-Bianchi (Università degli Studi di Milano, Italy)
Ofer Dekel (Microsoft Research)
Ohad Shamir (Weizmann Institute of Science)
More from the Same Authors
-
2021 Spotlight: Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems »
Itay Safran · Ohad Shamir -
2022 : On the Complexity of Finding Small Subgradients in Nonsmooth Optimization »
Guy Kornowski · Ohad Shamir -
2022 : On the Complexity of Finding Small Subgradients in Nonsmooth Optimization »
Guy Kornowski · Ohad Shamir -
2023 Poster: Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance »
Nikita Kornilov · Ohad Shamir · Aleksandr Lobanov · Alexander Gasnikov · Innokentiy Shibaev · Eduard Gorbunov · Darina Dvinskikh · Samuel Horváth -
2023 Poster: Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks »
Roey Magen · Ohad Shamir -
2023 Poster: From Tempered to Benign Overfitting in ReLU Neural Networks »
Guy Kornowski · Gilad Yehudai · Ohad Shamir -
2022 Poster: On Margin Maximization in Linear and ReLU Networks »
Gal Vardi · Ohad Shamir · Nati Srebro -
2022 Poster: The Sample Complexity of One-Hidden-Layer Neural Networks »
Gal Vardi · Ohad Shamir · Nati Srebro -
2022 Poster: Reconstructing Training Data From Trained Neural Networks »
Niv Haim · Gal Vardi · Gilad Yehudai · Ohad Shamir · Michal Irani -
2022 Poster: Gradient Methods Provably Converge to Non-Robust Networks »
Gal Vardi · Gilad Yehudai · Ohad Shamir -
2021 Poster: Learning a Single Neuron with Bias Using Gradient Descent »
Gal Vardi · Gilad Yehudai · Ohad Shamir -
2021 Poster: Oracle Complexity in Nonsmooth Nonconvex Optimization »
Guy Kornowski · Ohad Shamir -
2021 Poster: A Stochastic Newton Algorithm for Distributed Convex Optimization »
Brian Bullins · Kshitij Patel · Ohad Shamir · Nathan Srebro · Blake Woodworth -
2021 Oral: Oracle Complexity in Nonsmooth Nonconvex Optimization »
Guy Kornowski · Ohad Shamir -
2021 Poster: Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems »
Itay Safran · Ohad Shamir -
2020 : Poster Session 1 (gather.town) »
Laurent Condat · Tiffany Vlaar · Ohad Shamir · Mohammadi Zaki · Zhize Li · Guan-Horng Liu · Samuel Horváth · Mher Safaryan · Yoni Choukroun · Kumar Shridhar · Nabil Kahale · Jikai Jin · Pratik Kumar Jawanpuria · Gaurav Kumar Yadav · Kazuki Koyama · Junyoung Kim · Xiao Li · Saugata Purkayastha · Adil Salim · Dighanchal Banerjee · Peter Richtarik · Lakshman Mahto · Tian Ye · Bamdev Mishra · Huikang Liu · Jiajie Zhu -
2020 : Contributed talks in Session 1 (Zoom) »
Sebastian Stich · Laurent Condat · Zhize Li · Ohad Shamir · Tiffany Vlaar · Mohammadi Zaki -
2020 : Contributed Video: Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?, Ohad Shamir »
Ohad Shamir -
2020 Poster: Neural Networks with Small Weights and Depth-Separation Barriers »
Gal Vardi · Ohad Shamir -
2020 Session: Orals & Spotlights Track 11: Learning Theory »
Dylan Foster · Nicolò Cesa-Bianchi -
2019 Poster: On the Power and Limitations of Random Features for Understanding Neural Networks »
Gilad Yehudai · Ohad Shamir -
2018 Poster: Learning SMaLL Predictors »
Vikas Garg · Ofer Dekel · Lin Xiao -
2018 Poster: Are ResNets Provably Better than Linear Predictors? »
Ohad Shamir -
2018 Poster: Global Non-convex Optimization with Discretized Diffusions »
Murat Erdogdu · Lester Mackey · Ohad Shamir -
2017 : Poster session »
Nicolò Cesa-Bianchi -
2017 Workshop: Workshop on Prioritising Online Content »
John Shawe-Taylor · Massimiliano Pontil · Nicolò Cesa-Bianchi · Emine Yilmaz · Chris Watkins · Sebastian Riedel · Marko Grobelnik -
2017 Poster: Nonparametric Online Regression while Learning the Metric »
Ilja Kuzborskij · Nicolò Cesa-Bianchi -
2017 Poster: Online Learning with a Hint »
Ofer Dekel · arthur flajolet · Nika Haghtalab · Patrick Jaillet -
2017 Poster: Boltzmann Exploration Done Right »
Nicolò Cesa-Bianchi · Claudio Gentile · Gergely Neu · Gabor Lugosi -
2016 Poster: Dimension-Free Iteration Complexity of Finite Sum Optimization Problems »
Yossi Arjevani · Ohad Shamir -
2016 Poster: Without-Replacement Sampling for Stochastic Gradient Methods »
Ohad Shamir -
2016 Oral: Without-Replacement Sampling for Stochastic Gradient Methods »
Ohad Shamir -
2016 Poster: Efficient Second Order Online Learning by Sketching »
Haipeng Luo · Alekh Agarwal · Nicolò Cesa-Bianchi · John Langford -
2015 Poster: Bandit Smooth Convex Optimization: Improving the Bias-Variance Tradeoff »
Ofer Dekel · Ronen Eldan · Tomer Koren -
2015 Spotlight: Bandit Smooth Convex Optimization: Improving the Bias-Variance Tradeoff »
Ofer Dekel · Ronen Eldan · Tomer Koren -
2015 Poster: Communication Complexity of Distributed Convex Learning and Optimization »
Yossi Arjevani · Ohad Shamir -
2014 Poster: The Blinded Bandit: Learning with Adaptive Feedback »
Ofer Dekel · Elad Hazan · Tomer Koren -
2014 Poster: Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation »
Ohad Shamir -
2014 Poster: On the Computational Efficiency of Training Neural Networks »
Roi Livni · Shai Shalev-Shwartz · Ohad Shamir -
2013 Poster: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Oral: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Session: Oral Session 8 »
Ofer Dekel -
2013 Poster: A Gang of Bandits »
Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2012 Workshop: Multi-Trade-offs in Machine Learning »
Yevgeny Seldin · Guy Lever · John Shawe-Taylor · Nicolò Cesa-Bianchi · Yacov Crammer · Francois Laviolette · Gabor Lugosi · Peter Bartlett -
2012 Poster: A Linear Time Active Learning Algorithm for Link Classification »
Nicolò Cesa-Bianchi · Claudio Gentile · Fabio Vitale · Giovanni Zappella -
2012 Poster: Mirror Descent Meets Fixed Share (and feels no regret) »
Nicolò Cesa-Bianchi · Pierre Gaillard · Gabor Lugosi · Gilles Stoltz -
2011 Workshop: New Frontiers in Model Order Selection »
Yevgeny Seldin · Yacov Crammer · Nicolò Cesa-Bianchi · Francois Laviolette · John Shawe-Taylor -
2011 Poster: Efficient Online Learning via Randomized Rounding »
Nicolò Cesa-Bianchi · Ohad Shamir -
2011 Oral: Efficient Online Learning via Randomized Rounding »
Nicolò Cesa-Bianchi · Ohad Shamir -
2011 Poster: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2011 Spotlight: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2010 Workshop: Learning on Cores, Clusters, and Clouds »
Alekh Agarwal · Lawrence Cayton · Ofer Dekel · John Duchi · John Langford -
2010 Session: Spotlights Session 4 »
Ofer Dekel -
2010 Session: Oral Session 4 »
Ofer Dekel -
2009 Workshop: Learning from Multiple Sources with Applications to Robotics »
Barbara Caputo · Nicolò Cesa-Bianchi · David R Hardoon · Gayle Leen · Francesco Orabona · Jaakko Peltonen · Simon Rogers -
2009 Poster: Distribution-Calibrated Hierarchical Classification »
Ofer Dekel -
2008 Poster: Linear Classification and Selective Sampling Under Low Noise Conditions »
Giovanni Cavallanti · Nicolò Cesa-Bianchi · Claudio Gentile -
2008 Poster: From Online to Batch Learning with Cutoff-Averaging »
Ofer Dekel -
2006 Poster: Support Vector Machines on a Budget »
Ofer Dekel · Yoram Singer -
2006 Spotlight: Support Vector Machines on a Budget »
Ofer Dekel · Yoram Singer