  To the best of our knowledge, there are no methods today for training
differentially private regression models on sparse input data. To remedy this,
we adapt the Frank-Wolfe algorithm for $L_1$ penalized linear regression to be
aware of sparse inputs and to use them effectively. In doing so, we reduce the
training time of the algorithm from $\mathcal{O}( T D S + T N S)$ to
$\mathcal{O}(N S + T \sqrt{D} \log{D} + T S^2)$, where $T$ is the number of
iterations and a sparsity rate $S$ of a dataset with $N$ rows and $D$ features.
Our results demonstrate that this procedure can reduce runtime by a factor of
up to $2,200\times$, depending on the value of the privacy parameter $\epsilon$
and the sparsity of the dataset.
