Title: Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible,
Abstract: Non-interactive Local Differential Privacy (LDP) requires data analysts to
collect data from users through noisy channel at once. In this paper, we extend
the frontiers of Non-interactive LDP learning and estimation from several
aspects. For learning with smooth generalized linear losses, we propose an
approximate stochastic gradient oracle estimated from non-interactive LDP
channel, using Chebyshev expansion. Combined with inexact gradient methods, we
obtain an efficient algorithm with quasi-polynomial sample complexity bound.
For the high-dimensional world, we discover that under $\ell_2$-norm assumption
on data points, high-dimensional sparse linear regression and mean estimation
can be achieved with logarithmic dependence on dimension, using random
projection and approximate recovery. We also extend our methods to Kernel Ridge
Regression. Our work is the first one that makes learning and estimation
possible for a broad range of learning tasks under non-interactive LDP model.