Stochastics and Statistics Seminar

Abstract:   In this talk, we are going to discuss a new polynomial-time algorithmic framework for inference problems, based on the celebrated Lenstra-Lenstra-Lovasz lattice basis reduction algorithm. Potentially surprisingly, this algorithmic framework is able to successfully bypass multiple suggested notions of “computational hardness for inference” for various noiseless settings. Such settings include 1) sparse regression, where there is Overlap Gap Property and low-degree methods fail, 2) phase retrieval where Approximate Message Passing fails and 3) Gaussian clustering where the SoS…

Abstract:   The prediction accuracy of machine learning methods is steadily increasing, but the calibration of their uncertainty predictions poses a significant challenge. Numerous works focus on obtaining well-calibrated predictive models, but less is known about reliably assessing model calibration. This limits our ability to know when algorithms for improving calibration have a real effect, and when their improvements are merely artifacts due to random noise in finite datasets. In this work, we consider the problem of detecting mis-calibration of…

Abstract: Many empirical questions concern target parameters selected through optimization. For example, researchers may be interested in the effectiveness of the best policy found in a randomized trial, or the best-performing investment strategy based on historical data. Such settings give rise to a winner's curse, where conventional estimates are biased and conventional confidence intervals are unreliable. This paper develops optimal confidence intervals and median-unbiased estimators that are valid conditional on the target selected and so overcome this winner's curse. If…

Abstract: Variational approximations provide an attractive computational alternative to MCMC-based strategies for approximating the posterior distribution in Bayesian inference. Despite their popularity in applications, supporting theoretical guarantees are limited, particularly in high-dimensional settings. In the first part of the talk, we will study bayesian inference in the context of a linear model with product priors, and derive sufficient conditions for the correctness (to leading order) of the naive mean-field approximation. To this end, we will utilize recent advances in the…

Abstract: We study the problem of certification: given queries to an n-variable boolean function f with certificate complexity k and an input x, output a size-k certificate for f's value on x. This abstractly models a problem of interest in explainable machine learning, where we think of f as a blackbox model that we seek to explain the predictions of. For monotone functions, classic algorithms of Valiant and Angluin accomplish this task with n queries to f. Our main result is…

Abstract: The development of CRISPR-based assays and small molecule screens holds the promise of engineering precise cell state transitions to move cells from one cell type to another or from a diseased state to a healthy state. The main bottleneck is the huge space of possible perturbations/interventions, where even with the breathtaking technological advances in single-cell biology it will never be possible to experimentally perturb all combinations of thousands of genes or compounds. This important biological problem calls for a…

Abstract:  Many new random matrix ensembles arise in learning and modern signal processing. As shown in recent studies, the spectral properties of these matrices help answer crucial questions regarding the training and generalization performance of neural networks, and the fundamental limits of high-dimensional signal recovery. As a result, there has been growing interest in precisely understanding the spectra and other asymptotic properties of these matrices. Unlike their classical counterparts, these new random matrices are often highly structured and are the…

Abstract: Under the current Swiss law, taxpayers can deduct charitable donations from their individual’s taxable income subject to a 20%-ceiling. This deductible ceiling was increased at the communal and cantonal level from a previous 5%-ceiling in 2009. The goal of the reform was boosting charitable giving to non-profit entities. However, the effects of this reform, and more generally of the existing Swiss system of tax deductions for charitable giving has never been empirically studied. The aim of this work is…

Abstract: This talk will cover recent work in our group developing and applying algorithms to simulate rare events in atmospheric science and other areas. I will review a rare event simulation scheme that biases model simulations toward the rare event of interest by preferentially duplicating simulations making progress toward the event and removing others. I will describe applications of this approach to rapid intensification of tropical cyclones and instability of Mercury's orbit with an emphasis on the elements of algorithm…

Abstract: Many existing literature on bandits and reinforcement learning assume a linear reward/value function, but what happens if the reward is non-linear? Two curious phenomena arise for non-linear bandits: first, in addition to the "learning phase" with a standard \Theta(\sqrt(T)) regret, there is an "initialization phase" with a fixed cost determined by the reward function; second, achieving the smallest cost of the initialization phase requires new learning algorithms other than traditional ones such as UCB. For a special family of…