The Mathematics of Machine Learning Workshop

Abstract:

A recent line of work has analyzed the properties of deep learning models through the lens of Random Features (RF) and the Neural Tangent Kernel (NTK). In this talk, I will show how concentration bounds on RF and NTK maps provide insights on (i) the optimization of the network via gradient descent, (ii) its adversarial robustness, and (iii) the success of attention-based architectures, such as transformers. I will start by proving tight bounds on the smallest eigenvalue of the NTK for deep neural networks with minimum over- parameterization. This implies that the network optimized by gradient descent interpolates the training dataset (i.e., reaches 0 training loss), as soon as the number of parameters is information-theoretically optimal. Next, I will focus on the robustness of the interpolating solution. A thought-provoking

paper by Bubeck and Sellke has proposed a “universal law of robustness”: interpolating smoothly the data necessarily requires many more parameters than simple memorization. By providing sharp bounds on RF and NTK models, I will show that, while some random feature models cannot be robust (regardless of the over-parameterization), NTK features are able to saturate the universal law of robustness, thus addressing a conjecture by Bubeck, Li and Nagaraj. Finally, I will consider attention-based architectures, showing that random attention features are sensitive to a change of a single word in the context, as expected from a model suitable for NLP tasks. In contrast, the sensitivity of random features decays with the length of the context. This property translates into generalization bounds: due to their low word sensitivity, random features provably cannot learn to distinguish between two sentences that differ only in a single word. In contrast, due to their high word sensitivity, random attention features have higher generalization capabilities.

Abstract:

We revisit the fundamental problem of learning with distribution shift, in which a learner is given labeled samples from training distribution D, unlabeled samples from test distribution D′ and is asked to output a classifier with low test error. The standard approach in this setting is to bound the loss of a classifier in terms of some notion of distance between D and D′. These distances, however, seem difficult to compute and do not lead to efficient algorithms.

We depart from this paradigm and define a new model called testable learning with distribution shift (TDS learning), where we can obtain provably efficient algorithms for certifying the performance of a classifier on a test distribution. In this model, a learner outputs a classifier with low test error whenever samples from D and D′ pass an associated test; moreover, the test must accept if the marginal of D equals the marginal of D′. We give several positive results for learning well-studied concept classes such as halfspaces, intersections of halfspaces, and decision trees. Prior to our work, no efficient algorithms for these basic cases were known without strong assumptions on D′.

Bio:

Adam Klivans is a professor of computer science and director of the NSF AI Institute for Foundations of Machine Learning (IFML). He also leads the UT-Austin Machine Learning Lab. His research interests include algorithms for supervised learning and AI for protein design.

Abstract:

Robustness to changes in data is one of the main challenges faced by sequential machine learning and decision-making algorithms. Yet, most efficient and highly optimized deployed algorithms today were designed to work well on fixed data sets and ultimately fail when data evolves in unpredictable or adversarial ways. It is even more concerning that, for most fundamental problems in machine learning and optimization, providing any performance guarantees that do not completely diminish in the presence of all-powerful adversaries is impossible. In this talk, we will explore the smoothed analysis perspective on adaptive adversaries in machine learning and optimization, which goes beyond the worst-case scenario. We will examine both information theoretical and computational perspectives and present general-purpose techniques that provide strong robustness guarantees in practical domains for a wide range of applications, such as online learning, differential privacy, discrepancy theory, sequential probability assignment, equilibrium finding, and learning-augmented algorithm design. Our conclusion is that even small perturbations to worst-case adaptive adversaries can make learning in their presence as easy as learning over a fixed data set.

Bio:

Nika Haghtalab is an Assistant Professor in the Department of Electrical Engineering and Computer Sciences at UC Berkeley. She works broadly on the theoretical aspects of machine learning and algorithmic economics. Prof. Haghtalab’s work builds theoretical foundations for ensuring both the performance of learning algorithms in presence of everyday economic forces and the integrity of social and economic forces that are born out of the use of machine learning systems. Among her honors are Sloan fellowship, NSF CAREER award, Schmidt Sciences AI2050 award, the CMU School of Computer Science Dissertation Award, SIGecom Dissertation Honorable Mention, and NeurIPS and ICAPS outstanding paper awards.

Abstract:

Causal inference traditionally involves analyzing tabular data where variables like treatment, outcome, covariates, and colliders are manually labeled by humans. However, many complex causal inference problems rely on unstructured data sources such as images, text and videos that depict overall situations. These causal problems require a crucial first step - extracting the high-level latent causal factors from the low-level unstructured data inputs, a task known as "causal representation learning."

In this talk, we explore how to identify latent causal factors from unstructured data, whether from passive observations, interventional experiments, or multi-domain datasets. While latent factors are classically uncovered by leveraging their statistical independence, causal representation learning grapples with a thornier challenge: the latent causal factors are often correlated, causally connected, or arbitrarily dependent.

Our key observation is that, despite correlations, the causal connections (or the lack of) among factors leave geometric signatures in the latent factors' support - the ranges of values each can take. Leveraging these signatures, we show that observational data alone can identify the latent factors up to coordinate transformations if they bear no causal links. When causal connections do exist, interventional data can provide geometric clues sufficient for identification. In the most general case of arbitrary dependencies, multi-domain data can separate stable factors from unstable ones. Taken together, these results showcase the unique power of geometric signatures in causal representation learning.

This is joint work with Kartik Ahuja, Yoshua Bengio, Michael Jordan, Divyat Mahajan, and Amin Mansouri.

[1] https://arxiv.org/abs/2109.03795
[2] https://arxiv.org/abs/2209.11924
[3] https://arxiv.org/abs/2310.02854

Bio:

Yixin Wang is an assistant professor of statistics at the University of Michigan. She works in the fields of Bayesian statistics, machine learning, and causal inference. Previously, she was a postdoctoral researcher with Professor Michael Jordan at the University of California, Berkeley. She completed her PhD in statistics at Columbia, advised by Professor David Blei, and her undergraduate studies in mathematics and computer science at the Hong Kong University of Science and Technology. Her research has been recognized by the j-ISBA Blackwell-Rosenbluth Award, ICSA Conference Young Researcher Award, ISBA Savage Award Honorable Mention, ACIC Tom Ten Have Award Honorable Mention, and INFORMS data mining and COPA best paper awards.

Abstract:

Machine learning provides an invaluable toolbox for natural sciences, but it also comes with many open questions that theoretical branches of natural sciences can investigate and tackle. This talk will describe some recent trends and progress in the second direction. We will discuss how diffusion or flow-based generative models sample or fail to sample challenging probability distributions. We will present a toy model of dot-product attention that presents a phase transition between positional and semantic learning. We will also revisit some classical methods for estimating uncertainty and their status in the context of modern over-parametrized neural networks.

Bio:

Lenka Zdeborová is a professor of physics and of computer science at École Polytechnique Fédérale de Lausanne in Switzerland, where she leads the Statistical Physics of Computation Laboratory. Her expertise is in applications of concepts from statistical physics, such as advanced mean field methods, replica method and related message-passing algorithms, to problems in machine learning, signal processing, inference and optimization. She has said that she “enjoys erasing the boundaries between theoretical physics, mathematics and computer science.”

Zdeborová received a Ph.D. in physics from University Paris-Sud and from Charles University in Prague in 2008. She spent two years in the Los Alamos National Laboratory as the Director's Postdoctoral Fellow; she then spent ten years as a researcher at Centre national de la recherche scientifique (CNRS) working in the Institute of Theoretical Physics in CEA Saclay, France. She served as an editorial board member for Journal of Physics A, Physical Review E, Physical Review X, SIMODS, Machine Learning: Science and Technology, and Information and Inference.

Her honors include the CNRS bronze medal in 2014; the Philippe Meyer prize in theoretical physics in 2016; the Irène Joliot-Curie prize in 2018; and the Gibbs lectureship of AMS and the Neuron Fund award in 2021.

Abstract:

Modern machine learning often relies on overparameterized models, typically trained to overfit the data. Recent studies have suggested that such overfitting can be "benign," leading to estimators with strong generalization performance. In this talk, we further examine the consequences of overparameterization under distribution shifts and present the following findings:

1. For adversarially perturbed data, benign overfitting can result in models that lack adversarial robustness, even when the true underlying model is robust.

2. On the other hand, when test data are perturbed non-adversarially but exhibit a distribution shift from the training data, overparameterization proves advantageous. As the model size increases, the out-of-distribution performance also improves. We support our theoretical results with experimental evidence.

Abstract:

In this tutorial we will consider the design of an active learning agent that decides which experiments to perform sequentially. We formulate the learning task in the multi-armed bandit setting and highlight the distinction between reward maximisation and statistical testing. We then develop mathematical tools and solve three classic learning tasks: regret minimization, best arm identification with fixed confidence and best arm identification with fixed budget. We finally show how to scale up to instance-optimal learning for more advanced tasks including multi-objective optimization.

Bio:

Wouter Koolen is a professor of mathematical machine learning at Twente University and a senior researcher at the Centrum Wiskunde & Informatica Amsterdam. His specialties include full information online learning and bandits, statistical testing and saddle point computation.

Abstract:

We discuss an approach to estimate aggregation and adaptive estimation based upon (nearly optimal) testing of convex hypotheses. The proposed adaptive routines generalize upon now-classical Goldenshluger-Lepski adaptation schemes, and, in the situation where the observations stem from simple observation schemes (i.e., have Gaussian, discrete and Poisson distribution) and where the set of unknown signals is a finite union of convex and compact sets, attain nearly optimal performance.

As an illustration, we consider application of the proposed estimates to the problem of recovery of unknown signal known to belong to a union of ellitopes in Gaussian observation scheme. The corresponding numerical routines can be implemented efficiently when the number of sets in the union is “not very large.” We illustrate “practical performance” of the method in an example of estimation in the single-index model.

Bio:

Anatoli Juditsky received the M.S. in Electrical Engineering in 1985 from the Moscow Institute of Physics and Technology and the Ph.D. in 1989 from the Institute of Control Sci., Moscow, USSR. Since 1999 he is Professor at the Department of Mathematics and Informatics (IM2AG) of the University of Grenoble Alps, France; he held a research position at INRIA-IRISA, Rennes, in 1991--1996, and then at INRIA, Grenoble, in 1996--1999. His current research interests include stochastic and large-scale convex optimization, statistical theory and their applications.​

Abstract:

The mean-field Langevin dynamics (MFLD) is a nonlinear generalization of the gradient Langevin dynamics (GLD) that minimizes an entropy regularized convex function defined on the space of probability distributions, and it naturally arises from the optimization of two-layer neural networks via (noisy) gradient descent. In this talk, I will present the convergence analysis of MFLD and explain how the convergence of MFLD is characterized by the log-Sobolev inequality of the so-called proximal Gibbs measure corresponding to the current solution. Moreover, I will provide a general framework to prove a uniform-in-time propagation of chaos for MFLD that takes into account the errors due to finite-particle approximation, time-discretization, and stochastic gradient approximation. In the latter half, I will discuss the generalization error analysis of neural networks trained by MFLD. Thanks to its feature learning ability of neural networks, we can show that neural networks achieve better statistical properties than kernel methods in several problem settings. Finally, we also present recent developments of optimizing mean field neural networks for non-convex objectives appearing in reinforcement learning and in-context learning.

Abstract:

TBD

Bio:

Jason Lee is an associate professor in Electrical Engineering and Computer Science (secondary) at Princeton University. Prior to that, he was in the Data Science and Operations department at the University of Southern California and a postdoctoral researcher at UC Berkeley working with Michael I. Jordan. Jason received his PhD at Stanford University advised by Trevor Hastie and Jonathan Taylor. His research interests are in the theory of machine learning, optimization, and statistics. Lately, he has worked on the foundations of deep learning, representation learning, and reinforcement learning. He has received the Samsung AI Researcher of the Year Award, NSF Career Award, ONR Young Investigator Award in Mathematical Data Science, Sloan Research Fellowship, NeurIPS Best Student Paper Award and Finalist for the Best Paper Prize for Young Researchers in Continuous Optimization.

Abstract:

A fundamental causal modelling task is to predict the effect of an intervention (or treatment) on an outcome, given context/covariates. Examples include predicting the effect of a medical treatment on patient health given patient symptoms and demographic information, or predicting the effect of ticket pricing on airline sales given seasonal fluctuations in demand. The problem becomes especially challenging when the treatment and context are complex (for instance, "treatment" might be a web ad design or a radiotherapy plan), and when only observational data is available (i.e., we have access to historical data, but cannot intervene ourselves). The challenge is greater still when the covariates are not observed, and constitute a hidden source of confounding.

I will give an overview of some practical tools and methods for estimating causal effects of complex, high dimensional treatments from observational data. The approach is based on conditional feature means, which represent conditional expectations of relevant model features. These features can be deep neural nets (adaptive, finite dimensional, learned from data), or kernel features (fixed, infinite dimensional, enforcing smoothness). When hidden confounding is present, a neural net implementation of instrumental variable regression can be used to correct for this confounding. The methods will be applied to modelling employment outcomes for the US Job Corps program for Disadvantaged Youth, and in policy evaluation for reinforcement learning.

Bio:

Arthur Gretton is a Professor with the Gatsby Computational Neuroscience Unit, and director of the Centre for Computational Statistics and Machine Learning (CSML) at UCL; and a research scientist at Google Deepmind. His recent research interests include causal inference and representation learning, design and training of generative models, and nonparametric hypothesis testing.

Arthur has been an associate editor at IEEE Transactions on Pattern Analysis and Machine Intelligence, an Action Editor for JMLR, a Senior Area Chair for NeurIPS (2018,2021) and ICML (2022), a member of the COLT Program Committee in 2013, and a member of Royal Statistical Society Research Section Committee since January 2020. Arthur was program co-chair for AISTATS in 2016, tutorials co-chair for ICML 2018, workshops co-chair for ICML 2019, program co-chair for the Dali workshop in 2019, and co-organsier of the Machine Learning Summer School 2019 in London.