Timezone: »
Poster
Online Algorithms with Multiple Predictions
Keerti Anand · Rong Ge · Amit Kumar · Debmalya Panigrahi
This paper studies online algorithms augmented with {\em multiple} machine-learned predictions. We give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the {\em best} solution obtained from the predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting.
Author Information
Keerti Anand (Duke University)
Rong Ge (Duke University)
Amit Kumar (IIT Delhi)
Debmalya Panigrahi (Duke University)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Spotlight: Online Algorithms with Multiple Predictions »
Thu. Jul 21st 02:40 -- 02:45 PM Room Room 310
More from the Same Authors
-
2023 : The Role of Linguistic Priors in Measuring Compositional Generalization of Vision-language Models »
Chenwei Wu · Li Li · Stefano Ermon · Patrick Haffner · Rong Ge · Zaiwei Zhang -
2023 Poster: Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regression »
Mo Zhou · Rong Ge -
2023 Poster: Hiding Data Helps: On the Benefits of Masking for Sparse Coding »
Muthu Chidambaram · Chenwei Wu · Yu Cheng · Rong Ge -
2023 Poster: Provably Learning Diverse Features in Multi-View Data with Midpoint Mixup »
Muthu Chidambaram · Xiang Wang · Chenwei Wu · Rong Ge -
2022 Poster: Extracting Latent State Representations with Linear Dynamics from Rich Observations »
Abraham Frandsen · Rong Ge · Holden Lee -
2022 Spotlight: Extracting Latent State Representations with Linear Dynamics from Rich Observations »
Abraham Frandsen · Rong Ge · Holden Lee -
2021 Poster: Finding k in Latent $k-$ polytope »
Chiranjib Bhattacharyya · Ravindran Kannan · Amit Kumar -
2021 Spotlight: Finding k in Latent $k-$ polytope »
Chiranjib Bhattacharyya · Ravindran Kannan · Amit Kumar -
2021 Poster: Guarantees for Tuning the Step Size using a Learning-to-Learn Approach »
Xiang Wang · Shuai Yuan · Chenwei Wu · Rong Ge -
2021 Spotlight: Guarantees for Tuning the Step Size using a Learning-to-Learn Approach »
Xiang Wang · Shuai Yuan · Chenwei Wu · Rong Ge -
2020 Poster: High-dimensional Robust Mean Estimation via Gradient Descent »
Yu Cheng · Ilias Diakonikolas · Rong Ge · Mahdi Soltanolkotabi -
2020 Poster: Learning Opinions in Social Networks »
Vincent Conitzer · Debmalya Panigrahi · Hanrui Zhang -
2020 Poster: Customizing ML Predictions for Online Algorithms »
Keerti Anand · Rong Ge · Debmalya Panigrahi -
2019 Poster: Online Algorithms for Rent-Or-Buy with Expert Advice »
Sreenivas Gollapudi · Debmalya Panigrahi -
2019 Oral: Online Algorithms for Rent-Or-Buy with Expert Advice »
Sreenivas Gollapudi · Debmalya Panigrahi -
2018 Poster: Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator »
Maryam Fazel · Rong Ge · Sham Kakade · Mehran Mesbahi -
2018 Oral: Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator »
Maryam Fazel · Rong Ge · Sham Kakade · Mehran Mesbahi -
2018 Poster: Stronger Generalization Bounds for Deep Nets via a Compression Approach »
Sanjeev Arora · Rong Ge · Behnam Neyshabur · Yi Zhang -
2018 Oral: Stronger Generalization Bounds for Deep Nets via a Compression Approach »
Sanjeev Arora · Rong Ge · Behnam Neyshabur · Yi Zhang -
2017 Poster: How to Escape Saddle Points Efficiently »
Chi Jin · Rong Ge · Praneeth Netrapalli · Sham Kakade · Michael Jordan -
2017 Talk: How to Escape Saddle Points Efficiently »
Chi Jin · Rong Ge · Praneeth Netrapalli · Sham Kakade · Michael Jordan -
2017 Poster: No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis »
Rong Ge · Chi Jin · Yi Zheng -
2017 Poster: Generalization and Equilibrium in Generative Adversarial Nets (GANs) »
Sanjeev Arora · Rong Ge · Yingyu Liang · Tengyu Ma · Yi Zhang -
2017 Talk: No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis »
Rong Ge · Chi Jin · Yi Zheng -
2017 Talk: Generalization and Equilibrium in Generative Adversarial Nets (GANs) »
Sanjeev Arora · Rong Ge · Yingyu Liang · Tengyu Ma · Yi Zhang