Timezone: »
A burgeoning paradigm in algorithm design is the field of algorithms with predictions, in which algorithms can take advantage of a possibly-imperfect prediction of some aspect of the problem. While much work has focused on using predictions to improve competitive ratios, running times, or other performance measures, less effort has been devoted to the question of how to obtain the predictions themselves, especially in the critical online setting. We introduce a general design approach for algorithms that learn predictors: (1) identify a functional dependence of the performance measure on the prediction quality and (2) apply techniques from online learning to learn predictors, tune robustness-consistency trade-offs, and bound the sample complexity. We demonstrate the effectiveness of our approach by applying it to bipartite matching, ski-rental, page migration, and job scheduling. In several settings we improve upon multiple existing results while utilizing a much simpler analysis, while in the others we provide the first learning-theoretic guarantees.
Author Information
Misha Khodak (CMU)
Maria-Florina Balcan (Carnegie Mellon University)
Ameet Talwalkar (CMU)
Sergei Vassilvitskii (Google)
More from the Same Authors
-
2021 Spotlight: Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond »
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm · Ellen Vitercik -
2021 : Simulated User Studies for Explanation Evaluation »
Valerie Chen · Gregory Plumb · Nicholay Topin · Ameet S Talwalkar -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Sik Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet S Talwalkar · Hoda Heidari · Steven Wu -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet S Talwalkar · Hoda Heidari · Steven Wu -
2022 : AutoML for Climate Change: A Call to Action »
Renbo Tu · Nicholas Roberts · Vishak Prasad C · Sibasis Nayak · Paarth Jain · Frederic Sala · Ganesh Ramakrishnan · Ameet Talwalkar · Willie Neiswanger · Colin White -
2023 Poster: Meta-Learning Adversarial Bandit Algorithms »
Misha Khodak · Ilya Osadchiy · Keegan Harris · Maria-Florina Balcan · Kfir Y. Levy · Ron Meir · Steven Wu -
2023 Poster: Learning with Explanation Constraints »
Rattana Pukdee · Dylan Sam · J. Zico Kolter · Maria-Florina Balcan · Pradeep Ravikumar -
2023 Poster: Bicriteria Multidimensional Mechanism Design with Side Information »
Siddharth Prasad · Maria-Florina Balcan · Tuomas Sandholm -
2023 Poster: New Bounds for Hyperparameter Tuning of Regression Problems Across Instances »
Maria-Florina Balcan · Anh Nguyen · Dravyansh Sharma -
2023 Poster: Reliable learning in challenging environments »
Maria-Florina Balcan · Steve Hanneke · Rattana Pukdee · Dravyansh Sharma -
2022 Competition: AutoML Decathlon: Diverse Tasks, Modern Methods, and Efficiency at Scale »
Samuel Guo · Cong Xu · Nicholas Roberts · Misha Khodak · Junhong Shen · Evan Sparks · Ameet Talwalkar · Yuriy Nevmyvaka · Frederic Sala · Anderson Schneider -
2022 Poster: Use-Case-Grounded Simulations for Explanation Evaluation »
Valerie Chen · Nari Johnson · Nicholay Topin · Gregory Plumb · Ameet Talwalkar -
2022 Poster: Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts »
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm · Ellen Vitercik -
2022 Poster: Provably tuning the ElasticNet across instances »
Maria-Florina Balcan · Misha Khodak · Dravyansh Sharma · Ameet Talwalkar -
2022 Poster: Maximizing Revenue under Market Shrinkage and Market Uncertainty »
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm -
2022 Poster: Algorithms with Prediction Portfolios »
Michael Dinitz · Sungjin Im · Thomas Lavastida · Benjamin Moseley · Sergei Vassilvitskii -
2022 Poster: Efficient Architecture Search for Diverse Tasks »
Junhong Shen · Misha Khodak · Ameet Talwalkar -
2022 Poster: Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
2022 Poster: NAS-Bench-360: Benchmarking Neural Architecture Search on Diverse Tasks »
Renbo Tu · Nicholas Roberts · Misha Khodak · Junhong Shen · Frederic Sala · Ameet Talwalkar -
2021 : [S9] Simulated User Studies for Explanation Evaluation »
Valerie Chen · Gregory Plumb · Nicholay Topin · Ameet S Talwalkar -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Sik Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 Poster: Robust Online Correlation Clustering »
Silvio Lattanzi · Benjamin Moseley · Sergei Vassilvitskii · Yuyan Wang · Rudy Zhou -
2021 Poster: Data driven semi-supervised learning »
Maria-Florina Balcan · Dravyansh Sharma -
2021 Poster: Federated Hyperparameter Tuning: Challenges, Baselines, and Connections to Weight-Sharing »
Mikhail Khodak · Renbo Tu · Tian Li · Liam Li · Maria-Florina Balcan · Virginia Smith · Ameet Talwalkar -
2021 Oral: Faster Matchings via Learned Duals »
Michael Dinitz · Sungjin Im · Thomas Lavastida · Benjamin Moseley · Sergei Vassilvitskii -
2021 Poster: Faster Matchings via Learned Duals »
Michael Dinitz · Sungjin Im · Thomas Lavastida · Benjamin Moseley · Sergei Vassilvitskii -
2021 Poster: Rethinking Neural Operations for Diverse Tasks »
Nicholas Roberts · Mikhail Khodak · Tri Dao · Liam Li · Christopher Ré · Ameet Talwalkar -
2021 Poster: Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond »
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm · Ellen Vitercik -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2021 Poster: Learning-to-learn non-convex piecewise-Lipschitz functions »
Maria-Florina Balcan · Mikhail Khodak · Dravyansh Sharma · Ameet Talwalkar -
2021 Oral: Data driven semi-supervised learning »
Maria-Florina Balcan · Dravyansh Sharma -
2020 Workshop: International Workshop on Scalability, Privacy, and Security in Federated Learning (SpicyFL 2020) »
Xiaolin Andy Li · Dejing Dou · Ameet Talwalkar · Hongyu Li · Jianzong Wang · Yanzhi Wang -
2020 Poster: Regularizing Black-box Models for Improved Interpretability »
Gregory Plumb · Maruan Al-Shedivat · Ángel Alexander Cabrera · Adam Perer · Eric Xing · Ameet Talwalkar -
2019 : Break / Poster Session 1 »
Antonia Marcu · Yao-Yuan Yang · Pascale Gourdeau · Chen Zhu · Thodoris Lykouris · Jianfeng Chi · Mark Kozdoba · Arjun Nitin Bhagoji · Xiaoxia Wu · Jay Nandy · Michael T Smith · Bingyang Wen · Yuege Xie · Konstantinos Pitas · Suprosanna Shit · Maksym Andriushchenko · Dingli Yu · Gaël Letarte · Misha Khodak · Hussein Mozannar · Chara Podimata · James Foulds · Yizhen Wang · Huishuai Zhang · Ondrej Kuzelka · Alexander Levine · Nan Lu · Zakaria Mhammedi · Paul Viallard · Diana Cai · Lovedeep Gondara · James Lucas · Yasaman Mahdaviyeh · Aristide Baratin · Rishi Bommasani · Alessandro Barp · Andrew Ilyas · Kaiwen Wu · Jens Behrmann · Omar Rivasplata · Amir Nazemi · Aditi Raghunathan · Will Stephenson · Sahil Singla · Akhil Gupta · YooJung Choi · Yannic Kilcher · Clare Lyle · Edoardo Manino · Andrew Bennett · Zhi Xu · Niladri Chatterji · Emre Barut · Flavien Prost · Rodrigo Toro Icarte · Arno Blaas · Chulhee Yun · Sahin Lale · YiDing Jiang · Tharun Kumar Reddy Medini · Ashkan Rezaei · Alexander Meinke · Stephen Mell · Gary Kazantsev · Shivam Garg · Aradhana Sinha · Vishnu Lokhande · Geovani Rizk · Han Zhao · Aditya Kumar Akash · Jikai Hou · Ali Ghodsi · Matthias Hein · Tyler Sypherd · Yichen Yang · Anastasia Pentina · Pierre Gillot · Antoine Ledent · Guy Gur-Ari · Noah MacAulay · Tianzong Zhang -
2019 : TBD »
Ameet Talwalkar -
2019 Poster: Envy-Free Classification »
Maria-Florina Balcan · Travis Dick · Ritesh Noothigattu · Ariel Procaccia -
2019 Poster: Adaptive Gradient-Based Meta-Learning Methods »
Misha Khodak · Maria-Florina Balcan · Ameet Talwalkar -
2018 Poster: Model Agnostic Supervised Local Explanations »
Gregory Plumb · Denali Molitor · Ameet Talwalkar -
2018 Poster: Data-Driven Clustering via Parameterized Lloyd's Families »
Maria-Florina Balcan · Travis Dick · Colin White -
2018 Spotlight: Data-Driven Clustering via Parameterized Lloyd's Families »
Maria-Florina Balcan · Travis Dick · Colin White -
2017 : Invited Talk: Sample and Computationally Efficient Active Learning Algorithms »
Maria-Florina Balcan -
2017 Poster: Variable Importance Using Decision Trees »
Jalil Kazemitabar · Arash Amini · Adam Bloniarz · Ameet S Talwalkar -
2017 Poster: Federated Multi-Task Learning »
Virginia Smith · Chao-Kai Chiang · Maziar Sanjabi · Ameet S Talwalkar -
2017 Poster: Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions »
Maria-Florina Balcan · Hongyang Zhang -
2016 : Invited Talk: Paleo: A Performance Model for Deep Neural Networks (Ameet Talwalkar, UCLA) »
Ameet S Talwalkar -
2016 Poster: Noise-Tolerant Life-Long Matrix Completion via Adaptive Sampling »
Maria-Florina Balcan · Hongyang Zhang -
2016 Poster: Yggdrasil: An Optimized System for Training Deep Decision Trees at Scale »
Firas Abuzaid · Joseph K Bradley · Feynman Liang · Andrew Feng · Lee Yang · Matei Zaharia · Ameet S Talwalkar -
2016 Poster: Sample Complexity of Automated Mechanism Design »
Maria-Florina Balcan · Tuomas Sandholm · Ellen Vitercik -
2014 Workshop: Distributed Machine Learning and Matrix Computations »
Reza Zadeh · Ion Stoica · Ameet S Talwalkar -
2011 Workshop: Sparse Representation and Low-rank Approximation »
Ameet S Talwalkar · Lester W Mackey · Mehryar Mohri · Michael W Mahoney · Francis Bach · Mike Davies · Remi Gribonval · Guillaume R Obozinski -
2011 Poster: Divide-and-Conquer Matrix Factorization »
Lester W Mackey · Ameet S Talwalkar · Michael Jordan -
2010 Workshop: Low-rank Methods for Large-scale Machine Learning »
Arthur Gretton · Michael W Mahoney · Mehryar Mohri · Ameet S Talwalkar -
2009 Poster: Ensemble Nystrom Method »
Sanjiv Kumar · Mehryar Mohri · Ameet S Talwalkar