  Linear $L_1$-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
$L_1$ 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 $L_1$ screening
method is an open problem in the differential privacy literature.

Machine Learning;Cryptography and Security