# The Challenge of Differentially Private Screening Rules

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 16 references that are in the map.
- First posted on arXiv 18 Mar 2023.

## Builds on (most cited first, 4 of 4)

- [A Safe Screening Rule for Sparse Logistic Regression](https://mlsanity.com/paper/1307.4145/) (2013)
- [Differentially Private Model Selection with Penalized and Constrained Likelihood](https://mlsanity.com/paper/1607.04204/) (2016)
- [Differential Privacy for Sparse Classification Learning](https://mlsanity.com/paper/1908.00780/) (2019)
- [Lower-Cost epsilon-Private Information Retrieval](https://mlsanity.com/paper/1604.00223/) (2016)

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

- [Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations](https://mlsanity.com/paper/2310.19978/) (2023)
- [SoK: A Review of Differentially Private Linear Models For High-Dimensional Data](https://mlsanity.com/paper/2404.01141/) (2024)
- [High-Dimensional Distributed Sparse Classification with Scalable Communication-Efficient Global Updates](https://mlsanity.com/paper/2407.06346/) (2024)
- [Feature Selection from Differentially Private Correlations](https://mlsanity.com/paper/2408.10862/) (2024)
- [Better Locally Private Sparse Estimation Given Multiple Samples Per User](https://mlsanity.com/paper/2408.04313/) (2024)
- [Position: Challenges and Opportunities for Differential Privacy in the U.S. Federal Government](https://mlsanity.com/paper/2410.16423/) (2024)

## Abstract (arXiv)

Linear L1-regularized models have remained one of the simplest and most effective tools in data analysis, especially in information retrieval problems where n-grams over text with TF-IDF or Okapi feature values are a strong and easy baseline. Over the past decade, screening rules have risen in popularity as a way to reduce the runtime for producing the sparse regression weights of L1 models. However, despite the increasing need of privacy-preserving models in information retrieval, to the best of our knoweledge, no differentially private screening rule exists. In this paper, we develop the first differentially private screening rule for linear and logistic regression. In doing so, we discover difficulties in the task of making a useful private screening rule due to the amount of noise added to ensure privacy. We provide theoretical arguments and experimental evidence that this difficulty arises from the screening step itself and not the private optimizer. Based on our results, we highlight that developing an effective private L1 screening method is an open problem in the differential privacy literature.