We consider the problem of online scheduling on a single machine to minimize unweighted and weighted flow time. The existing algorithms for these problems require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios. We present a competitive algorithm (the competitive ratio is a function of the distortion) for unweighted flow time that do not require knowledge of the distortion in advance. For the weighted flow time we present competitive algorithms but, in this case, we need to know (an upper bound on) the distortion in advance. This is joint work with Stefano Leonardi and Noam Touitou based on papers appear in STOC 21 and SODA 2022.

This talk will discuss a model for augmenting algorithms with useful predictions to improve algorithm performance for running time. The model ensures predictions are formally learnable and robust. Learnability guarantees that predictions can be efficiently constructed from past data. Robustness formally ensures a prediction is robust to modest changes in the problem input. This talk will discuss predictions that satisfy these properties and result in improved run times for matching algorithms.

In this talk we will consider the number of predictions used by a learning-augmented algorithm as a resource measure. Focusing on two problems---online learning in the regret setting and online caching in the competitive-ratio setting---we show that a sublinear number of predictions suffices to achieve non-trivial performance gains.

The bulk of the literature on online algorithms with ML advice focuses on a single (possibly noisy) predictor. But, in reality, multiple ML models are often used to make future predictions for the same application, and their predictions/advice can differ from one another. In this case, how should an online algorithm choose among these different suggestions? This talk will focus on models, problems, and algorithms to address this question. The talk will include some recent results with Keerti Anand, Rong Ge, and Amit Kumar, and briefly touch upon older results with Sreenivas Gollapudi.

The design of learning-augmented online algorithms is a new and active research area. The goal is to understand how to best incorporate predictions of the future provided e.g. by machine learning algorithms that rarely come with guarantees on their accuracy. In the absence of guarantees, the difficulty in the design of such learning-augmented algorithms is to find a good balance: on the one hand, following blindly the prediction might lead to a very bad solution if the prediction is misleading. On the other hand, if the algorithm does not trust the prediction at all, it will simply never benefit from an excellent prediction. An explosion of recent results solve this issue by designing smart algorithms that exploit the problem structure to achieve a good trade-off between these two cases. In this talk, we will discuss this emerging line of work. In particular, we will show how to unify and generalize some of these results by extending the powerful primal-dual method for online algorithms to the learning augmented setting. This is joint work with Etienne Bamas and Andreas Maggiori.

Distribution testing problems often require an incredible number of samples. However, when useful oracles answering various questions about the distributions are available, dramatically fewer samples are needed. In this talk, I will give a survey of such results, including scenarios in which approximate oracles are learned from the data.

We present recent results on prophet inequalities for matching markets and two-sided mechanism design that provide near optimal approximations when limited information in the form of a single sample from each prior distribution is available.

We present Sparse Numerical Array-Based Range Filters (SNARF), a learned range filter that efficiently supports range queries for numerical data. SNARF creates a model of the data distribution to map the keys into a bit array which is stored in a compressed form. The model along with the compressed bit array which constitutes SNARF are used to answer membership queries. We evaluate SNARF on multiple synthetic and real-world datasets as a stand-alone filter and by integrating it into RocksDB. For range queries, SNARF provides up to 50x better false positive rate than state-of-the-art range filters, such as SuRF and Rosetta, with the same space usage. We also evaluate SNARF in RocksDB as a filter replacement for filtering requests before they access on-disk data structures. For RocksDB, SNARF can improve the execution time of the system up to 10x compared to SuRF and Rosetta for certain read-only workloads.

Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree search algorithm used to find optimal solutions. In this talk, we provide the first sample complexity guarantees for learning high-performing cut-selection policies tailored to the instance distribution at hand using samples. We then develop a general abstraction of tree search that captures key components such as node selection and variable selection. For this abstraction, we bound the sample complexity of learning a good policy for building the search tree.This talk is based on joint work with Nina Balcan, Siddharth Prasad, and Tuomas Sandholm.

We consider the problem of scheduling to minimize mean response time in a queueing system with Poisson arrivals and i.i.d. sizes (processing times), where predictions of size are known to the scheduler. We consider the setting of bounded multiplicative prediction error. We evaluate a policy by its approximation error, the ratio between its mean response time, and that of the optimal policy when sizes are exactly known. We present a simple, novel scheduling policy which achieves both consistency and graceful degradation. This is joint work with Ziv Scully and Michael Mitzenmacher based on a paper in ITCS 2022.