Symposium on Mathematical Foundations of Trustworthy Learning

Differential Privacy and the Broader Landscape of Robustness in Algorithmic Statistics
Speaker: Gautam Kamath

Abstract:

I will discuss differential privacy, a rigorous notion of data privacy, and its relationship to other constraints, including adversarial contamination and heavy-tailed data. I will explore conceptual and algorithmics connections between these seemingly different notions of robustness.

private statistical estimation via robustness and stability
Speaker: Sewoong Oh

Abstract:

Privacy enhancing technologies, such as differentially private stochastic gradient descent (DP-SGD), allow us to access private data without worrying about leaking sensitive information. This is crucial in the modern era of data-centric AI, where all public data has been exhausted and the next frontier models rely on access to high-quality data. Central component in these technologies is private statistical estimation. We present a series of results where robust statistics and stable algorithms have played critical roles in advancing the state-of-the-art in differentially private statistical estimation. This talk is based on papers https://arxiv.org/abs/2404.15409, https://arxiv.org/abs/2301.13273, and https://arxiv.org/abs/2111.06578.

Gentle Measurements of Quantum States
Speaker: Cristina Butucea

Abstract:

Gentle measurements of quantum states result in both a random variable and a non-collapsed post-measurement state which is at a prescribed trace-distance from the initial state. Unlike collapsed states, this can be further used in quantum computing. Connections of gentle measurements to quantum differential privacy have been established. We introduce here locally gentle measurements and prove a quantum data processing inequality for such measurements. We introduce a physically feasible gentle measurement called quantum Label Switch and show optimal rates for learning and testing of qubits.

Gradient optimization methods: the benefits of a large step-size
Speaker: Peter L. Bartlett

Abstract:

Deep learning has revealed some major surprises from the perspective of theory. Optimization in deep learning relies on simple gradient descent algorithms that are traditionally viewed as a time discretization of gradient flow. However, in practice, large step sizes - large enough to cause oscillation of the loss - exhibit performance advantages. This talk will review recent results on gradient descent with logistic loss with a step size large enough that the optimization trajectory is at the "edge of stability". We show the benefits of this initial oscillatory phase for linear functions and for multi-layer networks, and identify an asymptotic implicit bias that gradient descent imposes for a large family of deep networks. Based on joint work with Yuhang Cai, Michael Lindsey, Song Mei, Matus Telgarsky, Jingfeng Wu, Bin Yu and Kangjie Zhou.

Wild refitting for black box prediction
Speaker: Martin Wainwright

Abstract:

Obtaining inferential guarantees on the performance of a prediction method is essential in practice. However, many modern predictive methods are opaque, so that a statistician is limited to querying its predicted values only (with no further insight into its properties). At the same time, such queries can be computationally expensive, so that inferential methods only make a small number of queries. In this talk, we describe and analyze a method for black-box inference that meet these desideredata, and illustrate its performance on motion reconstruction and image denoising.

Fairness for automated decision making - more challenges than definite answers
Speaker: Shai Ben-David

Abstract:

Algorithmic tools for decision making show up in more and more areas that have significant impact on individuals or society. Along with the obvious benefits that such tools bring, questions about their "fairness" are of greatest concern. Can we trust ML based tools for deciding acceptance of students to a program? Deciding who a bank should give a loan to and with what conditions? Which criminal suspect should be released on bail? While traditionally such questions were discussed by philosophers and social scientists, the introduction of algorithmic based decision support requires consideration from a computer science perspective. Answers are far from obvious and are subject of heated discussions; Can fairness be formally defined? What can affect unfairness or bias in automated decision making? How can algorithm designers mitigate such concerns? In fact, this talk will be more about raising questions (and awareness) than about offering definite answers.

When does allocation require prediction?
Speaker: Rediet Abebe

Abstract:

TBD

On the merits of economic modeling for understanding the long-term impacts of AI regulation
Speaker: Hoda Heidari

Abstract:

The new paradigm in AI is that of General-purpose models: A firm releases a large, pretrained model, designed to be adapted and tweaked by other entities to perform domain-specific functions and create economic value. In this talk, I will explore how we can use tools from economics to understand the resulting market dynamics and the strategic behavior of key players in response to regulatory choices around AI (e.g., on safety and openness). I will end the talk with a discussion of merits and limitations of mathematical modeling as a tool for analyzing the broader, long-term impacts of AI in society.

Interactive Decision-Making via Autoregressive Generation
Speaker: Hongseok Namkoong

Abstract:

AI agents interacting with the real-world have to grapple with a perpetual lack of data in ever-changing environments. Interactive decision-making requires going beyond knowledge distillation: an intelligent agent must comprehend its own uncertainty and actively gather information to resolve it. Despite exhibiting impressive capabilities in basic knowledge work, state-of-the-art AI systems struggle to articulate their own uncertainty, e.g., OpenAI recently noted its latest agentic system “DeepResearch often fails to convey uncertainty accurately”. This talk covers a series of recent works that tackle the central challenge of uncertainty quantification in natural language-based interactive decision-making problems. Instead of modeling latent environment parameters, we view uncertainty as arising out of missing future outcomes and quantify it through autoregressive sequence generation—iteratively predicting the next outcome given the past. By adapting to new information through in-context learning rather than cumbersome posterior inference, our approach seamlessly scales to problems involving unstructured data, e.g., adaptive student assessment involving text and images. Formally, we establish a reduction from online decision-making to offline next-outcome prediction, enabling us to leverage the enormous datasets and computational resources dedicated to improving sequence prediction for interactive decision-making tasks.

Collaborative Prediction via Tractable Agreement Protocols
Speaker: Surbhi Goel

Abstract:

Designing effective collaboration between humans and AI systems is crucial for leveraging their complementary abilities in complex decision tasks. But how should agents possessing unique, private knowledge—like a human expert and an AI model—interact to reach decisions better than either could alone? If they were perfect Bayesians with a shared prior, Aumann's classical agreement theorem suggests conversation leads to a prediction via agreement which is accuracy-improving. However, this relies on implausible assumptions about their knowledge and computational power. We show how to recover and generalize these guarantees using only computationally and statistically tractable assumptions. We develop efficient "collaboration protocols" where parties iteratively exchange only low-dimensional information – their current predictions or best-response actions – without needing to share underlying features. These protocols are grounded in conditions like conversation calibration/swap regret, which relax full Bayesian rationality, and are computationally efficiently enforceable. First, we prove this simple interaction leads to fast convergence to agreement, generalizing quantitative bounds even to high-dimensional and action-based settings. Second, we introduce a weak learning condition under which this agreement process inherently aggregates the parties' distinct information, that is, agents via our protocols arrive at final predictions that are provably competitive with an optimal predictor having access to their joint features. Together, these results offer a new, practical foundation for building systems that achieve the power of pooled knowledge through tractable interaction alone.

Feature learning and the linear representation hypothesis for monitoring and steering LLMs
Speaker: Mikhail Belkin

Abstract:

Feature learningA trained Large Language Model (LLM) contains much of human knowledge. Yet, it is difficult to gauge the extent or accuracy of that knowledge, as LLMs do not always ``know what they know'' and may even be unintentionally or actively misleading. In this talk I will discuss feature learning introducing Recursive Feature Machines—a powerful method originally designed for extracting relevant features from tabular data. I will demonstrate how this technique enables us to detect and precisely guide LLM behaviors toward almost any desired concept by manipulating a single fixed vector in the LLM activation space. and "the linear representation hypothesis" for monitoring and steering LLMs

Causality and Robustness
Speaker: Jonas Peters

Abstract:

TBD

When We Talk About Replicability, What Are We Talking About?
Speaker: Amin Karbasi

Abstract:

Lack of replicability in experiments has been a major issue, usually referred to as the reproducibility crisis, in many scientific areas such as biology, chemistry, and artificial intelligence. Indeed, the results of a survey that appeared in Nature are very worrisome: more than 70% of the researchers that participated in it could not replicate other researchers’ experimental findings while over half of them were not able to even replicate their own conclusions!!! In its simplest form, replicability requires that if two different groups of researchers carry out an experiment using the same methodologies but different samples of the same population, it better be the case that the two outcomes of their studies are statistically indistinguishable. In this talk, we investigate this notion in the context of machine learning and characterize for which learning problems statistically indistinguishable learning algorithms exist.

Replicability: A computational view
Speaker: Jessica Sorrell

Abstract:

Connections between replicability and differential privacy have helped us establish boundaries on the statistical efficiency of replicable PAC learning, but the limits of computationally efficient replicability are somewhat less clear. In this talk, we'll discuss the conditions under which replicable PAC learning is computationally tractable, as well as cryptographic assumptions that separate differential privacy and replicability.