(Amplified) Banded Matrix Factorization: A unified approach to private training

Summary

Applying matrix factorization mechanism and balancing tradeoffs of the mechanism in differential privacy is a long living issue. This work constructs MF mechanism with banded matrices for both centralized and federated training setting across all privacy budgets. For federated setting, this work is compatible with real world federated learning devices. For centralized setting, banded matrices are on par with the same privacy amplification results of DP-SGD algorithm.

Strengths

1. Banded matrix factorization with amplification can outperform DP-SGD with amplification for centralized setting, and well-balance privacy-utility tradeoffs. 2. With b-min-sep-participation, banded MF can optimize (k,b)-participation, and reduce linear memory/time complexity for per-iteration noise generation to a constant.

Weaknesses

1. The bound of sensitivity of MF mechanism looks confusing although the first part looks tight (sup for C*x and C*x_tilde). See Question 5. 2. Although this work considers FL in the practice, the dataset like CIFAR 10 seems quite outdated and the scale of CIFAR10 is too small, which is not enough to convince the community. 3. Probably authors need to clarify questions I stated in the next sections.

Questions

1. Can you compare advantages and disadvantages of banded and unbanded matrix factorization for DP in FL setting? 2. In the Theorem 1, what is n? Is n the number of iterations or other things else? 3. In the Figure 1, it is hard to tell the difference of performance of Banded MF w/ amplification and multi-epoch MF w/o amplification. Why do you need amplification? What does the benefit of amplification for banded MF? 4. What does the \zeta mean for multiple participations? How does the \zeta affect the participations? 5. What is relationship between x, x tilde and u in equation 2?

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

2 fair

Limitations

1. This work has limited contribution on DP, because this work is more like an incremental work for multiple-epoch MF-DP-FTRL based on Choquette-Choo et al’s work to extend to federated learning setting. 2. It is not clear why we should assume in the cross-device FL setting, (k,b)-participation is not feasible. I know it is good to have some assumptions in the real world. However, I am wondering if it is necessary to restrict the scenario into such the practical case. 3. The MF optimization problem looks interesting and promising, but this work still needs more experiments, especially more datasets (at least three and other than small datasets like CIFAR10).

Summary

In this paper, the authors show how Matrix Factorization (MF) can subsume prior state-of-the-art algorithms in both federated and centralized training settings, across all privacy budgets. They apply the key technique: MF mechanisms with banded matrices. For both the cross-device federated learning setting and the centralized setting, the result in this paper improves or generalizes previous results. In addition, the $\hat{b}$-banded matrices substantially improve the memory and time complexity.

Strengths

1. The problem of Matrix Factorization for Differential privacy is well-motivated. 2. This paper is solid, the results look correct. 3. The result improves or generalizes previous results.

Weaknesses

The main result for the centralized setting is summarized in Section 5. However, it seems the result for federated learning setting is not stated clearly. Is there a summary of the result for FL setting?

Questions

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

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

No

Summary

This paper proposes banded matrix factorization for differential privacy. It shows this new mechanism can be effectively applied to centralized and federated-learning settings (where individuals can choose when and how many times to participate in training). The main technical part is the $b$-minsep-participation schema that generalizes the $(k, b)$-participation proposed in Choquette-Choo et al.

Strengths

The experiments in Sec 6 demonstrate that banded MF exhibits a very good improvement over multi-epoch MF and DP-SGD in the centralized settings, and almost coincides with (or improves modestly) the state-of-the-art performance in the federated learning.

Weaknesses

While the presentation of the paper is good for the most part, there are some issues that can be improved. For instance, the notation $\hat b$-banded matrices were used several times in the Abstract, Introduction, and Sec 2 without a precise (or even intuitive) definition [It was defined on Page 5!]. Also, $\hat b$ and $b$ seem to be interchanged arbitrarily (which is really confusing); see for instance lines 62, 188, 189. (I understand that $\hat b$ is taken to be equal to $b$ only in Sec 5, but not necessarily in the first 4 sections) Also, Theorem 1 is rather cryptic: Do the "equal-sized subsets" mean batches of the same size? Does the partition change for each iteration (like typical SGD)? Is it not the case that $B b = m$? This sentence (line 89-90) "The connection between DP empirical risk minimization [3, 4, 5, 7, 8, 9, 13, 15, 21, 23, 30, 34, 36,90 40, 45, 46, 47, 49] and DP online regret minimization [2, 4, 5, 24, 31, 33] has been studied for a long time." is awkward. What is the point of this sentence? Why not directly citing some of those works that studied this connection!! What is SGDM in lines 95 and 101? The argument in line 213 is not clear: How does Theorem 2 imply that $\text{diag}(X) = 1$ and bandedness mean the squared sensitivity is equal to $k$?

Questions

Can the authors clarify the argument given in line 224: "Since we only have equality constraints on 224 individual entries of $X$, Problem 2 is essentially an unconstrained optimization problem"? Are you saying that any constrained optimization problems with equality constraints are essentially unconstrained?

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

3 good

Limitations

Yes

Summary

The authors present a novel mechanism explicitly designed for differentially private training. The mechanism considers the sensitivity of different participation schemes in the context of fixed datasets during differentially private training. The key contributions of this work can be summarised as follows: 1. By accounting for the sensitivity of multistep participation schemes, the proposed mechanism eliminates the need for composition. 2. The authors illustrate how matrix factorisation can benefit from privacy amplification through subsampling and shuffling. 3. They propose a computationally efficient and precise implementation utilising b-banded matrices to compute sensitivity. 4. Additionally, they introduce an optimisation technique to craft these b-banded matrices. The authors provide theoretical proofs and compelling experimental results to support their claim that their approach outperforms DP-SGD accounting.

Strengths

* The paper effectively presents the problem, the proposed solution has a nice and clear structure, and the arguments flow in a natural way. * The related work is well-presented, providing context and the existing related work gap, namely if the matrix factorization can benefit from the same privacy amplification techniques as DP-SGD. * The experimental section is detailed, offering thorough explanations and interpretations of the results. * The paper elegantly recovers privacy amplification bounds from DP-SGD by carefully constructing the proposed linear operator.

Weaknesses

* the current presentation is not self-contained, as it has plenty of references to the appendix/other related work. It is not ideal, as the main statements of the paper are a bit hard to fully understand without them. I know that space is a limiting issue, especially for well-detailed works like this, but please reconsider restructuring so that the main results (Theorem 2. and Theorem 4.) are possibly more easily to grasp without relying on the appendix this much.

Questions

* More of a high-level question for the authors. In this scenario in which composition is bypassed altogether, why is the Gaussian Mechanism the "defacto" mechanism? I might miss something, but I always associate the Gaussian mechanism with composition + l2 sensitivity. It seems the authors have some space to explore other mechanisms (possibly). I was curious if the authors thought more in detail about this; is the Gaussian mechanism optimal in this scenario? * A unique perspective on this paper is that most amplification techniques are derived by analysing the linear operator itself and not analysing the output distributions (common, for example, for the subsampled Gaussian mechanism). This is a very interesting view of this work, as it abstracts the noise distribution from the privacy amplification guarantees, giving a more general/decoupled view of privacy amplification in this case. Do the authors think it is possible to design linear operators further to improve privacy guarantees/utility tradeoffs (like other forms of amplification given by the operator's structure), or have we reached some optimal design?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed 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

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

* Increased $O(b)$ multiplicative time/memory overhead compared to DP-SGD.

Summary

The paper studies the problem of how to optimize the Matrix factorization (MF) mechanisms so that the effect of random noise can be minimized. The MF mechanisms can be applied in addition to the well-known DP-FTRL or similar online DP algorithms in machine learning training. This technique decomposes the query matrix A (e.g., a matrix encoding the prefix sum) into two matrices and adds noise to the intermediate matrix multiplicative result of the data and one of the decomposed matrices. It can potentially introduce less variance to the final results. The key idea of the paper is formulating the MF problem into an optimization problem. The authors show the sensitivity of the mechanism under some constraints of the participation schema and discuss how to derive the best decomposition in terms of minimizing the error profile because of the decomposition. Some experimental results are provided to demonstrate that the proposed mechanism is at least as good as the classic DP-SGD mechanism.

Strengths

Generally speaking, this paper provides some in-depth results on the MF mechanism that can be interesting to the community. 1. The authors provide an insightful analysis angle on how to optimize the MF mechanism. 2. The authors derive the sensitivity of the MF mechanism under some additional assumptions about the participation schema of the users and the property of the original query matrix. 3. The authors show how one should optimize the MF mechanism via decomposition and how the mechanism can enjoy privacy amplification via sub-sampling.

Weaknesses

1. While the technical contributions are sufficient for building a good paper, the presentation in this paper makes readers somehow hard to follow. - MF mechanism is relatively new compared with the other DP mechanisms. So MF may be ambiguous if a reader is not familiar with the ancestors of this work (i.e., [14, 16]), as some readers may be confused DP MF problems (e.g. [1*, 2*]) with the MF mechanism at the first glance. Introducing problem formulation in (the beginning of) the introduction section may help readers evaluate and understand the value of the paper. - The explanation of why the MF mechanism can help and how the proposed methods are derived in this paper is not easy to follow. - It is unclear what are benefits one can get by following the participation schema and decomposition method proposed methods. There may be some discussion scattered around the paper, but a summary (via a table) comparing the results of this paper to the existing ones may deliver the results more directly to the readers. - The key algorithms are most deferred to the appendix. So main text itself is not self-contained and reader-friendly (readers have to jump between the main text and the appendix). At least some algorithms closely related to the main contribution of the paper, like the sampling scheme, should be stated in the main text, not just the theoretical results using this algorithm. 2. Some experimental results may need further explanation. - Why the BANDMF and MULTI-EPOCH MF tends to introduce a similar level of noise as DP-SGD when the number of epoch increases? - What is the exact RMSE for BANDMF, MULTI-EPOCH MF and DP-SGD in Figure 4? Also, how should one understand the relationship between RMSE and accuracy (From Table 5 in appendix, smaller noise in DP-SGD can have worse performance than ampl MF)? [1*]Hyejin Shin, Sungwook Kim, Junbum Shin, and Xiaokui Xiao. 2018. Privacy-enhanced matrix factorization for recommendation with local diferential privacy. IEEE Transactions on Knowledge and Data Engineering 30, 9 (2018), 1770–1782. [2*] Zitao Li, Bolin Ding, Ce Zhang, Ninghui Li, and Jingren Zhou. Federated Matrix Factorization with Privacy Guarantee. PVLDB, 15(4): 900 - 913, 2022

Questions

Refer to the Weaknesses

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

1 poor

Contribution

2 fair

Limitations

N/A

Thanks for the rebuttal

I thank the authors for the detailed response. All my concerns/questions have been addressed.