Scaling Up Differentially Private LASSO Regularized Logistic Regression
  via Faster Frank-Wolfe Iterations
Edward Raff Amol Khanna Fred Lu
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.