Efficient Exact Unlearning for Federated Zeroth-Order Optimization

1

Efficient Exact Unlearning for Federated Zeroth-Order Optimization

arXiv:2610.35211v1 [cs.LG] 26 Oct 2026

Weijun Yin, Yanqing Yao, Falko Dressler, Fellow, IEEE, Di Wang, Member, IEEE, Youming Tao Member, IEEE

Abstract—Federated zeroth-order optimization (FedZOO) reduces the memory and communication costs of collaborative training for edge intelligence by avoiding backpropagation while communicating only random seeds and scalar coefficients. However, existing methods lack efficient mechanisms for exact unlearning to fully remove the influence of training data when users request deletion. A key insight is that total variation stability of the learning algorithm creates overlap between model distributions before and after data deletion, allowing exact unlearning to reuse computation through coupling. Based on this observation, we jointly design two stable zeroth-order learning algorithms and their corresponding exact-unlearning procedures: F ED ZOO-S obtains stability through client and mini-batch subsampling, enabling F ED ZOUL-S to perform efficient unlearning by preserving earlier updates and restarting from the first affected step. F ED ZOO-NS further combines subsampling with Gaussian noise to increase overlap between update distributions; F ED ZOUL-NS exploits this overlap through rejection–reflection coupling to reuse affected updates when the coupling is accepted. We prove exact unlearning for both algorithms: the model and saved state have the same joint distribution as retraining with the corresponding learner on retained data. We further establish stability and convergence guarantees for the learning algorithms and derive upper bounds on expected unlearning cost. Experiments demonstrate effective unlearning with competitive model utility and up to 56.1% less cumulative unlearning time than re-optimization. Compared with first-order baselines, our methods reduce communication overhead by up to approximately four orders of magnitude. Index Terms—Federated learning, Exact Unlearning, ZerothOrder Optimization, Total Variation Stability

I. I NTRODUCTION Driven by advances in mobile and IoT hardware, edge intelligence has developed rapidly in recent years. Federated learning (FL) enables collaborative optimization across edge devices by allowing them to exchange model parameters or gradients without moving data out of the local domain [1]. However, practical deployment remains constrained by limited memory and communication resources, with growing model sizes further amplifying these challenges. Techniques such as quantization [2]–[4], sparsification [5]–[7], pruning and Weijun Yin and Yanqing Yao are with the School of Cyber Science and Technology, Beihang University, Beijing 100191, China, and also with the Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, Beihang University, Beijing 100083, China (e-mail: yinweijun@buaa.edu.cn; yaoyq@buaa.edu.cn). Falko Dressler and Youming Tao are with the School of Electrical Engineering and Computer Science, TU Berlin, 10623 Berlin, Germany (e-mail: dressler@ccs-labs.org; tao@ccs-labs.org). Di Wang is with the Division of Computer, Electrical and Mathematical Sciences and Engineering, King Abdullah University of Science and Technology, Saudi Arabia (email: di.wang@kaust.edu.sa).

submodel training [8]–[11], and knowledge distillation [12]– [14] can reduce computation or communication costs. More recently, parameter-efficient and subspace-based federated finetuning methods have been developed to adapt large language models (LLMs) with fewer trainable parameters [15], [16]. Nevertheless, these training approaches still rely on backpropagation, whose intermediate activations can impose substantial memory overhead even when only a small subset of parameters is trainable. Exchanging tensor-valued updates can also remain costly over bandwidth-constrained edge networks. Federated zeroth-order optimization (FedZOO) provides a promising alternative. Unlike first-order methods, zerothorder optimization (ZOO) estimates descent directions using only function evaluations and therefore avoids backpropagation [17]. This substantially reduces the memory required for optimization. Moreover, recent FedZOO methods exploit shared randomness to represent high-dimensional perturbations by random seeds and scalar coefficients [18], enabling communication costs that do not scale with the model dimension. In particular, a fixed finite seed pool allows accumulated zeroth-order updates to be represented in a compact seedcoordinate space. These properties make FedZOO particularly attractive for collaborative optimization of large models on resource-constrained edge devices. Existing FedZOO methods, however, do not address machine unlearning (MU). Federated systems may receive requests to remove training samples because of data corrections, user withdrawal, or privacy requirements such as the right to be forgotten under regulations under GDPR [19]. Simply deleting the requested samples from local storage is insufficient because their effects may already have been incorporated into the global model. Federated unlearning therefore aims to remove these historical contributions from the learned model without repeating the entire training process. This requirement is especially relevant to edge intelligence, where participating devices may continuously contribute user-generated and potentially sensitive data. Achieving efficient exact unlearning for FedZOO is challenging. Existing federated unlearning methods are largely designed around first- or second-order optimization and can reintroduce backpropagation, high-dimensional model states, or tensor-level communication, thereby losing the resource advantages that motivate FedZOO. Moreover, exact unlearning requires distributional equivalence to rerunning the learning algorithm on the retained data [20], for which retraining from scratch is always valid but computationally expensive. A key insight from stability-based exact unlearning is that this difficulty can be addressed from the learning side [20]–

2

[22]. If a randomized learning algorithm is stable in total variation under a single-sample change, then the output distributions on neighboring datasets overlap, creating opportunities to reuse computation through an appropriate coupling. This leads to a fundamental question in our setting: How can we design federated zeroth-order learning algorithms that are TV-stable while retaining the communication and memory advantages of FedZOO? To answer this question, we develop two TV-stable FedZOO learning algorithms and their corresponding exact-unlearning procedures, built on a common seed-encoded representation. The first, F ED ZOO-S, obtains stability from client and minibatch subsampling: a single sample changes the realized trajectory only when its client participates and the sample is selected for a local update. Its unlearning counterpart, F ED ZOUL-S, therefore preserves the unaffected prefix and replays only from the first affected step. The second, F ED ZOO-NS, augments subsampling with Gaussian randomization. The added noise creates overlap between the conditional update distributions on neighboring datasets, allowing some affected updates to be coupled rather than immediately replayed. Its unlearning counterpart, F ED ZOUL-NS, exploits this overlap through rejection–reflection coupling so that some affected realized updates can still be reused exactly. Our contributions are summarized as follows. (1) We formulate efficient exact federated unlearning for zeroth-order optimization through the lens of algorithmic total variation stability. Rather than treating unlearning as a post hoc correction to an arbitrary FedZOO procedure, we design the learning algorithm itself to be TV-stable, so that neighboring training datasets induce overlapping output distributions that can be exploited through coupling for computation reuse. At the same time, we retain the fixed finite seed representation of FedZOO to avoid highdimensional model-update communication. (2) We propose F ED ZOO-S, a TV-stable federated zerothorder learning algorithm whose stability arises from client and mini-batch subsampling, together with its exactunlearning algorithm F ED ZOUL-S. A deletion leaves the realized trajectory unchanged when the deleted samples have not contributed to any realized local update. Otherwise, F ED ZOUL-S preserves the unaffected prefix and replays only the suffix starting from the first affected local step. (3) We further propose F ED ZOO-NS, which augments subsampling with Gaussian randomization, together with its corresponding exact-unlearning algorithm F ED ZOULNS. The added noise creates overlap between the conditional update distributions on neighboring datasets, enabling rejection–reflection coupling. Consequently, some affected realized updates can still be reused exactly, and replay is required only after the first rejected coupling. (4) We establish exact-unlearning guarantees for both learning–unlearning pairs and analyze their TV stability, optimization utility, and unlearning efficiency. We further evaluate their optimization and unlearning performance

across federated learning settings with conventional models and large language models. II. R ELATED W ORK A. Federated Zeroth-Order Optimization. In recent years, zeroth-order optimization (ZO), has shown strong potential in FL, especially in resource-constrained edge collaboration settings, because it avoids backpropagation. Fang et al. [23] propose FedZO as one of the first derivative free federated ZO methods. For LLMs, Ling et al. [24] propose FedMeZO, which significantly reduces memory overhead and provides convergence analysis. Later, FedKSeed [18] and DeComFL [25] use scalar gradients and random seeds to synchronize perturbation randomness, achieving dimensionindependent communication between edge nodes and the cloud. HiSo [26] further accelerate the convergence efficiency of federated ZO. At the same time, since transmitting estimated gradients or scalar gradients may expose privacy risks, methods such as DPZero [27], DP-ZOSO [28] and DPAggZO [29] combine differential privacy with zeroth-order gradient estimation. These methods inject carefully calibrated noise during training to provide rigorous privacy guarantees. It is worth noting that this noise-based design not only strengthens privacy protection, but also motivates the noise perturbation strategy in our TV stable algorithm. B. Federated Unlearning. Federated unlearning (FU) aims to remove the influence of specified training data from a collaboratively learned model. Existing approaches can be broadly categorized into approximate and exact unlearning according to their guarantees relative to retraining on the retained data. Approximate methods seek to recover retraining-like behavior through model correction and gradient calibration [30]–[34], perturbation [35]–[39], or knowledge distillation [40], [41]. Related work on LLM unlearning also seeks to remove targeted knowledge while preserving useful model capabilities [42], [43]. Although some approaches provide certified guarantees that bound distributional discrepancies through calibrated randomization [37]– [39], these guarantees do not establish exact equality between the unlearning and retraining distributions. Exact FU requires the unlearning output to follow the same distribution as training on the retained data. To avoid full retraining, stabilitybased approaches exploit overlap between learning distributions to reuse prior computation [20], [22]. However, these methods are developed around gradient-based training and model- or curvature-level states, which do not directly retain the memory and communication advantages of zeroth-order optimization. Extending them to FedZOO requires more than replacing the gradient oracle: seed-and-scalar updates change the state needed for replay and the transition distributions used for coupling. We therefore jointly design TV-stable zerothorder learners and exact sample-level unlearning procedures around compact seed-encoded update histories. Our procedures reuse computation through subsampling and Gaussian coupling while preserving both the resource advantages of FedZOO and exact joint distributional equivalence of the model and saved state to retraining.

3

III. P RELIMINARIES A. Federated Zeroth-Order Optimization Consider a federated optimization system with M clients, where client c ∈ [M ] holds a finite local dataset Dc = {xc,1 , . . . , xc,nc } of size nc = |Dc |. The clients collaboratively optimize a global model w ∈ Rd under the coordination of a server. We consider the uniformly weighted finite-sum objective M

1 X ℓ(w; x). nc w∈Rd x∈Dc (1) Training proceeds for R communication rounds. In each round, m clients participate, and each participating client performs E local optimization steps before the server uniformly aggregates their updates. Zeroth-order optimization estimates descent directions using function evaluations without backpropagation. Given a model w, a sample x, and a perturbation z ∼ N (0, Id ), the two-point scalar gradient is min f (w) :=

1 X fc (w), M c=1

fc (w) :=

ℓ(w + µz; x) − ℓ(w − µz; x) , g(w; x, z) = 2µ

(W ul , S ul ) = U (W , S, {Dc,ul }c∈Cul ) . Definition 1 (Exact Federated Unlearning). A federated unlearning algorithm U is exact with respect to a randomized learning algorithm O if, for every federated dataset D and every valid deletion request, U (O(D), {Dc,ul }c∈Cul ) = O(D− ),

(2)

(5)

d

q

η XX g(w; xi , z i,j )z i,j , bq j=1

We consider valid deletion requests for which every retained local dataset remains large enough for the prescribed minibatch sampling, i.e., |Dc− | ≥ b for all affected clients. The request may arrive during training. We denote by (Rul , tul ) the local training position immediately preceding the request; that is, the request arrives immediately after local step tul of round Rul . Given the current model and saved state, an unlearning algorithm U updates them according to the deletion request:

d

where µ > 0 is the perturbation scale. The corresponding zeroth-order gradient estimator is g(w; x, z)z. For a mini-batch B of size b, suppose that q perturbations {z i,j }qj=1 are used for each xi ∈ B. One local step is the mini-batch averaged zeroth-order update w+ = w −

Dc,ul ⊆ Dc the samples requested for deletion from client c ∈ Cul . The retained federated dataset is ( Dc \ Dc,ul , c ∈ Cul , − − − − D = {D1 , . . . , DM }, Dc = Dc , c∈ / Cul .

(3)

xi ∈B

where all bq scalar gradients are evaluated at the same preupdate model w. Following the seed-based representation of FedKSeed [18], a perturbation can be reproduced from its random seed when the same pseudorandom number generator is used across devices. A fixed shared pool of K seeds can therefore represent zeroth-order updates through their scalar coefficients in seedcoordinate space, avoiding the transmission and storage of ddimensional update vectors. B. Federated Unlearning Let D = {D1 , . . . , DM } denote the federated dataset. A randomized federated learning algorithm O produces a model output together with auxiliary state maintained for subsequent unlearning: (W , S) ∼ O(D). (4) Here, W denotes the model output and S collects the internal state saved by the learning procedure. The randomness of O may include client participation, data sampling, zerothorder perturbations, and other algorithmic randomness. We use Oout (D) to denote the marginal distribution of the model output W . An unlearning request specifies samples to be removed from one or more clients. Let Cul be the set of affected clients and

where = denotes equality in distribution over both the model output and the maintained internal state. Thus, exact unlearning requires the post-unlearning procedure to have the same distribution as rerunning the original learning algorithm on the retained federated dataset, rather than merely producing a nearby model. C. Total Variation Stability For two probability measures P and Q on the same measurable space, their total variation (TV) distance is TV(P, Q) = sup |P (A) − Q(A)|,

(6)

A

where the supremum is over measurable events A. When P and Q admit densities p and q with respect to a common reference measure, 1 TV(P, Q) = ∥p − q∥1 . 2 ′ For two federated datasets D = {Dc }M = c=1 and D {Dc′ }M , define c=1

∆(D, D′ ) =

M X

|Dc △Dc′ |.

c=1

We call them sample-level adjacent, denoted by D ∼ D′ , if ∆(D, D′ ) = 1. Following the stability-based exact-unlearning framework, TV stability is defined on the marginal distribution of the learning algorithm’s model output, rather than on its auxiliary internal state. Definition 2 (ρ-Sample-Level TV Stability). A randomized federated learning algorithm O is ρ-sample-level TV stable if sup TV (Oout (D), Oout (D′ )) ≤ ρ,

D∼D ′

(7)

4

where ρ ∈ [0, 1] is the stability parameter. TV stability therefore controls how much the distribution of the learned model can change after modifying a single training sample. For neighboring datasets, a smaller ρ implies greater overlap between the two output distributions, which can be exploited by coupling-based unlearning to reuse computations from the original training trajectory.

and initializes ar,0 c = 0K . The local accumulator records only the updates generated by client c during the current round. Each local step consists of one mini-batch averaged zerothK order update. Specifically, let ∆ar,t denote the seedc ∈ R coordinate increment computed at local step t from wr,t−1 . c All scalar gradients in this step are evaluated at the same model wr,t−1 , accumulated into ∆ar,t c c , and applied jointly: r,t−1 ar,t + ∆ar,t c = ac c ,

IV. O UR M ETHOD We develop two pairs of federated learning and exactunlearning algorithms. Both pairs build on a common seedencoded representation of zeroth-order updates, which allows the realized training trajectory to be stored and replayed without retaining high-dimensional model updates. The first pair, F ED ZOO-S and F ED ZOUL-S, exploits client and sample subsampling: if a deleted sample has not entered the realized trajectory, the existing state remains valid; otherwise, exact unlearning replays the affected suffix. The second pair, F ED ZOO-NS and F ED ZOUL-NS, further randomizes local zeroth-order updates with Gaussian noise. The resulting overlap between update distributions on neighboring datasets allows some affected updates to be reused through coupling, reducing the need for replay. A. Seed-Encoded Zeroth-Order Updates All four algorithms use the same compact representation of zeroth-order updates. At initialization, the server generates a finite pool of K distinct perturbation seeds S = {s1 , . . . , sK }, which is shared by the server and all clients and remains fixed throughout training. With a fixed pseudorandom number generator, each seed sk deterministically generates a Gaussian perturbation z k = Perturb(sk ) ∈ Rd , where z k ∼ N (0, Id ). For model w, sample x, and seed sk , define the two-point zeroth-order scalar gradient as g(w; x, sk ) =

ℓ(w + µz k ; x) − ℓ(w − µz k ; x) . 2µ

The corresponding zeroth-order gradient estimator is g(w; x, sk )z k . Hence, once S is shared, an update along z k is completely specified by its seed index and scalar coefficient, rather than by a d-dimensional vector. Because the seed pool is fixed and reused throughout training, coefficients associated with the same perturbation can be accumulated in seed-coordinate space. Let ar = (ar1 , . . . , arK ) ∈ RK denote the global scalar-gradient accumulator after round r, where ark is the cumulative coefficient associated with z k . The corresponding global model is reconstructed as r

0

Rec(a ) = w − η

K X

ark z k ,

(8)

k=1

and we write wr = Rec(ar ). Thus, the persistent training state is represented by the K-dimensional accumulator ar , while the full model is reconstructed only when needed. At the beginning of round r, client c reconstructs wr−1 from ar−1

r,t−1 wr,t −η c = wc

K X

(9)

∆ar,t c,k z k .

(10)

k=1

Equivalently, r−1 wr,t −η c =w

K X

ar,t c,k z k .

k=1

After local training, the server aggregates the final local accumulators of the participating clients and adds the resulting increment to ar−1 , thereby obtaining ar . Exact unlearning additionally requires the realized randomness that determines the training trajectory to be recoverable. We therefore record the sampled clients, mini-batches, and perturbation seeds needed to reproduce each realized update. Distinct sources of randomness used by the algorithms are generated from independent random streams unless explicitly coupled by the unlearning procedure. B. Subsampling-Stable Learning and Unlearning Learning: FedZOO-S. A deletion does not affect the realized training trajectory if the deleted sample has never been used to compute an update. We exploit this property through two levels of subsampling: only a subset of clients participates in each communication round, and each participating client computes its local zeroth-order updates from randomly sampled mini-batches. This gives our first learning algorithm, F ED ZOO-S. At round r, the server uniformly samples C r ⊆ [M ] with r |C | = m and sends the current global accumulator ar−1 to the participating clients. Each c ∈ C r initializes r−1 wr,0 ), c = Rec(a

ar,0 c = 0K ,

and performs E local steps. At local step t, client c samples a mini-batch Bcr,t ⊆ Dc of size b uniformly without replacement. For each xi ∈ Bcr,t , it further samples q distinct seeds Sr,t c,i = {si,1 , . . . , si,q } ⊆ S uniformly without replacement. Let z i,j = Perturb(si,j ). All scalar gradients within the local step are evaluated at the same pre-update model: ℓ(wr,t−1 + µz i,j ; xi ) − ℓ(wr,t−1 − µz i,j ; xi ) c c . (11) 2µ The bq scalar gradients jointly form one mini-batch averaged zeroth-order update. For each sk ∈ S, define X 1 r,t ∆ar,t gi,j , (12) c,k = bq r,t r,t gi,j =

xi ∈Bc , j∈[q]: si,j =sk

5

where an empty sum is zero. The client then applies r,t−1 ar,t + ∆ar,t c = ac c , K X r,t−1 wr,t −η ∆ar,t c = wc c,k z k . k=1

For subsequent unlearning, the client r,t {Sr,t c,i }xi ∈Bcr,t , and ac . After the local steps, the server updates 1 X r,E ac , ar = ar−1 + m r

(13) (14) records

Bcr,t ,

(15)

c∈C

and records C r and ar . Algorithm 1 summarizes F ED ZOO-S. The two levels of subsampling directly enable efficient unlearning. A sample affects the realized trajectory only when its client participates in a round and the sample is subsequently selected into a local mini-batch. If this never occurs before an unlearning request, deleting the sample does not invalidate the realized trajectory. Otherwise, the first local step containing the sample identifies the earliest point from which replay is necessary. Exact unlearning: FedZOUL-S. Let Cul be the clients involved in an unlearning request, and let Dc,ul ⊆ Dc contain the samples to be deleted from client c. Suppose the request arrives immediately after local step (Rul , tul ). For later use, define the next training position as ( (r, t + 1), t < E, Next(r, t) = (r + 1, 1), t = E. Using the client-participation sets and mini-batches recorded during F ED ZOO-S, F ED ZOUL-S searches chronologically over the realized prefix up to (Rul , tul ) for the earliest step (r⋆ , t⋆ ) satisfying ⋆

⋆

Bcr ,t ∩ Dc,ul ̸= ∅

(16)

⋆

for some c ∈ Cul ∩ C r . If no such step exists, none of the deleted samples has contributed to the realized trajectory. After removing the requested samples, training therefore continues from Next(Rul , tul ) using the current state, without replaying any previous step. Otherwise, the algorithm preserves the entire trajectory before (r⋆ , t⋆ ) and restores the optimization state immediately ⋆ preceding this step. Specifically, it loads ar −1 and, for each r ⋆ ,t⋆ −1 r⋆ and reconstructs c ∈ C , restores ac ⋆

⋆

⋆

wrc ,t −1 = Rec(ar −1 ) − η

K X

⋆

the resulting model and saved state have the same distribution as a F ED ZOO-S run on the retained datasets. Algorithm 2 summarizes the procedure. We state the algorithm for setvalued deletion requests; the theoretical analysis considers a single deletion, with multiple requests handled sequentially. The limitation of F ED ZOUL-S is that once a deleted sample has contributed to a local update, the trajectory must be replayed from that update onward. The next learning–unlearning pair adds Gaussian randomization so that an affected update can sometimes be reused as well.

⋆

arc,k,t −1 z k .

(17)

k=1

Training then resumes from (r⋆ , t⋆ ) on the retained datasets using the same F ED ZOO-S procedure. All newly generated states replace their original counterparts. The preserved prefix contains no update involving a deleted sample. The coupling analysis in Section B-A shows that the two branches of F ED ZOUL-S jointly transport the original training law to the retained-data law: the realized prefix is preserved when no deleted sample appears, and the trajectory is regenerated from the first affected step otherwise. Therefore,

C. Noise-Stable Learning and Unlearning Learning: FedZOO-NS. F ED ZOO-S avoids replay when deleted samples have not contributed to the realized trajectory, but an affected update still requires replay of the remaining suffix. To further reduce this cost, we randomize each local zeroth-order update with Gaussian noise. The resulting overlap between update distributions on neighboring datasets allows some affected realized updates to be reused through coupling. We call the resulting learning algorithm F ED ZOO-NS. Client, mini-batch, and perturbation-seed sampling follow F ED ZOO-S. At local step (r, t), let Bcr,t be the sampled minir,t batch and Sr,t c,i the q perturbation seeds sampled for xi ∈ Bc . All scalar gradients are evaluated at the same pre-update model : wr,t−1 c r,t gi,j =

− µz i,j ; xi ) + µz i,j ; xi ) − ℓ(wr,t−1 ℓ(wr,t−1 c c , (18) 2µ

where z i,j = Perturb(si,j ). We clip each scalar gradient at level C and normalize it according to the mini-batch averaged update: 1 r,t hr,t clipC (gi,j ). (19) i,j = bq Fix a deterministic ordering of the bq sample–seed pairs bq and collect their coefficients into hr,t c ∈ R . Client c independently draws 2 ξ r,t c ∼ N (0, σρ Ibq ) and forms

e r,t = hr,t + ξ r,t . h c c c

(20)

The Gaussian noise is independent of the client, mini-batch, and perturbation-seed sampling. The noisy coefficient vector is mapped to the seedcoordinate increment ∆e ar,t ∈ RK . For each seed sk ∈ S, c P r,t e r,t e r,t the increment is ∆e ac,k = xi ∈Bcr,t , j∈[q]: hi,j , where hi,j si,j =sk

e r,t corresponding to the sampled denotes the component of h c pair (xi , si,j ). The sum includes all sampled pairs sharing sk and is zero if no such pair is selected. The client then updates r,t−1 ar,t + ∆e ar,t c = ac c , r,t−1 wr,t −η c = wc

K X

∆e ar,t c,k z k .

(21) (22)

k=1

After E local steps, the server performs the same uniform aggregation as in F ED ZOO-S: 1 X r,E ar = ar−1 + ac . (23) m r c∈C

6

For subsequent unlearning, each client records Bcr,t , r,t r,t e r,t {Sr,t c,i }xi ∈Bcr,t , hc , and ac . The clean vector hc need not be stored, since it can be recomputed from the saved preupdate state, mini-batch, and perturbation seeds. Algorithm 3 summarizes F ED ZOO-NS. Exact unlearning: FedZOUL-NS. Consider a deletion request {Dc,ul }c∈Cul arriving immediately after local step (Rul , tul ). F ED ZOUL-NS scans the realized prefix up to the request in chronological order. For an affected client c ∈ Cul ∩ C r , define

r,t If Bc,ul = ∅, the recorded local update is unaffected and is preserved. Otherwise, the algorithm couples the recorded minibatch to a mini-batch distributed as a uniform sample from the r,t retained local dataset. It removes Bc,ul and replaces these samples by the same number of retained samples, drawn uniformly without replacement from the retained dataset while excluding the samples already present in the mini-batch. Denote the resulting mini-batch by (Bcr,t )′ . The perturbation-seed sets of retained samples are unchanged, while each replacement sample inherits the seed set associated with the deleted sample that it replaces. Since data sampling and perturbation-seed sampling are independent, this produces the required coupled realization of the sampling randomness. Using the saved pre-update model, the coupled mini-batch, and the associated seeds, the client recomputes the clean ′ coefficient vector (hr,t c ) . Conditioned on the pre-update state and sampling realizations, the original and retained-data randomized updates follow

2 ′ 2 P = N hr,t Q = N (hr,t c , σρ Ibq , c ) , σρ Ibq .

Let p and q denote their densities. For the recorded realization e r,t , the rejection step accepts with probability h c ) ( e r,t ) q(h c r,t . (24) αc = min 1, e r,t ) p(h c

e r,t − hr,t ∥2 − ∥h e r,t − (hr,t )′ ∥2 ∥h c c c c 2 2 r,t αc = min 1, exp 2σρ2

.

The local model and accumulator therefore remain unchanged; only the saved mini-batch and its sample–seed correspondence are replaced by the coupled retained-data realization. If the test rejects, the algorithm uses reflection to obtain a realization from the retained-data transition. Let mr,t c =

For dr,t c ̸= 0, define er,t c =

dr,t c . ∥dr,t c ∥2

r,t ′ hr,t c + (hc ) . 2

r,t−1 ar,t + ∆e ar,t c = ac c , K X

∆e ar,t c,k z k .

(27) (28)

k=1

The saved state of this local step is then replaced by   e r,t )′ , ar,t , r,t ′ , (h (Bcr,t )′ , {Sr,t } c c c,i xi ∈(Bc ) namely, the coupled mini-batch and sample–seed correspondence, the reflected noisy coefficient vector, and the corrected local accumulator. All subsequent states depend on this corrected endpoint and are therefore regenerated on the retained datasets. If a rejection occurs at the last local step t = E, the corrected local endpoint first replaces its original counterpart and the server recomputes 1 X r,E ar = ar−1 + ac m r c∈C

before training proceeds from Next(r, E) = (r + 1, 1). If every affected step up to the request is accepted, the realized optimization state remains unchanged. After removing the requested samples, training continues from Next(Rul , tul ). If a rejection occurs at (r⋆ , t⋆ ), training instead continues from Next(r⋆ , t⋆ ) using the corrected state. Algorithm 4 summarizes the procedure. Thus, F ED ZOUL-NS first exploits subsampling to preserve unaffected steps and then uses Gaussian coupling to reuse some affected randomized updates. Replay is required only after the first rejected coupling.

!)

(25) If the test accepts, the recorded noisy coefficient vector is reused: e r,t )′ = h e r,t . (h c c

r,t ′ r,t dr,t c = (hc ) − hc ,

(26)

If the two clean coefficient vectors coincide, then P = Q and the step is accepted directly. The reflected vector is mapped to the fixed seed-coordinate space to obtain ∆e ar,t c and is applied to the state immediately preceding (r, t):

r,t−1 wr,t −η c = wc

r,t Bc,ul = Bcr,t ∩ Dc,ul .

Equivalently, (

The reflected coefficient vector is D r,t E e r,t )′ = h e r,t − 2 h e − mr,t , er,t er,t . (h c c c c c c

V. T HEORETICAL A NALYSIS We now explain why the proposed learning and unlearning procedures work. Two questions are central. First, after a sample is deleted, can we recover exactly the state that would have been obtained by training on the retained data, without rerunning everything from the beginning? Second, because all zeroth-order updates reuse the same finite seed pool, what optimization guarantee can we still give for the original federated objective? We keep the discussion here at the level of the main ideas and results; the complete statements and proofs are given in Appendix B. For reference, T = RE denotes the total number of local positions. For a deletion of x− from client c− , let nc− be that client’s data size immediately before deletion, and let n be a lower bound on such local dataset sizes. If the request arrives after round Rul and local step tul , then Tul = (Rul −1)E +tul positions have already been executed.

7

Algorithm 1: FedZOO-S: Subsampling-Stable Federated ZOO Input: w0 , R, E, K, q, b, m, η, µ. Output: wR . 1 Initialize fixed seed pool S = {s1 , . . . , sK } and a0 = 0K ; 2 for r = 1, . . . , R do 3 Sample C r ⊆ [M ], |C r | = m, uniformly without replacement; 4 foreach c ∈ C r in parallel do r−1 5 wr,0 ); ar,0 c ← Rec(a c ← 0K ; 6 for t = 1, . . . , E do 7 Sample Bcr,t and {Sr,t c,i }xi ∈Bcr,t ; 8 Compute ∆ar,t by Eqs. (11)–(12); c r,t 9 Update (wr,t , a ) by Eqs. (13)–(14); c c
r,t ; }, a 10 save Bcr,t , {Sr,t c c,i P 1 r,E 11 ar ← ar−1 + m c∈C r ac ; 12 save(C r , ar ); 13

return Rec(aR );

Algorithm 3: FedZOO-NS: Noise-Stable Federated ZOO Input: w0 , R, E, K, q, b, m, η, µ, C, σρ . Output: wR . 1 Initialize fixed seed pool S = {s1 , . . . , sK } and a0 = 0K ; 2 for r = 1, . . . , R do 3 Sample C r ⊆ [M ], |C r | = m, uniformly without replacement; 4 foreach c ∈ C r in parallel do r−1 5 wr,0 ); ar,0 c ← Rec(a c ← 0K ; 6 for t = 1, . . . , E do 7 Sample Bcr,t and {Sr,t c,i }xi ∈Bcr,t ; 8 Compute hr,t by Eqs. (18)–(19); c 2 9 Draw ξ r,t ∼ N (0, σ I c ρ bq ) and set r,t r,t r,t e ←h +ξ ; h c

10 11 12 13

Algorithm 2: FedZOUL-S: Exact Unlearning by Subsampling Input: Deletion request {Dc,ul }c∈Cul after (Rul , tul ); saved FedZOO-S states. Output: Unlearned model wR . 1 affected ← false; 2 for each (r, t) ⪯ (Rul , tul ) in chronological order do 3 foreach c ∈ Cul ∩ C r in parallel do 4 affectedc ← 1{Bcr,t ∩ Dc,ul ̸= ∅}; W 5 if c∈Cul ∩C r affectedc then 6 (r⋆ , t⋆ ) ← (r, t); 7 affected ← true; 8 break; Remove Dc,ul from each affected local dataset; if affected then 11 Restore the saved state immediately before (r⋆ , t⋆ ); 12 Continue FedZOO-S from (r⋆ , t⋆ ) on the retained datasets; 13 else 14 Continue FedZOO-S from Next(Rul , tul ) using the current state; 9

10

15

return wR ;

A. Stability, Exact Unlearning, and Cost The analysis of F ED ZOO-S starts from a simple observation: deleting a sample can only change the realized trajectory if its client is selected and the sample is actually drawn into a local mini-batch. We therefore couple the executions before and after deletion by sharing all randomness until that first event occurs. Up to that point, the two executions are identical. Since one local position hits the deleted sample with probability (m/M )(b/nc− ), the probability of a hit within

14 15

r,t

c

c

e to ∆e Map h ar,t c c ; r,t r,t Update (w , a c c ) by Eqs. (21)–(22);  r,t r,t e r,t , ar,t ; save B , {S }, h c

1 ar ← ar−1 + m r r save(C , a );

c,i

c

c

r,E c∈C r ac ;

P

return Rec(aR );

the first τ positions is at most min{1, τ mb/(M nc− )}. This gives the TV-stability result in Theorem 1 of Appendix B-A; in particular, T mb/(M n) ≤ ρ is sufficient for ρ-TV stability. The same coupling already contains the unlearning algorithm. If the deleted sample was never used, the current state is already distributed exactly as training on the retained data. If it was used, the two executions agree until its first occurrence, so only the computation after that point has to be regenerated. This is the idea behind F ED ZOUL-S. Theorem 2 in Appendix B-A proves exact unlearning for one deletion, and Corollary 1 in the same subsection extends the argument to a non-adaptive stream of deletions. F ED ZOO-NS begins with the same subsampling effect, but the added Gaussian noise gives us another way to keep previously computed updates. When deletion changes a sampled mini-batch, the mean of the noisy coefficient vector changes, but its covariance does not. The two Gaussian transition laws therefore overlap. Appendix B-B quantifies this overlap by coupling the mini-batches and sample–seed pairs first and then bounding the resulting Gaussian discrepancy. Theorem 3 gives the final TV bound. A convenient sufficient noise level is ( ) r 2C Tm 2C σρ = max , (29) √ , √ b q n qρ M p as stated in Corollary 2 of Appendix B-B. The factor m/M appears because client participation is sampled once per round and then shared across the E local steps. For unlearning, this Gaussian overlap is used constructively. At an affected local step, F ED ZOUL-NS first asks whether the previously generated noisy update is also valid under the retained-data transition. If so, it is kept. Otherwise, a reflection

8

Algorithm 4: FedZOUL-NS: Exact Unlearning by Rejection–Reflection Input: Deletion request {Dc,ul }c∈Cul after (Rul , tul ); saved FedZOO-NS states. Output: Unlearned model wR . 1 reject ← false; 2 for each (r, t) ⪯ (Rul , tul ) in chronological order do 3 foreach c ∈ Cul ∩ C r in parallel do 4 rejectc ← false; r,t 5 Bc,ul ← Bcr,t ∩ Dc,ul ; r,t 6 if Bc,ul ̸= ∅ then 7 Construct coupled mini-batch (Bcr,t )′ and its sample–seed correspondence; r,t ′ 8 Recompute hr,t c and (hc ) ; 9 Draw u ∼ Unif(0, 1); 10 if u ≤ αcr,t in Eq. (24) then 11 Replace the saved mini-batch and sample–seed correspondence by the coupled realization; 12 else e r,t )′ by Eq. (26); 13 Compute (h c

17

e r,t )′ to ∆e Map (h ar,t c c ; r,t−1 + ∆e ar,t ar,t c ; c ← ac P K r,t−1 − η ← w ar,t wr,t c c  k=1 ∆e c,k z k ;  r,t r,t ′ e r,t )′ , ar,t ; r,t ′ , (h save (B ) , {S }

18

rejectc ← true;

14 15 16

19 20 21

c

if

c,i xi ∈(Bc )

c

c

W

c∈Cul ∩C r rejectc then (r⋆ , t⋆ ) ← (r, t); reject ← true; break;

Remove Dc,ul from each affected local dataset; if reject then 24 if t⋆ = E then ⋆ 25 Recompute ar from the corrected local endpoints by Eq. (23);

22 23

Continue FedZOO-NS from Next(r⋆ , t⋆ ) using the corrected state; 27 else 28 Continue FedZOO-NS from Next(Rul , tul ) using the current state; 26

29

return wR ;

coupling produces an update with the correct retained-data law, and training continues from the next position. Theorem 4 in Appendix B-C proves that this procedure gives exact unlearning of the complete maintained state, and Corollary 3 in the same subsection covers a non-adaptive stream of deletions. Proposition 1 further bounds the probability that replay is triggered before aprequest √at Tul ; under Eq. (29), it is at most min{1, ρTul m/M / 2πT }. This replay probability is different from the final-model TV parameter ρ: one belongs to the particular transitionwise coupling used for unlearning,

while the other measures the distance between the final output laws. The cost analysis follows the same picture. For F ED ZOULS, work is repeated only if the deleted sample was used, and replay begins at its first occurrence. For F ED ZOUL-NS, affected updates are checked first and replay begins only after the first rejection, so some computation can still be retained even after the deleted sample has appeared. Theorem 5 and Corollary 4 in Appendix B-D give the corresponding lossevaluation, communication, and request-stream bounds. The important point is that the saving comes from reusing computation that can be coupled exactly to retained-data training; no approximation to retraining is introduced. B. Optimization with a Finite Seed Pool We next ask whether the same finite seed pool that makes communication and unlearning efficient still permits meaningful optimization. Seed reuse does not change the federated objective; it only restricts the directions in which√the model can move. Let Z = [z 1 , . . . , z K ] and A = Z/ K. Every iterate can be written as w = w0 + Au for some u ∈ RK . Hence the algorithm is optimizing the original objective on the affine space generated by the seed pool, with 1 ∥Z ⊤ ∇f (w)∥2 . (30) K The quantity on the right is therefore the gradient energy seen along the shared seed directions. Because the columns of Z need not be orthogonal, it should not be interpreted as an orthogonal projection. Appendix B-E gives the corresponding parameterization in detail. The convergence proof then follows the actual seedcoordinate update produced at each local step. What matters is its conditional bias, its variance, and its second moment. For F ED ZOO-S, the bias comes from the two-point finite difference. For F ED ZOO-NS, clipping adds bias and the Gaussian perturbation adds variance. Appendix B-F derives these quantities and states the required regularity conditions. Writing βA , νA , and GA for the corresponding uniform bounds, LZ for the smoothness constant in seed coordinates, ζZ for client heterogeneity, and χm = (M − m)/(m(M − 1)) for the finite-population client-sampling factor when M > 1 (with χm = 0 for M = 1), Theorem 6 in Appendix B-F shows that, whenever 4ηLZ E ≤ 1,   R 1 X 1 E ∥Z ⊤ ∇f (wr−1 )∥2 Z R r=1 K   νA2 2(f (w0 ) − f ⋆ ) 2 2 + 6βA + 8LZ η Eχm ζZ + ≤ ηER m 2 2 2 2 + 2LZ η E GA , (31) ∥∇FZ (u)∥2 =

where f ⋆ is any finite lower bound of the global objective. The four terms have a simple interpretation: finite-horizon optimization error, finite-difference or clipping bias, stochastic variation together with client heterogeneity, and the drift accumulated across local steps. In F ED ZOO-NS, the noise required for stability enters the variance and second-moment

9

terms, so the cost of making unlearning easier appears directly in the optimization bound. For a fixed training horizon ER, the stepsize η balances the first term, which scales as 1/(ηER), against the leading stochastic term, which grows linearly with η. Corollary 6 in Appendix B-F gives the resulting balanced rate when the balancing choice also respects the stepsize condition above. Since√χm ≤ 1/m, the leading stochastic term scales as O(1/ mER). Thus, for fixed E and while this term dominates, increasing the number of participating clients gives the usual linear speedup in communication rounds. The same bound also shows where this stops: finite-difference or clipping bias does not vanish with m, local drift eventually matters, and F ED ZOO-NS incurs an additional variance floor from the Gaussian noise used for stability.

C. From Seed-Subspace to Full-Space Guarantees The previous result controls exactly what the algorithm can observe through the shared seed directions. By itself, that need not imply full-space stationarity. If the seed span misses a component of the gradient, then Z ⊤ ∇f (w) can be small even when ∇f (w) is not. To bridge the two, Appendix B-G assumes that the seed directions capture the gradients encountered during training: for some κZ > 0 and εcov ≥ 0, 1 ∥Z ⊤ ∇f (w)∥2 ≥ κZ ∥∇f (w)∥2 − ε2cov . K

(32)

Corollary 7 in Appendix B-G then converts the seed-subspace bound into a full-space guarantee, with the expected 1/κZ scaling and additive coverage error ε2cov /κZ . For the Gaussian seed pool used in our algorithms, this condition has a concrete interpretation. If all global-checkpoint gradients that can arise in the analysis lie in a fixed rdimensional subspace chosen independently of the seed pool, Proposition 2 in Appendix B-G shows that sufficiently many Gaussian seed directions form a uniform near-isometry on that subspace. Together with the stepsize condition stated there, Corollary 8 gives the corresponding high-probability full-space result. The counterexample in the same subsection explains why some such condition is unavoidable when K < d: a rankdeficient seed span can make Z ⊤ ∇f (w) = 0 while the full gradient remains nonzero. Finally, exact unlearning closes the loop. After a deletion is processed, the returned state has exactly the same law as a fresh run on the retained data. There is therefore no separate optimization error caused by unlearning. If the retained objective satisfies the same regularity conditions and the inherited stepsize remains valid, the convergence analysis applies again with the retained-data constants. Corollaries 9 and 10 in Appendix B-H state the resulting seed-subspace and full-space guarantees. In this sense, the two halves of the theory fit together naturally: stability tells us which past computation can be kept exactly, and the fixed-seed convergence analysis tells us the quality of the resulting model.

VI. E XPERIMENTS In this section, we evaluate the proposed framework across different tasks and settings, focusing on optimization performance, unlearning effectiveness, and resource efficiency. We further examine how key parameters affect the trade-off between model utility and system overhead. A. Experimental Setup 1) Datasets and Models: We evaluate our methods on MNIST [44], FashionMNIST [45], SVHN [46], CIFAR10 [47], and the TOFU benchmark for LLM unlearning [48]. Vision data are partitioned across clients using a Dirichlet distribution with α ∈ {0.1, 0.5, 1.0}. To construct low-quality forget sets, we randomly select 20% of clients and flip the labels of 20% of their local samples. For TOFU, we use the standard Split99, Split95, and Split90, with retain/forget ratios of 99%/1%, 95%/5%, and 90%/10%. Retain data are uniformly distributed across all clients, whereas forget data are uniformly assigned to 20% of clients. We use a twohidden-layer MLP with 512 and 256 neurons and dropout for MNIST, a two-layer CNN for FashionMNIST and SVHN, and ResNet-18 for CIFAR-10. TOFU experiments use Llama-3.21B-Instruct and Llama-3.2-3B-Instruct. 2) Baselines: We compare our methods with state-of-theart baselines in federated optimization and unlearning. For optimization, we consider two zeroth-order baselines: FedKSeed Pro [18] uses a fixed seed pool and scalar-gradient accumulators; DeComFL [25] reconstructs client models from historical seeds and aggregated gradient scalars, making perround uplink and downlink costs independent of model dimension. In vision unlearning: Re-optimization retrains from scratch; FATS-SU [20] replays training from the first step involving a target sample; FedRR [30] uses Fisher information for fast retraining; and FUDD [41] generates private synthetic data through knowledge distillation for server-side unlearning. For TOFU, we consider two baselines: re-optimization and Oblivionis [42], which is a LoRA-based method that alternates between retain-set fine-tuning and forget-set unlearning. 3) Hyperparameters: The following settings are used unless otherwise specified: total number of clients M = 100, number of participating clients per round m = 10, accumulator size K = 4096, number of local steps E = 10, minibatch size b = 32, and number of perturbation directions per sample q = 1. For vision tasks, we run R = 300 communication rounds with perturbation scale µ = 10−3 and clipping threshold C = 50.0, and tune the learning rate η over {10−5 , 3 × 10−5 , 10−4 , 3 × 10−4 , 10−3 , 3 × 10−3 }. For TOFU, the corresponding settings are R = 30, µ = 5 × 10−5 , and C = 100.0; we tune η over {5 × 10−7 , 10−6 , 3 × 10−6 , 5 × 10−6 , 10−5 , 3 × 10−5 }. 4) Evaluation Metrics: (1) test accuracy evaluates model utility on vision tasks and tracks its changes under sequential unlearning requests; (2) ROUGE-L measures generation quality on TOFU, with retain- and forget-set scores reported before and after unlearning, and Real Authors and World Facts scores used to assess general knowledge retention; (3) time cost denotes wall-clock execution time; (4) communication cost

10

TABLE I C OMPARISON OF ACCURACY (%), RUNTIME ( S ), AND COMMUNICATION COST (MB) AGAINST ZEROTH - ORDER BASELINES UNDER VARYING LEVELS OF DATA HETEROGENEITY ON VISION TASKS . O UR METHODS ARE SHADED IN GRAY, WITH THE BEST ACCURACIES IN BOLD . Dataset

MNIST

FashionMNIST

SVHN

CIFAR-10

α = 0.1

Algorithm

α = 0.5

α = 1.0

Acc↑

Time↓

Comm↓

Acc↑

Time↓

Comm↓

Acc↑

Time↓

Comm↓

FedKSeed Pro DeComFL

78.18 66.59

7.05 7.93

0.17 0.02

79.42 80.03

7.28 7.91

0.17 0.02

79.44 79.63

7.10 7.98

0.17 0.02

FedZOO-S FedZOO-NS (σ = 0.1) FedZOO-NS (σ = 0.2)

83.22 79.14 75.04

8.19 8.25 8.28

0.17 0.17 0.17

83.81 82.08 79.00

8.21 8.23 8.26

0.17 0.17 0.17

84.09 80.73 79.02

8.17 8.24 8.24

0.17 0.17 0.17

FedKSeed Pro DeComFL

51.46 52.83

7.82 8.20

0.17 0.02

57.75 55.58

7.96 8.33

0.17 0.02

60.92 43.75

7.93 8.34

0.17 0.02

FedZOO-S FedZOO-NS (σ = 0.1) FedZOO-NS (σ = 0.2)

55.69 58.43 60.44

9.60 9.95 9.95

0.17 0.17 0.17

63.90 66.88 64.11

9.57 9.91 9.91

0.17 0.17 0.17

66.93 64.76 62.82

9.66 9.93 9.90

0.17 0.17 0.17

FedKSeed Pro DeComFL

14.33 15.30

18.60 19.03

0.17 0.02

19.59 19.59

18.38 19.08

0.17 0.02

19.64 19.59

18.56 19.12

0.17 0.02

FedZOO-S FedZOO-NS (σ = 0.1) FedZOO-NS (σ = 0.2)

15.95 16.07 13.37

20.62 22.57 21.93

0.17 0.17 0.17

19.59 19.56 16.30

21.31 22.08 22.45

0.17 0.17 0.17

20.59 22.22 16.97

21.77 22.49 22.18

0.17 0.17 0.17

FedKSeed Pro DeComFL

18.99 16.43

47.88 49.49

0.17 0.02

19.13 18.81

49.40 50.35

0.17 0.02

18.42 20.94

48.64 49.92

0.17 0.02

FedZOO-S FedZOO-NS (σ = 0.1) FedZOO-NS (σ = 0.2)

19.47 20.16 19.69

55.44 57.18 56.73

0.17 0.17 0.17

21.13 21.05 19.82

56.73 58.95 58.33

0.17 0.17 0.17

21.08 20.06 20.26

55.45 56.26 57.17

0.17 0.17 0.17

TABLE II C OMPARISON OF ROUGE-L SCORES (%), RUNTIME ( S ), AND COMMUNICATION COST (MB) WITH ZEROTH - ORDER BASELINES UNDER DIFFERENT SPLIT SETTINGS ON TOFU. O UR METHODS ARE SHADED IN GRAY, WITH THE BEST ROUGE-L SCORES IN BOLD .

Model

Llama-3.21B-Instruct

Llama-3.23B-Instruct

Split99

Algorithm

Split95

Split90

ROUGE-L↑

Time↓

Comm↓

ROUGE-L↑

Time↓

Comm↓

ROUGE-L↑

Time↓

Comm↓

FedKSeed Pro DeComFL

40.66 42.09

63.41 72.55

0.17 0.01

38.87 43.72

65.77 74.53

0.17 0.01

38.42 44.22

68.38 77.14

0.17 0.01

FedZOO-S FedZOO-NS (σ = 10) FedZOO-NS (σ = 20)

44.07 42.58 38.61

74.07 74.17 74.08

0.17 0.17 0.17

44.47 43.57 41.03

76.47 76.57 76.59

0.17 0.17 0.17

45.01 42.65 40.68

78.61 79.23 79.47

0.17 0.17 0.17

FedKSeed Pro DeComFL

41.83 43.48

178.74 194.49

0.17 0.01

42.04 46.38

185.11 196.60

0.17 0.01

45.38 46.63

191.99 204.29

0.17 0.01

FedZOO-S FedZOO-NS (σ = 10) FedZOO-NS (σ = 20)

46.84 46.16 43.02

201.88 207.60 207.21

0.17 0.17 0.17

48.79 48.70 46.56

205.42 212.93 213.70

0.17 0.17 0.17

48.78 46.21 45.90

212.13 220.67 220.34

0.17 0.17 0.17

accounts for the total bytes exchanged between the server and clients; and (5) peak GPU memory reports the maximum GPU memory usage during unlearning. Time and communication costs are reported per round for optimization and cumulatively over sequential requests for unlearning. B. Experimental Results 1) Performance of FedZOO-S and FedZOO-NS: We evaluate F ED ZOO-S and F ED ZOO-NS on four vision benchmarks, as well as TOFU. For F ED ZOO-NS, we consider multiple noise scales. We vary the degree of data heterogeneity on the vision benchmarks using α ∈ {0.1, 0.5, 1.0} and evaluate TOFU under retain/forget splits of 99%/1%, 95%/5%, and 90%/10%, using only the retain set for optimization. We compare our algorithms with two state-of-the-art baselines.

As shown in Table I, our methods match or outperform the baselines across all 12 vision settings, with accuracy gains of up to 9.13 percentage points. F ED ZOO-S achieves the best or tied-best accuracy in seven settings. These gains may partly arise from using bqE sample–direction pairs per participating client in each round, compared with E direction evaluations in FedKSeed Pro and DeComFL. For F ED ZOONS, the broader trend is that increasing the noise scale reduces accuracy. Nevertheless, it outperforms F ED ZOO-S in several settings, showing that moderate noise does not necessarily reduce model utility. Nevertheless, F ED ZOO-NS outperforms F ED ZOO-S in several settings, showing that moderate noise does not necessarily reduce model utility. With respect to data heterogeneity, F ED ZOO-S generally improves as α increases and data heterogeneity decreases, whereas F ED ZOO-NS ex-

11

FedZOO-S (w/o Unlearn) FedZOO-NS (w/o Unlearn) Re-optimization FedZOUL-S FedZOUL-NS

50 40 30

2

4

6

8

10

12

Unlearning Request Index

40 20 10

14

18

20

2

4

6

8

10

12

Unlearning Request Index

14

18

16 FedZOO-S (w/o Unlearn) FedZOO-NS (w/o Unlearn) Re-optimization FedZOUL-S FedZOUL-NS

14 12 2

4

6

8

10

12

Unlearning Request Index

FedZOO-S (w/o Unlearn) FedZOO-NS (w/o Unlearn) Re-optimization FedZOUL-S FedZOUL-NS

16 14 12

14

2

4

6

8

10

12

Unlearning Request Index

14

Fig. 1. Accuracy comparison of FedZOUL-S/NS against FedZOO-S/NS (before unlearning) and re-optimization under stream unlearning requests on four vision datasets. Top-left:MNIST, top-right: FashionMNIST, bottom-left: SVHN, bottom-right: CIFAR-10.

FedZOO-S

FedZOO-NS Oblivionis-FT Re-optimization Oblivionis-U FedZOUL-S FedZOUL-NS

80

ROUGE-L (%)

100

80

ROUGE-L (%)

100

60 40 20 0

Forget

Retain

Real Authors

World Fact

60 40 20 0

30000 20000 10000 0

Re-optimization FedZOUL-S FedZOUL-NS

25000 20000 15000 10000 5000

2

4

6

8

10

12

Unlearning Request Index

14

0

1

2

3

4

Unlearning Request Index

5

Fig. 3. Cumulative time cost of FedZOUL-S/NS against re-optimization under stream unlearning requests on four vision datasets. Left: CIFAR-10, right: TOFU (Llama-3.2-3B-Instruct).

Accuracy (%)

22

Accuracy (%)

20

10

FedZOO-S (w/o Unlearn) FedZOO-NS (w/o Unlearn) Re-optimization FedZOUL-S FedZOUL-NS

30

Re-optimization FedZOUL-S FedZOUL-NS

Time Cost (s)

50

60

Time Cost (s)

70

40000

Accuracy (%)

60

Accuracy (%)

80

Forget

Retain

Real Authors

World Fact

Fig. 2. ROUGE-L scores of FedZOUL-S and FedZOUL-NS compared with re-optimization and Oblivionis before and after stream unlearning requests on TOFU (Split95). Oblivionis-FT and Oblivionis-U denote fine-tuning and unlearning under the Oblivionis framework, respectively. Left: Llama-3.2-1BInstruct. Right: Llama-3.2-3B-Instruct.

hibits a non-monotonic trend, possibly due to noise-induced variation in its optimization trajectory. Table II reports the TOFU results. F ED ZOO-S achieves the highest ROUGE-L score for both model sizes across all splits. F ED ZOO-NS performs worse than F ED ZOO-S, with σ = 20 consistently underperforming σ = 10. This contrasts with the mixed effect of noise on the vision tasks and suggests that LLM finetuning may be more sensitive to scalar noise. The 3B model consistently outperforms the 1B model across all methods and splits, which may reflect its greater representational capacity. Taken together, Tables I and II show that our methods trade additional local computation for improved utility while retaining dimension-independent communication. Their higher runtime stems from evaluating bqE sample–direction pairs per participating client in each round, compared with E direction evaluations in FedKSeed Pro and DeComFL. F ED ZOO-S and F ED ZOO-NS match FedKSeed Pro in per-round communication by exchanging fixed-size scalar-gradient accumulators. Under our settings, this cost exceeds that of DeComFL, whose clients upload only per-update scalars and reconstruct models from server-provided seeds and historical aggregates.

Overall, both methods incur modest additional overhead, while their improved utility provides a strong foundation for the unlearning procedures. 2) Performance of FedZOUL-S and FedZOUL-NS: To evaluate the unlearning algorithms, we introduce a stream of unlearning requests at fixed intervals, with each request made by one or more target clients to remove samples from their local datasets. Figures 1 and 2 summarize the performance on the vision tasks and TOFU under Split95, respectively. On the vision tasks, F ED ZOUL-S improves over F ED ZOO-S by up to 13.37 percentage points after removing low-quality target data, while its final accuracy remains within 2.77 percentage points of re-optimization across all four tasks. On TOFU, both variants reduce forget-set ROUGE-L after unlearning; although F ED ZOUL-S has higher forget-set scores than Oblivionis-U, it better preserves general knowledge, achieving 90.93% and 95.13% on Real Authors for the 1B and 3B models, compared with 58.08% and 64.13% for OblivionisU. F ED ZOUL-NS achieves competitive final accuracy on the vision tasks and forget-set performance similar to OblivionisU and re-optimization on TOFU. However, with the additional randomness introduced by noise injection, F ED ZOUL-NS shows larger deviations at some intermediate vision requests and greater degradation in general knowledge, particularly for the 1B model, consistent with the behavior observed for F ED ZOO-NS in the federated optimization experiments. To evaluate efficiency, we compare the cumulative runtime of F ED ZOUL-S and F ED ZOUL-NS with re-optimization in Figure 3. At the final request, F ED ZOUL-S and F ED ZOULNS reduce runtime by 2.2% and 12.4% on CIFAR-10 and by 22.5% and 56.1% on TOFU with the 3B model, respectively. These savings arise because only a fraction of requests trigger suffix replay, while noise injection and rejection sampling further reduce replay in F ED ZOUL-NS. Figures 4 and 5 show similar gains in communication. Unlike FATSSU and FedRR, which transmit parameter-sized information, our methods exchange fixed-size scalar-gradient accumulators and reduce suffix replay. After 15 requests on CIFAR-10, F ED ZOUL-NS incurs 389.1 MB, which is 99.5%, 99.7%, 42.7%, and 5.7% lower than FATS-SU, FedRR, FUDD, and re-optimization, respectively. After five requests on TOFU with the 3B model, F ED ZOUL-S and F ED ZOUL-NS incur only 12.38 MB and 1.89 MB, compared with 27.08 GB for Oblivionis. Thus, F ED ZOUL-NS reduces communication by approximately four orders of magnitude, highlighting its

12

100 50

2

4

6

8

4

5

10

6

7

12

8

9 10

14

103 102 101

150 125

100

100 75 50

2

101

150

100

100

4

6

8

4

5

10

6

7

12

8

9 10

14

Unlearning Request Index

103

Oblivionis Re-optimization FedZOUL-S FedZOUL-NS

102 101 100

10 1

1

2

3

4

Unlearning Request Index

5

0.3

0.5

0.7

66 FedZOUL-S FedZOUL-NS

62

0.9

Client Participation Ratio

68

64

FedZOO-S FedZOO-NS 0.1

2

4

6

8

4

5

10

6

7

12

8

9 10

14

0.1

104 103 102 101

150

100

100

10 1

2

0.3

0.5

0.7

Client Participation Ratio

0.9

4

6

8

6

7

10

8

9 10 11 12

12

14

27083 MB

104 Oblivionis Re-optimization FedZOUL-S FedZOUL-NS

102 101 100 1

810

400 800

300 790

200 780

100 770 0.1

0.3

0.5

0.7

Client Participation Ratio

0.9

NS Runtime NS Communication 3,500

7,000

3,000 6,500

2,500 2,000

6,000

1,500 1,000

5,500

500 5,000

0.1

0.3

0.5

0.7

Client Participation Ratio

0.9

Unlearning Request Index

105 103

S Runtime S Communication

Unlearning Request Index

105

10 1

66

70

50

10 1

Communication Cost (MB)

Communication Cost (MB)

12556 MB

104

68

64

Fig. 4. Cumulative communication cost of FedZOUL-S/NS against reoptimization and first-order unlearning baselines under stream unlearning requests on four vision datasets. Top-left: MNIST, top-right: FashionMNIST, bottom-left: SVHN, bottom-right: CIFAR-10. 105

Accuracy (%)

Accuracy (%)

102

Unlearning Request Index

104

10 1

103

70

Cumulative Comm. (MB)

100

104

72

72

Cumulative Runtime (s)

150

74

Cumulative Comm. (MB)

101

FedZOUL-S FedZOUL-NS

Cumulative Runtime (s)

102

Communication Cost (MB)

103

10 1

Communication Cost (MB)

FUDD Re-optimization

Communication Cost (MB)

Communication Cost (MB)

FATS-SU FedRR

2

3

4

Unlearning Request Index

5

Fig. 5. Cumulative communication cost of FedZOUL-S/NS against reoptimization and Oblivionis under stream unlearning requests on TOFU (Split95). Left: Llama-3.2-1B-Instruct, right: Llama-3.2-3B-Instruct.

benefit for bandwidth-constrained federated unlearning. In terms of resource efficiency, we further evaluate peak GPU memory on vision tasks and TOFU, with detailed results reported in the Appendix A-A. Both F ED ZOUL-S and F ED ZOUL-NS require less memory than the first-order unlearning baselines. On TOFU, their memory advantage over Oblivionis becomes more pronounced as model size increases. These results complement the time and communication savings and support deployment on devices with limited memory. 3) Impact of the Client Sampling Ratio m/M : We study how the client sampling ratio m/M affects the utility and efficiency of F ED ZOO-S/NS and F ED ZOUL-S/NS on FashionMNIST. This ratio determines client participation and affects the TV-stability bounds of both learning algorithms. Figure 6 shows that increasing m/M from 0.1 to 0.3 improves optimization accuracy, while further increases provide limited gains. For unlearning, F ED ZOUL-S achieves its highest accuracy of 68.27% at m/M = 0.5, whereas F ED ZOULNS reaches 72.73% at 0.9. These results show that greater participation generally improves model utility, although accuracy does not increase monotonically. Except at m/M = 0.1, F ED ZOO-NS and F ED ZOUL-NS achieve higher accuracy

Fig. 6. Impact of the client sampling ratio (m/M ) on accuracy, cumulative runtime, and cumulative communication cost on FashionMNIST. Top row: accuracy; bottom row: cumulative runtime and communication cost. Left column: FedZOO-S/NS; right column: FedZOUL-S/NS.

than F ED ZOO-S and F ED ZOUL-S, respectively, indicating that introducing randomness does not reduce model utility. However, greater participation increases communication overhead, as each selected client uploads a fixed-size accumulator per round. The cumulative communication cost of F ED ZOO-S/NS increases by a factor of 8.27 from m/M = 0.1 to 0.9, while runtime changes little under parallel client execution. For unlearning, communication grows approximately linearly and runtime generally increases. This is because a higher client sampling ratio increases both the communication cost per round and the probability that local updates use target samples, which may require replay during unlearning. F ED ZOUL-NS consistently uses less time and communication than F ED ZOUL-S: Gaussian coupling allows affected updates to be reused until the first rejection. However, its runtime and communication savings decrease from 24.3% and 15.9% at m/M = 0.1 to 9.9% and 2.1% at 0.9, respectively, indicating a smaller efficiency advantage at higher participation levels, where more frequent use of target samples can increase replay probabilities for both methods. 4) Impact of Hyperparameters K and q: We examine the effects of K and q on FashionMNIST, with detailed results reported in the Appendix A-B. Smaller seed pools generally favor F ED ZOO-S, whereas larger pools tend to benefit F ED ZOO-NS. Increasing q can improve accuracy for both methods, although the gains are not monotonic. Communication cost grows linearly with K and is independent of q, while runtime increases with both parameters. VII. C ONCLUSION We present a framework for efficient federated zeroth-order optimization and exact unlearning based on total variation stability. F ED ZOO-S obtains stability through subsampling, and F ED ZOUL-S reuses unaffected training computation to achieve efficient exact unlearning. Building on this design,

13

F ED ZOO-NS incorporates Gaussian randomization, allowing F ED ZOUL-NS to reuse some affected updates through coupling and further reduce replay for more efficient exact unlearning. We establish theoretical guarantees and demonstrate competitive utility with lower runtime, communication, and memory costs. R EFERENCES [1] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas, “Communication-efficient learning of deep networks from decentralized data,” in 20th International Conference on Artificial Intelligence and Statistics (AISTATS 2017), Fort Lauderdale, FL, 4 2017, pp. 1273–1282. [2] Y. Fu, H. You, Y. Zhao, Y. Wang, C. Li, K. Gopalakrishnan, Z. Wang, and Y. Lin, “FracTrain: Fractionally Squeezing Bit Savings Both Temporally and Spatially for Efficient DNN Training,” in 34th Conference on Neural Information Processing Systems (NeurIPS 2020), H. Larochelle, M. Ranzato, R. Hadsell, M.-F. F. Balcan, and H.-T. Lin, Eds., vol. 33. Virtual Conference: Curran Associates Inc., 12 2020, pp. 12 127–12 139. [3] A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani, “FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization,” in 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), vol. 108. Virtual Conference: PMLR, 8 2020, pp. 2021–2031. [4] L. Ding, H. Zhang, W. Dai, C. Li, W. Lu, Z. Yang, X. Zhang, X. Ma, J. Zou, and H. Xiong, “LBI-FL: Low-Bit Integerized Federated Learning with Temporally Dynamic Bit-Width Allocation,” in 42nd International Conference on Machine Learning (ICML 2025), vol. 267. Vancouver, Canada: PMLR, 7 2025, pp. 13 885–13 899. [5] Y. Lin, S. Han, H. Mao, Y. Wang, and B. Dally, “Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training,” in 6th International Conference on Learning Representations (ICLR 2018). Vancouver, Canada: ICLR, 4 2018. [6] Y. Tao, S. Chen, C. Zhang, D. Wang, D. Yu, X. Cheng, and F. Dressler, “Private Over-the-Air Federated Learning at Band-Limited Edge,” IEEE Transactions on Mobile Computing, vol. 23, no. 12, pp. 12 444–12 460, 12 2024. [7] A. Guastella, L. Sani, A. Iacob, A. Mora, P. Bellavista, and N. D. Lane, “SparsyFed: Sparse Adaptive Federated Learning,” in 13rd International Conference on Learning Representations (ICLR 2025), vol. 2025. Singapore, Singapore: OpenReview.net, 4 2025. [8] Y. Huang, X. Qiao, J. Tang, P. Ren, L. Liu, C. Pu, and J. Chen, “Deepadapter: A collaborative deep learning framework for the mobile web using context-aware network pruning,” in 39th IEEE International Conference on Computer Communications (INFOCOM 2020). Virtual Conference: IEEE, 7 2020, pp. 834–843. [9] S. Horvath, S. Laskaridis, M. Almeida, I. Leontiadis, S. I. Venieris, and N. D. Lane, “FjORD: Fair and Accurate Federated Learning under Heterogeneous Targets with Ordered Dropout,” in 35th Conference on Neural Information Processing Systems (NeurIPS 2021), M. a. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Virtual Conference: Curran Associates Inc., 12 2021. [10] S. Chen, Y. Yuan, Y. Tao, T. Wang, Z. Cai, and D. Yu, “Adaptive pruningbased Newton’s method for distributed learning,” Theoretical Computer Science, vol. 1026, p. 114987, 2 2025. [11] Y. Tao, M. Simsek, and F. Dressler, “AutoSub: Autonomous Submodel Averaging,” in IEEE Annual Congress on Artificial Intelligence of Things (AioT 2026). Kobe, Japan: IEEE, 12 2026, to appear. [12] L. Zhang, J. Song, A. Gao, J. Chen, C. Bao, and K. Ma, “Be your own teacher: Improve the performance of convolutional neural networks via self distillation,” in IEEE/CVF International Conference on Computer Vision (ICCV 2019). Seoul, South Korea: IEEE, 10 2019, pp. 3712– 3721. [13] T. Lin, L. Kong, S. U. Stich, and M. Jaggi, “Ensemble distillation for robust model fusion in federated learning,” in 34th Conference on Neural Information Processing Systems (NeurIPS 2020), M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds. Virtual Conference: Curran Associates Inc., 12 2020, pp. 2351–2363. [14] T. Fan, W. Chen, Y. Kang, G. Ma, H. Gu, Y. Song, L. Fan, and Q. Yang, “FedCoT: Federated Chain-of-Thought Distillation for Large Language Models,” in 30th Conference on Empirical Methods in Natural Language Processing (EMNLP 2025). Suzhou, China: ACL, 11 2025, pp. 8546– 8557.

[15] Z. Zhang, Y. Yang, Y. Dai, Q. Wang, Y. Yu, L. Qu, and Z. Xu, “Fedpetuning: When federated learning meets the parameter-efficient tuning methods of pre-trained language models,” in Findings of the Association for Computational Linguistics: ACL 2023. Toronto, Canada: ACL, 7 2023, pp. 9963–9977. [16] S. Chen, Y. Tao, S. Chen, F. Dressler, Q. Ye, and D. Wang, “FedSubMuon: Communication-Efficient Federated LLM Fine-Tuning via Structured Subspace Muon,” in Conference on Empirical Methods in Natural Language Processing (EMNLP 2026). Budapest, Hungary: ACL, 10 2026. [17] L. Wang, J. Ren, H. Xu, J. Wang, H. Xie, D. E. Keyes, and D. Wang, “Scalable Zeroth-Order Fine-Tuning for Extremely Large Language Models with Limited GPU Memory,” in Second Conference on Language Modeling (COLM 2025). Montréal, Canada: OpenReview.net, 10 2025. [18] Z. Qin, D. Chen, B. Qian, B. Ding, Y. Li, and S. Deng, “Federated Full-Parameter Tuning of Billion-Sized Language Models with Communication Cost under 18 Kilobytes,” in 41st International Conference on Machine Learning (ICML 2024). Vienna, Austria: PMLR, 7 2024. [19] P. Voigt and A. Von dem Bussche, The EU General Data Protection Regulation (GDPR): A Practical Guide. Springer, 2024. [20] Y. Tao, C.-L. Wang, M. Pan, D. Yu, X. Cheng, and D. Wang, “Communication Efficient and Provable Federated Unlearning,” Proceedings of the VLDB Endowment, vol. 17, no. 5, pp. 1119–1131, 1 2024. [21] E. Ullah, T. Mai, A. Rao, R. A. Rossi, and R. Arora, “Machine unlearning via algorithmic stability,” in 34th Annual Conference on Learning Theory (COLT 2021). Boulder, CO: PMLR, 8 2021, pp. 4126–4142. [22] Y. Tao, W. Yin, H. Xie, Y. Yao, D. Yu, X. Cheng, D. Wang, and F. Dressler, “One-Shot Federated Model Editing for Device Dynamics at the Edge,” IEEE Transactions on Networking, 10 2026, to appear. [23] W. Fang, Z. Yu, Y. Jiang, Y. Shi, C. N. Jones, and Y. Zhou, “Communication-efficient stochastic zeroth-order optimization for federated learning,” IEEE Transactions on Signal Processing, vol. 70, pp. 5058–5073, 2022. [24] Z. Ling, D. Chen, L. Yao, Y. Li, and Y. Shen, “On the convergence of zeroth-order federated tuning for large language models,” in 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2024). Barcelona, Spain: ACM, 8 2024, pp. 1827–1838. [25] Z. Li, B. Ying, Z. Liu, C. Dong, and H. Yang, “Achieving dimensionfree communication in federated learning via zeroth-order optimization,” in 13rd International Conference on Learning Representations (ICLR 2025), vol. 2025. Singapore, Singapore: OpenReview.net, 4 2025. [26] ——, “Converge faster, talk less: Hessian-informed federated zerothorder optimization,” in 14th International Conference on Learning Representations (ICLR 2026), vol. 2026. Rio de Janeiro, Brazil: OpenReview.net, 4 2026. [27] L. Zhang, B. Li, K. K. Thekumparampil, S. Oh, and N. He, “DPZero: private fine-tuning of language models without backpropagation,” in 41st International Conference on Machine Learning (ICML 2024). Vienna, Austria: PMLR, 7 2024, pp. 59 210–59 246. [28] Z. Liu, J. Lou, W. Bao, Y. Hu, W. Wang, Z. Qin, and K. Ren, “Differentially Private Zeroth-Order Methods for Scalable Large Language Model Fine-tuning,” IEEE Transactions on Information Forensics and Security, vol. 21, pp. 4163 – 4175, 2026. [29] E. Bao, Y. Jiang, F. Wei, X. Xiao, Z. Li, Y. Li, and B. Ding, “Unlocking the Power of Differentially Private Zeroth-order Optimization for Finetuning $LLM s$,” in 34th USENIX Security Symposium (USENIX Security 2025). Seattle, WA: USENIX, 8 2025, pp. 1569–1588. [30] Y. Liu, L. Xu, X. Yuan, C. Wang, and B. Li, “The right to be forgotten in federated learning: An efficient realization with rapid retraining,” in 41st IEEE International Conference on Computer Communications (INFOCOM 2022). Virtual Conference: IEEE, 5 2022, pp. 1749–1758. [31] G. Liu, X. Ma, Y. Yang, C. Wang, and J. Liu, “FedEraser: Enabling efficient client-level data removal from federated learning models,” in 29th IEEE/ACM International Symposium on Quality of Service (IWQOS 2021). Chiyoda, Japan: IEEE, 6 2021. [32] P. Wang, W. Song, H. Qi, C. Zhou, F. Li, Y. Wang, P. Sun, and Q. Zhang, “Server-initiated federated unlearning to eliminate impacts of low-quality data,” IEEE Transactions on Services Computing, vol. 17, no. 3, pp. 1196–1211, 2024. [33] W. Su, P. Wang, Z. Wang, A. Muhammad, T. Tao, X. Tong, and Q. Zhang, “F2ul: Fairness-aware federated unlearning for data trading,” IEEE Transactions on Mobile Computing, vol. 23, no. 12, pp. 13 539– 13 555, 12 2024. [34] Z. Pan, Z. Wang, C. Li, K. Zheng, B. Wang, X. Tang, and J. Zhao, “Federated unlearning with gradient descent and conflict mitigation,” in 39th

14

AAAI Conference on Artificial Intelligence (AAAI 2025). Philadelphia, PA: AAAI, 2 2025, pp. 19 804–19 812. [35] T. Che, Y. Zhou, Z. Zhang, L. Lyu, J. Liu, D. Yan, D. Dou, and J. Huan, “Fast federated machine unlearning with nonlinear functional theory,” in 40th International Conference on Machine Learning (ICML 2023). Honolulu, HI: PMLR, 7 2023. [36] L. Zhang, T. Zhu, H. Zhang, P. Xiong, and W. Zhou, “Fedrecovery: Differentially private machine unlearning for federated learning frameworks,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 4732–4746, 2023. [37] Y. Fraboni, M. Van Waerebeke, K. Scaman, R. Vidal, L. Kameni, and M. Lorenzi, “Sifu: Sequential informed federated unlearning for efficient and provable client unlearning in federated optimization,” in 27th International Conference on Artificial Intelligence and Statistics (AISTATS 2024). Valencia, Spain: PMLR, 5 2024, pp. 3457–3465. [38] H. Wu, Y. Tao, A. Zhou, S. Chen, F. Dressler, and D. Yu, “Certified Unlearning in Decentralized Federated Learning,” in 45th IEEE International Conference on Computer Communications (INFOCOM 2026). Tokyo, Japan: IEEE, 5 2026, pp. 1–10. [39] H. Wu, J. Yang, S. Chen, D. Wang, D. Yu, and Y. Tao, “TrajectoryAware Certified Decentralized Unlearning via SGD Stability,” in 43rd International Conference on Machine Learning (ICML 2026), Poster Session. Seoul, South Korea: PMLR, 7 2026. [40] C. Zhou, C. Pan, M. Li, and P. Wang, “Federated unlearning with fast recovery,” IEEE Transactions on Mobile Computing, vol. 24, no. 10, pp. 9709 – 9725, 2025. [41] A. Mora, L. Valerio, and P. Bellavista, “Federated Unlearning via Distilled Data,” IEEE Transactions on Mobile Computing, vol. 25, no. 7, pp. 10 607 – 10 618, 2026. [42] F. Zhang, X. Yan, T. Wu, W. Li, T. Chen, Y. Cao, R. Yan, L. Huang, W. Y. B. Lim, and Q. Yang, “Oblivionis: A Lightweight Learning and Unlearning Framework for Federated Large Language Models,” in 40th AAAI Conference on Artificial Intelligence (AAAI 2026), vol. 40. Singapore, Singapore: AAAI, 1 2026, pp. 28 185–28 193. [43] J. Li, Y. Tao, B. He, and M. Ding, “Not All Change Is Damage: Update-Matched Unlearning for Large Language Models,” arXiv, cs.LG 2610.21230, 10 2026. [Online]. Available: https: //arxiv.org/abs/2610.21230 [44] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 11 1998. [45] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms,” arXiv, cs.LG 1708.07747, 8 2017. [46] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng, “Reading digits in natural images with unsupervised feature learning,” in 24th International Conference on Neural Information Processing Systems (NIPS 2011), NIPS Workshop on Deep Learning and Unsupervised Feature Learning, Granada, Spain, 12 2011. [47] A. Krizhevsky, “Learning multiple layers of features from tiny images,” University of Toronto, Technical Report TR-2009, 4 2009. [48] P. Maini, Z. Feng, A. Schwarzschild, Z. C. Lipton, and J. Z. Kolter, “TOFU: A Task of Fictitious Unlearning for LLMs,” in 38th Conference on Neural Information Processing Systems (NeurIPS 2024), NeurIPS 2024 Workshop on Red Teaming GenAI, vol. 37. Vancouver, Canada: Curran Associates Inc., 12 2024. [49] R. Vershynin, “Introduction to the non-asymptotic analysis of random matrices,” in Compressed Sensing: Theory and Applications. Cambridge University Press, 2012, pp. 210–268.

15

A PPENDIX A A DDITIONAL EXPERIMENTAL RESULTS A. GPU Memory cost of FedZOUL-S/NS We evaluate peak GPU memory in Figure 7. F ED ZOUL-S and F ED ZOUL-NS achieve the lowest peak memory across all tasks by avoiding parameter-sized gradients and backpropagation activations, while maintaining performance comparable to re-optimization. On CIFAR-10, each method requires 128.08 MB, 60.8% below FedRR and 54.0% below FUDD. On TOFU, their peak memory is 6.63 GB for the 3B model, compared with 11.15 GB for Oblivionis, and the reduction relative to Oblivionis increases from 24.3% for the 1B model to 40.5% for the 3B model. These results show that our methods maintain low peak memory across tasks, supporting deployment on resource-constrained edge devices. This advantage becomes more pronounced as model size increases, indicating favorable scalability. 128.08 128.08

CIFAR-10

278.40 278.52

128.08

Fashion MNIST

MNIST 0

19.15 19.15

36.38 40.60 36.38 19.15

19.12 19.12

33.73 40.21 33.73 19.12

17.88 17.88

24.26 36.93 24.26 17.88

50

5.19

Llama3.2-1B -Instruct

5.19 5.19

Model

Dataset

SVHN

326.89

100

150

Re-optimization FATS-SU FedRR 200 250

Memory Cost (MB)

FUDD FedZOUL-S FedZOUL-NS 300 350

6.63

Llama3.2-3B -Instruct 0

Re-optimization Oblivionis FedZOUL-S FedZOUL-NS

6.86

11.15

6.63 6.63

2

4

6

8

Memory Cost (GB)

10

12

14

Fig. 7. Peak GPU memory of FedZOUL-S/NS against re-optimization and first-order unlearning baselines under stream unlearning requests. Left: four vision datasets. Right: TOFU (Split95).

B. Impact of Hyperparameters K and q We investigate how the accuracy, communication cost, and time cost of F ED ZOO-S and F ED ZOO-NS vary with q and K on FashionMNIST, as shown in Figure 8. For F ED ZOO-S, increasing q generally improves accuracy, although the gains are not monotonic. At K = 1024, accuracy increases from 64.46% at q = 1 to 68.12% at q = 3, before decreasing to 67.71% at q = 4. F ED ZOO-NS also exhibits a non-monotonic response: increasing q from 1 to 2 improves accuracy for every tested K. Its best accuracy is attained at q = 2 for K ∈ {1024, 2048, 4096} and at q = 3 for K = 8192. The effect of K differs between the two methods. F ED ZOO-S achieves its highest accuracy at K = 1024 for q ∈ {2, 3, 4}, whereas K = 2048 performs best at q = 1. Increasing K can reduce accuracy: at q = 3, accuracy falls from 68.12% to 64.29% as K increases from 1024 to 8192. For F ED ZOO-NS, larger seed pools generally yield higher accuracy, but the trend is not monotonic. For example, at q = 1, accuracy increases from 55.38% at K = 1024 to 64.11% at K = 4096, then decreases to 60.19% at K = 8192. In terms of system overhead, the per-round communication cost is independent of q and increases linearly with K, with identical costs for both methods. Each of the m = 10 participating clients uploads a K-dimensional float32 accumulator, while the server broadcasts the global accumulator, resulting in a per-round communication cost of 4(m + 1)K = 44K bytes. The average per-round runtime increases with both q and K in all tested configurations. At K = 4096, increasing q from 1 to 2 improves F ED ZOO-NS accuracy from 64.11% to 71.26%, while increasing per-round runtime from 2.883 to 3.073 s and leaving communication cost unchanged. We use K = 4096 as an intermediate pool size and q = 1 to limit local computation.

16

0.6 0.4 0.2 0.0

1

2

q 3

8192 4096 2048 K 4 1024

Time Cost (s)

4.0 3.5 3.0 2.5 2.0

1

2

q 3

8192 4096 2048 K 4 1024

2048 K 4096 8192 1

0.6 0.4 0.2 0.0

0.3 0.2 0.1

1

2

q 3

8192 4096 2048 K 4 1024

4.5 4.0 3.5 3.0 2.5 2.0

3.5 3.0 2.5

1

2

q 3

70 65 60

4

Comm. Cost (MB)

1024

3 2 q

Time Cost (s)

2048 K 4096 8192 1

4

Comm. Cost (MB)

1024

3 2 q

75 70 65 60 55

68 67 66 65 64

Accuracy (%)

Accuracy (%)

69 68 67 66 65 64 63

8192 4096 2048 K 4 1024

0.3 0.2 0.1

4.0 3.5 3.0 2.5

Fig. 8. Impact of the number of per-sample perturbation directions (q) and the scalar gradient accumulator size (K) on the accuracy, per-round communication cost, and per-round time cost of FedZOO-S and FedZOO-NS on FashionMNIST. Left column: FedZOO-S, right column: FedZOO-NS. Top row: accuracy, middle row: communication cost, bottom row: time cost.

A PPENDIX B C OMPLETE T HEORETICAL A NALYSIS We now establish the theoretical guarantees of the proposed learning and unlearning procedures. Two questions are central. First, after a sample is deleted, we need to show that the state returned by the unlearning algorithm has exactly the same distribution as a fresh execution on the retained data, while avoiding a full rerun whenever possible. Second, because both training algorithms reuse a finite set of perturbation directions, we need to understand what optimization guarantee this restriction provides for the original federated objective. The two learning algorithms support exact unlearning in different ways. In F ED ZOO-S, a deletion has no effect unless the removed sample was actually selected during training. In F ED ZOO-NS, Gaussian noise provides an additional possibility: even when the deleted sample changes a local update, the old and retained-data updates can sometimes be coupled to the same value. We first analyze these two mechanisms and their resulting unlearning costs. We then study the optimization behavior of the learning algorithms under the shared finite seed pool and relate the resulting subspace guarantee to the full model space. The perturbation pool is sampled independently of the federated data and is shared by the neighboring executions considered below. We therefore condition on its realization throughout the analysis. All conditional guarantees remain valid after averaging

17

over the seed-pool randomness. We first ask how a deletion can change the state that has already been produced. Exact unlearning requires more than a nearby model: after processing the request, the entire maintained state must have the same distribution as if the deleted sample had never been present. The useful computation is therefore precisely the part of the realized trajectory that can be kept without changing this law. Let T = RE denote the total number of local positions, and index them in chronological order by τ (r, t) = (r − 1)E + t.

(33)

For a request arriving after (Rul , tul ), write Tul = τ (Rul , tul ). A position contains the local updates of the m participating clients and, when t = E, the corresponding server aggregation. Position zero denotes the initialization before the first client set is sampled. [τ ] For • ∈ {S, NS}, let O• (D) denote the joint law of the optimization variables and all saved state after τ positions when training on D. We use O•,out (D) for the marginal law of the final reconstructed model. With this notation, exact unlearning [T ] at Tul means that the state produced after processing the deletion has law O• ul (D− ), and continuing training from that state [T ] must yield O• (D− ). Whenever part of the trajectory is rerun, the newly generated state replaces the old saved state over that part of the execution. A. FedZOO-S Stability and Exact Unlearning We first consider F ED ZOO-S and its unlearning procedure F ED ZOUL-S. A deleted sample can change a F ED ZOO-S trajectory only if it was actually drawn into a local mini-batch. This observation suggests coupling the mini-batches before and after deletion so that they remain identical whenever the deleted sample was not selected. The following elementary fact gives the coupling we need. Lemma 1 (Deletion coupling for a uniform mini-batch). Let D contain n samples, let x− ∈ D, and let D− = D \ {x− }, where n − 1 ≥ b. Draw B uniformly from the size-b subsets of D. Construct B − as follows: ( B, x− ∈ / B, − (34) B = − b B, x ∈ B, where, on the second branch, Bb is drawn uniformly from the size-b subsets of D− , independently of B. Then B − is uniform over the size-b subsets of D− and b P(B − ̸= B) = . (35) n Proof of Lemma 1. Fix a size-b subset A ⊆ D− . The first branch outputs A
precisely when B = A, while the second branch is entered with probability b/n and then outputs A with probability 1/ n−1 b . Hence 1 b 1

n + n−1 n b b b 1 n−b 1

= n−1 + n n−1 = n b b

P(B − = A) =

1

.

n−1 b

(36)

Since the two mini-batches cannot agree on the second branch, the disagreement probability is b/n. When B − = B, use the same independently sampled size-q seed set for every sample in the two executions. On the second branch, draw the retained execution’s sample–seed correspondence afresh according to F ED ZOO-S. Because seed sampling is independent of data sampling, the second execution has the correct joint mini-batch–seed marginal. Consider one deletion x− ∈ Dc− and write nc− = |Dc− |. At local position (r, t), define Hr,t (x− ) = {c− ∈ C r , x− ∈ Bcr,t − }.

(37)

  τ mb ΛS (τ, c− ) = min 1, . M nc−

(38)

For the first τ local positions, let

The same coupling can now be followed through the whole training state. Use the same initialization and client set in the two executions, couple unaffected clients identically, and apply Lemma 1 whenever the affected client participates. Until the deleted sample first appears in a mini-batch, the sampled data, seed sets, coefficient increments, accumulators, and reconstructed models are identical. If a first hit occurs, the retained-data execution draws fresh local randomness from that position onward, while keeping the already sampled client set for the remainder of the current round. Thus the second execution has exactly the law of F ED ZOO-S on the retained data.

18

At any local position, a hit occurs with probability m b . M nc−

(39)

The same client set is reused within a round, so these events need not be independent. A union bound over the first τ positions nevertheless gives P(the two states differ by position τ ) ≤ ΛS (τ, c− ). (40) Theorem 1 (TV stability of FedZOO-S). For every admissible adjacent pair differing by deletion of x− ∈ Dc− ,
TV OS,out (D), OS,out (D− ) ≤ ΛS (T, c− ).

(41)

If a target 0 < ρ ≤ 1 is fixed before training and T mb ≤ ρ, Mn

(42)

then F ED ZOO-S is ρ-sample-level TV stable on the dataset class satisfying (47). Proof of Theorem 1. The construction above is a valid coupling of the complete training states on D and D− . By Eq. (40), their disagreement probability at τ = T is at most ΛS (T, c− ). Projecting the coupled states onto the final reconstructed model can only decrease total variation. Under (42), nc− ≥ n gives ΛS (T, c− ) ≤ ρ. Symmetry of total variation covers both orientations of every adjacent pair. The bound follows the way a deletion enters the trajectory. At each local position, the target client is selected with probability m/M , and conditional on participation, the deleted sample enters its mini-batch with probability b/nc− . Thus, increasing client participation or the mini-batch size makes it more likely that the deletion changes the realized trajectory. No additional noise is needed for this form of stability. This stability statement also suggests the unlearning procedure itself. If the deleted sample never appears before the request, the realized state already has the retained-data law and can be kept. Otherwise, the two executions agree up to the first affected [T ] mini-batch, so training only needs to be rerun from that point. Let US ul denote the state returned by F ED ZOUL-S at position Tul →T Tul after processing the deletion, and let US denote the state after the remaining training positions are completed. Theorem 2 (Exact unlearning of FedZOUL-S). For every valid single-sample deletion x− ∈ Dc− arriving after local position Tul ,   d [T ] [T ] [T ] US ul OS ul (D), {x− } = OS ul (D− ). (43) Consequently,   d [T ] [T ] USTul →T OS ul (D), {x− } = OS (D− ),

(44)

where both equalities hold jointly over the model and every maintained state. If ReplayS denotes the event that the deletion causes training to be rerun from an affected position, then P(ReplayS ) ≤ ΛS (Tul , c− ) ≤

Tul mb . M nc−

(45)

Under (42), this probability is at most ρ. Proof of Theorem 2. Use the same coupling as in the proof of Theorem 1 through position Tul , and let (r⋆ , t⋆ ) be the first hit in the original execution. If no hit occurs, the two executions are identical up to the request time. After removing x− , F ED ZOUL-S keeps that state and continues from Next(Rul , tul ). For the remainder of the current round it keeps the saved client set and current local states, while all future mini-batches and seed sets are drawn from the retained datasets. This is the retained-data continuation of the second coupled execution. If the first hit is (r⋆ , t⋆ ), the coupled executions agree through the state immediately before that position. The unlearning algorithm restores that common server and participating-client state and replays all participating clients from (r⋆ , t⋆ ) on the ⋆ retained datasets. The saved client set C r is kept for the remainder of the current round, while all local randomness from the hit onward and all randomness in later rounds follow the retained-data transition law. [T ] In both branches, the state returned at Tul has law OS ul (D− ). Completing the horizon with the retained-data kernels proves (44). Training is rerun only if a hit appears before the request, giving (45). Nothing in the preceding argument depends on there being only one request. It can be applied repeatedly, provided future deletions are not chosen in response to the randomness revealed by earlier training or unlearning. Consider a valid request stream (j)
k (1) (k) − c− 0 ≤ Tul ≤ · · · ≤ Tul ≤ T. (46) j , xj , Tul j=1 ,

19

The deleted samples and their request times may be fixed in advance or generated by external randomness, but they do not depend on the realized models, sampled mini-batches, Gaussian noise, or the outcomes of previous deletion requests. Arrival positions refer to the original training timeline and do not count any extra computation used to process earlier requests. (j) Let D(1) = D, and let D(j) and D(j+1) be the datasets immediately before and after request j. Thus x− j ∈ Dc− is removed j

(j+1)

to form Dc− , while the other local datasets are unchanged. We keep the learning hyperparameters fixed throughout the j stream and assume that every retained client dataset has size at least n≤

min 1≤j≤k+1, c∈[M ]

|Dc(j) |,

n ≥ b.

(47)

For a single request we use the actual pre-request dataset size; n is only needed when one common bound is used for the whole stream. Corollary 1 (Sequential deletion requests for FedZOUL-S). Consider the valid non-adaptive single-sample request stream in (j) (j) Eq. (46), and let nj = |Dc− | be the affected client’s pre-request data size. After every request j, the returned state at Tul has j

[T

(j)

]

law OS ul (D(j+1) ). If NSrep is the number of requests that trigger replay, then ) ( k (j) X Tul mb rep , E[NS ] ≤ min 1, M nj j=1   k (j)  X Tul mb  P(NSrep ≥ 1) ≤ min 1, .  M nj 

(48)

(49)

j=1

Under (47) and (42), these bounds are at most kρ and min{1, kρ}, respectively. Proof of Corollary 1. Fix the request stream and the perturbation pool. Let Xj− and Xj+ be the complete saved states (j) immediately before and after processing request j, both at position Tul . We prove by induction that d

[T

(j)

]

d

[T

(j)

]

Xj− = OS ul (D(j) ), Xj+ = OS ul (D(j+1) ).

(50)

The first equality for j = 1 follows from the initial learning run. Given its validity for request j, apply Theorem 2 with the fixed deletion x− j and fresh unlearning randomness to obtain the second equality. Continue with the retained-data learning (j+1) kernels and fresh randomness until Tul . This gives the first equality for request j + 1 and closes the induction. Equal arrival positions require no intervening learning. These are marginal state laws over all learning and unlearning randomness; they do not condition on the particular saved state produced by earlier requests or on whether those requests required replay. Let Ij indicate whether request j triggers replay. Applying the single-request replay bound to the first marginal in Eq. (50) gives ) ( (j) Tul mb . E[Ij ] = P(Ij = 1) ≤ min 1, M nj Pk Since NSrep = j=1 Ij , linearity of expectation proves Eq. (48); a union bound proves Eq. (49). Independence of the Ij is not needed. The bounds are uniform in the perturbation pool, so averaging over it preserves them. The calibrated bounds follow (j) from nj ≥ n and Tul ≤ T . For F ED ZOO-NS, subsampling plays the same first role: if the deleted sample is not selected, nothing changes. The difference is what happens after a hit. Replacing that sample changes the mean of the noisy coefficient vector but not its covariance, so the old and retained-data update distributions still overlap. This overlap can keep the two executions together even at an affected step. We quantify that one-step discrepancy first and then accumulate it over training. B. FedZOO-NS Stability For probability measures P ≪ Q, write 

Z DKL (P ∥Q) =

log Z 

D2 (P ∥Q) = log and let χ2 (P ∥Q) = exp(D2 (P ∥Q)) − 1.

dP dQ



dP, 2 dP dQ, dQ

(51)

20

Lemma 2 (Single-deletion replacement coupling). Let D = D− ∪ {x− } with |D| = n and |D− | = n − 1 ≥ b. Draw B uniformly from the size-b subsets of D and construct ( B, x− ∈ / B, ′ B = (52) − − (B \ {x }) ∪ {Y }, x ∈ B, where, on the second branch, Y is uniform on D− \ (B \ {x− }), independently of the seed sets and Gaussian noise. Then B ′ is uniform over the size-b subsets of D− , conditional on either branch and unconditionally. Keeping the seed sets of retained samples and assigning the seed set of x− to Y gives the joint mini-batch–seed law of a retained-data local step. Proof of Lemma 2. Conditional on x− ∈ / B, the original mini-batch is already a uniform size-b subset of D− . Conditional on a hit, fix a size-b subset A ⊆ D− . For each y ∈ A, the output is A when B \ {x− } = A \ {y} and Y = y. Hence P(B ′ = A | x− ∈ B) =

b

= n−1 b−1 (n − b)

1

.

n−1 b

(53)

The two branches therefore have the same retained mini-batch law. Conditional on any original batch and replacement, the seed sets assigned to the b resulting samples remain independent, each with the uniform size-q law on S. Indeed, replacement only relabels these seed sets and is independent of their values. This conditional law depends on neither the original batch nor the replacement. Averaging over their preimages proves the joint mini-batch–seed claim. The mini-batch itself remains an unordered set. For the coupling argument, we only need to match the coefficients associated with corresponding sample–seed pairs in the two executions. If the deleted sample is not selected, the two batches and all their seed sets are identical. If it is selected, the replacement sample inherits its seed set, while every retained sample keeps its original seeds. We can therefore compare the two clean coefficient vectors after placing corresponding sample–seed pairs in the same deterministic order. This ordering is only a representation: permuting the pairs together with their labels leaves both the Gaussian law and the accumulated seed-coordinate update unchanged. Under this correspondence, only the q coefficients that belonged to the deleted sample can change. Since each clipped and normalized clean coefficient lies in [−C/(bq), C/(bq)], the two clean vectors satisfy 2C ∥h − h′ ∥2 ≤ √ . b q

(54)

Here h′ denotes the retained-data coefficients written in the matched ordering. This is the only sensitivity bound needed below. For output stability, it is enough to follow the resulting seed-coordinate increment, because the local model and accumulator updates are deterministic once that increment is fixed. The saved sample identities and sample–seed correspondence matter for exact unlearning, but they do not affect the distributional comparison of the model updates themselves. Lemma 3 (One-step divergence after mini-batch subsampling). Fix a common pre-update state and suppose the affected client participates. Let n be its local data size before deletion. Let P and Q be the conditional laws of the resulting seed-coordinate increment on Dc and Dc− , respectively. Then DKL (P ∥Q) ≤ D2 (P ∥Q) ≤ εstep (n, σρ ),

(55)

where "

 2   2 2  # b 4C /(b q) exp εstep (n, σ) = log 1 + −1 . n σ2

(56)

Proof of Lemma 3. Let β = b/n, and let P1 denote the law of the seed-coordinate increment conditional on x− belonging to the original mini-batch. Conditional on a non-hit, the batch and its sample-specific seed sets have the retained-data law. Since the increment does not depend on how those pairs are enumerated, P = (1 − β)Q + βP1 .

(57)

On a hit, couple the batches by Lemma 2. Let λ collect the original batch, its replacement Y , and all sample-specific seed sets, and let π be their joint law conditional on the hit. Given λ, write both coefficient vectors in the original pair coordinates. Their Gaussian laws are Gλ = N (hλ , σρ2 Ibq ),

G′λ = N (h′λ , σρ2 Ibq ).

21

Define augmented measures P 1 (dλ, dv) = π(dλ)Gλ (dv) and Q(dλ, dv) = π(dλ)G′λ (dv). They share the same latent measure. Conditional Gaussian integration gives     ∥hλ − h′λ ∥22 2 −1 χ (P 1 ∥Q) = Eλ∼π exp σρ2  2 2  4C /(b q) ≤ exp − 1. (58) σρ2 Map both coefficient vectors to their seed-coordinate increments by summing coefficients that use the same seed. Under the matched sample–seed correspondence, the same labeled coefficients are summed on the two sides; only their values may differ. Lemma 2 gives the correct retained batch–seed law, so the second pushforward is exactly Q. Data processing therefore yields  2 2  4C /(b q) χ2 (P1 ∥Q) ≤ exp − 1. (59) σρ2 Writing u = dP1 /dQ, Eq. (57) implies Z exp(D2 (P ∥Q)) =

((1 − β) + βu)2 dQ

= 1 + β 2 χ2 (P1 ∥Q).

(60)

Combining this identity with Eq. (59) and DKL ≤ D2 proves the claim. The argument concerns the actual seed-coordinate update; no distributional comparison of an arbitrary storage ordering is needed. Theorem 3 (Output TV stability of FedZOO-NS). Consider an adjacent pair D and D− differing by the deletion of x− ∈ Dc− , and let nc− = |Dc− | before deletion. Conditionally on the fixed seed pool,
TV ONS,out (D), ONS,out (D− ) ( r ) Tm ≤ min 1, εstep (nc− , σρ ) . (61) 2M The same bound holds unconditionally over the random seed pool. Proof of Theorem 3. For the stability proof, condition on the sampled client sets and the seed-coordinate increments generated before the current local step. Mini-batch identities and the storage order of sample–seed coefficients need not be retained in this conditioning. Given Z, the initial state, and the preceding increments, the current model is deterministic, so Lemma 3 applies to the next update from the same pre-update model in the two executions. Fix this history before round r. The client set C r has the same data-independent law in both executions. If c− ∈ / C r , all − r conditional transitions in this round are identical. If c ∈ C , the KL chain rule and Lemma 3 give DKL (Pr ∥Qr | C r , Hr−1 ) ≤ Eεstep (nc− , σρ ).

(62)

Averaging over the common client-set law yields DKL (Pr ∥Qr | Hr−1 ) ≤

m Eεstep (nc− , σρ ). M

(63)

Applying the KL chain rule over the R rounds gives Tm εstep (nc− , σρ ). (64) M Data processing to the final model and Pinsker’s inequality prove (61). The bound is uniform in Z, so averaging over the pool gives the unconditional claim. DKL (P1:R ∥Q1:R ) ≤

Corollary 2 (Noise level for a target stability ρ). Fix 0 < ρ ≤ 1 before training and choose the standard deviation of every normalized scalar-noise coordinate as ( ) r 2C 2C Tm σρ = max . (65) √ , √ b q n qρ M Then F ED ZOO-NS is ρ-sample-level TV stable on the dataset class satisfying (47). More precisely,
TV ONS,out (D), ONS,out (D− ) r Tm 2C ≤ ρ. ≤ √ nc− q σρ M

(66)

22

Proof of Corollary 2. The first term in (65) ensures that the squared mean shift between the two Gaussian coefficient vectors is at most their noise variance. Using ex − 1 ≤ 2x for 0 ≤ x ≤ 1 and log(1 + x) ≤ x gives εstep (n, σρ ) ≤

8C 2 . n2 qσρ2

(67)

Substitution into Theorem 3 yields the first inequality in (66). The second term in (65), together with nc− ≥ n, gives the target bound. The NS bound reflects two events. A deletion can matter only when the affected client participates and the deleted sample enters its mini-batch. Even then, the two noisy updates may still coincide under the Gaussian coupling; this becomes more likely as the noise level grows relative to the possible change in the clean coefficients. Corollary 2 chooses the noise so that these effects accumulate to at most the target ρ. One detail in this bound is worth making explicit. The target client is sampled once per round, and that client set is reused for all E local steps. The factor m/M therefore appears once for the whole round, p rather than as an independent subsampling factor at every local position. This is why the sufficient noise scale depends on m/M . TV stability concerns only the distribution of the output. Exact unlearning is stronger: the saved state after a deletion must itself have the law of a fresh run on the retained data. For F ED ZOO-NS, the Gaussian noise lets us enforce this transition by transition. At an affected local step, we first try to keep the previously generated noisy coefficients through rejection sampling. If that fails, a reflection maps them to the correct retained-data Gaussian law, after which training continues on the retained data. This is the same coupling principle used for stability-based exact unlearning in [21], adapted here to the sample–seed coefficients and accumulators maintained by the federated algorithm. C. FedZOUL-NS Exact Unlearning Lemma 4 (Gaussian maximal coupling by hyperplane reflection). Let P = N (µ, σ 2 Ip ) and Q = N (ν, σ 2 Ip ), with densities p and q. For µ ̸= ν, define ν −µ µ+ν , e= m= , 2 ∥ν − µ∥2 Rµ,ν (x) = x − 2⟨x − m, e⟩e. (68) Draw X ∼ P and U ∼ Unif(0, 1) independently, and set ( X, U ≤ min{1, q(X)/p(X)}, Y = Rµ,ν (X), otherwise.

(69)

Then Y ∼ Q, and P(X ̸= Y ) = TV(P, Q)   ∥µ − ν∥2 −1 = 2Φ 2σ ∥µ − ν∥2 ≤ √ , 2πσ where Φ is the standard Gaussian CDF. If µ = ν, set Y = X.

(70)

Proof of Lemma 4. The map Rµ,ν is an involutive isometry with absolute Jacobian determinant one and exchanges the two means. Thus, p(Rµ,ν (x)) = q(x), q(Rµ,ν (x)) = p(x). (71) R For any measurable set A,R the accepted branch contributes A min{p, q}, while a change R of variables in the reflected branch shows that it contributes A (q − p)+ . Their sum is Q(A). The rejection probability is (p − q)+ = TV(P, Q). For distinct means, p(x) > q(x) precisely when ⟨x − m, e⟩ < 0. Integrating the two one-dimensional Gaussian projections on this √ halfspace gives the CDF formula. The final inequality follows from Φ(u) − 1/2 ≤ u/ 2π. Importantly, the target law Q is obtained by combining the acceptance and reflection branches. Conditional on rejection, the reflected value instead has density (q − p)+ / TV(P, Q) when this denominator is positive; it is not an independent draw from the full Q. For exact unlearning, the saved state also includes sample identities and seed assignments. The correspondence described above is enough to compare the two executions: retained samples keep their seeds, and the replacement sample inherits the deleted sample’s seeds. Whenever two coefficient vectors are compared, corresponding sample–seed pairs are written in the same deterministic order. Changing this order together with the labels does not change either the Gaussian law or the seed-coordinate update.

23

Lemma 5 (One-step exact transition for FedZOO-NS). Fix the seed pool, a local position (r, t), the participating client set, and common server and client optimization variables immediately before this position. Suppose the two datasets differ only by deleting x− ∈ Dc− . Couple the affected mini-batch as in Lemma 2, keep the corresponding seed assignments, and apply the rejection–reflection rule of Eqs. (24)–(26) when the affected client uses the deleted sample. Then the resulting mini-batches, seed assignments, noisy coefficients, and post-update variables have exactly the conditional law of one F ED ZOO-NS step on the retained data. If the rejection test accepts, the local model and accumulator remain unchanged. Proof of Lemma 5. All unaffected clients can use exactly the same transition. For the affected client, condition on the coupled original and retained mini-batches and their seed assignments. In the matched ordering, the original noisy coefficient vector has law N (h, σρ2 Ibq ), while the retained-data step requires N (h′ , σρ2 Ibq ). Lemma 4 shows that the acceptance and reflection branches together produce exactly this second Gaussian law. Reordering the transported coefficients together with their sample and seed labels, if needed by the deterministic storage convention, does not change that law. Lemma 2 already gives the correct retained mini-batch and seed-assignment distribution. Integrating over these coupled sampling variables therefore yields the correct joint law of the saved local information. The accumulator and model are deterministic functions of the noisy coefficients and the current optimization variables, so their post-update law is also correct. On acceptance, the coefficient values are unchanged under the sample–seed correspondence; because the same values are summed for each seed, the seed-coordinate increment, and hence the model and accumulator endpoints, are unchanged as well. [T

]

Tul →T Let UNSul denote the complete state returned by F ED ZOUL-NS at Tul after processing the deletion, and let UNS include completion of the horizon.

Theorem 4 (Exact unlearning of FedZOUL-NS). For every valid single-sample deletion x− ∈ Dc− arriving after local position Tul ,   d [T ] [T ] [T ] (72) UNSul ONSul (D), {x− } = ONSul (D− ). Consequently,   d [T ] [T ] Tul →T UNS ONSul (D), {x− } = ONS (D− ).

(73)

Both equalities hold jointly over the reconstructed model, global and local accumulators, sampled client sets, mini-batches, sample–seed correspondences, noisy coefficient vectors, and every other maintained state. The result holds for every σρ > 0. Proof of Theorem 4. Condition on the shared seed pool and process the executed training positions in chronological order. Before the first rejection, the two executions have the same optimization variables. At the next position, the original minibatch, seed assignments, and Gaussian noise have their usual fresh distributions. Lemma 5 then turns this step into the correct retained-data transition while preserving the current model and accumulator whenever the rejection test accepts. If the test accepts, only the saved sample identity may change: the noisy coefficient values are kept under the sample–seed correspondence, so the induced update is unchanged. If the first rejection occurs at (r⋆ , t⋆ ), the reflected coefficients give the correct retained-data update at that position. From Next(r⋆ , t⋆ ) onward, the algorithm generates fresh randomness on the retained data. The already sampled client set is kept for the rest of the current round, as it would be in the original training procedure, and later rounds draw fresh client sets. When t⋆ = E, the server first recomputes the round aggregation from the corrected local endpoints, exactly as specified in Algorithm 4. Applying this argument successively over the positions up to Tul shows that the state returned after the deletion follows the [T ] same transition kernels, in the same order, as a fresh F ED ZOO-NS execution on D− . Hence it has law ONSul (D− ). Continuing with the same retained-data kernels proves Eq. (73). Finally, averaging over the independently generated seed pool removes the conditioning. Define

 ϑρ = 2Φ

√  2C/(b q) − 1. 2σρ

(74)

This bounds the rejection probability conditional on a common pre-update model, coupled sampling variables, and a hit, before the current Gaussian noise and acceptance uniform are exposed. It is not a bound conditional on the realized noisy coefficient vector.

24

Proposition 1 (Probability of replay). Let ReplayNS denote the event that at least one verification test rejects. A rejection at Tul is included even though there is no later position to rerun: the endpoint at that position must still be corrected. For a deletion arriving at Tul , P(ReplayNS ) ≤ ΓNS (Tul , c− )   Tul mb := min 1, ϑρ M nc− ( ) 2CTul m ≤ min 1, √ . √ 2πM nc− q σρ

(75) (76)

Under (65), r  m ρTul P(ReplayNS ) ≤ min 1, √ M 2πT ) ( r Tm ≤ min 1, ρ . 2πM 

(77)

Proof of Proposition 1. Use the causal joint construction in the proof of Theorem 4. Given the paired past before a local position and its current client set, the original batch and noise have the prescribed fresh laws. If no earlier rejection has occurred and the affected client participates, the probability of a first rejection at this position is at most (b/nc− )ϑρ , by Lemma 4 and Eq. (54). Otherwise, a first rejection at this position is impossible. Dropping the no-earlier-rejection indicator and averaging over client participation bounds this probability by (m/M )(b/nc− )ϑρ . Summing over the first Tul positions proves Eq. (75). This calculation uses the marginal law at each position and does not condition on a particular saved training √ state. Equation (70) and ∥h − h′ ∥2 ≤ 2C/(b q) prove (76). Substituting (65), using nc− ≥ n, and then Tul ≤ T gives (77). Corollary 3 (Sequential deletion requests for FedZOUL-NS). Consider the valid non-adaptive single-sample request stream [T

(j)

(j)

]

(j)

in Eq. (46). After every request j, the state returned at Tul has law ONSul (D(j+1) ). In ΓNS (Tul , c− j ), evaluate the affected (j) rep client’s pre-request data size as nj = |Dc− |. If NNS counts requests for which the rejection test fails, including a rejection at j the request endpoint, then rep E[NNS ]≤

k X

(j)

ΓNS (Tul , c− j ),

(78)

j=1

  k  X  (j) rep P(NNS ≥ 1) ≤ min 1, ΓNS (Tul , c− ) . j  

(79)

j=1

Under (47) and (65), define (

r

ΓNS = min 1, ρ

Tm 2πM

) .

(80)

Then the two bounds are at most kΓNS and min{1, kΓNS }, respectively. Proof of Corollary 3. Fix the external request stream and the perturbation pool. Use the same induction as in Corollary 1, with Theorem 4 providing the single-request transition. If Xj− and Xj+ denote the complete states immediately before and after processing request j, then d

[T

(j)

]

d

[T

(j)

]

Xj− = ONSul (D(j) ), Xj+ = ONSul (D(j+1) ).

(81)

Fresh retained-data training between successive arrival positions preserves these marginal laws. Each request uses fresh replacement draws and acceptance uniforms. The induction is on the marginal law of the current state; it does not condition on the realized saved trajectory or on earlier acceptance outcomes. Let Ij indicate the first-rejection event for request j. Proposition 1, applied to the pre-request marginal, gives (j)

E[Ij ] = P(Ij = 1) ≤ ΓNS (Tul , c− j ). Linearity of expectation yields Eq. (78), and a union bound yields Eq. (79). The indicators need not be independent. Averaging over the perturbation pool preserves the bounds, and the calibrated claims follow from Eq. (77).

25

It is useful to distinguish the final-model stability guarantee from the probability that training must be rerun. Thepformer is bounded by ρ. The latter comes from the sequential coupling of local updates and is bounded by a quantity of order ρ T m/M , capped at one. The two need not coincide because F ED ZOUL-NS couples the training trajectory one local transition at a time rather than maximally coupling the final-model laws. The resulting replay bound is nevertheless no larger than the corresponding subsampling bound because ϑρ ≤ 1. Exactness tells us which state must be produced after a deletion. The next question is how much of the computation that has already been performed must be done again. We count only this additional work up to the request position; ordinary training after the request is not included. For F ED ZOUL-S, rerunning starts from the first position that used the deleted sample. For F ED ZOUL-NS, affected updates are first checked through the Gaussian coupling, and later training is rerun only if one of these checks rejects. D. Unlearning Cost We count loss evaluations, model reconstruction, and communication separately. A loss evaluation is one call to ℓ(w; x) for one sample. One scalar central difference therefore uses two evaluations, so rerunning one local position across all m participating clients uses 2mbq loss evaluations. Rerunning all Tul executed local positions uses Qfull (Tul ) = 2mbqTul .

(82)

These are aggregate oracle counts. They do not include restoring models, looking up saved coefficients, drawing replacement samples, or transferring checkpoints. For F ED ZOUL-NS, checking an affected position does not require recomputing all bq coefficients. Under the sample– seed correspondence, only the q pairs attached to the deleted sample can change. Let J denote these coordinates and write e with m = (h + h′ )/2, d = h′ − h. Then d is supported on J, and for the saved noisy vector h log

e J − mJ , dJ ⟩ e ⟨h q(h) = . e σρ2 p(h)

(83)

The reflection direction is supported on the same coordinates. Hence the acceptance test and, when needed, the reflection use only the q original and q replacement central differences, for at most 4q loss evaluations and O(q) coefficient operations once the pre-update model and saved coefficients are available. The corresponding correction to the local accumulator is obtained by summing the coefficient changes by seed; unchanged retained pairs need no new loss evaluation. A literal implementation that recomputes both full coefficient vectors uses up to 4bq evaluations instead, but the two implementations are algebraically equivalent. Let τS⋆ be the first executed position at which the deleted sample is used, with τS⋆ = ∞ if no such position exists. Define LS = (Tul − τS⋆ + 1)1{τS⋆ ≤ Tul }.

(84)

⋆ For F ED ZOUL-NS, let τNS be the first rejected affected position and set ⋆ ⋆ LNS = (Tul − τNS )1{τNS ≤ Tul },

(85)

because reflection already produces the correct retained-data update at the rejected position, so replay begins at its successor. Both lengths are defined to be zero when their trigger is absent. Let Nver count the affected local updates actually checked before the procedure stops, including the first rejected update when one exists. A rejection at the last executed position can trigger the NS correction even though no later position needs to be rerun. Proposition 1 bounds the probability of this event. Theorem 5 (Expected zeroth-order cost of one deletion). For a fixed single-sample deletion at 1 ≤ Tul ≤ T , using the sparse check above, E[LS ] ≤

Tul X

ΛS (u, c− )

u=1

( ≤ min Tul ,

) mbTul M nc− (Tul + 1) 2

,

(86)

and the aggregate loss-evaluation cost of F ED ZOUL-S satisfies E[QS ] = 2mbq E[LS ] ≤ Qfull (Tul )ΛS (Tul , c− ).

(87)

E[QS ] ≤ ρQfull (Tul ).

(88)

Under (42),

26

For F ED ZOUL-NS, mbTul , M nc− TX ul −1 E[LNS ] ≤ ΓNS (u, c− )

E[Nver ] ≤

(89)

u=1

≤ min

 



T − 1,  ul

mbϑρ  M nc− Tul (Tul − 1)

2

.

(90)



Its aggregate loss-evaluation cost satisfies TX ul −1 mbTul + 2mbq ΓNS (u, c− ) M nc− u=1   2 + ΓNS (Tul , c− ) . ≤ Qfull (Tul ) M nc−

E[QNS ] ≤ 4q

(91) (92)

Under (65), r   E[QNS ] 2 ρTul m ≤ + min 1, √ . Qfull (Tul ) M nc− M 2πT

(93)

Finally, when comparing one request under the same realized client and mini-batch sampling schedule, LNS ≤ LS

pathwise.

(94)

This compares replay lengths, not total query counts or running times. For Tul = 0, all query and replay counts are zero; the ratios above are used only for Tul > 0. Proof of Theorem 5. For F ED ZOUL-S, LS =

Tul X

1{τS⋆ ≤ u}.

(95)

u=1

Equation (40) gives P(τS⋆ ≤ u) ≤ ΛS (u, c− ). Taking expectations proves (86). Also, LS ≤ Tul 1{ReplayS }, which gives (87) and then (88). For F ED ZOUL-NS, verification occurs only when the target client is selected and the target sample appears in its mini-batch. mbTul The expected number of such hits is M nc− , and stopping after the first rejection can only reduce it. The sparse calculation above gives the verification cost and gives the pathwise accounting inequality QNS ≤ 4qNver + 2mbqLNS .

(96)

The reflected position requires no further loss evaluations. Moreover, LNS =

TX ul −1

⋆ 1{τNS ≤ u}.

(97)

u=1 ⋆ Proposition 1 gives P(τNS ≤ u) ≤ ΓNS (u, c− ). This proves (90) and the first query bound. Monotonicity of ΓNS gives the second. The bound under the chosen noise level follows from (77). Under a common sampling schedule, a rejection can occur only at a position where the deleted sample is used. Hence the first rejected position is no earlier than the first affected position, and replay after reflection starts one position later. This proves the pathwise inequality.

For F ED ZOUL-S, the expected loss-evaluation cost is controlled by the chance that the deleted sample appeared before the request. Under the chosen stability level, this is at most a ρ fraction of rerunning all executed positions. F ED ZOUL-NS adds a small verification cost, but Gaussian acceptance can avoid rerunning an affected update and everything that follows it. Equation (94) compares only the number of local positions rerun; model reconstruction and communication are considered next. Communication also depends on where the first hit or rejection occurs, because only round boundaries reached after that point need to be processed again. Server aggregation occurs at positions E, 2E, . . .. Hence the expected number of completed aggregations repeated by F ED ZOUL-S is at most ⌊Tul /E⌋

X r=1

ΛS (rE, c− ),

(98)

27

and for F ED ZOUL-NS it is at most

⌊Tul /E⌋

X

ΓNS (rE, c− ).

(99)

r=1

If the request arrives partway through a round, that last partial round is also visited whenever the first hit or rejection has already occurred. Thus the expected number of visited round blocks is bounded by ⌊Tul /E⌋

X

ΛS (rE, c− ) + 1{E ∤ Tul }ΛS (Tul , c− )

(100)

ΓNS (rE, c− ) + 1{E ∤ Tul }ΓNS (Tul , c− )

(101)

r=1

for F ED ZOUL-S, and by ⌊Tul /E⌋

X r=1

for F ED ZOUL-NS. These bounds use only the probability that the first hit or rejection has occurred by the corresponding boundary; no independence across rounds is required. These round counts determine the communication needed for the K-dimensional accumulator. The seed pool is already shared, the server stores the global accumulator checkpoints, and each client stores its own local state. With separate downlinks to the m clients, every visited round block needs at most one K-scalar global-accumulator download per client, and every completed aggregation that is repeated needs at most one K-scalar endpoint upload per client. Therefore, the expected additional accumulator communication of F ED ZOUL-S is at most   ⌊Tul /E⌋ X mK 2 ΛS (rE, c− ) + 1{E ∤ Tul }ΛS (Tul , c− ) . (102) r=1

For F ED ZOUL-NS, the corresponding bound is   ⌊Tul /E⌋ X mbTul . mK 2 ΓNS (rE, c− ) + 1{E ∤ Tul }ΓNS (Tul , c− ) + K M nc− r=1

(103)

The last term appears because checking an affected NS update may require the global accumulator that was current before that update. One such checkpoint is enough to reconstruct the corresponding model, wr,t−1 = w0 − η c

K X

ar−1 + ar,t−1 zk , k c,k

(104)

k=1 mbTul and the expected number of affected updates checked is at most M nc− . If a common downlink broadcast is counted once rather than once per recipient, the factors multiplying the completed-round sums become (m + 1)K instead of 2mK, while the partial-round download contributes only K. Sample identifiers, control messages, and protocol headers are not included because their size depends on the implementation. These bounds also clarify why replay length alone does not determine communication. A rejection at a completed final round can require correcting that aggregation even when there is no later local step to rerun. Conversely, NS may check several affected updates without rejecting any of them, so checkpoint downloads can be positive even when no training step is rerun. (j)

Corollary 4 (Cost over a request stream). Consider the valid non-adaptive single-sample request stream in Eq. (46). Let Tul be the executed horizon when request j arrives and let nj be the affected client’s data size immediately before that request. Then the cumulative expected loss-evaluation costs satisfy (j)

E[Q1:k S ] ≤ 2mbq E[Q1:k NS ] ≤ 4q

k T ul X X

  umb min 1, , M nj j=1 u=1

(105)

k (j) X mbT ul

j=1

M nj (j)

+ 2mbq

k Tul X X−1 j=1

Empty sums are interpreted as zero.



umbϑρ min 1, M nj u=1

 .

(106)

28

With separate downlinks, the cumulative expected accumulator communication of F ED ZOUL-S is at most  (j)   ⌊Tul /E⌋ k X X rEmb 2 mK min 1, M nj r=1 j=1 ( )# (j) Tul mb (j) +1{E ∤ Tul } min 1, , M nj

(107)

while for F ED ZOUL-NS it is at most mK

k X

(j)



⌊Tul /E⌋

2

X r=1

j=1



 rEmbϑρ min 1, M nj (

(j) +1{E ∤ Tul } min

+K

k (j) X mbT ul

j=1

M nj

.

(j)

T mbϑρ 1, ul M nj

)#

(108)

The corresponding broadcast bounds replace the factor 2mK on each completed-round sum by (m + 1)K and the factor mK on each partial-round term by K. Proof of Corollary 4. Fix the external request stream. By Corollaries 1 and 3, immediately before each request the current state has the same marginal law as the corresponding learning algorithm run on the data then present. The single-request bounds (j) above therefore apply to every request with its current horizon Tul and affected-client size nj . Summing these bounds and using linearity of expectation gives Eqs. (105)–(108). No independence across requests is needed. If the request stream itself is random but chosen independently of the algorithmic randomness, the same bounds hold after averaging over the stream. Loss evaluations and communication capture the dominant costs, but processing a deletion also entails ordinary arithmetic. Reconstructing one model from the K shared directions costs O(Kd) operations in a direct implementation. Rerunning one local step costs O(bqd + K) beyond the loss evaluations, a sparse NS check costs O(qd + q), and one server aggregation costs O(mK). Combining these per-operation costs with the expected numbers of checked updates, rerun positions, visited round blocks, and repeated aggregations above gives the corresponding expected arithmetic work. The chronological search for the first affected mini-batch can require up to O(bTul ) comparisons with a direct scan; an inverted index can reduce lookup time at the price of maintaining that index whenever stored mini-batches change. These are aggregate work bounds rather than elapsed-time guarantees. Under ideal parallel execution, the forward-evaluation component alone is 2bq evaluations per rerun S step and 4q evaluations per checked NS update plus 2bq evaluations per rerun NS step. Model reconstruction, saved-state access, communication, and synchronization remain additional costs. In particular, the TV parameter ρ directly bounds the expected S query fraction under the chosen subsampling level, whereas for NS the finalmodel TV guarantee and the transitionwise replay probability are different quantities. Consequently, neither the replay-length comparison nor the oracle-cost fraction by itself implies that one method has lower total unlearning time than the other. We next ask whether the same finite seed pool that makes communication and unlearning efficient still permits meaningful optimization. The objective being evaluated is unchanged, but every update lies in the span of the shared perturbation directions. We therefore first express the actual training trajectory in these seed coordinates, prove convergence in the resulting subspace, and then determine when that guarantee also controls the full model-space gradient. E. Fixed-Seed Parameterization Every update is a linear combination of the shared perturbation directions, so the entire trajectory stays in the affine space generated by the seed pool. It is convenient to use the accumulated seed coefficients themselves as optimization variables; this makes clear that the algorithm restricts the reachable model space, not the underlying federated objective. Let Z = [z 1 , . . . , z K ] ∈ Rd×K (109) be the perturbation matrix generated by the shared seed pool S = {s1 , . . . , sK }, where z k = Perturb(sk ). Define the normalized seed matrix 1 A = √ Z. (110) K For the global and local accumulators in Section IV-A, define √ (111) ur = −η K ar , √ r,t r−1 r,t uc = u − η K ac . (112)

29

The reconstructed models are therefore wr = w0 + Aur , 0 r,t wr,t c = w + Auc .

(113)

Thus, every model lies in WZ = w0 + range(Z). In these coordinates, the local and global objectives are simply FZ,c (u) = fc (w0 + Au), M

FZ (u) =

1 X FZ,c (u) = f (w0 + Au). M c=1

(114)

Equation (114) is exactly the original federated objective restricted to the affine space WZ . In particular, inf FZ (u) = inf f (w).

u∈RK

w∈WZ

(115)

This fixed random-subspace interpretation is consistent with the finite-seed representation used by FedKSeed [18]. By the chain rule, ∇FZ,c (u) = A⊤ ∇fc (w0 + Au), ∇FZ (u) = A⊤ ∇f (w0 + Au).

(116)

If every fc is L-smooth in model space, then every FZ,c is LZ -smooth in parameter space, where L ∥Z∥2op . K The gradient of the restricted objective has a direct full-space interpretation. At w = w0 + Au, LZ = L∥A∥2op =

(117)

1 ∥Z ⊤ ∇f (w)∥2 . (118) K Thus the convergence quantity below is simply the squared full gradient measured along the shared seed directions; no separate surrogate objective is introduced. For x ∈ Dc and k ∈ [K], define the fixed-seed central difference 1  ℓ(w0 + Au + µz k ; x) dµ,k (u; x) = (119) 2µ  − ℓ(w0 + Au − µz k ; x) . √ K, a query along z k is exactly a coordinatewise central difference of the parameterized original loss, Because Aek = z k / √ with coordinate step µ K. Let ∥∇FZ (u)∥2 =

[dµ (u; x)]k = dµ,k (u; x), 1 X dµ,c (u) = dµ (u; x). nc

(120)

x∈Dc

For FedZOO-NS, define the clipped counterparts by [dC µ (u; x)]k = clipC (dµ,k (u; x)), 1 X C dµ (u; x). dC µ,c (u) = nc

(121)

x∈Dc

r,t r,t−1 The accumulator update already gives the corresponding step in these coordinates. If ∆ar,t , then c = ac − ac √ r,t−1 ur,t − η K ∆ar,t c = uc c .

(122)

For F ED ZOO-S, uniform mini-batch and seed sampling therefore gives h√ i 1 E K ∆ar,t F , c, Z = √ dµ,c (ur,t−1 ), (123) r,t−1 c c K where Fr,t−1 contains the fixed seed pool, the current client set, and everything revealed before this local step. For F ED ZOONS, clipping changes the mean to h√ i 1 r,t−1 E K ∆ar,t F , c, Z = √ dC ). (124) r,t−1 c µ,c (uc K

30

The added scalar Gaussian noises are independent and mean zero. After mapping them to seed coordinates, their contribution to the conditional second moment is Kbqσρ2 ; repeated use of the same seed coordinate does not create cross terms because the scalar noises are independent. Define the finite-difference and clipping biases by 1 bµ,c (u) = √ dµ,c (u) − ∇FZ,c (u), K 1 bC,c (u) = √ (dC µ,c (u) − dµ,c (u)). K

(125) (126)

If every sample loss is L-smooth, then K

2 ∥bµ,c (u)∥2 ≤ βµ,Z ,

2 βµ,Z =

L2 µ2 X ∥z k ∥4 . 4K

(127)

k=1

Indeed, the error of the kth central difference is at most Lµ∥z k ∥2 /2. With this fixed-seed parameterization in place, we next quantify the optimization progress of both learners on the restricted form of the original federated objective. F. Convergence in the Seed Subspace Because all model movement is confined to the span of the shared seeds, the quantity we can control directly is the full gradient projected onto this span. The main result below shows how this projected stationarity depends on the number of rounds, participating clients, local steps, finite-difference error, and client heterogeneity. Unless stated otherwise, probabilities and expectations in this subsection are conditional on Z. At one local step, the only sampling variability comes from choosing a mini-batch and then choosing seed coordinates for the selected examples. We can compute this variance directly, without introducing another estimator solely for the proof. If a F ED ZOO-S step starts from u, then 2

√

E

1 K ∆ar,t c − √ dµ,c (u) K K −q 1 X = ∥dµ (u; x)∥2 bqK nc x∈Dc 1 X nc − b ∥dµ (u; x) − dµ,c (u)∥2 . + b(nc − 1)K nc

(128)

x∈Dc

The second term is zero when b = nc , with the ratio interpreted as zero when nc = b = 1. For F ED ZOO-NS, the same calculation applied before the Gaussian perturbation gives √

E

1 C K ∆ar,t c,clip − √ dµ,c (u) K   C2 K − q nc − b ≤ + . b q nc − 1

2

(129)

Here ∆ar,t c,clip denotes only the clipped finite-difference part of the accumulator increment at that step. Adding the independent Gaussian coefficients contributes another Kbqσρ2 to the conditional variance. These calculations expose the only differences between the two learners that matter for convergence: the mean of a local seed-coordinate update, its variation around that mean, and its overall second moment. We state the regularity conditions directly in terms of the update produced by the algorithm. Assumption 1 (Utility regularity). Conditionally on the realized seed pool Z, the following hold for the learner A ∈ {S, NS}. (i) Every sample loss is L-smooth, and the original federated objective is lower bounded: f (w) ≥ f ⋆ > −∞,

w ∈ Rd .

(130)

(ii) Client gradients in the fixed seed coordinates have bounded heterogeneity: M

1 X 2 ∥∇FZ,c (u) − ∇FZ (u)∥2 ≤ ζZ , M c=1

u ∈ RK .

(131)

31

(iii) When one local step starts from u, let ∆aA,c (u) be the random accumulator increment produced by that step. There exist finite constants βA , νA , GA such that, uniformly over clients and starting points, h√ i 2 E K ∆aA,c (u) | Z − ∇FZ,c (u) ≤ βA2 ,   2 √ √ E K ∆aA,c (u) − E[ K ∆aA,c (u) | Z] Z ≤ νA2 , h √ i (132) E ∥ K ∆aA,c (u)∥2 Z ≤ G2A . The bounds above also give explicit choices for these constants. For F ED ZOO-S, the only systematic bias is the centraldifference error, so 2 βS2 ≤ βµ,Z . (133) For F ED ZOO-NS, clipping adds another bias, and one may take 2 2 2 βNS ≤ 2βµ,Z + sup ∥dC (u) − dµ,c (u)∥2 . K c,u µ,c

(134)

Likewise, νS2 can be chosen as the supremum of the right-hand side of Eq. (128), while for F ED ZOO-NS one may use   nc − b C2 K − q 2 νNS + + Kbqσρ2 . ≤ sup (135) q nc − 1 c,u b Because every clipped coefficient has magnitude at most C/(bq), the noisy learner also satisfies the simple second-moment bound G2NS ≤ KC 2 + Kbqσρ2 . (136) The heterogeneity assumption above is no stronger than a standard model-space condition up to the geometry of the seed matrix. In particular, if M 1 X ∥∇fc (w) − ∇f (w)∥2 ≤ ζf2 , (137) M c=1 then

∥Z∥2op 2 ζf . K A standard model-space gradient bound is sufficient for these moment conditions. If there is a finite Gf such that 1 X ∥∇ℓ(w; x)∥2 ≤ G2f , c ∈ [M ], w ∈ Rd , nc 2 ζZ ≤ ∥A∥2op ζf2 =

(138)

(139)

x∈Dc

then sample-wise smoothness gives 1 X 2 ∥dµ (u; x)∥2 ≤ 2∥A∥2op G2f + 2βµ,Z . Knc

(140)

x∈Dc

Together with Eqs. (128)–(136), this is enough to make the constants in Assumption 1 finite for both learners. Equation (139) is only a sufficient condition; it is not implied by smoothness and is not otherwise required by the theorem. For uniform size-m client sampling without replacement, define   M − m , M > 1, χm = m(M − 1) (141)  0, M = 1. Theorem 6 (Convergence in the fixed seed subspace). Fix a realized pool Z and suppose Assumption 1 holds for A ∈ {S, NS}. If η > 0, 4ηLZ E ≤ 1, (142) then the corresponding learner satisfies   R 1 X 1 E ∥Z ⊤ ∇f (wr−1 )∥2 Z R r=1 K ≤

2(f (w0 ) − f ⋆ ) + 6βA2 ηER   νA2 2 + 8LZ η Eχm ζZ + + 2L2Z η 2 E 2 G2A . m

(143)

32

The expectation is over the learner’s randomness after the pool is fixed. Averaging over pools requires the conditions stated below. The four terms reflect different parts of the learning process. More rounds and local steps reduce the optimization term through 1/(ηER), whereas the finite-difference and clipping bias does not disappear merely by training longer. Averaging across participating clients reduces the centered local variation through νA2 /m. Increasing the number of local steps has a 2 second effect, however: it also enlarges the contribution of client heterogeneity and local drift through Eχm ζZ and E 2 G2A . In F ED ZOO-NS, the Gaussian noise required for stability enters the last two quantities as well, so the same inequality makes the stability–utility tradeoff explicit. Proof of Theorem 6. Let Hr−1 contain Z and the complete history through r − 1, before sampling C r , and write √ round r,t K ∆a for the scaled accumulator increment at Er [·] = E[· | Hr−1 ]. Fix r, put u = ur−1 and g = ∇FZ (u). Write v r,t = c c local step t. The bounds in Assumption 1 apply to these actual updates. The round recursion is E

ur = u − ηS r ,

Sr =

1 X X r,t vc . m r t=1

(144)

c∈C

To use uniform client sampling without tying a client’s local trajectory to whether it is selected, imagine drawing the local randomness for every client before C r is sampled, independently across clients, and then executing only the selected trajectories. This equivalent construction does not change the Plaw of the algorithm, and every such trajectory starts from u. The second− u = −η s<t v r,s moment bound together with ur,t−1 c c therefore gives, for every client, Er ∥ur,t−1 − u∥2 ≤ η 2 (t − 1)2 G2A . c

(145)

P Let v r,t = m−1 c∈C r v r,t c . Uniform client sampling, smoothness, Jensen’s inequality, and (145) imply Er [v r,t ] = g + er,t ,

(146)

∥er,t ∥2 ≤ 2L2Z η 2 (t − 1)2 G2A + 2βA2 .

(147)

where Using ⟨a, b⟩ ≥ −∥a∥2 /4 − ∥b∥2 for the error term, 3 ∥g∥2 − 2L2Z η 2 (t − 1)2 G2A − 2βA2 . (148) 4 At a fixed local step, separate each update into its local gradient, its conditional bias, and the fresh randomness of that step. Define r,t−1 bc (x) = E[v r,t = x, Z] − ∇FZ,c (x), (149) c | uc Er ⟨g, v r,t ⟩ ≥

so Assumption 1 gives ∥bc (x)∥2 ≤ βA2 . With Fr,t−1 denoting the history available immediately before the sampling and Gaussian noise at local step t, define r,t r,t−1 ϵr,t ) − bc (ur,t−1 ), c = v c − ∇FZ,c (uc c

E[ϵr,t c | Fr,t−1 ] = 0.

(150)

The difference between the full round update and Eg can then be written as four sources of error: client sampling, local drift, bias, and fresh stochastic variation, S r − Eg = Ar + D r + B r + N r , (151) where Ar = E Dr = Br = Nr =

1 m 1 m

! 1 X ∇FZ,c (u) − g , m r

c∈C E XX c∈C r t=1 E XX

∇FZ,c (ur,t−1 ) − ∇FZ,c (u) , c bc (ur,t−1 ), c

c∈C r t=1

E X 1 X

m t=1

ϵr,t c .

(152)

c∈C r

Each term is controlled by a different part of the assumptions. Uniform sampling without replacement gives the finite-population variance in the first line. Smoothness together with Eq. (145) controls the change of each local gradient in the second. The

33

third follows from the bias bound. Finally, the centered errors are martingale differences across local steps, while different clients use independent fresh sampling and noise at a fixed step. Hence 2 Er ∥Ar ∥2 ≤ E 2 χm ζZ , 2 2 4 L η E 2 Er ∥D r ∥2 ≤ Z GA , 3 2 2 2 Er ∥B r ∥ ≤ E βA , E (153) Er ∥N r ∥2 ≤ νA2 . m PE For the drift term, Cauchy–Schwarz gives L2Z E t=1 η 2 (t − 1)2 G2A . For the stochastic term, orthogonality of the martingale differences gives 2 E X E 1 X r,t 2 ≤ νA2 . ϵc (154) Er ∥N r ∥ = Er m m r t=1 c∈C

Only the new randomness generated at each local step is used here; the local trajectories themselves need not be independent across their E steps. Combining the four contributions yields 2 Er ∥S r ∥2 ≤ 2E 2 ∥g∥2 + 8E 2 χm ζZ + 8E 2 βA2 8E 2 8L2Z η 2 E 4 2 ν + GA . (155) + m A 3 We can now return to the objective. Smoothness of FZ applied to the round in Eq. (144), together with Eqs. (148) and Pupdate E (155), gives a descent term plus the three error contributions above. Using t=1 (t − 1)2 ≤ E 3 /3 and the step-size condition 4ηLZ E ≤ 1 simplifies their coefficients, giving

ηE ∥g∥2 + 3ηEβA2 2 4LZ η 2 E 2 2 + 4LZ η 2 E 2 χm ζZ + νA m 2 3 3 2 + LZ η E GA .

Er [FZ (ur )] ≤ FZ (u) −

(156)

Since FZ (ur ) = f (wr ) ≥ f ⋆ , summing over r and using Eq. (118) proves Eq. (143). The theorem controls an average over training checkpoints, rather than only the final model. Equivalently, if J is drawn independently and uniformly from {0, . . . , R − 1}, then the projected gradient at wJ obeys the same bound in Eq. (143). This random-checkpoint view is only an interpretation of the average: both algorithms still return wR , and the theorem does not claim the same guarantee for that last iterate or for a checkpoint chosen adaptively from the run. The result is conditional on the realized seed pool. For a Gaussian pool, ∥Z∥op has unbounded support, so no fixed positive step size can satisfy the theorem’s condition for every realization. The next corollary therefore chooses a deterministic step size that is valid on a high-probability spectral event. An unconditional expectation requires, in addition, control of the complementary event. Corollary 5 (Fixed step size with a Gaussian seed pool). Suppose the columns of Z are independent N (0, Id ) vectors. For 0 < δ < 1, set 2 p √ L √ Lδ = d + K + 2 log(2/δ) , K n o p √ √ Esp (δ) = ∥Z∥op ≤ d + K + 2 log(2/δ) . (157) Assume utility regularity holds for every pool in Esp (δ) and choose the deterministic step size 0<η≤

1 . 4ELδ

(158)

Then, with probability at least 1 − δ over the seed pool, Eq. (143) holds, with its expectation conditional on that pool. Proof of Corollary 5. The Gaussian singular-value bound [49] gives, for t ≥ 0,   √ √ 2 PZ ∥Z∥op > d + K + t ≤ 2e−t /2 .

(159)

Thus PZ (Esp (δ)) ≥ 1 − δ. On this event, LZ ≤ Lδ , so Eq. (158) implies Eq. (142). Apply Theorem 6 separately for each such pool.

34

Under the additional global moment condition (139), the excluded pools can also be controlled. Using its explicit constants above, the joint expectation obeys   R 1 X 1 ⊤ r−1 2 EZ,alg ∥Z ∇f (w )∥ R r=1 K s        2(f (w0 ) − f ⋆ ) νA2 2d 2 2 2 2 2 2 2 ≤ EZ 1Esp (δ) + 6βA + 8LZ η Eχm ζZ + + 2LZ η E GA + Gf δ d2 + . (160) ηER m K Indeed, ∥∇f (w)∥2 ≤ G2f by Jensen’s inequality, so K −1 ∥Z ⊤ ∇f (w)∥2 ≤ G2f ∥A∥2op . On the complementary event, Cauchy– Schwarz and E∥A∥4F = d2 + 2d/K give the second term. The latter identity follows by expanding the square of the sum of dK independent squared standard Gaussians, divided by K 2 . On Esp (δ), integrate the conditional theorem. All terms are integrable with the explicit constants, since they grow at most polynomially in the Gaussian entries. Without the additional moment condition, Corollary 5 remains a high-probability statement about the pool, not an unconditional expectation bound or a high-probability statement about the training noise. The leading terms in Theorem 6 have the familiar stepsize tradeoff: a smaller stepsize slows the decrease of the initial objective gap, whereas a larger one magnifies stochastic variation and client heterogeneity. Balancing these two effects gives a more transparent rate. Corollary 6 (Balanced step size). Under the conditions of Theorem 6, assume 2 Eχm ζZ +

If

s η=

νA2 > 0, m

f (w0 ) > f ⋆ .

1 f (w0 ) − f ⋆ ≤ , 2 2 4LZ ER (Eχm ζZ + νA /m) 4LZ E

(161)

then   R 1 X 1 ⊤ r−1 2 E ∥Z ∇f (w )∥ R r=1 K s
2 + ν 2 /m) LZ f (w0 ) − f ⋆ (Eχm ζZ A ≤8 + 6βA2 ER
LZ EG2A f (w0 ) − f ⋆ + 2 + ν 2 /m) . 2R (Eχm ζZ A

(162)

Proof of Corollary 6. Substitute Eq. (161) into Eq. (143). The first term and the term linear in η are then equal up to the displayed constants, while the η 2 term gives the final R−1 contribution. The upper bound on η is exactly the stepsize condition required by Theorem 6. If the balancing choice in Eq. (161) is larger than 1/(4LZ E), one may instead use this boundary value and apply Theorem 6 directly. For a stream of deletion requests, the stepsize is inherited from the original learning run and is not retuned after each request. The balanced bound also shows how client participation enters the rate. Since χm =

M −m 1 ≤ , m(M − 1) m

the quantity inside the square root is at most 2 EζZ + νA2 . m Hence, when E, the seed pool, and the estimator moments are fixed, the leading term decreases as   1 O √ . mER

(163)

For fixed E, this means that in the regime where the leading stochastic term dominates the bias and the higher-order local-drift term, multiplying the number of participating clients by a factor reduces the required number of communication rounds by the same factor. This is the usual linear client speedup. It is not a global asymptotic statement: as m grows, the R−1 local-drift term and any nonvanishing bias eventually become limiting. Full participation also removes the client-sampling heterogeneity term exactly because χM = 0.

35

For F ED ZOO-S, this averaging gain is not affected by any stability noise. For F ED ZOO-NS, increasing m still reduces the sampling and client-heterogeneity terms, but the Gaussian variance required for stability may leave a residual that does not shrink with mER. In particular, when the horizon-dependent term in Eq. (65) determines σρ , Kbqσρ2 4KbC 2 . = mER M n 2 ρ2

(164)

Thus the client-averaging benefit eventually saturates at the stability-induced noise and bias floors. This dependence is important when interpreting the balanced rate: for F ED ZOO-NS, the variance and second-moment bounds inherit the horizon dependence of σρ and should not be treated as fixed asymptotic constants. G. From Seed-Subspace to Full-Space Guarantees Up to this point, the theory controls only the component of the gradient seen through the fixed seed directions. Nothing stronger is possible for an arbitrary objective: a low-dimensional seed span may be orthogonal to a nonzero component of the full gradient. A full-space statement therefore needs one additional property–the seed span must preserve the gradients that can occur along the training trajectory. Assumption 2 (Gradient coverage by the seed span). For the realized perturbation pool, there exist finite constants κZ > 0 and εcov ≥ 0, fixed before the subsequent training randomness, such that every possible global checkpoint w satisfies 1 ∥Z ⊤ ∇f (w)∥2 ≥ κZ ∥∇f (w)∥2 − ε2cov . K Corollary 7 (Full-space stationarity). Under the conditions of Theorem 6 and Assumption 2,

(165)

R

1 X E∥∇f (wr−1 )∥2 R r=1  1 2(f (w0 ) − f ⋆ ) ≤ + 6βA2 + ε2cov κZ ηER    ν2 2 +8LZ η Eχm ζZ + A + 2L2Z η 2 E 2 G2A . m

(166)

Proof of Corollary 7. Rearrange (165), average over the iterates, and apply Theorem 6. Proposition 2 (Coverage under a fixed gradient subspace). Suppose z 1 , . . . , z K are independent N (0, Id ) vectors. Let V ⊆ Rd be a fixed r-dimensional subspace chosen independently of the seed pool. Assume, for every pool under consideration, that all possible global checkpoints satisfy ∇f (w) ∈ V. (167) For 0 < δ < 1, define

√

p 2 log(2/δ) √ . K If αK,r,δ < 1, then, with probability at least 1 − δ over the seed pool, αK,r,δ =

r+

1 ∥Z ⊤ g∥2 ≤ (1 + αK,r,δ )2 ∥g∥2 K simultaneously for every g ∈ V. Consequently, Assumption 2 holds with (1 − αK,r,δ )2 ∥g∥2 ≤

κZ = (1 − αK,r,δ )2 ,

εcov = 0.

(168)

(169)

(170)

Proof of Proposition 2. Let U ∈ Rd×r have orthonormal columns spanning V. Then Z ⊤ U is a K × r standard Gaussian matrix. The two-sided Gaussian singular-value bound used in the proof of Corollary 5 gives, with probability at least 1 − δ, σmin (A⊤ U ) ≥ 1 − αK,r,δ , σmax (A⊤ U ) ≤ 1 + αK,r,δ .

(171)

Applying these inequalities to g = U y proves (169). The event is uniform over the entire subspace, so it remains valid although the optimization iterates depend on the same seed pool. Corollary 8 (High-probability full-space guarantee). Suppose the Gaussian-pool and fixed-subspace conditions of Proposition 2 hold. Let 0 < δ < 1, αK,r,δ/2 < 1, and choose a deterministic step size 0<η≤

1 . 4ELδ/2

(172)

36

Assume utility regularity holds on Esp (δ/2). With probability at least 1 − δ over the seed pool,     R  1 X  2(f (w0 ) − f ⋆ ) 1 νA2 r−1 2 2 2 2 2 2 2 E ∥∇f (w )∥ | Z ≤ + 6βA + 8LZ η Eχm ζZ + + 2LZ η E GA . R r=1 (1 − αK,r,δ/2 )2 ηER m (173) Proof of Corollary 8. Let Ecov (δ/2) be the uniform embedding event in Proposition 2, and set Eδ = Esp (δ/2) ∩ Ecov (δ/2).

(174)

A union bound gives PZ (Eδ ) ≥ 1 − δ; independence of the two events is not needed. On this event, the fixed step size is valid and the coverage constant is at least (1 − αK,r,δ/2 )2 . Apply Corollary 7 conditionally on each such pool. If Eq. (139) also holds, the same event split yields the unconditional bound R

1 X EZ,alg ∥∇f (wr−1 )∥2 R r=1 h    i 0 νA2 )−f ⋆ ) 2 2 2 2 2 2 EZ 1Eδ 2(f (w + 6β + 8L η Eχ ζ + + 2L η E G Z m Z Z A A ηER m ≤ + δG2f , (1 − αK,r,δ/2 )2

(175)

because ∥∇f ∥2 ≤ G2f on the excluded pools. The fixed-subspace condition concerns the gradients themselves at all possible global checkpoints; it is not implied merely by a low-rank Hessian or the existence of a low-dimensional set of good solutions. The coverage condition cannot in general be removed. If rank(Z) < d, choose f (w) =

1 ∥w − w⋆ ∥2 2

(176)

with w⋆ − w0 ∈ / range(Z). The minimizer over WZ is w⋆Z = w0 + ΠZ (w⋆ − w0 ),

(177)

where ΠZ is the orthogonal projector onto range(Z). Its gradient is orthogonal to that range, so 1 ∥Z ⊤ ∇f (w⋆Z )∥2 = 0, K

∥∇f (w⋆Z )∥ > 0.

(178)

For an independent Gaussian pool with K < d, the same construction can be fixed before the pool is sampled: any nonzero w⋆ −w0 lies outside range(Z) almost surely. Thus a method confined to a rank-deficient seed span cannot guarantee full-space stationarity for arbitrary smooth objectives. A condition relating the seed span to the gradients encountered during training is therefore genuinely necessary, rather than an artifact of the proof. The exactness result now closes the loop between unlearning and utility. After request j is processed, the returned state has exactly the law of a fresh run on the retained data. The same convergence theorem can therefore be applied to that run without introducing a separate unlearning-error term. Only the objective, and hence its data-dependent constants, changes after deletion. H. Utility After Unlearning (j+1)

After request j, denote the retained local datasets by Dc

and write X 1 fc(j) (w) = (j+1) ℓ(w; x), |Dc | (j+1) x∈Dc

f (j) (w) =

M 1 X

f (j) (w). M c=1 c

(179)

The constants in Assumption 1 are evaluated for this retained objective and are denoted by βA,j , νA,j , GA,j , and ζZ,j ; also let fj⋆ = inf w f (j) (w) > −∞. The seed pool and algorithmic hyperparameters are inherited from the original run. The same sample-wise smoothness constant L therefore gives the same LZ . The other constants may change after a deletion and must be valid along the corresponding retained-data trajectory. Corollary 9 (Utility after unlearning). Consider the non-adaptive request stream in Eq. (46). After request j, continue the state returned by the unlearning procedure on D(j+1) to the fixed horizon R with no further requests, and denote the resulting

37

r,(j)

global trajectory by {wA }R r=0 . Suppose Assumption 1 holds for this retained dataset. Condition on a realized seed pool Z, keep the original step size, and assume 4ηLZ E ≤ 1. Then !   R 2 νA,j 2(f (j) (w0 ) − fj⋆ ) 1 1 X r−1,(j) 2 ⊤ (j) 2 2 E ∥Z ∇f (wA )∥ ≤ + 6βA,j + 8LZ η Eχm ζZ,j + + 2L2Z η 2 E 2 G2A,j . (180) R r=1 K ηER m The expectation is over the learning and unlearning randomness, conditional on the fixed seed pool and request sequence. Earlier deletion requests do not add a separate error term; their effect enters only through the retained objective and its constants. Proof of Corollary 9. Condition on the seed pool and the fixed request sequence. Exact unlearning for one request, together with the sequential-request corollaries, says that after request j the returned state has exactly the law of the corresponding learner on D(j+1) at the same logical point. Continuing both states with the ordinary retained-data learning transitions preserves this equality in law through round R. Theorem 6 therefore applies directly to the resulting retained-data trajectory and gives Eq. (180). If the seed pool is random, the same argument can be averaged over any event on which the retained-data assumptions and step-size condition hold. In particular, Corollary 5 applies on its spectral event whenever the retained objectives satisfy the required regularity there. An unconditional expectation additionally requires control of the complementary seed-pool event, exactly as in Eq. (160). The preceding corollary controls the gradient component visible to the fixed seed span. If that span also captures the retained full gradient, the same argument gives a full-space statement. Corollary 10 (Full-space utility after unlearning). Under the conditions of Corollary 9, suppose that, at every global checkpoint that can arise on the retained-data trajectory, 1 ∥Z ⊤ ∇f (j) (w)∥2 ≥ κZ,j ∥∇f (j) (w)∥2 − ε2cov,j (181) K for some κZ,j > 0 and εcov,j ≥ 0. Then, conditionally on the seed pool, ! # " R 2 νA,j 2(f (j) (w0 ) − fj⋆ ) 1 X 1 r−1,(j) 2 (j) 2 2 2 2 2 2 2 E∥∇f (wA )∥ ≤ + 6βA,j + 8LZ η Eχm ζZ,j + + 2LZ η E GA,j + εcov,j . R r=1 κZ,j ηER m (182) Proof of Corollary 10. Apply the displayed gradient-coverage inequality at each retained-data checkpoint and average it over the trajectory in Corollary 9. This gives Eq. (182) directly. For a random Gaussian pool, the averaging event must satisfy both the step-size condition and the retained-data coverage property. If the gradients of a retained objective lie in a fixed subspace, the Gaussian embedding result above can be applied to that subspace with the inherited step size. A guarantee that holds simultaneously for several retained objectives requires a common embedding event, or an explicit union bound over the relevant subspaces; the coverage statement for the original objective alone is not enough.

Related documents

• Efficient Exact Unlearning for Federated Zeroth-Order Optimization#1458681
• Runtime-Orchestrated Second-Order Optimization for Scalable LLM Training#194280
• Totoro$^+$: An Adaptive and Scalable Edge Federated Learning System#229472
• Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning#1161018
• Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning#1157538