Privacy-Accuracy Trade-offs in High-Dimensional LASSO under Perturbation Mechanisms
This work addresses privacy-accuracy trade-offs for high-dimensional data analysis, offering insights into differential privacy mechanisms, but it is incremental as it builds on existing AMP frameworks and privacy methods.
The paper tackles privacy-preserving sparse linear regression in high-dimensional settings using LASSO with differential privacy mechanisms, revealing that sparsity stabilizes estimators against data changes and that objective perturbation can have non-monotonic effects with excessive noise.
We study privacy-preserving sparse linear regression in the high-dimensional regime, focusing on the LASSO estimator. We analyze two widely used mechanisms for differential privacy: output perturbation, which injects noise into the estimator, and objective perturbation, which adds a random linear term to the loss function. Using approximate message passing (AMP), we characterize the typical behavior of these estimators under random design and privacy noise. To quantify privacy, we adopt typical-case measures, including the on-average KL divergence, which admits a hypothesis-testing interpretation in terms of distinguishability between neighboring datasets. Our analysis reveals that sparsity plays a central role in shaping the privacy-accuracy trade-off: stronger regularization can improve privacy by stabilizing the estimator against single-point data changes. We further show that the two mechanisms exhibit qualitatively different behaviors. In particular, for objective perturbation, increasing the noise level can have non-monotonic effects, and excessive noise may destabilize the estimator, leading to increased sensitivity to data perturbations. Our results demonstrate that AMP provides a powerful framework for analyzing privacy-accuracy trade-offs in high-dimensional sparse models.