Revisiting Differentially Private Algorithms for Decentralized Online Learning
Authors: Xiaoyu Wang
Wenhao Yang
Chang Yao
Mingli Song
Yuanyu Wan
Venue: ICML 2025 poster (2025)
Keywords: Decentralized Online Learning
Differential Privacy
Primary area: theory->online_learning_and_bandits

Abstract: Although the differential privacy (DP) of decentralized online learning has garnered considerable attention recently, existing algorithms are unsatisfactory due to their inability to achieve $(\epsilon, 0)$-DP over all $T$ rounds, recover the optimal regret in the non-private case, and maintain the lightweight computation under complex constraints. To address these issues, we first propose a new decentralized online learning algorithm satisfying $(\epsilon, 0)$-DP over $T$ rounds, and show that it can achieve $\widetilde{O}(n(\rho^{-1/4}+\epsilon^{-1}\rho^{1/4})\sqrt{T})$ and $\widetilde{O}(n (\rho^{-1/2}+\epsilon^{-1}))$ regret bounds for convex and strongly convex functions respectively, where $n$ is the number of local learners and $\rho$ is the spectral gap of the communication matrix. As long as $\epsilon=\Omega(\sqrt{\rho})$, these bounds nearly match existing lower bounds in the non-private case, which implies that $(\epsilon, 0)$-DP of decentralized online learning may be ensured nearly for free. Our key idea is to design a block-decoupled accelerated gossip strategy that can be incorporated with the classical tree-based private aggregation, and also enjoys a faster average consensus among local learners. Furthermore, we develop a projection-free variant of our algorithm to keep the efficiency under complex constraints. As a trade-off, the above regret bounds degrade to $\widetilde{O}(n(T^{3/4}+\epsilon^{-1}T^{1/4}))$ and $\widetilde{O}(n(T^{2/3}+\epsilon^{-1}))$ respectively, which however are even better than the existing private centralized projection-free online algorithm.

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Xiaoyu Wang' Wenhao Yang² Chang Yao
Mingli Song? Yuanyu Wan 13
Abstract
data. To be precise, it is commonly characterized as re- peated game between adversary and local learners connected by an undirected graph g = ([m) E), where E S [n] [n]] denotes the edge set. At each round t, each local learner i E [n] first needs to select a local decision xt(t) from a feasible set K. C Rd, and then receives a local loss function fta(+) K. + IR determined by the ad- versary. The goal of each local learner i is to choose a sequence of decisions minimize the regret in terms of the global function fx(x) - (x,(x) at each round f, i.e.,
Although the differential privacy (DP) of decen- tralized online learning has garnered consider- able attention recently, existing algorithms are unsatisfactory due to their inability to achieve (e, 0)-DP over all T rounds, recover the opti- mal regret in the non-private case, and maintain the lightweight computation under complex con- straints. To address these issues, we first propose new decentralized online learning algorithm sat- isfying (c, DD over T rounds, and show that it can achieve Ö(n(p- 1/4 + 1=1pp//4) and Ó(n(p-1/2 cc regret bounds for convex and strongly convex functions respectively, where is the number of local learners and p is the spec- tral gap of the communication matrix. As long as e= -P)))), these bounds nearly match existing lower bounds in the non-private case, which im- plies that (e, D) of decentralized online learn- ing may be ensured nearly for free. Our key idea is to design a glokkddccopped accelerated gossip strategy that can be incorporated with the classi- cal tree-based private aggregation, and also enjoys a faster average consensus among local learners. Furthermore, we develop a projection-free variant of our algorithm to keep the efficiency under com- plex constraints. As trade-off, the above regret bounds degrade to ((n(T3/4 + e e-1r"/4)) and Ö(n (T2/3 + e) respectively, which however are even better than the existing private central- ized projection-free online algorithm.
Ry.; Σi= (t) - minxex Et= ft(x), where T is the number of total rounds.
To this end, each local learner needs to estimate global information by communicating with its neighbors. Note that as a common protocol, the communications between these learners occur via only single gossip step (Xiao & Boyd, 2004) based on weight matrix P E R at each round. Moreover, to make this problem more tractable, it is common to assume that the decision set I. and all local loss functions ft,(() are convex. This setting is known as decentralized online convex optimization (D-OCO), and has been extensively studied (Yan et al., 2013; Hosseini et al., 2013; Zhang et al., 2017: Wan et al., 2020; 2022; 2024a;b), yielding nearly optimal O(np-I/4VTT) and ((mp-112) re- gret for convex and strongly convex functions, respectively, where < 1 is the spectral gap of P.!
It is worth noting that one critical appeal of D-OCO the intrinsic privacy-preservie property, as prevents each local learner from sharing any sensitive data directly (Yan et al., 2013). However, for traditional D-OCO algorithms,, the privacy-preservee they are still vulnerable to adversarial attacks, such as mem- bership inference attack (Shokri et al., 2017) and model inversion attack (Fredrikson et al., 2015). For this reason, there has been a growing research interest (Li al., 201 8; Hou al., 2019; Lü et al., 2023; Chen et al., 2023; Cheng et al., 2023; Zhang et al., 2024b) in designing D-OCO algo- rithms with differential privacy (DP), which prevents any attacker from identifying whether a particular individual is included in a dataset (Dwork et al., 2006).
ability is limited in the sense that
1. Introduction
Decentralized online leamnigg (Li et al., 2023) is a popu- lar way to solve distributed applications with streaming
'School of Software Technology, Zhejiang University, Ningbo, China Natiinal Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China "State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China. Correspondence to: Yuanyu Wan <wanyy @ zju.edu.cn>>.
'The Ö(-) notation hides constant factors well the poly- logarithmic factors.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
However, these private D-OCO algorithms are unsatisfac- tory for three issues. First, their main idea is to directly add noise to original decisions of some traditional D-OCO algo- rithms, which cannot trade off the regret and privacy well. Specifically, to achieve the state-of-the-art regret bound of O(n5/4p p 1- (T) and ( -) for convex and strongly convex functions (Li et al., 2018), 8), where is con- stant regarding the privacy level, these algorithms can only utilize time-decaying noise obtain (cT, 0)-DP over all T rounds in the worst case, which degrades linearly according to the increase of T. Second, there exist large gaps in terms of n and p between these state-of-the-an art regret bounds and nearly optimal regret bounds in the non- non-private case, which are caused by the standard gossip step (Xiao & Boyd, 2004) utilized in the communication. Third, a projection operation required by these algorithms to ensure the feasibility of each local decision, which could be time-consuming when facing complex decision sets (Hazan& & Kale, 2012).
the accelerated gossip strategy, but adopts block-decoupled communication for incorporating the tree-based technique. Furthermore, we notice that PD-FTGL still needs to per- form projection operations per block, and thus may also be time-consuming over complex decision sets. To im- prove the efficiency, we develop a projection-free variant by replacing its projection operations with only linear op- timization steps. Our analysis reveals that this variant can achieve (n + (T!/())) and ( + +)) re- gret bounds for convex and strongly convex functions, re- spectively. Although these regret bounds are worse than those of PD-FTGL, such degeneration is a common price for the projection-free property in both centralized and de- centralized online learning (Hazan & Kale, 2012; Wan et al., 2024b). Moreover, we want to emphasize that they are even better than the 0(--118/44 regret bound achieved by the existing centralized projection-free online algorithm with (t, D)-D (Ene et al., 2021).
To address these issues, this paper first proposes a new D- OCO algorithm, namely PD-FTGL, which not only satisfies (c, O)-DP over all T rounds, but also can achieve improved Ó(n(p 1/4 + pp==)) and O(n(p-1/2 +)- regret bounds for convex and strongly convex functions, respec- tively. For = (2(VP), these regret bounds match the nearly optimal regret bounds in the non-private case (Wan et al., 2024a;b) up to polylogarithiic factors, which implies that our PD-FTGL can ensure (e, DD nearly for free over wide range of c. Compared with existing private D-OCO algorithms, the main novelty of our PD-FTGL is to utilize the tree-based private aggregation (Dwork et al., 2010; Jain et al., 2012) to achieve a better trade-off between the regret and privacy, and exploit an accelerated gossip strategy (Liu & Morse, 201 1) reduce the approximation error caused by communication.
2. Related Work
In this section, we first briefly review previous studies on the differential privacy of the special D-OCO with n 1, and then introduce existing algorithms for the general D-OCO. Due to the limitation of space, here we mainly discuss the results that are either directly comparable with ours or provide some technical inspirations. Discussions on additional related work can be found in Appendix A.
2.1. Differential Privacy of Special D-OCO with n = 1
In the special case with n = 1, D-OCO reduces to the classi- cal online convex optimization (OCO) problem (Zinkevich, 2003). is well-known that the optimal regret of OCO O(VT) and Ollog T)) for convex and strongly convex func- tions, respectively (Abernethy et al., 2008). Moreover, these optimal regret bounds can be achieved by many algorithms such as online gradient descent (OGD) (Zinkevich, 2003), FTRL (Shalev-Shwartz& & Singer. 2007; Hazan, 2016). and the follow-the-leader (FTL.) algorithm for strongly convex functions (Hazan et al., 2007).
Note that although the tree-based technique has been uti- lized to equip various non-private algorithms for centralized online learning (i.e., n = 1) with the (c, 0)-DP guarantee (Smith & Thakurta, 2013; Agarwal & Singh, 2017; Ene et al., 2021; Kairouz et al., 2021), it is non-trivia to apply this technique in general D-OCO as explained below.
The differential privacy (DP) of OCO is first studied by Jain et al. (2012), who propose general framework to convert any given OCO algorithm into a privacy-preserving one. However, their main idea is to simply add some Gaussian noise to each original decision of the given OCO algorithm, which cannot trade off the regret and privacy well. Let and 8 be constants for privacy level. Intuitively, it is easy to ensure (c. 8)D for the decision at each round by using noise proportional to the sensitivity, which is gener- ally time-decaying for OCO algorithms. But, according to the classical --fold composition theorem (Dwork & Roth, 2014), the noise should be further magnified by a factor of (TT) to ensure (c, 6DP for all T' rounds, which destroys
This technique requires that any decision of the non- private algorithm is determined by the partial sum of some variables, e.g., historical gradients in the clas- sical regulaaazeeee leader (FTRL) algorithm (Shalev- & Singer, 2007; Hazan, 2016).
Unfortunately, existing D-OCO algorithms, including the decentralized variants of FTRL based on the accel- erated gossip strategy (Wan et al., 2024a;b), do not sat- isfy the above requirement, because their decisions rely on coupled communication between adjacent rounds.
To tackle this challenge, our PD-FTGL follows a block- ing update mechanism (Wan et al., 2024a;b) to exploit
2

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
the sublinearity of the original regret achieved by the given OCO algorithm. To address this issue, Jain et al. (2012) assume that the given OCO algorithm has linearly decaying sensitivity, which only holds for strongly convex functions, and exploit the interdependence between these decisions. Nonetheless, even combining their framework with the op- timal OCO algorithm for strongly convex functions, e.g., OGD, they can only achieve much worse regret bound of O VT) while ensuring (c, 5-DP for all T rounds. To further improve the regret, Jain et al. (2012) also consider special case of OCO with quadratic functions, and propose a private variant of FTL (Hazan et al., 2007) by combin- ing it with the tree-based private aggregation (Dwork et al., 2010). A critical precondition for this combination is that in this case, the decision of FTL can be determined by the partial sum of some variables related to the quadratic func- tions. Since the tree-based technique provides a better way to introduce noise, Jain et al. (2012) achieve (c, 6)DDP and O (log./ T) log() regret for the special case.
and an Ö(E-110/ regret bound, or (e, 0DDP and a slightly different regret bound. Besides the tree-based technique and FTRL used before, this projection-free algorithm adopts a blocking update mechanism, and performs each update via multiple iterations of the conditional gradient (CG) method (Frank & Wolfe, 1956; Jaggi, 2013), which only requires more efficient linear optimization steps.
2.2. Algorithms for General D-OCO with n 2
The pioncering work of Yan et al. (2013) proposes the first al- gorithm for D-OCO, which a decentralized variant of OGD (D-OGD). The main idea of D-OGD is to first apply the stan- dard gossip step (Xiao & Boyd, 2004) over local decisions, and then perform local gradient descent. As proven by Yan et al. (2013), D-OGD can achieve 0n2//4p11/2 and D(n3/2p-1) regret bounds for convex functions and strongly convex functions, respectively.
After that, the standard gossip step has been widely utilized to design algorithms for D-OCO. Specifically, Hosseini et al. (2013) exploit to develop a decentralized variant of FTRL (D-FTRI.), and achieve the same ((15/2p-1/2vT) regret bound for convex functions. To efficiently handle complex sets, Zhang et al. (2017) propose projection-free frree variant of D-FTRI, and establish an 0115//pp1/22/ 3/273//4 regret bound for convex functions. Later, Wan et al. (2020) introduce a blocking update mechanism to reduce the communication complexity of Zhang et al. (2017) from O(T) to O(VT) while keeping the same regret bound. The first projection- free D-OCO algorithm for strongly convex functions is pro- posed by Wan et al. (2021a), and can reduce the regret bound and communication complexity to O(n3/2p p (123/32-112/3 (T233) and Ö(T+/²), respectively. Moreover, Wan al. (2022) unify these two algorithms (Wan et al., 2020; 2021a) into a single one that inherits the thcoretical guarantees.
Later, Smith & Thakurta (2013) extend the private variant of FTL (Jain et al., 2012) into OCO with strongly convex functions by replacing FTL with an approximate variant (Hazan et al., 2007) that originally updates as
x(1 + 1) argmin Σ (x)
XEK
where fx() = 1000<Vpt (x()() + / 1|x x(2))12 and a the modulus of the strong convexity. Additionally, they propose to utilize Laplace noise, instead of Gaussian noise used in Jain et al. (2012). Based on these changes, Smith & Thakurta (2013) for the first time establish (c, 0)DP and O 1oc-'oo'5// 50g5/2T) T) regret for OCO with strongly con- vex functions. Interestingly, they show that by combining with a strongly convex approximation of general convex functions, their algorithm can be utilized to achieve an V(T) regret bound for the general OCO. Recently, Kairouz al. (2021) develop a specific algorithm with (c, 6)- DP for the general OCO, to achieve a better regret bound of ((e-))//TT). Compared with Smith & Thakurta (2013), the critical changes include utilizing Gaussian noise and replacing the approximate FTL in (1) with FTRL (Hazan, 2016) that originally updates as
However, Wan et al. (2024a;b) recently have pointed out that even the above projection-based algorithms are subop- timal by establishing M(np 1/4 (nn--1//VT 1/4 and 2(mp 112 -1/2 log T') lower bounds for D-OCO with convex and strongly con- vex functions, respectively. To address this issue, Wan et al. (2024a;b) develop a novel D-OCO algorithm, which reduces regret bounds for convex and strongly convex functions to Ö(p--1/4 1/4 (TT and (/2--122, respectively. Their main idea is to combine the accelerated gossip strategy (Liu & Morse, 2011) with both FTRL (Hazan, 2016) and the ap- proximate variant of FTL (Hazan et al., 2007). Moreover, Wan al. (2024b) also develop an improved projection-fi free D-OCO algorithm based on the accelerated gossip strategy. Compared with the projection-free algorithm in Wan et al. (2022), this improved one can reduce the regret bounds for convex and strongly convex functions to 0/4 and Ō ((TT2/3) by increasing the communication complexity to 0p-1122 1/2 VT) and Ö(p 11/211113) respectively.
1 (V)(((())), + 1)
x(t + 1) = argmin
|2
(2)
XEX
where 7) is tunable parameter.
Moreover, Ene et al. (2021) consider the case with complex decision sets, in which the above private algorithms may be time-consuming due to the (implicit) projection operation. To tackle the computational bottleneck, they develop the first projection-free OCO algorithm that achieves (c, DDP
3

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Table Comparison of results previous studies. Abbreviations: convex + cvx, strongly convex sevx.
Assumption
Reference
Regret Bound
Privacy
Decentralized?
Projection-free?
Li et al. (2018)
O 1/26 VT)
(EI, 0)-DP
Wan et al. (2024a;b)
Ö(p 1/4 1/4
Corollary 3.7
O(n(p- 1/4 + +--1)//)
(c,0)-DP
V
X
ft,()): evx
Ene et al. (2021)
0(6-118/44
(e,0)-DP
X
Wan al. (2024b)
O(1T3/4)
v
Corollary 3.10
+
(c,0)-DP
Li et al. (2018)
(pE))2(pE)-))
(eT.0)-DP
V
X
Wan et al. (2024a;b)
1(22-1/2)
fea()): scvx
Corollary 3.8
Ó(n(p-1/ 1/2 +1)
(c,0)-DP
Wan al. (2024b)
Ō(TT233)
Corollary 3.11
Ó(n(T2/3 +E
(e, O).D)
Besides the above progresses, the most relevant works to this paper are about the D-OCO with DP guarantee. Specifi- cally, Li et al. (2018) propose a private variant of D-OGD by simply adding noise to each original decision. Note that this idea is almost the same as the general framework proposed by Jain et al. (2012). Therefore, Li et al. (2018) can only ensure (e, DD for each round, while achieving sublinear O(n p 1/2,p-1 VT) regret bounds and 0nn3/2p c- for convex and strongly convex functions, respectively. Ac- cording to the food composition theorem (Dwork & Roth, 2014), such a privacy guarantee will degrade to (ET, 0)- DP over all T rounds in the worst case. Although a series of subsequent algorithms have been proposed (Hou et al., 2019; Lü et al., 2023; Chen et al., 2023; Cheng et al., 2023; Zhang et al., 2024b), both the privacy and regret are not improved. Additionally, these private algorithms are all projection-based. In contrast, this paper proposes a new D-OCO algorithm with (e, D)-DP over all rounds and im- proved regret bounds, and also develops a projection-free variant to efficiently handle complex decision sets. A de- tailed comparison between of previous and our results is summarized in Table
Assumption 3.1. The set K. is convex and contains the origin, i.c., 0 E KC. Moreover, there exists a constant It such that |x|| 1 R for any x E K.
Assumption 3.2. For any t E [7] and i [n]. the loss func- tion (x) is G-Lipschitz over K,, i.c., (x2,(()) fx), - c for any x,y E K.
Assumption 3.3. For any t E [T] and i E [n], the loss function (x, is a-strongly convex over K., i.e., fy,ily) 2 fx, (x. - x) + - yl2 for any x, E K. Assumption 3.4. The communication matrix P E R is supported on the graph G = ([n), E), symmetric, and doubly stochastic, i.c.
Pss > only if (i, E or Σド Pu. 1, vi [m] and Σ Pij 1, [n).
Morcover, P is positive semidefinite, and its second largest singular value denoted as (P) is strictly smaller than 1.
First, when = 0, Assumption 3.3 reduces to the case of general convex functions. Second, the spectral gap of P now can be defined as = - o2
Remark.
Then, we provide a formal definition for the differential privacy (DP) of D-OCO (Li al., 2018; Asi et al., 2023b).
3. Main Results
Definition 3.5. Let F = F((T) with F(t) = ()..,)...., (-)) be a sequence of loss functions, and F' be a neighboring sequence generated by replacing one f-,(-) by (-)(-) for some E [T'] and [n)]. Let A denote randomized D-OCO algorithm that takes F selected by the adversary Adv during the online process as the input, and outputs sequence of local decisions denoted as Ao in the space K"*T, Then, A (c, 5) diifferrettillly private Pr[A o Adv(F) E S] < e Pr[A o Adv(F') E S] + holds for any S C K
In this section, we first introduce necessary assumptions and definitions, and then introduce our proposed algorithms as well as the theoretical guarantees. All proofs can be found in the appendix.
3.1. Assumptions and Definitions
Let ||x|| denote the fo-m of any vector x. Following previous studies ( (Yan et al., 2013; Wan et al., 2024a), we first introduce common assumptions about D-OCO.

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
3.2. Our PD-FTGL
Algorithm 1 PD-FTGL
1: Input: L, 0, h. D, a
Inspired by previous studies on the DP of OCO (Jain et al.,
Initialize x; (1 = (1) = 0, vi E [n]
2012; Smith & Thakurta, 2013; Kairouz et al., 2021), natural idea to improve the privacy of D-OCO is to ploit the tree-based private aggregation (Dwork et al., 2010). However, different from FTRL and the approximate FTL in OCO, their decentralized variants (Hosseini et al., 2013;
3: Create complete balanced binary tree B, with nodes for any i E [n] 4: for 2 = 1, T/ do
2flog,
5: for each local learner i E [n]] do
6:
Set (2) =
Wan et al., 2024a;b) do not satisty the precondition of using the tree-based technique.
7:
for = 0,..., L - do
Set (2 1) + k +1
To be precise, their decentralized variants based the stan- dard gossip step can be unified to one algorithm called de- centralized follow-the-genee generalized-leade (D-FTGL) (Wan
Play x; (x) and query (z)((x(2))
10:
Set (2) dx(2) + fz, (x)
11:
If 2 2. update d +1 (= 1) by (5)
et al., 2024b), which performs the following update
12:
end for
(t + 1) = argmin(2z; + 1),x)+ ta + 2h
13:
Set d)()) = d (2) d.)
|
(3)
14:
d If 2 2, set w, 12- (1 1) and compute
xEX
2
(B,, (x)) = PrivatteSum (= 1), B. - 1, D)
for each local learner i, where h is a parameter and (t(++1) 1) maintained as
via Algorithm 2
15:
Update x,(2 + 1) as in (6)
16: end for
2t(t 1)= Σ +
- (xx(()) (4)
17:
end for
Let d(t)= -0))= + -ー (t).) where (t) = (x,((x(())
(t) We notice that the key role of 2t 1) is to approx- imate Σt=1 d(Tr,, and it thus can be viewed as an extension
for k 0, ................................ I. 1--1111 1, where P is mixing coefficient, and d 1) = d (2 1) d; 1). Then, we can apply the tree- braed technique to output private approximation of
of D (x(()) in (I) and (2). Nonetheless, it cannot be directly rewritten as a partial sum, because the communi- cation in (4) is coupled between adjacent rounds. The same issue also exists in their decentralized variants based on the accelerated gossip strategy (Wan et al., 2024a;b).
-= (T), denoted as (2), for each block z. Inspired
by (3), we utilize (2(2) to update the decision as
(= +1) = (2: + a(2 - 1)L + 2h XEK
||x||
2
To address the above issue, we first introduce a blocking update mechanism (Wan et al., 2020), which divides the total T rounds into L blocks, where L is parameter and T/L is assumed to be an integer without loss of generality. Then, we only maintain a fixed decision (2) for each lo- cal learner i at all rounds contained by each block x, i.e.,
(6)
Combining with the initialization of (1) = 21( = 0, the detailed procedures of our proposed algorithm are summa- rized in Algorithm 1, which is named as private decentral- ized follow-the follow-the-generalizee-eddd generalized-leade (PD-FTGL).
Remark. First, we want to clarify that the for loop among these n local learners, i..., line 5 in Algorithm 1, is mainly used to facilitate presentation, and we actually implement lines 15 in Algorithm in parallel for these local learn- ers. More specifically, they will synchronously perform the the accelerated gossip strategy via communication to com- pute d (z - 1) in line 11 of Algorithm 1. Second, the implementation of tree-based private aggregation follows Smith & Thakurta (2013). For the sake of completeness, the detailed procedures are outlined in Algorithm 2, where the noise distribution D will be specified later. As shown in line 14 of Algorithm 1, at the end of each block = 2 2. it is invoked to update the binary tree B, maintained by each local learner i and compute the private partial sum 2, (z). Finally, it is worth noting that although Wan et al. (2024a;b) have utilized the blocking update mechanism and the accelerated gossip strategy in D-OCO, they pro- pose to maintain (2( to approximate Σi=1 d(r) directly,
T. T== ((= - 1,,,+1, ..).. Let d()) = 1/2 E dz(z), where (z) = EIET. (x,,(((())) - ax,())) denote a
block-level variant of the previously defined d(t). During each block 2, we now can utilize I, communications to maintain (= -1 1) x d(= -) 1) for each local learner i. In- tuitively, even using the standard gossip step (Xiao & Boyd, 2004), the partial sum Σ (7). which is ready to be combined with the tree- technique, can play similar role as (1 ++ 1) in (4) for estimating the global information. However, as previously discussed, this approach will result in suboptimal dependence of the regret on and n.
Thus, inspired by Wan et al. (2024a;b), we adopt the ac- celerated gossip strategy (Liu & Morse, 2011) maintain d= --1 1). Specifically, we perform the following update
d=-1(=-1)= (1+0) Σ (2-1) aa (5)
1=1
5

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Algorithm 2 PrivateSum (Smith & Thakkrta, 2013)
Corollary 3.7. Under Assumptions 3.1, 3.2, 3.3 with
1: Input: vector Wt, binary tree B, counter i, noise distri-
and 3.4, for any E [n), by using parameters in Theorem
bution D
3.6 and setting h = G (2L//ALT2222 log, T)/ B. Algorithm
2: Assign W, the (-th leaf node from left to right
I ensures
3: Let L = {we + .... + root} be the path from w, to
E|Rr, STnGRy LT logo
root node
4: Let A denote the first left child of B in L
+ 4d + log, ////L/T/L.
5: for å w, - + A do
6: 6 W. + b.. where b. ~ D
Corollary 3.8. Under Assumptions 3.1, 3.2, 3.3 with a and 3.4, for any E [n], by using parameters in Theorem 3.6 and setting h aL, Algorithm 1 ensures
7: end for
8: for s the next node of A in I. > -> root do
9: s= we
E R... & 24a " + 2x (1+ In(/LL)
10: end for
+ (d + 2aR) (2 loga T)² + noLR
11: Let S denote the set contains all top noised nodes, i.e.,
their parent nodes are not added noise
12: V, Eses
Remark, By recalling the value of L in (7), Corollaries 3.7 and 3.8 show that our PD-FTGL enjoys regret bound for convex functions and
13: Output: updated binary tree B, private partial sum V.
of Ó(n(p-(n 1/4 + e 11111//) an improved one of Ó(n(p 1/2 + +)= for strongly con- vex functions. These two bounds are respectively tighter than the 0(n5/4p bounds of existing private D-OCO algorithms (Li al., 2018). Moreover, want to emphasize that our advan- tages include two aspects. First, our regret bounds have a better dependence on both n and p. which owes to the ex- ploitation of the accelerated gossip strategy (Liu & Morse, 2011). Second, our regret bounds decouple the negative effects of the decentralized setting and the demand for pri- vacy, i.e., e is not multiplicative to p-1/41 and 1/2 As result, we can nearly match the (1/pp-//4/T) and 1(mp-1/2 log 7') lower bounds for D-OCO in the non- private case, for = (Pp)), instead of only e = 2(1). It is also worth noting this improvement requires a non-trivial analysis that shows the sensitivity of the blocked update mechanism is independent of the block size, instead of sim- ply combining the previous analysis of the tree-based tech- nique (Jain al., 2012; Smith & Thakurta, 2013; Kairouz et al., 2021; Ene et al., 2021).
which needs to set (2) = 2 1) +
+ d, 1) and (2) / (2 - + ( = 1). Therefore, their com- munication block-coupled, and (z) cannot be rewritten as a partial sum. In contrast, the communication of our al- gorithm dico-ddecuupled, which is critical for exploiting the tree-based technique.
and 0(n3/2p-1e
regret
Now, we present the theoretical guarantees of Algorithm 1. Theorem 3.6. Under Assumptions 3.1, 3.2, 3.3, and 3.4, for any i E [n)]. by setting
-1 L [=4InnTTV1AA)) Vp
0 1+ 11+V1-03(P))
(7)
and D = (0, dc a2)(2 + log, T)), Algo- rithm 1 ensures (e, DD and the following regret bound
T/I.
12GL + 2aR)
E[RT,]] S nhR + mL Σ
azT. + 2h.
T/L
2G + al) (2 + logz T)
+ nL.
(8)
3.3. Our Projection-free Algorithm
<(a(z - ((((2-2)L-- + 2h)
2
We proceed to consider the case with complex decision sets, in which the implicit projection operation in (6) could become a computational bottleneck of our PD-FTGL. To address this limitation, we propose a projection-free algo- rithm by combining PD-FTGL with the classical conditional gradient (CG) method (Frank & Wolfe, 1956; Jaggi, 2013).
T/L Σ
6G(G + RR) n (a(2 (000-2)) 2) + 2h)
+ nL
2=2
Remark. From Theorem 3.6, our PD-FTGL can appro-
priately utilize the Laplace noise each coordinate, i.c., Lap"(.-), J to achieve (e, DD for D-OCO with both con- and strongly convex functions. Compared with existing algorithms with only (TT, 0)-DP (Li et al., 2018), our algo- rithm significantly improves the ability of privacy protection. Moreover, combining Theorem 3.6 with the value a and a suitable h, we can establish specific regret bounds for convex and strongly convex functions, respectively.
The detailed procedures of this algorithm are summarized in Algorithm 3, and it is named private decentralized online conditional gradient (PD-OCG).
Specifically, compared with PD-FTGL, there exist two crit- ical differences in our PD-OCG. First, as shown in lines and 16 of Algorithm 3, we further set (2) = 0 and compute (2 + 1) for 2 2 2 by applying L iterations of
6

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Algorithm 3 PD-OCG
maintaining good d (z). Therefore, as in line 12 of Algorithm 3, the second difference is to limit the number of accelerated gossip steps in each block by L', instead of the block size L.
1: Input: L, L', h, D,
2: Initialize x,(1) = (2) = 2(1)= 0, Vi E [n]
3: Create a complete balanced binary tree B, with
nodes for any [n] 4: for 1.,....., do
2 (1
Combining our analysis of PD-FTGL with the convergence property of CG, we establish the following guarantees on the privacy and regret of the projection free algorithm.
5: for each local learner i E [n] do
6: = 2 2, define (x) by (9)
Theorem 3.9. Under Assumptions 3.1, 3.2, 3.3, and 3.4,
7:
Set (1,())= 0
any i [nl), by setting
8:
for k = 0, 0..... L 1 do
9:
Set = (z L + +1
0 1+ 11+ 0B(P)) - L'= 44nnnTV Vp
10:
Play (z) and query (z))
11:
d.(z) = d=) (V (x,,,(x( (x)
(10)
12:
If 2 2 and k < L', update dltt1 (2 1) by (5)
and D = Lap (0, de (G + aR)(2 + log, T)), Algo- rithm ensures (c. 0) and the following regret bound
13:
end for
14:
Set (=) = 1 (2) = di(z)
15:
If 2 2, set -2 df (z 1) and compute PrivateSum(w via Algorithm? 2
TyL 24GL + 2a.t
B;, 1,
E R S nhR
mL Σ
azL + 2h
16:
I 2 2, invoke Algorithm to update the decision as (; + 1) = CG(K, L, (x), xx))
T/L
27dG (G + aR) (2 + log, T) <(o(z - 33 2h)
mL
Σ
(I1)
17:
end for
s=3
18: end for
T/L
12GB
6G + aR)
+ nL
+ n (a(z 13)2-334++ 2h)
VL
Algorithm 4 CG (Frank& & Wolfe, 1956; Jaggi, 2013)
1: Input: K., L. F(x), x(0)
Remark. From Theorem 3.9, our projection-free algorithm can ensure the same (c, OD as PD-FTGL, which is be- cause the exploitation of CG does not affect the privacy. Then, combining Theorem 3.9 with the value of a and suit- able h and L. we can establish specific regret bounds for convex and strongly convex functions, respectively.
2: for f = 0...., L, do
3: v(f) E argmin ( (V)(x))),
4: (tf) = argmin (o((t) x(t)))
5: x(t + 1) x x(t) (()(v(( x())
6: end for
7: Output: xL)
Corollary 3.10. Under Assumptions 3.1, 3.2, 3.3 with a O, and 3.4, for any i E [n], by using parameters in Theorem 3.9 and setting h = /15LTG/ R, = vT, Algorithm 3 ensures
CG to approximate the 2-th decision of local learner i in PD-FTGI. i.e.,
E RRr, S 21nGRTT/4 + 4c 4 ndGRT ///0044(22 log, T)
(
Corollary 3.11. Under Assumptions 3.1, 3.2, 3.3 with a O, and 3.4, for any i [n], by using parameters in The- orem 3.9 and setting h aL, I. = T2/3 In -n-3 2/37. T, CT In 2/3 T In 1/3 T, Algorithm ensures
where the detailed procedures of CG are outlined in Al- gorithm 4 for the sake of completeness, and the function (x) is defined
(x)( (2,(2 x),,) + a(2 2)L + 2h
|x
(9)
E R S 36a -6 CCr
2
R2 In 22/3 T 12nG In I/3T
In this way, these L iterations can be implemented in parallel to the for loop from lines 8 to 13 in Algorithm 3, which is standard trick avoid unbalanced computational costs at the end of each block (Wan al., 2022; 2024b). Moreover, let I'' denote the value of I, defined in (7). We notice that to control the approximation error of CG, the block size L needs to be sublinear to T, which is much larger than L'. However, from the convergence property of the accelerated gossip strategy (Liu & Morse, 201 1), L' is sufficient for
+ a.t) (2 + logg T)²
Remark. First, note that Corollaries 3.10 and 3.11 im- plicitly assume that T'' in (10) is smaller than L = vT and L = 72/3 In 2/3 T, respectively. This assumption is reasonable because in D-OCO is commonly much larger than other problem constants. Then, from these corollar- ies, our PD-OCG can achieve ( + -171/44) and

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
((n(Te/3 + +)) regret bounds for convex and strongly convex functions, respectively. Interestingly, if a= 0, our PD-OCG can reduce to the existing projection- free algorithm of Ene et al. (2021) with (e. O)-DP for OCO. However, they only establish an ((-11///4 log" 7) regret bound for convex functions, which is much worse than our bound the case of n = 1, i.e., O + -TT//44) This gap is because they simply bound the sensitivity of the block- ing update mechanism with the block size, and then need to add a corresponding scale of noise to ensure the privacy. In contrast, as discussed before, our novel analysis on the sensitivity implies that the scale of noise does not need to be proportional to the block size. Moreover, we want to empha- size that such an analysis brings more significant benefits to the projection frree algorithm. Specificallyy, the two regret bounds of our PD-OCG can nearly match the O(n25/a) and OnTT2/3) regret bounds of the best projection D-OCO algorithm in the non-private case (Wan et al., 2024b) for Q(T-1/2) and - 2/T respectively. Finally, similar to Wan et al. (2024b), the communication complex- ity of our projection-free algorithm is O ([T which becomes (T) and (p 1/271/3) according to the parameters in Corollaries 3.10 and 3.11, respectively.
Table 2. Summary of Datasets.
and
Dataset
# Features
# Classes
# Examples
letter
16
26
15000
poker
10
10
1000000
the original data, and evenly distribute them among the local learners, which implies that T' = 150000. For poker, we construct larger one including copies of the original data, and distribute them in the same way, which implies that T = 1000000. By default, we set n = 9 and use the complete graph, i.e., all nodes are connected to others.
The baseline in our experiments is the existing private vari- ant of D-OGD (PD-OGD) from Li et al. (2018). Note that the original PD-OGD can only achieve (e, 0)-DP for each round, instead of all T rounds. To make a fair compari- son, we increase the scale of noises added into PD-OGD to achieve (c. DD over all rounds. Moreover, following previous studies on DP (Abadi et al., 2016; Kairouz et al., 2021), we substitute the original gradient f(, by clipping gradient defined
golip i) fe,, max (I.
(VS,(XX(() C
4. Experiments
In this section, we conduct simulation experiments with con- vex functions to verify the performance of our algorithms.
where the constant C' is tuned from the set f0.01, 0.1, 1, 10} to obtain the best performance, and |1- denotes the Frobe- nius norm. In this way, the Frobenius norm of the clipping gradient is bounded by C, which simplifies the setting of noise scale when using the tree-based private aggregation. Additionally, for the parameter h of our algorithms, we multiply the theoretical value by a constant tuned from the set (0.0001, 0.0005, 0.001, 0.005.... ..., 10, 50} for the best performance. Other parameters of all algorithms are set as what their corresponding theories suggest.
4.1. Experimental Setup
Following previous studies (Zhang et al., 2017; Wan et al., 2020), the problem of decentralized online multiclass clas- sification is considered. Specifically, let p and y denote the number of features and classes, respectively. The decision set of is defined as K = [X E [ || I r). where ||X||= denotes the trace norm of X and = 10. At each round & E [T]. the loss function of each local learner is defined as
4.2. Experimental Results
Figures and 2 show the comparisons of average loss and nuntime of all algorithms with 10 on letter and poker, re- spectively. First, in terms of average loss, our PD-FTGL and PD-OCG are much better than PD-OGD. This is because the noise scale required by PD-OGD to achieve the same privacy level is much larger than our algorithms. Second, the average loss of our PD-OCG is worse than that of our PD-FTGL on both datasets, which can be viewed as the price of the projection-free property and is consistent with our theoretical results. Moreover, from the comparison of runtime, PD-OGD is much worse than our PD-FTGL. It is worth noting that this is because PD-OGD performs the projection operation once per round, whereas our PD-FTGL only needs one projection per block. Additionally, we also notice that our PD-OCG can be implemented faster than our
fr,(X) = log 1+ Σ ((xFe.10)xx())0000)
(t)(
where e;(t) E I²' and (t) E [g] denote the feature vector and class label of the single example at round f, x_ is the i-th row of the matrix for any i E [4]. and = argmax x (t) is the predicted class label based on the matrix X. Then, let (t) E K. denote the decision of each local learner i at each round t. Its average loss at this round equals to iL, = rm Σ'= Σj=1
Moreover, we use two publicly available datasets- and poker from the LIBSVM repository (Chang & Lin, 2011), 1), and their details are summarized in Table 2. For letter, we construct a larger one including 10n copies of
8

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
3.75
250
PD-FTGL
PD-OCG
3,50
200
Average Loss
PD-OGD
Runtime (s)
3,25
150
3.00
100
PD-FTGL
2.75
PD-OCG
50
PD-OGD
0
2.50
50000
100000
150000
50000
100000
150000
Number of Iterations
Number Iterations
(a) Average Loss
(b) Runtime
Figure 1. Comparison of all algorithms with 10 on the letter dataset, where we use the complete graph with n 9 nodes.
3.5
1200
PD-FTGL
PD-OCG
3.0
1000
PD-OGD
Average Loss
2.5
PD-FTGL
Rantime (s)
800
PD-OCG
600
PD-OGD
1.5
200
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Number of Iterations (x 10%)
Number of Iterations (x 106)
Average Loss
(b) Runtime
Figure 2. Comparison of all algorithms with 10 the poker dataset, where the complete graph with nodes.
PD-FTGL both datasets, which verifies the benefit of the projection-free property. Besides these experimental results, we have also evaluate the performance of our algorithms under different privacy levels, network sizes, and topologies, which can be found in Appendix B.
plex decision sets, propose projection-free variant of PD-FTGL, and establish Ö(n(T3/4 (T(//(4) and ((n +)= regret bounds for convex and strongly convex functions, respectively. These results can nearly match the regret bounds of the best existing projection-free free D-OCO algorithm in the non-private case for 1(7-1/2) and e = (2TT22/3) respectively. However, there still exist some open problems. First, it is appealing to investigate whether our PD-FTGL nearly optimal for any privacy level e or not. To this end, we need to establish general lower bounds for D-OCO with the DP guarantee, which seems highly non-trivial since there still lack such results even in the special case with = 1. Second, as later dis- cussed in Appendix A, it is possible to improve the regret of OCO with the DP guarantee via a lazy OCO technique the adversary is oblivious. Thus, is also natural to extend this improvement into the D-OCO setting.
5. Conclusion and Future Work
In this paper, propose the first algorithm to achieve (c, 0)- DP over all T rounds for D-OCO, namely PD-FTGL, and demonstrate that it enjoys O(n(p-1/4 + p/AA// and ((n(p11/2 + 1)) regret bounds for convex and strongly convex functions, respectively. These regret bounds are tighter than those achieved by existing D-OCO algorithms with only (eT, 0)-DP over all T rounds, and nearly match the lower bounds for D-OCO in the non-private case for = (Vv)). Furthermore, to efficiently deal with com-

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Acknowledgements
Asi, H., Koren, T., Liu, D., and Talwar, K. Private online learning via lazy algorithms. In Advances in Neural Information Processing Systems 37, pp. 74856-74889, 2024.
This work was partially supported by National Natural Sci- ence Foundation of China (62306275). Zhejiang Provincial Natural Science Foundation of China (LHZSD24F020001,
LMS255030002)), Ningbo Yongjiang Talent Introduction Programme (2023A-193-G) and Ningbo Natural Science Foundation (2024J206). The authors would also like to thank the anonymous reviewers for their helpful comments.
Chang, C.-C. and Lin, C.-J. LIBSVM: A library for support vector machines. ACM transactions on intelligent systems and technology, (3): 2011.
Chen, L., Zhang, M., and Karbasi, A. Projection-fiee bandit convex optimization. In Proceedings of the 22nd Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2047-2056, 2019.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, L., Ding, X., Zhou, P., and Jin, H. Distributed dy- namic online learning with differential privacy via path- length measurement. Information Sciences, 630(C):135- 157, 2023.
References
Cheng, H., Liao, X., and Li, H. Distributed online private learning of convex nondecomposable objectives. IEEE Transactions on Network Science and Engineering, 1 11(2): 1716-1728, 2023.
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, I.. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Duchi, J. C.,, Agarwal, A., and Wainwright, M. Dual aver- aging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions Automatic control, 57(3):592- 606, 2011.
Abernethy, J., Bartlett, P. L., Rakhlin, A., and Tewari, A. Optimal strategies and minimax lower bounds for on- line convex games. In Proceedings of the 21 Annual Conference on Learning Theory, pp. 415-423, 2008.
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3-4:211 1-11111-72111 2014.
Agarwal, N. and Singh, K. The price of differential privacy for online learning. In Proceedings of the 34th Inter- national Conference on Machine Learning, pp. 32 32,40, 2017.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptog- raphy, pp. 265-284, 2006.
Agarwal, N., Kale, S., Singh, K., and Thakurta, A. Differ- entially private and lazy online convex optimization. In Proceedings of the 36th Conference on Learning Theory, pp. 4599 4632, 2023.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Dif- ferential privacy under continual observation. Proceed- ings of the 42th ACM Symposium on Theory of Comput- ing, pp. 715-724 2010.
Agarwal, N., Kale, S., Singh, K., and Thakurta, A. G. Im- proved differentially private and lazy online convex opti- mization. In Proceedings of the 41st International Con- ference Machine Learning, pp. 343-3633 2024.
Enc, A., Nguyen, H. L., and Vladu, A. Projection-fire -free ban- dit optimization with privacy guarantees. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp. 7322-7330 2021.
Asi, H., Feldman, V., Koren, T., and Talwar, K. Near- optimal algorithms for private online optimization in the realizable regime. Proceedings of the 40th Interna- tional Conference on Machine Learning, pp. 1107-1120, 2023a.
Frank, M. and Wolfe, P. An algorithm for quadratic pro- gramming. Naval Research Logistics Quarterly, 3(1-2): 95-110, 1956.
Fredrikson, M., Jha, S., and Ristenpart, T. Model inver- sion attacks that exploit confidence information and ba- sic countermeasures. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 1322-1333, 2015.
Asi, H., Feldman, V., Koren, T., and Talwar, K. Private online prediction from experts: Separations and faster rates. In Proceedings of the 36th Conference on Learning Theory, pp. 674,699, 2023b.
10

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Garber, D. and Hazan, E. A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3): 149)))929--888 2016.
Kalhan, D. S., Bedi, A. S., Koppel, A., Rajawat, K., Hassani, H., Gupta, A. K., and Banerjee, A. Dynamic online learning via Frank-Wolfe algorithm. IEEE Transactions on Signal Processing, 69:932-948 947, 2021.
Garber, D. and Kretzu, B. Improved regret bounds for projection-free bandit convex optimization. In Proceed- ings of the 23rd International Conference on Artificial Intelligence and Statistics, pp. 2196-22066 2020.
Kretzu, B. and Garber, D. Revisiting projection-fre free online learning: the strongly convex case. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pp.
2021.
Garber, D. and Kretzu, B. New projection-free algorithms for online convex optimization with adaptive regret guar- antees. In Proceedings of the 35th Conference on Learn- ing Theory, pp. 2326-2359, 2022.
Levy, K. and Krause, A. Projection free online learning over smooth sets. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pp. 1458-1466, 2019.
Garber, D. and Kretzu, B. Projection-free online exp- concave optimization. In Proceedings of the 36th Confer- ence on Learning Theory, pp. 1259-1284, 2023.
Li, C., Zhou, P., Xiong. L., Wang, Q., and Wang. T. Differ- entially private distributed online learning. IEEE Transac- tions on Knowledge and Data Engineering, 3048):1440- 1453, 2018
Hazan, F. Introduction to online convex optimization. Fown- dations and Trends@ in Optimization, 2(3-4):157-325, 2016.
Li, X., Xie, L., and Li, N. A survey of decentralized online learning. Annual Reviews in Control, 56(100904), 2023.
Hazan, E. and Kale, S. Projection-free online learning. In Proceedings of the 29th International Conference on Machine Learning, pp. 1843-1850, 2012.
Liu, J. and Morse, A. Accelerated linear iterations for distributed averaging. Annual Reviews in Control, 35(2): 160-165, 2011.
Hazan, E. and Minasyan, E. Faster projection- free online learning. In Proceedings of the 33rd Conference on Learn-
Lü, Q., Zhang, K., Deng, S., Li, Y., Li, H., Gao, S., and Chen, Y. Privacy-preserving decentralized dual averaging for online optimization over directed networks. IEEE Transactions on Industrial Cyber-Physical Systems, 1:
ing Theory, pp. 1877-1893, 2020.
Hazan, E., Agarwal, A., and Kale, S. Logarithmic regret al- gorithms for online convex optimization. Machine Learn- ing, 69(2):199-192, 2007.
79-91, 2023.
Hosseini, S., Chapman, A., and Mesbahi, M. Online dis- tributed optimization via dual averaging. In Proceedings of the 52nd IEEE Conference on Decision and Control, pp. 1484 1489, 2013.
Mhammedi, Z. Efficient projection-free online convex op- timization with membership oracle. In Proceedings of the 35th Conference on Learning Theory, pp. 5314 5390, 2022.
Hou, M., Li, D., Wu, X., and Shen, X. Differential privacy of online distributed optimization under adversarial nodes. In Proceedings of the 2019 Chinese Control Conference, pp. 2172-2177 2019.
Chalev-Shwardh and Singer, Y. A primal-dual perspective of online learning algorithms. Machine Learning, 69:115 142, 2007.
Shokri, R., Stronati, M., Song, C., and Shmatikov, V. Mem- bership inference attacks against machine learning mod- els. In Proceedings of the 2017 IEEE Symposium Security and Privacy, pp. 3-18, 2017.
Jaggi, M. Revisiting Frank- Wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th Inter- national Conference on Machine Learning, pp. 427-435. 2013.
Jain, P., Kothari, P., and Thakurta, A. Differentially private online learning. In Proceedings of the 25th Conference on Learning Theory, pp. 2, 2012.
Smith, A. and Thakurta, A. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems 26, pp. 2733-2741, 2013.
Kairouz, P., Mcmahan, B., Song, S., Thakkar, O., Thakurta, A., and Xu. Z. Practical and private (deep) learning without sampling or shuffling. In Proceedings of the 38th International Conference on Machine Learning. pp. 5213-5225, 2021.
Wan, Y. and Zhang, L. Projection-free online learning over strongly convex sets. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp. 10076-10084, 2021.

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Wan, Y., Tu, W.-W,, and Zhang, L. Projection-free Dis- tributed Online Convex Optimization with O(v Com- munication Complexity. In Proceedings of the 37th In- ternational Conference on Machine Learning, pp. 9818- 9828, 2020.
Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp- 118-129, 2024a.
Zhang. K., Lü, Q., Liao, X., and Li, H. Zeroth-order de- centralized dual averaging for online optimization with privacy consideration. IEEE Transactions on Emerging Topics in Compulational Intelligence, 86):3755-3776. 2024b.
Wan, Y., Wang, G., and Zhang. L. Projection-free dis- tributed online learning with strongly convex losses. arXiv:2103.11 1102vl, 2021a.
Zhang, W. Zhao, P., Zhu, W., Hoi, S. C., and Zhang, Projection-free distributed online learning in networks. In Proceedings of the 34th International Conference on Machine Learning, pp. 4054-4066 2017.
Wan, Y., Xue, B., and Zhang, L. Projection-free online
learning in dynamic environments. Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp. 10067-10075, 2021b.
Zhou, H., Xu, Z., and Tzoumas, Efficient online learning with memory via Frank- Frank-Wolfe optimization: Algorithms with bounded dynamic regret and applications to control, In Proceedings of the 62nd IEEE Conference on Decision and Control, 2023.
Wan, Y., Wang. G., Tu, W.-W., and Zhang, L. Projection- free distributed online learning with sublinear commu- nication complexity. Journal of Machine Learning Re- search, 23(172))7442-794) 2022.
Wan, Y., Zhang, L., and Song, M. Improved dynamic regret for online fralk-wolfe. In Proceedings of the 36th Annual Conference on Learning Theory, pp. $304-3327 2023.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference Machine Learning, pp. 928 936, 2003.
Wan, Y., Wei, T., Song, M., and Zhang, L. Nearly optimal regret for decentralized online convex optimization. In Proceedings of the 37th Conference on Learning Theory, pp. 4862-4888, 2024a.
Wan, Y., Wei, T., Xue, B., Song, M., and Zhang, L. Optimal and efficient algorithms for decentralized online convex optimization. arXiv:2402.09117 2024b.
Wang, Y. Yang, W., Jiang, W., Lu, S., Wang, B., Tang, H., Wan, Y., and Zhang. Non-stationary projection- free online learning with dynamic and adaptive regret guarantees. In Proceedings of the 38th AAAI Conference Artificial Intelligence, pp. 1567 1-5799,,,,,, 2024.
Watts, D. J. and Strogatz, S. H. Collective dynamics of woold'- networks. Nature, 393:440 442, 1998.
Xiao, L. and Boyd, S. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
Yan, F., Sundaram, S., Vishwanathan, S., and Qi, Y. Dis- tributed autonomous online learning: Regrets and intrin- sie preeeering properties. IEEE Transactions Knowledge and Datu Engineering, 25(11):2483-2493, 2013.
Ye, H., Luo, I.., Zhou, 7.,, and Zhang, T. Multi-consensus decentralized accelerated gradient descent. Journal of Machine Learning Research, 24(306): 2023.
Zhang, C., Wang, Y., Tian, P., Cheng. X., Wan, Y., and Song, M. Projection-free bandit convex optimization over strongly convex sets. In Proceedings of the 28th
12

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
A. Additional Related Work
Here, we first introduce some recent efforts for improving the regret of private OCO algorithms under additional assumptions on functions, decision sets, or the adversary. Then, we briefly review the progress of projection-fre OCO algorithms.
A.1. Improved Private Algorithms for OCO
Similar to previous tree-based private algorithms, Agarwal & Singh (2017) propose an ()-D) algorithm for online linear optimization to achieve an improved regret bound of Ö(VT + )) Very recently. several DP algorithms have been proposed to achieve more desirable regret bounds for OCO with an oblivious adversary. Specifically, Asi et al. (2023a) consider a oblivious and realizable setting where a zero-loss solution exists, and demonstrate that the regret of the algorithm in Kairouz et al. (2021) can be significantly improved for convex (and smooth) functions. By exploiting recent advances on a lazy OCO setting where the decision can only be switched under limited budget, Asi et al. (2023b) develop an (e, 0DDP algorithm to achieve an Ö(vT+ + e -1T2/33 regret bound for convex functions. Following the lazy OCO technique, Agarwal et al. (2023) propose an improved (e, 6)-DP algorithm that can reduce the dependence of the regret bound of Asi et al. (2023b) on the dimensionality. Note that the original algorithm of Agarwal al. (2023) requires the smoothness of functions, which is removed by Agarwal et al. (2024) with careful modifications. Furthermore, Asi et al. (2024) consider the high privacy regime with <> 1, and achieve the (e, 6DD and Ö(VT + +e -2/3T11/3 regret bound via the lazy OCO technique.
A.2. Projection-free Algorithms for OCO
The first projection-free OCO algorithm is proposed by Hazan & Kale (2012), which is called online conditional gradient (OCG) and can achieve an O(T3/4) regret bound. Following this work, there is growing research interest in improving the regret of projection-frre OCO for special types of functions and decision sets (Garber & Hazan, 2016; Kretzu & Garber, 2021; Wan & Zhang, 2021; Levy & Krause, 2019; Hazan & Minasyan, 2020; Garber & Kretzu, 2022; 2023; Mhammedi, 2022). Among these works, the closest one to this paper is Wan & Zhang (2021), which develops a variant of OCG to achieve an (T2233 regret bound for strongly convex functions. Moreover, several projection free algorithms have been extended into the bandit setting (Chen et al., 2019; Garber & Kretzu, 2020; Kretzu & Garber, 2021: Zhang et al., 2024a), where only the loss value is revealed to the learner, instead of the full- full-information of functions. Recently, there has also been surge of research interest in developing projection-fre free OCO algorithms for non-stationary environments (Kalhan et al., 2021; Wan et al., b02 2023; Zhou et al., 2023; Wang et al., 2024), in which the regret is replaced with two more suitable metrics called adaptive regret and dynamic regret.
B. Additional Experimental Results
Note that these additional experiments are all conducted on the letter dataset. Moreover, we set 10, 9, and use the complete graph by default. As shown in Figure 3, we first compare the average loss of our PD-FTGL and PD-OCG with different privacy levels, i.e., E (2.5, 5, 10). We find that our two algorithms perform better as the value of increases. Moreover, compared with PD-FTGL, the average loss of PD-OCG varies less among different which implies that the privacy level has a weaker impact on PD-OCG. This is consistent with our theoretical results for convex functions, since the privacy-dependent term in the regret bound of PD-FTGL is Ône 11p1/4 /T) and that of PD-OCG is Ö(ne -1T2/4). ((n--111/4) Then, as shown in Figure 4, we compare the average loss of our algorithms with different network sizes, i.e., n E {9, 16, 25). As the network size increases, the average losses of our two algorithms become slightly worse, which is consistent with the dependence of our regret bounds on n.
Finally, we conduct experiments to verify the effect of different network topologies on our algorithms, including the complete graph, cycle graph and Watts-Strogaa (abbr. ws) graph (Watts& & Strogatz, 1998). Among these graphs, the complete graph has the largest spectral gap p. In contrast, the cycle graph, where each local learner is connected to only two neighbors, has the smallest p. The ws graph is generated by a random technique with tunable parameters including the average degree and rewiring probability. We set the average degree of the graph to be and the rewiring probability to be 0.5. As shown in Figures 5(a) and 5(b), for the graph with larger p. the average loss of PD-FTGL becomes worse when e 10, but becomes better when 1000. These opposite effects are due to the fact that the ((n(p-(( 114 e //p/A)/T) regret of PD-FTGL is dominant by Önne /T) and Ö(pp 1/4 /T) for e = 10 and e 1000, respectively. From Figures 5(c) and 5(d), the average loss of PD-OCG is almost unaffected by the topology of graph for both values of e, which is reasonable because the regret bound of PD-OCG does not depend on p.
13

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
3.75
3.75
=
10
E 10
5
3,50
3.50
Average Loss
= 2.5
Averago Loss
& 2.5
3,25
3.25
3.00
3.00
2.75
2.75
2.50
2.50
50000
100000
150000
50000
100000
150000
Number of Iterations
Number Iterations
(a) PD-FTGL
(b) PD-OCG
Figure Comparison the average loss of our algorithms with different 6, where we use the complete graph with n nodes.
3.75
3.75
n 9
NA
n = 16
n 16
3.50
3.50
Average Loss
n = 25
Average Loss
25
3.25
3.25
3.00
3.00
2.75
2.75
2.50
2.50
50000
100000
150000
0
50000
100000
150000
Number of Iterations
Number of Iterations
(a) PD-FTGL
(b) PD-OCG
Figure 4. Comparison of the average loss of our algorithms with e 10 and different n, where we use the complete graph.
C. Proof of Privacy Guarantee in Theorem 3.6
We define X (X(I), ..., ((T/L)), where X(=) (x)( x, (=)) for [T/L]. For any variable which is generated under loss function sequence F, use x' to denote the same variable that is generated under F.
It is not hard to verify that
|r| S] Pr[X's E E
max Pr[X E
max
SCKEXT/L
CEK
Pr
where & (E(1).....E(( (((I).....((T/L)) with {(2) denoting any possible value of X2)).
Thus, prove the (c, 0)-DP guarantee of Algorithm only need to prove that
T/L
Pr X = Pr X' [ II
E(3), X(2 1) = {(2 - 1]] P2 = {(2) X'()) (()) = x = E(3)...., 1) {( 1)] S ee.
Pr X((2) = {(2) x(1) = x() =
((2),
Specially, for : = 1 the decisions of all local learners are set to be 0, which is independent with loss function. As a result, the privacy can not leaked. For 2 2 2, since each (2) depends on 2 - 1). and 2, - 1) is the combination of nodes on the private binary tree specific form, according to lines 11 to 12 Algorithm we can say that all binary trees
14

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
3.75
3.25
complete graph
complete graph
ws graph
ws graph
3.50
3.00
Average Loss
cycle graph
Average Loss
cycle graph
3.25
2.75
3.00
2.50
2.75
2.25
2.50
2.00
100000 Number Iterations
50000
150000
50000
100000
150000
Number of Iterations
(a) PD-FTGL with = 10
(b) PD-FTGL with = 1000
3.75
3.75
complete graph
complete graph
ws graph
ws graph
3.50
3.50
Average Loss
cycle graph
Average Loss
cycle graph
3.25
3.25
3.00
3.00
2.75
2.75
2.50
2.50
50000
100000
150000
100000 Number Iterations
50000
150000
Number of Iterations
(c) PD-OCG with 10
(d) PD-OCG with 1000
Figure 5. Comparison of the average loss of our algorithms with different graphs, where we set n 9.
maintained by the local learners jointly determine the decision set X. Note that in each block, each local learner operates on the same nodes its own private tree via Algorithm in parallel. For brevity, we use m = [log; (T/L -1] and label all the Let (r) denote the noised value in the r-th node
nodes of binary tree in an post-order traversal order 1,..., 2 of the binary tree maintained by learner for any [n]] and E m2 1]. We use S(r) = (r) .r..................... S, (r)) to denote the set of noised values node position on the privacy trees of all local learners [n] and S (5(1). ((2m++ 1)) to denote the set of all nodes from all private trees BI...., Br. Moreover, let T (T(I)..... ((2mh 1)) denote any possible value of S, where ((r) = (r,).,.......))) for any [2m-1 - 1].
Due to the post-processing immunity theorem (Dwork et al., 2006), proving the (c, 0) property for Algorithm can be transferred to proving that
$ r
2
Pr ([()(r) ((r) (())))(1)..))) (())..., S - T(r 1)
Se.
(12)
Pr
Š' = T
Pr (*()) T(r) ('(() (')).....(( T(r -00-11
Under the conditions 5(1) = T(I) S(r 1) 1) and - ( 11 T(r 1), the local decisions determined by the nodes from 1 to 1 are also fixed, as well as all leaf nodes among these nodes. Furthermore, since the noise for each node of the binary tree for each local learner is independently sampled from the same Laplace
15

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
distribution D, each factor in the above product satisfies
Pr ((r) = (() $(1) = ((1) 1)) T(r
Pr ('())= T(r) (1) T()....,, St(r 1) = -(r
Pr (r) wi (r), ...)),...,...... (r) wr((r) ((() T(1), ..... S(r - 1) T - 1) -
Pr (r) (r). (r) = un. (r) (1( = r(1), 8'(r - 1) = r(- 1)
(13)
Pr (r) = wi (r) - (r) ... (r) = wn (r) - (r) $(1) = T(1), (
-( T(r - 1) 11)
Pr (r) = (r) - (r) (r) = wn (r) - s,) (1(1 = T(I). ((()....,,.((- -1) = T(r - 1)
pdf (r) = wi (r) - si (r), br(() = wr - sr) | $(1) = r()) 3(r 1) = -)
pdf
[(((r) wi (r) - (r), .......................... (r) wi, (r) (r) (1( T(I). ........................ Sr 1) T(r
where (r) denotes the noise added in the r-th node of local learner and s:(r) denotes the original value of this node. The second equality is due to lines 5 to 7 in Algorithm 2, which implies that (.(r) = s;(r) + b,)r). Then, by substituting the
probability density function of D Lap" (0. 6v de (G + (2 + log, T)), we have
pdf (r) = w1 (1)) - 1s sr))) ..... (r) = (r) - (r) S(1) = T()) 5(r - 1) T(r - 1
pdf [T(() = wi()) - - (r),...... ( wr (r) - (,)
(1( T()=)(()...)))))))))) + 1)= T(r - 1)
(rlw. BVZ(G+a)) log,
= I2Vä(G+aR/(2tlo exp
(14)
<)lw)(()-
12/06+aR](2+o0 7) exp
bvd(G++a))(2-oog T)
((lwi(r) - -
- [wi(r) - (()()l)))
}
dis((r) (r(r))l exp (6 + a2) + log, T)
S II 1=1
exp
6VZ(G + R2) + logg 7)
According to Algorithm 2, (r) is the sum of the original value of all its descendant leaf nodes. Due to the definition of DP, F and F only differ in at most one local loss function. We assume they differ at the r-th iteration for local learner
j and denote 2, as the block that time step is in. According to line 14 in Algorithm 1, wr(z 1) d (2 1) is the original value of lcaf nodes. Let the r--th node denote the leaf node that contains the noised version of c (2+ - 1). Here, we consider two cases.
1. Node r, is not descendant of node Since we compute the bound under the condition that all nodes 1 to r in binary trees of all local learners are fixed, the local decisions of all local learners generated by these nodes are also the same under F and F'. Since the original values in descendant leaf nodes of r depend on a subset of these decisions and the loss functions on the blocks of these leaf nodes are also the same under FF and F', these original values are the same as well, which implies that
(|s((r) - (t(r))l = O.
2. Node r, is a descendant of node r: The condition that the local decisions determined by nodes 1 to r - 1 are the same still holds. However, since F and J' differ at iteration t, the original value of rr, i.e., of (z+), differs between F. and F. Moreover, since loss functions on other time steps are the same in F and F', we have
(r) - (r)) = [ld(((z)) - df \I < (z,) - d'(z+)ll + l|d
a + - -
(15)
According lines 9 to 10 in Algorithm 1, gradients on one block do not interfere with each other, which implies that
| a(2+))
(VVi,, (x,(2)) -xx((=)))) (V (xx(2++) axx
n
2G
16

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Then, by using Lemma D.3, we have
AL(G + aR)
(z,) -d (2+))) + (2)) d(2))]
nf
We naively bound the f--norm of a vector by ||x||| - vd[x=| where d denotes the dimensionality of x. By substituting the above bound of (z,) - d(2,)ll and the above inequality into (15), we finally have
||<(Cr) (r)ll - va
ALLG + aR)
2G n
6 d(G++al
nT
n
By substituting the above bound of [r+((r) s,(r)]l into (14), bound (13) by
1) T(r - -1) (r T(1)...., Pr (((r)= (1) =
Pr [(())= T(r) ((1)
...
6vā(G+aRt
ne
S exp
e 2fllgg T
- = ((r (r--1)
6vd (2)
+ 1og2
Now, we can obtain the bound for each factor in the product of (12) by substituting the above inequality into (13). Moreover, since under the condition that when considering the node r for r E [2m++1 - 1]. noised value in nodes 1 to - are fixed, a change the value of a leaf node affects only its ancestor nodes, which total m + nodes. Since the same position nodes in the private trees maintained by each local learner are operated in the same block, changing one factor of the product in (12) will only affect m + 1 other factors, where m 1 is the number of layers in the binary tree. By substituting m [log2 (T/L. L - 1)7, we can finally prove the (c, O)-D guarantee for Algorithm 1 by
Pr r
e 2410gg Se.
S' =
D. Proof of the Regret Bound in Theorem 3.6
For any E [T/L], we define a virtual global decision
Σ a()),x + a(z 1) + 2h
argmin
||x|
(16)
xEk
2
where d(T)= = E regret Ri, will be bounded well.
(r)... As in Lemma D.I, we first notice that if the local decision x, (2) is close to y(2 + 1), the
Lemma D.I. Suppose Assumptions 3.1, 3.2, 3.3, and 3.4 hold, and (1) y(2+ 1)Il S B(=) for any E [n] and
= E LT)L), where E(z) is related to 2. Then, for any E [m]. Algorithm I satisfies [[RT,,] < 3nGL. E.GI E(=) + nnR
Instead of directly bounding the distance between (2) and f(z + 1), we further introduce an intermediate variable, i.c., a non-private version of (2) defined as (1) = 0 and
(=(=) = arginin(z 1), + a(2 -2) 2h ||x
xeK
for z 2 2, where 21(2) Σi=1 (T( are the non-private partial sum. Then, it is easy verify that
E [1]xx(2) y(= + 1)ll [[]x - yx(=))ll + (1x((2) y(= + +)ll-
(17)
To bound [2] y=(=)]]}, we introduce the following lemma.
Lemma D.2. (Lemma 5 in Duchi et al. (2011)) Let (u 7) argmin (u, [|/
We have
1 u -l--vvi vll-
[Tx (u, m) II mlll
n
17

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Let (r( denote the noise added for node in the private tree of local learner i. Due to the variance of noise distribution D. for any i [n] and E [2llog,(T/L-]]] 1], we have
[Va(G+aR)pe + log, 22) )))² 72d
Vd(G++af))? logg T)
E [|b(()) S 2
Then, let S, denote the set of nodes selected to compute the private sum 2,(z - 1). According to Algorithm 2, for any i [n]. we have [ < [Togg(T/L 1)1 + 1, because there is at most one node for each level of the private tree in the set St. Applying Lemma D.2 and combining the above inequality, for any E [xx] and 2, we have
12:(2 1) z.(= 1)ll
9d (G a.l)) (2 + log2 T)
E [[]x - (=)l < E
(18)
a(z - 2) + 2h
a(= 2) + 2h
c(a(2 - 2) + 22)
rES.
Next, we analyze the bound [lyx(z) - 8(2 + 1)1l, which requires an additional lemma. Lemma D.3. Let d(z) = n Ei= di(z). Under Assumptions 3.1, 3.2, 3.3, and 3.4, for any i E [n] and = E [T/L], when setting parameters as in (7), Algorithm/ ensures that
-x)= 2L aaR)
(19)
nT
Applying Lemmas D.2 and D.3, for any 2 2, we have
1
2(z 2 2) 2 aR)
2(G + aal
[lx;(z) 8(= 1)ll < a( 2)I 2h r=1
dd - a(T)l <
(20)
nT(aa(= - 2) + 2h) n(a(z 2) + 2h)
Now, we still need to analyze 1y< 1) y(2 + 1)ll- To this end, we define (x(xx (a(z).x) + aع | 2 and Jx(x) Σi= (x( 2|2 for any [T/T.]. It is easy to verify that the function J=(x) is (azl. + 2h stronnly convex and f(2 + 1) argmin (x)x).
Moreover, as proven by Hazan & Kale (2012), for any X-strongly convex functions f(x) over the set K. with x" argminxex (x)), it holds that
|xx 1|2 S f(x) - f(x'), Vx K.
(21)
2
Combining (21) with the strong convexity of (x()), for any 1 S 2' S 2, we have
[19(=') 8(= + 1)11 <
- J1(()=++))+)))))
azT. + 2h
(J (Jz-( J -x+ azL + 2h
2
Σ
azL + 2h
-=
<
(4((((2))) - (- 1)))
azL + 2h
T=2f-1
Additionally, for any 2 1, it is easy verify that
- y <||a(= (x) f, (y)l - (x), y) > [[V2. -
- 1) + aLx|| | - yll
Σ d.(z 1)1l + - ||--X|| < L(G + 2aRt ||x - -yll
where the last inequality is due to the following inequality derived under Assumptions 3.1 and 3.2
max xE[m]
[2)( = max
Σ
fe, - axx())) -x);)))))
S max rEIn)
Σ
(l/ (x, +
+| (x)l) < L(G + aR). (22)
=E(n.
B
18

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Then, for any 15 2' S 2, have
2
- azL + 2h
2 I) - 2aR).
(23)
Combining (18), (20) and the above inequality, for 2 2, have
2 + all)
9d (G ( al) (2+ log, 2)2
4L + 2a
E X (=)]l + (z), - (2 +(2+11) 1)1l nla(z - (0)(z--)---0 + 2h)
<(a(z - 2) + 2h)
azL + 2h
For 1, due to x; x;(1) - (1) = -(11) = 0, we have
(G + 22
(1) - yx) + Iy:(1) - <
aL + 2h
Finally, we can derive the regret bound in Theorem 3.6 by first substituting the above two inequalities into (17) and then using Lemma D.I.
E. Proof of Lemma D.1
According to Assumptions 3.2 and 3.3, for any KC, it is not hard to verify that
(x)( - (x),(x)
{x))({[(3)) fx)(x) + G||xx (=)=l
< (x)) x) - 1x, - Gxxx()))))))>-----)>)>>>)) (=)l
(V (1))))))((((+))))))))))
x|| -x] (V.,) y(2 + 1))
a -
(24)
- (|/+) xx)]
0 xx,(2) - x|| + 2G [x) y(2 + G||x - y(2 + 1)1l-
Recall that we suppose for any E [n] and E L], there exists a [(=) such that E [1|xx(=) - 5(2+ + 1)Il S B()). Then,
we have
- < (x), (xx)
x) クh |x, x|| 3GE
Furthermore, we notice that
[x,(2) - x||² = - (
1) + 117(2 +1) x|
-1xx -==-====)))(2==(((,))=====--- x) + |||| 115(2 + 11
(25)
2 (x).
+ |x| [| (2 + 1)|1.
Combining the above two inequalities, for any 2 2 and x E Kc we have
E (x), - fx,, & (Vfi,(((())) - ax, (z), 8(2 + 1) -
[xx| 11y(2 + 1)11²) + 3GE(2).
2
By summing up the above inequality overall T iterations and n local learners, for any x E IC, we have
T/LL
E(RT E
ΣΣΣ (Jes(x(())) - -
1=T:=11
T/L
T/T.
ΣΣΣ 8
(x))
x (|x|I2 - -15((2 1)I?))
3GE(z)
(26)
j=1
J=
T/L
T/L ()))),(=++1-x)) x)+ -))1))xx++++ a (15(3+ [|](=+1)11+00 1)||~~1||[] -1xx1²)) + 3nLG Σ
al
To bound the first term in the right side of (26), we introduce the following lemma.
19

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Lemma E.1. (Lemma 6.6 in Garber & Hazan (2016)) Let (((x)){=1 be sequence of functions and xi
xxx (x
(x))fffor for all t E [TT. Then, it holds that
T
Σ f((x))
min XEX
f(()=
S.
Let (x(x) = 12 and (x(x) (d(z). + 4 | for any [T/L]. Then, for any x K, it easy to verify that
T/C
(d(z), 11 x)
aL
(117(2 1)]1 -11x1())
2
(27)
T/L S /||x||| ()
Σ
h h1ys== + 1)11 hR?
where the first inequality is due to Lemma E.1 and f(= 1) argmin Σi=o & (x). Finally, we complete this proof by substituting (27) into (26).
F. Proof of Lemma D.3
Let H* : (z) Raxd for O...., , and H-1 H7 According (5), is easy to verify that
H++1 (1 + 0) - 0H* for k = ...... L 1.
(28)
Moreover, according the convergence property of the accelerated gossip strategy, have the following lemma.
Lemma F.I (Proposition 1 in Ye et al. (2023)) Under Assumption 3.4, the iterations of (28) with = (1+ o -1 ensure that
HH H| S (1 (1 (1-
V2 V -2(1) (
||
where H = 111 HD and || || denotes the Frobenius norm.
Note that 1111 T 11" = [d(z)]: ;a()) ;...;; ;d(=)d
From Lemma F.I, we have
(1- (s) - d(=)ll s |11T 1 -11 H0 || S = (1- V2
V1 (1--
v1- 02(())
1 n
1 -11-1171 1
HO
n
s 22114
1- 1-(1-1)
1111]
1
VI 12(()
|
[2
'
= 22144
1- 1
1-11--1
-1-o)(p))
(2)11
/22
Let 1- 1 V2
Due to L = [4 /pl and c- < 4, it is not hard to verify that
(1-cV1-o2(P)) s 1 (10)))=s(((0/)0111111 102/))
4la(nTVIIm) V[-og(P)
$ (1--0/1-
In(nZvI4m) cV1-o2(P)
In(m7/I1m
(1 <1-co/1 /c/l oo2(p) In 1n(:00/1-2(11))
1
714n
where the first inequality due to c/1 - 0 P) < and the second inequality due to In -1 2 Combining the above two inequalities, we can finally derive the lemma as
x for any x >
- 2 2/14 [d
2 max [2)]
2L(G + aR)
nT /44n
n
n.
where the last inequality is due to (22).
20

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
G. Proof of Corollaries 3.7 and 3.8
For Corollary 3.7, by substituting a and = 14LT log, T)/ into (8), we have
T/L
2GRVT.
E [[Rr, S 4nGRy LT
LAGRVLT((11 log, T) nL Σ
(2 + loge T)
T/L
4dGR(2 + log2 T)
GR
mL
eVTL
VL [. + log2 7)
2=2
4ndGR(2 + log, T)3/2
S <TGRR/LT(2 logg T)
eVL.
Similarly, for Corollary 3.8, substitute > and h aL into (8) and obtain that
T/L
T/L
12G(G + 2x
27dG (G aR) (2 + logg T)2 +
6G aR) n
E[ & naLR + nL)
Σ
+ n..
Σ
a(z + 2)
acaL
==1
==2
12nGLIG+ R) (1 (T(L))
S naTR +
a
27ndG (G + aR) (2 + log, 2)² (1 In(T/L)) GnG(G + aR) (1+ (1+In(T/L)) ln(T/L)
24mGI 20 (1 (1+ (nT/n())
+ 27nd(G 2a (2 logg T)3
+ naLRR.
ac
H. Proof of Theorem 3.9
Since the operation of CG does not introduce any additional sensitive data, the (e, 0)-DP guarantee of Theorem 3.9 be proved in the same way that of Theorem 3.6 in the Appendix C. Therefore, here only prove the regret guarantee in Theorem 3.9. For 2 3, we define
(x) argmin F. (x) argmin (2:(2 - 1,)2-2),xx x) + a(2 3) 2h ||x||
xEX
2
For = and z = 2, we set x3 (2) = 0. Thus, when : = and = 2, we have ||x;(2) - x² (2)l = 0. For 2 2 3, since it is easy to verify that F. (x) (a(= - 3) str-stryy convex, we have
2
x (2) (=)) a(2 3) + +
To bound the approximation error of linear optimization steps in CG, we introduce the definition of smooth functions and a lemma about the convergence rate CG.
Definition H.1. A function f(x): K + called 3-smooth over IC, it holds that f(y) s f(x) + (Vf(x),y x) + || 2 for any x, K.
Lemma H.2. (Derived from Theorem 1 in Jaggi (2013)) If function Fxx) K. + IR is convex and 8-smooth, and |x|| S R holds for any x E K., Algoritiu 4 ensures F(x,) - minxek F(x) < 83R² / (L +2). 2).
By utilizing Lemma H.2 and the fact that F= (x) is (a(= - 3)L + 2h) -moothh we have
(FF=1(xx(12 - F F=-1(x;
4R
(xx(2) - (2) -x
(29)
a(= 3) 2h
VT.
Then, similar to the analysis in Appendix D, set (1) 0 and (2) = Σド= de (T) for 2 2. Morcover, define (1) (2) = 0 and for 2 3,
(z(z)= = argmin(z, x), + a(2 3) + 2h
|x|
XEE
2
21

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
Therefore, for = 1 and z = =2, it holds that (x)
yx(=)] 0. For 2 similar to (18) in Appendix D, it is easy to 9d (G + (d
verify that
(2)) + log T)2
E
(30)
<(a(2z - 3) 2h)
Next, following the analysis in Appendix D, we reuse the definition of (1)) in (16). Note that the value of L' in (10) is the
same as the value of L in (7). Therefore, according to the proof of Lemma D.3, it is easy to verify that df (T) - d(()) for
Algorithm 3 also enjoys the same upper bound as in (19) of Lemma D.3. By further combining with Lemma D.2, for 2 3.
we have
[zyx(z) - yy 2] S a(= 3)L + 2h
Σ
2
df (T) - -
< nT (oo0==3)L+++ 3)L+221 I 2 + aR)
2(2 - (aa-3)[G+++ +aR)
(31)
(a(: (3) + 2h)
7=1
Note that (23) in Appendix D also holds for Algorithm 3. Combining (31) and (23), for 2 3, we have
2 + aR)
6L + 2aRt
(z) - y(z + 1)ll (x) (== 2) + ||y(= [= 2) -(( 1)1l V
(32)
n (a(2 - 3) + 2h)
az + 2h
For = =1 and : = 2, since yi(1) = (2) = -1) = 0, we have
[ly(1)) y()) = (1) y()) < 2L + +2aR)
4L(G + 2aR)
(1x. (1) s(3)]
(33)
aL+ 2h
al 2h
where the two inequalities are due to (23).
Combining (24), (25), (29), (30), and (32), for any = 2 3 and x E K. we have
E (xi, (z)) - (r,( < fV, (2)) - ax, (2)) -
a (|x2|1 - 117(2 1))1))
2
+ 2GB (x) - x=)=]|| +GB||xx (x) ||]]
-
+ (=) - (2 + 1)1l (+)l) -y(= +1]l
S (x) (x,) (2). -x x)
a
2 (1|x|2 11 1)1{3)
12GR 27dG (G + a R) (log, T + 2) logz T e <a((= - 3)L + 2h)
GG(G al))
18GL + 2aRR
VI
n (a(z - 33 2h)
azL + +2h
For z = and = 2, similar to the above inequality, we can utilize (33) and xx) = =x( = -y((2) = -0 to show that
-2- (||x| 11 + 1)119) + 12GL + 22RR
(x)(x((=)) (x) S (x)))(xx(=)) axx(
aL 2h
Then, by summing up overall T' iterations and n local learners, we have
T/L
E
Σ
- fno(()))
-
j=1
T/L
(V)s)(x))))) - (x) - -) - a [[x]] 2 - 118(2 1)11)) + 24nGL + 2oll)
2
aL + 2h
LET. j=1
T/L
+nl
12GR
27dG (G + aR) (2 + log, T)2
6G + aR)
+ 18GL + 2xR)
(34)
VL
<(a(= -3)L + 2h)
n (a(z - -3)L + 2h)
azL + +h
3=3
T/L
T/L
<n
Σ
(a(s). +1+ -) + aL
x)
(1>(2 + -111= + nL Σ 2
24GL + 2aR)
azL + +2h
#=1
T/L
12GR
27d (G + aR) (2 + log, 2)2
60 + aR)
nL
Σ
VI
c(a(z -3)L + 22h)
n (a(2 - 3)L + +2h)
Note that (27) the proof of Lemma D.1 still holds here. easy to complete this proof by substituting (27) into (34).
22

---

Revisiting Differentially Private Algorithms for Decentralized Online Learning
I. Proof of Corollaries 3.10 and 3.11
For Corollary 3.10, by substituting a = 0, h VILLTG/ and L = VT into (11), we have
I
4nGR
T
12GR
4dGR(2 + logg T)²
GR
B| 4nGRT3/4
+
T1/4
+
TB
T1/4
eT3/
nT
1=1
4ndGRT (2 + log, T)²
21nGRTT//4
For Corollary 3.11, we a 0, aL and L 72/3 2/3 T) into (11), and obtain that
T/L 2AG 22 -2/3
E RT, & naR2T2/3 In 2/3 T + n
+ 2n
alz +
2ml
T/L
27dG (G + RR) (2 + log, T) log,
6G aR)
+
ac(: - 1)
na(z -
2=3
RaR212/3 In 2/3 T 24nGI(G + 20 [n 2/3 T + In 1/
12nGRT2/3 In 2/3T
a (2TdG (G aR) (2 + log, T) In(T/L)) log, T 6G(G aR) (1 In [n(T/L])
ac
na
36nGT2/3 (In (1-3/ + T (G + 2aR)
naRRT221 In -2/3
T 12nGRT2/3 2 27ndG + aR) (2 + log, T)²
aE
23


Reviews:
[{"review_id": "K8BgzJ03aG", "reviewer": "Reviewer_N7y3", "summary": "This paper revists the regret bound for differentially private onilne learning. Based on the block-decoupled accelerated gossip strategy, the authors achieved a refined uppper bound $O(n\\rho^{1/4}/\\epsilon\\sqrt{T})$ under $(\\epsilon,0)$-DP. Theoretical results are derived under certain assumptions.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\nQ1: ... the theoretical results rely on restrictive assumptions ... an empirical evaluation against existing methods would significantly strengthen the work.\n\nA1: 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).\n\nMoreover, 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.\n\n---\nQ2: ... comparison with existing literature on differentially private online learning is inadequate ...\n\nA2: 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). \n\nAlthough 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. \n\n---\nQ3: ... The main contribution seems to extending the non-private results of Wan et al. (2024) ... which is incremental ...\n\nA3: 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.\n\n1) 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.\n\n2) 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$.\n\nMoreover, 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.\n\n---\nQ4: … it is critical for the paper to establish similar matching bounds under differential privacy guarantees …\n\nA4: 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.\n\n---\nQ5: Regarding the references for MIA …\n\nA5: Thanks for this suggestion. We will cite the work of Reza et al. (2016) in the revised version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "There is no empirical evaluation under benchmark datasets. The proposed methods are evaluated under mathematical proof.", "theoretical_claims": "I have not had the opportunity to verify the proof carefully, but the results appear intuitively reasonable.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "No.", "essential_references_not_discussed": "1. Regarding the references for MIA, the authors cited He et al., which is not the original literature. So please incoroperate the original one [A]\n\n[A] Membership Inference Attacks against Machine Learning Models. Reza et al., 2016.", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper is well-written and easy to follow. The theoretical results presented are intuitive and clearly motivated.\n\nWeakness:\n\n1. The paper does not provide an empirical comparison with existing online learning algorithms. Given that the theoretical results rely on restrictive assumptions—which are often challenging to verify in practice—an empirical evaluation against existing methods would significantly strengthen the work.\n\n2. The comparison with existing literature on differentially private online learning is inadequate. The authors briefly state: `` Finally, we notice that many recent efforts have been devoted to improve the regret of private OCO algorithms (Agarwal & Singh, 2017; Agarwal et al., 2023; 2024; Asi et al., 2023a;b; Jain et al., 2023; Hilal et al., 2024), but additional assumptions on functions, decision sets, or theadversary are required.\"\n\nHowever, a detailed comparison with these works—particularly the most recent publications from 2023 and 2024—is necessary to clarify the novelty and position the paper within the current research landscape.\n\n3.The motivation and approach of this paper appear primarily derived from Wan et al. (2024). The main contribution seems to extending the non-private results of Wan et al. (2024) to the privacy-preserving regime, which is incremental. If there are additional, more substantial contributions, the authors should clearly specify them.\n\n4. The authors argue that the derived upper bound matches the lower bound in the non-private regime ($\\epsilon=\\infty$). However, it is critical for the paper to establish similar matching bounds under differential privacy guarantees. Without matching the lower bound in the privacy-preserving regime, the theoretical results may seem incomplete or insufficiently self-contained.", "other_comments_or_suggestions": "No.", "questions_for_authors": "See the weaknesses part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fpNeDHZyuH", "reviewer": "Reviewer_YmUH", "summary": "This paper proposes differentially private decentralized online learning algorithms that achieve regret bounds nearly matching those in the non-private setting. The algorithms can be adapted to be projection-free using Frank-Wolfe methods, resulting in a degradation of the regret bounds. However, these bounds still outperform existing private centralized projection-free online algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews!\n\n---\nQ1: ... 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.\n\nA1: 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. \n\nTherefore, 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.", "claims_and_evidence": "Theoretical evidence is provided to support the claims of improved regret bounds for the proposed algorithms.", "methods_and_evaluation_criteria": "Yes, for the following reasons:\n\n- Theoretical evaluation metrics, like regret bounds, are widely used to assess the theoretical performance of online learning algorithms.\n    \n- The regret bounds were compared to existing ones under a consistent set of standard assumptions, including a bounded constraint set, Lipschitz continuity of the gradient, and (strong) convexity of the objective function.", "theoretical_claims": "No", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "Theoretical findings advances the development of privacy-preserving decentralized algorithms for online learning problems.", "essential_references_not_discussed": "Essential references are included.", "other_strengths_and_weaknesses": "**1. Strengths** \n\n* The regret bounds for the proposed algorithms under privacy budget are derived for strongly convex and convex decentralized online learning, based on standard assumptions.\n\n- These regret bounds outperform existing ones and closely approach the optimal regret bounds in the non-private setting.\n\n- Additionally, the results for projection algorithms are extended to projection-free variants using Frank-Wolfe algorithms, which yield worse regret bounds.\n\n\n**2. Weaknesses** \n\n- Similar to projection operators on the constraint set KK, Frank-Wolfe methods on KK can be just as challenging to solve as the projection operator on KK. Therefore, it is inaccurate to claim that Algorithm 2 is a projection-free algorithm.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fsPQ7fVlxf", "reviewer": "Reviewer_dtv5", "summary": "This paper explores the problem of decentralized online learning in a private setting. Previous works fail to achieve $(0, \\delta)$-DP over $T$ iterations and do not attain an optimal regret bound comparable to the non-private setting. This paper introduces a blocking update mechanism, an accelerated gossip strategy, and a tree aggregation mechanism, which together enable nearly matching regret bounds in the private setting while ensuring $(0, \\delta)$-DP over $T$ iterations. Additionally, the paper leverages the classical conditional gradient method to develop a projection-free algorithm, which reduces computational costs but slightly degrades the regret bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\nQ1: No experimental results ...\n\nA1: 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).\n\n---\nQ2: ... discussion on ... DP-FTRL.\n\nA2: 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.\n\n---\nQ3: Privacy analysis clarity …\n\nA3: 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.\n\nMoreover, 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)$.\n\n---\nQ4: Novelty in decentralized online learning …\n\nA4: We want to emphasize that there do exist some technical novelties in our algorithm and analysis, instead of simply combining existing techniques.\n\n1) 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. \n\n2) 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$.\n\n---\nQ5: Line 247: Why is $\\bar{\\mathbf{d}}$ mentioned here?\n\nA5: 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.\n\n---\nQ6: Algorithm 1 (Lines 10-11) …\n\nA6: 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. \n\nBased 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).\n\nFor 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I reviewed the main framework of the proof but did not go through the step-by-step details.", "experimental_designs_or_analyses": "No experimental results performed.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "There is a lack of discussion on prior work related to DP-FTRL.", "other_strengths_and_weaknesses": "Strengths:\n- The paper is well-written and structured.\n- It presents a novel result in DP decentralized online learning, achieving $(0, \\delta)$-DP over $T$ iterations with a regret bound close to the non-private case.\n- It addresses practical computational challenges by introducing a projection-free algorithm to reduce computational costs.\n\nWeakness:\n- Privacy analysis clarity: The paper does not clearly explain how the private term is bounded or how sensitivity is calculated.\n- Novelty in decentralized online learning: While I am familiar with differential privacy, I am less familiar with decentralized online learning. Since the proposed approach utilizes existing techniques (blocking update mechanism, accelerated gossip strategy, and tree aggregation mechanism), I am unsure about the novelty of its contributions beyond theoretical analysis.\n- Experimental validation is lacking.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "1. Line 247: Why is $\\bar{d}$ mentioned here? give more explanations.\n2. Algorithm 1 (Lines $\\mathbf{1 0 - 1 1 ) :}$\n- Line 10: The local learner updates its model.\n- Line 11: Does this step indicate that communication with neighbors occurs within the same block update? Could you clarify the update process?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hwkTcHEC6Z", "reviewer": "Reviewer_J5zj", "summary": "Two types of algorithms for differentially private online learning (PD-FTGL and PD-OCG) and their theoretical regret bounds are presented. While the conventional D-FTGL (Wan et al., 2024) employs a standard gossip step, the proposed PD-FTGL effectively exploits the accelerated gossip step (Liu & Morse, 2011), which plays a crucial role in achieving a regret bound closer to the lower bound of D-OCO. Additionally, PD-OCG utilizes the CG method (Frank & Wolfe, 1956; Jaggi, 2013) to eliminate the implicit projection operation, making it a more practical algorithm while also successfully improving the regret bound. This paper makes a solid theoretical contribution. However, no experimental or empirical validation is provided, even in the Appendix.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews! \n\n---\nQ1: 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.\n\nA1: 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.\n\nSpecifically, 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$. \n\nWe 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$.\n\nFrom these results, we have the following main observations.\n\n1) 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.\n\n2) 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.\n\n3) 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.\n\n[1] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. In TIST, 2011.\n\n---\nQ2: … how about summarizing the results … in a table form?\n\nA2: Thanks for your helpful suggestion. In the revised version, we will summarize these theoretical results in a table form.", "claims_and_evidence": "The proposed algorithms (PD-FTGL and PD-OCG) have been theoretically analyzed in terms of regret bounds, and improvements over related works can be confirmed (Sec. 3.2). I believe the theoretical contributions are sufficient.\n\nOn the other hand, it is common to experimentally demonstrate how the regret bound improvements manifest empirically through benchmark tests using convex loss functions. However, no such empirical evidence is provided, even in the Appendix.", "methods_and_evaluation_criteria": "The proposed method is well-suited for DP-OCO, and the theoretical evaluation criteria (regret bound analysis) are appropriate. However, it is generally expected to experimentally demonstrate how the theoretical regret bound improvements manifest empirically through benchmark tests based on convex functions, but this was not included in the paper.", "theoretical_claims": "The regret bound of PD-FTGL in Algorithm 1 is presented in Theorem 3.6, with its proof provided in Section 4 and Appendices B, C, and D. I focused my review on verifying this, which appears to be correct.", "experimental_designs_or_analyses": "No experiments were conducted, including in the Appendix. I believe that demonstrating how the theoretical regret bound improvements manifest empirically through benchmark tests based on convex functions would have made the paper more compelling. This absence has been a factor in my relatively lower score.", "relation_to_broader_scientific_literature": "This study focuses on D-OCO, and a thorough review of related work has been conducted, including Appendix A. The paper further advances the SOTA method, D-FTGL [Wan et al., 2024], demonstrating improved results.", "essential_references_not_discussed": "The survey of prior works is highly comprehensive, and the comparison with them regarding regret bounds is sufficiently detailed.", "other_strengths_and_weaknesses": "Nothing in particular.", "other_comments_or_suggestions": "The order of the regret bounds appears frequently throughout the paper. To make the theoretical contributions clearer, how about summarizing the results, including those from related works, in a table form?", "questions_for_authors": "I have no further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper discusses the setting of DP decentralized online learning.
All reviewers agree that the result is new and improves over existing known guarantees.
Nevertheless, the reviewers are divided regarding the level of novelty in the paper.

After going over the author's rebuttal and correspondence with reviewers, I think that the authors successfully addressed primary points raised during the review process. I also believe that this paper presents results that are relevant to ICML community, and therefore recommend for (weak) acceptance.
Decision: Accept (poster)