517 citations · 1.1k across the 28 of their papers we have counts for
29 papers
What can a Single Attention Layer Learn? A Study Through the Random Features Lens
Hengyu Fu, Tianyu Guo, Yu Bai +1
Attention layers -- which map a sequence of inputs to a sequence of outputs -- are core building blocks of the Transformer architecture which has achieved significant breakthroughs…
Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection
Yu Bai, Fan Chen, Huan Wang +2
Neural sequence models based on the transformer architecture have demonstrated remarkable \emph{in-context learning} (ICL) abilities, where they can perform new tasks when prompted…
Lower Bounds for Learning in Revealing POMDPs
Fan Chen, Huan Wang, Caiming Xiong +2
This paper studies the fundamental limits of reinforcement learning (RL) in the challenging \emph{partially observable} setting. While it is well-established that learning in Parti…
Plausible deniability for privacy-preserving data synthesis
Song Mei, Zhiqiang Ye
In the field of privacy protection, publishing complete data (especially high-dimensional data sets) is one of the most challenging problems. The common encryption technology can n…
Near-optimal multiple testing in Bayesian linear models with finite-sample FDR control
Taejoo Ahn, Licong Lin, Song Mei
In high dimensional variable selection problems, statisticians often seek to design multiple testing procedures that control the False Discovery Rate (FDR), while concurrently iden…
Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms
Fan Chen, Yu Bai, Song Mei
Partial Observability -- where agents can only observe partial information about the true underlying state of the system -- is ubiquitous in real-world applications of Reinforcemen…
Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games
Ziang Song, Song Mei, Yu Bai
Imperfect-Information Extensive-Form Games (IIEFGs) is a prevalent model for real-world games involving imperfect information and sequential plays. The Extensive-Form Correlated Eq…
Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent
Yu Bai, Chi Jin, Song Mei +2
A conceptually appealing approach for learning Extensive-Form Games (EFGs) is to convert them to Normal-Form Games (NFGs). This approach enables us to directly translate state-of-t…
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
Joao Basso, David Gamarnik, Song Mei +1
The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove…
Efficient and Differentiable Conformal Prediction with General Function Classes
Yu Bai, Song Mei, Huan Wang +2
Quantifying the data uncertainty in learning tasks is often done by learning a prediction interval or prediction set of the label given the input. Two commonly desired properties f…
Near-Optimal Learning of Extensive-Form Games with Imperfect Information
Yu Bai, Chi Jin, Song Mei +1
This paper resolves the open question of designing near-optimal algorithms for learning imperfect-information extensive-form games from bandit feedback. We present the first line o…
The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
Nikhil Ghosh, Song Mei, Bin Yu
To understand how deep learning works, it is crucial to understand the training dynamics of neural networks. Several interesting hypotheses about these dynamics have been made base…
Learning with convolution and pooling operations in kernel methods
Theodor Misiakiewicz, Song Mei
Recent empirical work has shown that hierarchical convolutional kernels inspired by convolutional neural networks (CNNs) significantly improve the performance of kernel methods in…
When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
Ziang Song, Song Mei, Yu Bai
Multi-agent reinforcement learning has made substantial empirical progresses in solving games with a large number of players. However, theoretically, the best known sample complexi…
Understanding the Under-Coverage Bias in Uncertainty Estimation
Yu Bai, Song Mei, Huan Wang +1
Estimating the data uncertainty in regression tasks is often done by learning a quantile function or a prediction interval of the true label conditioned on the input. It is frequen…
Local convexity of the TAP free energy and AMP convergence for Z2-synchronization
Michael Celentano, Zhou Fan, Song Mei
We study mean-field variational Bayesian inference using the TAP approach, for Z2-synchronization as a prototypical example of a high-dimensional Bayesian model. We show that for a…
Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
Zitong Yang, Yu Bai, Song Mei
Recent work showed that there could be a large gap between the classical uniform convergence bound and the actual test error of zero-training-error predictors (interpolators) such…
Learning with invariances in random features and kernel models
Song Mei, Theodor Misiakiewicz, Andrea Montanari
A number of machine learning tasks entail a high degree of invariance: the data distribution does not change if we act on the data with a certain group of transformations. For inst…
Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification
Yu Bai, Song Mei, Huan Wang +1
Modern machine learning models with high accuracy are often miscalibrated -- the predicted top probability does not reflect the actual accuracy, and tends to be over-confident. It…
When Do Neural Networks Outperform Kernel Methods?
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz +1
For a certain scaling of the initialization of stochastic gradient descent (SGD), wide neural networks (NN) have been shown to be well approximated by reproducing kernel Hilbert sp…
The generalization error of random features regression: Precise asymptotics and double descent curve
Song Mei, Andrea Montanari
Deep learning methods operate in regimes that defy the traditional statistical mindset. Neural network architectures often contain more parameters than training samples, and are so…
Limitations of Lazy Training of Two-layers Neural Networks
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz +1
We study the supervised learning problem under either of the following two models: (1) Feature vectors are -dimensional Gaussians and responses are $y_i = f_…
Proximal algorithms for constrained composite optimization, with applications to solving low-rank SDPs
Yu Bai, John Duchi, Song Mei
We study a family of (potentially non-convex) constrained optimization problems with convex composite structure. Through a novel analysis of non-smooth geometry, we show that proxi…
Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
Song Mei, Theodor Misiakiewicz, Andrea Montanari
We consider learning two layer neural networks using stochastic gradient descent. The mean-field description of this learning dynamics approximates the evolution of the network wei…