Information Systems Lab (ISL) Colloquium

ISL Colloquium presents "Demystifying the Efficiency of Reinforcement Learning: Two Recent Stories"

Topic: 
Demystifying the Efficiency of Reinforcement Learning: Two Recent Stories
Abstract / Description: 

Reinforcement learning (RL), which is frequently modeled as sequential learning and decision making in the face of uncertainty, is garnering growing interest in recent years due to its remarkable success in practice. In contemporary RL applications, it is increasingly more common to encounter environments with prohibitively large state and action space, thus imposing stringent requirements on the sample and computational efficiency of the RL algorithms in use. Despite the empirical success, however, the theoretical underpinnings for many popular RL algorithms remain highly inadequate even for the tabular setting.

In this talk, we present two vignettes regarding the effectiveness of RL algorithms. The first vignette demonstrates that a perturbed model-based RL approach is minimax optimal under a generative model, without suffering from a sample size barrier that was present in all past work. The second vignette covers policy optimization in reinforcement learning. On the one hand, we demonstrate that the popular softmax policy gradient method can take exponential time to converge; on the other hand, employing natural policy gradients and enforcing entropy regularization provably achieve fast global convergence. These results cover two distinctive RL paradigms, and might shed light on the efficacy of these algorithms in more complicated scenarios.

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

Reinforcement Learning Forum Talk: Provable Model-based Nonlinear Bandit and Reinforcement Learning

Topic: 
Provable Model-based Nonlinear Bandit and Reinforcement Learning
Abstract / Description: 

Deep model-based reinforcement learning methods have achieved state-of-the-art sample efficiency but we lack a theoretical understanding of them. This talk will first show that convergence to a global maximum requires an exponential number of samples even for a one-layer neural net bandit problem, which is strictly easier than RL. Therefore, we propose to study convergence to local maxima. For both nonlinear bandit and RL, I will present a model-based algorithm, Virtual Ascent with Online Model Learner (ViOL), which provably converges to a local maximum with sample complexity that only depends on the sequential Rademacher complexity of the model class. Our results imply novel global or local regret bounds on several concrete settings such as linear bandit with finite or sparse model class, and two-layer neural net bandit.

Paper: https://arxiv.org/pdf/2102.04168.pdf


Details available at RL site, link below

 

Date and Time: 
Thursday, April 15, 2021 - 2:30pm

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

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

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
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

Pages

Subscribe to RSS - Information Systems Lab (ISL) Colloquium