b'Ankur Moitra'

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...

0 Noah Golowich, et al. ∙

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...

0 Ainesh Bakshi, et al. ∙

research

∙ 06/03/2023

Provable benefits of score matching

Score matching is an alternative to maximum likelihood (ML) for estimati...

0 Chirag Pabbaraju, et al. ∙

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...

0 Zongchen Chen, et al. ∙

research

∙ 01/23/2023

A New Approach to Learning Linear Dynamical Systems

Linear dynamical systems are the foundational statistical model upon whi...

0 Ainesh Bakshi, et al. ∙

research

∙ 07/25/2022

Minimax Rates for Robust Community Detection

In this work, we study the problem of community detection in the stochas...

0 Allen Liu, et al. ∙

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 ...

0 Zongchen Chen, et al. ∙

research

∙ 06/29/2022

Distilling Model Failures as Directions in Latent Space

Existing methods for isolating hard subpopulations and spurious correlat...

0 Saachi Jain, et al. ∙

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...

0 Noah Golowich, et al. ∙

research

∙ 05/28/2022

Provably Auditing Ordinary Least Squares in Low Dimensions

Measuring the stability of conclusions derived from Ordinary Least Squar...

0 Ankur Moitra, et al. ∙

research

∙ 01/12/2022

Planning in Observable POMDPs in Quasipolynomial Time

Partially Observable Markov Decision Processes (POMDPs) are a natural an...

0 Noah Golowich, et al. ∙

research

∙ 12/13/2021

Robust Voting Rules from Algorithmic Robust Statistics

In this work we study the problem of robustly learning a Mallows model. ...

0 Allen Liu, et al. ∙

research

∙ 11/11/2021

Kalman Filtering with Adversarial Corruptions

Here we revisit the classic problem of linear quadratic estimation, i.e....

0 Sitan Chen, et al. ∙

research

∙ 10/25/2021

Can Q-Learning be Improved with Advice?

Despite rapid progress in theoretical reinforcement learning (RL) over t...

0 Noah Golowich, et al. ∙

research

∙ 06/15/2021

Spoofing Generalization: When Can't You Trust Proprietary Models?

In this work, we study the computational complexity of determining wheth...

0 Ankur Moitra, et al. ∙

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...

0 Jerry Li, et al. ∙

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...

0 Allen Liu, et al. ∙

research

∙ 04/19/2021

Learning GMMs with Nearly Optimal Robustness Guarantees

In this work we solve the problem of robustly learning a high-dimensiona...

0 Allen Liu, et al. ∙

research

∙ 01/15/2021

Learning to Sample from Censored Markov Random Fields

We study learning Censor Markov Random Fields (abbreviated CMRFs). These...

0 Ankur Moitra, et al. ∙

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...

0 Linus Hamilton, et al. ∙

research

∙ 11/06/2020

Settling the Robust Learnability of Mixtures of Gaussians

This work represents a natural coalescence of two important lines of wor...

0 Allen Liu, et al. ∙

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...

3 Sitan Chen, et al. ∙

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...

4 Sitan Chen, et al. ∙

research

∙ 06/04/2020

Tensor Completion Made Practical

Tensor completion is a natural higher-order generalization of matrix com...

0 Allen Liu, et al. ∙

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 ...

0 Sitan Chen, et al. ∙

research

∙ 02/24/2020

Learning Structured Distributions From Untrusted Batches: Faster and Simpler

We revisit the problem of learning from untrusted batches introduced by ...

0 Sitan Chen, et al. ∙

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...

0 Ankur Moitra, et al. ∙

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...

0 Cole Franks, et al. ∙

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 ...

0 Diego Cifuentes, et al. ∙

research

∙ 11/05/2019

Efficiently Learning Structured Distributions from Untrusted Batches

We study the problem, introduced by Qiao and Valiant, of learning from u...

0 Sitan Chen, et al. ∙

research

∙ 05/03/2019

Learning Some Popular Gaussian Graphical Models without Condition Number Bounds

Gaussian Graphical Models (GGMs) have wide-ranging applications in machi...

0 Jonathan Kelner, et al. ∙

research

∙ 04/11/2019

The Circuit Complexity of Inference

Belief propagation is one of the foundations of probabilistic and causal...

0 Ankur Moitra, et al. ∙

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...

0 Younhun Kim, et al. ∙

research

∙ 11/02/2018

Spectral Methods from Tensor Networks

A tensor network is a diagram that specifies a way to "multiply" a colle...

0 Ankur Moitra, et al. ∙

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...

0 Sitan Chen, et al. ∙

research

∙ 09/13/2018

The Paulsen Problem Made Simple

The Paulsen problem is a basic problem in operator theory that was resol...

0 Linus Hamilton, et al. ∙

research

∙ 08/17/2018

Efficiently Learning Mixtures of Mallows Models

Mixtures of Mallows models are a popular generative model for ranking da...

0 Allen Liu, et al. ∙

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...

0 Amelia Perry, et al. ∙

research

∙ 05/25/2018

Learning Restricted Boltzmann Machines via Influence Maximization

Graphical models are a rich language for describing high-dimensional dis...

0 Guy Bresler, et al. ∙

research

∙ 04/09/2018

Linear Programming Bounds for Randomly Sampling Colorings

Here we study the problem of sampling random proper colorings of a bound...

0 Sitan Chen, et al. ∙

research

∙ 03/17/2018

Learning Mixtures of Product Distributions via Higher Multilinear Moments

Learning mixtures of k binary product distributions is a central problem...

0 Sitan Chen, et al. ∙

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...

0 Ilias Diakonikolas, et al. ∙

research

∙ 03/02/2017

Being Robust (in High Dimensions) Can Be Practical

Robust estimation is much more challenging in high dimensions than it is...

0 Ilias Diakonikolas, et al. ∙

research

∙ 10/14/2016

Message-passing algorithms for synchronization problems over compact groups

Various alignment problems arising in cryo-electron microscopy, communit...

0 Amelia Perry, et al. ∙

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...

0 Amelia Perry, et al. ∙

research

∙ 05/27/2016

Provable Algorithms for Inference in Topic Models

Recently, there has been considerable progress on designing algorithms w...

0 Sanjeev Arora, et al. ∙

research

∙ 04/21/2016

Robust Estimators in High Dimensions without the Computational Intractability

We study high-dimensional distribution learning in an agnostic setting w...

0 Ilias Diakonikolas, et al. ∙

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...

0 Ankur Moitra, et al. ∙

research

∙ 03/02/2015

Simple, Efficient, and Neural Algorithms for Sparse Coding

Sparse coding is a basic task in many fields including signal processing...

0 Sanjeev Arora, et al. ∙

research

∙ 01/26/2015

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

In the noisy tensor completion problem we observe m entries (whose locat...

0 Boaz Barak, et al. ∙

Ankur Moitra

Featured Co-authors