Improving Online Algorithms via ML Predictions

Abstract

In this work we study the problem of using machine-learned predictions to improve the performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.

arXiv commentConference version appeared in Neurips 2018

Cited by in corpus (32)

• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design
• Scheduling with Predictions and the Price of Misprediction
• Learning Space Partitions for Nearest Neighbor Search
• The Primal-Dual method for Learning Augmented Algorithms
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• (Learned) Frequency Estimation Algorithms under Zipfian Distribution
• A primer on model-guided exploration of fitness landscapes for biological sequence design
• Learning Augmented Energy Minimization via Speed Scaling
• Customizing ML Predictions for Online Algorithms
• Robustness and Consistency in Linear Quadratic Control with Untrusted Predictions
• The Supermarket Model with Known and Predicted Service Times
• Learning-Assisted Competitive Algorithms for Peak-Aware Energy Scheduling
• Learning-based Support Estimation in Sublinear Time
• Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions
• Pandora's Box with Correlations: Learning and Approximation
• Faster Matchings via Learned Duals
• Online Page Migration with ML Advice
• Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice
• Contextual Pandora's Box
• Learning-Augmented $k$-means Clustering
• Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
• Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
• SEH: Size Estimate Hedging for Single-Server Queues
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
• Adversarial Deep Learning for Online Resource Allocation
• Fair Allocation with Interval Scheduling Constraints
• Can Q-Learning be Improved with Advice?
• Online Virtual Machine Allocation with Predictions
• Mixing predictions for online metric algorithms
• Learning-Augmented Query Policies
• Online Primal-Dual Algorithms with Predictions for Packing Problems
• Metrical Task Systems with Online Machine Learned Advice