research
∙
09/18/2023
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
The key assumption underlying linear Markov Decision Processes (MDPs) is...
share
research
∙
07/13/2023
Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems
Recently Chen and Poor initiated the study of learning mixtures of linea...
research
∙
06/03/2023
Provable benefits of score matching
Score matching is an alternative to maximum likelihood (ML) for estimati...
research
∙
04/04/2023
Strong spatial mixing for colorings on trees and its algorithmic applications
Strong spatial mixing (SSM) is an important quantitative notion of corre...
research
∙
01/23/2023
A New Approach to Learning Linear Dynamical Systems
Linear dynamical systems are the foundational statistical model upon whi...
research
∙
07/25/2022
Minimax Rates for Robust Community Detection
In this work, we study the problem of community detection in the stochas...
research
∙
07/06/2022
From algorithms to connectivity and back: finding a giant component in random k-SAT
We take an algorithmic approach to studying the solution space geometry ...
research
∙
06/29/2022
Distilling Model Failures as Directions in Latent Space
Existing methods for isolating hard subpopulations and spurious correlat...
research
∙
06/07/2022
Learning in Observable POMDPs, without Computationally Intractable Oracles
Much of reinforcement learning theory is built on top of oracles that ar...
research
∙
05/28/2022
Provably Auditing Ordinary Least Squares in Low Dimensions
Measuring the stability of conclusions derived from Ordinary Least Squar...
research
∙
01/12/2022
Planning in Observable POMDPs in Quasipolynomial Time
Partially Observable Markov Decision Processes (POMDPs) are a natural an...
research
∙
12/13/2021
Robust Voting Rules from Algorithmic Robust Statistics
In this work we study the problem of robustly learning a Mallows model. ...
research
∙
11/11/2021
Kalman Filtering with Adversarial Corruptions
Here we revisit the classic problem of linear quadratic estimation, i.e....
research
∙
10/25/2021
Can Q-Learning be Improved with Advice?
Despite rapid progress in theoretical reinforcement learning (RL) over t...
research
∙
06/15/2021
Spoofing Generalization: When Can't You Trust Proprietary Models?
In this work, we study the computational complexity of determining wheth...
research
∙
06/05/2021
Sparsification for Sums of Exponentials and its Algorithmic Applications
Many works in signal processing and learning theory operate under the as...
research
∙
06/04/2021
How to Decompose a Tensor with Group Structure
In this work we study the orbit recovery problem, which is a natural abs...
research
∙
04/19/2021
Learning GMMs with Nearly Optimal Robustness Guarantees
In this work we solve the problem of robustly learning a high-dimensiona...
research
∙
01/15/2021
Learning to Sample from Censored Markov Random Fields
We study learning Censor Markov Random Fields (abbreviated CMRFs). These...
research
∙
01/14/2021
No-go Theorem for Acceleration in the Hyperbolic Plane
In recent years there has been significant effort to adapt the key tools...
research
∙
11/06/2020
Settling the Robust Learnability of Mixtures of Gaussians
This work represents a natural coalescence of two important lines of wor...
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
∙
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
∙
06/04/2020
Tensor Completion Made Practical
Tensor completion is a natural higher-order generalization of matrix com...
research
∙
04/16/2020
Algorithmic Foundations for the Diffraction Limit
For more than a century and a half it has been widely-believed (but was ...
research
∙
02/24/2020
Learning Structured Distributions From Untrusted Batches: Faster and Simpler
We revisit the problem of learning from untrusted batches introduced by ...
research
∙
02/13/2020
Fast Convergence for Langevin Diffusion with Matrix Manifold Structure
In this paper, we study the problem of sampling from distributions of th...
research
∙
01/31/2020
Rigorous Guarantees for Tyler's M-estimator via quantum expansion
Estimating the shape of an elliptical distribution is a fundamental prob...
research
∙
12/03/2019
Polynomial time guarantees for the Burer-Monteiro method
The Burer-Monteiro method is one of the most widely used techniques for ...
research
∙
11/05/2019
Efficiently Learning Structured Distributions from Untrusted Batches
We study the problem, introduced by Qiao and Valiant, of learning from u...
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
∙
04/11/2019
The Circuit Complexity of Inference
Belief propagation is one of the foundations of probabilistic and causal...
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
∙
11/02/2018
Spectral Methods from Tensor Networks
A tensor network is a diagram that specifies a way to "multiply" a colle...
research
∙
10/30/2018
Improved Bounds for Randomly Sampling Colorings via Linear Programming
A well-known conjecture in computer science and statistical physics is t...
research
∙
09/13/2018
The Paulsen Problem Made Simple
The Paulsen problem is a basic problem in operator theory that was resol...
research
∙
08/17/2018
Efficiently Learning Mixtures of Mallows Models
Mixtures of Mallows models are a popular generative model for ranking da...
research
∙
07/02/2018
Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
A central problem of random matrix theory is to understand the eigenvalu...
research
∙
05/25/2018
Learning Restricted Boltzmann Machines via Influence Maximization
Graphical models are a rich language for describing high-dimensional dis...
research
∙
04/09/2018
Linear Programming Bounds for Randomly Sampling Colorings
Here we study the problem of sampling random proper colorings of a bound...
research
∙
03/17/2018
Learning Mixtures of Product Distributions via Higher Multilinear Moments
Learning mixtures of k binary product distributions is a central problem...
research
∙
04/12/2017
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
We study the fundamental problem of learning the parameters of a high-di...
research
∙
03/02/2017
Being Robust (in High Dimensions) Can Be Practical
Robust estimation is much more challenging in high dimensions than it is...
research
∙
10/14/2016
Message-passing algorithms for synchronization problems over compact groups
Various alignment problems arising in cryo-electron microscopy, communit...
research
∙
09/19/2016
Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
A central problem of random matrix theory is to understand the eigenvalu...
research
∙
05/27/2016
Provable Algorithms for Inference in Topic Models
Recently, there has been considerable progress on designing algorithms w...
research
∙
04/21/2016
Robust Estimators in High Dimensions without the Computational Intractability
We study high-dimensional distribution learning in an agnostic setting w...
research
∙
11/04/2015
How Robust are Reconstruction Thresholds for Community Detection?
The stochastic block model is one of the oldest and most ubiquitous mode...
research
∙
03/02/2015
Simple, Efficient, and Neural Algorithms for Sparse Coding
Sparse coding is a basic task in many fields including signal processing...
research
∙
01/26/2015
