  Differential Privacy offers strong guarantees such as immutable privacy under
post processing. Thus it is often looked to as a solution to learning on
scattered and isolated data. This work focuses on supervised manifold learning,
a paradigm that can generate fine-tuned manifolds for a target use case. Our
contributions are two fold. 1) We present a novel differentially private method
\textit{PrivateMail} for supervised manifold learning, the first of its kind to
our knowledge. 2) We provide a novel private geometric embedding scheme for our
experimental use case. We experiment on private "content based image retrieval"
- embedding and querying the nearest neighbors of images in a private manner -
and show extensive privacy-utility tradeoff results, as well as the
computational efficiency and practicality of our methods.
