
Spoofing Generalization: When Can't You Trust Proprietary Models?
In this work, we study the computational complexity of determining wheth...
read it

Sparsification for Sums of Exponentials and its Algorithmic Applications
Many works in signal processing and learning theory operate under the as...
read it

How to Decompose a Tensor with Group Structure
In this work we study the orbit recovery problem, which is a natural abs...
read it

Learning GMMs with Nearly Optimal Robustness Guarantees
In this work we solve the problem of robustly learning a highdimensiona...
read it

Learning to Sample from Censored Markov Random Fields
We study learning Censor Markov Random Fields (abbreviated CMRFs). These...
read it

Nogo Theorem for Acceleration in the Hyperbolic Plane
In recent years there has been significant effort to adapt the key tools...
read it

Settling the Robust Learnability of Mixtures of Gaussians
This work represents a natural coalescence of two important lines of wor...
read it

Online and DistributionFree Robustness: Regression and Contextual Bandits with Huber Contamination
In this work we revisit two classic highdimensional online learning pro...
read it

Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
In this paper we revisit some classic problems on classification under m...
read it

Tensor Completion Made Practical
Tensor completion is a natural higherorder generalization of matrix com...
read it

Algorithmic Foundations for the Diffraction Limit
For more than a century and a half it has been widelybelieved (but was ...
read it

Learning Structured Distributions From Untrusted Batches: Faster and Simpler
We revisit the problem of learning from untrusted batches introduced by ...
read it

Fast Convergence for Langevin Diffusion with Matrix Manifold Structure
In this paper, we study the problem of sampling from distributions of th...
read it

Rigorous Guarantees for Tyler's Mestimator via quantum expansion
Estimating the shape of an elliptical distribution is a fundamental prob...
read it

Polynomial time guarantees for the BurerMonteiro method
The BurerMonteiro method is one of the most widely used techniques for ...
read it

Efficiently Learning Structured Distributions from Untrusted Batches
We study the problem, introduced by Qiao and Valiant, of learning from u...
read it

Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
Gaussian Graphical Models (GGMs) have wideranging applications in machi...
read it

The Circuit Complexity of Inference
Belief propagation is one of the foundations of probabilistic and causal...
read it

How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories
Reconstruction of population histories is a central problem in populatio...
read it

Spectral Methods from Tensor Networks
A tensor network is a diagram that specifies a way to "multiply" a colle...
read it

Improved Bounds for Randomly Sampling Colorings via Linear Programming
A wellknown conjecture in computer science and statistical physics is t...
read it

The Paulsen Problem Made Simple
The Paulsen problem is a basic problem in operator theory that was resol...
read it

Efficiently Learning Mixtures of Mallows Models
Mixtures of Mallows models are a popular generative model for ranking da...
read it

Optimality and Suboptimality of PCA I: Spiked Random Matrix Models
A central problem of random matrix theory is to understand the eigenvalu...
read it

Learning Restricted Boltzmann Machines via Influence Maximization
Graphical models are a rich language for describing highdimensional dis...
read it

Linear Programming Bounds for Randomly Sampling Colorings
Here we study the problem of sampling random proper colorings of a bound...
read it

Learning Mixtures of Product Distributions via Higher Multilinear Moments
Learning mixtures of k binary product distributions is a central problem...
read it

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
We study the fundamental problem of learning the parameters of a highdi...
read it

Being Robust (in High Dimensions) Can Be Practical
Robust estimation is much more challenging in high dimensions than it is...
read it

Messagepassing algorithms for synchronization problems over compact groups
Various alignment problems arising in cryoelectron microscopy, communit...
read it

Optimality and Suboptimality of PCA for Spiked Random Matrices and Synchronization
A central problem of random matrix theory is to understand the eigenvalu...
read it

Provable Algorithms for Inference in Topic Models
Recently, there has been considerable progress on designing algorithms w...
read it

Robust Estimators in High Dimensions without the Computational Intractability
We study highdimensional distribution learning in an agnostic setting w...
read it

How Robust are Reconstruction Thresholds for Community Detection?
The stochastic block model is one of the oldest and most ubiquitous mode...
read it

Simple, Efficient, and Neural Algorithms for Sparse Coding
Sparse coding is a basic task in many fields including signal processing...
read it

Noisy Tensor Completion via the SumofSquares Hierarchy
In the noisy tensor completion problem we observe m entries (whose locat...
read it

Smoothed Analysis of Tensor Decompositions
Low rank tensor decompositions are a powerful tool for learning generati...
read it

New Algorithms for Learning Incoherent and Overcomplete Dictionaries
In sparse recovery we are given a matrix A (the dictionary) and a vector...
read it

A Practical Algorithm for Topic Modeling with Provable Guarantees
Topic models provide a useful method for dimensionality reduction and ex...
read it
Ankur Moitra
is this you? claim profile
Rockwell International Career Development Associate Professor at Massachusetts Institute of Technology