Privately Learning Subspaces Anonymous Author(s) Affiliation Address email

Private data analysis suffers a costly curse of dimensionality. However, the data1 often has an underlying low-dimensional structure. For example, when optimizing2 via gradient descent, the gradients often lie in or near a low-dimensional subspace.3 If that low-dimensional structure can be identified, then we can avoid paying (in4 terms of privacy or accuracy) for the high ambient dimension.5 We present differentially private algorithms that take input data sampled from6 a low-dimensional linear subspace (possibly with a small amount of error) and7 output that subspace (or an approximation to it). These algorithms can serve as a8 pre-processing step for other procedures.9