IT-Forum

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

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

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

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

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

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
Venue: 
Registration required

ISL Colloquium presents "The Well Tempered Lasso"

Topic: 
The Well Tempered Lasso
Abstract / Description: 

We study the complexity of the entire regularization path for least squares regression with 1-norm penalty, known as the Lasso. Every regression parameter in the Lasso changes linearly as a function of the regularization value. The number of changes is regarded as the Lasso's complexity. Experimental results using exact path following exhibit polynomial complexity of the Lasso in the problem size. Alas, the path complexity of the Lasso on artificially designed regression problems is exponential. We use smoothed analysis as a mechanism for bridging the gap between worst case settings and the de facto low complexity. Our analysis assumes that the observed data has a tiny amount of intrinsic noise. We then prove that the Lasso's complexity is polynomial in the problem size. While building upon the seminal work of Spielman and Teng on smoothed complexity, our analysis is morally different as it is divorced from specific path following algorithms. We verify the validity of our analysis in experiments with both worst case settings and real datasets. The empirical results we obtain closely match our analysis.

Joint work with Prof. Yuanzhi Li (CMU).

Date and Time: 
Thursday, January 28, 2021 - 4:30pm

IT Forum presents "Towards Model Agnostic Robustness"

Topic: 
Towards Model Agnostic Robustness
Abstract / Description: 

It is now common practice to try and solve machine learning problems by starting with a complex existing model or architecture, and fine-tuning/adapting it to the task at hand. However, outliers, errors or even just sloppiness in training data often lead to drastic drops in performance.

We investigate a simple generic approach to correct for this, motivated by a classic statistical idea: trimmed loss. This advocates jointly (a) selecting which training samples to ignore, and (b) fitting a model on the remaining samples. As such this is computationally infeasible even for linear regression. We propose and study the natural iterative variant that alternates between these two steps (a) and (b) - each of which individually can be easily accomplished in pretty much any statistical setting. We also study the batch-SGD variant of this idea. We demonstrate both theoretically (for generalized linear models) and empirically (for moderate-sized neural network models) that this effectively recovers accuracy in the presence of bad training data.

This work is joint with Yanyao Shen and Vatsal Shah and appears in NeurIPS 2019, ICML 2019 and AISTATS 2020.

Date and Time: 
Thursday, October 29, 2020 - 4:30pm
Venue: 
Registration required

Pages

Subscribe to RSS - IT-Forum