296 citations · 530 across the 29 of their papers we have counts for
7 papers · 1 filter
Privately Learning Thresholds: Closing the Exponential Gap
Haim Kaplan, Katrina Ligett, Yishay Mansour +2
We study the sample complexity of learning threshold functions under the constraint of differential privacy. It is assumed that each labeled example in the training data is the inf…
Adaptive Learning with Robust Generalization Guarantees
Rachel Cummings, Katrina Ligett, Kobbi Nissim +2
The traditional notion of generalization---i.e., learning a hypothesis whose empirical error is close to its true error---is surprisingly brittle. As has recently been noted in [DF…
A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret
Lachlan L. H. Andrew, Siddharth Barman, Katrina Ligett +4
We consider algorithms for "smoothed online convex optimization" problems, a variant of the class of online convex optimization problems that is strongly related to metrical task s…
Coordination Complexity: Small Information Coordinating Large Populations
Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan +2
We initiate the study of a quantity that we call coordination complexity. In a distributed optimization problem, the information defining a problem instance is distributed among $n…
A Learning Theory Approach to Non-Interactive Database Privacy
Avrim Blum, Katrina Ligett, Aaron Roth
In this paper we demonstrate that, ignoring computational constraints, it is possible to privately release synthetic databases that are useful for large classes of queries -- much…
A simple and practical algorithm for differentially private data release
Moritz Hardt, Katrina Ligett, Frank McSherry
We present new theoretical results on differentially private data release useful with respect to any target class of counting queries, coupled with experimental results on a variet…