Differentially-private learning of low dimensional manifolds

Anna Choromanska, Krzysztof Choromanski, Geetha Jagannathan, Claire Monteleoni

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper, we study the problem of differentially-private learning of low dimensional manifolds embedded in high dimensional spaces. The problems one faces in learning in high dimensional spaces are compounded in differentially-private learning. We achieve the dual goals of learning the manifold while maintaining the privacy of the dataset by constructing a differentially-private data structure that adapts to the doubling dimension of the dataset. Our differentially-private manifold learning algorithm extends random projection trees of Dasgupta and Freund. A naive construction of differentially-private random projection trees could involve queries with high global sensitivity that would affect the usefulness of the trees. Instead, we present an alternate way of constructing differentially-private random projection trees that uses low sensitivity queries that are precise enough for learning the low dimensional manifolds. We prove that the size of the tree depends only on the doubling dimension of the dataset and not its extrinsic dimension.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings
Number of pages15
StatePublished - 2013
Event24th International Conference on Algorithmic Learning Theory, ALT 2013 - Singapore, Singapore
Duration: Oct 6 2013Oct 9 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8139 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other24th International Conference on Algorithmic Learning Theory, ALT 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Differentially-private learning of low dimensional manifolds'. Together they form a unique fingerprint.

Cite this