Research map / Federated learning and privacy / Differential privacy
Better Locally Private Sparse Estimation Given Multiple Samples Per User
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 user-level local differentially private sparse linear regression, showing that with multiple samples per user the dimension dependence can be removed (error O(s*^2/(nm eps^2))), via a select-then-estimate two-round protocol.
Problem
Item-level LDP sparse linear regression has minimax error scaling linearly with dimension d (O(sd/(nm eps^2))), which is prohibitive in high dimensions; the question is whether having multiple samples per user under user-level LDP removes this dependence.
Approach
Half the users run local variable selection (each sends one sampled selected index), a heavy-hitter protocol over a binary prefix tree identifies a candidate support of size O(s*), and the remaining users fit low-dimensional estimates on that support, which are aggregated privately via a histogram-bin projection plus Laplace noise in two rounds.
Key results
- Theory: two-round protocol achieves ||beta*-beta||_2^2 = O(s*^2/(nm eps^2)) under the eps-ULDP constraint, removing the linear dependence on d present in item-level LDP minimax rates.
- On real data at eps=1, the proposed 2-SLR and M-SLR obtain rank sums of 24 and 19 versus 56 for LDPPROX and 50 for LDPIHT (lower is better).
- In simulation, 2-SLR achieves higher variable-selection F1 than Lasso and its error remains less sensitive to d than LDPIHT and Lasso when m is large (m=200).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use 2-SLR instead of the LDP comparison methods | Sparse linear regression · Real datasets, ε=1 and ε=4 | MSE ratio | Helped |
| Use 2-SLR instead of local-only Lasso | Sparse linear regression · Synthetic data across the tested (n, m, ε) settings | ℓ2 error | Helped |
| Use M-SLR instead of local-only Lasso | Sparse linear regression · Synthetic data across the tested (n, m, ε) settings | ℓ2 error | Mixed |
| Increase ε | Private methods · Synthetic data | ℓ2 error | Helped |
| Use 2-SLR instead of M-SLR | Sparse linear regression · Synthetic data | ℓ2 error | Helped |
| Use M-SLR instead of 2-SLR | Sparse linear regression · Real data | MSE ratio | Helped |
| Increase the number of users n | 2-SLR and M-SLR · Synthetic data | ℓ2 error | Helped |
| Use 2-SLR candidate variable selection instead of variables induced by the comparison methods | Candidate variable selection · Synthetic data, varying d | F1 score | Helped |
Surprising findings
- The proposed methods sometimes outperform non-private Lasso on the full data, attributed to strong signal strength enabling better rates and to subsampled-Lasso aggregation.
- M-SLR outperforms 2-SLR on real data although 2-SLR is better in simulation, attributed to implicit regularization from zero initialization on noisy data.
Limitations
- Requires m large enough (roughly m >= s*log d) for the selection guarantees; small-m regime not analyzed.
- Theoretical bounds include extra log n and alpha factors, and the multi-round protocol uses many communication rounds (O(sqrt(nm eps^2))).
Experimental setup
Datasets: Airline Loan MIP Taxi Wine Yolanda synthetic Gaussian data
Benchmarks: Airline Loan MIP Taxi Wine Yolanda synthetic Gaussian simulation
Metrics: squared error (l2) F1 score for variable selection MSE ratio relative to non-private Lasso rank sum
Baselines: LDPPROX LDPIHT Lasso
Builds on: Lasso subsampling aggregation (stability selection) heavy hitter detection via prefix tree (Bassily et al.) LDP linear regression lower bounds
Closest papers by meaning
- Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model (ICLR 2024 · similarity 0.91)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.89)
- Differentially Private High-dimensional Variable Selection via Integer Programming (NeurIPS 2025 · similarity 0.89)
- Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation (ICML 2024 · similarity 0.88)
- Truthful High Dimensional Sparse Linear Regression (NeurIPS 2024 · similarity 0.88)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.88)
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.