research
∙
07/19/2023
Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses
We study Glauber dynamics for sampling from discrete distributions μ on ...
share
research
∙
07/14/2023
Influences in Mixing Measures
The theory of influences in product measures has profound applications i...
research
∙
05/26/2023
Feature Adaptation for Sparse Linear Regression
Sparse linear regression is a central problem in high-dimensional statis...
research
∙
10/21/2022
A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models
We prove a new generalization bound that shows for any class of linear p...
research
∙
10/03/2022
Statistical Efficiency of Score Matching: The View from Isoperimetry
Deep generative models parametrized up to a normalizing constant (e.g. e...
research
∙
03/05/2022
Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs
Sparse linear regression with ill-conditioned Gaussian random designs is...
research
∙
02/17/2022
Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods
We consider Ising models on the hypercube with a general interaction mat...
research
∙
12/13/2021
Variational autoencoders in the presence of low-dimensional data: landscape and implicit bias
Variational Autoencoders (VAEs) are one of the most commonly used genera...
research
∙
12/08/2021
Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression
We study a localized notion of uniform convergence known as an "optimist...
research
∙
11/11/2021
Kalman Filtering with Adversarial Corruptions
Here we revisit the classic problem of linear quadratic estimation, i.e....
research
∙
11/05/2021
Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities
We introduce a framework for obtaining tight mixing times for Markov cha...
research
∙
09/23/2021
Multidimensional Scaling: Approximation and Complexity
Metric Multidimensional scaling (MDS) is a classical method for generati...
research
∙
09/14/2021
Reconstruction on Trees and Low-Degree Polynomials
The study of Markov processes and broadcasting on trees has deep connect...
research
∙
06/17/2021
Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
We consider interpolation learning in high-dimensional linear regression...
research
∙
06/17/2021
On the Power of Preconditioning in Sparse Linear Regression
Sparse linear regression is a fundamental problem in high-dimensional st...
research
∙
06/08/2021
Entropic Independence in High-Dimensional Expanders: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Polynomials and the Ising Model
We introduce a notion called entropic independence for distributions μ d...
research
∙
06/07/2021
Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
We consider the problem of learning a tree-structured Ising model from d...
research
∙
10/08/2020
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
In this work we revisit two classic high-dimensional online learning pro...
research
∙
10/02/2020
Representational aspects of depth and conditioning in normalizing flows
Normalizing flows are among the most popular paradigms in generative mod...
research
∙
07/25/2020
From Boltzmann Machines to Neural Networks and Back Again
Graphical models are powerful tools for modeling high-dimensional data, ...
research
∙
06/08/2020
Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
In this paper we revisit some classic problems on classification under m...
research
∙
04/27/2020
A Phase Transition in Arrow's Theorem
Arrow's Theorem concerns a fundamental problem in social choice theory: ...
research
∙
05/24/2019
Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
The analysis of Belief Propagation and other algorithms for the reconst...
research
∙
05/24/2019
Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay
Belief propagation is a fundamental message-passing algorithm for probab...
research
∙
05/03/2019
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
Gaussian Graphical Models (GGMs) have wide-ranging applications in machi...
research
∙
11/07/2018
How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories
Reconstruction of population histories is a central problem in populatio...
research
∙
08/22/2018
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
The free energy is a key quantity of interest in Ising models, but unfor...
research
∙
05/29/2018
Representational Power of ReLU Networks and Polynomial Kernels: Beyond Worst-Case Analysis
There has been a large amount of interest, both in the past and particul...
research
∙
05/25/2018
Learning Restricted Boltzmann Machines via Influence Maximization
Graphical models are a rich language for describing high-dimensional dis...
research
∙
02/16/2018
The Vertex Sample Complexity of Free Energy is Polynomial
We study the following question: given a massive Markov random field on ...
research
∙
02/16/2018
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
The mean field approximation to the Ising model is a canonical variation...
research
∙
11/05/2017
Approximating Partition Functions in Constant Time
We study approximations of the partition function of dense graphical mod...
research
∙
05/27/2016