mlsanityData to 7 Oct 2026

Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model

arXiv 2310.07367 ↗First posted 11 Oct 2023cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

In this paper, we revisit the problem of sparse linear regression in the local differential privacy (LDP) model. Existing research in the non-interactive and sequentially local models has focused on obtaining the lower bounds for the case where the underlying parameter is 1-sparse, and extending such bounds to the more general k-sparse case has proven to be challenging. Moreover, it is unclear whether efficient non-interactive LDP (NLDP) algorithms exist. To address these issues, we first consider the problem in the ε non-interactive LDP model and provide a lower bound of Omega(frac√dklog d√nε) on the ℓ2-norm estimation error for sub-Gaussian data, where n is the sample size and d is the dimension of the space. We propose an innovative NLDP algorithm, the very first of its kind for the problem. As a remarkable outcome, this algorithm also yields a novel and highly efficient estimator as a valuable by-product. Our algorithm achieves an upper bound of tildeO(fracd√k√nε) for the estimation error when the data is sub-Gaussian, which can be further improved by a factor of O(√d) if the server has additional public but unlabeled data. For the sequentially interactive LDP model, we show a similar lower bound of Omega(frac√dk√nε). As for the upper bound, we rectify a previous method and show that it is possible to achieve a bound of tildeO(frack√d√nε). Our findings reveal fundamental differences between the non-private case, central DP model, and local DP model in the sparse linear regression problem.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 31 of its 56 references that are in the map. First posted on arXiv 11 Oct 2023.

Builds on

31 of 56 references.

References · 31

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  3. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  4. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  5. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  6. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  7. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  8. 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 60
  9. 2017Adaptive Huber Regressioncited by 59
  10. 2014On Iterative Hard Thresholding Methods for High-dimensional M-Estimationcited by 53
  11. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  12. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
19 more
  1. 2017Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12cited by 42
  2. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  3. 2020Differentially Private Simple Linear Regressioncited by 33
  4. 2013Local Privacy, Data Processing Inequalities, and Statistical Minimax Ratescited by 26
  5. 2016A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recoverycited by 23
  6. 2020Unified lower bounds for interactive high-dimensional estimation under information constraintscited by 22
  7. 2017Heavy Hitters and the Structure of Local Privacycited by 20
  8. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 19
  9. 2017Differentially private significance tests for regression coefficientscited by 12
  10. 2017Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possiblecited by 12
  11. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  12. 2022High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantizationcited by 11
  13. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  14. 2018Locally Private Learning without Interaction Requires Separationcited by 7
  15. 2022The Role of Interactivity in Structured Estimationcited by 7
  16. 2022Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recoverycited by 7
  17. 2022(Nearly) Optimal Private Linear Regression via Adaptive Clippingcited by 6
  18. 2022Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regressioncited by 6
  19. 2022On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Datacited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  2. 2024Better Locally Private Sparse Estimation Given Multiple Samples Per Usercited by 1
  3. 2025Differentially Private Sparse Linear Regression with Heavy-tailed Responsescited by 1
  4. 2026A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learningcited by 0