Research map / Federated learning and privacy / Differential privacy
Truthful High Dimensional Sparse Linear Regression
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.
Designs a closed-form, soft-thresholded JDP estimator for high-dimensional sparse linear regression with noisy sufficient statistics and hard-thresholded covariance, combined with a rescaled Brier peer-prediction payment rule to get a truthful, privacy-preserving, individually rational mechanism.
Problem
Fitting high-dimensional sparse linear regression (d >> n) when data come from strategic, privacy-concerned agents who may misreport responses, under one-round interaction, while preserving privacy, accuracy, truthfulness, individual rationality and small payment budget.
Approach
A closed-form private estimator S_lambda(Sigma_XX^{-1} Sigma_XY) built by adding Gaussian noise separately to clipped sufficient statistics, hard-thresholding the noisy covariance to ensure invertibility, and a peer-prediction payment using the rescaled Brier score with a two-group split.
Key results
- Mechanism is (O(n^{-xi}), O(n^{-Omega(1)}))-JDP with xi in (1/3,1/2), per the corollary.
- Truthful reporting is an O~(n^{-xi-1})-Bayesian Nash equilibrium for a 1-O(n^{-3xi}) fraction of agents.
- Estimator error is O~(n^{2xi-1}) and total expected payment budget is O~(n^{1-3xi}), both vanishing as n grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sufficient-statistics perturbation instead of output perturbation | Private high-dimensional sparse linear regression · High-dimensional sparse linear regression | estimation error dependence on dimension | Helped |
| Hard-threshold the noisy covariance matrix | Private high-dimensional sparse linear regression estimator · Sparse covariance estimation | covariance estimation error | Helped |
Limitations
- Mechanism is not individually rational for all agents because privacy cost coefficients have unbounded exponential-decay tails.
- One-round communication constraint remains; the analysis follows prior truthful-regression frameworks.
- Theoretical results rely on sparsity and sub-Gaussian assumptions; no empirical experiments are reported.
Experimental setup
Metrics: l2 estimation error epsilon-Bayes Nash equilibrium gap individual rationality fraction total payment budget
Baselines: ridge-regression-based truthful linear regression OLS-based truthful linear regression
Builds on: joint differential privacy peer prediction rescaled Brier score output perturbation for truthful linear regression
Closest papers by meaning
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.88)
- On the Computational Complexity of Private High-dimensional Model Selection (NeurIPS 2024 · similarity 0.87)
- Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model (ICLR 2024 · similarity 0.87)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.87)
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination (NeurIPS 2025 · similarity 0.86)
- Stochastically Dominant Peer Prediction (NeurIPS 2025 · 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.