arXiv:2605.30123v1 [cs.CR] 28 May 2026
Privacy-Enhanced Zero-Order Federated Learning via xMK-CKKS over Wireless Channels Anthony Ayli
Khalil Harris
Jihad Fahs
Mohamad Assaad
Abstract—Homomorphic encryption (HE) enables privacypreserving aggregation in federated learning (FL) by allowing the server to operate on encrypted data without decryption. Existing HE-over-the-air methods mainly rely on single-key HE schemes and require channel estimation or pre-equalization to compensate for wireless fading. However, single-key HE remains vulnerable to honest-but-curious clients sharing the same secret key. In addition, compromising a single client may compromise the security of the entire network, while multi-key HE schemes provide stronger client-level security by assigning each device its own secret key. We propose a four-phase protocol that enables xMK-CKKS, a famous multi-key HE scheme, aggregation over a shared wireless channel without channel estimation. The protocol retransmits partial public keys and ciphertexts through the same channel realization, so that the dominant large-modulus encryption terms cancel algebraically during decryption. We integrate this protocol with zero-order FL over slowly varying LoS-dominant channels, where each device transmits a single encrypted scalar per round and the communication/encryption overhead is independent of the model dimension. √ We prove that the decoded encryption noise preserves the O(1/ K) convergence rate up to a negligible noise floor. The protocol is secure against an honest-but-curious server colluding with up to N − 1 clients, and numerical results on MNIST validate the analysis.
I. I NTRODUCTION Federated learning (FL) [1] enables edge devices to collaboratively train a shared model without sharing their local data. However, the model updates, gradients, or gradient surrogates transmitted by the devices may still reveal sensitive information and remain vulnerable to inference attacks [2]. Over-the-air computation [3] and zero-order (ZO) gradient estimation [4], [5] reduce the uplink communication cost by exploiting the superposition property of the wireless channel. In particular, ZO FL methods [4]–[6] can reduce the per-device communication load to one or two scalars per round, with one scalar sufficing when the channel has a non-zero mean. Nevertheless, these analog transmissions are unencrypted and therefore do not provide cryptographic protection. Homomorphic encryption (HE) offers a natural mechanism for privacy-preserving aggregation, since it allows the server to perform computations directly on encrypted data. Existing HE-over-the-air methods [7], [8] combine singlekey HE with over-the-air aggregation but rely on channel estimation, pre-equalization, or beamforming to compensate for wireless fading. While single-key HE architectures rely on a shared decryption domain among clients, an honestbut-curious (HBC) client possessing the shared secret key may decrypt or infer other clients’ updates, even if the HE
scheme remains secure against external adversaries. Moreover, compromising a single client may compromise the security of the entire network. Multi-key HE removes these limitations by assigning each device its own secret key. In particular, xMK-CKKS [9] requires all N participating devices to contribute partial decryption shares and remains secure against collusion of up to N − 1 devices with the server. This stronger security model has been validated, for example, in medical FL deployments [10]. However, secure RLWE-based implementations of xMKCKKS require large cryptographic parameters to achieve realistic security levels. For example, the Microsoft SEAL library [11] adopts parameter sets such as (n = 4096, q ≈ 2109 ) and (n = 8192, q ≈ 2218 ) for secure CKKS deployments. This observation motivates the central question addressed in this paper: can multi-key HE be combined with over-the-air aggregation without estimating or compensating the wireless channel? We answer this question by proposing a four-phase protocol in which the partial public keys and ciphertexts are transmitted through the same channel realization. As a result, the dominant large-modulus encryption terms experience the same channel coefficients and cancel algebraically at the decryption stage. The remaining channel and encryption noise are not amplified by q; instead, they enter the learning algorithm as bounded perturbations. The proposed protocol is particularly suited to slowly varying LoS-dominant links, such as short-range indoor THz communication scenarios [12]–[14]. Such links are often highly directional and dominated by a small number of propagation paths. In fixed or low-mobility deployments, the effective channel can remain approximately constant over the short duration of the four protocol phases. The main contributions of this paper are as follows: • We propose a four-phase over-the-air protocol that enables xMK-CKKS aggregation over a shared wireless channel without channel state information (CSI) acquisition or pre-equalization. • We show that retransmitting the partial public keys and ciphertexts through the same channel realization causes the dominant q-scale encryption terms to cancel algebraically during decryption. Therefore, channel uncertainty does not appear as a q-amplified pre-equalization error. • We integrate the protocol with ZO FL over slowly varying LoS-dominant channels. Each device transmits a single encrypted scalar per round, making the communication
and encryption overhead independent of the model dimension. • We show that the residual decoded encryption noise √ preserves the O(1/ K) convergence rate up to a negligible noise floor where K is the number of rounds. The residual channel noise enters the ZO gradient estimator as an additional perturbation and is accounted for in the convergence analysis. • We show that the protocol is secure against an HBC server that colludes with up to N − 1 clients, and we validate the analysis using MNIST experiments under Gaussian-fading channel models. The key takeaway is that single-key CKKS already scales to a large modulus over the air using CSI-based beamforming [7], where the server decrypts directly. The multi-key setting is different: the large q-scale key terms cancel only through the algebraic identity between the aggregated public key and the decryption shares, which requires both to carry the same channel coefficients. Imperfect channel estimation breaks this cancellation and leaves a q-scale residual at decryption. Rather than estimating the channel, the proposed protocol transmits the partial public keys and ciphertexts through the same realization so the cancellation holds, and channel uncertainty enters as a bounded perturbation handled by the learning algorithm instead of a decryption-breaking error. The remainder of the paper is organized as follows. Section II reviews existing HE-over-the-air methods and their limitations. Sections III and IV present the system model and the proposed protocol. Section V provides the convergence analysis. Section VI presents numerical results, and Section VII concludes the paper. II. R ELATED W ORK A. HE Over the Air Two recent methods combine HE with over-the-air computation. Wang et al. [7] proposed HEAirFed, which uses singlekey CKKS: each device encrypts its full gradient vector and the server aggregates over the air using MIMO beamforming with CSI at the devices and the server. Xie et al. [8] proposed AirHE, a single-key LWE scheme that transmits ciphertext digits as nested-lattice codewords and relies on channel estimation and pre-equalization. Both show that HE can be combined with over-the-air aggregation in single-key settings, but did not address the multi-key setting of this paper, where each device keeps an independent secret key. Table I shows that the proposed protocol adopts a multi-client architecture, providing stronger resistance against honest-but-curious clients and collision-related attacks. Moreover, the scheme follows the Microsoft SEAL recommended RLWE parameters [11], using n = 4096 and n = 8192, which are considered computationally secure against practical attacks. B. Why Existing Methods Do Not Extend to xMK-CKKS Two limitations separate these methods from the setting of this paper. The first is cryptographic and holds for any modulus: both use single-key HE, so any HBC client holding
TABLE I: Comparison of HE-over-the-air methods. AirHE [8]
HEAirFed [7]
Proposed
LWE Single 9 6560 Yes Yes Scalar None Vuln.
CKKS Single 4096 230 Yes Yes (beamf.) ∇F ∈ Rd None Vuln.
xMK-CKKS Multi-key 4096, 8192 2109 , 2218 No No Scalar N −1 Secure
HE scheme Key structure RLWE dim. n Ciph. mod. q CSI required Pre-equal. Enc. payload Collusion res. HBC client
the shared key can decrypt every other client’s update. Singlekey HE protects against external adversaries but gives no client-level collusion resistance. xMK-CKKS assigns each device its own secret key and requires all devices to contribute decryption shares, which gives resistance to collusion of up to N − 1 devices with the server. The second is tied to the modulus. Single-key CKKS with beamforming scales to a large modulus without difficulty. The multi-key case is different: the large gap between the modulus q and the scaling factor Λ means any residual channelestimation error is multiplied by the q-scale ciphertext terms and buries the Λ-scale message. For example, we will show in Fig. 3 of Section VI (Numerical Results) that both zero-forcing and MMSE pre-equalization diverge from the first iteration at q ≈ 2110 . To overcome this limitation, the proposed protocol retransmits the partial public keys and ciphertexts through the same channel realization, allowing the q-scaled terms to cancel algebraically while only small encryption and channel noise terms remain. III. S YSTEM M ODEL Throughout, i, j ∈ {1, . . . , N } index the devices and k ∈ {0, . . . , K} the communication rounds. A. Federated Learning Consider an FL framework with N edge devices and a central server coordinating the training of a global model θ ∈ Rd over a wireless network. Each device trains on its private local dataset. Let N = {1, . . . , N } denote the set of devices, and let Fi : Rd → R be the loss function associated with the data stored at device i. The global objective is to minimize F (θ) =
N X
Fi (θ),
Fi (θ) = Eξi ∼Di [fi (θ, ξi )] ,
(1)
i=1
where ξi is sampled from the local data distribution Di . The functions F , Fi , and fi are allowed to be nonconvex. B. Channel Model Let hi,k denote the channel coefficient between device i and the server during communication round k. We consider slowly varying block-fading channels with a nonzero mean due to a LoS component: E[hi,k ] = µi ̸= 0,
E[h2i,k ] = Ωi ,
1 ≤ i ≤ N.
(2)
The channel coefficients are assumed to be independent, not necessarily identically distributed across devices. Within each round k, hi,k remains constant per device i over all the protocol phases. Thus, each round corresponds to one fading block, whereas independent fading is assumed from one round to the next. This model is motivated by short-range indoor THz links with fixed or low-mobility devices. Such links are often LoSdominant and highly directional, with sparse multipath and high Rician K-factors. When the transmitter, receiver, and dominant scatterers remain stationary over the duration of a communication round, the coherence time can cover all phases of the proposed protocol [13], [15].
recommended parameters. The xMK-CKKS scheme [9] operates over the ring Rq = Zq [X]/(X n + 1), where n denotes the polynomial ring degree (RLWE dimension) and q represents the ciphertext coefficient modulus. The encoded message uses a scaling factor Λ to balance numerical precision and noise growth. Different cryptographic components and parameters of the xMK-CKKS scheme are summarized in the steps below: • Step 1: Secret-key generation. Each device di independently samples its secret key: si ∈ {−1, 1}n .
C. Zero-Order FL We consider a ZO method in which the channel disturbance is incorporated into the learning process, in the same spirit as [4]. At each round k, every device i computes the standard two-point ZO difference of its local loss [4], [16], [17]: ∆fi,k = fi (θk + γk Φk , ξi,k ) − fi (θk − γk Φk , ξi,k ),
•
Step 2: Partial public-key generation. Each device computes a partial public key: bi = −si a + ei
mod q,
(7)
where a is a common public polynomial and (3)
where Φk = (Φ1k , . . . , Φdk )⊤ is a perturbation vector with i.i.d. entries satisfying E[(Φjk )2 ] = b1 and ∥Φk ∥ ≤ b2 , and γk is the smoothing parameter. The perturbation sequence is generated randomly and made available to all devices. In the ZO FL scheme [4], each device transmits two scalars per round, a predefined constant αi in a first minislot and ∆fi,k in a second, and the server forms the gradient estimate from the product of the two over-the-air aggregates. When the channel has a nonzero mean, E[hi,k ] = µi ̸= 0, the preamble minislot is not needed. Each device knows, or estimates, the long-term channel mean µi and transmits the single scalar ∆fi,k /µi . The server receives the over-the-air aggregate: X ∆fi,k hi,k + nk , (4) Yk = µi
ei ∼ N (0, σe2 )⊗n , •
where nk ∼ N (0, σn2 ), and broadcasts Yk to all devices. Each device then forms the ZO gradient estimate:
i=1
Thus, b̃ + a
N X
si = b̃ + aS =
where S=
ei = Eagg ,
(10)
N X
si .
(11)
i=1 •
Step 4: Encryption. Each device encrypts its plaintext mi using the aggregated public key: cti = (c0,i , c1,i ), where and
(1)
c1,i = vi a + ei •
(12)
(0)
(13)
mod q.
(14)
c0,i = vi b̃ + mi + ei ,
D. xMK-CKKS Based on current knowledge, xMK-CKKS is considered one of the most prominent and suitable HE schemes for FL scenarios, as it provides multi-key security, supports floatingpoint computations, and relies on the RLWE lattice problem, for which no practical attacks are currently known under
N X i=1
i=1
(5)
The channel coefficient hi,k is not estimated or removed; it enters the gradient estimate as a perturbation. In [4], it is shown that including the channel disturbance in the learning does not change the convergence rate, which remains of √ order O(1/ K) in nonconvex settings. In Theorem 2, we extend the analysis to the encrypted setting and show that the proposed protocol preserves √ the same rate up to an explicit noise floor, namely O(1/ K)+ρ, where ρ is negligible under the considered parameter regime.
(8)
with σe = 3.2. Step 3: Aggregated public-key construction. The partial public keys are summed to form the aggregated public key: N X bi . (9) b̃ =
i∈N
gk = Φk Yk .
(6)
Step 5: Homomorphic aggregation. The server aggregates the ciphertexts: Csum =
N X
cti = (Csum,0 , Csum,1 ).
(15)
i=1 •
Step 6: Partial decryption. Each device computes a decryption share: Di = si Csum,1 + e∗i
mod q.
(16)
•
Step 7: Collaborative reconstruction. The server combines the aggregated ciphertext and all decryption shares: Csum,0 +
N X
Di
mod q.
(17)
i=1
After expansion, the large key-dependent terms involving a cancel algebraically, leaving: N X
mi + bounded noise.
(18)
i=1
Therefore, Csum,0 +
N X
Di ≈
i=1
N X
mi .
(19)
E. Why Naive OTA xMK-CKKS Fails We now explain why directly reusing digitally generated xMK-CKKS public keys over a wireless channel fails. Suppose first that, in round k, the partial public keys are transmitted over the air through the same channel realization hi,k . The server receives N X
hi,k bi + wb,k
i=1
=−
N X
! hi,k si
i=1
a+
N X
hi,k ei + wb,k .
(20)
i=1
Define S̃k :=
N X
hi,k si ,
i=1
Ẽagg,k :=
N X
The key observation is that the cancellation identity present in Eq. (10) fails over the air because the public keys bi are aggregated once during setup, while the channel coefficients hi,k change every round. To fix this, we retransmit bi every round through the same channel realization hi,k that carries the ciphertext and decryption shares. This ensures that the cancellation identity survives in channel-weighted form. The protocol consists of four phases per round, illustrated in Fig. 1. We add the following assumption on the HE randomness. Assumption 1. (HE randomness): The fresh randomness vi,k , e0,i,k , e1,i,k , e∗j,k and the channel noises wb,k , w0,k , w1,k , wD,k are mutually independent, zero-mean, and independent of Φk , h·,k , ξ·,k . We assume a perfect downlink: the server broadcasts b̃k , c̃1,k , and Mk to all devices without error. This is a standard assumption in over-the-air FL [3], [4].
hi,k ei + wb,k . A. Phase 1: Fresh Key Aggregation
i=1
Then the channel-weighted cancellation identity becomes b̃ota k + S̃k a = Ẽagg,k .
(21)
Therefore, the large q-scale term still cancels, provided that b̃ota and S̃k are generated through the same channel realizak tion. The failure occurs if the public keys are aggregated once during an initial setup phase and then reused in later rounds. In that case, the server holds b̃ota 0 , which is tied to the setup channel realization hi,0 , whereas the decryption shares in round k produce S̃k , which is tied to the current channel realization hi,k . The cancellation becomes b̃ota 0 + S̃k a = (S̃k − S̃0 )a + Ẽagg,0 . PN
IV. P ROPOSED P ROTOCOL
i=1
A detailed correctness analysis of the collaborative decryption procedure in xMK-CKKS is provided in Appendix A.
b̃ota k =
SEAL recommendations [11], the residual term may reach a magnitude proportional to q. By contrast, the encoded message has a scale of approximately Λ, with Λ = 240 . Thus, a q-scale residual can be roughly q/Λ ≈ 270 times larger than the encoded signal, which destroys decryption. The proposed protocol avoids this failure by retransmitting the partial public keys in every communication round, through the same channel realization that carries the encrypted scalar and the decryption shares. The proposed protocol does not try to estimate or invert the wireless channel; instead, it forces the public-key and decryption-share terms to experience the same fading coefficients, so that the largemodulus terms cancel algebraically. The complete protocol is described in the next section.
(22)
where S̃0 := i=1 hi,0 si is the channel-weighted secret from the setup round, so that b̃ota = −S̃0 a + Ẽagg,0 . The first 0 term on the right-hand side is no longer an encryption-noise term. It is a channel-mismatch residual multiplied by the public polynomial a ∈ Rq . Since the coefficients are reduced modulo q, with q ≈ 2109 or q ≈ 2218 following the Microsoft
Each client i transmits its partial public key bi over the uplink. The server receives: b̃k =
N X
hi,k bi + wb,k = −S̃k a + Ẽagg,k ,
(23)
i=1
P where S̃k P := i hi,k si is the channel-weighted secret and Ẽagg,k := i hi,k ei + wb,k . The channel-weighted cancellation identity (21) holds. B. Phase 2: Encryption The server broadcasts b̃k to all clients. Each client i encodes its ZO estimate as mi,k = ⌊Λ∆fi,k /µi ⌉ and transmits the (i) (i) ciphertext pair (c0 , c1 ): c0 = vi,k b̃k + mi,k + e0,i,k ,
(i)
(24)
(i) c1 = vi,k a + e1,i,k ,
(25)
where vi,k denotes a fresh encryption randomness, while e0,i,k and e1,i,k represent small error polynomials sampled according
OTA Aggregation
Edge Devices
Server
Device 1: sends b1 Device 2: sends b2 Device N : sends bN
Phase 1 Key Aggr.
P
b̃k =
i hi,k bi + wb,k
Receives b̃k Broadcasts b̃k to devices
broadcast b̃k
Phase 2 Encryption
Dev. 1: encrypts ∆f1,k /µi Dev. 2: encrypts ∆f2,k /µi Dev. N : encrypts ∆fN,k /µi
(c̃0,k , c̃1,k )
Device 1: sends D1 Device 2: sends D2 Device N : sends DN
P
Receives (c̃0,k , c̃1,k ) Broadcasts c̃1,k to devices broadcast c̃1,k
Phase 3 Dec. Share
D̃k =
All devices: gk = Φk Mk ,
Phase 4
j hj,k Dj + wD,k
θk+1 = θk − ηk gk
broadcast Mk
Update
Receives D̃k Recovery: M̂k = c̃0,k + D̃k b̃k + S̃k a = Ẽagg,k (q cancels) P hi,k Mk = i µi ∆fi,k + εk Broadcasts Mk to devices
Uplink (same resource, different channels) Downlink (broadcast)
Fig. 1: The proposed four-phase protocol for one round k. All devices transmit simultaneously on the same wireless resource. Each device holds its own secret key si . The server does not estimate any channel coefficient. In Phase 4, the q-scale terms cancel algebraically because b̃k and S̃k use the same channel realization hi,k . to a Gaussian distribution, as described in Section III-D. The server receives the aggregated ciphertexts over the air: X X c̃0,k = Vk b̃k + hi,k mi,k + hi,k e0,i,k + w0,k , (26) c̃1,k = Vk a +
Xi
E. Ring-Scale Cancellation
i
hi,k e1,i,k + w1,k ,
(27)
i
where Vk :=
P
i hi,k vi,k .
C. Phase 3: Decryption Share The server broadcasts c̃1,k . Each client j computes and transmits a partial decryption share Dj,k = sj c̃1,k +e∗j,k , where e∗j,k is a smudging noise. The server receives: X D̃k = S̃k c̃1,k + hj,k e∗j,k + wD,k . (28) j
D. Phase 4: Recovery The server forms M̂k := c̃0,k + D̃k . Substituting (26), (27), and (28): X M̂k = Vk b̃k + S̃k (Vk a + hi,k e1,i,k + w1,k ) + +
i X
X
hi,k mi,k +
i X
i ∗ hj,k ej,k + wD,k
X
hi,k mi,k + ε̂k
The term Vk (b̃k + S̃k a) contains two q-scale components Vk b̃k and S̃k Vk a, each ofPorder q ≈ 2109 or 2218 , far larger than the message Λ i hi,k ∆fi,k of order Λ ≈ 240 . Substituting b̃k = −S̃k a + Ẽagg,k from (23) gives Vk (b̃k + S̃k a) = Vk Ẽagg,k : the q-scale terms cancel exactly, leaving a product of two small polynomials whose second moment is P 2 of order n2 σe2 (Appendix B), independent of q. The i Ωi remaining expression is: Λ X M̂k = hi,k ∆fi,k + ε̂k , (30) µi i P where = Vk Ẽagg,k P + i hi,k e0,i,k + w0,k + P ε̂k S̃k i hi,k e1,i,k + S̃k w1,k + j hj,k e∗j,k + wD,k contains seven small noise terms. Decoding by 1/Λ: X hi,k 1 1 Mk = M̂k = ∆fi,k + εk , εk := ε̂k . (31) Λ µi Λ i F. Security of the OTA Protocol
hi,k e0,i,k + w0,k
j
= Vk (b̃k + S̃k a) +
(Proposition 1), rounding the real-valued superposition recovers the correct ring element, and the algebraic identities of Phases 1–4 hold under modular arithmetic.
(29)
i
Each ring coefficient is an integer in {0, . . . , q−1}, transmitted as an analog symbol; since ∥ε̂k ∥∞ < q/2 with high probability
Retransmitting bi every round raises the question of whether the server P can extract individual bi from the K superpositions b̃k = i hi,k bi + wb,k . The system has K observations and KN +N unknowns (channel coefficients and partial keys) and is underdetermined since the server never observes individual hi,k . Even if an adversary recovers each bi , this information is already publicly available in digital xMK-CKKS. Recovering the corresponding secret key si from bi = −si a + ei remains
computationally hard under the Ring-LWE assumption, whose security is reducible to hard lattice problems such as the Closest Vector Problem (CVP) [9]. The OTA setting therefore provides two layers of protection: the channel layer prevents the server from separating individual transmissions, while the cryptographic layer protects each bi even if it were recovered. In the digital setting only the second layer is present. G. Gradient Estimator Each device forms the gradient estimate from the broadcast Mk : ! X hi,k ∆fi,k + εk , gk = Φk Mk = Φk (32) µi i matching the structure of Eq. (5) with the channel noise nk replaced by the decoded HE noise εk . The model update is θk+1 = θk − ηk gk . H. Algorithm Algorithm 1 summarizes the main steps of the proposed encrypted EZOFL protocol over THz channels using xMKCKKS. Algorithm 1 Encrypted EZOFL over THz Channels Input: initial values θ0 , η0 , γ0 , channel mean µi 1: for k = 0, . . . , K do 2: Each device i computes ∆fi,k using its local data and encodes mi,k = ⌊Λ∆fi,k /µi ⌉. 3: Phase 1: Each device transmits bi . The server receives b̃k given in (23) and broadcasts it. (i) (i) 4: Phase 2: Each device transmits (c0 , c1 ) given in (24)– (25). The server receives (c̃0,k , c̃1,k ) and broadcasts c̃1,k . 5: Phase 3: Each device j transmits Dj,k = sj c̃1,k + e∗j,k . The server receives D̃k given in (28). 6: Phase 4: The server computes Mk given in (31) and broadcasts Mk to all devices. 7: Each device multiplies the received value by Φk to obtain gk given in (32). 8: Each device updates the model θk+1 = θk − ηk gk . 9: end for I. Encryption Overhead and Feasibility Table II presents two secure xMK-CKKS parameter sets, corresponding to n = 4096 and n = 8192, following the HE Standard [18] and Microsoft SEAL [11] recommendations, both providing an estimated 128-bit classical security level. The uplink communication per round is 4n⌈log2 q⌉ bits per device. This includes the transmission of the aggregated public (i) (i) key b̃k in Phase 1, the two ciphertext components (c0 , c1 ) in Phase 2, and the partial decryption share Di,k in Phase 3. Therefore, the transmission time per device at bandwidth B is given by 4n⌈log2 q⌉ Ttx = . B
The plaintext is represented as a floating-point value of 8 bytes. As shown in Table II, the ciphertext size increases from 109 KB for n = 4096 to 446 KB for n = 8192. This corresponds to a communication expansion of approximately 1.36 × 104 and 5.58 × 104 , respectively, compared with the plaintext size. Such an increase is expected in HE-based systems, since higher security levels require larger parameter sets and therefore larger ciphertexts. The transmission time reported in Table II corresponds to the communication performed during the first three phases of the proposed protocol described in Section IV. Therefore, increasing the security level also increases the communication overhead, which directly impacts the transmission time. At B = 1 THz, both configurations transmit in less than 8 ms, which remains well within the coherence time of static indoor THz channels, for example. Encryption and decryption-share operations have a computational complexity of O(n log n) per device per round due to the use of the NTT. In addition, the decoded noise variance scales as σ̄ε2 ∝ n/Λ2 (Appendix B), while the resulting noise floor ρ remains negligible across all parameter configurations. TABLE II: HE parameter sets and protocol overhead. n = 4096 log2 q Λ Security (HE Std.) Ciphertext size Uplink / round Ttx (B = 1 THz) Storage / device Encrypt (NTT) ρ (noise floor)
n = 8192
109 218 240 240 128-bit 128-bit 109 KB 446 KB 1.8 Mbit 7.1 Mbit 1.8 µs 7.1 µs 109 KB 446 KB O(n log n) per round ∼ 2×10−16 ∼ 4×10−16
V. C ONVERGENCE A NALYSIS We retain Assumptions 3.1–3.4 of [4]: L-smoothness and bounded Hessian ∥∇2 Fi ∥2 ≤ b (Assumption 3.1), Lipschitz continuity of fi (·, Pξi ) with constant P L (AssumptionP3.2), stepsize conditions k ηk γk = ∞, k ηk γk3 < ∞, k ηk2 γk2 < ∞ (Assumption 3.3), and perturbation vector Φk with i.i.d. entries satisfying E[(Φjk )2 ] = b1 and ∥Φk ∥ ≤ b2 (Assumption 3.4). We assume a perfect downlink: the server broadcasts b̃k , c̃1,k , and Mk to all devices without error. Let Hk = {θ0 , ξ0 , . . . , θk−1 , ξk−1 , θk } denote the history up to and including the model θk but excluding the current sample ξk , and let c1 = 2b1 and c3 = b b32 N/(2b1 ). A. Preliminary results Proposition 1. (Noise budget) Under Assumption 1 and the system model in (4), we have E[ε̂k ] = 0,
E[∥ε̂k ∥2 |Hk ] ≤ Bε2 ,
(33)
where Bε2 is given in Appendix B. The decryption correctness holds with probability greater than 1 − 4Bε2 /q 2 . The percoefficient decoded noise variance is: 2 ! PN 2 2 Ω n σ B i e i=1 . (34) σ̄ε2 := ε2 = O nΛ Λ2 Proof. See Appendix B. The noise budget dependsPon thePchannel statistics only P through the aggregate sums i Ωi , i Ω2i , and i µ4i ; For example, in the case of identical channels, Ωi = Ω for all i and Eq. (34) reduces to σ̄ε2 ≈ 6×10−17 Ω2 and σ̄ε2 ≈ 3×10−17 Ω2 for the parameter sets of Table II corresponding to n = 4096 and n = 8192 respectively. In both cases, the decoded noise variance is more than sixteen orders of magnitude below typical channel noise, so the encryption layer is invisible to the learning algorithm. Lemma 1. (Bias and second moment) Under Assumptions 3.1–3.4 and Assumption 1, E[gk |Hk ] 2
E[∥gk ∥ |Hk ]
=
c1 γk (∇F (θk ) + δk )
≤ C̃γ′ γk2 + C̃ε′ ,
(35)
with ∥δk ∥ ≤ c3 γk , c1 = 2b1 and where C̃γ′ = 4L2 b42
N X Ω
i 2 + N (N −1) µ i=1 i
,
C̃ε′ = b22 σ̄ε2 .
(36) (37)
Proof. See Appendix C. B. Asymptotic Convergence Rate Theorem 1. Under Assumptions 3.1–3.4 and Assumption 1, P if k ηk2 < ∞, then limk→∞ E[∥∇F (θk )∥2 ] = 0. Proof. The proof followsPfrom telescoping the descent inequality (58) and using k ηk γk = ∞ (Assumption 3.3); details are given in Appendix D. Theorem 2. Let ηk = η0 K −1/4 , γk = γ0 K −1/4 , where η0 , γ0 > 0. Under Assumptions 3.1–3.4 and Assumption 1, after K iterations: R min E[∥∇F (θk )∥2 ] ≤ √ + ρ, K
(38)
′
C̃ Lη0 γ0 ˆ ˆ = F (θ0 ) − F (θ ∗ ), where R = c12η∆ + c23 γ02 + γ c1 , ∆ 0 γ0 and Lb22 σ̄ε2 η0 C̃ ′ Lη0 = (39) ρ := ε c1 γ 0 2b1 γ0
is the noise floor introduced by the encryption. Furthermore, for any ϵ > ρ and β > 0, if K = R2 /(ϵβ − ρ)2 , then Pr mink=1:K ∥∇F (θk )∥2 < ϵ ≥ 1 − β. Proof. The global objective F is L-smooth by Assumption 3.1 of [4], which gives the descent inequality F (θk+1 ) ≤ F (θk ) − ηk ⟨∇F (θk ), gk ⟩ + L2 ηk2 ∥gk ∥2 .
R min E[∥∇F (θk )∥2 ] ≤ √ + ρ, k=1:K K √ where the R/ K term originates from the initial gap, the bias, and the gradient’s second moment, while the constant ρ originates from the decoded HE noise C̃ε′ . Since mink=1:K ∥∇F (θk )∥2 is nonnegative, Markov’s inequality gives, for any ϵ > ρ, 1 R 2 √ +ρ , Pr min ∥∇F (θk )∥ ≥ ϵ ≤ k=1:K ϵ K so that, taking complements, Pr(mink=1:K√∥∇F (θk )∥2 < √ 1 ϵ) ≥ 1 − ϵ (R/ K + ρ); setting 1ϵ (R/ K + ρ) = β gives K = R2 /(ϵβ − ρ)2 . The detailed proof is given in Appendix D. Theorem 2 implies that the algorithm √ converges to a neighborhood of size ρ at rate O(1/ K), where ρ = Lb22 σ̄ε2 η0 /(2b1 γ0 ). For the specific setup used in our experiments, namely the HE parameters of Table II (Λ = 240 , σe = 3.2, N = 10), identical channels with µi = µ and Ωi = Ω, and step sizes η0 = γ0 = 0.05, the decoded noise variance is σ̄ε2 ≈ 4 × 10−16 Ω2 , giving a noise floor of order ρ ≈ 10−16 . This is more than sixteen orders of magnitude below the channel noise variance σn2 , and is therefore negligible for all practical purposes. The number of iterations needed to reach mink=1:K ∥∇F (θk )∥2 < ϵ is then K ≈ R2 /(ϵβ)2 , the same as for the unencrypted algorithm. VI. N UMERICAL R ESULTS
Next, we present our main convergence results.
k=1:K
Taking E[· | Hk ], applying Lemma 1, summing over 1 ≤ k ≤ K, and substituting ηk = η0 K −1/4 and γk = γ0 K −1/4 yields
We evaluate the proposed protocol on MNIST 0-vs-1 binary classification with a logistic regression model (d = 785). The channel coefficient is hi,k ∼ N (µi , σi2 ), 1 ≤ i ≤ N , with µi = µ = 1 and σi = σ ∈ {1, 10}, giving Ωi = 1 + σ 2 ; the channel noise standard deviation is σn = 1. Step sizes are ηk = η0 (1 + k)−0.50 and γk = γ0 (1 + k)−0.25 , 1 ≤ k ≤ K, with η0 = γ0 = 0.05, batch size 128, K = 400 rounds, N = 10 devices. Fig. 2 shows the training loss under the proposed protocol for the two HE setups of Table II and the unencrypted baseline. Within each regime, the test accuracies between encrypted and unencrypted runs differ by less than 1% (Table III), confirming that the decoded HE noise σ̄ε2 ≈ 2 × 10−16 Ω2 and σ̄ε2 ≈ 4 × 10−16 Ω2 for the case n = 4096 and n = 8192 is invisible to the learning algorithm. We also compare to the CSI-based pre-equalization considered in Section III-B: each device estimates hi,k from a pilot (σpilot = 0.1, the standard deviation of the channel-estimation error) and pre-equalizes by zero-forcing or MMSE. The residual estimation error is multiplied by q at decryption, dominating the decoded gradient by a term of order q/Λ ≈ 270 . Fig. 3 confirms this: the training loss saturates near 1014 from the first iteration regardless of estimator or channel variance. Our proposed protocol avoids this by never estimating the channel.
Fig. 2: Training loss on MNIST 0-vs-1 under the proposed protocol for n ∈ {4096, 8192} and the unencrypted baseline, in both channel regimes σh ∈ {1, 10}. All four configurations converge to the same loss floor; trajectory differences result from independent channel realizations, not from encryption.
the gradient estimate is formed directly from the decrypted aggregate. The decoded HE noise introduces a noise floor that is negligible for all practical purposes. The numerical results on MNIST confirm this, and the ZO structure keeps the encrypted payload at a single scalar per device, so the encryption overhead does not grow with the model dimension d. Several directions remain open: reducing the key retransmission overhead by exploiting slow channel variation, extending the protocol to approximate block fading with controlled error, and combining HE with differential privacy where the channel noise serves as a privacy mechanism on top of the encryption layer. Fig. 3: Training loss under HE with CSI-based preequalization at q ≈ 2110 (σpilot = 0.1). Both ZF and MMSE equalization do not converge for either channel variance, since the residual estimation error is multiplied by q at decryption. TABLE III: Test accuracy on MNIST 0-vs-1 across the three HE parameter setups and the unencrypted baseline. Setup
n
log2 q
σ=1
σ = 10
A (HE) B (HE) no-enc
8192 4096 —
218 109 —
98.39% 98.39% 97.78%
93.52% 94.56% 94.33%
VII. C ONCLUSION We showed that HE and over-the-air aggregation can coexist: the additive structure of xMK-CKKS matches the wireless superposition, and the encryption noise vanishes after decoding. Among N users, each user’s device incorporates the known channel mean {µi }1≤i≤N into its encoding, and
R EFERENCES [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proc. AISTATS, ser. Proceedings of Machine Learning Research, vol. 54, 2017, pp. 1273–1282. [2] L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” in Proc. NeurIPS, 2019. [3] M. M. Amiri and D. Gündüz, “Federated learning over wireless fading channels,” IEEE Transactions on Wireless Communications, vol. 19, no. 5, pp. 3546–3557, 2020. [4] M. Assaad, Z. Nehme, and M. Debbah, “Communication-efficient zeroorder and first-order federated learning methods over wireless networks,” arXiv:2508.08013, 2025. [5] E. Mhanna and M. Assaad, “Countering the communication bottleneck in federated learning: A highly efficient zero-order optimization technique,” Journal of Machine Learning Research, vol. 25, no. 418, pp. 1–53, 2024. [6] W. Fang, Z. Yu, Y. Jiang, Y. Shi, C. N. Jones, and Y. Zhou, “Communication-efficient stochastic zeroth-order optimization for federated learning,” IEEE Transactions on Signal Processing, vol. 70, pp. 5058–5073, 2022. [7] Y. Wang, B. Zhang, J. Zhang, and C. Li, “Efficient privacy-preserving federated learning via homomorphic encryption-enabled over-the-air computation,” IEEE Transactions on Mobile Computing, vol. 24, no. 12, pp. 13 743–13 759, 2025.
[8] X. Xie, J. Hong, C. Hua, and Y. Xu, “Communication efficient ciphertext-field aggregation in wireless networks via over-the-air computation,” IEEE Transactions on Information Forensics and Security, vol. 20, pp. 31–45, 2025. [9] J. Ma, S.-A. Naas, S. Sigg, and X. Lyu, “Privacy-preserving federated learning based on multi-key homomorphic encryption,” International Journal of Intelligent Systems, vol. 37, no. 9, pp. 5880–5901, 2022. [10] I. Walskaar, M. C. Tran, and F. O. Catak, “A practical implementation of medical privacy-preserving federated learning using multi-key homomorphic encryption and flower framework,” Cryptography, vol. 7, no. 4, p. 48, 2023. [11] Microsoft Research, “Microsoft seal, release 4.1,” [Online]. Available: https://github.com/microsoft/SEAL, 2023. [12] I. F. Akyildiz, C. Han, Z. Hu, S. Nie, and J. M. Jornet, “Terahertz band communication: An old problem revisited and research directions for the next decade,” IEEE Transactions on Communications, vol. 70, no. 6, pp. 4250–4285, 2022. [13] Y. Chen, C. Han, Z. Yu, and G. Wang, “Channel measurement, characterization, and modeling for terahertz indoor communications above 200 ghz,” IEEE Transactions on Wireless Communications, vol. 23, no. 6, pp. 6518–6532, 2024. [14] J. M. Jornet, V. Petrov, H. Wang, Z. Popovic, D. Shakya, J. V. Siles, and T. S. Rappaport, “The evolution of applications, hardware design, and channel modeling for terahertz (THz) band communications and sensing: Ready for 6g?” Proceedings of the IEEE, vol. 112, no. 8, pp. 1115–1147, 2024. [15] S. Priebe and T. Kürner, “Stochastic modeling of thz indoor radio channels,” IEEE Transactions on Wireless Communications, vol. 12, no. 9, pp. 4445–4455, 2013. [16] J. C. Duchi, M. I. Jordan, M. J. Wainwright, and A. Wibisono, “Optimal rates for zero-order convex optimization: The power of two function evaluations,” IEEE Trans. Inf. Theory, vol. 61, no. 5, pp. 2788–2806, 2015. [17] A. Agarwal, O. Dekel, and L. Xiao, “Optimal algorithms for online convex optimization with multi-point bandit feedback,” in Proc. Conf. Learning Theory (COLT), 2010, pp. 28–40. [18] M. Albrecht et al., “Homomorphic encryption standard,” in Protecting Privacy through Homomorphic Encryption. Springer, 2021, pp. 31–62.
B. Encryption Each device encrypts plaintext mi as: cti = (c0,i , c1,i ), where: (0)
c0,i = vi b̃ + mi + ei , (1)
c1,i = vi a + ei . Here: • •
vi is a random masking polynomial, (0) (1) ei and ei are bounded Gaussian noise terms.
C. Homomorphic Aggregation The server computes: Csum =
cti = (Csum,0 , Csum,1 ),
i=1
with: Csum,0 =
N X
(0)
(vi b̃ + mi + ei ),
i=1
Csum,1 =
A PPENDIX A D ETAILED C ORRECTNESS V ERIFICATION OF X MK-CKKS This appendix provides a detailed derivation of the correctness of the collaborative decryption procedure in the xMKCKKS scheme and analyzes the resulting bounded noise terms.
N X
N X
(1)
(vi a + ei ).
i=1
D. Collaborative Decryption Shares Each device computes a partial decryption share: Di = si Csum,1 + e∗i ,
A. Aggregated Public Key Each device di generates a secret key si and computes its partial public key: bi = −si a + ei
where e∗i is an additional bounded masking noise. Substituting Csum,1 :
mod q, Di = si
where:
N X
(1)
(vj a + ej ) + e∗i .
j=1
a is a common public polynomial, • ei is a small RLWE error sampled from a Gaussian distribution. •
E. Server-Side Reconstruction The server reconstructs:
The aggregated public key is: b̃ =
N X
bi = −
i=1
N X
si a +
i=1
N X
ei
mod q.
Csum,0 + =
b̃ + a
N X i=1
si =
N X i=1
N N N N X X X X (0) (1) (vi b̃ + mi + ei ) + si (vj a + ej ) + e∗i , i=1
ei .
Di
i=1
i=1
Thus:
N X
i=1
j=1
where we substituted all terms to get the equality.
i=1
F. Expansion of the Aggregated Public Key
I. Correctness Result The final reconstructed value satisfies:
Using: b̃ = −
N X
sj a +
j=1
N X
ej ,
Csum,0 +
j=1
vi b̃ = −
i=1
N X N X
vi sj a +
i=1 j=1
N X N X
Csum,0 +
N X
Di = −
vi e j .
vi sj a +
i=1 j=1
N X N X
i=1
i=1 j=1
i=1 j=1
N X N X
vi sj a +
E∥pr∥2 = n2 σp2 σr2 .
i=1
N X
mi +
N N X X
N N X X
The seven terms of ε̂k from the recovery Eq. (29) are P P ε̂k = Vk Ẽagg,k + i hi,k e0,i,k + w0,k + S̃k i hi,k e1,i,k | {z } | {z } |{z} | {z }
si vj a
(A)
N X (0) ei vi e j +
+ S̃k w1,k + | {z } | (C2)
+
N X N X
(1)
si ej +
i=1 j=1
N X
e∗i .
i=1
The large key-dependent masking terms cancel algebraically: N N X X
vi sj a +
i=1 j=1
N X N X
si vj a = 0.
i=1 j=1
The remaining expression becomes:
i=1 j=1
v i ej +
N N X N N X X X (0) (1) ei + si ej + e∗i . i=1
i=1 j=1
{z
bounded RLWE noise
∗ j hj,k ej,k + wD,k ,
{z
(E)
}
(C1)
(41)
| {z } (D)
P P where Vk = i hi,k vi,k , S̃k = j hj,k sj , Ẽagg,k = P j hj,k ej + wb,k . Conditioning on h·,k and using Assumption 1, each term has zero conditional mean: P E[(A) | h·,k ] = i hi,k E[vi,k ] E[Ẽagg,k ] = 0, P E[(B1) | h·,k ] = i hi,k E[e0,i,k ] = 0, E[(B2)] = 0, P E[(C1) | h·,k ] = S̃k i hi,k E[e1,i,k ] = 0, E[(C2) | h·,k ] = S̃k E[w1,k ] = 0, E[(D)] = E[wD,k ] = 0 P E[(E) | h·,k ] = i hi,k E[e∗i,k ] = 0.
H. Bounded Noise Analysis
N X N X
(B2)
(B1)
P
i=1
i=1 j=1
i=1
|
(40)
We refer to Eq (40) as the ring product rule.
i=1 j=1
i=1 j=1
i=1
mi .
i=1
A. First Moment: E[ε̂k ] = 0
=−
−
N X
Let p, r ∈ Rq be independent zero-mean polynomials with i.i.d. coefficients of variances σp2 , σr2 . Then
Rearranging:
+
Di ≈
A PPENDIX B N OISE B UDGET
vi e j
G. Cancellation of Key-Dependent Terms
mi +
mi + bounded noise.
This establishes the correctness of collaborative decryption in xMK-CKKS.
N N X N N X X X (0) (1) mi + ei + si (vj a + ej ) + e∗i .
i=1
N X i=1
i=1 j=1
N X N X
i=1
N X
N X i=1
Csum,0 +
Thus:
=
mod q =
Hence:
N X
+
Di
i=1
we obtain:
N X
N X
i=1
}
All remaining noise terms are bounded because: the secret keys si are sampled from small distributions, the masking polynomials vi are bounded, (0) (1) ∗ • the error terms ei , ei , ei , and ei follow bounded discrete Gaussian distributions. • •
Therefore, as long as the accumulated noise magnitude remains below the CKKS decoding threshold, correct decryption is preserved.
Averaging over h·,k , we get E[ε̂k ] = 0. As ε̂k is independent of the model history, the same holds conditionally, thus yielding Proposition 1. B. Second Moment: Term-by-Term Each of the seven terms in (41) is a product of independent, zero-mean polynomials, so its second moment is computed in two stages: first, conditioning on h·,k , the ring product rule (Eq (40)) is applied to the HE and channel noises; then the expectation over h·,k is applied. For a Gaussian channel, E[h4i,k ] = 3Ω2i − 2µ4i , and by independence across clients 2 P 2 2 P P P E = + 2 i Ω2i − 2 i µ4i . (42) i hi,k i Ωi
P 4 P P 2 4 := Denote i µi , so P 2 S2Ω := 2 i Ωi , SΩ2 := i Ωi , SµP E[( i hi,k ) ] = SΩ + 2SΩ2 − 2Sµ4 and E[ i h2i,k ] = SΩ . The seven terms then evaluate to 2 2 E∥(A)∥2 = 32 n2 σe2 SΩ SΩ , + 2SΩ2 − 2Sµ4 + σw
Bias: Since hi,k is independent of (Φk , ξ·,k ) and εk is zero-mean and independent of (Φk , ξ·,k , h·,k ) (Assumption 1), and since the independence structure is unchanged given Hk , as noted after (45), taking E[·|Hk ] gives
E∥(B1)∥2 = nσe2 SΩ ,
2 E∥(B2)∥2 = nσw , 2 2 2 2 E∥(C1)∥ = n σe SΩ + 2SΩ2 − 2Sµ4 ,
2 E∥(C2)∥2 = n2 σw SΩ , 2
E∥(E)∥
E[gk |Hk ] =
= nσϕ2 SΩ .
C. Summing and Decoding
= 2
Using the triangular inequality E∥ ℓ=1 Xℓ ∥ P7 2 ℓ=1 E∥Xℓ ∥ and summing the identities in (43) gives 2 2 SΩ Bε2 = 23 n2 σe2 (SΩ + 2SΩ2 − 2Sµ4 ) + σw
=0 N X
EΦ,ξ [Φk ∆fi,k |Hk ],
(47)
i=1
≤
where the last equality uses E[hi,k ] = µi from (2). We follow the same two-point ZO argument as in [4, Appendix A-A] (a mean-value Taylor expansion of Fi (θk ± γk Φk ), we obtain
2 2 + nσe2 SΩ + nσw + n2 σe2 (SΩ + 2SΩ2 − 2Sµ4 )
(44)
The per-coefficient decoded variance is σ̄ε2 := Bε2 /(nΛ2 ). In the homogeneous case µi = µ, Ωi = Ω (SΩ = N Ω, SΩ2 = N Ω2 , Sµ4 = N µ4 ), this gives σ̄ε2 ≈ 6 × 10−17 Ω2 and σ̄ε2 ≈ 3 × 10−17 Ω2 for the parameters of II. For decryption to be correct, the CKKS decryption mechanism requires ∥ε̂k ∥∞ < q/2; otherwise, the modular reduction wraps around and the message cannot be recovered [9]. By ∥ε̂k ∥∞ ≤ ∥ε̂k ∥ and Markov’s inequality on ∥ε̂k ∥2 : Pr(∥ε̂k ∥∞ ≥ q/2) ≤ 4Bε2 /q 2 . With Bε2 from (44), which is independent of q, and q ≈ 2109 , 2218 , this probability is negligible. A PPENDIX C P ROOF OF L EMMA 1 The constants L, b, b1 , b2 are given by Assumptions 3.1– 3.4 of [4]: L is the Lipschitz constant of the gradient ∇Fi , i.e. ∥∇Fi (x) − ∇Fi (y)∥ ≤ L∥x − y∥; b is a uniform bound on the Hessian (∥∇2 Fi ∥2 ≤ b); b1 = E[(Φjk )2 ], which is a single constant because Φk has i.i.d. entries drawn from the same fixed distribution in every round, so all coordinates j share the same second moment and it does not vary with k; and b2 is a uniform upperbound on ∥Φk ∥ ≤ b2 . The derived constants are c1 = 2b1 and c3 = bb32 N/(2b1 ). Recall that the history of models and samples up to and including θk is denoted by Hk := {θ0 , ξ0 , . . . , θk−1 , ξk−1 , θk },
EΦ,ξ [Φk ∆fi,k |Hk ]
+ E[εk ] E[Φk |Hk ] | {z }
(43)
2 2 + n 2 σw SΩ + nσϕ2 SΩ + nσw .
µi
i=1
2 E∥(D)∥2 = nσw ,
P7
N X E[hi,k ]
(45)
∥E[gk |Hk ]∥ ≤ c1 γk (∥∇F (θk )∥ + c3 γk ),
(48)
which completes the proof of the first part of Lemma 1. We proceed with the proof of the second moment result. Since ∥Φk ∥ ≤ b2 , Eq (46) implies !2 X hi,k ∆fi,k + εk Hk . (49) E[∥gk ∥2 |Hk ] ≤ b22 E µ i i Expanding the square and noticing that E[εk ] = 0 and that εk is independent of (h·,k , Φk , ξ·,k ) by Assumption 1, the cross term vanishes and we get !2 X hi,k E ∆fi,k + εk Hk µ i i !2 X hi,k ∆fi,k Hk + σ̄ε2 . (50) = E µ i i For the first term, we expand the double sum and use the fact that hi,k is independent of (Φk , ξ·,k ), and hi,k , hj,k are independent for i ̸= j. We obtain !2 X hi,k E ∆fi,k Hk µ i i X X E[hi,k hj,k ] EΦ,ξ [∆fi,k ∆fj,k |Hk ] µi µj i j X Ωi X µi µj 2 = E[∆fi,k ∆fj,k |Hk ], E[(∆f ) |H ] + i,k k µ2i µi µj i
= where ξk := {ξi,k }N i=1 collects the round-k samples across devices. We note that by Assumption 3.4 of [4] and Assumption 1, the variables h·,k , Φk , ξ·,k , and the HE randomness are independent of Hk , hence conditioning on Hk preserves mutual independence. We proceed with the proof of Lemma 1. The gradient estimator is given by ! X hi,k ∆fi,k + εk . (46) gk = Φk µi i
i̸=j
(51) where we used E[h2i,k ] = Ωi and E[hi,k hj,k ] = µi µj for i ̸= j. For the diagonal terms, by the Lipschitz bound |∆fi,k | ≤ 2Lb2 γk (Assumption 3.2): E[(∆fi,k )2 |Hk ] ≤ 4L2 b22 γk2 .
(52)
For the cross terms (i ̸= j), since ξi,k and ξj,k are independent conditioned on Φk : |E[∆fi,k ∆fj,k |Hk ]| ≤ E|[∆fi,k ||∆fj,k ||Hk ] ≤ 4L2 b22 γk2 , (53) where the first inequality is due to Jensen |E[·]| ≤ E| · |, and where we used |∆fi,k | ≤ 2Lb2 γk (Assumption 3.2) to write the second inequality. Substituting (52) and (53) into (51) implies !2 X hi,k ∆fi,k Hk E µi i ≤
X Ωi i
4L2 b22 γk2 + N (N −1) 4L2 b22 γk2 µ2i
= 4L2 b22 γk2
X Ω i
i + N (N −1) µ2i
.
ˆ = F (θ0 ) − F (θ ∗ ). where ∆ P 3 ProofP of Theorem 1. By Assumption 3.3 of [4], P k η k γk < 2 2 2 ∞ and k ηk γk < ∞. The HE noise term requires k ηk < ∞, which holds for ηk = η0 (1 + k)−υ1Pwith υ1 > 1/2. The RHS of (60) is then finite. Since k ηk γk diverges by Assumption 3.3, we can show in a similar way to [4, Appendix A-C] that limk→∞ E[∥∇F (θk )∥2 ] = 0. Proof of Theorem 2. Set ηk = η = η0 K −1/4 , γk = γ = γ0 K −1/4 . Using (60) Kη0 γ0 K −1/2 min E[∥∇F (θk )∥2 ] k=1:K
ˆ C̃γ′ L 2 2 C̃ε′ L 2 1/2 2∆ + c23 η0 γ03 + η γ + η K . ≤ c1 c1 0 0 c1 0 Dividing by η0 γ0 K 1/2
(54)
min E[∥∇F (θk )∥2 ]
k=1:K
Using Eq. (54) in Eq. (49), we get
≤
E[∥gk ∥2 |Hk ] ≤ C̃γ′ γk2 + C̃ε′ ,
(55)
ˆ C̃ ′ Lη0 γ0 C̃ε′ Lη0 2∆ c2 γ 2 √ + √3 0 + γ √ + . c1 γ0 c1 η0 γ0 K K c1 K {z } | | {z } √ =O(1/ K)
where C̃γ′ := 4L2 b42
X Ω i
i
µ2i
+ N (N −1) ,
C̃ε′ := b22 σ̄ε2 ,
(56) (57)
where σ̄ε2 := Bε2 /(nΛ2 ) is defined in Appendix B-C. In the identical channles case µi = µ, Ωi = Ω, this reduces to C̃γ′ = 4N L2 b42 (Ω + (N − 1)µ2 )/µ2 . A PPENDIX D P ROOFS OF T HEOREMS 1 AND 2 By L-smoothness of F (Assumption 3.1 of [4]): L 2 η ∥gk ∥2 . 2 k Taking E[·|Hk ] and applying Lemma 1, we get F (θk+1 ) ≤ F (θk ) − ηk ⟨∇F (θk ), gk ⟩ +
(58)
K
k=0
k=0
2 X c1 X ˆ + c1 c3 ηk γk E[∥∇F (θk )∥2 ] ≤ ∆ ηk γk3 2 2
k=0
k=0
(60)
(63)
. Setting the RHS of (63)
R2 , (ϵβ − ρ)2
which completes the proof of Theorem 2.
≤ F (θk ) − c1 ηk γk ⟨∇F (θk ), ∇F (θk ) + δk ⟩ L + ηk2 (C̃γ′ γk2 + C̃ε′ ) 2 c1 c23 c1 ηk γk ∥∇F (θk )∥2 + ηk γk3 ≤ F (θk ) − 2 2 C̃γ′ L 2 2 C̃ε′ L 2 + η γ + η , (59) 2 k k 2 k where we used −⟨a, b⟩ ≤ 12 ∥a∥2 + 21 ∥b∥2 and ∥δk ∥ ≤ c3 γk in order to write Eq (59). Summing from k = 0 to K, taking full expectation over all possible history HK and using the tower property as done in [4], we obtain K
C̃ ′ Lη0 γ0
ˆ
where R = c12η∆ + c23 γ02 + γ c1 0 γ0 equal to β and solving, we get
(62)
ρ
By Markov’s inequality, for any ϵ > ρ and β > 0: 1 R √ +ρ , Pr min ∥∇F (θk )∥2 ≥ ϵ ≤ k=1:K ϵ K
K=
E[F (θk+1 )|Hk ]
K K C̃γ′ L X C̃ ′ L X 2 + ηk2 γk2 + ε ηk , 2 2
(61)