IT-Forum

IT-Forum: "Between tractable and intractable problems in reinforcement learning"

Topic: 
Between tractable and intractable problems in reinforcement learning
Abstract / Description: 

Markov decision processes (MDPs) capture some of the most important aspects of decision making under uncertainty and as such they are at the heart of many efforts to decision making under uncertainty. However, MDPs are "flat" with no structure and as such, planning and learning in MDPs with multidimensional state spaces, common in applications, is provably intractable. Yet, reinforcement learning methods have been quite successful in providing strong solutions to some of these seemingly intractable problems. In this talk I will present my view of how to think about these successes by presenting a framework where the key idea is to give algorithms hints that can create backdoors to crack otherwise intractable problems. The talk will then dive into categorizing hints based on whether they can indeed succeed at doing this for the special case when the hints are given in the form of constraints on how value functions look like in the context of planning with generative models, also known as simulation optimization. As we shall see, seemingly minor differences between hints can cause some hints to work, while others fail.

Date and Time: 
Thursday, June 10, 2021 - 4:30pm

IT-Forum: "The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions"

Topic: 
The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions
Abstract / Description: 

The Gittins scheduling policy minimizes the mean response in the single-server M/G/1 queue in a wide variety of settings. Most famously, Gittins is optimal when preemption is allowed and service requirements are unknown but drawn from a known distribution. Gittins is also optimal much more generally, adapting to any amount of available information and any preemption restrictions. However, scheduling to minimize mean response time in a multiserver setting, specifically the central-queue M/G/k, is a much more difficult problem.

In this work we give the first general analysis of Gittins in the M/G/k. Specifically, we show that under extremely general conditions, Gittins's mean response time in the M/G/k is at most its mean response time in the M/G/1 plus a term that grows logarithmically in the heavy-traffic limit, namely as the system load approaches capacity. A consequence of this result is that Gittins is optimal in the heavy-traffic M/G/k if the service requirement distribution has finite (2 + ε)th moment for any ε > 0. This is the most general result on minimizing mean response time in the M/G/k to date.

To prove our results, we combine properties of the Gittins policy and Palm calculus in a novel way. Notably, our technique overcomes the limitations of tagged job methods that were used in prior scheduling analyses.

Joint work with Isaac Grosof and Mor Harchol-Balter. Paper link: https://ziv.codes/publications/#the-gittins-policy-is-nearly-optimal-in-the-mgk-under-extremely-general-conditions

Date and Time: 
Friday, May 21, 2021 - 1:00pm to Saturday, May 22, 2021 - 12:55pm

Algorithms & Friends Seminar presents "Modeling the Heterogeneity in COVID-19’s Reproductive Number and Its Impact on Predictive Scenarios"

Topic: 
Modeling the Heterogeneity in COVID-19’s Reproductive Number and Its Impact on Predictive Scenarios
Abstract / Description: 

The correct evaluation of the reproductive number R for COVID-19 — which characterizes the average number of secondary cases generated by each typical primary case— is central in the quantification of the potential scope of the pandemic and the selection of an appropriate course of action. In most models, R is modelled as a universal constant for the virus across outbreak clusters and individuals— effectively averaging out the inherent variability of the transmission process due to varying individual contact rates, population densities, demographics, or temporal factors amongst many. Yet, due to the exponential nature of epidemic growth, the error due to this simplification can be rapidly amplified and lead to inaccurate predictions and/or risk evaluation. From the statistical modeling perspective, the magnitude of the impact of this averaging remains an open question: how can this intrinsic variability be percolated into epidemic models, and how can its impact on uncertainty quantification and predictive scenarios be better quantified? In this talk, we discuss a Bayesian perspective on this question, creating a bridge between the agent-based and compartmental approaches commonly used in the literature. After deriving a Bayesian model that captures at scale the heterogeneity of a population and environmental conditions, we simulate the spread of the epidemic as well as the impact of different social distancing strategies, and highlight the strong impact of this added variability on the reported results. We base our discussion on both synthetic experiments — thereby quantifying of the reliability and the magnitude of the effects — and real COVID-19 data.


 

Hosted by the Algorithms and Friends Seminar

Date and Time: 
Monday, April 5, 2021 - 12:00pm to Tuesday, April 6, 2021 - 11:55am

ISL Colloquium presents "Finding Global Minima via Kernel Approximations"

Topic: 
Finding Global Minima via Kernel Approximations
Abstract / Description: 

We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite sums of square smooth functions and has strong links with polynomial sum-of-squares hierarchies. Leveraging recent representation properties of reproducing kernel Hilbert spaces, the infinite-dimensional optimization problem can be solved by subsampling in time polynomial in the number of function evaluations, and with theoretical guarantees on the obtained minimum. (Joint work with Alessandro Rudi and Ulysse Marteau-Ferey).

Date and Time: 
Thursday, April 1, 2021 - 10:00am to Friday, April 2, 2021 - 9:55am

IT-Forum presents "Approximating cross-validation: guarantees for model assessment and selection"

Topic: 
Approximating cross-validation: guarantees for model assessment and selection
Abstract / Description: 

Cross-validation (CV) is the de facto standard for selecting accurate predictive models and assessing model performance. However, CV suffers from a need to repeatedly refit a learning procedure on a large number of training datasets. To reduce the computational burden, a number of works have introduced approximate CV procedures that simultaneously reduce runtime and provide model assessments comparable to CV when the prediction problem is sufficiently smooth. An open question however is whether these procedures are suitable for model selection. In this talk, I'll describe (i) broad conditions under which the model selection performance of approximate CV nearly matches that of CV, (ii) examples of prediction problems where approximate CV selection fails to mimic CV selection, and (iii) an extension of these results and the approximate CV framework more broadly to non-smooth prediction problems like L1-regularized empirical risk minimization.

Date and Time: 
Thursday, March 18, 2021 - 4:30pm
Venue: 
Zoom: register to receive ID

IT Forum presents "Robust Learning from Batches – The Best Things in Life are (Almost) Free"

Topic: 
Robust Learning from Batches – The Best Things in Life are (Almost) Free
Abstract / Description: 

In many applications, including natural language processing, sensor networks, collaborative filtering, and federated learning, data are collected in batches, some potentially corrupt, biased, or even adversarial. Learning algorithms for this setting have therefore garnered considerable recent attention. We develop a general framework for robust learning from batches, and determine the least number of samples required for robust density estimation and classification over both discrete and continuous domains. Perhaps surprisingly, we show that robust learning can be achieved with essentially the same number of samples as required for genuine data. For the important problems of learning discrete and piecewise-polynomial densities, and of interval-based classification, we achieve these limits with polynomial-time algorithms.

Based on joint work with Ayush Jain.

Date and Time: 
Thursday, March 11, 2021 - 4:30pm

Algorithms & Friends Seminar presents "How fast do algorithms improve?"

Topic: 
How fast do algorithms improve?
Abstract / Description: 

Algorithms are one of the fundamental building blocks of computing. But current evidence about how fast algorithms improve is anecdotal, using small numbers of case studies to extrapolate. In this work, we gather data from 57 textbooks and more than 1,137 research papers to present the first systematic view of algorithm progress ever assembled. There is enormous variation. Around half of all algorithm families experience little or no improvement. At the other extreme, 13% experience transformative improvements, radically changing how and where they can be used. Overall, we find that, for moderate-sized problems, 30% to 45% of algorithmic families had improvements comparable or greater than those that users experienced from Moore's Law and other hardware advances.

Joint work with Yash M. Sherry.

Date and Time: 
Monday, February 22, 2021 - 12:00pm to Tuesday, February 23, 2021 - 11:55am

IT Forum presents "Distribution-Free, Risk-Controlling Prediction Sets"

Topic: 
Distribution-Free, Risk-Controlling Prediction Sets
Abstract / Description: 

To communicate instance-wise uncertainty for prediction tasks, we show how to generate set-valued predictions for black-box predictors that control the expected loss on future test points at a user-specified level. Our approach provides explicit finite-sample guarantees for any dataset by using a holdout set to calibrate the size of the prediction sets. This framework enables simple, distribution-free, rigorous error control for many tasks, and we demonstrate it in five large-scale machine learning problems: (1) classification problems where some mistakes are more costly than others; (2) multi-label classification, where each observation has multiple associated labels; (3) classification problems where the labels have a hierarchical structure; (4) image segmentation, where we wish to predict a set of pixels containing an object of interest; and (5) protein structure prediction.

Date and Time: 
Friday, February 19, 2021 - 1:00pm to Saturday, February 20, 2021 - 12:55pm

IT Forum presents "Scaling Wasserstein distances to high dimensions via smoothing"

Topic: 
Scaling Wasserstein distances to high dimensions via smoothing
Abstract / Description: 

Wasserstein distances has recently seen a surge of applications in statistics and machine learning. This stems from many advantageous properties they possess, such as metric structure (they metrize weak convergence), robustness to support mismatch, compatibility to gradient-based optimization, and rich geometric properties. In practice, we rarely have access to the actual distribution and only get data from it, which necessitates estimating the distance from samples. A central issue is that such estimators suffer from the curse of dimensionality: their empirical convergence rate scales as n^{-1/d} for d-dimensional distributions. This rate deteriorates exponentially fast with dimension, making it impossible to obtain meaningful accuracy guarantees, considering the dimensionality of real-world data.

This talk will present a novel framework of smooth Wasserstein distances, that inherits the properties of their classic counterparts while alleviating the empirical curse of dimensionality. Specifically, we will show that the empirical approximation error of the smooth distance decays as n^{-1/2}, in all dimensions. For the special case of the smooth 1-Wasserstein distance, we will also derive a high-dimensional limit distribution, further highlighting the favorable statistical behavior of the smooth framework. Applications to implicit generative modeling will be considered, leveraging the statistical efficiency results to establish n^{-1/2} generalization bounds in any dimension.

Date and Time: 
Friday, February 12, 2021 - 1:00pm to Saturday, February 13, 2021 - 12:55pm

Algorithms & Friends Seminar presents "A New Approach for Fighting Infectious Disease, Combining Game Theory and Network Theory"

Topic: 
A New Approach for Fighting Infectious Disease, Combining Game Theory and Network Theory
Abstract / Description: 

There is a categorically new way to fight infectious disease, which could have a significant impact on the COVID pandemic now. Its origins come from game theory and computer science. It works against every COVID variant, and would play a key role in mopping up vaccine-resistant infections to block COVID's evolution. It's an app which is fundamentally different from every other app (and which resolves deep flaws in "contact tracing apps"). Functionally, it gives you an anonymous radar that tells you how "far" away COVID has just struck. "Far" is measured by counting physical relationships (https://novid.org, https://youtu.be/EIU-6FvwikQ). The simple idea flips the incentives. Previous approaches were about controlling you, preemptively removing you from society if you were suspected of being infected. This new tool lets you see incoming disease to defend yourself just in time. This uniquely aligns incentives so that even if everyone in a democratic society does what is best for themselves, they end up doing what is best for the whole.

Date and Time: 
Monday, February 8, 2021 - 12:00pm to Tuesday, February 9, 2021 - 11:55am
Venue: 
Registration required

Pages

Subscribe to RSS - IT-Forum