Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations

Summary

This paper studies how to equip differential priavate (DP) Frank Wolfe (FW) with the ability to cope with sparse data. The key insights are the proper priority queue data structures for handling the FW subproblem. To this end, a Fibonacci queue is proposed for non DP cases, and a big-step little-step sampler is designed for DP cases. The complexities of proposed approaches has improved dependence on N and D. Numerical results also suggests embracing sparsity fastens practical performance on large datasets.

Strengths

(+) The proposed data structures are useful for handling sparse data for DP-FW. It provides a much better computation complexity with improved N and D dependence. (+) Empirically, the smart use of these data structures leads to significantly faster performance that is up to 20x - 30x. Here I am comparing Alg. 2 + 4 with Alg. 2, since Alg. 2 is possibly a more reasonable benchmark if hopes to advance FW with sparsity. (+) The numerical improvement tends to be more significant given a smaller $\epsilon$. This is helpful for settings with high requirement on privacy.

Weaknesses

1.On the highlevel, this work focuses on developing efficient data structures for solving FW subproblem (in DP setting). Comparison with other data structures, such as those locality sensitive hashing ones https://arxiv.org/abs/2111.15139, is missing. 2.Can the proposed method benefit other FW approaches, such as https://arxiv.org/abs/2110.04243 3.The assertion in line 19 should be demonstrated more carefully.

Questions

See weakness.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

The paper presents an approach to train differentially private regression models on sparse input data. It leverages a modified version of the Frank-Wolfe algorithm to reduce the training time significantly by making the algorithm sensitive to sparse inputs.The algorithmic complexity is improved from the standard linear complexity to sub-linear. The authors have used their proposed method on multiple high-dimensional datasets improving the accuracy by 26.3% compared to previous methods.

Strengths

The paper is eloquently written, with algorithms clearly delineated and accompanied by ample commentary. The proposed algorithm showcases its versatility across various scenarios, offering a remarkable improvement in performance.

Weaknesses

The paper does not provide proven error bounds, and all theoretical results appear to revolve around the concept of speed optimization. It remains unclear whether this speed enhancement comes at the expense of accuracy. Additionally, the lack of released code poses a challenge to reproducibility. Privacy accounting is implict and lacking, the authors didn't directly explain how does their algorithm satisfy the DP condition (advanced compostion?).

Questions

Could you please clarify how the proposed algorithm ensures compliance with the Differential Privacy (DP) condition? Are there any alternative privacy accounting methods that may potentially enhance the overall performance? For example, better privacy accounting [1], using GDP/RDP [2] or tighter compostion theorems [3]. The authors suggest that their implementation requires fewer FLOPs compared to the standard Frank-Wolfe approach. Does this reduction in FLOPs translate directly to a commensurate speed increase, or is computational efficiency still constrained by factors such as RAM and cache access? Could you elaborate on the current computational bottlenecks? The experimentation appears to have been conducted using a single core. Would there be any potential benefits, such as efficiency or performance improvements, if this method were to be adapted for multicore processing? Can this method be extended beyond LASSO Regularized Logistic Regression? If not, what's the main challenge? [1]: Altschuler, J., & Talwar, K. (2022). Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 35, 3788-3800. [2] Liu, Y., Sun, K., Jiang, B., & Kong, L. (2022). Identification, amplification and measurement: A bridge to gaussian differential privacy. Advances in Neural Information Processing Systems, 35, 11410-11422. [3] Kairouz, P., Oh, S., & Viswanath, P. (2015, June). The composition theorem for differential privacy. In International conference on machine learning (pp. 1376-1385). PMLR.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See weakness.

Summary

This paper proposes new private variants of the Frank-Wolfe algorithm that takes advantage of the sparsity in the data. The proposed methods are shown to significantly speed up Frank-Wolfe algorithm in a multitude of tasks while still achieving similar accuracy.

Strengths

- The authors make an effort to explain a lot of what is going on in their algorithm. - Since the result of the paper is about reducing computational complexity, I appreciate that the author denotes the complexity of every operation in their algorithms. - The proposed method seems to do well in practice. The speed-up is quite significant.

Weaknesses

- Even though I appreciate the effort the author put in to explain their algorithms, I still feel like the explanation is very confusing. The paper would really benefit if the author can add a bit more discussion in the appendix to make things a bit clearer. - Some of the technical terms are used in the paper before being defined properly. For example, the term FLOPs is used in line 187 but only is defined in line 319. Or the Fibonacci Heap is used without even having a few sentences defining what it is. Again, I think the author should consider having more discussions in the appendix. - Section 3.3 presents a private algorithm without having a Theorem showing that the algorithm is $\epsilon$-DP. - Figure 1 and 2 are very confusing. For example, in the caption of Figure 1, it says that Algorithm 2 is the dotted line but every line is a dotted line. The legend of the chart also does not have either Algorithm 2 or Algorithm 1. - The authors use the phrase "handle something sparsely" often but it is a bit unclear what it means. Maybe explain it in the beginning or say something like "allow us to handle the update in 1 dimension"?

Questions

- In Algorithm 1, what do we need $g_t$ for? It isn't used anywhere else in the algorithm. Based on the experiment, seems like the authors want to output $g_t$ as the convergence gap, then the algorithm should output both $w_T$ and $g_t$? - I'm a bit confused about the statement in line 139. Isn't $\bar v_t^{(i)} = \sum_{j=1}^dX^{i,j}w_t^{j}$. Thus, when 1 single coordinate of $w_t$ changes, every $\bar v_t^{(i)}$ will also change? - Can the author explain how using $\gamma$ to update allow us to not use $\bar y$ anymore? - What are $\textbf{c}$ and $z_\Sigma$ in Algorithm 4? Those 2 are used without being defined. - What is the sparsity of the data used in the experiments?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

N/A

Summary

This paper studies DP regression problem when the data is $\ell_1$-sparse and aims to improve the computational efficiency. Specifically, they consider LASSO regularized logistic regression model and sparse aware Frank-Wolfe algorithm. The proposed method computes mathematical equivalent results as in the original algorithms but computationally much more efficient for large sparse datasets. The experiments confirm that the proposed methods are significant faster than existing methods.

Strengths

1. This paper provides a practical tool for DP regression on large sparse datasets. Prior works on sparse regressions are either purely theoretical or non-scalable. As far as I know, this is the first paper that focus on the computational efficiency. 2. This paper is well-written and clearly states its contribution.

Weaknesses

This paper does not discuss any utility guarantees in terms of its theoretical dependence on $d, \lambda, L, \varepsilon, n$. I am uncertain about the performance of sparse-aware DP Frank-Wolfe on this problem. Previous work [1] is known to be near-optimal in terms of utility. If the proposed method is sub-optimal, accelerating a sub-optimal algorithm may be of less interest. [1] Cai, T.T., Wang, Y., and Zhang, L. (2021). The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5), 2825-2850.

Questions

Please see weakness

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

This paper has not addressed the limitations.