6 citations · 39 across the 21 of their papers we have counts for
11 papers · 1 filter
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Clément L. Canonne, Samuel B. Hopkins, Jerry Li +2
We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samp…
Minimax Rates for Robust Community Detection
Allen Liu, Ankur Moitra
In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolera…
Semi-Random Sparse Recovery in Nearly-Linear Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
Sparse recovery is one of the most fundamental and well-studied inverse problems. Standard statistical formulations of the problem are provably solved by general convex programming…
Robust Voting Rules from Algorithmic Robust Statistics
Allen Liu, Ankur Moitra
Maximum likelihood estimation furnishes powerful insights into voting theory, and the design of voting rules. However the MLE can usually be badly corrupted by a single outlying sa…
Robust Model Selection and Nearly-Proper Learning for GMMs
Jerry Li, Allen Liu, Ankur Moitra
In learning theory, a standard assumption is that the data is generated from a finite mixture model. But what happens when the number of components is not known in advance? The pro…
Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over
Allen Liu, Ankur Moitra
In this work we study orbit recovery over , where the goal is to recover a function on the sphere from noisy, randomly rotated copies of it. We assume that the function is a…
Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu, Ankur Moitra
This work represents a natural coalescence of two important lines of work: learning mixtures of Gaussians and algorithmic robust statistics. In particular we give the first provabl…
Tensor Completion Made Practical
Allen Liu, Ankur Moitra
Tensor completion is a natural higher-order generalization of matrix completion where the goal is to recover a low-rank tensor from sparse observations of its entries. Existing alg…
Variable Decomposition for Prophet Inequalities and Optimal Ordering
Allen Liu, Renato Paes Leme, Martin Pal +2
We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number o…
Optimal Contextual Pricing and Extensions
Allen Liu, Renato Paes Leme, Jon Schneider
In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in and only observes the purchasing decisi…
Efficiently Learning Mixtures of Mallows Models
Allen Liu, Ankur Moitra
Mixtures of Mallows models are a popular generative model for ranking data coming from a heterogeneous population. They have a variety of applications including social choice, reco…