Information Systems Lab (ISL) Colloquium

ISL Colloquium presents "Adaptive Experimental Design for Best Identification and Multiple Testing"

Topic: 
Scalable semidefinite programming
Abstract / Description: 

Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This talk describes a provably correct randomized algorithm for solving large, weakly constrained SDP problems by economizing on the storage and arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment problems. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over 10^14 entries.

This talk will highlight the ideas behind the algorithm in a streamlined setting. The insights include a careful problem formulation, design of a bespoke optimization method, use of randomized eigenvalue computations, and use of randomized sketching methods.

Joint work with Alp Yurtsever, Olivier Fercoq, Madeleine Udell, and Volkan Cevher. Based on arXiv 1912.02949 (Scalable SDP, SIMODS 2021) and other papers (SketchyCGM in AISTATS 2017, Nyström sketch in NeurIPS 2017).

Date and Time: 
Thursday, April 8, 2021 - 4:30pm

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

RL Forum Talk: Diffusion Asymptotics for Sequential Experiments

Topic: 
Diffusion Asymptotics for Sequential Experiments
Abstract / Description: 

I will discuss in this talk a new diffusion-asymptotic analysis for sequentially randomized experiments. Rather than taking sample size n to infinity while keeping the problem parameters fixed, we let the mean signal level scale to the order 1/\sqrt{n} so as to preserve the difficulty of the learning task as n gets large. In this regime, we show that the behavior of a class of methods for sequential experimentation converges to a diffusion limit. This connection enables us to make sharp performance predictions and obtain new insights on the behavior of Thompson sampling. Our diffusion asymptotics also help resolve a discrepancy between the Θ(log(n)) regret predicted by the fixed-parameter, large-sample asymptotics on the one hand, and the Θ(\sqrt{n}) regret from worst-case, finite-sample analysis on the other, suggesting that it is an appropriate asymptotic regime for understanding practical large-scale sequential experiments.

Date and Time: 
Tuesday, March 23, 2021 - 1:00pm to Wednesday, March 24, 2021 - 12:55pm

ISL Colloquium presents "Exploiting symmetries in Inference and Learning"

Topic: 
Exploiting symmetries in Inference and Learning
Abstract / Description: 

Symmetries play a crucial role in much of mathematics and physics. In this talk I will explore the role that symmetries are playing in machine learning. In particular I will discuss the concept of equivariance and apply it to neural networks. After the introduction I will discuss two newer works: first E(n) equivariant graph neural networks that are equivariant to both permutations of the nodes and global E(n) transformations of the node features. These models are ideal for predicting molecular properties in biology and chemistry and to model objects as point clouds in computer vision. Secondly I will show how invariance if probability densities result in very efficient deterministic mcmc samplers with better convergence behavior. We show that by modeling the sampler as a push-forward of the density according to an ODE, and by identifying a very large set of symmetries for an arbitrary density characterized divergence free vector fields, we can indeed design highly efficient samplers. Finally we extend these ideas to discrete sampling spaces, such as the Ising model.

Joint work with Kirill Neklyudov and Roberto Bondesan.

Date and Time: 
Thursday, March 4, 2021 - 9:00am to Friday, March 5, 2021 - 8:55am
Venue: 
Registration required

ISL Colloquium presents "Chasing the Long Tail: What Neural Networks Memorize and Why"

Topic: 
Chasing the Long Tail: What Neural Networks Memorize and Why
Abstract / Description: 

Deep learning algorithms that achieve state-of-the-art results on image and text recognition tasks tend to fit the entire training dataset (nearly) perfectly including mislabeled examples and outliers. This propensity to memorize seemingly useless data and the resulting large generalization gap have puzzled many practitioners and is not explained by existing theories of machine learning. We provide a simple conceptual explanation and a theoretical model demonstrating that memorization of outliers and mislabeled examples is necessary for achieving close-to-optimal generalization error when learning from long-tailed data distributions. Image and text data are known to follow such distributions and therefore our results establish a formal link between these empirical phenomena. We then demonstrate the utility of memorization and support our explanation empirically. These results rely on a new technique for efficiently estimating memorization and influence of training data points.

Based on a joint work with Chiyuan Zhang.

Date and Time: 
Thursday, February 25, 2021 - 4:30pm

ISL Colloquium presents "Enabling Fast and Robust Federated Learning"

Topic: 
Enabling Fast and Robust Federated Learning
Abstract / Description: 

In many large-scale machine learning applications, data is acquired and processed at the edge nodes of the network such as mobile devices, users' devices, and IoT sensors. Federated learning is a recent distributed learning paradigm according to which a model is trained over a set of edge devices. While federated learning can enable a variety of new applications, it faces major bottlenecks that severely limit its reliability and scalability including communications bottleneck as well as data and system's heterogeneity bottleneck. In this talk, we first focus on communication-efficient federated learning, and present FedPAQ, a communication-efficient and scalable Federated learning method with Periodic Averaging and Quantization. FedPAQ is provably near-optimal in the following sense. Under the problem setup of expected risk minimization with independent and identically distributed data points, when the loss function is strongly convex the proposed method converges to the optimal solution with near-optimal rate, and when the loss function is non-convex it finds a first-order stationary point. In the second part of the talk, we develop a robust federated learning algorithm that achieves strong performance against distribution shifts in users' samples. Throughout, we show several numerical results to empirically support our theoretical results.

Date and Time: 
Thursday, February 18, 2021 - 4:30pm

ISL Colloquium presents "Data, decisions, and dynamics"

Topic: 
Data, decisions, and dynamics
Abstract / Description: 

Consequential decisions compel individuals to react in response to the specifics of the decision rule. This individual-level response in aggregate can disrupt the statistical patterns that motivated the decision rule, leading to unforeseen consequences.

In this talk, I will discuss two ways to formalize dynamic decision making problems. One, called performative prediction, makes macro-level assumptions about the aggregate population response to a decision rule. The other, called strategic classification, follows microeconomic theory in modeling individuals as utility-maximizing agents with perfect information. We will see key results and limitations of either approach. Drawing on lessons from the microfoundations project in economics, I will outline a viable middleground between the two.

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

ISL Colloquium presents "End-to-end learning for computational microscopy"

Topic: 
End-to-end learning for computational microscopy
Abstract / Description: 

Computational imaging involves the joint design of imaging system hardware and software, optimizing across the entire pipeline from acquisition to reconstruction. Computers can replace bulky and expensive optics by solving computational inverse problems. This talk will describe end-to-end learning for development of new microscopes that use computational imaging to enable 3D fluorescence and phase measurement. Traditional model-based image reconstruction algorithms are based on large-scale nonlinear non-convex optimization; we combine these with unrolled neural networks to learn both the image reconstruction algorithm and the optimized data capture strategy.

Date and Time: 
Thursday, February 4, 2021 - 4:30pm

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

ISL Colloquium presents "Adaptive Experimental Design for Best Identification and Multiple Testing"

Topic: 
Adaptive Experimental Design for Best Identification and Multiple Testing
Abstract / Description: 

Adaptive experimental design (AED), or active learning, leverages already-collected data to guide future measurements, in a closed loop, to collect the most informative data for the learning problem at hand. In both theory and practice, AED can extract considerably richer insights than any measurement plan fixed in advance, using the same statistical budget. Unfortunately, the same mechanism of feedback that can aid an algorithm in collecting data can also mislead it: a data collection heuristic can become overconfident in an incorrect belief, then collect data based on that belief, yet give little indication to the practitioner that anything went wrong. Consequently, it is critical that AED algorithms are provably robust with transparent guarantees. In this talk I will present my group's recent work on near-optimal approaches to adaptive testing with false discovery control and the best-arm identification problem for linear and combinatorial bandits, and how these approaches relate to, and leverage, ideas from non-adaptive optimal linear experimental design.

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

Pages

Subscribe to RSS - Information Systems Lab (ISL) Colloquium