558 citations · 3.6k across the 65 of their papers we have counts for
4 papers · 1 filter
Better Agnostic Clustering Via Relaxed Tensor Norms
Pravesh K. Kothari, Jacob Steinhardt
We develop a new family of convex relaxations for -means clustering based on sum-of-squares norms, a relaxation of the injective tensor norm that is efficiently computable using…
Certified Defenses for Data Poisoning Attacks
Jacob Steinhardt, Pang Wei Koh, Percy Liang
Machine learning systems trained on user-provided data are susceptible to data poisoning attacks, whereby malicious users inject false training data with the aim of corrupting the…
Does robustness imply tractability? A lower bound for planted clique in the semi-random model
Jacob Steinhardt
We consider a robust analog of the planted clique problem. In this analog, a set of vertices is chosen and all edges in are included; then, edges between and the rest o…
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
Jacob Steinhardt, Moses Charikar, Gregory Valiant
We introduce a criterion, resilience, which allows properties of a dataset (such as its mean or best low rank approximation) to be robustly computed, even in the presence of a larg…