# Better Locally Private Sparse Estimation Given Multiple Samples Per User

arXiv: https://arxiv.org/abs/2408.04313 · HTML: https://mlsanity.com/paper/2408.04313/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 72 references that are in the map.
- First posted on arXiv 8 Aug 2024.

## Builds on (most cited first, 30 of 35)

- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Position: Considerations for Differentially Private Learning with Large-Scale Public Pretraining](https://mlsanity.com/paper/2212.06470/) (2022)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [A Continuous-Time View of Early Stopping for Least Squares](https://mlsanity.com/paper/1810.10082/) (2018)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Learning discrete distributions: user vs item-level privacy](https://mlsanity.com/paper/2007.13660/) (2020)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Federated Heavy Hitters Discovery with Differential Privacy](https://mlsanity.com/paper/1902.08534/) (2019)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible](https://mlsanity.com/paper/1706.03316/) (2017)
- [On User-Level Private Convex Optimization](https://mlsanity.com/paper/2305.04912/) (2023)
- [Mean Estimation with User-level Privacy under Data Heterogeneity](https://mlsanity.com/paper/2307.15835/) (2023)
- [Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations](https://mlsanity.com/paper/2310.19978/) (2023)
- [Optimal Locally Private Nonparametric Classification with Public Data](https://mlsanity.com/paper/2311.11369/) (2023)
- [The Challenge of Differentially Private Screening Rules](https://mlsanity.com/paper/2303.10303/) (2023)
- [Rate Optimality and Phase Transition for User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.11923/) (2024)
- [Locally Differentially Private Sparse Vector Aggregation](https://mlsanity.com/paper/2112.03449/) (2021)
- [Differentially Private Empirical Risk Minimization with Sparsity-Inducing Norms](https://mlsanity.com/paper/1905.04873/) (2019)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [Differentially Private Estimation and Inference in High-Dimensional Regression with FDR Control](https://mlsanity.com/paper/2310.16260/) (2023)

## Built on by (most cited first, 1 of 1)

- [PrAda-GAN: A Private Adaptive Generative Adversarial Network with Bayes Network Structure](https://mlsanity.com/paper/2511.07997/) (2025)

## Abstract (arXiv)

Previous studies yielded discouraging results for item-level locally differentially private linear regression with s^*-sparsity assumption, where the minimax rate for nm samples is O(s*d / nmvarepsilon2). This can be challenging for high-dimensional data, where the dimension d is extremely large. In this work, we investigate user-level locally differentially private sparse linear regression. We show that with n users each contributing m samples, the linear dependency of dimension d can be eliminated, yielding an error upper bound of O(s*2 / nmvarepsilon2). We propose a framework that first selects candidate variables and then conducts estimation in the narrowed low-dimensional space, which is extendable to general sparse estimation problems with tight error bounds. Experiments on both synthetic and real datasets demonstrate the superiority of the proposed methods. Both the theoretical and empirical results suggest that, with the same number of samples, locally private sparse estimation is better conducted when multiple samples per user are available.