Sketched Gaussian Mechanism for Private Federated Learning
Authors: Qiaobo Li
Zhijie Chen
Arindam Banerjee
Venue: NeurIPS 2025 spotlight ()
Keywords: Federated Learning
Differential Privacy
Sketching
Communication Efficiency
Adaptive Optimizer
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Communication cost and privacy are two major considerations in federated learning (FL). For communication cost, gradient compression by sketching the clients’ transmitted model updates is often used for reducing per‐round communication. For privacy, the Gaussian mechanism (GM), which consists of clipping updates and adding Gaussian noise, is commonly used to guarantee client‐level differential privacy. Existing literature on private FL analyzes privacy of sketching and GM in an isolated manner, illustrating that sketching provides privacy determined by the sketching dimension and that GM has to supply any additional desired privacy. 

In this paper, we introduce the Sketched Gaussian Mechanism (SGM), which directly combines sketching and the Gaussian mechanism for privacy. Using Rényi-DP tools, we present a joint analysis of SGM's overall privacy guarantee, which is significantly more flexible and sharper compared to isolated analysis of sketching and GM privacy. In particular, we prove that the privacy level of SGM for a fixed noise magnitude is proportional to $1/\sqrt{b}$, where $b$ is the sketching dimension, indicating that (for moderate $b$) SGM can provide much stronger privacy guarantees than the original GM under the same noise budget. We demonstrate the application of SGM to FL with either gradient descent or adaptive server optimizers, and establish theoretical results on optimization convergence, which exhibits only a logarithmic dependence on the number of parameters $d$. Experimental results confirm that at the same privacy level, SGM based FL is at least competitive with non‐sketching private FL variants and outperforms them in some settings. Moreover, using adaptive optimization at the server improves empirical performance while maintaining the privacy guarantees.

Sketched Gaussian Mechanism for Private Federated Learning
Qiaobo Li
Zhijie Chen
Siebel School of Computing and Data Science University of Illinois Urbana- Chaaaa-aa giaobol28illimg meresllinoi...... edu
Siebel School of Computing and Data Science University Illinois Urbana- Urbana-Champan Champaign lucmon@il linois..ed.
Arindam Banerjee
Siebel School Computing and Data Science University of Illinois Oabana-Champaige arindamb0illine .
Abstract
Communication cost and privacy are two major considerations in federated learning (FL). For communication cost, gradient compression by sketching the clients' transmitted model updates is often used for reducing per-round communication. For privacy, the Gaussian mechanism (GM), which consists of clipping updates and adding Gaussian noise, commonly used to guarantee client-level differential privacy. Existing literature private FL analyzes privacy of sketching and GM in an isolated manner, illustrating that sketching provides privacy determined by the sketching dimension and that GM has to supply any additional desired privacy.
In this paper. we introduce the Sketched Gaussian Mechanism (SGM), which directly combines sketching and the Gaussian mechanism for privacy. Using Rényi- DP tools, we present a joint analysis of SGM's s overall privacy guarantee, which is significantly more flexible and sharper compared to isolated analysis of sketching and GM privacy. In particular, we prove that the privacy level of SGM for fixed noise magnitude is proportional to 1/Vb, where is the sketching dimension, indi- cating that (for moderate b) SGM can provide much stronger privacy guarantees than the original GM under the same noise budget. We demonstrate the application of SGM to FL with either gradient descent adaptive server optimizers, and establish theoretical results on optimization convergence, which exhibits only a the number of parameters d. Experimental results
logarithmic dependence confirm that at the same privacy level. SGM based FL is at least competitive with non-sketching private FL variants and outperforms them in some settings. More- over, using adaptive optimization at the server improves empirical performance while maintaining the privacy guarantees.
Introduction
Federated learning (FL) 44 is a widely used machine learning framework where shared global model is trained under the coordination of central server using data distributed across various clients. In FL, each client carries out training steps on local data and sends only the model updates back to the server, which then refines the global model by suitably aggregating these local updates. Because the data remains on the clients, FL can offer enhanced privacy protection compared to traditional centralized learning. Nonetheless, FL faces two significant challenges: (1) it lacks rigorous privacy guarantee (e.g., differential privacy (DP) I7 and has been shown to be susceptible various
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

inference attacks, leading to local information leakage during training 449 50 75 83, 84]; and (2) it usually requires a high communication overhead due to the frequent communication between the server and the client [3 Many recent advances in FL. have been motivated by these two challenges.
Towards reducing communication costs, a key goal has been to reduce the communication cost per round by compressing local updates from clients to a lower dimension [30] 33), including sparsi- fication [40] 70 [1, quantization 4 41 (2), and sketching [59] 54 28 Among these approaches, sketching methods stand out for its simplicity, making it easier to integrate with existing FL methods. As an unbiased compressor, it does not require bias correction using error feedback mechanisms, unlike sparsification, which incurs additional memory costs [57] 60]. As linear operation, sketching ensures the geometric properties are approximately preserved after compression [ as opposed to quantization distorting the inner product structure, potentially slowing convergence 4
Towards preserving privacy, two DP definitions are commonly considered in FL algorithm design: sample-level privacy and client-level privacy, where client-level privacy is the stricter guarantee in the sense that ensures the output remains statistically indistinguishable when an entire client's dataset is altered, rather than merely hiding the inclusion or exclusion of individual data samples as sample-level privacy (А. Various FL algorithms [21 71
63 66 have focused on client-level privacy by adapting standard differential privacy techniques from centralized training (i.e., clipping
gradients and adding Gaussian noise to the clipped values [T 19 to the federated learning setting.
Though privacy and ceaammunicationffffiieen. have mostly been studied independently, there have been some efforts towards solving these two challenges together. D2P-FED(ZI] combines stochastic quantization and random rotation 44 techniques to lower communication costs, to the discrete Gaussian mechanism for privacy (9. along with secure aggregation 7 to mitigate noise magnitude. Alternatively, DPSFL [80] directly applies the standard Gaussian mechanism to the communication- efficient federated learning algorithm FetchSGD (54). However, these methods merely select individ- ual compression and privacy components and stitch them together, treating communicaiion-effccinnn and differential privacy as separate concerns rather than examining their intrinsic interplay.
B7 is one of the very few works to investigate the underlying relationship between differential privacy and communication efficiency in distributed learning. It demonstrates that the Count Sketch algorithm [10], despite being originally developed for communication efficiency, inherently satisfies form of differential privacy for distributed learning algorithms. However, their results have several major limitations. First, when the privacy level c provided by the Count Sketch mechanism falls short of the requirement, additional Laplacian characterization of the amount of noise required. Second, their theoretical guarantees require arguably impractical assumptions, including the input (client gradients) to follow a Gaussian distribution and the sketching dimension 6 S Vd where is the input (gradient) dimension, which contradicts typical empirical configurations in sketched distributed learning, where b is often a fixed fraction of d, e.g.. b d/ 100, to avoid derailing the optimization.
Gaussian noise must be injected, but there is no precise
In this paper, we introduce the Sketched Gaussian Mechanism (SGM), which combines an isometric Gaussian sketching transform [59] with the classical Gaussian mechanism. Leveraging tools from Rényi differential privacy (RDP) [46] with the subsampling, post-processing, and composition theorems of differential privacy 18] we derive tight upper bound on the overall privacy level
e of SGM. Concretely, with all other hyperparameters held fixed, e = 0 Thoz 9
). where b denotes
the sketch dimension and of the variance of the added Gaussian noise. Our new result for SGM establishes a clear dependence of c on both b and oz. Unlike prior work, our result imposes no restrictive upper limit on b, thereby covering practical regimes in which b is a fixed fraction of the ambient dimension d. More importantly. this bound implies that for suitably large b, SGM achieves strictly stronger privacy guarantees than the standard Gaussian mechanism, demonstrating that the sketching operation itself confers inherent privacy benefits.
We further integrate SGM into a federated learning (FL. framework, referred to as Fed-SGM, supporting flexible choices of server optimizers to match practical deployment needs. We prove that this Fed-SGM satisfies client-level privacy guarantees. Moreover, by fully leveraging the fast- decaying spectrum of the deep-learning loss Hessian [77 [2 76. which implies a small absolute intrinsic dimension (26). we establish rigorous optimization convergence bounds that scale only logarithmically in the ambient dimension d and linearly in this absolute intrinsic dimension, ensuring scalability to high- dimensional problems.
2

---

We empirically validate our approach on deep learning models for both vision and language bench- marks. Across these tasks, federated SGM requires strictly less Gaussian noises than the standard DD-FedAvg algorithm [8] to achieve the same privacy guarantee, and consistently delivers com- parable or even superior model aceuracy. Furthermore, when we replace vanilla gradient descent on the server with an adaptive optimizer, we observe additional accuracy gains, highlighting the practical benefit of incorporating adaptive optimization into our framework.
federated learning
The remainder of the paper organized as follows. Section provides the description of our SGM and establishes the privacy guarantee. Section introduues Fed-SGM, the application of SGM into federated learning setting, and establish optimization analysis of our framework. Section 4 we present experimental evaluations that assess performances of our Fed-SGM and compare them with existing approaches. Finally, Section [ concludes our contributions and highlight potential future directions. Due to space limit, we present our discussion on related works in Appendix A
2 Privacy Guarantee of SGM
In this section, we will introduce the Sketched Gaussian Mechanism (SGM), and provide the privacy guarantee with two different kinds of analysis.
Definition 2.1 (Sketched Gaussian Mechanism (SGM)). For any statistic ((D) Rd of the dataset D, the Sketched Gaussian Mechanism outputs (G R) = Ro + E, in which R E R is Gaussian sketching matrix with each entry sampled i.i.d. from (0, + and & E R follows the Gaussian distribution A (Z.
Algorithm/ Sketched Gaussian Mechanism
Hyperparameters: learning rate Te, noise scale gg. clipping threshold T, number of iterations T. Inputs:
Examples D = { }. loss function ((0) = _ - x(),
Initialize 6u randomly.
tor 0,..., T 1 do
Take mini-batch B, of m samples with sampling probability Computer gradient: For each i Br, (x;) < VL(O,, x.))
Clip the gradient: ğe (x;,) clip(g (x. min (ac
Apply SGM: For each i Bd, (x:) SG(G Et.)
Aggregate: 9: ΣiEB, (z,))
Update parameter: 0 OPT (Or, (e,5e, nc)
end for
Outputs: final model 0r
Algorithm| I outlines a standard application of SGM in training model with parameter 0 in a similar manner to the standard DP-SGD M. At each step of training, we compute the gradient for random subset of examples, apply clipping and SGM to each gradient, and update the parameter with the optimizer OPT using the aggregated gradient.
Denote (D) = EiEB, (e(x;) then (D) S me.. Notice that sketching with the random matrix R2 is linear operation, so we can rewrite the aggregated gradient Ôe as:
gt-
Σ (x()))
Σ
(a())(as); Er,)
Σ
(Rig((xs) + Er.))
M
m YEB.
m
iEB
SEB.
R
Σ (o( VEB.
+ Σ Ea,
1 Rrx(D)+ + Σ Ev,
(D() R,, E.)
where & EiEB, Ee, is a Gaussian vector with covariance matrix mozlk. Therefore, the aggregated gradient 9. is also an output of SGM based on the examples.
We study the privacy guarantec of Algorithm D subject to the rigorous privacy guarantees of Differen- tial Privacy (I7 whose formal definition is given below.
3

---

Definition 2.2. A randomized algorithm M is (c, diffffrrreyt private if for any pair of datasets D' differ in exactly one data point and for all event y the output range of M, we have
IP (M(D) E E & e (M(D') E v) +
where the probability is taken over the randomness of M.
2.1 Warm Up: Privacy Analysis by Moments Accountant
Compared to the standard Gaussian mechanism [8]. SGM incorporates an additional sketching operation. By the Johnson-Lindenstraus lemma [3]. sketching can be interpreted as a distance- preserving embedding that approximates the original high-dimensional update in lower-dimensional subspace, Under this viewpoint of sketching, we obtain the privacy guarantee for Algorithm by
an extension of the moments accountant analysis of Gaussian mechanism [T]. We state the main theorem below with the full proof in Appendix C.I
Theorem 2.1. There exists constants 0j and 02 so that given the sampling probability q = m and the number of steps T. for any 6p c1q²T, Algorithm 7 iis (Eps dyf-dfffrrett private for any 8p if we choose
VV
1
lo (2m)1/6p)) mI (2/()))))
vb
0g 2 C2
ncp
Remark 2.1. This privacy bound decreases monotonically in the sketching dimension b. However, since the dependence is of the form (1 + (1/VV)),, even for large b, the requisite Gaussian noise variance o² remains asymptotically at par with that of standard DP-SGD M. Here, the analysis attributes the entire privacy solely to the Gaussian mechanism, treating sketching purely as an approximation and omitting any potential privacy that the sketching step might confer.
2.2
Main Result: Privacy Analysis by Rényi Differential Privacy
To more precisely characterize the privacy guarantees of the Sketched Gaussian Mechanism and to investigate any privacy contributions imparted by the sketching step, we develop the following novel privacy guarantee of [lgorithm[]
Theorem 2.2. There exists constants and that given the sumpling probability q and the number of steps T. for any Cp S cagvTT, Algorithm 1 is (cp, 5pi-differeen private for any 8p > if we choose
og caqT² (oggg(2/T/8)))
(2)
Vbe,
Remark 2.2. In Theorem 2.2 for any fixed privacy target Ep. the required Gaussian noise variance of is monotonically decreasing function of the sketch dimension b, so sketching to moderately high dimensions provably reduces the marginal variance of the Gaussian mechanism. Moreover, compared to Theorem 2.1 one attains the same privacy guarantee with strictly less noise once the
sketch dimension satisfies 2 Ω
(nee (2g(2)7)
(1/88)
We refer readers to Appendix C.2 for detailed proof, and provide high-level sketch here. Our analysis leverages tools from the Rényi Differential Privacy (RDP) framework (46..
Definition 2.3 (Rényi divergence (53). For two probability distributions P and Q defined over R,
the Rényi divergence of order a > 1 is Da (PIIQ) & n-1 log Ex~q
(
P(z))
(((=)
From the definition of SGM, Sg(m: R., ~ N (o, (1.(111(0 [Iba(p)) + moo? T.). which can be used
to show the following result:
Lemma 2.1. The Rényi divergence between SG(16; Ri, Ex) for neighboring datasets D, D' is
bfa. ()
[na(D')) + mbo?
Da (B
|mx(D)11 mbb?
where (x) = log 1)-11 log -1-

---

In |nx( [n(( we define the ratio sensitivity
Since this divergence purely depends on the ratio of the statistic analogous to the classical sensitivity measure in the Gaussian mechanism [18] Definition 2.4 (Ratio Sensitivity), For any constant c 2 0, define the ratio sensitivity of f as
|0(D))) +
rsens, (0) sup D.D'
[[( c
where the supremum is over all neighboring datasets D, D' From the definition, direct analysis shows
2T
27²
S 1 S rsens, Vmba (1)) S 1+
(4)
b
rsens Vmbo, (7e)
bo
Since (at is monotonically decreasing for S 1 and increasing for 2 1, we can obtain the following bound on the Rényi divergence.
Lemma 2.2. For any neighboring datasets D, D',
27 bo?
2T do?
a²74 (a - 1)bog
Da (SG(m)(D); &.) (S(()(D))) R.) & max fa 1
Sa
We are now ready to analyze the privacy of SGM using Rényi Differential Privacy (RDP). Definition 2.5 ((a, e)-RDP [46]). A randomized mechanism f D + R is said to have e-Rényi differential privacy of order a, or (a, c)-RDP for short, if for any adjacent D, D' E DD it holds that Da (fD)) S c.
Recall that RDP can be transformed into the standard (e, 8)-P.
Lemma 2.3 (Relationship with (e, 6DDP 46 ). If is an (a, (a,e)-RDP mechanism, it also satisfies (c+ log 1/8 o-1 . :8)
- --ifferreniall privacy for any 8 <
Based on Lemma 2.2 and Lemma 2.3
immediately have the RDP and DP result for SGM.
Lemma 2.4. SGM on "f. (a:, (a-1)
RDP, therefore
2- log(1/6)
8)-DP.
(a-1)bo7
a-1
Optimizing over the Rényi order a (in Lemma 2.4 recovers the optimal (c, 5)DD guarantee for
SGM at each step for the entire dataset D. Subsequently, by invoking the subsampling lemma, the post-processing invariance, and the sequential composition theorem from [8] we can establish the complete privacy guarantee of Algorithm
Remark 2.3. Theorem 2.2 shows that, holding all other parameters fixed, the privacy level Ep is monotonically decreasing with the sketching dimension b. This can appear counterintuitive at first, so we outline the intuition. According to the previous calculation, SG(x(D); Re,&,) ~
N (o. (Ize + mo?) I.). As b grows, the signal term lIn(D)] vanishes and the noise term mo² dominates, making the output distribution increasingly independent D. Consequently. for any two neighboring datasets D and D', the distributions S9(+, Re, & and Sg(x R, &.) become increasingly similar, since both are essentially noise-driven. Lemma 2.2 formalizes this: for a fixed noise multiplier g//T, the RéRén divergence between these two distributions bounded by 2²,4 1)-1) so that larger b strictly decreases the divergence. Therefore, increasing b makes it harder to distinguish which dataset produces the sketch, which implies higher privacy level.
b
(a()) & where & N' (0, (ll) (D)))D) and ((x))))) are Gaussian distributions with the same variance og. but
Remark 2.4. For the original Gaussian mechanism, i.e., 9(>
different means "n (D) and (D') respectively. So their Rényi divergence is a² a²-²
(2))))() <
20
20 which is fixed for any dimensions. In contrast, for the SGM, Sg (T)( and Sg (Tx (D)) are
two Gaussians with the same mean of 0 but different variances [nx( + +mo and |
b + +
b
and their Rényi divergence is proportional to O(+) according to Lemma 2.2 This offers intuitive
justification for the additional 1 1/vb factor Theorem 2.2 privacy bound, as compared to the privacy guarantee of the standard Gaussian mechanism [1
D
5

---

Algorithm 2 Fed-SGM
Hyperparameters: server learning rate Tiglobal. local learning rate Mlocal noise scale dg. clipping threshold r, number rounds T.
Inputs: local datasets D. ((ri,er Vi,e) and loss function L.(0) 1 ne
E e(0, (Zi,er Vi,e))
for clients с [C].
Initialize 0n randomly.
for tort=0, -ort=0,.... ....., T T- do
Take subset C₁ of clients with sampling probability g =
On Client Nodes:
for c C, do
Assign local initialization: Octt,0 < Of
Local update:
for h: = 1,..., K do
0c,r, f Oc,t,R-1 - Mocal 9o,t,k end for
Compute update: Do,t + O2 O0.2.K
Clip the update: Ao,t = clip
Ani
Moccll
Apply SGM: Å.,t Mocal SG(
SG(A (D (xx); Ra, Zo.t)
Send Å. to the server
end for
On Server Node:
Aggregate: Å. = N ErEc, Åc,t
Broadcast Å, to the clients
On Client Nodes:
Update parameter: 0c+1 GLOBAL_OPT (cc, R, A. Nglobal
end for
Outputs: final model 0.
3 Application in FL: Fed-SGM
In this section, we introduce Fed-SGM, the application of the SGM within federated learning framework that simultaneously achieves communication efficiency and differential privacy guarantees. We then establish its client-level privacy bounds and derive optimization convergence results.
We consider federated learning setting with C' clients indexed by holds local dataset D. {<r,ee F2 of size ne and defines its empirical loss by (e
[C]. Each client
Ne E {0;; (Zi,es )t,e)). where 0 E Id the model parameter and the per-example loss. The goal Σe (O).
of the algorithm is to minimize the average empirical loss over clients, i.c.,(())
Algorithm formalizes the Fed-SGM algorithm. At each communication round, the server samples a subset of N clients uniformly random without replacement. Each selected client then:
1. Performs local stochastic gradient descent (SGD) on its local dataset to obtain an update Ac,
Clips A..t with respect the clipping threshold
Theal
Applies the SGM to the clipped update and transmits the resulting sketch to the server.
Upon receiving client sketches, the server computes their aggregate and broadcasts this aggregated sketch back to every client. Each client inverts the sketch to recover the aggregated update in the original ambient space, and then updates the global model parameters in a single step via the GLOBAL_OPT operator. In this paper, we study the case with gradient descent (GD) and AMSGrad as GLOBAL_OPT.
In the parameter-update step, we lift the aggregated sketch back to the ambient space using the transpose R.J rather than the equt-esuares estimator R/, i.e., the Moore-Penrose pseudo- inverse. This preference is motivated by the following points. First, since each entry of the sketching matrix R, bxd is drawn i.i.d. Gaussian with mean and variance 1 so E [R. R.] Ia-
Remark 3.1.
/ Therefore, for any vector g. E [R_ Rig] g, which shows that R, can recover in expectation,

---

implying R is a near-optimal desketching operator for our use. Second, computing R each round requires solving a least-squares system, typically via QR/SVD, with per-round cost on the order of O (1)d) plus the overhead of forming and inverting Gram matrix. In contrast, the transpose map R is single matrix-vectoo multiplication with cost Obbd), which is substantially cheaper.
3.1 Privacy Guarantee
As a direct application of Theorem 2.2 we can obtain the following client-level privacy guarantee of Algorithm 2
Theorem 3.1. There exists constants 03 and e4 so that given the sampling probability q = ~ and the number of commumication rounds T, for any Ep S e3gV'T, Algorithm 2 is (Cp. clieente-ll private for any 6, > if we choose
og caqr² (og'
(5)
Vhep
3.2 Convergence Analysis
In this section, we analyze the optimization performance of Fed-SGM as specified in Algorithm 2 Section 3.2.I our assumptions on the loss-gradient bounds and Hessian spectrum, and justifies their empirical validity via prior work. Section 3.2.2 then establishes convergence guarantees for Fed-SGM when employing AMSGrad as the GLOBAL OPT, with the corresponding gradient- descent analysis deferred to Appendix D
3.2.1 Assumptions
We begin by presenting a set of standard assumptions that are widely adopted in the literature on first-order stochastic methods.
Assumption 1 (Bounded Loss Gradients). There exists a constant G 0, such that for every A E IRP and c E [C], (0)ll)) G.
According the definition, VC(()= + Σ (O), so we can directly see that ||V G. Therefore, G is the upper bound for both the client and global gradient norms. We also assume the stochastic noise from mini-batches is uub-Gaussian, which widely adopted in first-order optimization [25 48).
Assumption 2
Noise). The stochastic noise [V (x) =o(x))l2 each client is T.--uu--Guussia random variable, i.e. (()VVL.())) ge(x)) l 2 a) 2exp( texp(-a²/e /oz), ) for all
a 2 O.
Besides, also assume special structure the Hessian eigenspectrum (A,, of the loss function f.
Assumption 3 (Bounded Loss Hessian Eigenvalues). For each E [C), the smoothness of the loss function L. i.e. the largest eigenvalue of the loss Hessian Hc,, is bounded by L.
This local smoothness assumption is commonly used in many federated learning analysis [55] 20) Due to a similar reason as Assumption [ this assumption also indicates the L-smoothness of the average loss function L.
Assumption 4 (Loss Hessian Eigenspetrum). Denote (2:) the eigenvectors of the Hessian matrix He of the average loss function L. Then we assume the absolute intrinsic dimension of H is bounded, i.e., max, X.
Einldd I.
EE
The absolute intrinsic dimension considered here, max, is close to the concept of intrinsic dimension proposed in (26), and the difference is that consider absolute values of eigenvalues. A growing amount of empirical research suggests that the absolute intrinsic dimension of the Hessian in deep learning be significantly smaller than the ambient dimension d. Studies by 22 38 42
indicate that the eigenspectrum undergoes a sharp decay in magnitude. Additionally, research by [56] 39] demonstrates that substantial portion of the eigenspectrum is concentrated near zero. Further investigations by 776 [2) reveal that the eigenvalues follow plwer-law distribution, suggesting that in such cases, the absolute intrinsic dimension remains much smaller order than d.
3.2.2 Optimization Analysis
In this section, we will demonstrate the optimization result Algorithm with AMSGrad as GLOBAL_OPT. We refer the reader to Appendix for more formal statement with the full analysis.
7

---

Theorem 3.1. [Informal version of Theorem E. Suppose {0:) is generated by Algorithm with AMSGrad as GLOBAL_OPP Denote L the minimum of the average empirical loss. Under Assumption 14
with learning rate yf "/ocaal we have that with prohability at least 1 - θ (6),
Σ VV [VL E EAMSGnd EAMSGra
EAMSGrad
in which E EAMSGra EC EAMSGrad and Eg AMMSGrad denote terms from sketching- based FedAvg algorithm. caused by clipping, and caused by Gaussian noises. Specifically, with TKGG min {T, KG,
FAAMSGra =0
(C(00)-2
+6
1
+0 (Mreaa K)+Ō
TK.G (<bTK)
+6
(Mmocal + 112) T +0
1
T/K
VNT)
K
1TK
(e+0 (++n0N)))))
G(KG-1 -
Ee
AMSGrrd
max
Ke
(Meeal + v1I) oy
EAASGrra
NK
Remark 3.2. Regarding the term E.MSGrad most of the optimization results for aketching-based algorithms are expectation results [59 54]. while ours is a high-probabilityy optimization bound for the sketching-based FedAvg algorithm. In addition, previous optimization results in expectation either have a linear dependence on the ambient dimension [59]. or get around the dependence by using Top-k components of the gradient vector with rely on heavy-hitter assumptions [54 [0) As contrast, our result EAASSirl only has logarithmic dimensional dependence from the need of high probability with additional mechanisms.
Remark 3.3. When there is no clipping activated, i.c., 2 KG, with learning rates Mocaa
O
VI VTK ) .7= O (VTIK) ). can get the term LAMSsrad at the order of Ô (Vz) When
clip with constant, i.e., T O1),, by setting Macal O (VNTR)
VTT the order of
E EAMSGad becomes Ô
VI
VNT
VTK
Remark 3.4. Regarding the term AMSSGrd caused by clipping. it is a reasonable term in the sense that it is monotonically decreasing with the clipping threshold r. In the extreme case, when clipped updates will become 0, so that there is no training, then EAMSGra v G2 is a natural bound of (I2 = |/ (l0)) with Assumption when 7 2 KG, there is no clipping activated + Σ |
all the
during training, which is aligned with the fact that EAMSGrdd max { 0, (
0.
Remark 3.5. Regarding the term F.g
F-MSGind caused by Gaussian noises, with the learning rates men-
tioned in Remark 3.3 AMSGrad Ô
VIo? Besides, E EMMSGrd does not have any dependence
g
NVTK
on either the ambient dimension d or the sketching dimension b.
Remark 3.6. From the proof in Appendix F
we can see that our analysis on AMSGrad can be generalized to any adaptive optimizers involved with first-order and second-order moments, including
Adam 32] Yogi 778). etc.
4
Experiments
We conduct empirical evaluations of Fed-SGM on neural network training for both vision and language benchmarks. Across various privacy budgets Ep. compare Fed-SGM using GD and Adam as the global optimizer against their unsketched counterparts--D-. -D--FedAgg [81] for the GD variant and a matched unsketched Adam implementation, and additionally benchmark against DiffSketch (37] The results are presented after a detailed description of the experimental setup.
Datasets and Network Structure. We adopt two different experiment settings including both vision and language tasks. For the vision task, We use the full EMNIST ByClass dataset, which comprises 814K training samples and 140K testing samples across 62 classes, representing the complete set of

---

60%
adam-4a5
adam-445
adam-no
20%
adam-nn
Diftkkethh
Diflsbetch
200
130
Communication Hound
Communication Hound
(a) Training Accuracy, Sp = 1.00
(b) Tost Accuracy, ep = 1.60
(c) Test accuracy across privacy levels
Figure 1: (a)(b) Comparison of Fed-SGM with ADAM, Fed-SGM with GD, DP-FedAvg and its Adam variant of ResNet101 trained on EMNIST with Ep 1.6. The X-axis is the number of communication rounds T. and the Y-axis is the train/test accuracy. (c) The trend of test accuracy over privacy levels. The X-axis is the Ep. and the Y-axis the test accuracy. In all three subfigures, 'sgd' and 'adam' denote the selection of GID and Adam as the global optimizers, respectively; '4e5' signifies a sketching dimension of 10', and 'no' indicates that no sketching applied.
90%
Accurayy
90%
80%
20%
246
spl-265
60%
592
50
150
50
150
Communication
Communication
(a) Training Accuracy, cp
(b) Accuracy, eu
accuracy across privacy
Figure (a)(b) Comparison of Fed-SGM with ADAM, Fed-SGM with GD, DP-FedAvg and its Adam variant of Bert finetuned SST-2 with Ep 1.44. The X-axis is the number of communication rounds T. and the Y-axis the train/test accuracy. (c) The trend of test accuracy over privacy levels. The X-axis is the Cp. and the Y-axis is the test accuracy. In all three subfigures, 'sgd' and 'adam' denote the selection of GD and Adam as the global optimizers, respectively; '2e5' signifies a sketching dimension of 2 x 10 and 'no' indicates that sketching is applied.
handwritten characters. We conduct experiments on ResNet101 74 with a total of 42M parameter. For the language task, we use the SST-2 dataset from the GLUE benchmark [69], which comprises 67349 training samples and 1821 1 test samples across two sentiment classes. We finetune BERT-Base model 14, comprising approximately 100M parameters.
Parameter Setting We deploy C = 625 clients in total, sampling N = 4 clients uniformly at random in each communication round. Each selected client executes K 18 local SGD updates on mini-batches of size 64, with gradient clipping threshold = 1. Sketching dimension and total rounds are chosen per task: for the vision task, we 6 10t (approximately 1% compression rate)
and run T = 500 communication rounds; for the language task, we use b = 2 10y (approximately 0.2% compression rate) and T 200 rounds.
Privacy Level and Noise calculation; For privacy, we fix the parameter 6 = 10-5 For both tasks, consider noise scales ag E {0.8, 1, 4) for the unsketched algorithms. By employing the Moments Accountant method [ 88. we compute the cumulative privacy loss and obtain ap- proximately {2.75, 1.60, 0.42, 0.18) for the vision task and (2.45, 1.44, 0.35, 0.12) for the language task, each corresponding to the respective noise scales. For Fed-SGM, at each privacy level, we compute the minimal noise scale 0g by calculating the RDP and minimizing over the Rényi order numerically [46]. This yields the noise levels approximately (0.0883, 0. 001013, 0.1588, 0.2265) for the vision task and (0.0948, 0.1071, 06644, 0.2580) for the language task. Across all considered privacy budgets in both learning tasks, Fed-SGM attains the same privacy guarantee with strictly lower Gaussian noise variance than the corresponding unsketched algorithm.

---

Experimental Results We report our experimental results in Figure I and Additional figures and ablation studies are presented in Appendix [F] For each task, Figures and 2a depict the training accuracy of the five algorithms at fixed privacy budget, whereas Figures 1b and 2b show the corresponding test accuracy. Additionally, Figures [c 2 trend of the test accuracies of these algorithms under various privacy levels, providing deeper insight into their performance across different privacy constraints. Based on these figures, the following observations can made:
Regardless of the choice of global optimizer, Fed-SGM consistently matches or surpasses its unsketched counterpart, confirming the effectiveness of sketching within a differentially private FL framework. Notably, when Adam is employed, Fed-SGM even outperforms the non-sketching baseline. This improvement arises because Fed-SGM always requires a strictly lower Gaussian noise variance than the unsketched mechanism to attain the same privacy level. The resulting reduction in the amount of injected noise may compensate for any performance degradation typically associated with sketching.
Irrespective of whether sketching is employed, the variant using Adam consistently outperforms the ones using gradient descent and the baseline DiffSketch. Notably, even the Adam variant with sketching surpasses the gradient descent variant without sketching, and this trend is maintained across different privacy levels. These results demonstrate the performance enhancement achieved by employing Adam.
Remark 4.1. For experiment results in Figure I and Figure we use an IID split of the train- ing dataset across all 625 clients. To assess robustness under heterogeneity. we rerun our image- classification experiments with a non-IID partition using a Dirichlet distribution with concentration parameter 0.05. Table T compares test accuracy for models with and without sketching, under both SGD and AMAGrad global optimizers. As expected, overall accuracy decreases under non-III) settings; however, AMSGrad variants still outperforms SGD) counterparts, and sketching methods remains competitive with and sometimes outperforms non-sketching ones.
Table 1: Test accuracy under IID vs. Non-IID data.
GD. Sketching GD, -oe-Skkt Adam, Sketching Adam, Mon-Sketching
IID
62.98%
63.34%
85.09%
78.60%
Non-III>
40.71%
42.31
52.55%
51.42%
Remark 4.2. We use Adam as a representative adaptive optimizer in our experiments. To assess sensitivity to the optimizer choice, we repeated the image-llassification experiments with AMSGrad under the same settings as Figure As shown Table 2 the results with AMSGrad are comparable to those with Adam.
Table 2: Adam vs. AMSGrad as the adaptive global optimizer.
Sketching
Non-Sketching
Adam
85.09%
78.60%
AMSGrad 85.04%
78. 10%
5 Conclusion
In conclusion, we introduced the Sketched Gaussian Mechanism (SGM), which combines an isomet- ric sketching transform with the classical Gaussian mechanism, and showed via Rényi differential privacy together with subsampling, post-processing and composition theorems that its privacy
loss satisfies 0
without imposing any restrictive upper bound on the sketching di-
Vbo
mension b, thereby demonstrating inherent privacy amplification from sketching. We then embed SGM into a federated learning framework (Fed- SGM) supporting arbitrary server optimizers and prove convergence guarantees that grow only logarithmically in the ambient dimension d and linearly in the empirically small absolute intrinsic Hessian dimension I. Empirical results on vision and language benchmarks confirm that Fed-SGM attains fixed privacy budget with strictly less noise than unsketched DP-FedAvg, consistently matches or exceeds model aceuracy, and benefits further from adaptive optimization. As direction for future work, note that our analysis is currently limited to isotropic Gaussian sketching matrices. therefore remains to establish whether comparable privacy and convergence guarantees hold for more general classes of sketching transforms.
10

---

Acknowledgmentt
The work supported by the National Science Foundation (NSF) through awards IIS 21-31335, OAC 21-30835, DBI 20-21898, as well as a C3.ai research award. Compute support for the work was provided by the National Center for Supercomputing Applications (NCSA) and the Illinois Campus Cluster Program (ICCP).
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Kook Jin Ahn, Sudipto Guha, and Andrew McGiregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACCTSSIC. symposium Principles of Database Systems, pages 5-14, 2012.
[3] Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. arXiv preprint ww..i::704..0555 70..000011 2017.
[4] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiiieenn sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
[5] Leighton Pate Barnes, Huseyin A Inan, Berivan Isik, and Ayfer Özgür. rtop-k: A statistical estimation approach to distributed sgd. IEEE Journal on Selected Areas in Information Theory, 1(3):897-901 2020.
[6] Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Guha Thakurta. Practical locally private heavy hitters. Advances in Neural Information Processing Systems, 30, 2017.
[7] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 175-1191, 2017.
[8] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su. Deep learning with gaussian differential privacy. Harvard data science review, 2020(23), 2020.
[9] Clément L Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differen- tial privacy. Advances in Neural Information Processing Systems,
2020.
[10] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002.
[11] Wei-Ning Chen, Christopher Choquette Choo, Peter Kairouz, and Ananda Theertha Suresh. The fundamental price of secure aggregation in differentially private federated learning. In International Conference on Machine Learning, pages 3056-3089. PMLR, 2022.
[12] Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithmss 55(1):58-75, 2005.
[13] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60-65, 2003.
[14] Jacob Devlin, Ming Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume (long and short papers), pages 4171-4186 2019.
[15] Edgar Dobriban and Sifan Liu. Asymptotics for sketching least squares regression. Advances in Neural Information Processing Systems, 32, 2019.

---

[16] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[17] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptogruphy: Third Theory of Cryplography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 365-284. Springer, 2006.
[18] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- lions and Trends@ in Theoretical Computer Science, 9(3-4):21 1-0077, 2014.
[19] Huang Fang, Xiaoyun Li, Chenglin Fan, and Ping Li. Improved convergence of differential private sgd with gradient clipping. In The Eleventh International Conference on Learning Representations, 2023.
[20] lyya Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves error feedback! Advances in Neural Information Processing Systems, 36, 2024.
[21] Robin Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv:1712.07557 2017.
[22] Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net opti- mization via hessian eigenvalue density. In International Conference on Machine Learning, pages 2232-2241. PMLR, 2019.
[23] Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. ACM SIGMOD Record, 30(2):58 66, 2001.
[24] Farzin Haddadpour, Belhal Karimi, Ping Li, and Xiaoyun Li. Fedsketch: Communication- efficient and private federated learning via sketching. arXiv preprint arXiv:2008.0499 2020.
[25] Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579-1613. PMLR, 2019.
[26] Isse CF Ipsen and Arvind K Saibaba. Stable rank and intrinsic dimension of real and complex matrices. arXiv preprint arXiv:2407.21594, 2024.
[27] Berivan Isik, Francesco Pase, Deniz Gunduz, Tsachy Weissman, and Michele Zorzi. Sparse ran- dom networks for communication-effiiine federated learning, arXiv preprint arXiv:2209.15328, 2022.
[28] Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Ion Stoica, Raman Arora, et al. Communication- efficient distributed sgd with sketching. Advances in Neural Information Processing Systems, 32, 2019.
[29] Jiawei Jiang, Fangcheng Fu, Tong Yang, and Bin Cui. Sketchml: Accelerating distributed machine learning with data sketches. In Proceedings of the 2018 International Conference Management of Data, pages 1269-1284, 2018.
[30] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and trends@ in machine learning, 14(1 12:1: 2200 2021.
[31] Daniel Kane and Jelani Nelson. Sparser johnson-linndenstraus transforms. Journal of the ACM (JACM), 61(1):1-23, 2014.
[32] Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint
1rXiv:1412.6980, 2014.
[33] Ang Li, Jingwei Sun, Binghui Wang, Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. fotteryfl: Personalized and communication-efficenn federated learning with lottery ticket hypothesis non-iid datasets. arXiv preprint arXiv:2008.033771 2020.
12

---

[34] Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen. Fedmask: Joint computa- tion and communication-effee
personalized federated learning via heterogeneous masking. In Proceedings of the 19th ACM Conference Embedded Networked Sensor Systems, pages 42-55, 2021.
[35] Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long. Eugene J Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. 11th USENIX Symposium on operating systems design and implementation (OSDI 14), pages 583 983-598,200 2014.
[36] Mu Li, David G Andersen, Alexander Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. Advances in Neural Information Processing Systems, 27, 2014.
[37] Tian Li, Zaoxing Liu, Vyas Sekar, and Virginia Smith. Privacy for free: Communication efficient learning with differential privacy using sketches. arXiv preprint 111.02191..00972. 2019.
[38] Xinyan Li, Qilong Gu, Yingxue Zhou, Tiancong Chen, and Arindam Banerjee. Hessian based analysis of sgd for deep nets: Dynamics and generalization. In Proceedings of the 2020 SIAM International Conference on Data Mining, pages 190-198. STAM, 2020.
[39] Zhenyu Liao and Michael W Mahoney. Hessian eigenspectra of more realistic nonlinear models. Advances in Neural Information Processing Systems, 34:20104 1111104-21111 17, 2021.
[40] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient com- pression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887 2017.
[41] Heting Liu, Fang He, and Guohong Cao. Communication-fffiiiee federated learning for heterogencous edge devices based on adaptive gradient quantization. In IEEE INFOCOM 2023-IEEE Conference on Computer Communications, pages 1-10. IEEE, 2023.
[42] Hong Liu, Zhiyuan Li, David Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. arXiv preprini arXiv:2305. 14342, 2023.
[43] Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv: 19Xv:0990..0983, 2019.
[44] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication--fficiee learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[45] Luca Melis, George Danezis, and Emiliano De Cristofaro. Efficient private statistics with succinct sketches. arXiv preprint arXiv: 00115500800111110 10, 2015.
[46] Ulya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEÉ, 2017.
[47] Amirkeivan Mohtashami, Martin Jaggi, and Sebastian Stich. Masked training of neural networks with partial gradients. In International Conference on Artificial Intelligence and Statistics, pages 5876-5890. PMLR, 2022.
[48] Wenlong Mou, Chris Junchi Li, Martin J Wainwright, Peter L Bartlett, and Michael I Jordan. On linear stochastic approximation: Fine-grained polyak-ruppert and non-asymptotic concentration. In Conference on learning theory, pages 2947-2997. PMLR, 2020.
[49] Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP), pages 239-753. IEEE, 2019.
[50] Anastasia Pustozerova and Rudolf Mayer. Information leaks in federated learning. In Pro- ceedings of the network and distributed system security symposium, volume 10, page 122, 2020.
13

---

[51] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
[52] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Redpaq: communication-efficennn federated learning method with periodic averaging and quantization. In International conference artificial intelligence and statistics, pages 2021- 1- 2031. PMLR, 2020.
[53] Alfréd Rényi On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume I: contributions to the theory of statistics, volume 4, pages 547-562. University of California Press, 1961.
[54] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication--ffiiieee federated learning with sketching. In International Conference on Machine Learning, pages 8253-8265. PMLR, 2020.
[55] Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. Fednl: Making newton-type methods applicable to federated learning, arXiv preprint arXiv:2106.02900 2021.
(56) Levent Sagun, Leon Bottou, and Yann LeCun. Figenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv: 16/ 1.07476, 2016.
[57] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Interspeech, volume 2014, pages 1058-1062. Singapore, 2014.
[58] Mayank Shrivastava, Berivan Isik, Qiaobo Li, Sanmi Koyejo, and Arindam Banerjee. Sketching for distributed deep learning: A sharper analysis. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[59] Zhao Song, Yitan Wang, Zheng Yu, and Lichen Zhang. Sketching for first order method: efficient algorithm for low-bandwidth channel and vulnerability. In International Conference on Machine Learning, pages 32365-32417. PMLR, 2023.
[60] Sebastian U Stich, Jean- Baptise Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in neural information processing systems, 31, 2018
[61] Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International conference on machine learning. pages
PMLR, 2017.
[62] Tijmen Tieleman and G Hinton. Divide the gradient by a running average of its recent magnitude. coursera: Neural networks for machine learning. Technical report, 2017.
[63] Aleksei Triasteyn and Boi Faltings. Federated learning with bayesian differential privacy. In 2019 IEEE International Conference on Big Data (Big Data), pages 2596-2596. IEEE, 2019.
[64] Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Practical sketching algo- rithms for low-rank matrix approximation. SIAM Journal on Matrix Analysis and Applications, 38(4):1454-1485, 2017.
[65] Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. A hybrid approach to sevacy-preserving federated learning. In Proceedings of the 12th ACM workshop on artificial intelligence and security, pages 2019.
[66] Stacey Truex, Ling Liu, Ka-Ho Chow. Mehmet Emre Gursoy, and Wenqi Wei. Ldp-fed: Federated learning with local differential privacy. In Proceedings of the third ACM international workshop on edge systems, analytics and networking, pages 61-66, 2020.
[67] Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben- Ben-Itzhak, and Michael Mitzenmacher. Drive: One- distributed mean estimation. Advances in Neural Information Processing Systems, 34:362-377, 2021.
14

---

[68] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019.
[69] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv: 07461, 2018.
[70] Hongyi Wang. Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-effcienn learning via atomic sparsification. Advances in neural information processing systems. 31, 2018.
[71] Lun Wang, Ruoxi Jia, and Dawn Song. D2p-fed: Differentially private federated learning with efficient communication. arXiv preprint arXiv:2006. / 33039, 2020.
[72] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on information forensics and security, 15:3454-3469, 2020.
[73] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang. Yiran Chen, and Hai Li. Terngra: Ternary gradients reduce communication in distributed deep learning. Advances in neural information processing systems, 30, 2017.
[74] Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pages 3-19. 2018.
[75] Chulin Xie, Keli Huang. Pin-Yu Yu Chen, and Bo Li. Dba: Distributed backdoor attacks against federated learning. In International conference learning representations, 2019.
[76] Zeke Xie, Qian- Yuan Tang, Yunfeng Cai, Mingming Sun, and Ping Li. On the power-law hessian spectrums in deep learning. arXiv preprint arXiv:2201. 13011, 2022.
[77] Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of the hessian. In 2020 IEEE international conference on big data (Big data), pages 581-590. IEEE, 2020.
[78] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in neural information processing systems, 31, 2018.
[79] Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 1212.5701, 2012.
[80] Meifan Zhang, Zhanhong Xie, and Lihua Yin. Private and communication--ffiiient federated learning based differentially private sketches. arXiv preprint arXiv:2410.057.31 2024.
[81] Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Under- standing clipping for federated learning: Convergence and client-level differential privacy. In International Conference on Machine Learning, ICML 2022, 2022.
[82] Yushun Zhang, Congliang Chen, Tian Ding, Ziniu Li, Ruoyu Sun, and Zhi-Quan Luo. Why transformers need adam: A hessian perspective. arXiv preprint arXiv:2402. 16788, 2024.
[83] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. idlg: Improved deep leakage from gradients. arXiv preprint wrXiv:2001.026// 2020.
[84] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019.
[85] Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, and Wei Li. Federated heavy hitters discovery with differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 3837-3847. PMLR, 2020.
15

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clearly state theoretical and experimental claims in our abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We mention the limitation of this research Section 5,
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

We provide proofs for all theoretical results in this paper in the appendix, and also supply proof sketches and the associated intuition in the main paper. Guidelines:
Justification:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We disclose all the information needed to reproduce the experimental results in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-souree dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results. 5. Open access to data and code
17

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide the link of the code in Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
onliiicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
gwwccs/gg//e//eeee 7 //nips.co hwwbliiccuudde//odeeuuiiiii.
ssinnPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We present the training and test details our experiments in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Although do not include error bars in the experiments, repeat each experiment five times and report the average results.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The compute resources of our experiments are provides in Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpps://euuipp..oo http:///wrrrpp..oooo/oo////aaaaa
Answer: [Yes]
Justification:
We fully comply with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our work establishes novel theoretical result on privacy in machine learning, thereby deepening the formal understanding of privacy guarantees within this domain.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
19

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We discuss the data and models used in experiments and cite all original papers in Section 4.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the link of the code in Appendix
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We do use LLM for the core method development of this research.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttt::://neuris... http://arrrir.cc/ooferrrere///// c for what should or should be described.
22

---

A Related Work
Communication-Elliicee Distributed Learning, The substantial cost of transmitting model updates between clients and the central server has driven recent efforts to enhance communication efficiency in both distributed and federated learning. One widely adopted method, FedAvg 44 reduces
communication frequency by allowing clients to conduct multiple local updates within each training round before syncing with the server. Another prevalent approach is compressing model updates before transmission, lowering the communication burden per round. These compression strategies
generally fall into five categories: sparsification 3 70 40], quantization [6]
73 low-rank
factorization [67 47 (8), sketching [54, 59 29), and sparse subnetwork training [2
33 34 While
some of these techniques, such as certain quantization methods [4], naturally maintain unbiasedness, many introduce bias and require additional mechanisms to mitigate it for improved convergence [40]
541. Another important characteristic is linearity, which guarantees that the geometric properties remain largely intact after compressing [13]. Among these techniques, sketching is particularly notable for its simplicity as a linear and unbiased transformation, allowing computations to be performed in the liwer-dimensional space before reconstruction via desketching.
Privacy in Federated Learning. Differential Privacy (DP) [17] is the commonly used rigorous privacy guarantees in machine learning. In centralized training, the standard approach for ensuring DP follows a simple procedure applying a clipping operation to the stochastic gradient, and introducing random Gaussian noise to the clipped gradient [1]. The clipping step plays crucial role in enforcing DP, as the required noise variance is directly influenced by the chosen clipping threshold. [18]. Privacy mechanisms involving clipping are also widely applied in federated learning scenarios, but various requirements and factors result in different clipping operations. For sample-level privacy, clipping and injecting noise to every local update is proposed [65] while causing noticeable decline in performance. For client-level privacy, local models are clipped before transmission and perturbed bounded parameters [72 66) Later the mechanism clip local updates instead was raised and turns out to have better numerical performance than model clipping (1 71
Sketching. For decades, sketching has served core tool across various applications, predating the rise of deep learning in the 2010s [2 23 31. It has been widely used in tasks such as low- rank approximation [64], graph sparsification 22) and least squares regression [15]. More recently, sketching has been increasingly employed in distributed and federated learning to compress model updates, thereby improving communication efficiency (29
28
54
59
24
58). Sketching-basee
frameworks have also been seamless integrated with secure aggregation and differential privacy mechanisms [I] 59 45 83 6). However, most of these approaches restrict their privacy analysis to the randomness injected after sketching and do not quantify any privacy amplification inherent to the sketching transformation itself. (37 is among the few investigate this intrinsic privacy contribution of sketching.
Adaptive Optimizers 32 introduced Adam, an optimizer that has demonstrated rapid convergence and robustness to hyper-parameter choices. Adagrad [16) and RMSprop (62] update parameters using the gradient directly rather than relying momentum. Additionally, Adadelta 79) modifies Adam's 's variance term to follow a non-decreasing update rule, and AdaBound [43] introduces both upper and lower bounds for this variance component. Most of these adaptive optimizers rely on first-order and second-ore -oddrr moment estimates, which is central to how these adaptive methods balance rapid progress during early training with more stable convergence later on [3]. [5T] introduces general federated optimization framework integrating adaptive server optimizers, demonstrating improved convergence rates and empirical performance in heterogeneous federated learning settings.
B Sketching Guarantee
We have the following lemma of sketching guarantee from (59 for Gaussian sketching matrix.
Lemma B.1 (Lemma D.24 from (59). Let R E bR denote random Gaussian matrix. Then for any fixed vector & Rdd and any fixed vector g E Rdd, the following property holds:
log 1.5 (d/5)
[(g R Rh) - (g (gTh)) h)) R~ll
Pr
19 |//l
s @
vb
23

---

C Privacy Analysis
In this section, we will provide the proof of Theorem 2.1 and Theorem 2.2 of Algorithm
the privacy guarantee
C.1 Proof of Theorem
Following the analysis of [. we provide a proof of Theorem 2.1 We restate the theorem first.
Theorem C.1. There exists constants 01 and 02 so that given the sampling probability m and the number of steps T, for any Ep < CTq Algorithm is (<p. 6p) d.f-diiffrentially private for any 6p > 0
if we choose
log (2mT/6p) /b
mT (2)()))))
0g 02
nep p
Proof. Since the process after getting Ht can be viewed as post-processing, and due to the post- processing property of differential privacy, we only need to explore the privacy guarantee till the aggregation step Algorithm[]
According to Lemma
B.1 for each & E [7), E Tex, we have that
[ 2 1 log (2mT/5p) P
[10o(x:)1
8p 2mT
vb
Therefore, with probability at least 1
8x 2,
for all E [T] and i E Li.
[1 S v1+ 1+ log!.
log" 1.5 (2mT/0g (5p)
[(r((;)) S TV 1+ log 1.5 (2mT)) /6p)
vb
vb
Denote & = (1(00 STVI l vt E [T] L.). then we have P (8) 2
1 T There are two difference cases:
Case I: When & happens, the function I mentioned in Lemma 3 in I is still bounded by a constant. Therefore, still follow the Moments Accountant (MA) method in Lemma 3, Theorem 1, and
Theorem 2 in to get that Algorithm is Ep.
6, -differentially private for any 6p > 0 if
2
log (2mT//6p) vb
m. log
Og
C3
Y1pp
Case 2: When & does not happen, we have (E")=
<
3z
Combining these two cases, so we can get that Algorithm is (Ep, -yf-diffrrentially private with
log' (2mT/55))
mTlog 2
vb
nep
Then finish the proof.
C.2 Proof of Theorem 2.2
We will establish our analysis in the framework of [46]. We will restate the concepts and proposition here.
Definition C.1 (Rényi divergence). For two probability distributions and Q defined over R, the Rényi divergence of order > 1 is
1 a
P
Da (PI(Q) A
log Exn
Q(x))

---

Definition C.2 ((a, RD-PDP) A randomized mechanism f D + R is said to have e-Rényi differential privacy of order a, or (a, c)-RDP for short, if for any adjacent D, D' D, it holds that
Da (J()))) Se.
Lemma C.2 (Lemma 2.1
Da (0G) = bfa ( |bx(D))) + mbr??
(v
Im((D)) mbo
where
x²a
fa(2) = log r +
log ax
2(a - 1)
+ 1
Proof. According the definition of SGM,
IT((Di11
S9(r N
0,
+mog
Ib
b
(D())(D'); Re: N (0,
[Tn(D2)1
mo
To
Denote
of =
(D)ll
mo? gz
o2 = 1re(D')1 b
+ mo²
We need compute the order-a Rényi divergence between p= =(O00 of Ib) and Q - According definition of multivariate Gaussian distribution, for x IR write density functions
||0|| 2
P(x) (2Ta7) 6/2 exp
2
||0|
Q(x) = (2mO²)- -b2 exp
20
Hence
Exna [( ((()) 07
P((x)
(((z))
Q(x)
Q(x)) dx
P(x)*Q(x)) 1(x))~"da -a
Rd
f (2moo2) - exp
|| )
(2TO²)
-
exp
(
||0||
1-a
dx
20
20
(2mO?) - 2 (2TO
JR
exp
|
α
2
+
o
a
dx
④ (2TO?)- (2TTO?)
a1-a30
π
1-a
cab -(1-a}b
1 -
01 02
+
07
02
(oo} +1 - a)
(1-a)b
02 0
where (1) uses the standard Gaussian integral fox e || (27/a)//2 for a >> 0. Therefore, following the definition of Rényi divergence in Definition C.I
[ ((x)) (1(z)
Da (PI[Q) a - log Q
25

---

- log (002 + (1 a) of)
2 00 )
log (oo) + (1 a) 01 a of (1 a) log
a
log (002 + (1 -1-01 a) o) log (a 1) log of - (a 1) log
a
1
log (02) log (1o3 + (1 a) a) ) + (log - log
2
02
0
b
log
+ 2 (a - 1)
log
ad + (1
73
02
log
+ 2 (a - 1)
log
a + 1 o1
Substituting of (Dx
+ mo g and o3
|m(0'>11 + mo into the above equation, we can
obtain that
Da (89 (7e(D); Re, &r) ||Sg (Ta(D'); E())
0, Im((D)12 mo² |
(0. (m)
-Da
N
mo 9
b
1 +
Ix((D")1 + mo? 8 h
1
(D)
+ma3
-log
log
[xx(D)I mo?
2 (a 1)
|
+ma?
+
|r +
Ihr(D')11 + mbo?
b
(m + m
=blog
log
\
Im((D)11 + mbb7
2(a (la-1) 1)
Inx(D) + màoo
1mx(D'>11 + mbo? (1
=bfa
Ihr(D)] + mbo?
with
1
x²
fa(x) log
log
2(a - 1)
ax +
Definition C.3 (Ratio Sensitivity). For any constant 2 0, define the ratio sensitivity of 0 as
10(D)) - c2 rsens, (0) sup D,
[D) + c2
where the supremum is over all neighboring datasets D, D'.
Now we prove the monotonicity of fa and the bound on rsens rsens.mba, (7)).
Lemma C.3 (Monotonicity of fa). For any (x, a) such that fo is well-defined, fa(x) is monotoni- cally decreasing with respect to æ for x S I and increasing for 1;
Proof. In fact,
2 f.(x)) = |log + 2(a 1) log a + 1 - ạ
26

---

1
x²2
= (logx)* +
log
2(a - 1]
ax2 +1
1
ax² +1
x²
2(a - 1)
x²2
o. + 1 - 1
1
ax² 2 + -
2r (ax² + 1 - a) 2xx x²
2(a 1)
x2
(axx2 + - a)
1
ax² +
2x Q)
2(a - 1)
x²
(ax² + 1 a) 2
1
x
(ax² + 11-ai
1
ax² + -
ax 1) +1)
x aar2 + 1 a a)
Therefore, fa 2 for x 2 1 and fa S 0 for x < 1.
Lemma C.4 (Bound on rsens /mbo 9 (1t)).
2T bo
Im((D')1 + mèo? g
inf D,D
rsens Vmbo, (71)
|rc(D)11 + mbbo
Ib((D'11 + mbo? Ine(D))1 mbo
+ 27
Sisens Vinbo, (7)) = sup D,D'
bo
g
Proof. According to Definition C.3
In((D')1 2 + mèo?
rsens /mba, (11) 2 1;
sup D.D
Ihr(D))1 + mào3
In((D))112 + mèo? Ihr(D))1 + mbo3
1
1
inf D,D' In addition.
5 1.
rsens Vmboo isens/mbo (7c)
sup
Im((D)) 2 + mbo
rsens Vmba, (7t) sup
[D)(D)] 2 mboo
D,D'
1+ |m((D)12 - (D')?
< sup D.D
(D) 2 + mbo?
1 (()x(D)) + (1x(( (D)) 11xx
sup D,D'
(D) mbbo
1 (L)( + 1| (D)) III [1Tx(DD - [I
sup D
[1rx (D) 2 + +mboz
(mr + mT)
272
mbo g
bo
27

---

and we can get the lower bound
In(er)11 + mbb3
1
2T
inf D.D
rsens Vimligg (1t)
Ihr(D)I1 + +mbo
bo 2
with similar calculation.
Now we can obtain the upper bound of Da (SG(n Re, R.) Lemma C.5 (Lemma 2.2). For any neighboring datasets D, D',
Da (S9(r)(D)): Re ((ll)(( Re, Ex)
27²
2r²
a²74
<b <bmax far
1+
bog fa (V
bo?
a 10bogg
Proof. According to Lemma
Da (SG()) Rr, (D) = bfa (1
|nx(D'))1 + mbbo? |bx(D))12 + mloo?
9
From Lemma C.4
we have
2r2
In((D)12 + mbb
1m((D)12 + mbo
|rx(D')) + mbo Int(D) mbo,
1+ 272
S inf
S sup D.D
bo?
D,D'
[n)(1 mbor?
Ihx(D)] + mbo
bo?
Based on the monotonicity of fa in Lemma C.3
DA (0) R.) = bfa ()
|nx((D))) + mbba? [D)( + mbbb
<b <bmax { Ja
la
(v1+
(1
2r²
.s (v
2T²
}
bir
bo?
In addition,
2r²
fa (11
2r 11
1
27
+
boy
log
1
+ (a 1) log
bor?
2
bo? g
a
1 +
2r2 boy
+ +1-a
2r
1
2T
+
be
log
1
log
2
bo?
2 (a - 1)
2 bey
1
27
1
1 27
2
log
+
1og
log
1+
2
bo?
(a
1)
bo?
g
27
20t2
a log 1
- log
+
2 (a 1)
boo
bag
1
27
2072
1
2or
a bo?
2 (a 1)
bag
2
bo?
7
(a - 1) bog
And similarly we can also get that So.
(v
2n (V1-
boy
<
2,4 Ta-100003
Therefore,
Da (. R,, Ex))
28

---

Zbmax fa (vi+
2T² bo
So (vi-
272 bog
7² (ax - 1) bog
Definition C.4 ((a, RD- 46 ). randomized mechanism f R said to have e-Rényi differential privacy of order a, or (a, c)-RDP for short, if for any adjacent D, D' E DD it holds that
Da (f()))l(()) <.
And RDP can be transformed into the standard (e, 6-DP)
Lemma C.6 (Relationship with (c, 6) 46 ) If is an (a, c)-RDP mechanism, it also satisfies e-1 -differential privacy for any 0 < 6 < 1.
(c+ log 1/8
So we immediately have the RDP and DP result of SGM from Lemma
C.5
and Lemma C.6
Lemma C.7. SGM on Y is (a: (a-1)b0g
a²+' )-RDP, therefore
a²
log(1/8) 8)-DP
1)bo a-1
Finally we can prove Theorem 2.2
Theorem C.8. There exists constants C3 and 64 that given the sampling probability and the number of steps T, for any S cag SagvT, Algorithm is (Ep, -iffferrrenti private for any 6p > if we choose
caqr² VT (Too(22/T/8p))
(6)
Vhep
Proof. According to Lemma 2.4
SG(n: Re; Ee) is
2²,4
+
log(1/5m)
60 6o) -DP. By taking the
(a
a-
borg log(1/60)
derivative, we can get the optimal choice a = + V
1
we can get that
7
a 2274
+ log (1/5u)
274
bog log(1/do)
1
(a - 1) bo
-
bod
74
r log(1 1/6))
bo (oR(1/50)
in the case when 2 co max
then
2 co. we have that
J log( 1//65)
o
274 bogd
bo log(1100g
S 2
1
bot log(1/5o)
bog log(1/66)
bo log(1/6o)
1 1 1
+
$1o0
71
bot
Co
74
co
(1 + vco + 1) 72 (21))2222/g// Vlog(1//0
7²
Voog(1/00
Vau
vboz
v vboz
7² Plog(1//m
get that M is (co, 5a)-DP with cg
Vhr3
Now list the subsampling and composition properties of (c, 8)-
Lemma C.9 Sub-sampling of (c, 8)-DP). If (c, DD,,) then M' M Sample,, obeys (c', (C'P with é' log(1 1 p(e" 1)) and 8' = p8, in which p is the sampling ratio.
Lemma C.10 (Strong composition of (c. 8)-DP). For all 5 2 0. the class of (c, diffferrentll private mechanisms satisfies (c', kō diffferrrtll privacy under k--fold adaptive composition for:
/2k log (1/8')e + ke -11
72 /'v/log1/bb)) Since 6o = ci
so according to Lemma C.9 M o Sample,, satisfies (EI, (ôo) -DD Veg"
vooz
with
p7 Alglloo//// (1/6)
e1 = log (1 p - 1)) < C2peo ci 0102
/boz
29

---

According to Lemma C.10 we can see that T-fold composition of M Sample, m satisfies (e DDP with
22 v 27 (olg0(1/8)) + Tei
$ v (1/log(1/8))) + c3
pr² Vlog(1/80)
pr² (ooloo(1//0)
v 2T log(1/8)) 0102 vbog
+ cgT
c122
vbog
0022 27 log(1 /8) log 01601/6)pp7
T log(1/60)
+ &G3303
Vboz
bog
C102PV 27' log(1/0")
c/p2csp2T
Vco
C0
By setting 62 = and choosing 6p
8
8' = 2
TpT
C'VTpr² log (2pT/8)
bb
then we can obtain (c, DD.P
30

---

D Optimization Analysis with GD as GLOBAL_OPT
First write down Algorithm 3 which will be called as GLOBAL_OPT each round to do one-step
GD update of the global parameter 0z-1 with desketched aggregated updates desk (Âr-1).
Algorithm 3 GLOBAL_OPP (GD)
model 0;-1, desketched update desk (3.
Inputs:
Output: model Br-
One-step GD: 0r - 0 - Nglobal deskí Á1-1).
Then will introduce the optimization result of Algorithm 2 with Algorithm 3 We follow similar analysis to (59), but we exploit the second order structure of the deep learning losses, which helps avoid picking up dimension dependence due the sketching operation. We will state the formal result.
Theorem D.I. Suppose (0,)²-n is generated by Algorithm 2 with Algorithm GLOBAL_ OPT.
Denote L the minimum of the average empirical loss. Under Assumption with learning rate
Tocal have that with probability at least 106,
C(00) C 22og(2T/0)C² LKG nKT
2GG 12Glog(2T/8),
VC(00)1
T
VNT
VNTK ( (NTd/6)GTKC
2
+ max (0, G(KG-
(2T/62)))
K
VITK
T/K
2n log 2
(2T/5) og
2
II
(2dT//)
NK
NK
which
log 1.5 (NTd/10)
01 1+
-KKG min (T, KG)
Vb
Remark D.1. To analyze the bound in terms of T, we consider all other parameters as fixed and distinguish between two principal regimes:
When KG: In this regime, clipping may be activated, and
upper bound
on the norm of each clipped update Aet according to our algorithm. The total bound in this
case is given by ((%))-e" ( mbeLKGG + V2G (og + max {0, G(KG-r)
nKT
VNT
VNTK
v2 (VTd)(VV (2T/88/)
WTK + 2n (2T 2
log" We can observe NK
VDTK that (NTU//GT + 210 in the optimization bound of the sketching-based algorithm is V6TK
NK
K
monotonically increasing in т, while max (0. G(KG-T) caused by clipping is monotonically
decreasing in r. This trf highlights the need for careful choice of overly aggressive clipping introduces clipping bias, while too loose threshold amplifies optimization error of sketching algorithms.
2. When 5 2 KG: In this regime, the clipping operation becomes inactive under our algorithm, all updates fall within the clipping threshold KG effectively bounds the norm of each update Aet, and the clipping no longer influences the computation. The total bound becomes ((8,)-6 (2 VNT
RKT
LKG
VZG (8T
(NT4/8)0" (2T/6i0" K
2n (2T/000))
JNTK
VOT
NK
LLK log Consequently, the entire bound becomes independent of and NK remains constant as increases further.
Proof. According the algorithm, we can write the update in the sync step as:
0c41 - 0, =-lglobal desk (B,)
31

---

Iglobal desk
Σ
Do.e
N
DEC,
)) + bectt)
-gllabal desk
Moccl
sk
clip
N
Mocaa
CECt
Σ Ic,e,k: 7) 1) + Zoit
=n
Re
clip
iEC.
Σ R R,clip OEC. which 1) = Toocaal By Taylor expansion, we have
1
Jc,tkki
2 Σ
R2 Ze,
N
N
CEC,
[(0++1) = [(0.) VL(,)) (0t+1 0,) (0++1 - B,) (c,,(0c+1 B+)
By taking summation from to T - 1, we can get that
T
1
[((r) L(0n) Σ
- -((0++))(((0)) = VL((O)) - 0,) + E
E(0 (0--1 0o) - Hc,100+11 - 0z)
t=1
t=1
Ti
T2
D.1 Bounding Ti
For each term in Ti, we have
v VL(.)) ((1+1 -e)
VC(.))
" Σ
R R.cli
Σ Ic.t,kes
1
Σ
Riy Zeet
N
eEC.
oEC,
VL(O.)
Σ
R2 R,clip
Σ Nestoke
VC(O.)
RT Ze,z
N
N
cEC,
cEC.
By taking summation from 1, we can get that
T
T
K
T
VL(()) - 0,) = -
VC(0.) Σ
R.
R.clip
Σ
T
1
VL(6,)
Σ
RT Ze,t
N
N
oEC.
km
eEC,
$1
82
(8)
D.1.1 Bounding Si
For each term in Si, we have that
VL(0))
ΣR,
R.
Riclip
Σ kc
N
ocC,
b=1
C
1 C
KK
VCO.).
(..
+K VC(O.),
Σ (..(O.)
Σ
vc.(0.)
C
N
C
1=1
CEC,
c=1
(((.))
Σ
(V.o
VCo(0.)) )+ + VL(O.),
1
Σ
(go VC.
N
N
(EC
GEC
VC(O),
clip
Σ (c..
Σ
Ie,t,k
N
oEC.
k=
k=1
32

---

K
K
))
VC(O,),
Σ
R2 Reclip
Σ J0 v
clip
Σ
7
CEC,
By taking summation from 0 to T - 1, we can get that
VL(())
T
Σ OEC₁
R.clip
Σ
9c.t,k:
N
1=1
C
c
VL(O,),
(..(
+K Σ
VL(O.),
Σ
vLo(0.) - -
(0)
N
c=1
CEC,
c=1
1/2
1
1
VC(O.)) N
V - VCCo(0))
+
VL(O.),
(0,t (Lo(Oc.k.k))
N
DEC,
OEC,
Y3
K Σ BettdeT)
K Je,t.k
VL(I)); 1
Σ oEC,
clip
N
A=1
Y/s
K Σ
K Σ k=1
VL(O.); N
Σ
R2 R.clip
-clip
7
(9)
oEC,
k=1
Ya
D.1.1.1 Bounding Yi
According to the definition,
1 Σ (..(
VL(0,),
-1V22(0))1
c=1
T = t=1
1 VL(0,), 1 T Vc.(0))
(10)
D.1.1.2 Bounding Y2
We first bound each term with a fixed E [T] Y2. According to the assumption, each C, is uniformly randomly selected from [C], so by Hoeffding's 's inequality, we have
(K VC(O),, N
1 C Σ SEEV.O VC..0.)) 2a
Σ v.)(O.)
CEC.
2Na²
(- 2-
Naa 2G4
<2cxp
= cexpp
(2GP)2
2 log (2T
By selecting a
we have that with probability at least
VN
T
K
C vV.100)) < /2log(2T/8)C)
VC(())
1
Σ
VL.
N
VN
REC.
c=
Then denote Z, = (C(+)), 1/2 Exec, VL.(O,) 2 -C VL.((..)). we can see that Z, is martingale with respect to the selection each round, and from the above analysis, have that
33

---

with probability at least - 8. for all E [T],
7 Z = VC(O), 1 N E (f))
1 C
_ vL.(01)) )
2og (2T (2Tog(2T/8)C /8
C
OEC,
c=1
Then by Azuma's inequality, we have
a
(-
N log
P PZ S -a) 1 exp
exp
2.T. T.
VN
2vT /6)
By selecting a
we can get that with probability least 25,
VN
T
c
2vTlog(2T/8)C
7--1= = VL(I.)
Σ
(O.
C
Σ VC.((1))
2
(11)
N
VN
[=1
eEC₁
D.1.1.3 Bounding Y3
For each term, we have
K
VL(()),
1
ΣV -Ca(0.t))- (..
N
OEC, #=1
K
VC(,)), fe (D0. -0))
OEC, k=1
Mocal
VL((,), Arott Σ Joan
N
CEC, k=1
K
Mocal
VL(00))l T.
l1 12
N
OEC, oEC, k=1
K
Mocal
N G2 GL.L)
N
Nocal LK222
2
SO
T
VL(0.);
1
Σ - vCC((.))
K
2
nocal TLK2G
(12)
N
2
CEC,
k=1
D.1.1.4 Bounding Y
We first bound each term with fixed / E [T) in Y4.
(ge,t,k v.clloax)) /
VC Σ
OEC, k=
VL(())) 119c,.. (cceac))
N
dEC, k=1
G Σ
Σ
I1ge,t.k - (Lo(0...)
k=1
34

---

According to the assumption, the stochastic noise llge,c, VLe(Oe..k))ll) is o, Cug-uub-Gaussann Gaussian random variable, so by Hoeffding's inequality,
a²
IP
119 VCo(Oca))l22 2 < 2xp
NKo?
LEC,
By selecting v NK log((7 (T)os have that with probability at least
7.
Mart V.o S v NK 1og(21/0)os
CEC, k=1
SO
K
VC(0.):
(g (.CoO
N
CEC,
k=1
K
19 V.o
CEC k=1
GV K (1T
VNK logKog(271)) (2T
VN
Then denote W - (VC(O)) # Eeec, Σk= (go,'' V.. (0..r we can see that W; martingale with respect to the stochastic noise, and from the above analysis, we have that with probability at least - 5, for all E [T],
W. W.-i = VCOO)
1 N
K
(ge - VLo(Ontth)) )
G K log(2T/6)oo
VNV
nEC,
k=1
Then by Azuma's inequality, we have
a
2 2TG log /
P(TT-1S-00 S exp
2
exp
G (ooloo//7/5
T.
VN
By selecting a
Gv2TK log(2T /8)0,,
we can get that with probability at least 25,
VN
W7-1= Σ VC(O.))
(ga,e, (.oc(()))))) )
GV2TK 1og(2T/86o
(13)
N
VN
CEC, k=1
D.1.1.5 Bounding Yo
For each term, for r S KG, we have
VL(O))
Σ
clip
Hest,k
gest,k
N
CEC.
k=1
K
K
|
1
|VL(0))12
Σ
clip
Σ
Iest.ki T
go,t.k
N
OEC,
A=1
1=1
2 G(KG-r)
for 2 KG, we have
K
VC(0.), N
Σ
clip
Σ go.t.ki7
Σ
9o,t,
SEC,
35

---

50
VL(0)):
1
Σ
clip Σ
se.t,k
Σ gc,t,k )) max {0, G(KG-
nEC,
By taking summation from 0 to T
1, we can get that
K
K Σ gc.tk
2 max (0,TG(KG - -T)} (14) )) )
VC(O)),
Σ
clip
Σ
N
oEC,
1=1
k=1
D.1.1.6 Bounding Yo
We first bound each term with fixed E [T] in Yo. According to Lemma B.1 probability least 1 $.
we have that with
K
K Σ
[(())) N
R. R,elip
Σ
gost,ks
- clip
GEC,
1=1
A=
log LG (NTd/6)
VL((6))l2
clip Σ Ic,e,bes
Vb
nEC+
log 1.5 (NTd/ō)GTK.
vb
with TK, min (r, KG).
Then denote
K Σ
K Morrt gorr Re
U-= Σ VL(1+)) r'=0
Σ
clipp
yo
clip
Σ
N
CEC,,
see that U, is martingale with respect to the sketching matrices, and from the above analysis, we have that with probability at least 8, for all E [T].
U0g - U--1 | VC())) N
K Σ 9o..R. - clip
K
))}
log' 1.5 (NTd/6))TKe)
Σ cEC,
R. R.clip
Σ
ge...ke
vb
1=1
Then by Azuma's inequality, have
a²
baz
P PUT--15 1--55-a) a) S exp
log (NT vb
2
= exp
(-
2T 2og log 3 GNT
2.
log (N
By selecting a
we can get that with probability at least 28,
vb
K
Σ Set.ke 1)
K
log /NT/////2TGG
WT-1 Σ
VL(O),, N
Σ OEC.
R R.clip
Σ
Je,e,kr T - clip
vb
(15)
Substituting
10
13 14
15 into
we have that with probability at least 1 - 68,
T
VC()))
Σ REc,
R2 Raclip
Σ Ic.t.k. T
C
C Σ (L.
VC())),
(.)
+K
VL(0.), N
Σ vL.(l))
c=1
LEC.
c=1
Y2
36

---

1
I
1
K
VC(0.):
v Lo(Oc.e -Lol0ca))-VCoo( VL.(0.))
+
VL(0.),
90,1
VLo
N
CEC,
CEC
Yg
VC((,))
1
clip Σ Ieatdss5 Σ Jott,k
N
SEC,
K
1 N
VL(());
Σ
R2 R.clip
Σ BeckkiT
clip
Σ Sc,t,ks 7
(16)
OEC,
k=1
k=1
Ya
T
2K / (2T /
Mucal TLK
GV2TK 12T /8)o,
2K
VN
2
VN
max (0, TGKTGG log (NTd/8)
(17)
vb
D.1.2 Bounding S2
We first bound each term with fixed E [T] in S2. Noticing that & Exec, Bed ~ N (0. (+1) and
Rs V ((0)) is
1l2161ll2 sub-Gaussian random vector, according to Bernstein inequality, vb
P ( R
1 C...)
a
Σ Ze,t
2 < 22exp
min
N
b
do
IV 1V1011
cEC
VN
vb
Na²
aveN VL((0))l2
= 2 exp
-min
[V
? Tg
so taking Pnl(V[((,)]] (og(22/))
we have that with probability at least 1 5
VN
L.V)) R
1
Σ
0g [Q),)l) (og(27(8) 0g Goggo0()
N
VN
VN
DEC₁
Then denote =f= (L,V)(()))) Enec, Ze, we can see that X, is a martingale with respect to the Gaussian noise, and from the above analysis, have that with probability least 1 - 6, for all f E (T).
| R.V.
Σ Bost / OEC.
o GoGGog((21))
X X
N
VN
Then by Azuma's inequality, we have
Na²
P P -a) < exp
exp
(g,Glog(2Ty8)
2 log 2 (21/8)
T.T.
V/
By selecting
get that with probability at least 1 - 28,
V/V
log² (2T/8)
XT-1= Σ
R.V((O))))
Σ
Ze,t
(18)
VN
37

---

Substituting
17 and 18 into 8
we have that with probability at least - 86,
T
V Vl())) (0++1 - 0s)
VL((.)) Σ
R
Rellip
Σ ge
VL(O.)
Σ
R2 Zeat
N
eEC,
k=1
OEC,
< - nk VC(00112 2n log 2T/0)G²
MocaaTLK GGV2TK log (2T /
VN
2
+ 1f max (O.TG(KG- - +}} n log
(NTd/O)/2TTTH
(2T
vb
VN
VC(00)1 2n VT (2T
GGVTK log /8)0
5 5-nk rk
VN
2
VN
+ 1) max (0,TG(KG- -) 1g (NTd/5)22TGR.c + +log2 (DTT(2T/))2
Tr"Tloo' (2T/8)o3
vb
(19)
D.2 Bounding T2
We first bound each term T2 with a fixed E [T].
d
-.)) (6,,(6 - 0e) = -Talball ddesk (āt))
Σ
Amaiy i==
(desk (ši)
12
(desk (3.)
Iigobal
4/s
(20)
1=1
For each i E [cd]. we have
(desk((.)) 0/
= (/desk(3.),,))
Sest wi) )
R
N
eEC,
sk (clip
clip Ae.
))
Mocal
Zc
2/
Mocal
rEC,
K
Mecal
Σ
RTJ R,clip Σ
Mocal
Σ R2 Rects
gost,k 7
N
N
LEC.
leE.
(21)
For the first term, according to Lemma B.I
with probability at least
dr
Σ IEC.
R Raclip
Σ
T
2/4
-=1
log 1.5 ((NTP/88)
K Σ
||ui112 Σ
clip
vb
CEC-
k=1
log 1.5 (NTd2/8)
NTK.G
(22)
vb
38

---

For the second term, ( Deec, R₁ Zc,t = (Ress, N Ecec, Zor))
Noticing that
o N Exce, eet ~ N (o, N 11 and Rev is to -sub-Gaussian random vector, so according Bern- stein inequality,
Na² aveN
Retli
Σ Zest CEC,
2
S 2exp
-emin
= 2 2exp
-emin
N
Oa VON
o 0g
so taking
My log (247/6)
we have that with probability at least 1 -
6
VN
d7
) 0g log(2dT/6)
R
(23)
N
VN
cEC
Substituting 22 and
23 into 21
we have that with probability least 1
24
(()sk(()))
T
Mocal
R Reclip
Σ 9o.kkiT ). ..0
Nloca
Σ
Rs Zo,ts 24
21
N
N
ccC,
ICE
log!.6 (NTdd/8)
log"
TK.G + Mocal log (2dT/6)
nocal
1
vb
VN
which implies that
(deekk(ā.)
1 log 1.5 (NTTP15)
Moocll y log (ogT////)
2
<
Mocal
TKG +
Vb
VN
log 1.5 (NTPP/0)
2
M loog lo (2dT/8)
2mhcaal
1
Vb
TKKG
+
N
(24)
Substituting 24 into 20 we have that with probability at least
26
7
(0.+1 - 0,) (0.11 0₂) Nigiobal
Σ X
(desk (3.) Di
21 (1+ log" log1.5 1.5 (NTd&18)
2
2n o2 g
log (2dT
S nglobal
KK.G +
2
vb
N
(1+ log 1. (NTTa 10)
2n 2 I log (2dI/8)
2n)²
Vb
IL
K.G
+
N
By taking summation from 0 to T 1, we have that with probability at least 25,
log ANT.s(NNd)))))
(NTTP/0) ) ILTTk 2n 2 I log log (2dT/8)
(0.t1 - -T) (c. 0,) < 2n² [+
Vb
(25)
Substituting 19 and 25 into 7
we have that with probability at least - 106,
T
T
[((T) -(())) VC(0.) (0 0:) + Σ
2 (0++1- - -a) f.c,(0041111 00)
t=1
1=1
2nK log//
Mocaal TLK2G²
GGV2TKlog log /8)0.
K
VC(00)1 1=1
VN
2
VN
+ mmxax (0,T((GG-)) + n loo
(NTd/8)) 2TGT
+ 2
vb
vb
2n ("TToo'"(TT())) 2)
log (NT&/16)
2n o (2dT
+ 27²
1+
ILT
vb
N
39

---

Since
(())) [(OT) S C(00) L
we can get that with probability at least 106,
-(00)-E2
2 (
log
VC
T
nKT
VNT
2
VNTK
+ max 0, G(KG T)
V2 (NTdf6)GTKK) +
log 12T/(2/)))
K
VUTK
nTK
2n log 2 (2T/0)09
2ma
2n log" 2 (2dT/6)
NK
K
NK
in which
log 1.5 (NTd//)
01 1+
TK,G min KG),
Vb
then we finish the proof.
40

---

E Optimization Analysis with AMSGrad as GLOBAL_OPT
Similar Appendix[] D we will state Algorithm which will be used as GLOBAL_ to do one-step
adaptive update of 0 with desk (1--)).
Algorithm 4 GLOBAL_OPT (AMSGrad)
Inputs: model -,- desketched update desk (8:-1). Output: model 8r-
Update first moment estimate: my -11m--1 + (1 - (1) desk( (
Update second moment estimate: 6, = -200-1111
32) (dskk( (1))))
Update maximum of past second moment estimates: 82 max (Ut: Uz-
Update parameters: 0: 0 Nglobal
mh--1
Nglobal V m4-1
you I+e
Then we demonstrate the optimization result of Algorithm 2 with Algorithm which is the formal version of Theorem
Theorem E.1. Suppose {0e] is generated by Algorithm with Algorithm as GLOBAL_OPP Denote L the minimum of the average empirical loss. Under Assumption with learning rate
7 = Ogiobal Docal: we have that with probability at least 196,
T
V C(())11
T 1=1
02
(C(Ou) L*)
20 log log(2T/6)G2
Oooa PoggGlo((2T00))
nKT
VNTc
2e
VNTKe
+ max {
G2G - T)
V2az log (NTd/O)GTK.G
+ a 31)1I-IIV- 32GT (2g(2((/0)
KE
VoTKc
Ke 31)
Mocal + 2.1)vI-- G (ogd (2dI/0) 02 log 2 (2T/5)C2
2naz log (2T
NKe (1)
TKe
NK.
2nafaz (1 (2,)) (1++1) 31)ILTKKG
21a02(1 + 23 233) + 31 31)0 (2dT1/))))
Ke2(1-B1
NK - B1)²
in which
01 = 1+ log (NTd)/8) /8) = Macal (1+ log 1.5 (NTT/18)
TK.G Blocal log (2dT
+
vb
Vb
with TR.G = min (T, KG).
Remark E.1. To analyze the bound in terms of r, we consider all other parameters as fixed and distinguish between two principal regimes:
When S KG: In this regime, clipping may be activated, and 7 acts as an upper bound on the norm of each clipped update de, according to our algorithm. The total bound in this case is given
02 (((())))-)) + nKT
20z 1og(2T/6) + LKG
VZog (2)(27/6)) + max (o. VNTKc
GgG(KG-r)
by
+
VNTc
2c
Ke
y 2zg lug (NTT/8)GT
(24 (2g(2
(126)(1+2))/111-p))) log (2dT /
VbTKe
Ke(1-81)
NK<-11-8,
log (2T/8)G
2n0a (2T))))))
2no2(1+28.((++))) log
(2/7)/)) (28T/8)
NKc
(
NK 3,
VZou (NT4//)))
+ 1hurofaa(+48))1112 (2g(2)7/8)
We
can
observe that
Vo
k<((1-A))
2no (1228) in the optimization bound of the sketching- algorithm is (e-(1-
monotonically increasing in T, while max (0, dcGIKG-1) caused by clipping monotonically decreasing in т. This tra highlights the need for careful choice of as overly aggressive
Ke
41

---

clipping introduces clipping bias, while too loose a threshold amplifies optimization error of sketching algorithms.
2. When т 2 KG: In this regime, the clipping operation becomes inactive under our algo- rithm, as all updates fall within the clipping threshold KG effectively bounds the norm of each update Ae., and the clipping no longer influences the computation. The total bound be-
comes a=(C(8))-27
log(2T/6)G² BooaggKK
V2agG 1og(2T/6)o,
Vlaa log' (NTd/8GG VbTe
RRT
VNTe
2x
VNTK: 1
Mesal 7oa M (oR(247/6)
(2
Clo (K-(1191)
logglo"(a (247/8)
(2T/
+
e (1-
Kl'Ke
21a0 log (27 + (1000
21po2(1 (1-2(11)8)) (1 +1))))))))) Ing (247/6) Consequently,
+
NKe
<11--1)²
N NK-(I-81)
the entire bound becomes independent of 7 and remains constant as T mcreases further.
Proof. Let
B1
31
= 02 +
(0,
02-1)
0.
O2-1
1 31
1 31
1
31
and set 0-1 Oo that 700
0.. Then, the update 7/8 can be expressed
B1
71+1 7/2 = 1 - 31
(0++1 8τ)
(0: - -0-11)
- 1-31 31
1
Nglabal V
1/2 m4 +
1- 31 nekohal Vi-1 1/2
B1
m
B1
31
Nglabal V,
1/2 1/2 (81m+-1 + (1 - 31) desk (R:) +
N/global V.-1 -14-1
1/2
1 B1
1 BI
81 Mgtobal
(v--1/2- 1/2) m Nillbbll V₂
1/2 1/22 desk(Ar)
B1
31 Aglobal
r-1 - 1/2
Nglobal
1/2 RR Σ Åe,t
m N
1- B1
oEC₁
B1 Aglobal
(v,-1/2 v/-
m V.
Aglobal
1/2 R2
Moccl
sk clip
Acst
))
5
Zess
B1
Mocal
OEC.
Bi Nglobal
(vil//2 -V, v1- m
V1
1/2
R2 R,clip
Jest
V,-1/2 Σ
R
Beat
1 B1
N
N
cEC,
OEC.
in which v) "gglohal//ccal
By Taylor expansion, we have
1
((7++)) = [(++) + vL(T)) (7++1 7c) (7011-77) - 7o) f1c(1441 -1)
1
= C(m)) + V.((.) (T)())))(((1+>)))) - 76) -V((m))VV(()) (7441 - -m) ++2(tt1 -7) "H,,(144 -1))
VL(0)))
By taking summation from 0 to T - 1, we can get that
T
[(Tr) L(0)) = C(rr) - L(%0)
Σ (c(m+1) - L(x))
T
(()0)))((7++111 - -7) + 1 Σ
TL(0))((77+1 76) +
(V)))) VL(O.)) (74+1
(741
TT
Ac, 76)
T
T2
Ts
(26)
E.1 Bounding Tj
For each term in Ti, we have
vL(,.) (741 7))
42

---

=VL(0,))
81 Aglobal
(v=11 -V; m
"
1/2 Σ CEC,
Ve=
R2 Reelip
Σ go,t,k: 7
K
7
Vi-1//
1/2
Σ
Ry Boit
31
N
I
SEC,
=VC(())
Aighotall
(v-11²² -V. m VC(0,) -V=1?
Σ
R Raclip
Σ ko
1 51
OEC.
K Eectter)
N V2(0,) V, 1/2
Σ RR
R,clip
VL((,)
Vv, 1/2 Σ
R Ze,
N
oECr
R=1
eECa
By taking summation from 0 T 1, we can get that
T
V VL())) V (74+1 -7)
T
VL(0,)
Agggllall
[v,]1/ Vi 1/2
m4-1
1 B1
VL((0))
(V-1/2-V1-11
Σ cEC,
R2 R.clip
Σ gest,ke?
N
K
T
Vv
VL(0,)
Σ R R,clip
Ie.
VL(())
TV
1/2
Σ R Ze
N
N
ecC,
nEC,
89
84
(27)
E.1.1
Bounding S2
We first bound each term with fixed / E [7) in S2. According to Lemma probability at least 1 à
B.1
we have that with
7
K
N VC(A)T
(v--1/2 -V/12)
Σ
R. Raclip
Σ
ge.t,kr
OEC₁
N VL((.), -V,13 Σ
R R.clip
Σ Je.t,ke
oEC,
N (1 log 1.5 (NTG((0) /V 1/ (1
K
V= 1/2
Σ cEC.
clip
Σ
Vb
A=
<GTK,G (1+ log 1.5 (NTd2/0)
|v-1/22-v_11 1/2
(28)
vb
[v- V, 1/2
In addition. if 04,4
1-116 then
0.
If 41
Ut-1,ir
then
V.-1/2 1/-1
< 0, and
1/- V, 1/-1
1
/ut, +e
Vo--ii +E
VU--1,1 /0,,
(Vur, +c)
(v +
1/-1,1 D4.5
(Vors +c) (Vo--1, +c) (Vec-1, + vves)
43

---

(1 32) ([(desk())))
11-1,
(Vors +e)
(y0t-1,i + 6) (1-1, vers))
(desk(á)) 21
(1 1-)
desk (es)((ā)))
6² eV
(1
82)
v1
B2
v
62
v1
$2
Mocal
Dost ,7)
R2 Raclip
+ Rs Ze,t
6²
Macal
OEC,
v1 - BeThaaa
Σ OEC.
R2 Raclip
Ac,t Noocl
+
v1 -
BeMalaal
Σ
Ri
Zeet
Ne²
Ne
LoEG.
(29)
Therefore, we have
V1 1/2
V
1/2
max
Vv-1/2
V,
Dest Macal
max
R Riclip
Σ Ro Ze,t
2
Ne²
OEC.
LOEC,
< <ax
BeThoca
Σ GEC,
R2 R.clip
Dc.t
)1
+ max
vI - Bemhoca
Σ
Rs Ze,t
2
Mocal
Ne
LCEC,
(30)
For the first term, according Lemma
B.1 for each i E [d], with probability at least 1
TT
Ae.t
-7
Dese Mocal
(
Ae,t Tiocal
T 7)
log
1.5 (NTd//0)
R R.clip
R. R.clip
Ree; Raclip
Miccl
vb
TK.G
(31)
then we can get that with probability at least 1 - T
VI B2mocal
Ac,t
]
max
Σ
R R.clip
T
N
Moccl
.EC,
I BoTnocal
Ac,t
max
Σ
R R,clip
T
Ne2
Thocal
eec,
1 B2mocal
(1+
log 1.5 (NTd2/8)
TK.G
Ne
vb
B2mooatTKKG
1 (1+10g) log 1ogg.5( logT5(NTTP/0)
(32)
vb
For the second term, N Eeec, R2 ze,el, = (Reess & Ecec, Ze.1). Noticing that N Eesc, Ze,t ~
N (0, a and Rie; is tf --s-uu--uur sub-GGuussia random vector, so according to Bernstein incquality.
N
Naa avbN)
Rees, N
Σ Ze,t eec,
2 a
< 2exp
-emin
= 2 exx
-emin
o3 0g
44

---

so taking
Co log (241
we have that for each i E [d], with probability at least 1
4
VN
TT²
0g (8
Σ
R
Ze,t
(33)
VN
LeEC,
then we can get that with probability at least 1
T
max
VT Mooccal
Σ
R2 Zeet
S
Bethocal
0g log((d7)
v1
BoThocal 9
N
VN
VNe²
LoEC2
(34)
Substituting
32 and
34 into
30 we have that with probability at least 1 T
V 1/2
max
B2Mooaa
Σ
R
Relip(
Dctt
+
max
vI B2mhoal
Σ R zei
2
Mocal
N
IEC,
LOEC,
1 3oocc TK.G
log" 1.5 (NTd
-1-B32 327 log (2dT/6)
1
(35)
vb
VNe²
Substituting
35 into
28 have that with probability at least
36
T
K
Vc()))
(Vo 1/2
Σ
R₂
Raclip
Σ
gc,t,k?? T
N
CEC,
log" (
||161/2 V=11/2
<GTK.G
1
vb
log (NT.:(NNd//5)) 18)
VV
3emhoca (1 (1 log (NTTN/N)
v1 B2mooaa 9 (2d(2)/0))
<GTKGG
1
1
+
vb
2
vb
VNe²
Thocal /
(1+
log 1-5 (NTP/88
Moocal - 32GTK,GO, log (2dT/5)
log" 1. log'. (NNT
1
22
Vb
VNe²
vb
(36)
By taking summation from 0 to T 1, we can get that with probability at least 33,
VC(O.) (V- -1,11/2VV=11) Σ RT R,clip
Σ go,t, T
Moccl B2TGTk.
(1+ log 1.5 (NTT&/ (6)
2
Mocal VI ByTGTK.Go log(2dT/O)
/
log (NT (/T2/18
1+
22
vb
VN
vb
(37)
E.1.2 Bounding S
We first bound each term with fixed / E [T] in Si. According to the definition of m 1, we have that
VL(,))
31 Aglobla
(v/1/2
1/2 Vq 1/2) m
1 B1
=VL(0.)
31 Mglobal
(v=1/22 -V,
V. 1/2)
(1 (1- (1-81)391--1 desk((ā))
1 B1
-VC(0.) Bigglobal
(Vill/=-V;"" 10-1/2_1-117 -V
3 g
N ()s)((
45

---

8 Nggiohal
VL((,)T
(v V,- R. Σ
N
oEC,
8 Mglobal
vL(O)) (v= - Vi 1/-
1/2
R Σ
Mocal
sk clip
Aer' x :7) + Ze,r!
.7
Mocal
CEC,
8
Ac, Mocal
((())) -V-1/2-1,- Σ
R.P
Ry.p
,7)
N
oEC,
W1
vL(O.)
- -V-1/-V
Σ
(38)
N
CEC,
W/
E.1.2.1 Bounding W1
We first bound each term with a fixed & E [T] in W1. By applying the same analysis as above, we can get the same bound as 36 with probability at least
36
1 VC(O.) N
1 (v-1//- V
Σ cEC,
RZ, clip
Σ
gosr Jos
k=1
Mocal
VI K
(1+ log 1.5 (NTd
2
Thocal
32GTK,GO log(2dT/ (1+
log 1.5 log (NTd)) //))/))))))
22
vb
VNea
vb
By taking summation from 0 to - 1, we have that with probability at least 1 1-36
(C(,)) -V
Σ
R.T,
clipp
'Hocaal
cEC,,
MMocall I - B2GTR,C (1+ (14 (NTT)
MMMocaa 3.GTK.0 log (og(2d(/8) (1+ log' logg (NT oe
Σ
37
vb
VNe²
vb
Macclll 31 11/1-B2Tr B2GT..
1.5 (1+ l (NTT
+ Mocaa vT 32GTK,00 log(2dT/6)
log
1.5
(NTT (
1+
e(1- B1)
vb
VNe(1 -B1)
(39)
E.1.2.2 Bounding W2
We first bound each term with a fixed & [T] in W2.
V.().) (vi-/2 V 1/2)
Σ R Re
Ry (vi_1/² - V1 1/2) T
VL(O.),
1 Σ RTZes
N
N cEC,
cEC,
Noticing that
1
[v= 1/2 V 1/-1
Σ
Zorr' ~ N
0,
o
N
N
cEC,
|/ -v-
and R., (v=\/2-v,- V C((,)) is so according to Bernstein inequality.
Sub-Gaussian random vector,
vb
v22 P (( Ry (vi)1/2 11,12211111)) VL(8.),
Σ R.IZZe
2a
eEc,
46

---

a²
22exp
-emin
V 1/2
V, 1/2
V. 1/2 V, v8
1/2
b 12
Na²
av
bN
exp
-cmin
0
V V
1/2
V. 1/2
VL((0)
0g
V V
1/2
1/2
| log(27/6) and combining with 35 we have that with so taking a da 1/-1/-v/ 1V
probability at least 1 1 T
Rr (Vi-1/2 1/2 - -v-
VC(O.), 1 Σ R
N
OEC,'
V 1/2
1/2 - -V,
[L((0))l2 (2g(2T/6)
/
2
VN
Jg GgGgo((2)/))
[vI
3eThocaTK.C (1+ log 15 (NTdP/8) vb (1 log (NTTP))
VI BeThoca og log (2dT/8)
VN
22
VNe²
Maccl I
Bro co
nocal /I 320 2 log (2T log (2dT/8) /8)
V
vb
Ne²
By taking summation from 0 to - 1, we have that with probability at least 1 - 35,
7 (C(O)T (V - V1 1/-)
Σ
N
OEC,,
M)hccl - B20 GTK, log(2T/0)
(1+ log 1.5 (NTdP/0)
+ 1)Tlcaal /1 320 log (ogg((T//))) log log(2TT) (2dT (og (8)
Σ
39
VNe²
vb
Ne
-/=0
Mocal 31 V I
(2T/0) VNe((1 B1)
1 log
1.5 (NTdd/0)
MM V1 B20 (og((///)))) log (2dT
Vb
Ne (1)
(40)
Substituting 39 and 40 into
38
we can get that with probability at least 46,
VL()))
31 Pglobal
[v (v_ Vē 12) m4-1
31
VC(O.T -V/12-V111/3 Σ
R.J. clpp
Aesr Mocal )r)
N
oEC,,
g 1I
VC(O.) (V=1/2- - VV
N
cEC,
MMocal B1 /1 BaGTK.G
(1+ log (NTiP//)
2
Mixcal 31 VT - 32GTK,G log(2dT/6)
(1 log 1.5 (NT)P/8)
+
211 31)
Vb
VNe(1 - 31)
Vb
+ Miocal 31 V/VI B2o,GTKKG
log
1.5 (NTTP/0)
Milcal 3IvI 1 (loo((og(TT/5)) (og(2)))))) 1og(2dT/0))
11
+
VNe((1 (1-1)))) (1)
Vb
Ne B1)
Mocal - (1+ log 1.5 (NTT)/1))))))
21mocal 31 VI 32GTK (og.TT//00)())100) (1 log 1.5 (NTT
(1)
vb
VNe2(1- (1-)(
vb
MMocaa 31 31V1- B30 log (2dT//))
Ne²(1 11-1) 31)
47

---

By taking summation from 0 to T 1, we can get that with probability at least - 46,
VL().)
31 Agnloball
- (v 1/2)
m4-1
1 B1
Mhocal B1 /1 32TGTR.
log" log!.0 (NTd 1+
21/Mlcal 31 vI 32 GTg log(2dT/8) ( log (ogg.(NNdd)
1+
e²(1 B1)
vb
VNe - 31)
vb
Moccal 31 vI 32 (2dT/8)
(41)
Ne2(1 31) 91)
E.1.3 Bounding $4
We first bound each term with a fixed E [T] in St. NN VV (R.V ( N Exec, Ret)-
1/2 E.ec. R Ze,t =
Noticing that NN Exec Bett
N N(O, (0,,711 TT), and
R₂ (V(()/ is ( 1/2
Do-Gaussiin random vector, so according to Bernstein
vb
inequality,
IP
R 1/2 VL(O.),
Σ
Ze,t
2 a
N
.EC₁
a²
<xe
-emin
V.
1/2 2
[V
1. 1/3
VN
vb
Na
av avbN
=2cxp
-cmin
VL(()))
V.
1/212
1/2
og IVV((0))
V,-1/2 1/2
g
so taking a <.I V. 1/2
1og(2T/8) /8)
and noticing that V, 1/2
S e we have that with
probability least 1 1 VN
2
á 7.
Og VL(,,) log (TT
og G Gogg(11/))
RAV, 1/2 VCC,))
Σ Ze.t
N
VNee
VNe
CEC.
Then denote x, Et [C()))) 1/7 V/ Ecec, RIIZe,r we can that X, is martingale with respect to the Gaussian noise, and from the above analysis, we have that with probability at least 1 8, for all [T'.
I X - VC(O.) N
(
1
1/2
1/2 Σ Rr Ze,t
Og GogTTT(2T VNe
Then by Azuma's inequality, we have
a
Nea 2To3 log (2T
P (XX--5--)) exp
cxp
(a.Glog(2T))) VNee
T.
(2T
By selecting a
we can get that with probability at least 1 282 28,
VNv
X7-1=
VL(0.),
1
V Σ
V.
Rí Ze,t
2
log? ((22T/8//2Tog
(42)
N
VNe
1=1
cEC,
48

---

E.1.4 Bounding S3
For each term in S1, we have that
T 1/2
Σ
Ry
Reclip
Σ BesKITT
N
OEC,
k=1
KK
VL(O.), V= 1/2 1
(.. +K ( (VCIO))VV
Σ
(Lo(0.)
C - Σ
vV.(0.)))
C
N
OEC.
i=1
K
K
+
V, (((,)),
1/2
(VLo(OcAN)) - VLc(01)) -V((CL))) + vC(0)).
V, V,- 1/2
(ge,t. - VLe(Oe,,.k)))
N
N
OEC, Am1
oEC, Am
VC(O.), N CEC.
V/
Σ
clip Σ Desties
Σ gost,
VL(O.), V 1/2
R₂ Riclip
Σ Besthr
clip
Σ
N
cEC,
k=
By taking summation from 0 to T 1, we can get that
VC().) TV=
1/2 Σ
R
R.clip
Σ
go,t,k.
CEC.
A=1
T
T
C
VL(0,), V
C (O.)
1
+K
VL(O.).VTll
V-11/
Σ (Lc(O.))
- Σ
v (co(
N
CEC,
1=1
12
VL(O.); 1
1
1/2
(0.ek) vC.(O.))
N DEC, A=1
VL(0.), -
1 1/2
v
(ge,e, (Lo(Oo.))))
N oEC, k=1
Y4
K
K
+
VL(0.), 1 1/2
Σ N cEC,
clip
Σ go.
- Σ
gc,t,k
1=1
Y:
K
K
1 VL(O.); 1 V-1/3
Σ CEC.
R Riclip
Σ
Ie.tkk: 7
clip
Σ
Jest,ke
(43)
N
k=1
Yi
E.1.4.1 Bounding Y
According to the definition of Vi-1, we have that
1/2
[(vo-i++] +))
(Vur-1,5
Substituting 31 and 33 into
29
we can see that with probability at least
28
for any E (7).
d.
()))
2 9.
Mocal Σ
R Relip
Art
7)) + R. Ze,t
Mocal
oECi
49

---

Mocal
R2
Reclip
Aest Mocal
]
Nocal
Σ
RS Best
N
OEC.
LCEC,
log (NTd' /6)
Thoca g log(2d7) (6)
$
Mocal
++
TK,G +
vb
VN
Then according the definition of second order moment, we have that with probability at least 1 26
(desk(()))) 2]
(I+ log 1.5 (NTP/1))
Mocal g log 2dT 2dT/6)
0t- S max
Mocal
TK.G +
vb
N
so we can get that with probability at least
20, for all i [d].
[v= +6)
(1+
log 1.5 (NTT /0)
Mocal log (dT//)
Mocal
TK.
vb
/ N
which implies that with probability
VL(0,), V_(1 C Σ
vo.(
C=1
Mocal
1+ log" (NTTP/8)
vb
TK.G + Mocal (og(2d//))
VN
+E
1 VL(1))
C
Σ
V (o.)))
log (NTd//O)
TK.G + Mocal log( (2TT (8)
1
+c)
Moccl
vb
N
so with probability at least 1 - 20,
C vC(O))
log (NT&/18)
TK.G Moncal g log (2dT/5)
-
Σ vC.(())
Moocal
1+
+e)
V
C
vb
VN
(44)
E.1.4.2 Bounding
first bound each term with a fixed E [T] Y2. According to the assumption, each C, uniformly randomly selected from [C], so by Hoeffding's inequality, we have
<((
P
C(()))
v/
1 N GEC,
Σ
(L.(O)) (VVC(00)) 2a
2N+
(-Ne2)
Neet
<2exp
2exp
2G2
2G4
/2log(2T/8)G²
By selecting a
we have that with probability at least
VNe
T
- - vV....))
logo /5)G2
VC(O,).VIl'
Σ (O.)
<
N
VNee
CEC.
iml
Then denote Z, Et (Tc(0r,, ( Exec, VC.
EE VC.(Or))) we can see that Z, is a martingale with respect to the selection each round, and from the above analysis. we have that with probability at least 8, for E (7),
1ze Z (C(())
Σ (..
C Σ (...00))
)
2log(21/0)C) (2og(21/0))
VNe
SEC,
1=1
50

---

Then by Azuma's inequality, we have
a²
N
P (1 -a) S exp
(V2log(T/666c cxp
4T log (2T
D.
/Nr
21oR(2T TC
By selecting
t
we can get that with probability at least - 26,
VNve
-T-1
T
VL(O)):
Σ
VC.(0))
1 -
-
Σ VL.(0))
2log(2T/8)
(45)
N
VNe
[=1
E. 1... Bounding Y3
For each term, we have
VL(0.), 1/2 V-
1
(oolk))))) VL.(0))))
N OEC, k=1
K
VL(O.), V 1 (fc,tk Oi)
N
OEC, kml
K
nocal
VL(0,), V/ fockk Σ
Destiv
N
CEC, kml
x=1
K
Mocal
[L(,0))
N
k=1 k=1
Mocal
N. G²
L
Σ
k
N
Mocal 2K2
26
so
T
K (VCo(Ocr))-
Thocal To T222
VC(O)), - V=
(46)
N
2E
CEC, k=1
E.1.4.4 Bounding Y4
We first bound each term with fixed / [T] Y4.
K
1
1/2
1/2
- VL.c(ot..))
N
k= k=1
K
I1ac,e.k (CC [LL()))l2
N
oEC,
k=
G
Σ oEC,
- (Cc.O..k)
Ne
According to the assumption, the stochastic noise l|ge,e,k - VLo(Oe..))ll) o Cg-sub-Gaussina random variable, by Hoeffding's inequality,
a²
IP
11a.... (Lc 2 20) < 2cexp
[NKo
DEC,
R=1
51

---

By selecting a / NK 1og(2T/6)0, we have that with probability at least 7
Σ
VLo(Oaa - Noggo
k=1
K (go,t,t VLo
v((O)) - v
N
CEC, k=1
G
19,tth
Ne
oEC, k=1
G No
GV 1og(27/0)
VNc
Then denote W, = E+= VL(0)), $/2 4 E Ex (ga,'' - (Lo(Oar(x))) we can
that W, is martingale with respect to the stochastic noise, and from the above analysis, we have that with probability at least 1 - 5, for all E (T].
W. - Wi-1 VL(0)) 1 V N
K
(gc,e.k - V(c(Oc.)))) )
G K 1og(2T/8)0,
-
VNe
oEC, k=1
Then by Azuma's inequality, we have
a
Neaa 2TG
P(WT-15 < exp
exp
G//Koo(22/880,
(
2 T.
VNr
By selecting
Gy2TK 1og(2T /8ja,
we can get that with probability at least -25,
VNc
1 VL(O.),
(ge,t, vlocOctt.))) )
GV2TK log /8)0
WT-1
N
VNc
(47)
E.1.4.5 Bounding Y:
For each term, for KG, have
K
VL(O.):
N
1
1-1
1/2
Σ
clip
Σ
Bestokis T
Σ gest.k
cEC.
k=1
1=1
K
V/
clip
Σ Ie.e.bs 7
ge,e,k
N
rEC.
cEC,
G(KG-T)
for 2 KG, we have
K
Σ go,t. )) =
K
VL(0,), V-21/2 Σ
clip Σ gest.ks F
cEC,
8o
1 1 1/2 VC(O))
1/2
Σ
clip Σ 7
ge,t,k )) max 0,
G(KG- -T)
N
e
R=
52

---

By taking summation from 0 to T 1, we can get that
K
K
))
2 max {
TG(KG- -
VL(),),
N 1/1/2
clip
Σ
Dest,ks
7
Σ
c
CEC.
1=
(48)
E.1.4.6 Bounding Yo
We first bound each term with a fixed E [T] in Yo. According to Lemma probability least 1 4.
B.1
we have that with
K
K
VL(0,), N 1-1
Σ
Rí R.clip
Σ
Destods T
- clip
Σ
CEC,
k=1
k=1
log" 1.5 (NTd/O)
K Σ
VCC(0))l2
/ clip
Iost,k+ T
Vb
oEC,
A=1
log 1.5 (NTd/O)GTKGG
Vbe
Then denote U, = = VC(+))) +/ Exec, (R, (Ek- &e 7) clip (Ek Io,t de x)))
we can see that U, is a martingale with respect to the sketching matrices, and from the above analysis, we have that with probability at least 8, for all E [T]]
U - U--
V((,,),
1/2
R2 R,clip
Σ Imsteks 7) clip Σ Dc,t,
N
OEC.
log 1-5 (NTd/8)
Vbe
Then by Azuma's inequality, we have
a²
be
P PUT-11 aa) exp
log 1.5 (NTdd/))GKk
2
exp
2T log
( 6N
T.
Vbe
log" (NTd/8)
By selecting
we get that with probability at least 1 - 28,
Vbe
K
K
WT =
1 VL(O,),
V (-1
Σ
R R.clip
Σ
ge,t.k. v
clip Σ
Sesteks
N
oEC.
1=1
k=1
log2
(49)
bE
Substituting 44
45
46
43
have that with probability at least 86,
VC(A)) TV,
1/2 Σ R. R.clip
gc,t,ks
cEC.
K
VC(O0.) v 1/2 1
V (O.))
+
T
VC(O)),V
1/2
Σ (..(0.)
Σ 1=1
C
vc.(0.))
v
C
N
1=1
cEC.
VC(0.); 1 V-1/2
V L. v.o((t))
N GEC, 1=1
VL(0), N DEC, km1
1 -ー 1/2 1/2
Σ
(ge,t,k (CC(Ae)))))
53

---

VL((.): 1
V
1/2
Σ
clip Σ go,t,ke 7
K
K
g0.t,
N REC,
1 VL(O,):
V 1/2
Σ
Ry R,clip Σ So 7
clip
Σ Je
N
DEC.
log (NT
Mocal log( (2dT/b) 15)
-1
T
2K 2K (log
Moxal
1+
vb
TK,G +
VN
+c)
K
[V((0)112
VNe
t=1
Mocal
TLK2G
GV2TK
log (2g
TG(KG 7)
max
0.
2E
VNe
vbe
(50)
Substituting
37
41
42
50
into
we have that with probability least 1 - 176,
(l,)) (76+1 7c
Vl(0))
B7gglohal
-V, m4-1
1 B1
K
vc(0,) (v-1/2- -V;T//)
Σ CEC,
Rí R.clip
Σ Dost.ki
N
K Jost.ke
VC(O,) TV Σ
Rí R,clip
1
VC(,,) TV,
1/2
Σ Ri Ze.t
N
OEC,
OEC,
<- Moccal (+ log 1.5 (NTT)
Mocal log (2dT
-1
TK,
+C)
n
V L((e)))
vb
VN
2n K VToog(2T//
Mocaa T TLK
GGV2TK 12g (8)
TG(KG T)
+
max
VNe
2E
VNe
+ 7) log" (NTd2 (8) TTGTKK
Monca -1-VV/1-/-00 B2TGTKo (1+
1. (NTT""
+
Vbc
62
vb
Micca v1 TTT,TK,G C log(2dT/8)
(1+ (NTT)((NT
VN
vb
MMoca 31v | 11---IGTKKC 11 log 15 (NT
e 31)
vb
+ 21/hhcat 31 vI B2TGTK,0o log (2)(2/)/))
1. (CKTd/8) log
1+
VNe2(1 - -1)
vb
7//oca VI o (2dT +
n (2T)
Nee -31)
VNe
-- Mocal (1+ log 1.3 (NTTPP/)
Mocal 9 (2dT
-1
T n Σ
TK.
+0
(L.)))1
vb
VN
2n
Mocaa T GGVTTK log(2T/0)) 18)0
TG(KG -)
+
max
VNe
2E
VNe
+ 71 log" 2 (NTd/8) 2TG
Meoca v1 - B2TGTk. (+ log 1.5 (NTTd 16)
log..'
Vbc
(211
vb
+ MPocaal (1 BT)TT BTGTTKO log(2dT/5) (1+
1og 1ogT>((TT22/))))
(Ne(1-8))
vb
54

---

Whocal V1 B2To log (2dT/6) (20T// ( (2T
(2T
Ne 31)
VNc
s-(Tica) (foccal
log (NTT TK,G +
T Log(2d(//) /0)
Mocal (1+
+e)
n
VL(()))
Vb
VN
+ 2n /To +
nG IGK log(2T/8)0,
TG(KG- - T)
max 0,
VNe
26
VNe
+ 7 log 2 (NTd/5) (
MMocal (2 B1) 32TGTR.G
log 1.5 (NTT /0)
1+
Vbe
2 (11)
vb
Mocaal (1 + 232 231)v11 B2 log (2dT/6)
2 - 31)
log" (2T/8)C² log" (2T200/0)
(51)
Ne
E.2 Bounding T2
For each term in T2, we have
(VL(n) VL((,)) (1641 - %)
-7h -7x-00 0,) H2,, (7441 71))
B1
B1
(0; - 0c-1) M2. ( B1 (0(+1 (01+1-0)) - 01)
(0, - 02 0--1)
1 B1
1 31
31
88
(1 - )1 (0: - -0=11) i1',, (0c+1 - -0)) (1 31)2 (0, 0--1)² fl'e, (0: - 0z-1)
By taking summation from 0 to T - 1, we can get that
T
[(ve(m)- -L(()) ((()))))()))))1------- (741-77
t=1
31
3
Σ (0, 0--1) it'e,
(0, 0-11) it'e, (0. - 02-1)
(1 31
(1 B1)²
Sb
Sq
(52)
E.2.1 Bounding Ss
We first bound each term in S₁ with fixed E [T'.
(0e- 0.-1) T H'',, (0t41 0c) ngianal
(ViI//2m mp-1
H2,, (V.1122m)
d
[i [/-l/2m0
Σ )aray 1=1
(v: (v:
Ngiobal
d
Ngioball
Σ
A;
(V:3//2
(v=
[-1
Us (v. (o)
(53)
1=1
For each i E [d], we have that
(v. 1/ (1/mm--))
T
01
=(1 (11)
6-1
vi g 1- 11-1-1.-- 1-2 desk((
1-1
< - 31)
Σ
8
11-1-7
(vV desk((rr))
+'=0
55

---

(v= desk(ár))) ii
I max r Elt-11
(54)
Similarly,
Vi
1/2 me)
T
0i
v max r'E(
(v- desk ((rsk(n)))
(55)
For each T'E E 1).
Vi desk desk(A (,,))) T
v/
(desk((r)) Vi-2(-233
Rig
Σ
Å o V/-l/2
cEC,'
1
RT Σ REC,,
Mocal
sk (clip
clip
Acr
.r))
Ze,r"
v= 216
N
noocl
)
nocal
Σ R clip
Σ Jor's MarrR (iTT) Vi= 04
nocal
Σ cEE,
R Vi 1s
N
N
(56)
For the first term, according Lemma
B.1
with probability at least
5
K
Σ IeC,,
R Ry clip
Σ
90, ke 7
VV=\/30
V1
log 1.5 (NT))18)
| 21
Σ
clip
Σ Jear Ne
Vb
DEC,,
1+ log 1.b 1.b
(NTd/
NTK,
(57)
vb
For the second term, ( Eose, Riizer V/ (/))))
Ro V
1/2 1/2
N Exec, Zo,r' )
Noticing
|=
that Exec, Zer N (0, (+11 and R, V/11 according to Bernstein inequality,
0/ is
2 -su-ub--rr Gaussian random vector, so
vb
((R. 1/2 Vi N
Σ Ze,
2 a
2exp
-min
V
2
V 1-1
eEC,,
N
VbN
Na
avbN
bN
2 exxp
-emin
o
V
1/2
0g
V V 1/2
0o vollvv-//31 (2) /N
so taking
and noticing that
v 1/2
we have that with probability
least
1
5
Td
RT Vi--1 24 )
o V,
1/2
log (2
1
Σ
og log(2dT/6)
(58)
N
N
VNe
oEC,
56

---

Substituting 57 and 58 into 56
we have that with probability at least 1
25
dT'
(v=r?2 desk (esk(A))))
Vi
Σ (ertsssT vv:l1/ 1/ ))
Nooccll N
Σ R.. R.
nocal
Σ
R
N
leEC,
IoEC,
Moocal TK,G TK.G
(I (1+
log.. (NTd/
log"
noccll log(2dT/0) VNe
(59)
vb
Similarly, we can get that for r' E [t], with probability at least 1
28
27
Vv. 1/2 desk Ar,))
1/2
U2
T. (1- log (NTT(NTT)) /0)
Vb
Mocall log (2dT/b
VNe
(60)
Substituting 59 into 54
60
and
55
we have that with probability least 1 d
( V 1/2 m=-1)
(v= desk((ār))
6-1
Us
S
max r'E(t-1]
Mocal MocaaTKK.G
(1 1+
(NTTN(//)) log" 1.5
Mocal g (og(2dT/o)
(61)
vb
VNe
(v- me)
(v-2//0 desk (eesk(A)))
< max r'E(d]
nhocal TK.G
(1+ log 1.5
(NTd2
+ Mocal 1og(2dT/8)
(62)
e
vb
VNe
Substituting 61 and 62 into 53
we have that with probability least 1 28,
(0) 12-1) H',,t (0e+1 01)
Iglobal
A
V= m/--m)-1))) )
T Ui
Vi
1/2 (V-1//mm))
me)
T
Mo.cTTK.. (1+ log (NTTd2
2
Mocal
S Agiobal
vb
VNe
i=1
(2
MTocalKKGG (1+ log (og20((
2
noccll 9 log(2d7 (200///0)
))
2)
Englobal
+ +
Σ
Av
Vb
VNe
1=1
2n LTkaL
(1+ log (NTPP))
II log 2 (2dT/8)
+
2
Vb
Nea
By taking summation from 0 to T - 1, we have that with probability at least 1 - 25,
21 (1+
log 1.5 (NTd2/0) 10)
2 +
2nj² o I LT log (2dT/8)
Σ (0, 9.,1) T fl'e, (0t41 01) <
22
vb
Ne
(63)
E.2.2 Bounding So
We first bound each term in Sa with a fixed E [T].
0.-00_1) H'.. (0. - Oc-1) = nigarall (Vi-l/2m me-
We, mi-1)
d
= natobal V/=l(2mo-)
Σ
xooo (Vi m
57

---

globbll
X
(v-
(
m
1/
(64)
Substituting 61 into 64
have that with probability at least 28.
(0, - - He, (0x 0(-1) = Iglobal
Σx,
As
(v
(V=\(mm-))) m
1/2
U/
2=1
MocclTKK. (1+ log 1.5 (NTdd
nlocal log (og(()//))
glaball
Σ
12
vb
VNe
2n LIPIL
11110' log' (egl.(NNd'))
o IL (2dT/5)
[1+
2²
vb
Ne²
By taking summation from 0 to T - 1, we have that with probability at least 1-28, 28,
Σ 00 - 0(-1) Hl'. (0. - 02-1) 2n II.
T
(1+ log logg (NTTd//))))))
2n o LT log (2dT)
vb
Ne
(65)
Substituting
63 and 65 into 52
we have that with probability at least 1 - -22
T
(VL(m)) - V2(0)) (7++1 7))
B1
T
87
T
Σ
(0: - -0-11) H',,, (0c+1 -0)
(0, 02-1)
H',,, (0. 02-1)
(1 B,)3
(1- (.83) )1)
t=1
31(1 + 31)
21 IIT TK.
log" 1.5 (NTd// I+
2
2n
2 LT log" (2dT/8)
y
(1 31)²
E
vb
Ne²
20 (1 + BB)IILTTKK.G
log 1
2
21 + log (2dT/8)
1+
é² B1)2
vb
Ne -31)²
(66)
E.3
Bounding T3
For each term in T3. we have
(1+41 7a)) Ac. (76+1 - -
B1
1
B1
1 31 (0c+1 0z) 1 B1
(0. 02-1)
Hc,
(0r+1 0z)
(0: 0c-1)
1 B1
1 31
2.3
(0c+1 - 0z) He,t (0++1 0c)
(0.+1 0e) Ac., (0: 0.-1)
(1 - }2
(1 31)3
189
+ - 3 (0+41 - 02) Mc.. (0u41 0₂)
By taking summation from 0 to T 1, we can get that
(7t1 mt)_ Hc, (7+11 ve)
2,1 (0t+1 0.) Me,t (0e41 -4)
(0.41 06) He. (0, 0.-1)
(1 )
B1)
$7
(0.+1 - 0,) He. (0.41 - 0.)
(67)
(1 - 3
58

---

E.3.1 Bounding S
We first bound each term in SS with a fixed E [7].
(0c+1 - -0)) ee (0z+1 Oc) - ngiaball
(Vi (v=
mi)
Heg (
2 Nglobal
V V/- mi)
Σ
)v.)vo (v-1//ma)
!glohal
Σ X
m2)
Vb
(68)
Substituting 62 into
68 have that with probability at least - 28,
(0t+1 0e) He, (0(+1 0c)
Σ d
(v--1/2m))
Vi
1/2 ml)
T U/3
2
Iglohal
Ail (MocalTKK (1+ (Mhoarkaa1++ log 1ogl.((N)) 1oTL:(NTTP/65)
Mocal log (2g(2)//8)
Σ
Iglobal
vb
VNe
1=1
2n IITKa
(1+
log!. (NTTP/0)
log
2 +
2 log (2dT/6)
[+
22
vb
2
By taking summation from to T 1, we have that with probability at least 25,
IITT
(1 1
log" 1.5 ((NTP/0))
2n o IIT LT log
(2dT/o))
(0++1 0,) Hc,, (fc+1 0.) s
22
vb
Ne
(69)
E.3.2 Bounding Ss
We first bound each term in Sg with a fixed E [T].
(0++1 - 0.) Hc (0. 0c-1) nelobal
(v- 1/2 Hc (V-l/2 m--1)
ngiobal
Vi- (v-1/2mm) me)
Σ Navikk
(Vit(/mme
1/2 m)-1)
2 Ngiobal
>i
(v.
U/ (v:)) (-1/) D/
(70)
i=1
Substituting 61 and 62 into
70
we have that with probability at least 1 - 28,
wz (v, 1V22 1/-122m441 m4-1) )) T
(0++1 0₂) He. (0: - 0--1) = Viloball
A
V1
1/2m²)
m)
1=1
Mocal (1+ log (ogT>((NNd2//) +
Mocal log /6)
2
> - Ngiobal
Σ
Nil
vb
VNc
1=1
2n ILTKO
(1+
log
(oT_)((TT//8)) 2 II log (2d
vb
Nea
By taking summation from 0 to To T -1, we have that with probability at least 1 28,
T
2n 2
(1+
(NT(/8)) /6) log2. 2 21/2 LT log
(NT
2 (2dT
Σ (0.t1 - 0,) Hc. (0: - 0.-1)
2
vb
Ne²
(71)
59

---

E.3.3 Bounding Sy
We first bound each term in Sg with a fixed E [7).
(0, 1 Hc,, (0g- 81-1) = ngiahal
(vi-1² 1/2 ml-1)
Hos (Vil?2m--))
(/-11
1/2 m
Σ Aevio?
(vi-l m
Ngiabal
(1. m)-)) (v=-)/m0-11
/global
A
V/s
(72)
Substituting 61 into 72 we have that with probability at least
28,
T (v= -1-2)---))))
(0,- 0.-1) Me. (0+41 - 0t) = Vigaball
U/
i=1
T.ocuTKK.G 1
log" 1og.55 logo (NT& (8)
Tloall log (2dT/8)
2
Viglobal
Nel
vb
VNe
i=1
2ny In
(1+
log (NTTc/1))
2
211a 2 log" (2dT/8)
+
2
Vb
Ne
By taking summation from 0 to T - 1, we have that with probability at least - 25,
T
2IPILTTRK
(1+
log 1.5 (NTT 10)
2
2n of log loggoggg2gg2 (2dT/8)
Σ
(0, - (1-
22
vb
Ne
(73)
Substituting
73 into 67
we have that with probability at least 26,
(1+11 - 7b)
Ao, (7411 - 7(
T
23
T -1,
(0.41 -6) Hc,, (0.+1 06) (1- --)33
(0.+1 - 0,) Hc., (0, 02-1)
(1
B1)
t=1
1=1
87
T
(01+1 0c) Hc,, (0t41 8i)
(1- 31
1=1
(1 + 31)3
2 ITLILT (1+ log 1 1 (NTNP/8)
2 IIT log 22d7//
+
(1 31)²
2
vb
Ne²
21 + P.ITITTK
(1+ log (NTd
21 + 3, IIT log (2dT/44 (5)
(11 - (1)2
vb
2e B1)
(74)
Substituting
51 66 74 into
26
we have that with probability at least 1 - 198,
-(Tr)-(((1)) T
T
1 T
VC(0.) ((00))((7641 - 76)+ +
[(VC()) - vL(())) ((00)))((6+1111 -76) +
Σ
(7+1
- m))
Hoc.H -m)
2
1=1
t=1
(1+ log 1.5 log
(NT(P/))))
Mocai 9 log (2)
-1
5- Moccal
TK.G
+E)
nk
VC()))1
Vb
VN
t=1
K /To
Miccal TLK
2GK (2g
TG(KG T)
11 max
0,
VNe
2c
VNe
60

---

") log n (NTd/6)v /2 27 GTG, +
Mocal (2 3TTGT
(
1 log (NNT.
vbe
-(1- (1)
vb
Mocaal (1 + 231) vI B (2dT/6)
log (2T/8)
2np (2T/6)0²
(1 31)
Ne
21/ (1 + 31)ILTT
2 log 1.5 (NTT
27 + O log (2dT
1 vb
211 -3)
Nc² 33)
2n (1 + 81) II)TIT
(1+10g Mogg"((Ndd///)
21 (11+++)) 31)0002 log" (2dT/o)
c2 - 31)
vb
Nce B1)²
Alocal 1+ 1+100 (ogTs
Moocl log (og(2dT/6))
T
TK.G +
+()
n
IV
Vb
VN
k vT (og((2//))
Mhlaa TL
GGV2TK
log(2T/8)0
TG(KG- -T)
+
maaxxx 0,
VNe
2e
VNee
7 log" (NTd/8) 2TG
Mocaa (2 +BBivTT -32TGT
14 log 1.5
(NTT
Vbe
-31)
Vb
MMocal (1 + 23:3311= B (2dT/0)
log 2og2(211) (2T/8)G2
21 (logg((27) (2T/8)0
Nea(1 - -B1)
Ne
2x/2 (1 281) BI)IITTKKG
1 log 1.5 (NTT& 10)
2
2T 23:) + LL) (2dT/8) (20T1/))
+
+
-1)
vb
12(11-1)
Since
((0b) [(rr) S C(Ou) L
can get that with probability at least 196,
02 (C(0)) -f)) + 2012 log (og(2T/5)CC 2
|VC(0))
T
nKT
VNTc
VNTKe
a2G((KG
/2az log" (NTd/0)GTKGC
M 31 B2G
+ max (0.
Ke
VOTKe
Ke (2(1)131)
Mocal
(1+02221+11))) 211) (og + ag log log2 (2I/8)C2 + 2no log" (2g2(22))))))
(2dT/0)
(Ke2(1-8))
TTK
NKc
2maaa (1+ 231 (1 +1,)IITTK.C 2ma2(1 - 231) + I1)o (2dT
+
Ke2(1-
NKe - 31)²
in which
= 1+ log (NTd2/5)
(1+
log 1.5 (NTd//8)
Mocal log (2dT) /8)
vb
0'2 = nocal
Vb
TK.G
N
with TK.G min {r, KG), then we finish the proof.
61

---

Additional Experimental Results
We will present more experiment results under different privacy levels. These figures further verifies our observations and conclusions in Section
F1
Vision Tasks
E.1.1
ResNet101 on EMNIST
E1111 Different Privacy Level Ep
Training dynamics and test accuracies of Fed-SGM with ADAM, Fed-SGM with GD, De-FedAvg and its Adam variant, and DiffSketch training ResNet101 on EMNIST with 6p = (2.75. 0.42, 0.18) presented in Figure 3 Furthermore, in Figure 6 with fixed privacy level ep 1.6, also show the comparison of training dynamics and test accuracies among sketching dimension b {4 104, 4 10 4 10 4 x 10"].
F.111. Ablation Studies
We conduct the following groups of ablation experiments, mirroring the setup of Figure Tand varying only the clipping threshold and the number of local steps K.
We compare our original setting (r 1) with T = 0.5 and T holding all other hyperparameters constant. As shown in Table 3 in current experimental setup, test accuracy increases as grows, indicating that a looser clipping bound allows larger gradient norms and yields better utility under our noise regime.
Table 3: Test accuracy (%) for different clipping thresholds т.
GD, Sketching
GD. Non-Sketching Adam, Sketching Adam. Non-Sketching
0.5
62.91%
62. 02.89%
85.03%
78.42%
1
62.98%
63.34%
85.09%
78.60%
=
2
63. 18%
63.57%
85.33%
78.75%
We compare our original setting (K = 18) with = and K = 36, keeping all other hyperparameters fixed. Table T shows that, in our current experimental setup, increasing allows each client to perform more optimization steps, which leads to better test accuracy.
Table 4: Test accuracy (%) for different local steps K.
GD, Sketching
GD, Non-Sketching Adam, Sketching Adam, Non-Sketching
K 9
56.54%
56.66%
83.63%
76.57%
= 18
62.98%
63.34%
85.09%
78. 78.60%
36
71.81%
72.18%
86.72%
81.04%
F.1.2 ResNet50 on MNIST
Training dynamics and test accuracies of Fed-SGM with ADAM, Fed-SGM with GD, DP-FedAvg and Adam variant training ResNet50 on EMNIST with 6p (2.75, 0.1100188) are presented in Figure
10
F2 Language Tasks
Training dynamics and test accuracies of Fed-SGM with ADAM, Fed-SGM with GD, De-FedAvg and its Adam variant finetuning Bert on SST-2 with Ep (2.45, 0.35, 0.12] are presented in Figure
Alll experiments in this section and Section 4 are conducted on a computing cluster with an AMD EPYC 7713 64-core processor and an NVIDIA A100 Tensor Core GPU, and the code is provided at http:///giiubb.com//uucm/////tgt
62

---

Test Accuracy
60%
60%
sgd-4e5
sgd-4e5
40%
sgd-no
40%
sgd-no
adam-4e5
adam-4e5
20%
adam-no
20%
adam-no
DiffSketch
Diffsketch
100
200
300
400
500
100
200
300
400
500
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 3: Vision Task: EMNIST, Ep 2.75
80%
Accuracy
Test Accuracy
60%
60%-
sgd-4e5
sgd-4e5
40%-
sgd-no
40%
adam-4e5
adam-4e5
20%
adam-no
20%
adamino
DitrSketch
DifiSketch
100
200
300
400
500
100
200
300
400
500
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 4: Vision Task: EMNIST, Ep 0.42
80%
80%
Accuracy
Test Accuracy
60%
60%
40%
sgd-no
sgd-4e5
40%
sgd-no
sgd-4e5
adam-4e5
adam-4e5
20%
adam-no
20%
adam-no
DiffSketch
DiffSketch
100
200
300
400
500
100
200
300
400
500
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 5: Vision Task: EMNIST, c, -.188
63

---

90%
85%
85%
Accuracy
Test Accuracy
80%
80%
75%
75%
4e4
4e4
70%
4e5
4e5
70%
4e6
65%
4e7
65%
100
200
300
400
500
100
200
300
400
500
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 6: Vision task: EMNIST, Ep = 1, 60, Comparison with Different Sketching Dimensions
100%
100%
95%
95%
Accuracy
90%
Test Test Accuracy
85%
80%
sgd-2e5
80%
sgd-2e5
75%
sgd-no
75%
adam-2e5
adam 2e5
70%
adam-no
70%
adam-no
100
200
300
400
500
100
200
300
400
500
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 7: Vision task: MNIST, Ep 2.75
100%
100%
95%
95%
Accuracy
90%
Test Accuracy
90%
85%
85%
80%
sgd-2e5
sgd-2e5
75%
sgd-no
sgd-no
70%
adam-2e5
adam-2e5
adam-no
70%
adam-no
65%
100
200
300
400
500
100
200
300
400
500
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 8: Vision task: MNIST, 6, = 1.60
64

---

100%
100%
90%
90%
Train Accuracy
80%
Test Accuracy
80%
70%
70%
sgd-2e5
60%
sgd-2e5
sgd-no
sgd-no
50%
adam-2e5
50%
adam-2e5
adam-no
40%
300
400
500
100
300
400
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 9: Vision task: MNIST,
0..2
100%
100%
80%
Test Accuracy
60%
Train
sgd-2e5
sgd-2e5
40%
sgd-no
sgd-no
adam-2e5
adam-2e5
adam
20%
300
400
500
100
200
300
400
500
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 10: Vision task: MNIST, 6p = 0.18
90%
80%
Test Accuracy
80%
70%
sgd-2e5
sgd-2e5
60%
sgd-no
60%
sgd-no
adam-2e5
adam-225
50%
adam-no
50%
adam-no
50
200
100
150
200
Communication
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 11: Language task, Ep 2.45
65

---

M
90%
90%
Accuracy
Test Accuracy
80%
70%-
70%
sgd-2e5
sgd-2e5
60%
sgd-no
60%
adam: 2e5
adam 2e5
50%
adam-no
50%
adam-no
200
100
150
200
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 12: Language task, ep 0.35
MMM
90%
Accuracy
80%
Test Accuracy
80%
70%
70%
sgd-2e5
sgd-2e5
sgd-no
60%
adam-Zes
adam-2e5
50%
adam-re
50%
adam-no
100
150
200
50
100
150
200
Communication Round
Communication Round
(a) Training Accuracy
(b) Test Accuracy
Figure 13: Language task, 6p 0.12
66


Reviews:
[{"review_id": "cP9w0mcwpZ", "reviewer": "Reviewer_EkNe", "summary": "This paper studies two key challenges (communication efficiency and privacy) simultaneously in FL. The paper introduces the Sketched Gaussian Mechanism, which incorporates sketching into the gaussian mechanism to achieve both communication efficiency and privacy guarantees. The authors provide a strong connection between these components and support their approach with both theoretical analysis and empirical validation.", "questions": "* Why does the performance degrade in Figure (a) when gradient sketching is not applied? Is this due to the need for a larger $\\sigma_g$ to satisfy the DP guarantee without sketching?\n\n* Why both the bounded gradient assumption and gradient clipping are used in the paper/theoretical analysis? In some adaptive FL papers, such as [1] and [2], the convergence analysis relies on the bounded stochastic gradient assumption. SGD-based FL methods typically do not require this. In my opinion, if Fed-SGM already includes a gradient clipping step for DP, the additional bounded stochastic gradient assumption is naturally satisfied, so we don't need the bounded gradient one anymore. Could the authors clarify this point? Moreover, it would be relevant to include discussions with methods designed for adaptive FL, such as [1][2].﻿\n\n[1] Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečný, J., ... & McMahan, H. B. (2020). Adaptive federated optimization\n\n[2] Wang, Y., Lin, L., & Chen, J. (2022, June). Communication-efficient adaptive federated learning.\n\n* Some other minor issues:\n\n  * The update parameter $\\theta_{t+1}$ does not match the final model output $\\theta_T$\n  * In Theorem 3.1, the summation still runs from $t=0$ to $T-1$\n  * What is $z_{c,t}$ in Algorithm 2?", "limitations": "Yes, they discussed the limitations.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The paper is well-structured, well-written, and easy to follow.\n* DP guarantee is provided, supporting the privacy claims. The paper also includes a convergence analysis.\n* I find the conclusion that “Fed-SGM usually requires a strictly lower Gaussian noise variance than the unsketched mechanism to attain the same privacy level” quite interesting, and the related analysis to support this claim is solid.\n\nWeaknesses: \n* It seems that Fed-SGM is used with Adam in the experiments, but the theoretical analysis presents results based on the global AMSGrad optimizer.\n* Does Theorem 3.1 account for the stochasticity (i.e., stochastic noise) in gradient computation? It seems that the authors assume bounded stochastic noise in their assumptions, but the term $\\sigma_s$ does not appear in Theorem 3.1.\n* I think it is not clear enough to figure out the result of DP-FedAvg.  It seems that the SGD-no and Adam-no curves in Figures 1 and 2 correspond to DP-FedAvg, but this is not made explicit and could be confusing to readers.\n* How do the authors partition the data across clients? Is the data split in an IID or non-IID manner? Given that the participation ratio is only 4 out of 625, it seems challenging to achieve good performance under heterogeneous data distributions. Moreover, the theoretical analysis does not appear to account for data heterogeneity either.\n\n* Some ablation studies are missing:\n\n  * As mentioned earlier, an ablation on data partitioning (e.g., IID vs. non-IID) would be helpful.\n  * It would also be helpful to include ablations on the clipping threshold $\\tau$ and/or the number of local steps $K$, to evaluate how these factors influence convergence behavior.", "was_revised": true, "final_justification": "After the rebuttal, I would like to maintain my positive score of 4.", "rebuttal": "We thank the reviewer for highlighting the strengths of the work. We appreciate that the reviewer found a key conclusion of the work 'quite interesting' and that the analysis to support the claim is solid. \n\nWe first address the points mentioned under **Weaknesses** and then the points under **Questions**.\n\n**Weaknesses:**\n\n**W1: AMSGrad in theory vs. Adam in experiments**\n\nThanks for highlighting the mismatch between the optimizer in experiments (Adam) and the one in our theory (AMSGrad). Below we address this point along two perspectives:\n\n1. Theoretically, AMSGrad and Adam share the same update rules of first-order momentum $m_{t}$ and second-order momentum $\\hat{v}\\_{t}$, with AMSGrad using $v_{t}=\\max(\\hat{v_{t}},v_{t-1})$. As a result, our proof for AMSGrad can be modified to get a similar bound for Adam as well—we will add relevant details.\n3. Experimentally, we have rerun our ResNet101 experiments on EMNIST using AMSGrad in addition to Adam under the same condition as Figure 1. The results demonstrate that the experiment results with AMSGrad are similar to Adam.\n\n||Sketching|Non-Sketching|\n|:-:|:-:|:-:|\n|Adam|$85.09\\\\%$|$78.60\\\\%$|\n|AMSGrad|$85.04\\\\%$|$78.10\\\\%$|\n\n---\n**W2: Accounting for stochastic noise $\\sigma_s$ in Theorem 3.1**\n\nYes, Theorem 3.1 does account for the stochasticity in gradient computation. \n\nThe reason $\\sigma_{s}$ does not appear in Theorem 3.1 is that Theorem 3.1 is an informal version (as noted in the paper), where $\\sigma_{s}$ is treated as a constant and omitted in order notation. In the formal version (Theorem E.1 in appendix), $\\sigma_{s}$ appears in the term $\\frac{\\sqrt{2}\\alpha_{2}G\\log(2T/\\delta)\\sigma_{s}}{\\sqrt{NTK}\\epsilon}$. We will make this clear in the final version. \n\n---\n**W3: Does SGD-no and Adam-no curves in Figures 1 and 2 correspond to DP-FedAvg?**\n\nApologies for lack of clarity—yes, \"SGD-no\" corresponds to DP-FedAvg. \n\nAs we noted in captions of Figures 1 and 2, each curve label has two parts: the first part, “SGD” or “Adam”, indicates the global optimizer in Algorithm 2; and the second part is either a number, denoting the sketching dimension $b$, or “no,” indicating the non‑sketching version. Consequently, “SGD‑no” corresponds to the original DP‑FedAvg method from [1], and “Adam‑no” denotes the same method with Adam substituted for SGD. We will provide a clearer exposition in the final version.\n\n[3] Zhang, Xinwei, et al. \"Understanding clipping for federated learning: Convergence and client-level differential privacy.\" ICML 2022.\n\n---\n**W4: Data partition across clients (IID vs non-IID), handling heterogeneity**\n\nFor experiment results in the paper, we used an IID split across all 625 clients. \n\nTo assess robustness under heterogeneity, we have rerun our image‐classification experiments with a non‑IID partition (using a Dirichlet distribution with concentration parameter 0.05). The table below compares test accuracy for models with and without sketching, under both SGD and AMAGrad optimizers. As expected, overall accuracy decreases under non‑IID; however, AMSGrad still outperforms SGD, and sketching methods remains competitive with non‑sketching ones.\n\n||GD, Sketching|GD, Non-Sketching|AMSGrad, Sketching|AMSGrad, Non-Sketching|\n|:-:|:-:|:-:|:-:|:-:|\n|IID|$62.98\\\\%$|$63.34\\\\%$|$85.04\\\\%$|$78.10\\\\%$|\n|Non-IID|$40.71\\\\%$|$42.31\\\\%$|$52.50\\\\%$|$51.27\\\\%$|\n\nFor theoretical analysis, according to our data setting in line 189, we optimize over a fixed, already‐sampled dataset, i.e., finite sum or empirical loss, and make no assumption that each client’s local data share the same distribution. Consequently, our convergence bounds (for empirical loss) hold equally for both homogeneous (IID) and heterogeneous (non‑IID) partitions.\n\n---\n**W5: Ablations on the clipping threshold $\\tau$ and/or the number of local steps $K$**\n\nWe have added the following groups of ablation experiments, mirroring the setup of Figure 1 (ResNet‑101 on EMNIST) and varying only the clipping threshold $\\tau$ and the number of local steps $K$:\n\n1. We compare our original setting ($\\tau = 1$) with $\\tau = 0.5$ and $\\tau = 2$, holding all other hyperparameters constant. As shown in the table below, in our current experimental setup, test accuracy increases as $\\tau$ grows, indicating that a looser clipping bound allows larger gradient norms and yields better utility under our noise regime.\n\n||GD, Sketching|GD, Non-Sketching|AMSGrad, Sketching|AMSGrad, Non-Sketching|\n|:-:|:-:|:-:|:-:|:-:|\n|$\\tau=0.5$|$62.91\\\\%$|$62.89\\\\%$|$84.97\\\\%$|$78.06\\\\%$|\n|$\\tau=1$|$62.98\\\\%$|$63.34\\\\%$|$85.04\\\\%$|$78.10\\\\%$ |\n|$\\tau=2$|$63.18\\\\%$|$63.57\\\\%$|$85.26\\\\%$|$78.23\\\\%$|\n\n2. We compare our original setting ($K = 18$) with $K = 9$ and $K = 36$, keeping all other hyperparameters fixed. This table shows that, in our current experimental setup, increasing $K$ allows each client to perform more optimization steps, which leads to better test accuracy.\n\n||GD, Sketching|GD, Non-Sketching|AMSGrad, Sketching|AMSGrad, Non-Sketching|\n|:-:|:-:|:-:|:-:|:-:|\n|$K=9$|$56.54\\\\%$|$56.66\\\\%$|$83.81\\\\%$|$76.21\\\\%$|\n|$K=18$|$62.98\\\\%$|$63.34\\\\%$|$85.04\\\\%$|$78.10\\\\%$|\n|$K=36$|$71.81\\\\%$|$72.18\\\\%$|$86.43\\\\%$|$80.61\\\\%$|\n\n---\n\nNext we answer points raised under **Questions**.\n\n**Questions:**\n\n**Q1: Reason for performance degradation without sketching; is this due to the need for a larger $\\sigma_{g}$ to satisfy the DP guarantee without sketching?**\n\nYes, without sketching, we need larger $\\sigma_g$ to satisfy DP which degrades the performance. \n\nAs discussed in the first point starting from line 310 in the paper, gradient sketching reduces per‑round Gaussian noise for privacy in 2 ways:\n1. **Reduced noise dimensionality:** Instead of adding noise in the original $d$‑dimensions, sketching projects each update to a $b$‑dimensional space with $b\\ll d$, so that every round incurs only $b$‑dimensional noise. In our experiments, we set $b = 0.01~d$.\n2. **Lowered per‑dimension noise variance:** Within an appropriate range of $b$, our privacy analysis (Theorem 3.1) far smaller variance noise suffices to meet the same privacy level.In our experiments, our FedSGM needed only $\\approx 1/10$ of the noise variance used by the non‑sketching version. \n\nThese two effects sharply decrease the total noise needed by Fed-SGM to reach the same privacy level, compensating for performance loss due to the projection itself. As a result, the sketching methods achieve performance that is competitive with, and in some cases superior to, the non‑sketching baseline, as shown in Figure 1 and Figure 2.\n\n---\n**Q2: Need for both bounded gradient assumption and gradient clipping** \n\nIn analyses of private FL that incorporate gradient clipping, it is standard to also impose a uniform bound on the true stochastic gradient norm [3] [4]. \n\nThis assumption serves a crucial purpose: by ensuring every gradient lies within a known radius $G$ _before clipping_, it guarantees that clipping introduces only bounded bias rather than uncontrolled distortion. Without this bound, one could not rule out arbitrarily large clipping errors.\n\nIn our analysis, Theorem 3.1 in Section 3.2.2 decomposes convergence error into 3 terms; the term $E_{c}^{\\text{AMSGrad}}$ captures the bias due to clipping. Controlling $E_{c}^{\\text{AMSGrad}}$ relies directly on the bound $G$ from Assumption 2, as noted in Remark 3.3.\n\n[3] Zhang, Xinwei, et al. \"Understanding clipping for federated learning: Convergence and client-level differential privacy.\" ICML 2022. \n\n[4] Lun Wang, et al. “D2p-fed: Differentially private federated learning with efficient communication,” arXiv:2006.13039, 2020.\n\n---\n**Q3: Include discussions with methods designed for adaptive FL, such as [1][2].**\n\n[1] Reddi, S., et al (2020). Adaptive federated optimization.\n\n[2] Wang, Y., et al (2022). Communication-efficient adaptive federated learning.\n\nThanks for the suggestion—we agree that deeper discussion of these works will strengthen the paper’s context. We will expand this discussion in the revised manuscript.\n* While FedAvg is effective in many settings, it inherits SGD’s limitations since FedAvg aggregates local SGD updates. As a result, several works have indeed adopted adaptive methods into federated learning, including [1][2][5][6]. \n* For communication-cost, server-side adaptivity imposes no extra per-round communication on clients but accelerates convergence. Combined with sketching, we get a significant reduction in overall communication cost. \n* For privacy, the choice of server optimizer does not affect the privacy guarantee, since any optimizer to the output of SGM in each round is post‑processing, hence does not alter the privacy level. \n\n[5] Tang, H., et al. \"1-bit adam: Communication efficient large-scale training with adam’s convergence speed.\" ICML, 2021.\n\n[6] Chen, C., et al. \"Efficient-adam: Communication-efficient distributed adam.\" IEEE Transactions on Signal Processing, 2023.\n\n---\n**Minor issues**\n\n**M1:** \"The update parameter $\\theta_{t+1}$ does not match the final model output $\\theta_{T}$.\"\n\nThank you for identifying the typo. We will revise the range of $t$ to run from 0 to $T-1$ to ensure proper index alignment in Algorithm 2.\n\n---\n**M2:** \"In Theorem 3.1, the summation still runs from $t=0$ to $T-1$\".\n\nOur analysis yields an upper bound on the average squared gradient norm at $\\theta_{t}$ throughout the learning process; the same bound holds when averaging over $t=0,...,T$. We will clarify this expression and ensure it is fully consistent with the notation in Algorithm 2.\n\n---\n**M3:** \"What is $\\mathbf{z}_{c,t}$ in Algorithm 2?\"\n\nPer Definition 2.1, SGM takes three inputs: the target parameter, the Gaussian projection matrix, and Gaussian noise. In Algorithm 2, $\\mathbf{z}_{c,t}$ is the third input, indicating that it corresponds to the Gaussian noise. We will clarify this in Algorithm 2’s description in a future revision."}, {"review_id": "baasnBHT3n", "reviewer": "Reviewer_q7wo", "summary": "While existing works primarily analyze the privacy guarantees of sketching and Gaussian mechanisms in isolation, this paper considers the inherent privacy benefits of the sketching operations and derives tighter privacy bounds for the combined sketched Gaussian mechanism by leveraging Rényi differential privacy. The proposed framework is applied to federated learning with both gradient descent and adaptive optimizers, demonstrating superior empirical performance.", "questions": "1. Is it possible to add comparisons with more recent works on privacy-communication-accuracy tradeoff? Comparisons from both theoretical and experimental perspectives will benefit the paper. \n2. I do not get the first equality in line 646 of Lemma C.2. Could you please clarify?", "limitations": "The authors have mentioned that the analyses are limited to isotropic Gaussian sketching matrices.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. The theoretical derivation is comprehensive and rigorously demonstrates a tighter bound on the privacy level of SGM.\n2. Beyond the theoretical analysis, the authors apply SGM to Federated Learning (FL) and conduct a thorough convergence analysis, demonstrating its performance in terms of convergence bounds.\n3. Both NLP and image classification tasks are considered in the experiments.\n\nWeakness:\n1. The derivation is quite complex, and some high-level explanations would help readers better understand and appreciate the analyses.\n2. In the experiments, the proposed method is only compared with DiffSketch (which was published in 2019) from the communication overhead perspective. Considering that there are many existing works that consider the tradeoff between privacy, communication overhead, and utility, comparisons with more recent works are expected.\n3. Some equations are not appropriately numbered.", "was_revised": true, "final_justification": "After the rebuttal, I remain positive about this paper.", "rebuttal": "We’re grateful for the reviewer’s acknowledgement of our novel tighter privacy derivation for SGM, our thorough convergence guarantees in the federated learning setting, and broad empirical validations across NLP and image classification.\n\nWe’ll address the points listed under **Weaknesses** and **Questions**.\n\n**Q1: High-level explanations to clarify the complex derivation**\n\nThank you for the suggestion. We agree that high-level explanations can help improve accessibility of the analysis. Below is a brief overview of key ideas behind our derivations.\n\n**Privacy analysis:** To clarify privacy guarantees of SGM, we include proof sketches in Section 2.2. Our goal is to analyze $(\\epsilon,\\delta)$-differential privacy (DP) of SGM using Renyi Differential Privacy (RDP) framework. According to the definition, a mechanism $\\mathcal{M}$ satisfies $(\\alpha,\\epsilon(\\alpha))$-RDP if $D_{\\alpha}(\\mathcal{M}(D)\\|\\mathcal{M}(D'))\\leq\\epsilon(\\alpha)$, where $D_{\\alpha}$ is Renyi divergence of order $\\alpha$. Leveraging the standard conversion between RDP and $(\\epsilon,\\delta)$-DP (Lemma 2.3), we focus on bounding RDP of SGM. This requires bounding Renyi divergence between output distributions under neighboring datasets $D$ and $D'$.\n\nUsing Lemma 2.1, we reduce the problem to analyzing the ratio sensitivity (Definition 2.4) and $f_{\\alpha}$ (Lemma 2.1). By bounding the ratio sensitivity and obtaining properties of $f_{\\alpha}$, we derive Lemma 2.2, which shows that the divergence is bounded by $O(1/b)$. This leads to an RDP guarantee and, via conversion, to a $(\\epsilon,\\delta)$-DP result (Lemma 2.4). Finally, applying standard tools in DP analysis, including post-processing, composition, and sub-sampling, we derive privacy guarantee for Algorithm 1 in Theorem 3.1.\n\n**Optimization guarantee:** We first analyze convergence of Fed-SGM under global GD optimizer. The second-order Taylor expansion (equation (7), line 707) splits the loss difference to two parts: a first-order term $T_{1}$ and a second-order term $T_{2}$. \n\nFor $T_{1}$, we use the update rule of $\\theta_{t}$ and isolate the contribution of clipped updates (term $S_{1}$) and that of Gaussian noise (term $S_{2}$) in equation (8), line 710. $S_{1}$ is bounded using sketching-based concentration inequalities, and $S_{2}$ via concentration bounds for Gaussian noise.\n\nFor $T_{2}$, which involves the loss Hessian matrix, we leverage the special structure of its spectrum stated in Assumption 4. This allows us to express $T_{2}$ as a sum of contributions along each eigenvector direction (equation (20), line 765). Each component is controlled similarly to $T_{1}$. Combining all these pieces yields Theorem D.1. \n\nFor Fed-SGM with AMSGrad, we follow a similar strategy, resulting in a more complicated but structurally similar bound, presented in Theorem E.1.\n\nWe hope this summary provides better intuition for underlying analyses.\n\n---\n**Q2: Theoretical and experimental comparisons with recent privacy–communication–utility tradeoff methods beyond DiffSketch.**\n\nWe extend our evaluation to DPSFL and DPSFL-AC in [1] from October 2024 which are differentially private variants of the communication-efficient FetchSGD algorithm from [2].\n\nFrom a theoretical perspective, DPSFL employs a count-sketch matrix for dimension reduction, whereas our approach uses a Gaussian sketch matrix. As shown in Theorem 2 of [1], their privacy analysis does not guarantee that the required noise variance decreases as sketching dimension grows. In contrast, our privacy result (Theorem 3.1) shows that noise variance scales down proportionally to $1/\\sqrt{b}$ with sketching dimension $b$. In their convergence analysis (Theorem 6), they restrict to single local step ($K=1$), while our analysis supports multiple local updates. Under specialized learning rate settings, both DPSFL’s Theorem 6 and our Remark 3.2 yield an $1/\\sqrt{T}$ dependence on the number of communication rounds $T$.\n\nExperimentally, we compare DPSFL and DPSFL-AC from [1] and variants of our methods under our Figure 1 setup (ResNet101 on EMNIST). According to the table, DPSFL and DPSFL-AC outperform our GD-based variants; this gap follows the fact that FetchSGD (the non-private base of DPSFL) outperforms FedAvg (the non-private base of our method) before privacy [2, Figures 3–5]. Crucially, with Adam as global optimizer, our methods, with or without sketching, surpass DPSFL and DPSFL‑AC, demonstrating that combination of Gaussian sketching and adaptive server optimization yields superior trade‑offs among privacy, communication, and accuracy.\n\n|GD, Sketching|GD, Non-Sketching|Adam, Sketching|Adam, Non-Sketching|DPSFL|DPSFL-AC|\n|:-:|:-:|:-:|:-:|:-:|:-:|\n|$62.98\\\\%$|$63.34\\\\%$|$85.09\\\\%$|$78.60\\\\%$|$70.13\\\\%$|$75.64\\\\%$|\n\n[1] Zhang, Meifan, Zhanhong Xie, and Lihua Yin. \"Private and communication-efficient federated learning based on differentially private sketches.\" arXiv preprint arXiv:2410.05733.\n\n[2] Rothchild, Daniel, et al. \"Fetchsgd: Communication-efficient federated learning with sketching.\" International Conference on Machine Learning. PMLR, 2020.\n\n---\n**Q3: Clarification of the first equality in line 646 of Lemma C.2**\n\nWe apologize for the typo: in line 646, the first term on left‑hand side of the first equation should be $\\log\\left(\\frac{\\sqrt{\\frac{\\\\|\\gamma_{t}(D')\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}}{\\sqrt{\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}}\\right)^{b}$ instead of $\\log\\left(\\frac{\\sqrt{\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}}{\\sqrt{\\frac{\\\\|\\gamma_{t}(D')\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}}\\right)^{b}$. All subsequent equations are correct starting from the second equation.\n\nNow we present the derivation of the equation. Denote $\\sigma_{1}^{2}=\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}$, $\\sigma_{2}^{2}=\\frac{\\\\|\\gamma_{t}(D')\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}$, we need to calculate Renyi divergence between $P=\\mathcal{N}(0,\\sigma_{1}^{2}\\mathbb{I}\\_{b})$ and $Q=\\mathcal{N}(0,\\sigma_{2}^{2}\\mathbb{I}\\_{b})$. According to definition of multivariate Gaussian distribution, for $x\\in\\mathbb{R}^{b}$, we can write density functions\n\\begin{align*}\n    P(x)&=(2\\pi\\sigma_{1}^{2})^{-\\frac{b}{2}}\\exp\\left(-\\frac{\\\\|x\\\\|\\_{2}^{2}}{2\\sigma_{1}^{2}}\\right),\\\\\\\\\n    Q(x)&=(2\\pi\\sigma_{2}^{2})^{-\\frac{b}{2}}\\exp\\left(-\\frac{\\\\|x\\\\|\\_{2}^{2}}{2\\sigma_{2}^{2}}\\right).\n\\end{align*}\nSo we have:\n\\begin{align*}\n    \\mathbb{E}\\_{x\\sim Q}\\left[\\left(\\frac{P(x)}{Q(x)}\\right)^{\\alpha}\\right]\n    &=\\int_{\\mathbb{R}^{b}}Q(x)\\left(\\frac{P(x)}{Q(x)}\\right)^{\\alpha}dx\\\\\\\\\n    &=\\int_{\\mathbb{R}^{b}}P(x)^{\\alpha}Q(x)^{1-\\alpha}dx\\\\\\\\\n    &=\\int_{\\mathbb{R}^{b}}\\left((2\\pi\\sigma_{1}^{2})^{-\\frac{b}{2}}\\exp\\left(-\\frac{\\\\|x\\\\|\\_{2}^{2}}{2\\sigma_{1}^{2}}\\right)\\right)^{\\alpha}\\cdot\\left((2\\pi\\sigma_{2}^{2})^{-\\frac{b}{2}}\\exp\\left(-\\frac{\\\\|x\\\\|\\_{2}^{2}}{2\\sigma_{2}^{2}}\\right)\\right)^{1-\\alpha}dx\\\\\\\\\n    &=(2\\pi\\sigma_{1}^{2})^{-\\frac{\\alpha b}{2}}(2\\pi\\sigma_{2}^{2})^{-\\frac{(1-\\alpha)b}{2}}\\int_{\\mathbb{R}^{b}}\\exp\\left(-\\frac{\\\\|x\\\\|\\_{2}^{2}}{2}\\left(\\frac{\\alpha}{\\sigma_{1}^{2}}+\\frac{1-\\alpha}{\\sigma_{2}^{2}}\\right)\\right)dx\\\\\\\\\n    &\\overset{(1)}{=}(2\\pi\\sigma_{1}^{2})^{-\\frac{\\alpha b}{2}}(2\\pi\\sigma_{2}^{2})^{-\\frac{(1-\\alpha)b}{2}}\\cdot\\left(\\frac{\\pi}{\\frac{1}{2}\\left(\\frac{\\alpha}{\\sigma_{1}^{2}}+\\frac{1-\\alpha}{\\sigma_{2}^{2}}\\right)}\\right)^{\\frac{b}{2}}\\\\\\\\\n    &=(\\alpha\\sigma_{2}^{2}+(1-\\alpha)\\sigma_{1}^{2})^{-\\frac{b}{2}}\\sigma_{2}^{\\alpha b}\\sigma_{1}^{(1-\\alpha)b}\n\\end{align*}\nin which $(1)$ uses that for every $a>0$, $\\int_{\\mathbb{R}^{b}}\\exp(-a\\\\|x\\\\|\\_{2}^{2})=(\\frac{\\pi}{a})^{\\frac{b}{2}}$. Therefore, according to Definition C.1,\n\\begin{align*}\n    D_{\\alpha}(P\\\\|Q)&=\\frac{1}{\\alpha-1}\\log\\mathbb{E}\\_{x\\sim Q}\\left[\\left(\\frac{P(x)}{Q(x)}\\right)^{\\alpha}\\right]\\\\\\\\\n    &=\\frac{1}{\\alpha-1}\\log\\left((\\alpha\\sigma_{2}^{2}+(1-\\alpha)\\sigma_{1}^{2})^{-\\frac{b}{2}}\\sigma_{2}^{\\alpha b}\\sigma_{1}^{(1-\\alpha)b}\\right)\\\\\\\\\n    &=\\frac{1}{\\alpha-1}\\left(-\\frac{1}{2}\\log(\\alpha\\sigma_{2}^{2}+(1-\\alpha)\\sigma_{1}^{2})^{b}+\\alpha\\log\\sigma_{2}^{b}+(1-\\alpha)\\log\\sigma_{1}^{b}\\right)\\\\\\\\\n    &=\\frac{1}{2(\\alpha-1)}\\left(\\log(\\sigma_{2}^{2})^{b}-\\log(\\alpha\\sigma_{2}^{2}+(1-\\alpha)\\sigma_{1}^{2})^{b}\\right)+(\\log\\sigma_{2}^{b}-\\log\\sigma_{1}^{b})\\\\\\\\\n    &=\\log\\left(\\frac{\\sigma_{2}}{\\sigma_{1}}\\right)^{b}+\\frac{1}{2(\\alpha-1)}\\log\\left(\\frac{\\sigma_{2}^{2}}{\\alpha\\sigma_{2}^{2}+(1-\\alpha)\\sigma_{1}^{2}}\\right)^{b}\\\\\\\\\n    &=\\log\\left(\\frac{\\sigma_{2}}{\\sigma_{1}}\\right)^{b}+\\frac{1}{2(\\alpha-1)}\\log\\left(\\frac{\\frac{\\sigma_{2}^{2}}{\\sigma_{1}^{2}}}{\\alpha\\frac{\\sigma_{2}^{2}}{\\sigma_{1}^{2}}+1-\\alpha}\\right)^{b}\n\\end{align*}\nSubstituting $\\sigma_{1}^{2}=\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}$ and $\\sigma_{2}^{2}=\\frac{\\\\|\\gamma_{t}(D')\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}$, we can obtain that\n\\begin{align*}\n    &D_{\\alpha}(\\mathcal{SG}(\\gamma_{t}(D);R_{t},\\xi_{t})\\\\|\\mathcal{SG}(\\gamma_{t}(D');R_{t},\\xi_{t}))\\\\\\\\\n    =&D_{\\alpha}\\left(\\mathcal{N}\\left(0,\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}\\right)\\Big\\\\|\\mathcal{N}\\left(0,\\frac{\\\\|\\gamma_{t}(D')\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}\\right)\\right)\\\\\\\\\n    =&\\log\\left(\\frac{\\sqrt{\\frac{\\\\|\\gamma_{t}(D')\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}}{\\sqrt{\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}}\\right)^{b}+\\frac{1}{2(\\alpha-1)}\\log\\left(\\frac{\\frac{\\frac{\\\\|\\gamma_{t}(D')\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}{\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}}{\\alpha\\frac{\\frac{\\\\|\\gamma_{t}(D')\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}{\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}}+1-\\alpha}\\right)^{b}.\n\\end{align*}\nwhich is exactly the first equation in line 646. We will add this part of calculation to the original proof later.\n\n---\n**Q4: Some equations are not appropriately numbered.**\n\nThank you for noting this. We will conduct a thorough review of all equation numbering and correct any inconsistencies in the revised manuscript."}, {"review_id": "IgNi9wIsQ2", "reviewer": "Reviewer_VjkF", "summary": "The paper proposes Sketched Gaussian Mechanism to provide a joint privacy analysis for both sketching and Gaussian mechanism, which results in a tighter bound while providing detailed theoretical proofs and certain experimental evaluation.", "questions": "1. Why do we only look at Renyi mechanism? What not consider zCDP?\n2. What are the justifications of fixing the experimental setups to the following: \"sampling N = 4 clients uniformly at289\nrandom in each communication round. Each selected client executes K = 18 local SGD updates290\non mini-batches of size 64, with gradient clipping threshold τ = 1.\" For the privacy part, why is the ${\\delta}_p$ fixed?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n1. The paper proposes Sketched Gaussian Mechanism to provide a joint privacy analysis for both sketching and Gaussian mechanism, which results in a tighter bound by $\\frac{1}{\\sqrt{d}}$.\n\n2. The paper includes detailed theoretical proofs for both privacy guarantee and convergence analysis.\n\n## Weaknesses\n\n1. The evaluation is limited to some datasets and specific models. Additionally, the experimental setups are fixed to one dimension. The expandability of the work is unclear. It seems like the experiment was run once, there is no indicator of statistical significance especially considering the random sampling from the Gaussian mechanism. \n\n2. The paper can benefit from a more clarified problem statement with proper background knowledge. Specifically, there is no clear introduction on Renyi DP and sketching but the paper jumped straight to the definition of SGM.\n\n3. The paper is based on the assumption that DP-based solution can solve the privacy challenge for federated learning, but in reality, DP-based solutions fall short when handling a distributed training system with small client sizes. There is no discussion on other privacy-preserving solutions including MPC, HE and hybrid of DP + cryptographic primitives.\n\n4. Minor:  \n(1) typo in Algorithm 2: \"Computer update\" -> \"Compute update\"\n(2) Equation at Line 252 is out of bound.", "was_revised": true, "final_justification": "The usage of Sketched Gaussian Mechanism in this work improves the privacy bound in federate learning by a promising margin.", "rebuttal": "We thank the reviewer for noting our Sketched Gaussian Mechanism and our rigorous proofs of both privacy guarantees and convergence.\n\nWe will respond to the problems outlined in the **Weaknesses** and **Questions** sections.\n\n**Q1: The evaluation is limited to some datasets and specific models.**\n\nWe thank the reviewer for raising concerns about breadth of our evaluation. In the paper, we report results on two different tasks：ResNet-101 on EMNIST for image classification and BERT on SST-2 for sentiment analysis。 In both cases, Adam as the global optimizer outperforms GD, while our sketching variants remain competitive with non-sketching counterparts. We believe this consistent behavior across vision and language benchmarks speaks to the generality of our approach.\n\nTo further demonstrate expandability, we add a new experiment using ResNet-50 on MNIST with privacy level $\\epsilon_{p}=1.60$. We observe the same qualitative trends: Adam yields higher accuracy than GD, and sketching incurs no significant loss relative to non-sketched baseline. These additional results reinforce that our method extend well beyond the initially reported settings.\n\n|GD, Sketching|GD, Non-Sketching|Adam, Sketching|Adam, Non-Sketching\n|:-:|:-:|:-:|:-:|\n|$82.56\\\\%$|$83.44\\\\%$|$90.26\\\\%$|$89.42\\\\%$|\n\n---\n**Q2: Experimental setups are fixed to one dimension.**\n\nWe fixed the sampling rate $N=4$, the number of local updates $K=18$, mini‑batch size 64, and clipping threshold $\\tau=1$ in order to compare the four algorithmic variants under identical system conditions, so that any observed performance gap then reflects only the choice of global optimizer (SGD vs. AMSGrad) and the presence or absence of sketching.\n\nTo verify that these relative comparisons hold more broadly, we ran additional experiments under the setting of Figure 1 (ResNet-101 on EMNIST), varying the clipping threshold $\\tau$ and the number of local steps $K$, while keeping all other settings the same. Across different values of $\\tau$ and $K$, the four variants exhibit the same pattern: AMSGrad consistently outperforms SGD as the global optimizer, and sketching‑enabled methods remain competitive with or superior to their non‑sketching counterparts.\n\n|          | GD, Sketching |   GD, Non-Sketching    |Adam, Sketching|Adam, Non-Sketching|\n|:-----------:|:---:|:----------:|:---:|:---:|\n| $\\tau=0.5$  |  $62.91\\\\%$ | $62.89\\\\%$ | $85.03\\\\%$ | $78.42\\\\%$ |\n| $\\tau=1$      |  $62.98\\\\%$ | $63.34\\\\%$  |$85.09\\\\%$ | $78.60\\\\%$ |\n| $\\tau=2$  |  $63.18\\\\%$ | $63.57\\\\%$ | $85.33\\\\%$ | $78.75\\\\%$|\n\n|          | GD, Sketching |   GD, Non-Sketching    |Adam, Sketching|Adam, Non-Sketching|\n|:-----------:|:---:|:----------:|:---:|:---:|\n| $K=9$  |  $56.54\\\\%$ | $56.66\\\\%$ | $83.63\\\\%$ | $76.57\\\\%$ |\n| $K=18$      |  $62.98\\\\%$ | $63.34\\\\%$  |$85.09\\\\%$ | $78.60\\\\%$ |\n| $K=36$  |  $71.81\\\\%$ | $72.18\\\\%$ | $86.72\\\\%$ | $81.04\\\\%$|\n\n---\n**Q3: For the privacy part, why is the $\\delta_{p}$ fixed?\"**\nWe fix the privacy failure probability $\\delta_{p}=10^{-5}$ as a constant in all of our experiments, which is standard practice in the differential‑privacy literature。 For example， both Section 4 of [1] and Section 7 of [2] likewise set $\\delta_{p}=10^{-5}$. By holding $\\delta_{p}$ at this sufficiently small value, it allows us to isolate the impact of $\\epsilon$ and our algorithmic choices without conflating changes in $\\delta_{p}$.\n\n[1] Zhang, Xinwei, et al. \"Understanding clipping for federated learning: Convergence and client-level differential privacy.\" International Conference on Machine Learning, ICML 2022.\n\n[2] Wang, Lun, Ruoxi Jia, and Dawn Song. \"D2P-Fed: Differentially private federated learning with efficient communication.\" arXiv preprint arXiv:2006.13039 (2020).\n\n---\n**Q4:** \"It seems like the experiment was run once, there is no indicator of statistical significance especially considering the random sampling from the Gaussian mechanism.\"\n\nWe thank the reviewer for pointing out the need for statistical significance. As noted in our NeurIPS Paper Checklist (line 1193), each of our core experiments was in fact repeated 5 times with independent random seeds for the Gaussian noises and sketching matrices, and the curves in the paper represent the mean performance across those 5 runs. To make this explicit, we present the following table with error bars showing the standard deviation over the five trials. These error bars demonstrate that the performance trends we report hold consistently across repetitions, thereby addressing concerns about variability due to random sampling.\n\n | GD, Sketching |   GD, Non-Sketching    | Adam, Sketching| Adam, Non-Sketching\n|:---:|:----------:|:---:|:---:|\n|$62.98\\\\%\\pm0.76\\\\%$|$63.34\\\\%\\pm0.37\\\\%$|  $85.09\\\\%\\pm0.28\\\\%$ | $78.60\\\\%\\pm0.19\\\\%$ |\n\n---\n**Q5: Clarified problem statement with proper background knowledge on Renyi DP and sketching**\n\nThank you for the suggestion. We agree that a more thorough introduction to both Renyi Differential Privacy (RDP) and sketching would improve clarity and accessibility for a broader audience. We will revise the manuscript to incorporate these foundational elements more explicitly in the main text.\n* **Renyi DP:** Renyi DP is a widely used analytical framework for differential privacy. A randomized mechanism $M$ is said to satisfy $(\\alpha,\\epsilon(\\alpha))$-RDP of order $\\alpha$ if $D_{\\alpha}(M(D)\\|M(D'))\\leq\\epsilon(\\alpha)$, where $D_{\\alpha}$ denotes the Renyi divergence of order $\\alpha$ (see Definition 2.3). RDP is particularly suitable in our setting for two main reasons. First, it has a well-established connection to $(\\epsilon,\\delta)$-DP via Lemma 2.3, allowing us to translate RDP bounds into standard privacy guarantees. Second, because both the sketching transformation and the added noise in SGM are Gaussian, the resulting mechanism remains Gaussian, enabling a closed-form and tractable analysis of the Rényi divergence. These properties make RDP a natural choice for our privacy analysis.\n* **Sketching:** Sketching is a classical technique for dimensionality reduction. Given a high-dimensional vector or matrix $X$, sketching applies a projection via a sketching matrix $S$ to produce $SX$, which resides in a lower-dimensional subspace. This reduces communication and computation while approximately preserving key geometric properties of the original data. We briefly introduce sketching in the Introduction section and provide additional applications of sketching in Related Work in appendix.\n\n---\n**Q6: Why do the authors focus exclusively on DP for federated learning without considering other privacy-preserving approaches like MPC, HE, or DP–cryptographic hybrids?**\n\nWe appreciate the reviewer’s suggestion to consider cryptographic approaches such as secure multi-party computation (MPC), homomorphic encryption (HE), and hybrid schemes that combine differential privacy (DP) with cryptographic primitives. We are aware of active line of work in this area and agree that these methods provide strong privacy guarantees at protocol level.\n\nThat said, our work is grounded in the well-established line of research that uses differential privacy (DP) as central mechanism for privacy protection in federated learning. DP-based solutions to privacy of federated learning have been extensively studied, particularly for their composability, formal guarantees, and scalability to large client populations. Notable examples include [1, 2, 3], among many others.\n\nOur focus is on improving the utility and communication efficiency of DP-based federated learning while maintaining formal privacy guarantees. If opportunity allows, we are interested in extending our techniques and analyses to hybrid approaches that incorporate cryptographic protections, and we view this as a promising direction for future work.\n\n[1] Geyer, Robin C., Tassilo Klein, and Moin Nabi. \"Differentially private federated learning: A client level perspective.\" arXiv preprint arXiv:1712.07557 (2017).\n\n[2] Zhang, Xinwei, et al. \"Understanding clipping for federated learning: Convergence and client-level differential privacy.\" International Conference on Machine Learning, ICML 2022.\n\n[3] Wang, Lun, Ruoxi Jia, and Dawn Song. \"D2P-Fed: Differentially private federated learning with efficient communication.\" arXiv preprint arXiv:2006.13039 (2020).\n\n---\n**Q7:** \"Why do we only look at Rnyi mechanism? What not consider zCDP?\"\n\nWe first recall the two definitions. A mechanism $\\mathcal{M}$ satisfies $(\\alpha,\\epsilon(\\alpha))$-RDP if $D_{\\alpha}\\left(\\mathcal{M}(D)\\|\\mathcal{M}(D')\\right)\\leq\\epsilon(\\alpha)$, where $D_{\\alpha}$ is the Renyi divergence of order $\\alpha$. By contrast, $(\\xi,\\rho)$-zCDP requires that for every $\\alpha>1$, $D_{\\alpha}\\left(\\mathcal{M}(D)\\|\\mathcal{M}(D')\\right)\\leq\\xi+\\rho\\alpha$. In other words, zCDP can be viewed as a special case of RDP in which the mechanism satisfies $(\\alpha,\\epsilon(\\alpha))$-RDP for all $\\alpha>1$, and the corresponding $\\epsilon(\\alpha)$ grows linearly with the order $\\alpha$. In our Lemma 2.4, however, we demonstrates that SGM satisfies $(\\alpha,\\epsilon(\\alpha))$-RDP with $\\epsilon(\\alpha)=\\frac{\\alpha^{2}\\tau^{4}}{(\\alpha-1)b\\sigma_{g}^{4}}$ which fails the linear growth condition of $\\epsilon(\\alpha)$ required by zCDP. Therefore, we cannot claim a zCDP guarantee for any fixed $(\\xi,\\rho)$. Instead, we work in the full RDP framework, which precisely captures the true $\\alpha$-dependence of our privacy bound.\n\n---\n**Q8:** \"Minor: typo in Algorithm 2: \"Computer update\" $\\to$ \"Compute update\".\"\n\nThank you for pointing out the typo in Algorithm 2. We will thoroughly proofread the entire manuscript and correct all typographical errors in the upcoming revision.\n\n---\n**Q8:** \"Minor: Equation at Line 252 is out of bound.\"\n\nwe will ensure that any equations exceeding the column width are reformatted either by using a smaller font size or by breaking them across multiple lines in the next revision."}, {"review_id": "eQkxf0ofFE", "reviewer": "Reviewer_5oY6", "summary": "This paper proposes the Sketched Gaussian Mechanism (SGM), an approach to jointly address communication efficiency and differential privacy (DP) in federated learning (FL). SGM combines isometric Gaussian sketching with the Gaussian mechanism for DP. The main contribution is a new privacy analysis showing that sketching itself provides DP benefits, proportional to ${b}^{-1/2}$, where $b$ is the sketching dimension. When $b$ is large enough, the established privacy bound is better than the corresponding bound with standard analysis which ignores the effect of sketching on privacy. The paper also proposes an FL algorithm incorporating SGM and provides convergence bounds including for adaptive global optimizers. It also empirically validates its effectiveness across vision and language tasks, showing competitive or better accuracy while requiring less noise.", "questions": "Please answer the questions in weaknesses.", "limitations": "Limitations have been touched upon briefly in Section 5 but more discussion is needed, especially pertaining to some of the points I mentioned in weaknesses.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** The joint analysis of sketching and differential privacy is significant and interesting (although I have some doubts which I mention in weaknesses). Its integration into FL and derivation of a high-probability convergence bound ( especially when the global optimizer is adaptive) is good. Empirically, the benefits of the proposed scheme are decent for Adam.\n\n**Weaknesses:**\n\n**1.** One thing that is not clear is why should the privacy bound decrease monotonically with $b$ -- especially when the sketching matrix $R_t$ is known globally, as is the case in Algorithm 2 ($R_t$ is used in \"Update parameter\" step). As $b$ increases and in the case when $R_t$ is known, the amount of information released (in terms of the number of noisy projections of the vector being privatized) increases, so it is not intuitively clear to me why the privacy bounds should improve. Maybe I'm missing something here, but the authors should discuss this. In particular, when $b=d$ and suppose no extra Gaussian noise is added, one should be able to retrieve the vector being sketched precisely ($R_t$ should be invertible w.h.p.). *If this is addressed properly, I can raise my score*.\n\n**2.** In Algorithm 2, in the \"Update parameter\" step, why is $R_t^\\top$ being used instead of the pseudo-inverse of $R_t$? I'd expect least squares estimate to be better(?) Is it for ease of analysis or something else? The authors should discuss this. \n\n**3.** The bound in Theorem 2.2 does not improve with $n$. Can the authors provide some discussion on the tightness of this bound? \n\n**4.** Parsing the three terms together in Theorem 3.1 is a bit hard, especially for different values of $\\tau$. I'd write the overall bound (combining the three terms) for different regimes of $\\tau$. \n\n**5.** While the authors admit that their analysis is limited to isotropic Gaussian sketching matrices, the proposed sketching method could be inefficient computationally for very large models ($d$ is very large). \n\n**6.** The values of $b$ chosen for the experiments seem somewhat arbitrary. How should one chose $b$ in practice? I didn't see discussion on this. If I missed this, please point me to it.\n\n**7.** The empirical benefits of the proposed scheme for SGD don't seem great. In particular, in Fig. 2, sketching seems to be doing worse.", "was_revised": true, "final_justification": "The authors have addressed my questions and concerns decently. Overall, I think this is a solid contribution so I decided to raise my score to 5.", "rebuttal": "We thank the reviewer for recognizing the significance of our joint sketching and differential privacy analysis, its integration into federated learning with high-probability convergence bounds for adaptive optimizers, and clear empirical benefits.\n\nWe will answer the questions in **Weaknesses** and **Questions**.\n\n**Q1: Why does the privacy guarantee get strictly stronger as the sketch dimension $b$ increases—even though releasing more noisy projections with a known $R_t$ should intuitively leak more information (up to exact recovery when $b=d$)?**\n\nThank you for this important question. We address the question in two parts.\n\n* According to a direct calculation from line 151, $\\mathcal{SG}(\\gamma_{t}(D);R_{t},\\xi_{t})\\sim\\mathcal{N}\\left(0,\\left(\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}+m\\sigma_{g}^{2}\\right)\\mathbb{I}\\_{b}\\right)$. As $b$ grows, the “signal” term $\\frac{\\\\|\\gamma_{t}(D)\\\\|\\_{2}^{2}}{b}$ vanishes and the “noise” term $m\\sigma_{g}^{2}$ dominates, making the output distribution increasingly independent of $D$. Consequently, for any two neighboring datasets $D$ and $D'$, the distributions $\\mathcal{SG}(\\gamma_{t}(D);R_{t},\\xi_{t})$ and $\\mathcal{SG}(\\gamma_{t}(D');R_{t},\\xi_{t})$ become increasingly similar, since both are essentially noise–driven. We make this rigorous in Lemma 2.2, where we show that for a fixed noise multiplier $\\sigma_{g}/\\tau$, the $\\alpha$-Renyi divergence between these two distributions is bounded by $\\frac{\\alpha^{2}\\tau^{4}}{(\\alpha-1)b\\sigma_{g}^{4}}$, so that larger $b$ strictly decreases the divergence. Therefore, increasing $b$ makes it ever harder to distinguish which dataset produced the sketch, which implies a higher privacy level.\n* Recall that for a given (gradient) vector $g$, SGM produces $\\tilde{g}=Rg+\\xi$, so just doing $R^\\top\\tilde{g}$ (or $R^\\dagger\\tilde{g}$) to recover $g$ will not work due to the added noise $\\xi$. In fact, our privacy-amplification result hinges critically on the presence of strictly positive Gaussian noise variance $\\sigma_g^2$ for $\\xi$. As shown in Theorem 3.1, we need $\\sigma_{g}^{2}\\geq\\frac{c_{4}q\\tau^{2}\\sqrt{T}\\log(2qT/\\delta_{p})}{\\sqrt{b}\\epsilon_{p}}$. Hence, only when $\\sigma_{g}^{2}>0$ does the privacy level $\\epsilon_{p}$ decrease with $b$. In degenerate case of zero added noise with $\\sigma_{g}^{2}=0$, the bound in our Theorem 3.1 blows up and no privacy guarantee holds, and this includes the special case of $b=d$ with an invertible sketch. Thus, that added Gaussian noise is essential for any privacy-amplification effect.\n\nWe will improve the exposition to make the point clear. \n\n\n---\n**Q2: Why use $R_{t}^{\\top}$ instead of the pseudo-inverse of $R_{t}$ in the parameter update of Algorithm 2?**\n\nThank you for this insightful question. We chose to “desketch” with the transpose $R_{t}^{\\top}$ rather than the pseudo‑inverse $R_{t}^{\\dagger}$ for three closely related reasons.\n\n* Since each sketching matrix $R_t\\in\\mathbb{R}^{b\\times d}$ is drawn i.i.d. Gaussian with variance $\\frac{1}{\\sqrt{b}}$ so that $\\mathbb{E}[R_t^\\top R_t]=\\mathbb{I}\\_d$, then for any vector $g$, $\\mathbb{E}[R_t^\\top R_tg]=g$, i.e., $R_t^\\top$ can recover $g$ in expectation. Furthermore, standard concentration results imply $R_t^\\top R_t\\approx\\mathbb{I}\\_{d}$ when $b$ is in the usual Johnson–Lindenstrauss regime. Then, $(R_{t}^{\\top}R_{t})^{-1}\\approx\\mathbb{I}\\_{d}$, so $R_{t}^{\\dagger}=(R_{t}^{\\top}R_{t})^{-1}R_{t}^{\\top}\\approx R_{t}^{\\top}$, which shows that $R_t^\\top$ suffices. \n* Inverting the $d\\times d$ matrix $R_{t}^{\\top}R_{t}$ at every round would introduce significant extra computation cost. \n* In the common case where $b\\ll d$ (e.g., $b\\approx0.01d$ in our experiments), the system $R_tg = y$ is underdetermined. Even the pseudo-inverse $R_{t}^{\\dagger}$ recovers only the projection of $g$ onto the row space of $R_t$, losing the complementary subspace. Hence, any desketching operator—whether transpose or pseudo-inverse—cannot recover the unencoded information.\n\nThis was an excellent question----we will add a discussion to make the point clear.\n\n---\n**Q3: The bound in Theorem 2.2 does not improve with $n$.**\n\nThe bound in Theorem 2.2 does, in fact, exhibit improvement with respect to the number of clients $n$, though this dependency is implicit. Specifically, the bound is given by $\\sigma_{g}^{2}\\geq\\frac{c_{4}q\\tau^{2}\\sqrt{T}\\log(2qT/\\delta_{p})}{\\sqrt{b}\\epsilon_{p}}$, where $q=\\frac{m}{n}$ represents the per‑round sampling ratio, with $m$ being batch size and $n$ being total sample size. It is evident from this formulation that, when all other parameters are held fixed, the bound decreases monotonically as $n$ increases. In this sense, the bound improves with a larger sample population $n$.\n\n---\n**Q4: Bound in Theorem 3.1 separately for each regime of τ to make it easier to parse.**\n\nThank you for the suggestion on Theorem 3.1. We agree that clarifying how three components interact—especially with respect to clipping threshold $\\tau$—will improve exposition. \n\nWe present the bound in the two regimes of $\\tau$:\n\n1. When $\\tau\\leq KG$: In this regime, clipping may be active, and $\\tau$ acts as an upper bound on the norm of each clipped update $\\Delta_{c,t}$ according to our algorithm. The bound in this case is $\\mathcal{O}\\left(\\frac{\\mathcal{L}(\\theta_0)-\\mathcal{L}^*}{\\eta TK} \\right)+\\tilde{\\mathcal{O}}\\left(\\frac{1}{\\sqrt{NT}}\\right)+\\tilde{\\mathcal{O}}(\\eta_{\\text{local}}K)+\\tilde{\\mathcal{O}}\\left(\\frac{\\tau}{\\sqrt{bT}K}\\right)+\\tilde{\\mathcal{O}}\\left(\\frac{(\\eta_{\\text{local}}+\\eta\\mathcal{I})\\tau^2}{K}\\right)+\\tilde{\\mathcal{O}}\\left(\\frac{1}{\\eta TK}\\right)+\\max\\left\\\\{0,\\frac{\\left(\\epsilon+\\tilde{\\mathcal{O}}(\\eta_{\\text{local}})\\right)G(KG-\\tau)}{K\\epsilon}\\right\\\\}+\\tilde{\\mathcal{O}}\\left(\\frac{(\\eta_{\\text{local}}+\\eta\\mathcal{I})\\sigma_g^2}{NK}\\right).$ We observe that $\\tilde{\\mathcal{O}}\\left(\\frac{\\tau}{\\sqrt{bT}K}\\right)+\\tilde{\\mathcal{O}}\\left(\\frac{(\\eta_{\\text{local}}+\\eta\\mathcal{I})\\tau^2}{K}\\right)$ in the optimization bound of sketching algorithm is monotonically increasing in $\\tau$, while $\\max\\left\\\\{0,\\frac{\\left(\\epsilon+\\widetilde{\\mathcal{O}}(\\eta_{\\text{local}})\\right)G(K G-\\tau)}{K\\epsilon}\\right\\\\}$ caused by clipping is monotonically decreasing in $\\tau$. This trade-off highlights the need for a careful choice of $\\tau$, as overly aggressive clipping threshold introduces clipping bias, while too loose a threshold amplifies optimization error of sketching algorithm.\n\n2. When $\\tau\\geq KG$: In this regime, the clipping operation becomes inactive, as all updates fall within clipping threshold $\\tau$. $KG$ effectively bounds norms of each update $\\Delta_{c,t}$, and clipping no longer influences computation. Therefore, the total bound becomes $\\mathcal{O}\\left(\\frac{\\mathcal{L}(\\theta_0)-\\mathcal{L}^*}{\\eta TK}\\right)+\\tilde{\\mathcal{O}}\\left(\\frac{1}{\\sqrt{NT}}\\right)+\\tilde{\\mathcal{O}}(\\eta_{\\text{local}}K)+\\tilde{\\mathcal{O}}\\left(\\frac{1}{\\sqrt{bT}} \\right)+\\tilde{\\mathcal{O}}\\left((\\eta_{\\text{local}}+\\eta\\mathcal{I})K\\right)+\\tilde{\\mathcal{O}}\\left(\\frac{1}{\\eta TK}\\right)+\\tilde{\\mathcal{O}}\\left(\\frac{(\\eta_{\\text{local}}+\\eta\\mathcal{I})\\sigma_g^2}{NK}\\right)$. Consequently, the bound becomes independent of $\\tau$ and remains constant as $\\tau$ increases further.\n\nWe believe this two-regime characterization offers a clearer view of how $\\tau$ affects the bound and further confirms the intuition behind its tuning.\n\n---\n**Q5: Sketching with Gaussian matrices could be inefficient computationally for large models.**\n\nWe acknowledge that isotropic Gaussian sketching adds computational cost for large $d$, due to matrix–vector operations during sketching and de-sketching at each client. Our key contribution is showing that sketching, beyond dimension reduction, also reduces the noise needed for differential privacy. Future work will extend this to more general, efficient sketching matrices like CountSketch and SRHT.\n\n---\n**Q6: Choice of $b$**\n\nAs stated in Parameter Setting in Section 4, we chose $b$ as a very small fraction of the original parameter dimension $d$ to demonstrate the practicality of sketching. For image classification experiments in Figure 1 (ResNet‑101 on EMNIST), we used a $1\\\\%$ compression rate, i.e., $b = 0.01d$, reducing the dimension from 42 million down to $4\\times10^5$. For the language task in Figure 2(BERT on SST‑2), we applied a $0.2\\\\%$ compression rate, i.e., $b=0.002d$, shrinking 100 million dimensions to $2\\times10^5$. \n\nRemarkably, despite this aggressive reduction in dimensions, the sketching‑based method remains competitive with the non‑sketching baseline and even outperforms it under certain situations.\n\n---\n**Q7: Empirical benefits of the proposed scheme for SGD**\n\nFirst, projecting each client’s gradient into a lower-dimensional subspace alters the update direction, introducing some loss relative to the original unsketched update, regardless of using vanilla SGD or adaptive optimizers. This explains why sketching-based curves in Figure 2 may lie slightly below the non-sketching baseline.\n\nStill, the sketching algorithms closely match—and sometimes exceed—the non-sketching baselines in accuracy. This stems from sketching’s dual role in reducing Gaussian noise for privacy: (1) shrinking noise dimensionality from $d$ to $b\\ll d$—with $b$ set to $0.2\\\\%$ of $d$ in Figure 2 (a 500-fold reduction); and (2) requiring significantly lower noise variance per coordinate. Theorem 3.1 shows that, for the same privacy guarantee, sketching needs smaller variance per coordinate compared to non-sketching methods (nearly one-tenth in Figure 2). These two effects drastically lower total noise, offsetting the projection-induced error.\n\nFinally, this holds under extreme sketching compression rates ($0.2\\\\%$), drastically reducing per-round communication. Achieving strong accuracy with such low communication highlights the scheme’s practical utility in large-scale federated learning."}]

Author rebuttal:

Meta-review: This paper introduces the Sketched Gaussian Mechanism (SGM), a novel method that combines sketching and differential privacy for Federated Learning. The paper was accepted because it makes a significant and well-validated contribution to a hot area. The reviewers liked the joint privacy analysis, leading to a tighter privacy bound than prior work, and the comprehensive theoretical and empirical validation. The authors provided a great rebuttal, including new experiments and ablation studies. This led one reviewer to raise their score, leading to unanimous support for the submission.
Decision: Accept (spotlight)