Timezone: »
Poster
Online Learning with Primary and Secondary Losses
Avrim Blum · Han Shao
We study the problem of online learning with primary and secondary losses. For example, a recruiter making decisions of which job applicants to hire might weigh false positives and false negatives equally (the primary loss) but the applicants might weigh false negatives much higher (the secondary loss). We consider the following question: Can we combine ``expert advice'' to achieve low regret with respect to the primary loss, while at the same time performing {\em not much worse than the worst expert} with respect to the secondary loss? Unfortunately, we show that this goal is unachievable without any bounded variance assumption on the secondary loss. More generally, we consider the goal of minimizing the regret with respect to the primary loss and bounding the secondary loss by a linear threshold. On the positive side, we show that running any switching-limited algorithm can achieve this goal if all experts satisfy the assumption that the secondary loss does not exceed the linear threshold by $o(T)$ for any time interval. If not all experts satisfy this assumption, our algorithms can achieve this goal given access to some external oracles which determine when to deactivate and reactivate experts.
Author Information
Avrim Blum (Toyota Technological Institute at Chicago)
Han Shao (Toyota Technological Institute at Chicago)
More from the Same Authors
-
2021 Spotlight: Excess Capacity and Backdoor Poisoning »
Naren Manoj · Avrim Blum -
2021 : One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning »
Richard Phillips · Han Shao · Avrim Blum · Nika Haghtalab -
2021 : On classification of strategic agents who can both game and improve »
Saba Ahmadi · Hedyeh Beyhaghi · Avrim Blum · Keziah Naggita -
2021 : The Strategic Perceptron »
Saba Ahmadi · Hedyeh Beyhaghi · Avrim Blum · Keziah Naggita -
2021 : One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning »
Richard Phillips · Han Shao · Avrim Blum · Nika Haghtalab -
2021 : On classification of strategic agents who can both game and improve »
Saba Ahmadi · Hedyeh Beyhaghi · Avrim Blum · Keziah Naggita -
2021 : The Strategic Perceptron »
Saba Ahmadi · Hedyeh Beyhaghi · Avrim Blum · Keziah Naggita -
2022 : Certifiable Robustness Against Patch Attacks Using an ERM Oracle »
Kevin Stangl · Avrim Blum · Omar Montasser · Saba Ahmadi -
2022 Panel: Panel 2C-2: Agreement-on-the-line: Predicting the… & A Theory of… »
Han Shao · Christina Baek -
2022 : Panel »
Meena Jagadeesan · Avrim Blum · Jon Kleinberg · Celestine Mendler-Dünner · Jennifer Wortman Vaughan · Chara Podimata -
2022 Poster: Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness »
Avrim Blum · Omar Montasser · Greg Shakhnarovich · Hongyang Zhang -
2022 Poster: A Theory of PAC Learnability under Transformation Invariances »
Han Shao · Omar Montasser · Avrim Blum -
2021 Poster: Excess Capacity and Backdoor Poisoning »
Naren Manoj · Avrim Blum -
2020 Workshop: Workshop on Dataset Curation and Security »
Nathalie Baracaldo · Yonatan Bisk · Avrim Blum · Michael Curry · John Dickerson · Micah Goldblum · Tom Goldstein · Bo Li · Avi Schwarzschild -
2020 Session: Orals & Spotlights Track 24: Learning Theory »
Avrim Blum · Steve Hanneke -
2018 Poster: On preserving non-discrimination when combining expert advice »
Avrim Blum · Suriya Gunasekar · Thodoris Lykouris · Nati Srebro -
2017 Poster: Collaborative PAC Learning »
Avrim Blum · Nika Haghtalab · Ariel Procaccia · Mingda Qiao -
2014 Poster: Learning Optimal Commitment to Overcome Insecurity »
Avrim Blum · Nika Haghtalab · Ariel Procaccia -
2014 Poster: Learning Mixtures of Ranking Models »
Pranjal Awasthi · Avrim Blum · Or Sheffet · Aravindan Vijayaraghavan -
2014 Poster: Active Learning and Best-Response Dynamics »
Maria-Florina F Balcan · Christopher Berlind · Avrim Blum · Emma Cohen · Kaushik Patnaik · Le Song -
2014 Spotlight: Learning Mixtures of Ranking Models »
Pranjal Awasthi · Avrim Blum · Or Sheffet · Aravindan Vijayaraghavan -
2010 Spotlight: Trading off Mistakes and Don't-Know Predictions »
Amin Sayedi · Avrim Blum · Morteza Zadimoghaddam -
2010 Poster: Trading off Mistakes and Don't-Know Predictions »
Amin Sayedi · Morteza Zadimoghaddam · Avrim Blum -
2009 Workshop: Clustering: Science or art? Towards principled approaches »
Margareta Ackerman · Shai Ben-David · Avrim Blum · Isabelle Guyon · Ulrike von Luxburg · Robert Williamson · Reza Zadeh -
2009 Poster: Tracking Dynamic Sources of Malicious Activity at Internet Scale »
Shobha Venkataraman · Avrim Blum · Dawn Song · Subhabrata Sen · Oliver Spatscheck -
2009 Spotlight: Tracking Dynamic Sources of Malicious Activity at Internet Scale »
Shobha Venkataraman · Avrim Blum · Dawn Song · Subhabrata Sen · Oliver Spatscheck -
2008 Workshop: New Challanges in Theoretical Machine Learning: Data Dependent Concept Spaces »
Maria-Florina F Balcan · Shai Ben-David · Avrim Blum · Kristiaan Pelckmans · John Shawe-Taylor