Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
This work addresses privacy-preserving data analysis for users under non-interactive local differential privacy, representing a foundational advancement rather than an incremental improvement.
The paper tackles the challenge of enabling non-interactive locally private learning by proposing methods for smooth generalized linear losses and high-dimensional tasks, achieving quasi-polynomial sample complexity and logarithmic dimension dependence.
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.