ICTS

Graph alignment is a generic high-dimensional statistical inference problem with many applications, ranging from social network data de-anonymization to separation of functional regions in cortical surfaces. The aim of this short course is to present several recent theoretical results on graph alignment when the graphs to be aligned come from a specific generative model, namely the correlated Erdös-Rényi random graph model. Specifically, we shall first present results on information-theoretic limits to feasibility of graph alignment: below some threshold, the observed graphs do not contain enough information for alignment to be feasible, while above that threshold, some algorithms are known to succeed at alignment, although in exponential time. We shall then present results on computational feasibility of alignment, describing a second threshold which determines when a family of ‘local’, polynomial-time algorithms succeed at alignment. Together, these results show a rich phenomenology for graph alignment, displaying an ‘impossible phase’, a ‘hard phase’ and an ‘easy phase’ for feasibility of the task.

Stein Variational Gradient Descent (SVGD) has emerged as a popular particle based sampling algorithm. While its infinite particle mean field limit is well understood, its finite particle behavior is not well understood. In this talk, I will introduce the Virtual Particle SVGD (VP-SVGD) which is computationally efficient and converges provably fast to the target in the finite particle regime, the first such algorith. The main idea is to employ unbiased stochastic approximation in the space of probability distribution and use this to track the evolution of KL-divergence to the target distribution. 

Many data processing problems can be cast as minimizing a convex functional over (a subset of) the space of signed measures. These includes problems as diverse as training two-layer neural networks, sparse spikes deconvolution, Wasserstein barycenters, and trajectory inference. In this mini-course I will present recent conceptual tools and theoretical guarantees pertaining to "particle methods". This is a class of approaches to solve such problems which are versatile and practical, where the unknown measure is parameterized as a sum of Dirac masses. We will cover fixed-support methods, conic particle methods, noisy gradient methods and discuss their link with Wasserstein geometry, and (generalized) Langevin dynamics for sampling. Concepts from Optimal Transport, Stochastic Differential Equations (SDEs) and Partial Differential Equations (PDEs) will be introduced and used throughout the course.

Matrix completion is the study of recovering an underlying matrix from a sparse subset of noisy observations. Traditionally, it is assumed entries of the matrix are “missing completely at random” (MCAR), i.e., each entry is revealed at random, independent of everything else, with uniform probability. This is likely unrealistic due to the presence of “latent confounders”, i.e., unobserved factors that determine both the entries of the underlying matrix and the missingness pattern in the observed matrix. For example, in the context of movie recommender systems—a canonical application for matrix completion—a user who vehemently dislikes horror films is unlikely to ever watch horror films. In general, these confounders yield “missing not at random” (MNAR) data, which can severely impact any inference procedure. We develop a formal causal model for matrix completion through the language of potential outcomes, and provide novel identification arguments for a variety of causal estimands of interest. We combine a nearest neighbors approach for matrix completion —popularly known as collaborative filtering—with the synthetic controls approach for panel data, to design a simple two-step algorithm, which we call “synthetic nearest neighbors” (SNN) to estimate these causal estimands. We prove entry-wise finite-sample consistency and asymptotic normality of the SNN estimator for matrix completion with MNAR data. 

Lastly, we show how algorithms for reinforcement learning, where the data is collected offline and there is potentially unobserved confounding in how actions are picked, can be effectively designed through the lens of causal tensor completion, an extension of matrix completion to higher dimensions.

Recently, the theory of infinite-width neural networks led to the first technology, muTransfer, for tuning enormous neural networks that are too expensive to train more than once. For example, this allowed us to tune the 6.7 billion parameter version of GPT-3 using only 7% of its pretraining compute budget, and with some asterisks, we get a performance comparable to the original GPT-3 model with twice the parameter count. In this talk, I will explain the core insight behind this theory. In fact, this is an instance of what I call the *Optimal Scaling Thesis*, which connects infinite-size limits for general notions of “size” to the optimal design of large models in practice, illustrating a way for theory to reliably guide the future of AI. I'll end with several concrete key mathematical research questions whose resolutions will have incredible impact on how practitioners scale up their NNs.

We present results on fitting manifolds to data where the standard deviation of the noise is large compared to the reach of the manifold being fit. This is joint work with Charles Fefferman, Sergei Ivanov and Matti Lassas.

In this talk, we discuss several contemporary aspects of risk-aware multi-armed bandits. First, we design and analyze Thompson sampling-style algorithms for mean-variance MAB and provide comprehensive regret analyses for Gaussian and Bernoulli bandits. Our algorithms achieve the best known regret bounds for mean-variance MABs and also attain the information-theoretic bounds in some parameter regimes. Second, we seek to identify the best arm under the fixed-confidence setup and under a stringent constraint that the variance of the chosen arm is strictly smaller than a given threshold. An algorithm VA-LUCB is developed and its sample complexity is shown to be characterized by a fundamental variance-aware hardness quantity H_{VA} . By proving an information-theoretic lower bound, we show that sample complexity of VA-LUCB is optimal up to a factor logarithmic in H_{VA}. Finally, we formulate a probably anytime-safe stochastic combinatorial semi-bandits problem in which the agent is given the option to select a subset of size at most K from a set of L ground items. Each item is associated with a certain mean reward as well as a variance that represents its risk. To mitigate the risk that the agent incurs, we require that with probability at least 1−δ, over the entire horizon of time T, each of the choices that the agent makes should contain items whose sum of variances does not exceed a certain variance budget.

Recently, the theory of infinite-width neural networks led to the first technology, muTransfer, for tuning enormous neural networks that are too expensive to train more than once. For example, this allowed us to tune the 6.7 billion parameter version of GPT-3 using only 7% of its pretraining compute budget, and with some asterisks, we get a performance comparable to the original GPT-3 model with twice the parameter count. In this talk, I will explain the core insight behind this theory. In fact, this is an instance of what I call the *Optimal Scaling Thesis*, which connects infinite-size limits for general notions of “size” to the optimal design of large models in practice, illustrating a way for theory to reliably guide the future of AI. I'll end with several concrete key mathematical research questions whose resolutions will have incredible impact on how practitioners scale up their NNs.