Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations
This work addresses a gap in differentially private machine learning for sparse data, offering a scalable solution with significant speed improvements, though it is incremental as it builds on existing Frank-Wolfe methods.
The paper tackles the problem of training differentially private regression models on sparse input data by adapting the Frank-Wolfe algorithm for L1 penalized linear regression to be aware of sparsity, resulting in runtime reductions of up to 2,200× depending on privacy parameters and dataset sparsity.
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 $ε$ and the sparsity of the dataset.