Moritz Hardt
I'm currently a post-doctoral researcher in the theory group at IBM Research Almaden. I completed my PhD in Computer Science at Princeton University in 2011. My advisor was Boaz Barak. Before coming to Princeton, I spent a year as a research scholar at Carnegie Mellon University and three years at Saarland University from where I obtained a B.Sc. and an M.Sc. in Computer Science in 2007.
My research interests revolve around sensitive data analysis, algorithms, complexity and learning theory.
I'm on the ICALP 2012 program committee.
Publications (selected)
See all publications. See selected publications.
-
In Proc. of STOC 2012 (to appear)
Versions: Technical report (arXiv)
Abstract: Computing accurate low rank approximations of large matrices is a fundamental data mining task. In many applications however the matrix contains sensitive information about individuals. In such case we would like to release a low rank approximation that satisfies a strong privacy guarantee such as differential privacy. Unfortunately, to date the best known algorithm for this task that satisfies differential privacy is based on naive input perturbation or randomized response: Each entry of the matrix is perturbed independently by a sufficiently large random noise variable, a low rank approximation is then computed on the resulting matrix.
We give (the first) significant improvements in accuracy over randomized response under the natural and necessary assumption that the matrix has low coherence. Our algorithm is also very efficient and finds a constant rank approximation of an m x n matrix in time O(mn). Note that even generating the noise matrix required for randomized response already requires time O(mn).
-
In Proc. of SODA 2012: 168–187
Versions: Technical report (arXiv), Proceedings (pdf), Short talk (pdf, no step effects)
Abstract: This work considers computationally efficient privacy-preserving data release. We study the task of analyzing a database containing sensitive information about individual participants. Given a set of statistical queries on the data, we want to release approximate answers to the queries while also guaranteeing differential privacy–protecting each participant's sensitive data.
Our focus is on computationally efficient data release algorithms; we seek algorithms whose running time is polynomial, or at least sub-exponential, in the data dimensionality. Our primary contribution is a computationally efficient reduction from differentially private data release for a class of counting queries, to learning thresholded sums of predicates from a related class.
We instantiate this general reduction with a variety of algorithms for learning thresholds. These instantiations yield several new results for differentially private data release. As two examples, taking {0,1}^d to be the data domain (of dimension d), we obtain differentially private algorithms for:
- Releasing all k-way conjunction counting queries (or k-way contingency tables). For any given k, the resulting data release algorithm has bounded error as long as the database is of size at least d^{O(\sqrt{k\log(k\log d)})} (ignoring the dependence on other parameters). The running time is polynomial in the database size. The best sub-exponential time algorithms known prior to our work required a database of size \tilde{O}(d^{k/2}) [Dwork McSherry Nissim and Smith 2006].
- Releasing a (1-\gamma)-fraction of all 2^d parity counting queries. For any \gamma \geq \poly(1/d), the algorithm has bounded error as long as the database is of size at least \poly(d) (again ignoring the dependence on other parameters). The running time is polynomial in the database size.
Several other instantiations yield further results for privacy-preserving data release. Of the two results highlighted above, the first learning algorithm uses techniques for representing thresholded sums of predicates as low-degree polynomial threshold functions. The second learning algorithm is based on Jackson's Harmonic Sieve algorithm [Jackson 1997]. It utilizes Fourier analysis of the database viewed as a function mapping queries to answers.
-
In Proc. of ITCS 2012 (to appear)
Versions: PDF
Abstract: We initiate a principled study of graph densification. Given a graph G the goal of graph densification is to come up with another graph H that has significantly more edges than G but nevertheless approximates G well with respect to some set of test functions. In this paper we focus on the case of cut and spectral approximations. As it turns out graph densification exhibits rich connections to a set of interesting and sometimes seemingly unrelated questions in graph theory and metric embeddings. In particular we show the following results:
- A graph G has a multiplicative cut approximation with an asymptotically increased density if and only if it does not embed into ell_1 under a weak notion of embeddability. We demonstrate that all planar graphs as well as random geometric graphs possess such embeddings and thus do not have densifiers. On the other hand, expanders do have densifiers (namely, the complete graph) and as a result do not embed into ell_1 even under our weak notion of embedding.
- An analogous characterization is true for multiplicative spectral approximations where the embedding is into ell_2^2. Using this characterization we expose a surprisingly close connection between multiplicative spectral and multiplicative cut densifiers.
- We also consider additive cut and spectral approximations. We exhibit graphs that do not possess non-trivial additive densifiers.
-
In Proc. of ITCS 2012 (to appear)
Versions: Technical report (arxiv)
Abstract: "What can be learned about from the sole fact that I have been shown this on-line advertisement?" By definition, the answer to this question is non-trivial whenever advertisements are not served indiscriminately. Advertisers, hoping to have targeted precisely and appropriately, use information from multiple sources to give different on-line experiences to different people. Thus the message of "giving you the ads that interest you" does not tell the whole story of behavioral targeting, and the resulting differentiation in user experience may, or may not, work to the advantage of the user. When it results in differential pricing it arguably does not benefit some users; when it results in steering minorities away from certain neighborhoods or toward less advantageous credit card offerings, it is illegal. This raises the question of fairness in advertising, and, more generally, of fairness in classification. This rather broad topic is not restricted to the digital world, and encompasses classification in such diverse areas as banking, health care, and school admissions. Recognizing the real-life significance of fairness in classification we initiate its formal study.
-
Manuscript.
Versions: Technical Report (arxiv)
Abstract: 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 variety of real world data sets. Specifically, we study a simple combination of the multiplicative weights approach of [Hardt and Rothblum, 2010] with the exponential mechanism of [McSherry and Talwar, 2007]. The multiplicative weights framework allows us to maintain and improve a distribution approximating a given data set with respect to a set of counting queries. We use the exponential mechanism to select those queries most incorrectly tracked by the current distribution. Combing the two, we quickly approach a distribution that agrees with the data set on the given set of queries up to small error. The resulting algorithm and its analysis is simple, but nevertheless improves upon previous work in terms of both error and running time. We also empirically demonstrate the practicality of our approach on several data sets commonly used in the statistical community for contingency table release.
-
In Proc. of STOC 2011: 803–812
Versions: Technical Report (arXiv)
Abstract: Suppose we would like to know all answers to a set of statistical queries C on a data set up to small error, but we can only access the data itself using statistical queries. A trivial solution is to exhaustively ask all queries in C. Can we do any better?
- We show that the number of statistical queries necessary and sufficient for this task is---up to polynomial factors---equal to the agnostic learning complexity of C in Kearns' statistical query (SQ) model. This gives a complete answer to the question when running time is not a concern.
- We then show that the problem can be solved efficiently (allowing arbitrary error on a small fraction of queries) whenever the answers to C can be described by a submodular function. This includes many natural concept classes, such as graph cuts and Boolean disjunctions and conjunctions. In doing so we also give a new learning algorithm for submodular functions that improves upon recent results in a different context.
While interesting from a learning theoretic point of view, our main applications are in privacy-preserving data analysis:
Here, our second result leads to the first algorithm that efficiently releases differentially private answers to all Boolean conjunctions with 1% average error. This presents significant progress on a key open problem in privacy-preserving data analysis.
Our first result on the other hand gives unconditional lower bounds on any differentially private algorithm that admits a (potentially non-privacy-preserving) implementation using only statistical queries. Not only our algorithms, but also most known private algorithms can be implemented using only statistical queries, and hence are constrained by these lower bounds. Our result therefore isolates the complexity of agnostic learning in the SQ-model as a new barrier in the design of differentially private algorithms.
-
In Proc. of SODA 2011: 512–531
Versions: Technical Report (ECCC), Talk (PDF)
Short abstract: We consider the following seemingly unrelated questions:
• Is the MaxCut problem hard on random geometric graphs of the type considered by Feige and Schechtman (2002)?
• Is the value of a mathematical relaxation for a constraint-satisfaction problem (CSP) preserved when one passes from an instance P to a random induced sub-formula of P?
It turns out that the answer to the first question is ``no'' and in fact this is intimately related to the second question. The answer to the second question is much more subtle, and, in contrast to the case of the objective value of the CSP, the answer strongly depends on the type of relaxation and CSP.
-
In Proc. of FOCS 2010: 61–70
Versions: Proceedings (pdf), full version forthcoming (see my thesis in the meantime), Talk (PDF, Video)
Short abstract: We consider privacy-preserving statistical data analysis with online queries. In this setting a trusted curator maintains a database of sensitive information about individual participants, and releases privacy-preserving answers to queries as they arrive online. Our primary contribution is a new differentially private multiplicative weights mechanism for answering a large number of counting queries that arrive online and may be adaptively chosen. Our mechanism is the first to achieve worst-case accuracy guarantees (accuracy on every input database) for a large number of online queries together with a runtime that is polynomial in the data universe. The error is optimal in its dependence on the size of the database and depends only logarithmically on the number of queries being answered. The runtime is nearly linear in the size of the data universe.
Our main technical contributions are a new application of multiplicative weights techniques to the differential privacy setting, and a new privacy analysis for multiplicative weights algorithms.
-
In Proc. of STOC 2010: 705–714
Versions: Technical Report (arXiv), Proceedings (DOI)
Short abstract: We give a connection between convex geometry and differentially private data analysis. Specifically, we study the noise complexity of differentially private mechanisms in the setting where the data is represented by a histogram and the user asks a number of linear queries non-adaptively. We show that the amount of noise necessary and sufficient to achieve differential privacy is determined by two geometric parameters of a convex body associated with the set of queries. We use this connection to give tight upper and lower bounds for random linear queries. Assuming the truth of a deep conjecture from convex geometry, known as the Hyperplane conjecture, we can extend our results to arbitrary linear queries giving nearly matching upper and lower bounds.
-
Manuscript.
Versions: Video lecture at IAS
Forster's lower bound (2001) on the sign rank of a matrix is a fundamental theorem in communication complexity with applications to learning theory. We give a short, arguably simpler and algorithmic proof of Forster's theorem.
Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors. We point out an efficient algorithm to compute the radial isotropic position of a given set of vectors when it exists. We believe that this may be of independent interest. Our algorithm builds on tools due to Barthe (1998) that are related to the equality cases of the generalized Brascamp-Lieb inequalities. -
In Proc. of SODA 2009: 1193–1200
-
In Proc. of FOCS 2008: 374–383
Versions: Preprint (pdf), Proceedings (DOI)
Short abstract: We show an essentially tight connection between the semidefinite programming relaxation of Unique Games and their behavior under parallel repetition. Our results generalize and help to explain Raz's refutation of the Strong Parallel Repetition Conjecture. Indeed, we show that a Unique Game is a counterexample to strong parallel repetition whenever its SDP value is significantly larger than its integral value.
-
In Proc. of ICALP (1) 2008: 345–356
-
In Inf. Process. Lett. 109(3): 187–192
See my DBLP entry for more information.
Thesis
-
Dissertation. Princeton University, 2011
Versions: PDF
Abstract: In this thesis we consider the challenges arising in the design of algorithms that interact with sensitive personal data---such as medical records, online tracking data, or financial records.
One important goal is to protect the privacy of those individuals whose personal information contributed to the data set. We consider algorithms that satisfy the strong privacy guarantee known as differential privacy. A wide range of computational tasks reduces to the setting in which a trusted database curator responds to a number of statistical queries posed by an untrusted data analyst. The basic question is how accurately and efficiently the curator can release approximate answers to the given queries while satisfying differential privacy. We make the following main contributions to differentially private data analysis:
- We expose a connection between differential privacy and certain problems in convex geometry revolving around a deep conjecture known as the Hyperplane conjecture. Assuming the truth of this conjecture we give differentially private mechanisms with nearly optimal accuracy in the case where the queries are given all at once (non-interactively) and the number of queries does not exceed the database size.
- Multiplicative weights mechanisms are a powerful tool in algorithms, machine learning and optimization. We introduce a privacy-preserving multiplicative weights framework suitable for answering a huge number of queries even in the interactive setting. The accuracy of our algorithm in terms of database size and number of queries matches the statistical sampling error that already arises in the absence of any privacy concerns. Our algorithm can also be used to produce a differentially private synthetic data set encoding the curator's answers. For this task the runtime of our algorithm---which is linear in the universe size---is essentially optimal due to a prior cryptographic hardness result.
- We then consider avenues for obtaining differentially private algorithms with a runtime polynomial in the size of the data set or at least subexponential in the universe size. Based on a new learning algorithm for submodular functions, we present the first polynomial-time algorithm for answering a large number of Boolean conjunction queries (or contingency tables) with non-trivial accuracy guarantees. Conjunction queries are a widely used and important class of statistical queries.
- Furthermore, we exhibit an explicit and efficient reduction from the problem of privately releasing a class of queries to the problem of non-privately learning a related class of concepts. Instantiating this general reduction with new and existing learning algorithms yields several new results for privately releasing conjunctions and other queries.
Not all problems arising in the presence of sensitive data are a matter of privacy. In the final part of this thesis, we isolate fairness in classification as a formidable concern and thus initiate its formal study. The goal of fairness is to prevent discrimination against protected subgroups of the population in a classification system. We argue that fairness cannot be achieved by blindness to the attribute we would like to protect. Our main conceptual contribution is in asserting that fairness is achieved when similar individuals are treated similarly. Based on the goal of treating similar individuals similarly, we formalize and show how to achieve fairness in classification, given a similarity metric. We also observe that our notion of fairness can be seen as a generalization of differential privacy.
