Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation

Thank you for your positive review and for your comments.

We address all of your concerns and kindly ask you to update your score accordingly.

---

Q: Adding experiments
A: We have now added experiments that demonstrate the applicability of our approach and corroborate our theoretical guarantees (Logistic regression over MNIST). Please see our response to Reviewer kvrv.

---

Q: Novelty over the full-participation paper [Reshef and Levy, 2024]
A: The trusted server setting is indeed quite simple — as explicitly mentioned in our paper.
But this is not the case for the untrusted-server setting, which is our main contribution.

We understand that our approach seems simple in hindsight. However:

• In Section 4.1 of our paper, we depict two natural extensions of [Reshef and Levy, 2024] that completely fail to achieve optimal guarantees.
• As shown in our analysis in Appendices D and E, the combination of partial participation and correlated noise:
  • substantially complicates the analysis
  • introduces challenges well beyond those in [Reshef and Levy, 2024]

-Moreover, our approach is: (i) the first to achieve optimal generalization guarantees in the partial-participation setting
(ii) the first to achieve linear computational complexity in this setting

-Finally, we believe that: (i) a simple algorithm is an advantage, not a disadvantage
(ii) while our approach is simple in hindsight, it was very challenging to develop and analyze this non-trivial idea

---

Q: Other related works
A: Let us re-emphasize the relation to previous works:

• For the case where machines trust each other:

  • The work of [Feldman et al. 2020] achieves optimal guarantees with linear computational complexity, but only for the last iterate.
  • Their technique does not extend to the case where machines do not trust each other, since they only maintain privacy of the last iterate, while all intermediate iterates are non-private.
    • Conversely, our approach works when machines do not trust each other (regardless of whether they trust the server), and still obtains optimal guarantees and complexity.

• For the case where machines do not trust each other, beyond the work of [Lowy & Razaviyayn, 2023] that requires $O(|S|^{3/2})$ complexity, there is a recent work of [Gao et al. 2024] brought to our attention by Reviewer kvrv. However:

  • In the full-participation case, [Gao et al. 2024] achieves optimal generalization with a complexity of $O(|S|^{9/8})$, which improves over [Lowy & Razaviyayn, 2023], but is still suboptimal compared to our work.

  • In the partial-participation case, [Gao et al. 2024] achieves suboptimal guarantees (see below), and still requires superlinear computation in $|S|$.

  -Conversely, we obtain optimal performance for the partial-participation case, and enjoy linear computational complexity in $|S|$.

Elaborate Comparison to [Gao et al. 2024]

The work of [Gao et al. 2024] indeed provides guarantees for DP-FL learning.

Regarding guarantees:

• In the full-participation setting:

  • [Gao et al. 2024] achieves optimal DP generalization (i.e., population loss guarantees)
  • However, their approach requires super-linear computational complexity, i.e., $O(|S|^{9/8})$, where $|S|$ is the total number of samples used (see Eq. (7) in their paper)
  • Note that in their notation:
    $|S| = nN$, where:
    • $N$ = total number of machines
    • $n$ = number of samples per machine

• Comparably, in this setting we:

  • achieve optimal DP generalization
  • require only linear computational complexity in $|S|$
  • In our notation, $|S| = n$ denotes the total number of datapoints used by all machines during training

• In the partial-participation setting:

  • [Gao et al. 2024] still uses $|S| = nN$ (even when only $M \leq N$ machines are used per round; see Alg. 1 and Alg. 2)
  • Theorem C.1 (Eq. (17)) in their paper shows a convergence rate of:
  $$O\left(\frac{1}{\sqrt{Mn}} + \frac{\sqrt{d}}{\epsilon \sqrt{M}n}\right)$$

  -Translating to total data $|S| = nN$, this becomes:

  $$O\left(\frac{N/M}{\sqrt{|S|}} + \frac{\sqrt{d}N/\sqrt{M}}{\epsilon |S|}\right)$$

  which is suboptimal

  • Moreover, their approach still requires superlinear computation in $|S|$

• Conversely, in our partial-participation setting, we:

  • obtain optimal guarantees of: $$O\left(\frac{1}{\sqrt{|S|}} + \frac{\sqrt{d}\sqrt{M}}{|S|}\right)$$
  • achieve linear computational complexity in $|S|$
  • Note: in our notation, $M$ = total number of machines

We shall add this comparison to the paper.

Thank you for the review.

We address all of your concerns and kindly ask you to increase your score accordingly.

---

Q: Novelty over the full-participation paper [Reshef and Levy, 2024]
A: We understand that our approach seems simple in hindsight. However,
let us highlight that coming up with this idea and analyzing it was not trivial at all.

Concretely:

• In Section 4.1 of our paper, we depict two natural extensions of [Reshef and Levy, 2024] that completely fail to achieve optimal guarantees.

• As shown in our analysis in Appendices D and E, the incorporation of partial participation and correlated noise:

  • substantially complicates the analysis
  • introduces challenges far beyond those in [Reshef and Levy, 2024]

• Moreover, our approach is:

  • the first to achieve optimal generalization guarantees in the partial-participation setting
  • the first to achieve linear computational complexity in this setting

• Finally, we believe that:

  • a simple algorithm is an advantage rather than a disadvantage
  • while our approach is simple in hindsight, it was very challenging to develop and analyze this non-trivial algorithmic idea

---

Q: Novelty over previous work with noise-cancellation, [DPNCT: A Differential Private Noise Cancellation Scheme for Load Monitoring and Billing for Smart Meters]
A: Please note again that our work is the first approach to achieve optimal guarantees for DP-FL with partial participation.

The work you referenced indeed discusses noise cancellation in the context of privacy, and we will gladly cite it in the final version of the paper. However, that paper:

• does not consider machine learning training!
• does not provide any guarantees! — not even privacy guarantees!

Conversely, our work:

• discusses machine learning, specifically DP training in the federated partial-participation setting
• provides optimal guarantees for: - population risk - computational complexity - differential privacy
• proposes the use of noise-cancellation in conjunction with the $\mu^2$-SGD approach, which is crucial to achieving our guarantees
  (using noise-cancellation with standard SGD estimates would fail to provide optimal guarantees)

---

Q: Adding experiments
A: We have now added experiments that demonstrate the applicability of our approach and corroborate our theoretical guarantees (Logistic regression over MNIST). Please see our response to Reviewer kvrv.

Thank you for the review.

We address all of your concerns and kindly ask you to increase your score accordingly.

Regarding your comment:

---

Q: Novelty over full-participation paper [Reshef and Levy, 2024]
A: We understand that our approach seems simple in hindsight. However,
let us highlight that coming up with this idea and analyzing it was not trivial at all.

Concretely,

• In Section 4.1 of our paper, we depict two natural extensions of [Reshef and Levy, 2024] that completely fail to achieve optimal guarantees!

• Moreover, as you can see in our analysis appearing in Appendices D and E, the partial participation and correlated noise:

  • substantially complicate the analysis
  • are substantially more challenging compared to the analysis of [Reshef and Levy, 2024]

• In pages 12–16 of the appendix we do have some overlap with [Reshef and Levy, 2024], but these appendices are provided for completeness.
  Actually, [Reshef and Levy, 2024] themselves also provide this for completeness, and this part is not a novelty of their work.
  We shall highlight this in the final version of the paper.

• Moreover, our approach is:

  • the first to achieve optimal generalization guarantees in the partial-participation setting
  • the first to achieve linear computational complexity in this setting

• Finally, we believe that:

  • a simple algorithm is an advantage rather than a disadvantage
  • while our approach is simple in hindsight, it was very challenging to come up with this non-trivial algorithmic idea and analyze it

Thank you for your positive review and for your comments.

We address all of your comments and kindly ask you to update your score accordingly.

Regarding your comments:

---

Q: Comparison to [Gao et al. 2024]
A: The work of [Gao et al. 2024] indeed provides guarantees for DP-FL learning.

Regarding guarantees:

• In the Full-Participation setting, [Gao et al. 2024] enjoy optimal DP generalization (i.e., population loss guarantees), while requiring a computational complexity which is super-linear in the size of the dataset, i.e., $O(|S|^{9/8})$, where we define $|S|$ to be the overall number of samples used (see Eq. (7) therein).
  Note that in the notation of [Gao et al. 2024], $|S| = nN$, where they use $N$ to denote the total number of machines, and $n$ to be the size of the data on each machine.

• Comparably, in this setting we achieve optimal DP generalization while requiring only linear computational complexity in $|S|$.
  Note that in the notation of our paper, $|S| = n$, since we denote $n$ as the total number of datapoints used by all machines throughout the training process.

• In the Partial-Participation setting, [Gao et al. 2024] obtain sub-optimal DP generalization guarantees.
  Concretely, the total data used in their work is still $|S| = nN$, where $N$ is the total number of machines and $n$ is the number of data points on each machine. This applies even when they are using $M \leq N$ machines in every round (see Alg. 1 and Alg. 2 in their paper).

  The bound they establish in Theorem C.1 (Eq. (17)) shows a convergence rate of:
  $O\left(\frac{1}{\sqrt{Mn}} + \frac{\sqrt{d}}{\epsilon \sqrt{M}n}\right).$
  Translating this into the size of the dataset $|S| = nN$ implies a bound of:
  $O\left(\frac{\sqrt{N/M}}{\sqrt{|S|}} + \frac{\sqrt{d}N/\sqrt{M}}{\epsilon |S|}\right),$
  which is suboptimal.
  Moreover, their approach requires a computation which is superlinear in $|S|$.

  Conversely, in the partial participation case we obtain optimal guarantees of:
  $O\left(\frac{1}{\sqrt{|S|}} + \frac{\sqrt{d}\sqrt{M}}{|S|}\right),$
  and our computational complexity scales linearly with $|S|$.
  Note that in our notation $M$ is the total number of machines.

  We shall add this comparison to the paper.

---

Q: Stating overall lower bounds, w.r.t. Population loss
A: Thank you for this suggestion, we will do so.

---

Q: Relation of our noise-cancellation mechanism to [Koloskova et al. 2023]
A: [Koloskova et al. 2023] discusses the idea of adding general correlated noise patterns during DP training. But they:

• only discuss ERM problems
• suggest adding correlated noise to FTRL or SGD which use standard gradient estimates
• do not provide explicit guarantees, and do not discuss partial-participation

Conversely in our work we:

• discuss and provide population-loss guarantees
• suggest adding noise-cancellation (and therefore correlated noise) to $\mu^2$-SGD estimates, which is crucial to our guarantees
• provide explicit bounds for partial-participation

We shall add this discussion to our work.

---

Q: Experiments.
A: We performed experiments that illustrate the benefit of our approach and corroborate our theoretical findings. See below.

Experimental Results (MNIST, Logistic Regression)
We compare our method (“Our Work”) to Noisy SGD [DL DP] and [Lowy & Razaviyayn, 2023]. All use n=60,000 samples. In Our Work and Noisy SGD, each sample is used only once (single pass). The low accuracy (<70%) is due to privacy noise and single-pass training.

Privacy-Level Comparison (fixed m=50, M=100):

Participation-Level Comparison (fixed ρ=8, M=100):

Key Takeaways:

• For strong DP requirement (low $\rho$) and partial-participation (low $m$) we consistently achieve better performance with runtimes comparable to noisy-SGD. The runtime of [Lowy & Razaviyayn] is substantially higher! And in this regime they obtain substantially worse performance.

-For weak DP requirement (high $\rho$) and when approaching full-participation (high $m$), the accuracy of [Lowy & Razaviyay] improves but the runtime is very high.