Research map / Federated learning and privacy / Differential privacy
Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies sparse linear regression under local DP, giving k-sparse lower bounds and the first non-interactive LDP algorithm (closed-form soft-thresholded estimator), plus a corrected and improved LDP iterative hard thresholding bound for the sequentially interactive model.
Problem
Sparse linear regression estimation error under local differential privacy (non-interactive and sequentially interactive models), where prior work only handled 1-sparse lower bounds, had no efficient non-interactive algorithm, and had a flawed interactive upper bound.
Approach
Derive k-sparse lower bounds via a private Assouad's lemma over random sparse hard instances, and build a closed-form NLDP estimator by privately releasing clipped/shrunken second-moment statistics and applying soft-thresholding to the resulting OLS-like estimate; for the interactive model, correct and generalize LDP iterative hard thresholding with coordinate-wise shrinkage.
Key results
- Non-interactive LDP lower bound of Omega(sqrt(dk log d /(n eps^2))) for k-sparse sub-Gaussian data.
- Non-interactive LDP algorithm with error O~(d sqrt(k) / (sqrt(n) eps)) for sub-Gaussian data, improved to O~(sqrt(dk)/(sqrt(n) eps)) with public unlabeled data.
- Sequentially interactive lower bound Omega(sqrt(dk/(n eps^2))) and corrected LDP IHT upper bound O~(k sqrt(d)/(sqrt(n) eps)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use public unlabeled data to estimate the covariance matrix | Proposed NLDP estimator · NLDP with public unlabeled data, k-sparse sub-Gaussian | ℓ2 estimation error: improve the estimation error by a factor of O(\sqrt{d}) | Helped |
| Add the soft-thresholding operator (ablation) | Proposed NLDP estimator · NLDP, k-sparse sub-Gaussian | ℓ2 estimation error upper bound: \tilde{O}(\frac{d^{\frac{3}{2}}}{\sqrt{n}\epsilon}) versus \tilde{O}(\frac{d\sqrt{k}}{\sqrt{n}\epsilon}) | Helped |
| Correct the claimed sensitivity analysis for LDP Iterative Hard Thresholding | LDP Iterative Hard Thresholding · Sequentially interactive LDP, k-sparse | ℓ2 estimation error upper bound: \tilde{O}(\sqrt{\frac{dk}{n\epsilon^2}}) -> \tilde{O}(\frac{k\sqrt{d}}{\sqrt{n}\epsilon}) | Hurt |
Surprising findings
- The prior LDP iterative hard thresholding upper bound of O~(sqrt(dk)/(sqrt(n) eps)) is incorrect; the corrected rate is O~(k sqrt(d)/(sqrt(n) eps)).
Limitations
- Non-interactive upper bound is conjectured but not shown tight relative to the lower bound, leaving an open gap of about sqrt(d).
- Non-interactive upper bound requires n large enough and relies on the l1-norm assumption on theta*.
- Assumes kappa constants and sub-Gaussian covariates; the interactive result is stated for isotropic covariates in the main text.
Experimental setup
Metrics: l2-norm estimation error sample complexity lower bound
Baselines: LDP iterative hard thresholding (prior work) Gaussian-perturbed sufficient statistics 1-sparse NLDP lower bound
Builds on: LASSO Dantzig estimator LDP iterative hard thresholding private Assouad's lemma
Closest papers by meaning
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.91)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.88)
- On the Computational Complexity of Private High-dimensional Model Selection (NeurIPS 2024 · similarity 0.88)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.87)
- Truthful High Dimensional Sparse Linear Regression (NeurIPS 2024 · similarity 0.87)
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.