Revisiting Differentially Private Algorithms for Decentralized Online Learning

Many thanks for the constructive reviews!

Q1: No experiments were conducted … demonstrating how the theoretical regret bound improvements manifest empirically ... would have made the paper more compelling. This absence has been a factor in my relatively lower score.

A1: We agree with the significance of empirical evaluations, and have conducted experiments to verify the performance of our algorithms during the rebuttal period. Since the absence of experiments affected your evaluation of our paper, we hope that you could raise the score if the concern has been addressed.

Specifically, we conducted experiments on the problem of decentralized online multiclass classification, where the feasible set consists of all matrices with bounded trace norm, and adopt a complete graph with $n=9$ nodes as the communication network (see Section 4.1 of Zhang et al. (2017) for more detailed setup about this task). We set the bound of trace norm to 10. The dataset is letter selected from LIBSVM repository [1], which contains $15000$ examples and $26$ classes. Moreover, the dataset is reused $n \times 10$ times, and then evenly distributed among the $n$ local learners, which implies that $T=150000$.

We compare our PD-FTGL and PD-OCG against Algorithm 1 in Li et al., (2018), which is called PD-OGD. Note that the original PD-OGD can only achieve $(\epsilon, 0)$-DP for each round, instead of all rounds. To make a fair comparison, we increase the scale of noises added into PD-OGD to achieve $(\epsilon, 0)$-DP over all rounds. Figures 1 and 2 in the link https://anonymous.4open.science/r/ICML2025-8764/Experiments@v2.pdf present our experimental results. Specifically, in Figures 1(a) and 1(b), we compare the average loss of these algorithms under $\epsilon=10$, and their corresponding runtime, respectively. In Figures 2(a) and 2(b), we respectively report the average loss of our PD-FTGL and PD-OCG under different privacy levels, i.e., $\epsilon = 10, 5,$ and $2.5$.

From these results, we have the following main observations.

1. From Figure 1(a), both our PD-FTGL and PD-OCG have much lower average loss than PD-OGD (Li et al., 2018). This is because PD-OGD requires much larger scale of noises to achieve the same privacy level. Moreover, the average loss of our PD-OCG is worse than that of our PD-FTGL, which is consistent with our theoretical results.

2. From Figure 1(b), the runtime of PD-OGD is much longer than that of our PD-FTGL. This is because PD-OGD performs the projection operation once per round, whereas our PD-FTGL only do this once per block. Moreover, our PD-OCG requires shorter runtime than our PD-FTGL, which verifies the benefit of the projection-free property.

3. From Figure 2, in terms of the average loss, both our PD-FTGL and PD-OCG perform better as \epsilon\ increases. It is worth noting that the average loss of PD-OCG varies less with different $\epsilon$, which implies that the privacy level has a smaller impact on PD-OCG. This is also consistent with the theoretical results, since the privacy-related term in the regret of PD-OCG and PD-FTGL for convex functions is $\tilde{O}(n\epsilon^{-1}T^{1/4})$ and $\tilde{O}(n\epsilon^{-1}\rho^{1/4}\sqrt{T})$, respectively.

[1] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. In TIST, 2011.

Q2: … how about summarizing the results … in a table form?

A2: Thanks for your helpful suggestion. In the revised version, we will summarize these theoretical results in a table form.

Many thanks for the constructive reviews! We hope the reviewer could reevaluate our paper, and are very happy to respond more questions during the reviewer-author discussion period.

Q1: No experimental results ...

A1: Please check our response to Q1 of Reviewer J5zj, which presents experimental results to verify the performance of our algorithms (or check the link https://anonymous.4open.science/r/ICML2025-8764/Experiments@v2.pdf for a quick browse).

Q2: ... discussion on ... DP-FTRL.

A2: First, we want to clarify that the original work of DP-FTRL (Kairouz et al., 2021) and its latest results in a realizable regime (Asi et al., 2023a) have been cited. From lines 146 to 157, we have provided detailed discussions about Kairouz et al. (2021), and will introduce more details about Asi et al. (2023a) in the revised version. Moreover, we are also willing to cite and discuss more works related to DP-FTRL if the reviewer could suggest some concrete references.

Q3: Privacy analysis clarity …

A3: We apologize for this confusion, and will provide more explanations in the revised version. First, the privacy term (we guess what you mean is the noise added at each node in the binary tree) is analyzed and bounded from lines 403 to 412, and then the bound is utilized in Eq. (13), which is critical for establishing our desired regret bounds.

Moreover, we want to clarify that the detailed analysis of privacy guarantees is provided in Appendix D due to the limitation of pages. As an important part of the analysis, the derivation about the sensitivity for each node in the binary tree is carried out from lines 790 to 818, which finally establishes an $\ell_1$-sensitivity of $6n^{-1}\sqrt{d}(G+\alpha R)$.

Q4: Novelty in decentralized online learning …

A4: We want to emphasize that there do exist some technical novelties in our algorithm and analysis, instead of simply combining existing techniques.

1. The closest existing algorithm to ours is the non-private AD-FTGL in Wan et al. (2024b), which has already utilized the blocking update and accelerated gossip. Our algorithm can be viewed as a private extension of AD-FTGL based on the tree-based technique. However, AD-FTGL originally does not satisfy the requirement of applying the tree-based technique due to the block-coupled communication (see Remark below our Algorithm 2 for detailed discussions). To address this issue, our algorithm for the first time adopts block-decoupled communication.

2. When deriving the privacy guarantees, according to the previous study (Ene et al., 2021), it is natural to bound the sensitivity of the blocking update by the block size. However, this will lead to worse regret bounds under the same privacy level. By contrast, we provide a novel analysis to show that the sensitivity is independent of the block size (see Appendix D), which allows us to recover the non-private regret bounds over a wide range of $\epsilon$.

Q5: Line 247: Why is $\bar{\mathbf{d}}$ mentioned here?

A5: We apologize for this confusion, and will provide more explanations as you suggested. Actually, from Wan et al. (2024b), the role of $\mathbf{z}\_i(t+1)$ in Eq. (4) is to approximate $\sum_{\tau=1}^{t}\bar{\mathbf{d}}(\tau)$, where $\bar{\mathbf{d}}(t)= \frac{1}{n}\sum_i^n (\nabla f_{t,i}(\mathbf{x}_i(t))-\alpha \mathbf{x}_i(t))$. However, as discussed below Eq. (4), $\mathbf{z}_i(t+1)$ cannot be directly rewritten as a partial sum. To address this issue, our key idea is to approximate each $\bar{\mathbf{d}}(t)$ respectively, and then compute the sum of these local approximations. Moreover, to satisfy the communication protocol, i.e., only one communication per round, we introduce a blocking update mechanism, and thus need to approximate $\bar{\mathbf{d}}(z)$ introduced in line 247.

Q6: Algorithm 1 (Lines 10-11) …

A6: We apologize for this confusion, and will provide more explanations as you suggested. Specifically, we want to clarify that these $n$ local learners actually implement lines 6 to 15 in our Algorithm 1 in a synchronously parallel way, though these steps are contained in a for-loop about these learners.

Based on the parallel strategy, in line 10, we update the variable $\mathbf{d}\_i(z)$ for block $z$ and learner $i$, which finally gets $\mathbf{d}\_i(z)= \sum\_{t\in\mathcal{T}\_{z}}(\nabla f\_{t,i}(\mathbf{x}_i(z)) - \alpha \mathbf{x}\_i(z))$ at the end of block $z$, and will be utilized as the initialization of the accelerated gossip strategy implemented during block $z+1$ (see line 13 in Algorithm 1).

For this reason, in line 11, we only update $\mathbf{d}^{k+1}\_i(z-1)$ by Eq. (5), instead of updating $\mathbf{d}^{k+1}\_i(z)$. Moreover, it is worth noting again that the update in line 11 occurs synchronously among all local learners, and the computation of the term $\sum_{j=1}^nP\_{ij}\mathbf{d}^{k}\_i(z-1)$ in Eq. (5) relies on the local communication between these learners.

Many thanks for the constructive reviews! We hope the reviewer could reevaluate our paper, and are very happy to respond more questions during the reviewer-author discussion period.

Q1: ... the theoretical results rely on restrictive assumptions ... an empirical evaluation against existing methods would significantly strengthen the work.

A1: First, we agree with the significance of empirical evaluations, and have conducted experiments to verify the performance of our algorithms during the rebuttal period. Please check our response to Q1 of Reviewer J5zj, which introduces the detailed results (or check the link https://anonymous.4open.science/r/ICML2025-8764/Experiments@v2.pdf for a quick browse).

Moreover, we want to clarify that our assumptions for theoretical results actually are not restrictive because they have been commonly utilized in previous studies and can be easily satisfied in practice, e.g., our experiments.

Q2: ... comparison with existing literature on differentially private online learning is inadequate ...

A2: We will provide more detailed discussions about those briefly reviewed works. Here, we want to emphasize that the main overlap between our work and previous works on private online learning is the tree-based technique, which actually has been clearly discussed during the introduction about Jain et al. (2012), Smith & Thakurta (2013), Kairouz et al. (2021), and Ene et al. (2021).

Although those briefly reviewed works provide some new results for private online learning, it is unclear whether their results can be further extended into the decentralized setting focused by our paper or not. Therefore, we believe that those works do not affect the novelty and significance of our results.

Q3: ... The main contribution seems to extending the non-private results of Wan et al. (2024) ... which is incremental ...

A3: We agree that our algorithm can be viewed as a private extension of AD-FTGL in Wan et al. (2024b), but want to emphasize that both the algorithm and analysis are highly non-trivial, as explained below.

1. The key idea of our extension is to combine AD-FTGL with the tree-based technique. However, AD-FTGL originally does not satisfy the requirement of applying the tree-based technique due to the block-coupled communication (see Remark below our Algorithm 2 for detailed discussions). To address this issue, our algorithm for the first time adopts block-decoupled communication.

2. When deriving the privacy guarantees, according to the previous study (Ene et al., 2021), it is natural to bound the sensitivity of the blocking update by the block size. However, this will lead to worse regret bounds under the same privacy level. By contrast, we provide a novel analysis to show that the sensitivity is independent of the block size (see Appendix D), which allows us to recover the non-private regret bounds over a wide range of $\epsilon$.

Moreover, it is also worth noting that our paper is the first to achieve the $(\epsilon, 0)$-differential privacy for decentralized online learning (DOL), and meanwhile improve the regret bound and efficiency (for handling complex constraints) of existing private DOL algorithms.

Q4: … it is critical for the paper to establish similar matching bounds under differential privacy guarantees …

A4: We agree with the significance of matching lower bounds under differential privacy guarantees. However, even for online convex optimization with differential privacy, which has been extensively studied, there still lack such lower bounds. Thus, we would like to leave the problem about lower bounds as a future work, and hope the reviewer could reevaluate our paper based on our significant improvements on the existing private decentralized online learning algorithms.

Q5: Regarding the references for MIA …

A5: Thanks for this suggestion. We will cite the work of Reza et al. (2016) in the revised version.

Many thanks for the constructive reviews!

Q1: ... Frank-Wolfe methods on KK can be just as challenging to solve as the projection operator ... it is inaccurate to claim that ... is a projection-free algorithm.

A1: There may be some misunderstandings about our projection-free algorithm. We agree that if the number of linear optimization steps is not limited, the invocation of the Frank-Wolfe (FW) method (i.e., CG in our paper) could be as challenging as performing the projection operation. However, in our Algorithm 3, the number of linear optimization steps is limited to $L$ for each invocation of FW, and FW is only invoked $O(T/L)$ times.

Therefore, the total number of linear optimization steps required by our Algorithm 3 is $O(LT/L)=O(T)$, and it could be more efficient than our Algorithm 1 that requires almost $O(T)$ projection operations. Moreover, following previous studies, especially a formal definition in Hazan & Minasyan (2020), an algorithm can be said to be efficiently projection-free if the number of linear optimization steps is $O(1)$ per round on average. Clearly, our Algorithm 3 satisfies this definition, and thus can be claimed as a projection-free algorithm.