1 Introduction↩︎

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 single-key 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 honest-but-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 xMK-CKKS require large cryptographic parameters to achieve realistic security levels. For example, the Microsoft SEAL library [11] adopts parameter sets such as \((n=4096,q\approx2^{109})\) and \((n=8192,q\approx2^{218})\) 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/\sqrt{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.

2 Related Work↩︎

2.1 HE Over the Air↩︎

Two recent methods combine HE with over-the-air computation. Wang et al.[7] proposed HEAirFed, which uses single-key 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 1 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.

2.2 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 the shared key can decrypt every other client’s update. Single-key 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 \(\Lambda\) means any residual channel-estimation error is multiplied by the \(q\)-scale ciphertext terms and buries the \(\Lambda\)-scale message. For example, we will show in Fig. 4 of Section 6 (Numerical Results) that both zero-forcing and MMSE pre-equalization diverge from the first iteration at \(q \approx 2^{110}\). 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.

3 System Model↩︎

Throughout, \(i, j \in \{1,\ldots,N\}\) index the devices and \(k \in \{0,\ldots,K\}\) the communication rounds.

3.1 Federated Learning↩︎

Consider an FL framework with \(N\) edge devices and a central server coordinating the training of a global model \({\boldsymbol{\boldsymbol{\theta}}} \in \mathbb{R}^d\) over a wireless network. Each device trains on its private local dataset. Let \(\mathcal{N}=\{1,\ldots,N\}\) denote the set of devices, and let \(F_i:\mathbb{R}^d\to\mathbb{R}\) be the loss function associated with the data stored at device \(i\). The global objective is to minimize \[\label{eq:global95loss} F({\boldsymbol{\boldsymbol{\theta}}}) = \sum_{i=1}^{N} F_i({\boldsymbol{\boldsymbol{\theta}}}), \qquad F_i({\boldsymbol{\boldsymbol{\theta}}}) = \mathbb{E}_{\xi_i \sim \mathcal{D}_i} \left[ f_i({\boldsymbol{\boldsymbol{\theta}}},\xi_i) \right],\tag{1}\] where \(\xi_i\) is sampled from the local data distribution \(\mathcal{D}_i\). The functions \(F\), \(F_i\), and \(f_i\) are allowed to be nonconvex.

3.2 Channel Model↩︎

Let \(h_{i,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: \[\label{eq:channel95stats} \mathbb{E}[h_{i,k}] = \mu_i \neq 0, \qquad \mathbb{E}[h_{i,k}^2] = \Omega_i, \qquad 1 \leq i \leq N.\tag{2}\] The channel coefficients are assumed to be independent, not necessarily identically distributed across devices. Within each round \(k\), \(h_{i,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 LoS-dominant 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].

3.3 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]: \[\label{eq:delta95f} \Delta f_{i,k} = f_i({\boldsymbol{\theta}}_k+\gamma_k {\boldsymbol{\Phi}}_k,\xi_{i,k}) - f_i({\boldsymbol{\theta}}_k-\gamma_k {\boldsymbol{\Phi}}_k,\xi_{i,k}),\tag{3}\] where \({\boldsymbol{\Phi}}_k=(\Phi_k^1,\ldots,\Phi_k^d)^\top\) is a perturbation vector with i.i.d.entries satisfying \(\mathbb{E}[(\Phi_k^j)^2]=b_1\) and \(\|{\boldsymbol{\Phi}}_k\|\leq b_2\), and \(\gamma_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 \(\alpha_i\) in a first minislot and \(\Delta f_{i,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, \(\mathbb{E}[h_{i,k}]=\mu_i\neq 0\), the preamble minislot is not needed. Each device knows, or estimates, the long-term channel mean \(\mu_i\) and transmits the single scalar \(\Delta f_{i,k}/\mu_i\). The server receives the over-the-air aggregate: \[\label{eq:Y295ezofl} Y_k = \sum_{i\in\mathcal{N}} \frac{\Delta f_{i,k}}{\mu_i} h_{i,k} + n_k,\tag{4}\] where \(n_k\sim\mathcal{N}(0,\sigma_n^2)\), and broadcasts \(Y_k\) to all devices. Each device then forms the ZO gradient estimate: \[\label{eq:gk95ezofl} {\boldsymbol{g}}_k = {\boldsymbol{\Phi}}_k Y_k.\tag{5}\] The channel coefficient \(h_{i,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/\sqrt{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/\sqrt{K})+\rho\), where \(\rho\) is negligible under the considered parameter regime.

3.4 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 floating-point computations, and relies on the RLWE lattice problem, for which no practical attacks are currently known under recommended parameters.
The xMK-CKKS scheme [9] operates over the ring \[R_q=\mathbb{Z}_q[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 \(\Lambda\) 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 \(d_i\) independently samples its secret key: \[s_i \in \{-1,1\}^n.\]

• Step 2: Partial public-key generation.

  Each device computes a partial public key: \[b_i=-s_i a+e_i \mod q,\] where \(a\) is a common public polynomial and \[e_i\sim\mathcal{N}(0,\sigma_e^2)^{\otimes n},\] with \(\sigma_e=3.2\).

• Step 3: Aggregated public-key construction.

  The partial public keys are summed to form the aggregated public key: \[\tilde{b}=\sum_{i=1}^{N}b_i.\]

  Thus, \[\label{eq:cancel95digital} \tilde{b}+a\sum_{i=1}^{N}s_i = \tilde{b}+aS = \sum_{i=1}^{N}e_i = E_{agg},\tag{6}\] where \[S=\sum_{i=1}^{N}s_i.\]

• Step 4: Encryption.

  Each device encrypts its plaintext \(m_i\) using the aggregated public key: \[ct_i=(c_{0,i},c_{1,i}),\]

  where \[c_{0,i}=v_i\tilde{b}+m_i+e_i^{(0)},\]

  and \[c_{1,i}=v_i a+e_i^{(1)} \mod q.\]

• Step 5: Homomorphic aggregation.

  The server aggregates the ciphertexts: \[C_{\mathrm{sum}} = \sum_{i=1}^{N}ct_i = (C_{\mathrm{sum},0},C_{\mathrm{sum},1}).\]

• Step 6: Partial decryption.

  Each device computes a decryption share: \[D_i=s_i C_{\mathrm{sum},1}+e_i^{*}\mod q.\]

• Step 7: Collaborative reconstruction.

  The server combines the aggregated ciphertext and all decryption shares: \[C_{\mathrm{sum},0}+\sum_{i=1}^{N}D_i \mod q.\]

  After expansion, the large key-dependent terms involving \(a\) cancel algebraically, leaving: \[\sum_{i=1}^{N}m_i+\text{bounded noise}.\]

  Therefore, \[C_{\mathrm{sum},0}+\sum_{i=1}^{N}D_i \approx \sum_{i=1}^{N}m_i.\]

A detailed correctness analysis of the collaborative decryption procedure in xMK-CKKS is provided in Appendix 8.

3.5 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 \(h_{i,k}\). The server receives \[\begin{align} \tilde{b}_k^{\mathrm{ota}} &= \sum_{i=1}^N h_{i,k} b_i + w_{b,k} \nonumber\\ &= -\left(\sum_{i=1}^N h_{i,k}s_i\right)a + \sum_{i=1}^N h_{i,k}e_i + w_{b,k}. \end{align}\] Define \[\tilde{S}_k:=\sum_{i=1}^N h_{i,k}s_i, \qquad \tilde{E}_{\mathrm{agg},k} := \sum_{i=1}^N h_{i,k}e_i+w_{b,k}.\] Then the channel-weighted cancellation identity becomes \[\label{eq:cancel95ota} \tilde{b}_k^{\mathrm{ota}} + \tilde{S}_k a = \tilde{E}_{\mathrm{agg},k}.\tag{7}\] Therefore, the large \(q\)-scale term still cancels, provided that \(\tilde{b}_k^{\mathrm{ota}}\) and \(\tilde{S}_k\) are generated through the same channel realization.

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 \(\tilde{b}_0^{\mathrm{ota}}\), which is tied to the setup channel realization \(h_{i,0}\), whereas the decryption shares in round \(k\) produce \(\tilde{S}_k\), which is tied to the current channel realization \(h_{i,k}\). The cancellation becomes \[\label{eq:residual95full} \tilde{b}_0^{\mathrm{ota}} + \tilde{S}_k a = (\tilde{S}_k-\tilde{S}_0)a + \tilde{E}_{\mathrm{agg},0}.\tag{8}\] where \(\tilde{S}_0 := \sum_{i=1}^N h_{i,0}s_i\) is the channel-weighted secret from the setup round, so that \(\tilde{b}_0^{\mathrm{ota}} = -\tilde{S}_0 a + \tilde{E}_{\mathrm{agg},0}\). The first 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\in R_q\). Since the coefficients are reduced modulo \(q\), with \(q \approx 2^{109}\) or \(q \approx 2^{218}\) following the Microsoft SEAL recommendations [11], the residual term may reach a magnitude proportional to \(q\).

By contrast, the encoded message has a scale of approximately \(\Lambda\), with \(\Lambda=2^{40}\). Thus, a \(q\)-scale residual can be roughly \(q/\Lambda \approx 2^{70}\) 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 large-modulus terms cancel algebraically. The complete protocol is described in the next section.

4 Proposed Protocol↩︎

The key observation is that the cancellation identity present in Eq. 6 fails over the air because the public keys \(b_i\) are aggregated once during setup, while the channel coefficients \(h_{i,k}\) change every round. To fix this, we retransmit \(b_i\) every round through the same channel realization \(h_{i,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 \(v_{i,k}\), \(e_{0,i,k}\), \(e_{1,i,k}\), \(e_{j,k}^*\) and the channel noises \(w_{b,k}\), \(w_{0,k}\), \(w_{1,k}\), \(w_{D,k}\) are mutually independent, zero-mean, and independent of \({\boldsymbol{\Phi}}_k\), \(h_{\cdot,k}\), \(\xi_{\cdot,k}\).

We assume a perfect downlink: the server broadcasts \(\tilde{b}_k\), \(\tilde{c}_{1,k}\), and \(M_k\) to all devices without error. This is a standard assumption in over-the-air FL [3], [4].

4.1 Phase 1: Fresh Key Aggregation↩︎

Each client \(i\) transmits its partial public key \(b_i\) over the uplink. The server receives: \[\label{eq:bk} \tilde{b}_k = \sum_{i=1}^{N} h_{i,k} b_i + w_{b,k} = -\tilde{S}_k a + \tilde{E}_{\mathrm{agg},k},\tag{9}\] where \(\tilde{S}_k := \sum_i h_{i,k} s_i\) is the channel-weighted secret and \(\tilde{E}_{\mathrm{agg},k} := \sum_i h_{i,k} e_i + w_{b,k}\). The channel-weighted cancellation identity 7 holds.

4.2 Phase 2: Encryption↩︎

The server broadcasts \(\tilde{b}_k\) to all clients. Each client \(i\) encodes its ZO estimate as \(m_{i,k} = \lfloor \Lambda \Delta f_{i,k}/\mu_i \rceil\) and transmits the ciphertext pair \((c_0^{(i)}, c_1^{(i)})\): \[\begin{align} c_0^{(i)} &= v_{i,k}\tilde{b}_k + m_{i,k} + e_{0,i,k}, \tag{10}\\ c_1^{(i)} &= v_{i,k} a + e_{1,i,k}, \tag{11} \end{align}\] where \(v_{i,k}\) denotes a fresh encryption randomness, while \(e_{0,i,k}\) and \(e_{1,i,k}\) represent small error polynomials sampled according to a Gaussian distribution, as described in Section 3.4. The server receives the aggregated ciphertexts over the air: \[\begin{align} \tilde{c}_{0,k} &= V_k \tilde{b}_k + \sum_i h_{i,k} m_{i,k} + \sum_i h_{i,k} e_{0,i,k} + w_{0,k}, \tag{12}\\ \tilde{c}_{1,k} &= V_k a + \sum_i h_{i,k} e_{1,i,k} + w_{1,k}, \tag{13} \end{align}\] where \(V_k := \sum_i h_{i,k} v_{i,k}\).

4.3 Phase 3: Decryption Share↩︎

The server broadcasts \(\tilde{c}_{1,k}\). Each client \(j\) computes and transmits a partial decryption share \(D_{j,k} = s_j \tilde{c}_{1,k} + e_{j,k}^*\), where \(e_{j,k}^*\) is a smudging noise. The server receives: \[\label{eq:Dk} \tilde{D}_k = \tilde{S}_k \tilde{c}_{1,k} + \sum_j h_{j,k} e_{j,k}^* + w_{D,k}.\tag{14}\]

4.4 Phase 4: Recovery↩︎

The server forms \(\hat{M}_k := \tilde{c}_{0,k} + \tilde{D}_k\). Substituting 12 , 13 , and 14 : \[\begin{align} \hat{M}_k &= V_k \tilde{b}_k + \tilde{S}_k(V_k a + \sum_i h_{i,k} e_{1,i,k} + w_{1,k}) \notag\\ &\quad + \sum_i h_{i,k} m_{i,k} + \sum_i h_{i,k} e_{0,i,k} + w_{0,k} \notag\\ &\quad + \sum_j h_{j,k} e_{j,k}^* + w_{D,k} \notag\\ &= V_k(\tilde{b}_k + \tilde{S}_k a) + \sum_i h_{i,k} m_{i,k} + \hat{\varepsilon}_k \label{eq:Mhat95expand} \end{align}\tag{15}\] Each ring coefficient is an integer in \(\{0,\ldots,q-1\}\), transmitted as an analog symbol; since \(\|\hat{\varepsilon}_k\|_\infty < q/2\) with high probability (Proposition 1), rounding the real-valued superposition recovers the correct ring element, and the algebraic identities of Phases 1–4 hold under modular arithmetic.

4.5 Ring-Scale Cancellation↩︎

The term \(V_k(\tilde{b}_k + \tilde{S}_k a)\) contains two \(q\)-scale components \(V_k\tilde{b}_k\) and \(\tilde{S}_k V_k a\), each of order \(q \approx 2^{109}\) or \(2^{218}\), far larger than the message \(\Lambda\sum_i h_{i,k}\Delta f_{i,k}\) of order \(\Lambda \approx 2^{40}\). Substituting \(\tilde{b}_k = -\tilde{S}_k a + \tilde{E}_{\mathrm{agg},k}\) from 9 gives \(V_k(\tilde{b}_k + \tilde{S}_k a) = V_k\tilde{E}_{\mathrm{agg},k}\): the \(q\)-scale terms cancel exactly, leaving a product of two small polynomials whose second moment is of order \(n^2\sigma_e^2\big(\sum_i\Omega_i\big)^2\) (Appendix 9), independent of \(q\). The remaining expression is: \[\label{eq:Mhat95final} \hat{M}_k = \frac{\Lambda}{\mu_i} \sum_i h_{i,k} \Delta f_{i,k} + \hat{\varepsilon}_k,\tag{16}\] where \(\hat{\varepsilon}_k = V_k \tilde{E}_{\mathrm{agg},k} + \sum_i h_{i,k} e_{0,i,k} + w_{0,k} + \tilde{S}_k \sum_i h_{i,k} e_{1,i,k} + \tilde{S}_k w_{1,k} + \sum_j h_{j,k} e_{j,k}^* + w_{D,k}\) contains seven small noise terms. Decoding by \(1/\Lambda\): \[\label{eq:Mk} M_k = \frac{1}{\Lambda}\hat{M}_k = \sum_i \frac{h_{i,k}}{\mu_i} \Delta f_{i,k} + \varepsilon_k, \quad \varepsilon_k := \frac{1}{\Lambda}\hat{\varepsilon}_k.\tag{17}\]

4.6 Security of the OTA Protocol↩︎

Retransmitting \(b_i\) every round raises the question of whether the server can extract individual \(b_i\) from the \(K\) superpositions \(\tilde{b}_k = \sum_i h_{i,k} b_i + w_{b,k}\). The system has \(K\) observations and \(KN + N\) unknowns (channel coefficients and partial keys) and is underdetermined since the server never observes individual \(h_{i,k}\). Even if an adversary recovers each \(b_i\), this information is already publicly available in digital xMK-CKKS. Recovering the corresponding secret key \(s_i\) from \(b_i = -s_i a + e_i\) 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 \(b_i\) even if it were recovered. In the digital setting only the second layer is present.

4.7 Gradient Estimator↩︎

Each device forms the gradient estimate from the broadcast \(M_k\): \[\label{eq:gk95enc} {\boldsymbol{g}}_k = {\boldsymbol{\Phi}}_k \, M_k = {\boldsymbol{\Phi}}_k\left(\sum_i \frac{h_{i,k}}{\mu_i} \Delta f_{i,k} + \varepsilon_k\right),\tag{18}\] matching the structure of Eq. 5 with the channel noise \(n_k\) replaced by the decoded HE noise \(\varepsilon_k\). The model update is \({\boldsymbol{\theta}}_{k+1} = {\boldsymbol{\theta}}_k - \eta_k {\boldsymbol{g}}_k\).

4.8 Algorithm↩︎

Algorithm 2 summarizes the main steps of the proposed encrypted EZOFL protocol over THz channels using xMK-CKKS.

4.9 Encryption Overhead and Feasibility↩︎

Table 2 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\lceil\log_2 q\rceil\) bits per device. This includes the transmission of the aggregated public key \(\tilde{b}_k\) in Phase 1, the two ciphertext components \((c_0^{(i)},c_1^{(i)})\) in Phase 2, and the partial decryption share \(D_{i,k}\) in Phase 3. Therefore, the transmission time per device at bandwidth \(B\) is given by \[T_{\mathrm{tx}}=\frac{4n\lceil\log_2 q\rceil}{B}.\] The plaintext is represented as a floating-point value of \(8\) bytes. As shown in Table 2, 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\times10^4\) and \(5.58\times10^4\), 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 2 corresponds to the communication performed during the first three phases of the proposed protocol described in Section 4. 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 \(\bar{\sigma}_\varepsilon^2 \propto n/\Lambda^2\) (Appendix 9), while the resulting noise floor \(\rho\) remains negligible across all parameter configurations.

5 Convergence Analysis↩︎

We retain Assumptions 3.1–3.4 of [4]: \(L\)-smoothness and bounded Hessian \(\|\nabla^2 F_i\|_2 \leq b\) (Assumption 3.1), Lipschitz continuity of \(f_i(\cdot, \xi_i)\) with constant \(L\) (Assumption 3.2), step-size conditions \(\sum_k \eta_k\gamma_k = \infty\), \(\sum_k \eta_k\gamma_k^3 < \infty\), \(\sum_k \eta_k^2\gamma_k^2 < \infty\) (Assumption 3.3), and perturbation vector \({\boldsymbol{\Phi}}_k\) with i.i.d.entries satisfying \(\mathbb{E}[({\Phi}_k^j)^2] = b_1\) and \(\|{\boldsymbol{\Phi}}_k\| \leq b_2\) (Assumption 3.4). We assume a perfect downlink: the server broadcasts \(\tilde{b}_k\), \(\tilde{c}_{1,k}\), and \(M_k\) to all devices without error. Let \(\mathcal{H}_k = \{{\boldsymbol{\theta}}_0, \xi_0, \ldots, {\boldsymbol{\theta}}_{k-1}, \xi_{k-1}, {\boldsymbol{\theta}}_k\}\) denote the history up to and including the model \({\boldsymbol{\theta}}_k\) but excluding the current sample \(\xi_k\), and let \(c_1 = 2b_1\) and \(c_3 = b\,b_2^3 N/(2b_1)\).

5.1 Preliminary results↩︎

The noise budget depends on the channel statistics only through the aggregate sums \(\sum_i \Omega_i\), \(\sum_i \Omega_i^2\), and \(\sum_i \mu_i^4\); For example, in the case of identical channels, \(\Omega_i = \Omega\) for all \(i\) and Eq. ?? reduces to \(\bar{\sigma}_\varepsilon^2 \approx 6\times10^{-17}\,\Omega^2\) and \(\bar{\sigma}_\varepsilon^2 \approx 3\times10^{-17}\,\Omega^2\) for the parameter sets of Table 2 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.

5.2 Asymptotic Convergence Rate↩︎

Next, we present our main convergence results.

Theorem 2 implies that the algorithm converges to a neighborhood of size \(\rho\) at rate \(O(1/\sqrt{K})\), where \(\rho = Lb_2^2\bar{\sigma}_\varepsilon^2\eta_0/(2b_1\gamma_0)\). For the specific setup used in our experiments, namely the HE parameters of Table 2 (\(\Lambda=2^{40}\), \(\sigma_e=3.2\), \(N=10\)), identical channels with \(\mu_i=\mu\) and \(\Omega_i=\Omega\), and step sizes \(\eta_0=\gamma_0=0.05\), the decoded noise variance is \(\bar{\sigma}_\varepsilon^2 \approx 4 \times 10^{-16}\,\Omega^2\), giving a noise floor of order \(\rho \approx 10^{-16}\). This is more than sixteen orders of magnitude below the channel noise variance \(\sigma_n^2\), and is therefore negligible for all practical purposes. The number of iterations needed to reach \(\min_{k=1:K}\|\nabla F({\boldsymbol{\theta}}_k)\|^2 < \epsilon\) is then \(K \approx R^2/(\epsilon\beta)^2\), the same as for the unencrypted algorithm.

6 Numerical Results↩︎

We evaluate the proposed protocol on MNIST 0-vs-1 binary classification with a logistic regression model (\(d = 785\)). The channel coefficient is \(h_{i,k} \sim \mathcal{N}(\mu_i, \sigma_i^2)\), \(1 \leq i \leq N\), with \(\mu_i = \mu = 1\) and \(\sigma_i = \sigma \in \{1, 10\}\), giving \(\Omega_i = 1 + \sigma^2\); the channel noise standard deviation is \(\sigma_n = 1\). Step sizes are \(\eta_k = \eta_0(1+k)^{-0.50}\) and \(\gamma_k = \gamma_0(1+k)^{-0.25}\), \(1 \leq k \leq K\), with \(\eta_0 = \gamma_0 = 0.05\), batch size 128, \(K = 400\) rounds, \(N = 10\) devices.

Fig. 3 shows the training loss under the proposed protocol for the two HE setups of Table 2 and the unencrypted baseline. Within each regime, the test accuracies between encrypted and unencrypted runs differ by less than \(1\%\) (Table 3), confirming that the decoded HE noise \(\bar{\sigma}_\varepsilon^2 \approx 2\times 10^{-16}\,\Omega^2\) and \(\bar{\sigma}_\varepsilon^2 \approx 4 \times 10^{-16}\,\Omega^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 \(h_{i,k}\) from a pilot (\(\sigma_{\mathrm{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/\Lambda \approx 2^{70}\). Fig. 4 confirms this: the training loss saturates near \(10^{14}\) from the first iteration regardless of estimator or channel variance. Our proposed protocol avoids this by never estimating the channel.

7 Conclusion↩︎

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 \(\{\mu_i\}_{1\leq i\leq N}\) into its encoding, and 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.

8 Detailed Correctness Verification of xMK-CKKS↩︎

This appendix provides a detailed derivation of the correctness of the collaborative decryption procedure in the xMK-CKKS scheme and analyzes the resulting bounded noise terms.

8.1 Aggregated Public Key↩︎

Each device \(d_i\) generates a secret key \(s_i\) and computes its partial public key: \[b_i=-s_i a+e_i \mod q,\] where:

• \(a\) is a common public polynomial,

• \(e_i\) is a small RLWE error sampled from a Gaussian distribution.

The aggregated public key is: \[\tilde{b}=\sum_{i=1}^{N}b_i = -\sum_{i=1}^{N}s_i a + \sum_{i=1}^{N}e_i \mod q.\]

Thus: \[\tilde{b}+a\sum_{i=1}^{N}s_i = \sum_{i=1}^{N}e_i.\]

8.2 Encryption↩︎

Each device encrypts plaintext \(m_i\) as: \[ct_i=(c_{0,i},c_{1,i}),\] where: \[c_{0,i}=v_i\tilde{b}+m_i+e_i^{(0)},\] \[c_{1,i}=v_i a+e_i^{(1)}.\]

Here:

• \(v_i\) is a random masking polynomial,

• \(e_i^{(0)}\) and \(e_i^{(1)}\) are bounded Gaussian noise terms.

8.3 Homomorphic Aggregation↩︎

The server computes: \[C_{\mathrm{sum}} = \sum_{i=1}^{N}ct_i = (C_{\mathrm{sum},0},C_{\mathrm{sum},1}),\] with: \[C_{\mathrm{sum},0} = \sum_{i=1}^{N} (v_i\tilde{b}+m_i+e_i^{(0)}),\] \[C_{\mathrm{sum},1} = \sum_{i=1}^{N} (v_i a+e_i^{(1)}).\]

8.4 Collaborative Decryption Shares↩︎

Each device computes a partial decryption share: \[D_i=s_i C_{\mathrm{sum},1}+e_i^{*},\] where \(e_i^{*}\) is an additional bounded masking noise.

Substituting \(C_{\mathrm{sum},1}\): \[D_i = s_i \sum_{j=1}^{N} (v_j a+e_j^{(1)}) + e_i^{*}.\]

8.5 Server-Side Reconstruction↩︎

The server reconstructs: \[\begin{align} &C_{\mathrm{sum},0} + \sum_{i=1}^{N}D_i\\ &= \sum_{i=1}^{N} (v_i\tilde{b}+m_i+e_i^{(0)}) + \sum_{i=1}^{N} s_i \sum_{j=1}^{N} (v_j a+e_j^{(1)}) + \sum_{i=1}^{N}e_i^{*}, \end{align}\] where we substituted all terms to get the equality.

8.6 Expansion of the Aggregated Public Key↩︎

Using: \[\tilde{b} = -\sum_{j=1}^{N}s_j a + \sum_{j=1}^{N}e_j,\] we obtain: \[\sum_{i=1}^{N}v_i\tilde{b} = - \sum_{i=1}^{N}\sum_{j=1}^{N}v_i s_j a + \sum_{i=1}^{N}\sum_{j=1}^{N}v_i e_j.\]

Thus: \[C_{\mathrm{sum},0} + \sum_{i=1}^{N}D_i = - \sum_{i=1}^{N}\sum_{j=1}^{N}v_i s_j a + \sum_{i=1}^{N}\sum_{j=1}^{N}v_i e_j\] \[+ \sum_{i=1}^{N}m_i + \sum_{i=1}^{N}e_i^{(0)} + \sum_{i=1}^{N}\sum_{j=1}^{N}s_i(v_j a+e_j^{(1)}) + \sum_{i=1}^{N}e_i^{*}.\]

8.7 Cancellation of Key-Dependent Terms↩︎

Rearranging: $$=
{i=1}^{N}{j=1}^{N}v_i s_j a
+
{i=1}^{N}{j=1}^{N}s_i v_j a\[ \]+
_{i=1}^{N}m_i
+
{i=1}^{N}{j=1}^{N}v_i e_j
+
_{i=1}{N}e_i{(0)}\[ \]+
{i=1}^{N}{j=1}^{N}s_i e_j^{(1)}
+
_{i=1}{N}e_i{*}.$$

The large key-dependent masking terms cancel algebraically: \[- \sum_{i=1}^{N}\sum_{j=1}^{N}v_i s_j a + \sum_{i=1}^{N}\sum_{j=1}^{N}s_i v_j a = 0.\]

8.8 Bounded Noise Analysis↩︎

The remaining expression becomes: \[= \sum_{i=1}^{N}m_i + \underbrace{ \sum_{i=1}^{N}\sum_{j=1}^{N}v_i e_j + \sum_{i=1}^{N}e_i^{(0)} + \sum_{i=1}^{N}\sum_{j=1}^{N}s_i e_j^{(1)} + \sum_{i=1}^{N}e_i^{*} }_{\text{bounded RLWE noise}}.\]

All remaining noise terms are bounded because:

• the secret keys \(s_i\) are sampled from small distributions,

• the masking polynomials \(v_i\) are bounded,

• the error terms \(e_i\), \(e_i^{(0)}\), \(e_i^{(1)}\), and \(e_i^{*}\) follow bounded discrete Gaussian distributions.

Therefore, as long as the accumulated noise magnitude remains below the CKKS decoding threshold, correct decryption is preserved.

8.9 Correctness Result↩︎

The final reconstructed value satisfies: \[C_{\mathrm{sum},0} + \sum_{i=1}^{N}D_i \mod q = \sum_{i=1}^{N}m_i + \text{bounded noise}.\]

Hence: \[C_{\mathrm{sum},0} + \sum_{i=1}^{N}D_i \approx \sum_{i=1}^{N}m_i.\]

This establishes the correctness of collaborative decryption in xMK-CKKS.

9 Noise Budget↩︎

Let \(p, r \in R_q\) be independent zero-mean polynomials with i.i.d.coefficients of variances \(\sigma_p^2\), \(\sigma_r^2\). Then

\[\label{eq:rpr} \mathbb{E}\|pr\|^2 = n^2\sigma_p^2\sigma_r^2.\tag{19}\]

We refer to Eq 19 as the ring product rule.

9.1 First Moment: \(\mathbb{E}[\hat{\varepsilon}_k] = 0\)↩︎

The seven terms of \(\hat{\varepsilon}_k\) from the recovery Eq. 15 are \[\begin{align} \hat{\varepsilon}_k &= \underbrace{V_k\tilde{E}_{\mathrm{agg},k}}_{(A)} + \underbrace{\textstyle\sum_i h_{i,k}e_{0,i,k}}_{(B1)} + \underbrace{w_{0,k}}_{(B2)} + \underbrace{\tilde{S}_k\textstyle\sum_i h_{i,k}e_{1,i,k}}_{(C1)} \notag\\ &\quad + \underbrace{\tilde{S}_k w_{1,k}}_{(C2)} + \underbrace{\textstyle\sum_j h_{j,k}e_{j,k}^*}_{(E)} + \underbrace{w_{D,k}}_{(D)}, \label{eq:seven} \end{align}\tag{20}\] where \(V_k = \sum_i h_{i,k}v_{i,k}\), \(\tilde{S}_k = \sum_j h_{j,k}s_j\), \(\tilde{E}_{\mathrm{agg},k} = \sum_j h_{j,k}e_j + w_{b,k}\).

Conditioning on \(h_{\cdot,k}\) and using Assumption 1, each term has zero conditional mean: \[\begin{align} \mathbb{E}[(A)\mid h_{\cdot,k}] &= \Big(\textstyle\sum_i h_{i,k}\mathbb{E}[v_{i,k}]\Big)\,\mathbb{E}[\tilde{E}_{\mathrm{agg},k}] = 0, \\ \mathbb{E}[(B1)\mid h_{\cdot,k}] &= \textstyle\sum_i h_{i,k}\,\mathbb{E}[e_{0,i,k}] = 0, \quad \mathbb{E}[(B2)] = 0,\\ \mathbb{E}[(C1)\mid h_{\cdot,k}] &= \tilde{S}_k\textstyle\sum_i h_{i,k}\,\mathbb{E}[e_{1,i,k}] = 0, \\ \mathbb{E}[(C2)\mid h_{\cdot,k}] &= \tilde{S}_k\mathbb{E}[w_{1,k}] = 0, \quad \mathbb{E}[(D)] = \mathbb{E}[w_{D,k}] = 0\\ \mathbb{E}[(E)\mid h_{\cdot,k}] &= \textstyle\sum_i h_{i,k}\,\mathbb{E}[e_{i,k}^*] = 0. \end{align}\] Averaging over \(h_{\cdot,k}\), we get \(\mathbb{E}[\hat{\varepsilon}_k]=0\). As \(\hat{\varepsilon}_k\) is independent of the model history, the same holds conditionally, thus yielding Proposition 1.

9.2 Second Moment: Term-by-Term↩︎

Each of the seven terms in 20 is a product of independent, zero-mean polynomials, so its second moment is computed in two stages: first, conditioning on \(h_{\cdot,k}\), the ring product rule (Eq 19 ) is applied to the HE and channel noises; then the expectation over \(h_{\cdot,k}\) is applied. For a Gaussian channel, \(\mathbb{E}[h_{i,k}^4]=3\Omega_i^2-2\mu_i^4\), and by independence across clients \[\label{eq:ch5} \mathbb{E}\!\left[\!\Big(\textstyle\sum_i h_{i,k}^2\Big)^{\!2}\right] = \Big(\textstyle\sum_i\Omega_i\Big)^2 + 2\textstyle\sum_i\Omega_i^2 - 2\textstyle\sum_i\mu_i^4.\tag{21}\]

Denote \(S_\Omega:=\sum_i\Omega_i\), \(S_{\Omega^2}:=\sum_i\Omega_i^2\), \(S_{\mu^4}:=\sum_i\mu_i^4\), so \(\mathbb{E}[(\sum_i h_{i,k}^2)^2]=S_\Omega^2+2S_{\Omega^2}-2S_{\mu^4}\) and \(\mathbb{E}[\sum_i h_{i,k}^2]=S_\Omega\). The seven terms then evaluate to \[\begin{align} \mathbb{E}\|(A)\|^2 &= \tfrac{2}{3}n^2\!\left[\sigma_e^2\bigl(S_\Omega^2+2S_{\Omega^2}-2S_{\mu^4}\bigr)+\sigma_w^2 S_\Omega\right], \notag\\ \mathbb{E}\|(B1)\|^2 &= n\sigma_e^2 S_\Omega, \qquad \mathbb{E}\|(B2)\|^2 = n\sigma_w^2, \nonumber\\ \mathbb{E}\|(C1)\|^2 &= n^2\sigma_e^2\bigl(S_\Omega^2+2S_{\Omega^2}-2S_{\mu^4}\bigr), \notag\\ \mathbb{E}\|(C2)\|^2 &= n^2\sigma_w^2 S_\Omega, \qquad \mathbb{E}\|(D)\|^2 = n\sigma_w^2, \nonumber\\ \mathbb{E}\|(E)\|^2 &= n\sigma_\phi^2 S_\Omega. \label{eq:C195final} \end{align}\tag{22}\]

9.3 Summing and Decoding↩︎

Using the triangular inequality \(\mathbb{E}\|\sum_{\ell=1}^7 X_\ell\|^2 \leq \sum_{\ell=1}^7 \mathbb{E}\|X_\ell\|^2\) and summing the identities in 22 gives \[\begin{align} B_\varepsilon^2 &= \tfrac{2}{3}n^2\bigl(\sigma_e^2(S_\Omega^2+2S_{\Omega^2}-2S_{\mu^4})+\sigma_w^2 S_\Omega\bigr) \notag\\ &\;+ n\sigma_e^2 S_\Omega + n\sigma_w^2 + n^2\sigma_e^2(S_\Omega^2+2S_{\Omega^2}-2S_{\mu^4}) \notag\\ &\;+ n^2\sigma_w^2 S_\Omega + n\sigma_\phi^2 S_\Omega + n\sigma_w^2. \label{eq:Beps} \end{align}\tag{23}\] The per-coefficient decoded variance is \(\bar{\sigma}_\varepsilon^2 := B_\varepsilon^2/(n\Lambda^2)\). In the homogeneous case \(\mu_i=\mu\), \(\Omega_i=\Omega\) (\(S_\Omega=N\Omega\), \(S_{\Omega^2}=N\Omega^2\), \(S_{\mu^4}=N\mu^4\)), this gives \(\bar{\sigma}_\varepsilon^2 \approx 6\times10^{-17}\,\Omega^2\) and \(\bar{\sigma}_\varepsilon^2 \approx 3\times10^{-17}\,\Omega^2\) for the parameters of 2.

For decryption to be correct, the CKKS decryption mechanism requires \(\|\hat{\varepsilon}_k\|_\infty < q/2\); otherwise, the modular reduction wraps around and the message cannot be recovered [9]. By \(\|\hat{\varepsilon}_k\|_\infty \leq \|\hat{\varepsilon}_k\|\) and Markov’s inequality on \(\|\hat{\varepsilon}_k\|^2\): \(\mathrm{Pr}(\|\hat{\varepsilon}_k\|_\infty \geq q/2) \leq 4B_\varepsilon^2/q^2.\) With \(B_\varepsilon^2\) from 23 , which is independent of \(q\), and \(q \approx 2^{109}, 2^{218}\), this probability is negligible.

10 Proof of Lemma 1↩︎

The constants \(L\), \(b\), \(b_1\), \(b_2\) are given by Assumptions 3.1–3.4 of [4]: \(L\) is the Lipschitz constant of the gradient \(\nabla F_i\), i.e.\(\|\nabla F_i({\boldsymbol{x}})-\nabla F_i({\boldsymbol{y}})\|\leq L\|{\boldsymbol{x}}-{\boldsymbol{y}}\|\); \(b\) is a uniform bound on the Hessian (\(\|\nabla^2 F_i\|_2 \leq b\)); \(b_1 = \mathbb{E}[({ \Phi}_k^j)^2]\), which is a single constant because \({\boldsymbol{\Phi}}_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 \(b_2\) is a uniform upperbound on \(\|{\boldsymbol{\Phi}}_k\| \leq b_2\). The derived constants are \(c_1 = 2b_1\) and \(c_3 = bb_2^3 N/(2b_1)\). Recall that the history of models and samples up to and including \({\boldsymbol{\theta}}_k\) is denoted by \[\label{eq:Hk95def} \mathcal{H}_k := \{{\boldsymbol{\theta}}_0, \xi_0, \ldots, {\boldsymbol{\theta}}_{k-1}, \xi_{k-1}, {\boldsymbol{\theta}}_k\},\tag{24}\] where \(\xi_k := \{\xi_{i,k}\}_{i=1}^N\) collects the round-\(k\) samples across devices. We note that by Assumption 3.4 of [4] and Assumption 1, the variables \(h_{\cdot,k}\), \({\boldsymbol{\Phi}}_k\), \(\xi_{\cdot,k}\), and the HE randomness are independent of \(\mathcal{H}_k\), hence conditioning on \(\mathcal{H}_k\) preserves mutual independence.

We proceed with the proof of Lemma 1. The gradient estimator is given by \[\label{eq:gk95expand} {\boldsymbol{g}}_k = {\boldsymbol{\Phi}}_k\left(\sum_i \frac{h_{i,k}}{\mu_i}\Delta f_{i,k} + \varepsilon_k\right).\tag{25}\]

Bias

Since \(h_{i,k}\) is independent of \(({\boldsymbol{\Phi}}_k, \xi_{\cdot,k})\) and \(\varepsilon_k\) is zero-mean and independent of \(({\boldsymbol{\Phi}}_k, \xi_{\cdot,k}, h_{\cdot,k})\) (Assumption 1), and since the independence structure is unchanged given \(\mathcal{H}_k\), as noted after 24 , taking \(\mathbb{E}[\cdot|\mathcal{H}_k]\) gives \[\begin{align} \mathbb{E}[{\boldsymbol{g}}_k|\mathcal{H}_k] &= \sum_{i=1}^N \frac{\mathbb{E}[h_{i,k}]}{\mu_i}\,\mathbb{E}_{\Phi,\xi}[{\boldsymbol{\Phi}}_k\Delta f_{i,k}|\mathcal{H}_k] \notag\\ &\quad + \underbrace{\mathbb{E}[\varepsilon_k]}_{=\,0}\,\mathbb{E}[{\boldsymbol{\Phi}}_k|\mathcal{H}_k] \notag\\ &= \sum_{i=1}^N \mathbb{E}_{\Phi,\xi}[{\boldsymbol{\Phi}}_k\Delta f_{i,k}|\mathcal{H}_k], \label{eq:bias95step1} \end{align}\tag{26}\]

where the last equality uses \(\mathbb{E}[h_{i,k}] = \mu_i\) from 2 .

We follow the same two-point ZO argument as in [4] (a mean-value Taylor expansion of \(F_i({\boldsymbol{\theta}}_k \pm \gamma_k{\boldsymbol{\Phi}}_k)\), we obtain \[\label{eq:first95moment95bound} \|\mathbb{E}[{\boldsymbol{g}}_k|\mathcal{H}_k]\| \leq c_1\gamma_k(\|{\nabla} F({\boldsymbol{\theta}}_k)\| + c_3\gamma_k),\tag{27}\] which completes the proof of the first part of Lemma 1.

We proceed with the proof of the second moment result. Since \(\|{\boldsymbol{\Phi}}_k\| \leq b_2\), Eq 25 implies \[\label{eq:sm95start} \mathbb{E}[\|{\boldsymbol{g}}_k\|^2|\mathcal{H}_k] \leq b_2^2\,\mathbb{E}\!\left[\left(\sum_i \frac{h_{i,k}}{\mu_i}\Delta f_{i,k} + \varepsilon_k\right)^{\!2}\Big|\mathcal{H}_k\right].\tag{28}\]

Expanding the square and noticing that \(\mathbb{E}[\varepsilon_k] = 0\) and that \(\varepsilon_k\) is independent of \((h_{\cdot,k}, {\boldsymbol{\Phi}}_k, \xi_{\cdot,k})\) by Assumption 1, the cross term vanishes and we get \[\begin{align} &\mathbb{E}\!\left[\left(\sum_i \frac{h_{i,k}}{\mu_i}\Delta f_{i,k} + \varepsilon_k\right)^{\!2}\Big|\mathcal{H}_k\right] \notag\\ &= \mathbb{E}\!\left[\left(\sum_i \frac{h_{i,k}}{\mu_i}\Delta f_{i,k}\right)^{\!2}\Big|\mathcal{H}_k\right] + \bar{\sigma}_\varepsilon^2. \label{eq:square95expand} \end{align}\tag{29}\] For the first term, we expand the double sum and use the fact that \(h_{i,k}\) is independent of \(({\boldsymbol{\Phi}}_k, \xi_{\cdot,k})\), and \(h_{i,k}\), \(h_{j,k}\) are independent for \(i \neq j\). We obtain \[\begin{align} &\mathbb{E}\!\left[\left(\sum_i \frac{h_{i,k}}{\mu_i}\Delta f_{i,k}\right)^{\!2}\Big|\mathcal{H}_k\right]\nonumber\\ &= \sum_i\sum_j \frac{\mathbb{E}[h_{i,k}h_{j,k}]}{\mu_i\mu_j}\,\mathbb{E}_{\Phi,\xi}[\Delta f_{i,k}\Delta f_{j,k}|\mathcal{H}_k] \notag\\ &= \sum_i \frac{\Omega_i}{\mu_i^2}\,\mathbb{E}[(\Delta f_{i,k})^2|\mathcal{H}_k] + \sum_{i \neq j} \frac{\mu_i\mu_j}{\mu_i\mu_j}\,\mathbb{E}[\Delta f_{i,k}\Delta f_{j,k}|\mathcal{H}_k], \label{eq:main95expand} \end{align}\tag{30}\] where we used \(\mathbb{E}[h_{i,k}^2] = \Omega_i\) and \(\mathbb{E}[h_{i,k}h_{j,k}] = \mu_i\mu_j\) for \(i \neq j\).

For the diagonal terms, by the Lipschitz bound \(|\Delta f_{i,k}| \leq 2Lb_2\gamma_k\) (Assumption 3.2): \[\label{eq:lip1} \mathbb{E}[(\Delta f_{i,k})^2|\mathcal{H}_k] \leq 4L^2b_2^2\gamma_k^2.\tag{31}\]

For the cross terms (\(i \neq j\)), since \(\xi_{i,k}\) and \(\xi_{j,k}\) are independent conditioned on \({\boldsymbol{\Phi}}_k\): \[\begin{align} |\mathbb{E}[\Delta f_{i,k}\Delta f_{j,k}|\mathcal{H}_k]| &\leq \mathbb{E}|[\Delta f_{i,k}||\Delta f_{j,k}||\mathcal{H}_k] \leq 4L^2b_2^2\gamma_k^2, \label{eq:lip2} \end{align}\tag{32}\] where the first inequality is due to Jensen \(|\mathbb{E}[\cdot]|\le\mathbb{E}|\cdot|\), and where we used \(|\Delta f_{i,k}|\le 2Lb_2\gamma_k\) (Assumption 3.2) to write the second inequality.

Substituting 31 and 32 into 30 implies \[\begin{align} &\mathbb{E}\!\left[\left(\sum_i \frac{h_{i,k}}{\mu_i}\Delta f_{i,k}\right)^{\!2}\Big|\mathcal{H}_k\right] \nonumber\\ &\leq \sum_i \frac{\Omega_i}{\mu_i^2}\, 4L^2b_2^2\gamma_k^2 + N(N\!-\!1)\, 4L^2b_2^2\gamma_k^2 \notag\\ &= 4L^2b_2^2\gamma_k^2\Big(\sum_i \frac{\Omega_i}{\mu_i^2} + N(N\!-\!1)\Big). \label{eq:main95bound} \end{align}\tag{33}\]

Using Eq. 33 in Eq. 28 , we get \[\label{eq:sm95final} \mathbb{E}[\|{\boldsymbol{g}}_k\|^2|\mathcal{H}_k] \leq \tilde{C}'_\gamma\,\gamma_k^2 + \tilde{C}'_\varepsilon,\tag{34}\] where \[\begin{align} \tilde{C}'_\gamma &:= 4L^2b_2^4\Big(\sum_i \frac{\Omega_i}{\mu_i^2} + N(N\!-\!1)\Big), \tag{35}\\ \tilde{C}'_\varepsilon &:= b_2^2\,\bar{\sigma}_\varepsilon^2, \tag{36} \end{align}\] where \(\bar{\sigma}_\varepsilon^2 := B_\varepsilon^2/(n\Lambda^2)\) is defined in Appendix 9-C. In the identical channles case \(\mu_i=\mu\), \(\Omega_i=\Omega\), this reduces to \(\tilde{C}'_\gamma = 4NL^2b_2^4(\Omega+(N-1)\mu^2)/\mu^2\).

11 Proofs of Theorems 1 and 2↩︎

By \(L\)-smoothness of \(F\) (Assumption 3.1 of [4]):

\[\label{eq:smoothness} F({\boldsymbol{\theta}}_{k+1}) \leq F({\boldsymbol{\theta}}_k) - \eta_k\langle \nabla F({\boldsymbol{\theta}}_k), {\boldsymbol{g}}_k\rangle + \frac{L}{2}\eta_k^2\|{\boldsymbol{g}}_k\|^2.\tag{37}\]

Taking \(\mathbb{E}[\cdot|\mathcal{H}_k]\) and applying Lemma 1, we get \[\begin{align} &\mathbb{E}[F({\boldsymbol{\theta}}_{k+1})|\mathcal{H}_k] \notag\\ &\leq F({\boldsymbol{\theta}}_k) - c_1\eta_k\gamma_k\langle{\nabla} F({\boldsymbol{\theta}}_k), {\nabla} F({\boldsymbol{\theta}}_k) + {\boldsymbol{\delta}}_k\rangle \notag\\ &\quad + \frac{L}{2}\eta_k^2(\tilde{C}'_\gamma\gamma_k^2 + \tilde{C}'_\varepsilon) \notag\\ &\leq F({\boldsymbol{\theta}}_k) - \frac{c_1\eta_k\gamma_k}{2}\|{\nabla} F({\boldsymbol{\theta}}_k)\|^2 + \frac{c_1c_3^2}{2}\eta_k\gamma_k^3 \notag\\ &\quad + \frac{\tilde{C}'_\gamma L}{2}\eta_k^2\gamma_k^2 + \frac{\tilde{C}'_\varepsilon L}{2}\eta_k^2, \label{eq:descent} \end{align}\tag{38}\] where we used \(-\langle a,b\rangle \leq \frac{1}{2}\|a\|^2 + \frac{1}{2}\|b\|^2\) and \(\|{\boldsymbol{\delta}}_k\| \leq c_3\gamma_k\) in order to write Eq 38 .

Summing from \(k = 0\) to \(K\), taking full expectation over all possible history \(\mathcal{H}_K\) and using the tower property as done in [4], we obtain \[\begin{align} &\frac{c_1}{2}\sum_{k=0}^K\eta_k\gamma_k\mathbb{E}[\|{\nabla} F({\boldsymbol{\theta}}_k)\|^2] \leq \hat{\Delta} + \frac{c_1c_3^2}{2}\sum_{k=0}^K\eta_k\gamma_k^3 \notag\\ &\quad + \frac{\tilde{C}'_\gamma L}{2}\sum_{k=0}^K\eta_k^2\gamma_k^2 + \frac{\tilde{C}'_\varepsilon L}{2}\sum_{k=0}^K\eta_k^2, \label{eq:tele} \end{align}\tag{39}\] where \(\hat{\Delta} = F({\boldsymbol{\theta}}_0) - F({\boldsymbol{\theta}}^*)\).

Proof of Theorem 1. By Assumption 3.3 of [4], \(\sum_k\eta_k\gamma_k^3 < \infty\) and \(\sum_k\eta_k^2\gamma_k^2 < \infty\). The HE noise term requires \(\sum_k\eta_k^2 < \infty\), which holds for \(\eta_k = \eta_0(1+k)^{-\upsilon_1}\) with \(\upsilon_1 > 1/2\). The RHS of 39 is then finite. Since \(\sum_k\eta_k\gamma_k\) diverges by Assumption 3.3, we can show in a similar way to [4] that \(\lim_{k\to\infty}\mathbb{E}[\|{\nabla} F({\boldsymbol{\theta}}_k)\|^2] = 0\).

Proof of Theorem 2. Set \(\eta_k = \eta = \eta_0 K^{-1/4}\), \(\gamma_k = \gamma = \gamma_0 K^{-1/4}\). Using 39 \[\begin{align} &K\eta_0\gamma_0 K^{-1/2}\min_{k=1:K}\mathbb{E}[\|{\nabla} F({\boldsymbol{\theta}}_k)\|^2] \notag\\ &\leq \frac{2\hat{\Delta}}{c_1} + c_3^2\eta_0\gamma_0^3 + \frac{\tilde{C}'_\gamma L}{c_1}\eta_0^2\gamma_0^2 + \frac{\tilde{C}'_\varepsilon L}{c_1}\eta_0^2 K^{1/2}. \label{eq:rate95sub} \end{align}\tag{40}\]

Dividing by \(\eta_0\gamma_0 K^{1/2}\) \[\begin{align} &\min_{k=1:K}\mathbb{E}[\|{\nabla} F({\boldsymbol{\theta}}_k)\|^2] \notag\\ &\leq \underbrace{\frac{2\hat{\Delta}}{c_1\eta_0\gamma_0\sqrt{K}} + \frac{c_3^2\gamma_0^2}{\sqrt{K}} + \frac{\tilde{C}'_\gamma L\eta_0\gamma_0}{c_1\sqrt{K}}}_{= O(1/\sqrt{K})} + \underbrace{\frac{\tilde{C}'_\varepsilon L\eta_0}{c_1\gamma_0}}_{\rho}. \label{eq:rate} \end{align}\tag{41}\]

By Markov’s inequality, for any \(\epsilon > \rho\) and \(\beta > 0\): \[\begin{align} &\mathrm{Pr}\!\left(\min_{k=1:K}\|{\nabla} F({\boldsymbol{\theta}}_k)\|^2 \geq \epsilon\right) \leq \frac{1}{\epsilon}\left(\frac{R}{\sqrt{K}} + \rho\right), \label{eq:markov} \end{align}\tag{42}\] where \(R = \frac{2\hat{\Delta}}{c_1\eta_0\gamma_0} + c_3^2\gamma_0^2 + \frac{\tilde{C}'_\gamma L\eta_0\gamma_0}{c_1}\). Setting the RHS of 42 equal to \(\beta\) and solving, we get \[\label{eq:K95formula} K = \frac{R^2}{(\epsilon\beta - \rho)^2},\tag{43}\] which completes the proof of Theorem 2.

References↩︎