1
Three Birds, One Stone: Solving the Communication-Memory-Privacy Trilemma in LLM Fine-tuning Over Wireless Networks with Zeroth-Order Optimization
arXiv:2604.12401v1 [cs.DC] 14 Apr 2026
Zhijie Cai, Yuhao Zheng, Haolong Chen, Dongzhu Liu, Bin Wang, Guangxu Zhu
Abstract—Federated Learning (FL) offers a promising pathway for collaboratively fine-tuning Large Language Models (LLMs) at the edge; however, this paradigm faces a critical bottleneck: the prohibitive communication and memory overheads incurred by exchanging high-dimensional gradients. Furthermore, recent studies reveal that user training data can still be recovered from these local gradients, undermining the core privacy promise of FL. In this paper, we address this trilemma of communication, memory, and privacy by proposing pAirZero, a novel framework that synergizes Zeroth-Order (ZO) optimization with Over-theAir (OTA) computation. Uniquely, pAirZero enables resourceconstrained devices to submit their local gradient with only bitlevel communication loads while participating in federated finetuning of LLMs with inference-level memory costs. This approach not only eliminates the high memory requirements needed for LLM fine-tuning but also alleviates the strict synchronization requirements that plague conventional OTA methods. We further formulate a rigorous optimization model to adaptively determine the optimal transmit power and noise levels, ensuring consistent privacy protection regardless of channel conditions. Numerical experiments demonstrate the superiority of pAirZero in enabling secure, efficient LLM fine-tuning over wireless networks, with only 25% peak memory cost on OPT-125M and magnitudesof-order lower communication load compared to conventional methods. Index Terms—Federated learning, zeroth-order optimization, LLM fine-tuning, over-the-air computation, differential privacy.
I. I NTRODUCTION The advent of Large Language Models (LLMs) has revolutionized artificial intelligence, enabling unprecedented capabilities in natural language understanding and generation. However, the sheer scale of these models—often spanning billions of parameters—traditionally confines their deployment to centralized data centers. This centralization creates a critical disconnect: while the most valuable, context-rich data resides at the network edge (on smartphones, IoT devices, and vehicles), the computational power required to learn from it remains locked in the cloud. In contrast, recent regulations Z. Cai and H. Chen are with Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research Institute of Big Data, The Chinese University of Hong Kong-Shenzhen, Guangdong, China. Y. Zheng is with the School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China. D. Liu is with the School of Computing Science, University of Glasgow, Glasgow, U.K. B. Wang and G. Zhu are with Shenzhen Research Institute of Big Data, The Chinese University of Hong Kong-Shenzhen, Guangdong, China. Corresponding authors: B. Wang ([email protected]) and G. Zhu ([email protected]).
such as the GDPR (General Data Protection Regulation) and the ADPPA (American Data Privacy and Protection Act) have imposed restrictions on sharing privacy-sensitive data among different clients or platforms. Consequently, collecting a sufficient amount of data to train machine learning models for these applications is a challenging task. The gap becomes even more emergent, as pointed out by [1], publicly available data will soon be depleted. Therefore, it is crucial to enable the secure use of personal data for model training. Federated Learning (FL) has emerged as the de facto solution to bridge this gap, allowing edge devices to collaboratively fine-tune models without exposing raw private data. Yet, deploying FL for LLMs at the edge introduces a formidable “trilemma” that current infrastructure struggles to support: Communication Bottleneck: Transmitting the gradients of massive LLMs overwhelms the limited bandwidth of wireless edge networks. • Memory Wall: Standard backpropagation (BP) requires storing intermediate activation maps, demanding memory far exceeding the capacity of typical edge devices. • Privacy Leakage: Despite FL’s promise, recent gradient inversion attacks [2] have demonstrated that sensitive user data can be reconstructed from the very gradients intended to protect it. •
Existing solutions often tackle these challenges in isolation. Quantization [3] and sparsification [4] reduce communication but overlook memory constraints. Split learning alleviates memory pressure but incurs high latency [5], and Differential Privacy (DP) mechanisms often degrade model accuracy [6], [7]. Furthermore, traditional Over-the-Air (OTA) computation—a physical-layer technique that aggregates signals via channel superposition—offers a potential solution to bandwidth constraints [8]; however, it suffers from strict synchronization requirements [9] and analog signal distortion [10]. In this paper, we propose a unified framework that leverages these challenges to create synergies. We observe that ZerothOrder (ZO) optimization, which estimates gradients by probing the loss function with random perturbations, naturally aligns with the properties of OTA computation. ZO is inherently robust to the noise that plagues analog OTA transmission, turning the wireless channel’s imperfections into a mechanism for differential privacy. Furthermore, by eliminating the need for backpropagation, ZO optimization shatters the memory wall; by leveraging the superposition property of wireless channels,
2
OTA computation dissolves the communication bottleneck. Ultimately, a classic ZO algorithm, known as SPSA [11], if combined with PRNG [12], can reduce the per iteration communication load to bit-level, as will be detailed in Section IV-A. Building on this insight, we introduce pAirZero, a novel privacy-preserving FL framework designed specifically for fine-tuning LLMs at the edge. Unlike traditional approaches that treat privacy as an afterthought, pAirZero embeds DP directly into the wireless transmission process. We utilize the inherent noise of wireless channels, supplemented by artificial noise injection, to mask individual contributions ”in the air.” This creates a privacy-by-design architecture where the aggregation process itself acts as the privacy mechanism. Our specific contributions are as follows: • Holistic Framework for Efficient Edge LLM FineTuning: We propose pAirZero, the first framework to synergize ZO optimization with OTA computation for private LLM fine-tuning. This combination natively supports a wider range of indifferentiable objectives, reduces memory consumption to inference-level standards (75% reduction) and decouples communication costs from the number of participating devices. Moreover, ZO reduces the per-iteration load to a bit-level by refraining from sending true gradients, instead sending gradient projections on pseudo-random directions. • Privacy-by-Design Transmission: We develop a rigorous differential privacy mechanism embedded within the gradient transmission. By optimizing the transmit power and injecting calibrated artificial noise, we ensure that the aggregated signal remains useful for learning while mathematically guaranteeing that individual user data cannot be distinguished. • Empirical Validation: Extensive experiments on the well-recognized and light-weighted OPT-125M model demonstrate that pAirZero achieves test performances comparable to that of ideal, non-private baseline while significantly outperforming standard methods and naive schemes in terms of communication and memory efficiency. The remainder of this paper is organized as follows. We first review related works in Section II, introduce the system model in Section III, and present the algorithm design in Section IV. We conduct convergence bound analysis in Section V, and minimize it with optimization problems in Section VI. We present empirical evaluations Section VII and conclude this work in Section VIII. II. R ELATED W ORKS A. Communication-Efficient FL The benefits of FL come at the expense of extremely high communication costs, as FL requires frequent gradient uploads [13], The communication bottleneck of FL originates in the excessively high dimensionality of the gradient vectors. This bottleneck becomes even more prominent when training or fine-tuning LLMs. Compression-based methods offer a way to reduce the per-iteration communication cost in FL. The
first direction is to sparsify [4] the local gradient such that only a small portion of elements need to be uploaded to the edge server. The rationale behind this is that most of the gradient elements are small (in magnitude), and reserving only those significant elements can well approximate the direction of the local gradient. A similar strategy is to let each client upload a quantized local gradient [3] . In addition to elementwise compression, client selection-based methods [14] and local training-based methods [15]–[17] can also be regarded as special types of compression-based methods. The rationale behind these methods is to reduce the upload frequency of each client, thereby alleviating the communication burden in each iteration; however, this often occurs at the cost of slower convergence. Apart from machine learning algorithm design, advanced communication protocols can also be employed to improve communication efficiency. Orthogonal multiple access (OMA) allows numerous clients to share the same communication resource (such as time, frequency, or code) by assigning mutually orthogonal signal resources to different clients, thereby enabling the receiver to avoid interference between clients. However, the number of clients that can simultaneously be served is limited by the total amount of orthogonal resources (such as time slots and subcarriers). In massive connectivity scenarios such as federated learning, this becomes a bottleneck. An alternative to OMA is the so-called non-orthogonal multiple access (NOMA). In NOMA, clients share the same time-frequency resources, with differentiation achieved through power differences (power-domain NOMA) [18] or sparse codebooks (code-domain NOMA) [19]. Theoretically, NOMA can support overloaded transmission scenarios in which the number of clients exceeds the number of available resource blocks. FL applications favor such a characteristic [20]. However, NOMA is affected by the phenomenon of error propagation. Specifically, if one client’s signal is incorrectly decoded, the error will accumulate, causing all subsequent decoding attempts to fail as well. In conventional FL, the edge server averages all local gradients after receiving each individual. Similar to NOMA, OTA also allows all clients to share the same radio resources. The key difference is that the gradient average is obtained through the electromagnetic superposition of all clients’ wireless signals. Therefore, OTA does not require decoding each client’s signal. In OTA, all client transmits their local gradients synchronously with uncoded transmission [8], [21]–[24]. The performance can be further enhanced with proper power control [25], beamforming design [26], and inference management [27]. While these works assume analog modulations, [28] established a digital modulationbased framework. However, all the above-mentioned methods require stringent transmit synchronization across different clients, which is hardly achievable in practical systems (see [9] for an experimental implementation). B. Memory-Efficient FL We notice that there are some overlapping techniques between memory-efficient and communication-efficient FL. In
3
Fig. 1. The workflow of pAirZero.
the particular area of fine-tuning, Parameter-Efficient FineTuning (PEFT) [29]–[31] is deeply related to compressionbased methods. For example, the essence of Low Rank Adaptation (LoRA) [31] is to freeze the weights of the pre-trained model and then update several additional low-rank trainable parameter matrices. Therefore, this method can be easily incorporated into FL to reduce communication and memory costs, as seen in [32]–[34]. Nevertheless, these methods still face communication bottlenecks because the communication load still scales with the number of learnable parameters. Moreover, they still rely on first-order (FO) optimization methods that require excessive memory, such as SGD and Adam. Recently, the approach of zeroth-order (ZO) optimization [11] is regarded as a possible solution to overcome this bottleneck. Instead of directly computing the gradient via backpropagation, ZO estimates the gradient by calculating one or a few random directional derivatives. The effectiveness of ZO-SGD for fine-tuning LLMs in a centralized setting is first demonstrated in [35]. It shows that ZO-SGD performs comparably to full-parameter fine-tuning across various tasks while reducing memory consumption by up to 12 times [35]. In this regard, uploading the estimated gradient can be simplified to transmitting only the gradient projection on the designated random direction coded by the random seed. Subsequently, ZO-based methods have been rapidly adopted in federated learning [36] , with the focus shifting from memory reduction to improving communication efficiency. More recently, studies such as FedKSeed [37] and FwdLLM [38] have demonstrated that, empowered by ZO, even low-capacity networks with transmission rates of only a few kilobytes per second can support federated LLM fine-tuning. Additionally, a recent pioneering work [39] combines OTA and ZO to enhance the spectrum efficiency further.
is to introduce uncertainty into the disclosed information, thereby obscuring contributions from individual data points. A considerable amount of research has been conducted on the application of DP in FL, including standard FL [42], NOMA-based FL [43], digital quantization-based FL [44], and OTA-based FL [45]. However, these works all employ traditional back-propagation for model training. More recently, DP has also been combined with ZO-based FL methods, as seen in [46]–[48]. Nevertheless, these studies do not account for imperfect communications. Therefore, differential privacy cannot guarantee a consistent level of privacy protection. III. S YSTEM M ODEL A. Learning Model We consider a wireless federated edge learning system consisting of a single-antenna edge server and K singleantenna clients. Each client is connected to the edge server via a shared noisy channel. We aim to fine-tune an LLM collaboratively; this amounts to solving the following problem: min F (w), (1) w∈Rd
where w ∈ Rd is the model vector to be fine-tuned, PK 1 F (w) ≜ K k=1 Fk (w), is the global loss function, P (t) (t) Fk (w) ≜ |D1k | {u(t) ,v(t) }∈D f (w; uk,i , vk,i ), k,i
k,i
k
(2) (3)
is the local loss function held by client k, Dk is the client k’s (t) (t) local training dataset, and {uk,i , vk,i } is the ith training data sample. We assume a SGD-based wireless federated edge learning process, specifically, each client k estimate the gradient of its (t) local loss function g̃ k at each iteration t, then the clients PK (t) 1 update their models by w(t+1) = w(t) − η K k=1 g̃ k .
C. Differentially Private FL
B. Communication Model
Even though FL avoids direct data exposure, it is still possible to recover client data from the uploaded local gradient (see [2]). Malicious clients could potentially infer the presence of an individual data sample from a learned model through a membership attack [40] or a model inversion attack [41]. Differential privacy provides a cheap and convenient way to enhance privacy protection. The core idea of DP
The essence of OTA transmission is to obtain an average of several transmitted numerical values via the superposition of electromagnetic waves emitted by the clients, each encoded (t) by pk . Consider a block fading channel where the channel coefficient remains unchanged within the t-th transmission, the received signal at the edge server can be written as PK (t) (t) y (t) = k=1 hk xk + z (t) , (4)
4
(t)
where hk ∈ C is the channel coefficient between the kth (t) client and the edge server, xk ∈ C, a processed version of (t) pk , is client k’s uploading signal (containing both the desired signal and artificial noise), z t ∈ C is the Gaussian random (t) noise at the edge server. We defer the specific form of xk to the following sections. Upon receiving y (t) , rather than recovering the noiseless average value, the edge server attempts to recover the average PK (t) 1 k=1 pk through channel inversion, namely, K (t)
y p̂(t) = Kc (5) (t) . After this, the noisy average is broadcast back to all clients1 . Upon receiving p̂(t) , the clients will get ready for a next round of computation.
C. Trillema of Communication, Memory, and Privacy In conventional FO-based edge learning systems, we face (t) significant communication costs when setting pk as the (t) elements of the gradient vectors g̃ k computed by BP, which also incurs substantial memory consumption. Moreover, privacy-preserving by DP introduces additional computation by generating and adding correct noise vectors to the original gradient, resulting in a significant computational load on resource-constrained devices. This incentivizes us to find a communication-memory-privacy-efficient way for edge LLM fine-tuning. IV. pAirZero: C OMMUNICATION -M EMORY-P RIVACYE FFICIENT E DGE LLM F INE - TUNING (t)
As done in most of prior works, the payload xk is the true estimated gradients from back-propagations. However, in order to improve the availability of LLMs on resource-constrained devices, we switch to ZO-based optimization. We first describe the local gradient estimation, then we elaborate on the details of transmission. We then confirm the feasibility of the design with convergence analyses. An illustration of the workflow is Fig. 1. A. Memory-efficient Gradient Estimation At each iteration, each client k pulls a seed s(t) from the edge server and then estimates its local gradient by simultaneous perturbative stochastic approximation (SPSA): (t) (t) Local gradient: g k = pk z (t) , (6) where z ∈ N (0, I d ) is random vector generated by the seed (t) (t) pk , µ is the scale of perturbation, and pk is referred to as the gradient projection which is defined as (t) (t) (t) ) k (w−µz . Local gradient projection: pk = Fk (w+µz )−F 2µ (7) In the above, Fk (w + µz (t) ) and Fk (w − µz (t) ) are computed using either the entire local training data or a mini-batch of local training data. In ZO, only ptk needs to be uploaded to the edge server for gradient aggregation. This is because z (t) can be generated by the random seed s(t) stored at the edge 1 We assume that the downlink broadcast is noise-free. This is reasonable since the edge server is much more communication powerful than the clients.
server. With each local gradient given by Eq. (6), the global PK (t) (t) 1 aggregated gradient should be g (t) = ( K k=1 pk )z . Remark 1 (Compatibility with indifferentiable objectives). Unlike in FO methods, it is not necessary for Fk to be a differentiable function. This will give ZO methods an advantage in dealing with a wider range of objective functions that are more often used in modern LLMs. Remark 2 (Memory efficiency). In the above, instead of adopting back-propagation to compute a true gradient as done in most prior works, we employ a ZO gradient estimation method. Unlike acquiring excessive memory for backpropagation, the ZO method only requires inference-level memory overhead, as the gradient computation relies solely on loss function values. This will significantly reduce the memory overhead during the fine-tuning process, making it exceptionally appealing for clients (often assumed to be resourceconstrained) participating in the FL system. A simple comparison can be found in Section VII-C.
B. Communication-efficient Gradient Aggregation In terms of communication, we consider two different designs: pAirZero and Sign-pAirZero as follows. 1) pAirZero: With analog modulation, the sending signal is (t) (t) (t) (t) xk = αk (pk + nk ), (8) (t)
(t)
where αk is the scaling factor, nk ∈ C is the artificial noise used to facilitate differential privacy. In this regard, the received signal at the edge server becomes PK (t) (t) (t) (t) y (t) = k=1 hk (αk (pk + nk )) + z (t) , (9) (t)
where αk is the scaling factor. 2) Sign-pAirZero: To accommodate digital modulation, which is more similar to modern communication design, we utilize a one-bit compression on the gradient projection for simplicity. We then design the sending signal to K X (t) (t) (t) (t) xk = αk (sign sign{pk } + nk ), (10) k=1
and thus the received signal is given as PK (t) (t) (t (t) y (t) = k=1 hk (αk (sign{pk } + nk )) + z (t) ,
(11)
(t) (t) Suppose hk αk = c(t) , then for both cases, the effective PK (t) (t) noise is k=1 c nk + z t , whose standard deviation is given
as m(t) = (c(t) )2
1/2 (t) 2 . k=1 (σk ) + N0
PK
(12)
Remark 3 (Communication efficiency). The communication efficacy of pAirZero is two-fold. Firstly, the above 1-bit compression seems to share a similar form with signSGD [3]. However, it should be noted that signSGD compresses each local gradient element-wise. For this reason, the communication overhead scales with the ambient dimension. In contrast, both pAirZero and Sign-pAirZero admit an O(1) communication load independent of the ambient model dimension. This results in magnitudes of order lower communication overhead, and will alleviate the stringent communication synchronization often assumed in previous OTA computation works, making OTA
5
computation more realistic for resource-constrained clients. Secondly, note that OTA computation allows all users to transmit on the same resource block, the latency is independent of the number of participating clients. 3) Model Updates: Each client updates the model vector via w(t+1) = w(t) − η · p̂(t) z (t) , where η is the learning rate. C. Privacy-preserving Gradient Sharing Differential privacy imposes a point-wise upper bound on the divergence between the distributions P(y|D) and P(y|D′ ), conditioned on the use of either one of two “neighboring” global data sets D and D′ . The formal definition is given as follows. Definition 1 (Differential Privacy (DP) [6]). The learning process is (ϵ, δ)-differentially private if for any two possible ′ ′′ K ′′ adjacent global data sets D′ = ∪K k=1 Dk and D = ∪k=1 Dk ′ where there exists only one client indexed j satisfying ∥Dj − Dj′′ ∥1 = 1 and ∥Dk′ − Dk′′ ∥1 = 0 for any k ̸= j, it holds that P(y|D′ ) ≤ exp(ϵ)P(y|D′′ ) + δ, (13) where ∥ · ∥1 is the Hamming distance [49], ϵ ∈ (0, ∞) and δ ∈ [0, 1) are two constants characterizing the privacy budget. If Eq. (13) holds, then the differential privacy loss, defined as P(y|D ′ ) (14) LD′ ,D′′ (y) = ln P(y|D ′′ ) . satisfies P(|LD′ ,D′′ (y)| < ϵ) > 1 − δ. (15) Setting a sufficiently small ϵ and δ will forbid any adversary who knows all other data samples in the data set from identifying the remaining individual from the observed outputs. Lemma 1 (Privacy Loss Bound). The learning process of pAirZero, equipped with analog modulation, is (ϵ, δ)-DP if √ (t) (t) (t) 2 PT 2c γ /m ≤ Rdp (ϵ, δ), ∀k, (16) t=1 where p 2 Rdp (ϵ, δ) = ϵ + [C −1 (1/δ)]2 − C −1 (1/δ) , (17) √ x2 −1 C(x) is a function defined as C(x) = πxe , and C is the inverse function of C(x). Proof. See Appendix A. Remark 4 (Privacy efficiency). Unlike [45], we privatize the gradient projection rather than the gradient itself, which is a long vector. While privatizing on a long vector results in a completely random vector of the same size as the gradient, leading to significant computation overhead per iteration, privatizing on only a scalar is convenient for resourceconstrained client devices. We summarize the algorithm in pseudo-code, as shown in Algorithm 1. V. C ONVERGENCE AND O PTIMALITY G AP A NALYSIS To verify the feasibility of the algorithm design given the vastly reduced communication and memory overhead with an efficient privacy mechanism, we conduct theoretical analyses on the convergence for the proposed pAirZero and SignpAirZero.Regarding the loss function, we make the following widely adopted assumptions.
Algorithm 1 The proposed pAirZero and Sign-pAirZero Ensure: Trained model w(T ) . 1: Initialize w (0) , clients pull w (0) 2: for t = 1, . . . , T do 3: clients estimate Eq. (7) in parallel 4: if Analog then (t) 5: Determine c(t) and σk from Theorem 3; 6: client sends Eq. (8); 7: edge server receives by Eq. (9); 8: else (t) 9: Determine c(t) and σk from Theorem 4; 10: client sends Eq. (10); 11: edge server receives by Eq. (11); 12: end if 13: edge server estimate p̂(t) by Eq. (5) and broadcast it to all clients; 14: Each client updates w(t+1) ← w(t) − η p̂(t) z (t) ; 15: end for
Assumption 1 (Gradient Lipschitz continuity, [50]). The gradient of the global loss function F (w) is assumed to globally L-Lipschitz continuous, namely, ∥∇F (w) − ∇F (w′ )∥22 ≤ L∥w − w′ ∥22 , ∀w, w′ ∈ Rd (18) Assumption 2 (Polyak-Łojaciewicz property, [51]). The global loss function F (w) is said to have the PolyakŁojaciewicz property if it holds ∥∇F (w)∥22 ≥ 2M (F (w) − F ∗ ), ∀w ∈ Rd , (19) where F ∗ is the global optimum and M ∈ (0, ∞) is a constant. Assumption 3 (Sample-wise bounded gradient projection). In (t) iteration t, the gradient projection pk (u, v) computed at any training sample (u, v) ∈ Dk is assumed to be smaller than (t) a constant γk > 0. For convenience, we also define γ (t) ≜ (t) max γk . Assumption 4 (Local r-effective rank, [35]). Define G(w(t) ) ≜ max(u,v)∈D ||∇F (w(t) ; u, v)||2 . The global loss function is said to have local r-effective rank if, for any wt , there exists an effective rank-r matrix H w(t) ≼ L · I d such that ∇2 F (w) ≤ H w(t) holds for ∀w ∈ {w | ||w − w(t) ||2 ≤ η ·d·G(w(t) )}, where the effective rank is defined as the value of tr(H w(t) )/∥H w(t) ∥op . Assumption 5 (Unbiased batch gradient with finite variance, [50]). The batch gradient is unbiased, and the variance of the FO batch gradient estimation is finite, specifically, E[∇F (w; B)] = ∇F (w), (20) E[∥∇F (w; B)∥22 ] = ∥∇F (w)∥22 + tr(Σ)/b, (21) where b is the batch size of B, Σ represents the covariance matrix of the true gradient ∇F . In the above, the gradient Lipschitz continuity as well as the Polyak-Łojaciewicz property are widely assumed in federated learning, as they are key to proving the convergence of gradient-based optimization methods. The bounded gradient projection assumption is crucial for avoiding infinite privacy
6
loss in a single iteration. At last, the local r-effective rank and finite batch gradient variance assumptions are widely used in the analysis ZO when fine-tuning an LLM. In particular, the local r-effective rank assumption ensures that the convergence speed of ZO is independent of the ambient dimension, which is essential; otherwise, the ZO gradient would be unable to achieve a sufficient decrease in the objective function of the LLM. The global convergence behavior of pAirZero with analog modulation is summarized as the following theorem: Theorem 1 (Optimality Gap Bound of pAirZero). Under Assumptions 1, 2 and 4, with a sufficiently small η detailed in the proof, after T iterations, the expected optimality gap is upper bounded as PT η2 LSOr (m(t) )2 (22) E[G(T ) ] ≤ AT G(0) + t=1 2bA t−T (Kc(t) )2 , where S := maxt tr(Σ(t) ), G(t) = F (wt ) − F ∗ represents the optimality gap at iteration t, Or is the corrected low-rank factor of the model, b is batch size, and A = 1 − M η is the contraction factor. Proof. See Appendix B. In the above, since A is smaller than 1, AT G(0) vanishes with a linear rate. Besides, the second term in the righthand side of Eq. (22) is upper-bounded by a constant number (since it is a sum of a geometric decaying sequence whose common ratio is A). This theorem indicates that pAirZero converges linearly to a neighborhood of the global optimal point, provided that m(t) and c(t) are upper bounded. In fact, the linear convergence rate is the best result that can be obtained with the PL condition. In the next section, we will also show how to minimize the neighborhood term by tuning the per-client transmit power and the strength of the artificial noise. Unlike analog modulation, where the desired signals are directly aggregated, digital modulation relies on a majority voting scheme to reach a consensus. This leads to a completely different convergence analysis, which is summarized in the following theorem: Theorem 2 (Optimality Gap Bound for Sign-pAirZero). Under Assumptions 1 to 3 and 5, with a sufficiently small η detailed in the proof, after T iterations, the expected optimality gap is upper-bounded as PT E[G(w(T ) )] ≤ ÃT G(0) + t=1 ÃT −t θ · (e(t) )2 + r (23)
Assuming that the probability of the sign of the batch gradient projection estimator differs from that of the true gradient projection is no larger than e0 , namely, (t) (t) ek ≜ P(pk ∇F (w(t) )⊤ z (t) < 0) ≤ e0 . (25) Also assume that e0 ≤ 1/2. Then we have (e ) ≤
4Ke0 (1−e0 )+
(26)
Proof. See Appendix D. Remark 5. Although it is difficult to theoretically justify the validity of e0 ≤ 1/2, numerical experiments indicate this is indeed the case, see Section VII-D. Noticing that for both cases, the global loss converges linearly to the optimal point with a bounded neighborhood, whose size is a summation on a geometric series with their common ratio no larger than 1. With the derivation of the convergence bound, it turns out that the optimality gap bound is dominated by both the effective noise m(t) and channel gain c(t) . However, the answer to the following question remains unclear: how can we achieve optimal performance by carefully setting the periteration transmission power and artificial noise scale while avoiding constraint violations? VI. C LOSING O PTIMALITY G AP VIA P OWER C ONTROL Towards building a communication-memory-privacyefficient system for LLM FFT, we incorporated artificial noise and channel noise into the uploading process to facilitate DP protection on the gradient projection admitted by ZO optimization. To this aim, based on the convergence bound provided in Section V, we build optimization problems (t) for optimality gap minimization by tuning c(t) and σk dynamically. A. Power Allocation Optimization for pAirZero Ignoring the constants, the optimality gap bound of Eq. (22) yields PT PK (t) 2 N0 −t (27) t=1 A k=1 (σk ) + (c(t) )2 The bound minimization problem with DP and per-client transmit power constraints is formulated as PK PT (t) 2 N0 −t min (P1) t=1 A k=1 (σk ) + (c(t) )2 (t)
(t)
{ck ,σk }
s.t.
Proof. See Appendix C.
s.t.
Lemma 2 (Upper Bound of e(t) ). Define e(t) as the sign reversing probability, namely, e(t) ≜ P(p̂(t) ∇F (w(t) )⊤ z (t) < 0). (24)
(m(t) )2 +K 2 (1−2e0 )2 (c(t) )2
(t)
2
Different from the analog case, the quantity e does not have an explicit expression. Nevertheless, we can derive an upper bound for e(t) , as shown in the following lemma.
(m(t) )2 (c(t) )2
provided that 0 < ek < 1/2.
where à = 1 − Mθπη is the contraction factor, and e(t) is the total reversed sign probability at iteration t.
(t)
4Ke0 (1−e0 )+
(t) 2
PT
2(γ (t) )2 (t) 2 (σ k=1 k ) +
t=1 PK
(t) 2 c (t) hk
N0 (c(t) )2
≤ Rdp (ϵ, δ),
(t) (t) (γk )2 + d(σk )2 ≤ P, ∀k, t.
(C1) (C2)
where the first constraint is equivalent to the DP constraint, and the second constraint is the power Recall that (t) constraint. 2 the original power constaint is E ∥xk ∥ ≤ P , and (C2) is (t) (t) (t) (t) obtained by invoking xk = αk (pk + nk ). The following lemma explains the equivalence between (C1) and the DP constraint. Despite the complex form of the problem (P1), we show that the optimal solution to this problem can be obtained in
7
closed form. As such, the per-client transmit power and the strength of the artificial noise can be conveniently tuned in each iteration. Theorem 3 (Closed-form Solution to P1). The optimal solution to (P1) is given as follows: • If condition PT (t) 2 2P (28) t=1 mink {(hk ) } < Rdp (ϵ, δ) KN0 holds true, then ∗ 1 (t) (t) (t)∗ c(t) = min{P 2 hk (γk )−1 }, σk = 0, (29)
TABLE I L EARNING RATE GRID SEARCH , SELECTED LEARNING RATES ARE BOLDED . η
holds, then ∗
adaptive term
(30) where the value of ζ ∗ can be obtained by bisection search so as to meet the DP constraint, namely, n t P (h(t) )2 o PT A− 2 (t) 2 k , min = Rdp (ϵ, δ). 1 k (t) 2 t=1 2(γ ) min (t) N0 (γk )
(2ζ) 2 γ
(31) Proof. The proof of this theorem is very similar to that of Theorem P2, therefore, we omit it.
1
k
Similar to the analog case, by ignoring the constants, the right-hand side of Eq. (23), we can construct the following optimality gap bound minimization problem: PT −t (t) 2 min{c(t) ,σ(t) } (P2) t=1 Ã ηθ(e ) k k PT 2 s.t. ≤ Rdp (ϵ, δ), (C3) N0 (t) 2 t=1 PK k=1 (σk
) +
(c(t) )2
(t) 2 (t) s.t. c(t) /hk (1 + d(σk )2 ) ≤ P, ∀k, t. (C4) In the above problem, the equivalence between the constraint (C3) and the DP-constraint is shown in the following lemma, and the power constraint follows immediately by realizing that γ = 1.
Lemma 3 (Privacy Loss Bound for Sign-pAirZero). The learning process of pAirZero, equipped with digital modulation, is (ϵ, δ)-DP if, for each device k, PT 2(c(t) )2 ≤ Rdp (ϵ, δ) (32) (t) 2 t=1 (t) 2 PK (c
)
k=1 (σk
) +N0
Proof. Since clients send only a sign, setting γ = 1 in Lemma 1 yields the desired result. At last, we can also derive a closed-form solution to problem (P2), see the following theorem. Theorem 4 (Closed-form Solution to P2). The optimal solution to problem (P2) is given as follows: • If condition 2 PT 2(h(t) k ) P mink t=1 KN ≤ Rdp (ϵ, δ) (33) 0
= 0,
(34)
is the unique optimal solution to problem (P2), which means that the client with the poorest channel condition transmits the uncoded gradient projection with full power P. • Otherwise, problem (P2) admits non-unique optimal solutions, among which the solution that minimizes the transmit power n among 1all clients is given as (t) (t)∗ c = min mink {P 2 hk }, 1 1 o N02 (2(Ã−t B22 −2ζ ∗ )) 2 (t)∗ , σk = 0. (35) 1 √ (B1 +B2 ) 4ζ ∗ +
|
8Ã−t B22 ζ ∗
{z
2
}
adaptive term ∗
where the value of ζ can be obtained by bisection so as to satisfy the DP constraint, namely, n PT (t) 2 t=1 2 min mink {P (hk ) }, o 2(Ã−t B22 −2ζ ) √ = Rdp (ϵ, δ). (36) −t 2 (B1 +B2 ) 4ζ+
B. Power Allocation Optimization for Sign-pAirZero
(t)∗
(t)
c(t) = min{P 2 hk }, σk
k
is the unique solution to (P1), which means that the client with the poorest channel condition transmits the uncoded projection with full power P . • Otherwise, (P1) admits non-unique solutions, among which the solution that minimizes the transmit power among all clients is given as 1 o n t P 12 h(t) ∗ A− 4 N02 (t)∗ k , σk = 0. c(t) = min 1 , mink 1 (t) (t) ∗ γ 4 2 (2ζ ) (γ ) k | {z }
{1e − 7, 3e − 7, 5e − 7, 1e − 6, 5e − 6} {1e − 6, 5e − 6, 1e − 5, 3e − 5, 5e − 5}
pAirZero Sign-pAirZero
8Ã
B2 ζ
Proof. See Section E. VII. S IMULATIONS In this section, we provide simulation results to demonstrate the superiority of the proposed pAirZero and Sign-pAirZero. All the experiments are conducted on the OPT-125M model. In particular, we demonstrate that both pAirZero and SignpAirZero achieve comparable performance to non-DP cases and consistently outperform the baselines. All empirical results were obtained on a machine equipped with an AMD EPYC 7742 64-Core Processor and four NVIDIA A100-SXM4-80GB GPUs. A. Experimental Settings We employ OPT-125M [52], a well-recognized light-weight LLM. The number of clients is assumed to be K = 5. We include two classic language tasks for comparison: 1. SST-2 [53] (Stanford Sentiment Treebank, binary version), a binary sentence-level sentiment classification task (positive or negative); 2. SQuAD [54] (Stanford Question Answering Dataset), a reading comprehension task where the model is asked to extract the correct answer span directly from the provided passage. We select these two tasks to comprehensively evaluate the model’s improvement during fine-tuning, considering both basic abilities, such as understanding and classification (SST2), and more advanced abilities, including contextual understanding and information retrieval (SQuAD). In terms of parameter setting, the perturbation scale in Eq. (7)
8
is set to µ = 0.001, and the number of training samples is fixed as 1000. Moreover, we also set ϵ = 5, δ = 0.01, T = 8000 throughout this section. For each reported instance, we conduct a grid search to determine the learning rate that yields the best performance. The search grid is shown in Table I. Each data point in the main results represents the average of 4 trials, where we perform four independent runs with random seeds and report the mean and standard deviation of the corresponding measurements to minimize bias due to chance. As for the value of e0 and A, and γ, we set e0 = 0.4960, A = Ã = 0.998, and γ = 100, these choices will be elaborated in Section VII-D. To evaluate the performance w.r.t. different channel conditions, we define the maximum signal-to-noise ratio as SNRmax = P/dN0 , (37) where dN0 represents the power of the channel noises within one communication block, so that devices may optimally transmit with a power strictly smaller than P .
Fig. 2. Main results on OPT-125M with SST2 and SQuAD task.
B. Main Results We implement the proposed pAirZero and Sign-pAirZero across wireless channels with different maximum SNRs. We compare the solution-induced power allocation with the following cases: 1) Perfect. It provides the upper bound of the metrics in evaluation. In this sense, we assume that the aggregation is noise-free, that is, PK (t) (t) 1 (38) pAirZero: g (t) = K k=1 pk z , P (t) K (t) Sign-pAirZero: g (t) = sign k=1 Sign{pk } z . (39) 2) Static. Instead of featuring an adaptive power allocation, it distributes privacy budget evenly across all training iterations by replacing the adaptive term in c(t) in Eq. (30) and Eq. (35) q with the following constant:
Fig. 3. Performance with and without solution-based power allocation with analog modulation.
N R (ϵ,δ)
0 dp c(t) = . (40) 2T γ 2 3) Reversed. It is observed that the adaptive term of the optimization-induced solutions in both the pAirZero and Sign-pAirZero implies an increasing channel gain c(t) . To verify the effectiveness of this increasing trend, we t t replace A− 4 and Ã−t by A 4 and Ãt , respectively. Sign-pAirZero is more stable across SNR with privacy constraints. We report the main results in Fig. 2. We found that digital OTAs exhibit small fluctuations in performance (within one standard deviation), whereas analog OTAs are completely compromised in the low SNR regime. This is due to the zeroth-order gradient projection having a wide spread, detailed in Figure 7. This is because the DP model assumes full privacy loss, with the fluctuation of the disclosed function always in its maximum, as in Lemma 1. However, the privacy loss is often much smaller since the fluctuation is usually smaller. In other words, analog OTA requires a privacy model to overestimate privacy loss, leading to more noisy updates with lower SNR. pAirZero has higher possible performance. We observe that in harder tasks like SQuAD, analog OTA has a lead for more than one standard deviation compared to its digital
version. This is due to the larger gradient noise introduced by the one-bit compression on the gradient projection. Solution-based power allocation outperforms other baselines. We ablate on the power allocation scheme and report the results in Fig. 3. It is shown that Solution outperforms other baselines. Moreover, it is found that the model is compromised under the Static case. This is because ZO-based fine-tuning requires a large number of aggregations, which necessitates a minimal channel gain Eq. (40) with a large value of T , highlighting the need for optimization in Eq. (P1). C. Memory and Communication Efficiency We present a minimum memory overhead and per-iteration upload analysis in Table II assuming an FP16 precision. We observe a magnitude-of-orders reduction in per-iteration upload and 75% less memory cost in Sign-pAirZero and pAirZero, compared to conventional methods relying on FO methods. The massive reduction in memory cost and upload will make pAirZero and Sign-pAirZero preferred for resourceconstrained clients in an FL system.
9
TABLE II E STIMATED LOCAL MINIMUM MEMORY OVERHEAD AND PER - ITERATION UPLOAD FOR FINE - TUNING OPT-125M. Model size Sign-pAirZero pAirZero FO SGD FO Adam
Memory cost 238.88 MB ∼ 250 MB ∼ 250 MB ∼ 600 MB 955.58 MB
Per-iteration Upload 1 bit 16 bits 238.88 MB 238.88 MB
D. Parameter Study Since the analysis and problem solution involve key numerical parameters that cannot be directly obtained (e.g., e0 , A, and Ã) or need to be determined manually (e.g., γ), we therefore conduct a study to justify our choices of their value. 1) Sign Reversing Probability e0 : As stated in Theorem 2, the convergence of Sign-pAirZero is dependent on the signreversing probability e(t) , so knowledge of the range of this value is necessary for us to understand the convergence behavior of Sign-pAirZero. Since the explicit expression of e(t) is non-obtainable due to the complicated dynamics from data batches to gradient projections, we resort to an empirical study.
is always smaller than 1/2. Also, we can observe that the analog sensitivity function overestimates the privacy loss mainly due to the wide distribution of the batch gradient projection. 2) Contraction Ratio A and Ã: The contraction ratio absorbs numerous intractable parameters such as L, M , and Or . Nevertheless, this quantity plays a critical role in the power control. Therefore, an empirical estimation of this parameter is necessary. To this end, we record the loss values throughout one fine-tuning process on OPT-125M with the SST2 task, and estimate the upper bound of A as mint {(G(t) /G(0) )1/t }. The estimated upper bound is 0.998. We hence set A and à as this value. 3) Gradient Projection Clip Threshold γ: To avoid infinite privacy loss, we assert Assumption 3. However, gradient projections have a wide range of applications. An overly large γ will accordingly result in an overestimated privacy loss, while an excessively small γ leads to frequent gradient clips. Both of these situations are undesirable because they all jeopardize the convergence speed of the proposed algorithm. To get a favorable value of γ, we recorded gradient projections throughout one fine-tuning process on OPT-125M with the SST2 task and made a histogram, which is shown in Figure 7. It is found that over 97% of the gradient projections fall within [−100, 100], hence we set γ = 100. VIII. C ONCLUDING R EMARKS
Fig. 4. Inherent sign-reversing probability density.
Simulation Settings. We run OPT-125M on the SST2 task. We choose a training set consisting of 5000 samples, and for every 4000 iterations, we evaluate the gradient projection by sampling the gradient direction corresponding to seeds s = 0 to 39. We average the gradient projections to ob(t) tain z ⊤ s L(w ). We then uniformly sample 10000 batches of size 64 and take an average of the gradient projection (t) (t) as the proportion of the z⊤ s L(w , B). We compute ek batches holding a batch gradient projection with its sign (t) different from that of z ⊤ s ∇L(w ). Range of Inherent Sign-Reversing Probability. We report (t) the measured ek in Figure 5. It is noticed that the gradient projections are generally small, mainly due to the high dimen(t) sionality of the ambient space. The highest reading of ek , ⊤ namely 0.4968, is obtain at t = 12000, with z ∇L(w) = −0.3330. Near-Symmetric Distribution of z ⊤ ∇L(w, B). In Figure 6, we report the value of z ⊤ s ∇L(w, B) from s = 0 to 4, with t = 0, 4000, 8000, 12000, 16000. The red lines marks the corresponding z ⊤ ∇L(w). The distributions exhibit an obvious symmetric pattern. In summary, upon modeling the distribution of the batch gradient projections as a symmetric distribution centered at the proper gradient projection, the local sign-reversing probability
In this paper, we have proposed a communication-memoryprivacy-efficient over-the-air (OTA) transmission-based federated fine-tuning method, termed pAirZero, along with its digital adaptation, Sign-pAirZero. The differential privacy (DP) mechanism is embedded into the gradient transmission process to prevent privacy leakage. The proposed method requires only bit-level communication loads and inference-level memory usage. Additionally, it removes the strict synchronization requirements, which are the major obstacle to conventional OTA-based methods. More importantly, we have formulated an optimization model to determine the optimal transmit power and artificial noise level per iteration, ensuring a guaranteed level of privacy protection regardless of the channel noise strength. Numerical experiments demonstrate the superiority of our method. A PPENDIX A. Proof of Lemma 1 (1)
(T )
To start, let y k ≜ [yk , . . . , yk ] represent the received signal of client k over all T iterations. The privacy loss for client k after T iterations as Q is given (t) (t−1) (1) P (yk |yk ,...,yk ,D ′ ) T ′ ′′ LD ,D (y k ) = log (t) (t−1) (1) t=1 ′′ P (yk |yk
=
T P
=
t=1 T P
log exp
log exp −
t=1 (t)
(t)
,...,yk ,D )
(t)
−(yk −c(t) pk,D′ )2 (t)
2(mk )2 (t)
(rk )2 (t) 2(mk )2
(t)
/ exp
(t)
2(mk )2 (t)
/ exp −
(t)
−(yk −c(t) pk,D′′ )2 (t)
(rk +vk )2 (t) 2(mk )2
(41)
where pk,D′ is the local gradient projection at iteration t given (t) a dataset D′ , rk is the effective noise, the second line is obtained from Eq. (14), the third line is obtained by realizing
10
(t) ). Fig. 5. Inherent sign-reversing probability vs. z ⊤ s ∇F (w
Fig. 7. Distribution of gradient projections.
Fig. 6. Distribution of z ⊤ s ∇L(w, B). The red lines are estimated z ⊤ ∇L(w).
(t)
that vk is the difference of the observation with different local datasets, namely, (t) (t) (t) (t) (t) vk = hk αk (pk,D′ − pk,D′′ ) ≤ 2c(t) γ (t) . (42) Following Appendix A in [45], the privacy violation probability can be bounded by PT (t) (t) (t) (t) P | t=1 (2rk vk + (vk )2 )/2(mk )2 | > ϵ (a) PT PT (t) (t) (t) (t) (t) ≤ P | t=1 rk vk /(mk )2 | > ϵ − ( t=1 (vk )2 /2(mk )2 ) P T T P (t) (t) (t) (t) (t) =2P rk vk /(mk )2 > ϵ − (vk )2 /2(mk )2 t=1
(b)
t=1
2
t=1 (vk
(43)
/mk )2
B. Proof of Theorem 1 We denote the true zeroth-order batch gradient from miniˆ (w(t) ; B). According to batch B and model w(t) as ∇F Assumption 1, we have 2 F (w(t+1) ) ≤F (w(t) ) − η∇F (w(t) )⊤ g (t) + Lη2 ∥g (t) ∥22 ˆ (w(t) ; B) ≤F (w(t) ) − η∇F (w(t) )⊤ ∇F 2
2
s 2σ ≤ s√ exp − 2σ , 2 2π where PT (t) (t) σ = ( t=1 (vk /mk )2 )1/2 ,
(a) is because P(X < −ϵ − b) ≤ P(X < −ϵ + b) holds for an arbitrary b ≥ 0, and (b) comes from the following Mills’ bound of tail probability of Gaussian probability X ∼ N (0, σ 2 ): R∞ x2 P(X > s) = σ√12π s exp − 2σ dx 2 R 2 ∞ x ≤ σ√12π s xs exp − 2σ dx 2 2 s = s√σ2π exp − 2σ . (44) 2 From Eq. (43), we can immediately obtain the desired result: 2 P(|LD′ ,D′′ (yk )| > ϵ) ≤ q√1 π e−q < δ, where P (t) (t) 2 1 √ 2 ϵ− T t=1 2 (vk /mk ) q= q P , C(x) = πxex . (t) (t) T
(t))2
(m (t) ˆ + Lη2 (1 + (Kc ; B)∥22 (t) )2 )∥∇F (w
(45)
≤F (w(t) ) − η∇F (w(t) )⊤ ∇F (w(t) ; B)
(46)
2
s=ϵ−
(t) 1 (t) t=1 2 (vk /mk ),
PT
2 (m(t)) (t) + Lη 2Or (1 + (Kc ; B)∥22 , (t) )2 )∥∇F (w
(47)
11
where Eq. (45) comes from the fact that g (t) = p̂(t) z (t) with 2
(m(t)) p̂(t) ∼ N (p(t) , (Kc (t) )2 ), Eq. (46) is from the unbiasedness (t) ˆ
of ∇F (w ; B), and Eq. (47) comes from proof of Theorem 1 (page 33) of [35] (the norm of the ZO gradient scaled the quadratic norm by Or times compared to that of FO, where Or = dr+2d d+2 as we set the number of perturbation samples n = 1 under Assumption 4). It then follows by Assumption 5: F (w(t+1) ) ≤ F (w(t) ) − η∥∇F (w(t) )∥22 2
(t) 2
(t)
2
(t)
(m ) (t) 2 + Lη 2Or (1 + (Kc )∥2 + tr(Σb (t) )2 )(∥∇F (w
≤F (w
)
)
(t) 2
(m ) (t) 2 ) − (η − Lη 2Or (1 + (Kc )∥2 (t) )2 ))∥∇F (w
2
(t) 2
) r S(m + η LO 2b(Kc(t) )2
2
(t) 2
For ∥∇F (w(t) )∥2 in Eq. (51), take 0 < 23/2 π 1/2 θ min{ 5∥∇F } and apply Assumption 2 yields (w(t) )∥2
η
≤
2
(t) 2 − η( π2 )1/2 ∥∇F (w(t) )∥2 + 2η θπ ∥∇F (w )∥2 2
η ∥∇F (w(t) )∥22 ≤ − 2θπ 2
≤ − Mθπη (F (w(t) ) − F ∗ ) (52) Substituting Eq. (52) into Eq. (49), and subtracting F ∗ in both sides of the resulting inequality, we have E[F (w(t+1) )] − F ∗ 2
2
≤(1 − Mθπη )(F (w(t) ) − F ∗ ) + θ(e(t) )2 + η 2Lr t
(53)
(t) 2
≤ÃG(w ) + θ(e ) + r (54) PT T (0) −t (t) 2 ≤à G + t=1 Ã θ · (e ) + r (55) where the second inequality is obtained by setting 0 < η ≤ ( L2 )1/2 as well as the definition of Ã, and the third inequality is obtained by telescoping the third line.
) r S(m ≤F (w(t) ) − η2 ∥∇F (w(t) )∥22 + η LO , (48) 2b(Kc(t) )2 where Eq. (48) is obtained by choosing 0 < η ≤ (m(t) )2 (t) mint {1/(LOr (1+ (Kc ). We then (t) )2 ))} and S = maxt tr(Σ ∗ subtract F from both sides as follows: 2 (t) 2 D. Proof of Lemma 2 ) r S(m F (w(t+1) ) − F ∗ ≤ (1 − M η)(F (w(t) ) − F ∗ ) + η LO . 2b(Kc(t) )2 Denote strue ≜ sign{∇F (w(t) )⊤ z (t) }. For simplicity, we At last, we obtain the desired result by telescoping the above assume that local datasets are independent and identically inequality. (t) distributed, which means that ek s are identical across all clients. Nevertheless, the subscript is preserved to distinguish them from the total sign reversing probability e(t) . C. Proof of Theorem 2 (t) (t) Suppose nk = zk = 0, then from (Eq. (11)) we have By Taylor’s expansion, we have y (t) = c(t) (1 − 2w)strue , (56) F (w(t+1) ) ≤ F (w(t) ) − η∇F (w(t) )⊤ (w(t+1) − w(t) ) (t) where w ∼ Binomial(K, ek ). For this case, it holds + 12 η 2 (w(t+1) − w(t) )⊤ H w(t) (w(t+1) − w(t) ) (t) E[y (t) ] = c(t) K(1 − 2ek )strue , (57) Taking expectation over B and z, we have (t) (t) (t) 2 (t) (t+1) V[y ] = 4(c ) Kek (1 − ek ). (58) E[F (w )] (t) ⊤ (t) ⊤ (t) z ∇F (w )z ∇F (w ;B) Now suppose the noise in yk is nonzero. Recall that the effec≤F (w(t) ) − ηEz,B |z ⊤ ∇F (w(t) ;B)| tive noise is independent of the transmitted signal, therefore, η2 z⊤ ∇F (w(t) ;B)z⊤ H (t) z⊤ ∇F (w(t) ;B)z w we have + Ez,B (t) ⊤ 2 2(z ∇F (w ;B)) (t) (t) (t) i h ⊤ V[y (t) ] = 4(c(t) )2 Kek (1 − ek ) + (mk )2 . (59) (t) ⊤ (t) z ∇F (w )z ∇F (w ) (t) (t) =F (w ) − η(1 − 2e )Ez |z ⊤ ∇F (w(t) )| Further invoking Eq. (5), we have (t) η2 z⊤ H (t) z⊤ E[p̂(t) ] = (1 − 2ek ) · strue , (60) w +E , 2
where e(t) is the probability that the aggregated sign differs from the true sign, the equality comes from the fact that z ⊤ ∇F (w(t) )z ⊤ ∇F (w(t) ; B) = −z ⊤ ∇F (w(t) )z ⊤ ∇F (w(t) ) holds with probability e(t) . Since z is a standard i.i.d. Gaussian random vector, z ⊤ ∇F (w(t) )z ⊤ ∇F (w(t) ) will be half-Gaussian with a mean of |z ⊤ ∇F (w(t) )| 2 1/2 (t) ( π ) ∥∇F (w )∥2 . For the last term in the right-hand side, based on Assumption 4 we have E[F (w(t+1) )] ≤F (w(t) ) − η( π2 )1/2 ∥∇F (w(t) )∥2 2
+ 2ηe(t) ( π2 )1/2 ∥∇F (w(t) )∥2 + η 2Lr .
(49) To obtain a convex objective function for the optimality gap optimization problem, we need to decouple e(t) from the multiplication. Using the arithmetic inequality, for ∀θ > 0 we have 2 (t) 2 2ηe(t) ( π2 )1/2 ∥∇F (w(t) )∥2 ≤ θ(e(t) )2 + 2η θπ ∥∇F (w )∥2 . (50) Substituting Eq. (50) into Eq. (49) yields E[F (w(t+1) )] ≤F (w(t) ) − η( π2 )1/2 ∥∇F (w(t) )∥2 (51) 2
2
η Lr (t) 2 + θ(e(t) )2 + 2η θπ ∥∇F (w )∥2 + 2 .
(t)
4e
(t)
(1−e
(t) 2
)
(m ) V[p̂(t) ] = k K k + (Kc (61) (t) )2 . Combining Eq. (24) and the definition of strue , we have e(t) = P(strue · p̂(t) < 0), (62) Recall the Chebyshev-Cantelli inequality [55], namely, P(X < 0) = P(X − E[X] ≤ λ) ≤ V[X]/(V[X] + λ2 ),
with λ = −E[X] (63) Let X be set as strue · p̂(t) , then the Chebyshev-Cantelli inequality leads to (t)
(t) 2
(t)
(e ) ≤ e
≤
(t)
4Kek (1−ek )+ (t)
(t)
4Kek (1−ek )+
≤
(t) (m(t) )2 +K 2 (1−2ek )2 (c(t) )2
4Ke0 (1−e0 )+ 4Ke0 (1−e0 )+
(m(t) )2 (c(t) )2
(m(t) )2 (c(t) )2
(64)
(m(t) )2 +K 2 (1−2e0 )2 (c(t) )2
(t)
where the last inequality has invoked Eq. (25) (i.e., ek ≤ e0 ) as well as the fact that this fractional function is monotonically (t) increasing in the regime of 0 < ek < 1/2. E. Proof of Theorem 4 Recall that e(t) is upper bounded in Lemma 2, replacing
12
e(t) by this upper bound yields −t
−t
(t) 2
à ηθ(e ) ≤ à = Ã−t ηθ 1 −
equation
P N0 (t) 2 B1 +( K k=1 (σk ) + (c(t) )2 ) ηθ PK N (t) B1 +B2 +( k=1 (σk )2 + (t)0 2 ) (c
B2 P (t) 2 B1 +B2 +( K k=1 (σk ) +
)
N0 ) (c(t) )2
(66)
where B1 = K 2 (1 − 2e0 ) , B2 = 4Ke0 (1 − e0 ) . (67) Using fundamental algebra, we have (t) (t) (t) (t) (t) (t) mk = (σk )2 + N0 /(ck )2 , nk = (hk )2 (ck )−2 . (68) Thus, the original variables can be written as (t) (t) (t) (t) (t) (t) (t) (σk )2 = mk − N0 nk /(hk )2 , (ck )2 = (hk )2 (nk )−1 . (69) Substituting this into problem (P2), we obtain the following equivalent problem: PT B2 −t (P3) min t=1 Ã (1 − B1 +B2 +(m(t) ) ) (t)
(t)
{ck ,σk }
which is a convex problem. To solve this problem, define the Lagrange function as T PT P L= Ã−t (1 − B1 +BB22+m(t) ) + ζ( t=1 2(t) − Rdp (ϵ, δ)) mk
t=1
(t) (t) (t) + t=1 (ξ (t) (N0 nk /(hk )2 − mk )+ PT (t) (t) 2 (t) (t) t=1 β ((1 + d(mk ) − (dN0 /(hk ) + P )nk ) (t) (t)
PT
(71) where ζ ≥ 0, β ≥ 0 and ξ ≥ 0 are the Lagrange multipliers associated respectively with the DP constraint, transmit power constraints, and non-negative parameter constraints. The KKT condition can be given accordingly as (t) 2 ∂L 2 −t 2 ( B1 +B2B+(m (t) = Ã (t) ) ) − 2ζ/(mk ) ∂mk
+ β (t) d − ξ (t) = 0. (72) (t) ∂L (t) (dN0 /(hk )2 + P ) (t) = −β ∂nk (t)
+ ξ (t) N0 /(hk )2 = 0, PT ζ( t=1 2(t) − Rdp (ϵ, δ)) = 0, mk (t) (t) (t) (t) β 1 + d(mk ) − (dN0 /(hk )2 + P )nk = 0, (t)
(t)
(t)
ξ (t) (mk − N0 nk /(hk )2 ) = 0, PT 2 t=1 (t) − Rdp (ϵ, δ) ≤ 0, (t)
(74) (75) (76) (77)
mk
(t)
(73)
(t)
1 + d(mk ) − (dN0 /(hk )2 + P )nk ≤ 0,
(78)
(t) (t) (t) N0 nk /(hk )2 − mk ≤ 0.
(79)
Eq. (73) immediately implies ξ (t) = β (t)
(t)
(dN0 /(hk )2 +P )
(80)
(t)
N0 /(hk )2
Plugging this equality into Eq. (72) and Eq. (76) yields
β
B22
(t) (B1 +B2 +mk )2 √ (t) 2 (t) d( N0 /hk ) +P √ (t) ( N0 /hk )2
−ζ (
2 (t) (mk )2
− β (t)
(t)
P (hk )2 =0 N0
(t) (t) N0 n − mk ) = 0 (t) (hk )2 k
(81) (82)
Combining Eq. (82) and Eq. (75), we get the following
(83)
ensure that the lower bound is smaller than the upper bound, (t) mk should satisfy (t) N0 (84) mk ≥ (t) 2 (hk ) P
In this case, the power is fully utilized for transmitting the local gradient. Furthermore, from Eq. (83), we have the equality β (t) = 0 if follows Eq. (84). With β (t) = 0, Eq. (81) becomes (t) (t) (Ã−t B22 − 2ζ)(mk )2 − 4ζ(B1 + B2 )mk −2ζ(B1 + B2 )2 = 0
(85)
(t) Since mk
> 0, the positive root of the quadratic equation Eq. (85) should be the desired solution: √ (t)
2 t=1 m(t) ≤ Rdp (ϵ, δ), (t) (t) (t) (t) (1/nk )(1 + d(mk − N0 nk /(hk )2 )2 ) ≤ P, ∀t, (t) (t) (t) mk − N0 nk /(hk )2 ≥ 0, ∀t, (t) (t) mk ≥ 0, nk ≥ 0, ∀t. (70)
(t)
P (hk )2 (t) mk ) = 0 N0
(t) With a fixed mk , we can the lower bound and the upper (t) bound of nk from Eq. (78) and Eq. (79), respectively. To
mk =
PT
s.t.
Ã−t
β (t) (1 −
(65)
(B1 +B2 )(4ζ+ 8Ã−t B22 ζ) 2(Ã−t B22 −2ζ)
(86)
(t) Since mk
should also satisfy the constraints Eq. (78) and Eq. (79), therefore we have √ n o (B1 +B2 )(4ζ+ 8Ã−t B22 ζ) (t) N0 mk = max , (87) (t) 2 2(Ã−t B 2 −2ζ) (hk ) P
2
(t)
Since mk should also satisfy Eq. (77), we need to ensure the second term in the right-hand side of (Eq. (87)) satisfies Eq. (77). This can be achieved by searching for a proper ζ via bisection search. In particular, from Eq. (74) we know PT (t) that ζ should be 0 if t=1 2(hk )2 P/N0 < Rdp (ϵ, δ). After (t) (t) obtaining mk , the value of nk can be obtained by using Eq. (78) and Eq. (79), namely, (t)
d(
√
1+dmk
(t) N0 /(hk ))2 +P
(t)
≤ nk ≤
(t)
(t)
(hk )2 mk N0
(88)
(t) At last, since the optimal value of mk is known, and the range (t) of nk is determined by Eq. (88). According to Eq. (69), the (t) (t) feasible range of σk and ck can be located. Recall that we
prefer a solution with the minimum transmit power; therefore, (t) let nk be set to the right-hand side of Eq. (88), which yields the desired result. R EFERENCES [1] P. Villalobos, A. Ho, J. Sevilla et al., “Will we run out of data? Limits of LLM scaling based on human-generated data,” arXiv preprint arXiv:2211.04325, pp. 13–29, 2024. [2] L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” in Advances in Neural Information Processing Systems, 2019. [3] J. Bernstein, Y. Wang, K. Azizzadenesheli et al., “signSGD: Compressed optimisation for non-convex problems,” in International Conference on Machine Learning, 2018, pp. 560–569. [4] S. Stich, J.-B. Cordonnier, and M. Jaggi, “Sparsified SGD with memory,” Advances in Neural Information Processing Systems, 2018. [5] C. Thapa, P. C. M. Arachchige, S. Camtepe, and L. Sun, “Splitfed: When federated learning meets split learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 8, 2022, pp. 8485–8493. [6] C. Dwork, “Differential privacy,” in International Colloquium on Automata, Languages, and Programming. Springer, 2006, pp. 1–12. [7] M. Abadi, A. Chu, I. Goodfellow et al., “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC conference on Computer and Communications Security, 2016, pp. 308–318. [8] G. Zhu, Y. Wang, and K. Huang, “Broadband analog aggregation for low-latency federated edge learning,” IEEE transactions on wireless communications, vol. 19, no. 1, pp. 491–506, 2019. [9] S. Pradhan, A. Koc, K. Alemdar et al., “Experimental demonstration of over the air federated learning for cellular networks,” arXiv preprint arXiv:2503.06376, 2025.
13
[10] H. H. Yang, Z. Chen, T. Q. Quek, and H. V. Poor, “Revisiting analog over-the-air machine learning: The blessing and curse of interference,” IEEE Journal of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 406–419, 2021. [11] J. C. Spall, “Multivariate stochastic approximation using a simultaneous perturbation gradient approximation,” IEEE transactions on automatic control, vol. 37, no. 3, pp. 332–341, 1992. [12] J. K. Salmon, M. A. Moraes, R. O. Dror, and D. E. Shaw, “Parallel random numbers: as easy as 1, 2, 3,” in Proceedings of 2011 international conference for high performance computing, networking, storage and analysis, 2011, pp. 1–12. [13] J. Konečnỳ, H. McMahan, F. Yu et al., “Federated learning: Strategies for improving communication efficiency,” arXiv preprint arXiv:1610.05492, 2016. [14] T. Chen, G. Giannakis, T. Sun et al., “LAG: Lazily aggregated gradient for communication-efficient distributed learning,” Advances in Neural Information Processing Systems, 2018. [15] B. McMahan, E. Moore, D. Ramage et al., “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017, pp. 1273–1282. [16] X. Zhang, M. Hong, S. Dhople et al., “FedPD: A federated learning framework with adaptivity to non-iid data,” IEEE Transactions on Signal Processing, vol. 69, pp. 6055–6070, 2021. [17] K. Mishchenko, G. Malinovsky, S. Stich et al., “Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!” in International Conference on Machine Learning, 2022, pp. 15 750– 15 769. [18] O. Maraqa, A. Rajasekaran, S. Al-Ahmadi et al., “A survey of rateoptimal power domain NOMA with enabling technologies of future wireless networks,” IEEE Communications Surveys & Tutorials, vol. 22, no. 4, pp. 2192–2235, 2020. [19] Z. Liu and L. Yang, “Sparse or dense: A comparative study of codedomain noma systems,” IEEE Transactions on Wireless Communications, vol. 20, no. 8, pp. 4768–4780, 2021. [20] H. Sun, X. Ma, and Q. Hu, “Adaptive federated learning with gradient compression in uplink noma,” IEEE Transactions on Vehicular Technology, vol. 69, no. 12, pp. 16 325–16 329, 2020. [21] T. Sery and K. Cohen, “On analog gradient descent learning over multiple access fading channels,” IEEE Transactions on Signal Processing, vol. 68, pp. 2897–2911, 2020. [22] M. Amiri and D. Gündüz, “Machine learning at the wireless edge: Distributed stochastic gradient descent over-the-air,” IEEE Transactions on Signal Processing, vol. 68, pp. 2155–2169, 2020. [23] N. Zhang and M. Tao, “Gradient statistics aware power control for overthe-air federated learning,” IEEE Transactions on Wireless Communications, vol. 20, no. 8, pp. 5115–5128, 2021. [24] K. Yang, T. Jiang, Y. Shi et al., “Federated learning via over-the-air computation,” IEEE Transactions on Wireless Communications, vol. 19, no. 3, pp. 2022–2035, 2020. [25] X. Cao, G. Zhu, J. Xu et al., “Optimized power control for over-theair computation in fading channels,” IEEE Transactions on Wireless Communications, vol. 19, no. 11, pp. 7498–7513, 2020. [26] J. Yao, W. Xu, G. Zhu et al., “Over-the-air multi-task federated learning via cost-effective hybrid beamforming,” IEEE Transactions on Signal Processing, 2025. [27] J. Yao, W. Xu, G. Zhu, K. Huang, and S. Cui, “Energy-efficient edge inference in integrated sensing, communication, and computation networks,” IEEE Journal on Selected Areas in Communications, 2025. [28] G. Zhu, Y. Du, D. Gündüz et al., “One-bit over-the-air aggregation for communication-efficient federated edge learning: Design and convergence analysis,” IEEE Transactions on Wireless Communications, vol. 20, no. 3, pp. 2120–2135, 2020. [29] D. Narayanan, M. Shoeybi, J. Casper, P. LeGresley, M. Patwary, V. Korthikanti, D. Vainbrand, P. Kashinkunti, J. Bernauer, B. Catanzaro et al., “Efficient large-scale language model training on gpu clusters using megatron-lm,” in Proceedings of the international conference for high performance computing, networking, storage and analysis, 2021, pp. 1–15. [30] X. L. Li and P. Liang, “Prefix-tuning: Optimizing continuous prompts for generation,” arXiv preprint arXiv:2101.00190, 2021. [31] E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, W. Chen et al., “Lora: Low-rank adaptation of large language models.” ICLR, vol. 1, no. 2, p. 3, 2022. [32] Y. Sun, Z. Li, Y. Li et al., “Improving LoRA in privacy-preserving federated learning,” arXiv preprint arXiv:2403.12313, 2024.
[33] Y. Cho, L. Liu, Z. Xu et al., “Heterogeneous lora for federated finetuning of on-device foundation models,” in International Workshop on Federated Learning in the Age of Foundation Models in Conjunction with NeurIPS 2023, 2023. [34] Z. Zhang, Y. Yang, Y. Dai et al., “Fedpetuning: When federated learning meets the parameter-efficient tuning methods of pre-trained language models,” in Annual Meeting of the Association of Computational Linguistics 2023, 2023, pp. 9963–9977. [35] S. Malladi, T. Gao, E. Nichani et al., “Fine-tuning language models with just forward passes,” Advances in Neural Information Processing Systems, pp. 53 038–53 075, 2023. [36] Z. Ling, D. Chen, L. Yao et al., “On the convergence of zeroth-order federated tuning for large language models,” in Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2024, p. 1827–1838. [37] Z. Qin, D. Chen, B. Qian et al., “Federated full-parameter tuning of billion-sized language models with communication cost under 18 kilobytes,” 2024. [Online]. Available: https://arxiv.org/abs/2312.06353 [38] M. Xu, D. Cai, Y. Wu et al., “FwdLLM: Efficient FedLLM using forward gradient,” 2024. [Online]. Available: https://arxiv.org/abs/2308.13894 [39] Z. Chen, H. Yang, Z. Li et al., “Zeroth-order over-the-air federated large model tuning over edge networks,” IEEE Wireless Communications Letters, 2025. [40] R. Shokri, M. Stronati, C. Song et al., “Membership inference attacks against machine learning models,” in IEEE Symposium on Security and Privacy, 2017, pp. 3–18. [41] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015, pp. 1322–1333. [42] K. Wei, J. Li, M. Ding et al., “Federated learning with differential privacy: Algorithms and performance analysis,” IEEE transactions on Information Forensics and Security, vol. 15, pp. 3454–3469, 2020. [43] M. Seif, R. Tandon, and M. Li, “Wireless federated learning with local differential privacy,” in IEEE International Symposium on Information Theory, 2020, pp. 2604–2609. [44] A. Sonee and S. Rini, “Efficient federated learning over multiple access channel with differential privacy constraints,” arXiv preprint arXiv:2005.07776, 2020. [45] D. Liu and O. Simeone, “Privacy for free: Wireless federated learning via uncoded transmission with adaptive power control,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 1, pp. 170–185, 2020. [46] L. Zhang, K. Thekumparampil, S. Oh et al., “DPZero: Dimensionindependent and differentially private zeroth-order optimization,” in International Workshop on Federated Learning in the Age of Foundation Models in Conjunction with NeurIPS 2023, 2023. [47] Z. Liu, J. Lou, W. Bao et al., “Differentially private zeroth-order methods for scalable large language model finetuning,” arXiv preprint arXiv:2402.07818, 2024. [48] X. Tang, A. Panda, M. Nasr, S. Mahloujifar, and P. Mittal, “Private finetuning of large language models with zeroth-order optimization,” arXiv preprint arXiv:2401.04343, 2024. [49] B. Waggener and W. N. Waggener, Pulse code modulation techniques. Springer Science & Business Media, 1995. [50] L. Bottou, F. Curtis, and J. Nocedal, “Optimization methods for largescale machine learning,” SIAM review, vol. 60, no. 2, pp. 223–311, 2018. [51] B. Polyak, “Gradient methods for solving equations and inequalities,” USSR Computational Mathematics and Mathematical Physics, vol. 4, no. 6, pp. 17–32, 1964. [52] S. Zhang, S. Roller, N. Goyal et al., “Opt: Open pre-trained transformer language models,” arXiv preprint arXiv:2205.01068, 2022. [53] R. Socher, A. Perelygin, J. Wu et al., “Recursive deep models for semantic compositionality over a sentiment treebank,” in Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, 2013, pp. 1631–1642. [54] P. Rajpurkar, J. Zhang, K. Lopyrev et al., “Squad: 100,000+ questions for machine comprehension of text,” arXiv preprint arXiv:1606.05250, 2016. [55] S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities - A Nonasymptotic Theory of Independence. Oxford University Press, 2013. [Online]. Available: https://doi.org/10.1093/acprof:oso/ 9780199535255.001.0001