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.
Figures & tables
Figure 1: ση -dependence of (a) the fraction of nonzero components in the estimator and (b) the generalization error for various regularization parameters λ under objective perturbation. Circles ( ∘ ) denote AMP results and solid lines show the corresponding analysis by replica method. In the AMP experiments, we set p=1000 , α=0.5 , ρ=0.1 , and σξ=0.1 . AMP results are averaged over 100 datasets; error bars indicate the standard error. For each dataset, a single realization of privacy noise η is generated. The dashed lines in (b) shows the generalization error under output perturbation.
Figure 2: (a) λ -dependence of the generalization error for different privacy noise levels ( ση=0.1 , 0.3 ) compared with the noiseless case. (b) Generalization error as a function of the resulting ρ . The experimental setup and plotting style are the same as in Fig. 1 .
Figure 3: (a) Dependence of the ratio between generalization and training errors on ρ at ρ=0.1 , σξ=1 , and ση=0.1 , for α=0.5 and α=0.3 , as predicted by state evolution in the high-dimensional limit. Circles represent the AMP results. (b) Parameter region where AMP does not converge at α=0.5 , ρ=0.5 and σξ=0.1 . The solid line denotes the boundary predicted by the replica method, circles and squares indicate the empirical convergence limit of AMP, and squares indicate that of coordinate descent. For both AMP and coordinate descent, convergence was evaluated over 100 independent runs, and a point is marked as non-convergent if at least one run fails to converge.
Figure 4: Comparison of distribution of the estimators with respect to data by AMP ( ∘ ) and DE (boxes) at α=0.5 , ρ=0.3 , σξ=0.1 , λ=0.5 and ση=0.1 . Distributions for different β(0) and η are shown: (a) β(0)=1.0629,η=0.0460 , (b) β(0)=−1.0412,η=−0.0238 , (c) β(0)=−2.1796,η=−0.0079 , (d) β(0)=2.1290,η=−0.0317 , (e) β(0)=3.2188,η=0.0556 , (f) β=−3.2333,η=−0.0321 , (g) β(0)=−1.0095,η=0.2907 , (h) β(0)=0.1017,η=−0.3261 , (i) β(0)=0,η=0.3579 , (j) β(0)=0,η=−0.3233 .
Figure 5: Examples of the distributions of the AMP estimates induced by the injected privacy noise (solid lines) and the corresponding SE predictions (dashed lines) at α=0.5 , ρ=0.5 , σy=0.1 , λ=1 , and ση=0.5 . For AMP, we set N=500 , and 1000 realizations of the objective noise are used in the computation. Panels (a)-(f) correspond to β(0)=0 , 0.3554 , 1.308 , −1.279 , 2.191 , and −2.432 , respectively. The circle at β=0 indicates the height of the peak of the AMP distribution.
Figure 6: cwOnAveKL under output perturbation as a function of the noise strength ση for different parameter settings: (a) α=0.5 , ρ=0.1 , (b) α=0.5 , λ=1 , and (c) ρ=0.1 , λ=1 . The observation noise strength is set to σξ=0.1 .
Figure 7: cwOnAveKL under objective perturbation as a function of the noise strength ση for different parameter settings: (a) α=0.5 , ρ=0.1 , (b) α=0.5 , λ=1 , and (c) ρ=0.1 , λ=1 . The observation noise strength is set to σξ=0.1 .
Figure 8: Privacy-accuracy trade-off at α=0.5 , ρ=0.1 , and σξ=0.1 for (a) output and (b) objective perturbation. The vertical dashed lines represent the generalization error in the noiseless case, and circles denote the points closest to the origin. The inset in (b) magnifies the curve around the minimum.
Figure 9: (a) Optimal noise strength under output perturbation at α=0.5 and σξ=0.1 for different values of ρ . (b) Optimal noise strength under objective perturbation under the same conditions.
Figure 10: Generalization error (a) and cwOnAveKL (b) at the optimal noise strength, for α=0.5 , ρ=0.1 , and σξ=0.1 .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 11: Graphical representation of the privacy-preserving LASSO with n=4 and p=6 .