Results 491 - 500 of 23762

A landmark result in computational learning theory is the ``Low-Degree Algorithm" of Linial, Mansour, and Nisan that brought techniques from harmonic analysis to bear on learning theory. A striking application of their approach is that $AC^0$ circuits can be learned using quasipolynomial time and samples from the uniform distribution. This remains the state-of-the-art and their running time is known to be tight under various cryptographic assumptions. In this work, our focus is on the fundamental question: Is their quasipolynomial time algorithm an isolated phenomenon, or are there less brittle distributional assumptions that enable computationally efficient learning? In particular, can it be extended to natural distributions that allow for correlations? There are major challenges in doing so, most notably that we no longer have the convenience of a nice family of orthogonal functions. Our main result is a quasipolynomial time learning algorithm for $\mathsf{AC}^0$ circuits under high-temperature \emph{Ising models} of polynomial growth, nearly matching what is known in the product distribution setting. Our approach relies on constructing approximate Ising model samplers with low circuit complexity that can also be inverted. Such samplers can then be combined with recent advances on learning under nasty noise. The construction of these samplers builds on structural properties of Ising models, uncovering an exciting connection between strong spatial mixing and PAC learnability. Joint work with Gautam Chandrasekaran, Jason Gaitonde and Ankur Moitra

Fault-tolerant quantum computation (FTQC) is the study of making quantum computation robust against the presence of noise models of interest. In this talk, I will briefly describe recent progress that significantly improves the encoding rate and time efficiency of FTQC against the `local’ noise models, standard in physics. Then, I will switch gears to other complexity theory-inspired noise models and propose some open questions that I hope to think about at Simons.

Membership inference attacks (MIAs) are the primary tool for detecting memorization and auditing privacy in ML. But mounting a successful attack requires background knowledge about the data distribution, it is a knowledge that must itself be learned from auxiliary samples. What is the statistical cost of acquiring this knowledge?

I will present sharp bounds showing a dramatic dependence on prior knowledge. Without structural knowledge of the data distribution, attackers may require significantly more samples to audit a model than were used to train it. This suggests that standard heuristic attacks are statistically underpowered and may systematically underestimate memorization risk.
 

I will talk about my research on various aspects of Safety, Security & Privacy in the AI era.

I will discuss several aspects of how gradient descent interacts with the algorithmic randomness inherent to many training algorithms in machine learning. Randomness may be generated through the usual mini-batch sampling in SGD, but also noise-based regularization techniques, such as dropout or stochastic sharpness-aware minimization. This leads to the core question of what it should even really mean to have a "qualitative" understanding of how the injected noise affects the training process and final estimate. Using simple examples, I will illustrate how the added randomness may cause surprising outcomes and how the goals of optimization and statistical estimation may not always align perfectly.

My research focuses on the societal and economic implications of machine learning algorithms, including the role of incentives in data sharing and collaborative learning, the foundations of responsible AI—particularly data privacy and algorithmic fairness—and the goal of alignment with human preferences. In this talk, I will highlight three research problems I have worked on in connection with these areas and present the insights drawn from this work.

Abstract not available.

This talk highlights new research areas in collaborative learning, where multiple humans and/or autonomous agents interact under uncertainty and potentially misaligned incentives. Specifically, I’ll overview three directions that I am particularly excited about exploring: how to assign credit on AI content generation platforms like Sora, how to detect malicious agents within cooperative multi-agent systems, and how to leverage the wisdom of the crowd to make informed decisions using prediction markets. A common thread across these topics is understanding how incentives, information, and uncertainty affect collaborative learning, and how we can design decision-making systems that are more robust and reliable in the presence of these factors.