Introduction
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 [26 ] . However, practical deployment remains constrained by limited memory and communication resources, with growing model sizes further amplifying these challenges. Techniques such as quantization [27 , 43 , 47 ] , sparsification [44 , 37 , 48 ] , pruning and submodel training [28 , 46 , 36 , 40 ] , and knowledge distillation [29 , 45 , 49 ] can reduce computation or communication costs. More recently, parameter-efficient and subspace-based federated fine-tuning methods have been developed to adapt large language models (LLMs) with fewer trainable parameters [30 , 35 ] . 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, zeroth-order optimization (ZOO) estimates descent directions using only function evaluations and therefore avoids backpropagation [2 ] . 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 [1 ] , 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 seed-coordinate 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 [31 ] . 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 [3 ] , 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 [33 , 3 , 41 ] . 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:
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, FedZOO-S, obtains stability from client and mini-batch 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, FedZOUL-S, therefore preserves the unaffected prefix and replays only from the first affected step. The second, FedZOO-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, FedZOUL-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.
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 high-dimensional model-update communication.
We propose FedZOO-S, a TV-stable federated zeroth-order learning algorithm whose stability arises from client and mini-batch subsampling, together with its exact-unlearning algorithm FedZOUL-S. A deletion leaves the realized trajectory unchanged when the deleted samples have not contributed to any realized local update. Otherwise, FedZOUL-S preserves the unaffected prefix and replays only the suffix starting from the first affected local step.
We further propose FedZOO-NS, which augments subsampling with Gaussian randomization, together with its corresponding exact-unlearning algorithm FedZOUL-NS. 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.
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.
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. [20 ] propose FedZO as one of the first derivative free federated ZO methods. For LLMs, Ling et al. [21 ] propose FedMeZO, which significantly reduces memory overhead and provides convergence analysis. Later, FedKSeed [1 ] and DeComFL [8 ] use scalar gradients and random seeds to synchronize perturbation randomness, achieving dimension-independent communication between edge nodes and the cloud. HiSo [22 ] 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 [23 ] , DP-ZOSO [24 ] and DP-AggZO [25 ] 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.
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 [9 , 12 , 14 , 15 , 13 ] , perturbation [16 , 17 , 19 , 39 , 38 ] , or knowledge distillation [18 , 10 ] . Related work on LLM unlearning also seeks to remove targeted knowledge while preserving useful model capabilities [11 , 42 ] . Although some approaches provide certified guarantees that bound distributional discrepancies through calibrated randomization [19 , 39 , 38 ] , 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, stability-based approaches exploit overlap between learning distributions to reuse prior computation [3 , 41 ] . 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 zeroth-order 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.
Preliminaries
Federated Zeroth-Order Optimization
Consider a federated optimization system with M M M clients, where client c ∈ [ M ] c\in[M] c ∈ [ M ] holds a finite local dataset D c = { x c , 1 , … , x c , n c } \mathcal D_c=\{x_{c,1},\ldots,x_{c,n_c}\} D c = { x c , 1 , … , x c , n c } of size n c = ∣ D c ∣ n_c=|\mathcal D_c| n c = ∣ D c ∣ . The clients collaboratively optimize a global model w ∈ R d \boldsymbol w\in\mathbb R^d w ∈ R d under the coordination of a server. We consider the uniformly weighted finite-sum objective
min w ∈ R d f ( w ) ≔ 1 M ∑ c = 1 M f c ( w ) , f c ( w ) ≔ 1 n c ∑ x ∈ D c ℓ ( w ; x ) . \begin{equation}
\min_{\boldsymbol w\in\mathbb R^d}
f(\boldsymbol w)
\coloneqq
\frac{1}{M}
\sum_{c=1}^{M}
f_c(\boldsymbol w),
\qquad
f_c(\boldsymbol w)
\coloneqq
\frac{1}{n_c}
\sum_{x\in\mathcal D_c}
\ell(\boldsymbol w;x). \tag*{(1)}
\end{equation} w ∈ R d min f ( w ) : = M 1 c = 1 ∑ M f c ( w ) , f c ( w ) : = n c 1 x ∈ D c ∑ ℓ ( w ; x ) . (1)
Training proceeds for R R R communication rounds. In each round, m m m clients participate, and each participating client performs E E 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 \boldsymbol w w , a sample x x x , and a perturbation z ∼ N ( 0 , I d ) \boldsymbol z\sim\mathcal N(\boldsymbol 0,I_d) z ∼ N ( 0 , I d ) , the two-point scalar gradient is
g ( w ; x , z ) = ℓ ( w + μ z ; x ) − ℓ ( w − μ z ; x ) 2 μ , \begin{equation}
g(\boldsymbol w;x,\boldsymbol z)
=
\frac{
\ell(\boldsymbol w+\mu\boldsymbol z;x)
-
\ell(\boldsymbol w-\mu\boldsymbol z;x)
}{
2\mu
}, \tag*{(2)}
\end{equation} g ( w ; x , z ) = 2 μ ℓ ( w + μ z ; x ) − ℓ ( w − μ z ; x ) , (2)
where μ > 0 \mu>0 μ > 0 is the perturbation scale. The corresponding zeroth-order gradient estimator is g ( w ; x , z ) z g(\boldsymbol w;x,\boldsymbol z)\boldsymbol z g ( w ; x , z ) z .
For a mini-batch B \mathcal B B of size b b b , suppose that q q q perturbations { z i , j } j = 1 q \{\boldsymbol z_{i,j}\}_{j=1}^{q} { z i , j } j = 1 q are used for each x i ∈ B x_i\in\mathcal B x i ∈ B . One local step is the mini-batch averaged zeroth-order update
w + = w − η b q ∑ x i ∈ B ∑ j = 1 q g ( w ; x i , z i , j ) z i , j , \begin{equation}
\boldsymbol w^{+}
=
\boldsymbol w
-
\frac{\eta}{bq}
\sum_{x_i\in\mathcal B}
\sum_{j=1}^{q}
g(\boldsymbol w;x_i,\boldsymbol z_{i,j})
\boldsymbol z_{i,j}, \tag*{(3)}
\end{equation} w + = w − b q η x i ∈ B ∑ j = 1 ∑ q g ( w ; x i , z i , j ) z i , j , (3)
where all b q bq b q scalar gradients are evaluated at the same pre-update model w \boldsymbol w w .
Following the seed-based representation of FedKSeed [1 ] , 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 K K seeds can therefore represent zeroth-order updates through their scalar coefficients in seed-coordinate space, avoiding the transmission and storage of d d d -dimensional update vectors.
Federated Unlearning
Let D = { D 1 , … , D M } \mathcal D
=
\{\mathcal D_1,\ldots,\mathcal D_M\} D = { D 1 , … , D M } denote the federated dataset. A randomized federated learning algorithm O \mathcal O O produces a model output together with auxiliary state maintained for subsequent unlearning:
( W , S ) ∼ O ( D ) . \begin{equation}
(\boldsymbol W,\boldsymbol S)
\sim
\mathcal O(\mathcal D). \tag*{(4)}
\end{equation} ( W , S ) ∼ O ( D ) . (4)
Here, W \boldsymbol W W denotes the model output and S \boldsymbol S S collects the internal state saved by the learning procedure. The randomness of O \mathcal O O may include client participation, data sampling, zeroth-order perturbations, and other algorithmic randomness. We use O o u t ( D ) \mathcal O_{\mathrm{out}}(\mathcal D) O out ( D ) to denote the marginal distribution of the model output W \boldsymbol W W .
An unlearning request specifies samples to be removed from one or more clients. Let C u l \mathcal C_{ul} C u l be the set of affected clients and D c , u l ⊆ D c \mathcal D_{c,ul}\subseteq\mathcal D_c D c , u l ⊆ D c the samples requested for deletion from client c ∈ C u l c\in\mathcal C_{ul} c ∈ C u l . The retained federated dataset is
D − = { D 1 − , … , D M − } , D c − = { D c ∖ D c , u l , c ∈ C u l , D c , c ∉ C u l . \mathcal D^{-}
=
\{\mathcal D_1^{-},\ldots,\mathcal D_M^{-}\},
\qquad
\mathcal D_c^{-}
=
\begin{cases}
\mathcal D_c\setminus\mathcal D_{c,ul},
& c\in\mathcal C_{ul},\\
\mathcal D_c,
& c\notin\mathcal C_{ul}.
\end{cases} D − = { D 1 − , … , D M − } , D c − = { D c ∖ D c , u l , D c , c ∈ C u l , c ∈ / C u l .
We consider valid deletion requests for which every retained local dataset remains large enough for the prescribed mini-batch sampling, i.e., ∣ D c − ∣ ≥ b |\mathcal D_c^{-}|\ge b ∣ D c − ∣ ≥ b for all affected clients.
The request may arrive during training. We denote by ( R u l , t u l ) (R_{ul},t_{ul}) ( R u l , t u l ) the local training position immediately preceding the request; that is, the request arrives immediately after local step t u l t_{ul} t u l of round R u l R_{ul} R u l . Given the current model and saved state, an unlearning algorithm U \mathcal U U updates them according to the deletion request:
( W u l , S u l ) = U ( W , S , { D c , u l } c ∈ C u l ) . (\boldsymbol W_{ul},\boldsymbol S_{ul})
=
\mathcal U
\left(
\boldsymbol W,
\boldsymbol S,
\{\mathcal D_{c,ul}\}_{c\in\mathcal C_{ul}}
\right). ( W u l , S u l ) = U ( W , S , { D c , u l } c ∈ C u l ) .
Definition 1 (Exact Federated Unlearning). A federated unlearning algorithm U \mathcal U U is exact with respect to a randomized learning algorithm O \mathcal O O if, for every federated dataset D \mathcal D D and every valid deletion request,
U ( O ( D ) , { D c , u l } c ∈ C u l ) = d O ( D − ) , \begin{equation}
\mathcal U
\left(
\mathcal O(\mathcal D),
\{\mathcal D_{c,ul}\}_{c\in\mathcal C_{ul}}
\right)
\overset{d}{=}
\mathcal O(\mathcal D^{-}), \tag*{(5)}
\end{equation} U ( O ( D ) , { D c , u l } c ∈ C u l ) = d O ( D − ) , (5) where = d \overset{d}{=} = d 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.
Total Variation Stability
For two probability measures P P P and Q Q Q on the same measurable space, their total variation (TV) distance is
TV ( P , Q ) = sup A ∣ P ( A ) − Q ( A ) ∣ , \begin{equation}
\operatorname{TV}(P,Q)
=
\sup_{A}
|P(A)-Q(A)|, \tag*{(6)}
\end{equation} TV ( P , Q ) = A sup ∣ P ( A ) − Q ( A ) ∣ , (6)
where the supremum is over measurable events A A A . When P P P and Q Q Q admit densities p p p and q q q with respect to a common reference measure,
TV ( P , Q ) = 1 2 ∥ p − q ∥ 1 . \operatorname{TV}(P,Q)
=
\frac{1}{2}\|p-q\|_1. TV ( P , Q ) = 2 1 ∥ p − q ∥ 1 .
For two federated datasets D = { D c } c = 1 M \mathcal D=\{\mathcal D_c\}_{c=1}^{M} D = { D c } c = 1 M and D ′ = { D c ′ } c = 1 M \mathcal D'=\{\mathcal D'_c\}_{c=1}^{M} D ′ = { D c ′ } c = 1 M , define
Δ ( D , D ′ ) = ∑ c = 1 M ∣ D c △ D c ′ ∣ . \Delta(\mathcal D,\mathcal D')
=
\sum_{c=1}^{M}
|\mathcal D_c\triangle\mathcal D'_c|. Δ ( D , D ′ ) = c = 1 ∑ M ∣ D c △ D c ′ ∣.
We call them sample-level adjacent, denoted by D ∼ D ′ \mathcal D\sim\mathcal D' D ∼ D ′ , if Δ ( D , D ′ ) = 1 \Delta(\mathcal D,\mathcal D')=1 Δ ( 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 (ρ \rho ρ -Sample-Level TV Stability). A randomized federated learning algorithm O \mathcal O O is ρ \rho ρ -sample-level TV stable if
sup D ∼ D ′ TV ( O o u t ( D ) , O o u t ( D ′ ) ) ≤ ρ , \begin{equation}
\sup_{\mathcal D\sim\mathcal D'}
\operatorname{TV}
\left(
\mathcal O_{\mathrm{out}}(\mathcal D),
\mathcal O_{\mathrm{out}}(\mathcal D')
\right)
\le \rho, \tag*{(7)}
\end{equation} D ∼ D ′ sup TV ( O out ( D ) , O out ( D ′ ) ) ≤ ρ , (7) where ρ ∈ [ 0 , 1 ] \rho\in[0,1] ρ ∈ [ 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 ρ \rho ρ implies greater overlap between the two output distributions, which can be exploited by coupling-based unlearning to reuse computations from the original training trajectory.
Our Method
We develop two pairs of federated learning and exact-unlearning algorithms. Both pairs build on a common seed-encoded 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, FedZOO-S and FedZOUL-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, FedZOO-NS and FedZOUL-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.
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 K K distinct perturbation seeds
S = { s 1 , … , s K } , \mathbb{S}=\{s_1,\ldots,s_K\}, S = { s 1 , … , s K } ,
which is shared by the server and all clients and remains fixed throughout training. With a fixed pseudorandom number generator, each seed s k s_k s k deterministically generates a Gaussian perturbation z k = P e r t u r b ( s k ) ∈ R d \boldsymbol z_k=\mathsf{Perturb}(s_k)\in\mathbb{R}^d z k = Perturb ( s k ) ∈ R d , where z k ∼ N ( 0 , I d ) \boldsymbol z_k\sim\mathcal{N}(\boldsymbol 0,I_d) z k ∼ N ( 0 , I d ) . For model w \boldsymbol w w , sample x x x , and seed s k s_k s k , define the two-point zeroth-order scalar gradient as
g ( w ; x , s k ) = ℓ ( w + μ z k ; x ) − ℓ ( w − μ z k ; x ) 2 μ . g(\boldsymbol w;x,s_k) = \frac{ \ell(\boldsymbol w+\mu\boldsymbol z_k;x) - \ell(\boldsymbol w-\mu\boldsymbol z_k;x) }{2\mu}. g ( w ; x , s k ) = 2 μ ℓ ( w + μ z k ; x ) − ℓ ( w − μ z k ; x ) .
The corresponding zeroth-order gradient estimator is g ( w ; x , s k ) z k g(\boldsymbol w;x,s_k)\boldsymbol z_k g ( w ; x , s k ) z k . Hence, once S \mathbb S S is shared, an update along z k \boldsymbol z_k z k is completely specified by its seed index and scalar coefficient, rather than by a d d 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 a r = ( a 1 r , … , a K r ) ∈ R K \boldsymbol a^r=(a_1^r,\ldots,a_K^r)\in\mathbb{R}^K a r = ( a 1 r , … , a K r ) ∈ R K denote the global scalar-gradient accumulator after round r r r , where a k r a_k^r a k r is the cumulative coefficient associated with z k \boldsymbol z_k z k . The corresponding global model is reconstructed as
R e c ( a r ) = w 0 − η ∑ k = 1 K a k r z k , \begin{equation}
\mathsf{Rec}(\boldsymbol a^r) = \boldsymbol w^0-\eta\sum_{k=1}^{K}a_k^r\boldsymbol z_k, \tag*{(8)}
\end{equation} Rec ( a r ) = w 0 − η k = 1 ∑ K a k r z k , (8)
and we write w r = R e c ( a r ) \boldsymbol w^r=\mathsf{Rec}(\boldsymbol a^r) w r = Rec ( a r ) . Thus, the persistent training state is represented by the K K K -dimensional accumulator a r \boldsymbol a^r a r , while the full model is reconstructed only when needed. At the beginning of round r r r , client c c c reconstructs w r − 1 \boldsymbol w^{r-1} w r − 1 from a r − 1 \boldsymbol a^{r-1} a r − 1 and initializes a c r , 0 = 0 K \boldsymbol a_c^{r,0}=\boldsymbol 0_K a c r , 0 = 0 K . The local accumulator records only the updates generated by client c c c during the current round. Each local step consists of one mini-batch averaged zeroth-order update. Specifically, let Δ a c r , t ∈ R K \Delta\boldsymbol a_c^{r,t}\in\mathbb{R}^K Δ a c r , t ∈ R K denote the seed-coordinate increment computed at local step t t t from w c r , t − 1 \boldsymbol w_c^{r,t-1} w c r , t − 1 . All scalar gradients in this step are evaluated at the same model w c r , t − 1 \boldsymbol w_c^{r,t-1} w c r , t − 1 , accumulated into Δ a c r , t \Delta\boldsymbol a_c^{r,t} Δ a c r , t , and applied jointly:
a c r , t = a c r , t − 1 + Δ a c r , t , w c r , t = w c r , t − 1 − η ∑ k = 1 K Δ a c , k r , t z k . \begin{align}
\boldsymbol a_c^{r,t} &= \boldsymbol a_c^{r,t-1} + \Delta\boldsymbol a_c^{r,t}, \tag*{(9)} \\ \boldsymbol w_c^{r,t} &= \boldsymbol w_c^{r,t-1} - \eta \sum_{k=1}^{K} \Delta a_{c,k}^{r,t}\boldsymbol z_k. \tag*{(10)}
\end{align} a c r , t w c r , t = a c r , t − 1 + Δ a c r , t , = w c r , t − 1 − η k = 1 ∑ K Δ a c , k r , t z k . (9) (10)
Equivalently,
w c r , t = w r − 1 − η ∑ k = 1 K a c , k r , t z k . \boldsymbol w_c^{r,t} = \boldsymbol w^{r-1} - \eta\sum_{k=1}^{K} a_{c,k}^{r,t}\boldsymbol z_k. w c r , t = w r − 1 − η k = 1 ∑ K a c , k r , t z k .
After local training, the server aggregates the final local accumulators of the participating clients and adds the resulting increment to a r − 1 \boldsymbol a^{r-1} a r − 1 , thereby obtaining a r \boldsymbol a^{r} a r . 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.
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, FedZOO-S.
At round r r r , the server uniformly samples C r ⊆ [ M ] \mathcal C^r\subseteq[M] C r ⊆ [ M ] with ∣ C r ∣ = m |\mathcal C^r|=m ∣ C r ∣ = m and sends the current global accumulator a r − 1 \boldsymbol a^{r-1} a r − 1 to the participating clients. Each c ∈ C r c\in\mathcal C^r c ∈ C r initializes
w c r , 0 = R e c ( a r − 1 ) , a c r , 0 = 0 K , \boldsymbol w_c^{r,0}
=
\mathsf{Rec}(\boldsymbol a^{r-1}),
\qquad
\boldsymbol a_c^{r,0}
=
\boldsymbol 0_K, w c r , 0 = Rec ( a r − 1 ) , a c r , 0 = 0 K ,
and performs E E E local steps.
At local step t t t , client c c c samples a mini-batch B c r , t ⊆ D c \mathcal B_c^{r,t}\subseteq\mathcal D_c B c r , t ⊆ D c of size b b b uniformly without replacement. For each x i ∈ B c r , t x_i\in\mathcal B_c^{r,t} x i ∈ B c r , t , it further samples q q q distinct seeds
S c , i r , t = { s i , 1 , … , s i , q } ⊆ S \mathbb S_{c,i}^{r,t}
=
\{s_{i,1},\ldots,s_{i,q}\}
\subseteq\mathbb S S c , i r , t = { s i , 1 , … , s i , q } ⊆ S
uniformly without replacement. Let z i , j = P e r t u r b ( s i , j ) \boldsymbol z_{i,j}=\mathsf{Perturb}(s_{i,j}) z i , j = Perturb ( s i , j ) . All scalar gradients within the local step are evaluated at the same pre-update model:
g i , j r , t = ℓ ( w c r , t − 1 + μ z i , j ; x i ) − ℓ ( w c r , t − 1 − μ z i , j ; x i ) 2 μ . \begin{equation}
g_{i,j}^{r,t}
=
\frac{
\ell(\boldsymbol w_c^{r,t-1}+\mu\boldsymbol z_{i,j};x_i)
-
\ell(\boldsymbol w_c^{r,t-1}-\mu\boldsymbol z_{i,j};x_i)
}{
2\mu
}. \tag*{(11)}
\end{equation} g i , j r , t = 2 μ ℓ ( w c r , t − 1 + μ z i , j ; x i ) − ℓ ( w c r , t − 1 − μ z i , j ; x i ) . (11)
The b q bq b q scalar gradients jointly form one mini-batch averaged zeroth-order update. For each s k ∈ S s_k\in\mathbb S s k ∈ S , define
Δ a c , k r , t = 1 b q ∑ x i ∈ B c r , t , j ∈ [ q ] : s i , j = s k g i , j r , t , \begin{equation}
\Delta a_{c,k}^{r,t}
=
\frac{1}{bq}
\sum_{\substack{
x_i\in\mathcal B_c^{r,t},\,j\in[q]:\\
s_{i,j}=s_k
}}
g_{i,j}^{r,t}, \tag*{(12)}
\end{equation} Δ a c , k r , t = b q 1 x i ∈ B c r , t , j ∈ [ q ] : s i , j = s k ∑ g i , j r , t , (12)
where an empty sum is zero. The client then applies
a c r , t = a c r , t − 1 + Δ a c r , t , w c r , t = w c r , t − 1 − η ∑ k = 1 K Δ a c , k r , t z k . \begin{align}
\boldsymbol a_c^{r,t}
&=
\boldsymbol a_c^{r,t-1}
+
\Delta\boldsymbol a_c^{r,t}, \tag*{(13)}
\\
\boldsymbol w_c^{r,t}
&=
\boldsymbol w_c^{r,t-1}
-
\eta
\sum_{k=1}^{K}
\Delta a_{c,k}^{r,t}\boldsymbol z_k. \tag*{(14)}
\end{align} a c r , t w c r , t = a c r , t − 1 + Δ a c r , t , = w c r , t − 1 − η k = 1 ∑ K Δ a c , k r , t z k . (13) (14)
For subsequent unlearning, the client records B c r , t \mathcal B_c^{r,t} B c r , t , { S c , i r , t } x i ∈ B c r , t \{\mathbb S_{c,i}^{r,t}\}_{x_i\in\mathcal B_c^{r,t}} { S c , i r , t } x i ∈ B c r , t , and a c r , t \boldsymbol a_c^{r,t} a c r , t .
After the local steps, the server updates
a r = a r − 1 + 1 m ∑ c ∈ C r a c r , E , \begin{equation}
\boldsymbol a^r
=
\boldsymbol a^{r-1}
+
\frac{1}{m}
\sum_{c\in\mathcal C^r}
\boldsymbol a_c^{r,E}, \tag*{(15)}
\end{equation} a r = a r − 1 + m 1 c ∈ C r ∑ a c r , E , (15)
and records C r \mathcal C^r C r and a r \boldsymbol a^r a r . Algorithm algo:FedZOOS summarizes FedZOO-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 C u l \mathcal C_{ul} C u l be the clients involved in an unlearning request, and let D c , u l ⊆ D c \mathcal D_{c,ul}\subseteq\mathcal D_c D c , u l ⊆ D c contain the samples to be deleted from client c c c . Suppose the request arrives immediately after local step ( R u l , t u l ) (R_{ul},t_{ul}) ( R u l , t u l ) . For later use, define the next training position as
N e x t ( r , t ) = { ( r , t + 1 ) , t < E , ( r + 1 , 1 ) , t = E . \mathsf{Next}(r,t)
=
\begin{cases}
(r,t+1), & t<E,\\
(r+1,1), & t=E.
\end{cases} Next ( r , t ) = { ( r , t + 1 ) , ( r + 1 , 1 ) , t < E , t = E .
Using the client-participation sets and mini-batches recorded during FedZOO-S, FedZOUL-S searches chronologically over the realized prefix up to ( R u l , t u l ) (R_{ul},t_{ul}) ( R u l , t u l ) for the earliest step ( r ⋆ , t ⋆ ) (r^\star,t^\star) ( r ⋆ , t ⋆ ) satisfying
B c r ⋆ , t ⋆ ∩ D c , u l ≠ ∅ \begin{equation}
\mathcal B_c^{r^\star,t^\star}
\cap
\mathcal D_{c,ul}
\neq
\varnothing \tag*{(16)}
\end{equation} B c r ⋆ , t ⋆ ∩ D c , u l = ∅ (16)
for some c ∈ C u l ∩ C r ⋆ c\in\mathcal C_{ul}\cap\mathcal C^{r^\star} c ∈ C u l ∩ 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 N e x t ( R u l , t u l ) \mathsf{Next}(R_{ul},t_{ul}) Next ( R u l , t u l ) using the current state, without replaying any previous step.
Otherwise, the algorithm preserves the entire trajectory before ( r ⋆ , t ⋆ ) (r^\star,t^\star) ( r ⋆ , t ⋆ ) and restores the optimization state immediately preceding this step. Specifically, it loads a r ⋆ − 1 \boldsymbol a^{r^\star-1} a r ⋆ − 1 and, for each c ∈ C r ⋆ c\in\mathcal C^{r^\star} c ∈ C r ⋆ , restores a c r ⋆ , t ⋆ − 1 \boldsymbol a_c^{r^\star,t^\star-1} a c r ⋆ , t ⋆ − 1 and reconstructs
w c r ⋆ , t ⋆ − 1 = R e c ( a r ⋆ − 1 ) − η ∑ k = 1 K a c , k r ⋆ , t ⋆ − 1 z k . \begin{equation}
\boldsymbol w_c^{r^\star,t^\star-1}
=
\mathsf{Rec}(\boldsymbol a^{r^\star-1})
-
\eta
\sum_{k=1}^{K}
a_{c,k}^{r^\star,t^\star-1}\boldsymbol z_k. \tag*{(17)}
\end{equation} w c r ⋆ , t ⋆ − 1 = Rec ( a r ⋆ − 1 ) − η k = 1 ∑ K a c , k r ⋆ , t ⋆ − 1 z k . (17)
Training then resumes from ( r ⋆ , t ⋆ ) (r^\star,t^\star) ( r ⋆ , t ⋆ ) on the retained datasets using the same FedZOO-S procedure. All newly generated states replace their original counterparts.
The preserved prefix contains no update involving a deleted sample. The coupling analysis in § 9.1 shows that the two branches of FedZOUL-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, the resulting model and saved state have the same distribution as a FedZOO-S run on the retained datasets. Algorithm algo:FedZOULS summarizes the procedure. We state the algorithm for set-valued deletion requests; the theoretical analysis considers a single deletion, with multiple requests handled sequentially.
The limitation of FedZOUL-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.
Noise-Stable Learning and Unlearning
Learning: FedZOO-NS. FedZOO-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 FedZOO-NS.
Client, mini-batch, and perturbation-seed sampling follow FedZOO-S. At local step ( r , t ) (r,t) ( r , t ) , let B c r , t \mathcal B_c^{r,t} B c r , t be the sampled mini-batch and S c , i r , t \mathbb S_{c,i}^{r,t} S c , i r , t the q q q perturbation seeds sampled for x i ∈ B c r , t x_i\in\mathcal B_c^{r,t} x i ∈ B c r , t . All scalar gradients are evaluated at the same pre-update model w c r , t − 1 \boldsymbol w_c^{r,t-1} w c r , t − 1 :
g i , j r , t = ℓ ( w c r , t − 1 + μ z i , j ; x i ) − ℓ ( w c r , t − 1 − μ z i , j ; x i ) 2 μ , \begin{equation}
g_{i,j}^{r,t}
=
\frac{
\ell(\boldsymbol w_c^{r,t-1}+\mu\boldsymbol z_{i,j};x_i)
-
\ell(\boldsymbol w_c^{r,t-1}-\mu\boldsymbol z_{i,j};x_i)
}{
2\mu
}, \tag*{(18)}
\end{equation} g i , j r , t = 2 μ ℓ ( w c r , t − 1 + μ z i , j ; x i ) − ℓ ( w c r , t − 1 − μ z i , j ; x i ) , (18)
where z i , j = P e r t u r b ( s i , j ) \boldsymbol z_{i,j}=\mathsf{Perturb}(s_{i,j}) z i , j = Perturb ( s i , j ) . We clip each scalar gradient at level C C C and normalize it according to the mini-batch averaged update:
h i , j r , t = 1 b q clip C ( g i , j r , t ) . \begin{equation}
h_{i,j}^{r,t}
=
\frac{1}{bq}
\operatorname{clip}_C(g_{i,j}^{r,t}). \tag*{(19)}
\end{equation} h i , j r , t = b q 1 clip C ( g i , j r , t ) . (19)
Fix a deterministic ordering of the b q bq b q sample–seed pairs and collect their coefficients into h c r , t ∈ R b q \boldsymbol h_c^{r,t}\in\mathbb R^{bq} h c r , t ∈ R b q . Client c c c independently draws
ξ c r , t ∼ N ( 0 , σ ρ 2 I b q ) \boldsymbol\xi_c^{r,t}
\sim
\mathcal N(\boldsymbol0,\sigma_\rho^2 I_{bq}) ξ c r , t ∼ N ( 0 , σ ρ 2 I b q )
and forms
h ~ c r , t = h c r , t + ξ c r , t . \begin{equation}
\widetilde{\boldsymbol h}_c^{r,t}
=
\boldsymbol h_c^{r,t}
+
\boldsymbol\xi_c^{r,t}. \tag*{(20)}
\end{equation} h c r , t = h c r , t + ξ c r , t . (20)
The Gaussian noise is independent of the client, mini-batch, and perturbation-seed sampling.
The noisy coefficient vector is mapped to the seed-coordinate increment Δ a ~ c r , t ∈ R K \Delta\widetilde{\boldsymbol a}_c^{r,t}\in\mathbb R^K Δ a c r , t ∈ R K . For each seed s k ∈ S s_k\in\mathbb S s k ∈ S , the increment is Δ a ~ c , k r , t = ∑ x i ∈ B c r , t , j ∈ [ q ] : s i , j = s k h ~ i , j r , t \Delta\widetilde a_{c,k}^{r,t}
=
\sum_{\substack{
x_i\in\mathcal B_c^{r,t},\,j\in[q]:\\
s_{i,j}=s_k
}}
\widetilde h_{i,j}^{r,t} Δ a c , k r , t = ∑ x i ∈ B c r , t , j ∈ [ q ] : s i , j = s k h i , j r , t , where h ~ i , j r , t \widetilde h_{i,j}^{r,t} h i , j r , t denotes the component of h ~ c r , t \widetilde{\boldsymbol h}_c^{r,t} h c r , t corresponding to the sampled pair ( x i , s i , j ) (x_i,s_{i,j}) ( x i , s i , j ) . The sum includes all sampled pairs sharing s k s_k s k and is zero if no such pair is selected. The client then updates
a c r , t = a c r , t − 1 + Δ a ~ c r , t , w c r , t = w c r , t − 1 − η ∑ k = 1 K Δ a ~ c , k r , t z k . \begin{align}
\boldsymbol a_c^{r,t}
&=
\boldsymbol a_c^{r,t-1}
+
\Delta\widetilde{\boldsymbol a}_c^{r,t}, \tag*{(21)}
\\
\boldsymbol w_c^{r,t}
&=
\boldsymbol w_c^{r,t-1}
-
\eta
\sum_{k=1}^{K}
\Delta\widetilde a_{c,k}^{r,t}\boldsymbol z_k. \tag*{(22)}
\end{align} a c r , t w c r , t = a c r , t − 1 + Δ a c r , t , = w c r , t − 1 − η k = 1 ∑ K Δ a c , k r , t z k . (21) (22)
After E E E local steps, the server performs the same uniform aggregation as in FedZOO-S:
a r = a r − 1 + 1 m ∑ c ∈ C r a c r , E . \begin{equation}
\boldsymbol a^r
=
\boldsymbol a^{r-1}
+
\frac{1}{m}
\sum_{c\in\mathcal C^r}
\boldsymbol a_c^{r,E}. \tag*{(23)}
\end{equation} a r = a r − 1 + m 1 c ∈ C r ∑ a c r , E . (23)
For subsequent unlearning, each client records B c r , t \mathcal B_c^{r,t} B c r , t , { S c , i r , t } x i ∈ B c r , t \{\mathbb S_{c,i}^{r,t}\}_{x_i\in\mathcal B_c^{r,t}} { S c , i r , t } x i ∈ B c r , t , h ~ c r , t \widetilde{\boldsymbol h}_c^{r,t} h c r , t , and a c r , t \boldsymbol a_c^{r,t} a c r , t . The clean vector h c r , t \boldsymbol h_c^{r,t} h c r , t need not be stored, since it can be recomputed from the saved pre-update state, mini-batch, and perturbation seeds. Algorithm algo:FedZOONS summarizes FedZOO-NS.
Exact unlearning: FedZOUL-NS. Consider a deletion request { D c , u l } c ∈ C u l \{\mathcal D_{c,ul}\}_{c\in\mathcal C_{ul}} { D c , u l } c ∈ C u l arriving immediately after local step ( R u l , t u l ) (R_{ul},t_{ul}) ( R u l , t u l ) . FedZOUL-NS scans the realized prefix up to the request in chronological order. For an affected client c ∈ C u l ∩ C r c\in\mathcal C_{ul}\cap\mathcal C^r c ∈ C u l ∩ C r , define
B c , u l r , t = B c r , t ∩ D c , u l . \mathcal B_{c,ul}^{r,t}
=
\mathcal B_c^{r,t}\cap\mathcal D_{c,ul}. B c , u l r , t = B c r , t ∩ D c , u l .
If B c , u l r , t = ∅ \mathcal B_{c,ul}^{r,t}=\varnothing B c , u l r , t = ∅ , the recorded local update is unaffected and is preserved. Otherwise, the algorithm couples the recorded mini-batch to a mini-batch distributed as a uniform sample from the retained local dataset. It removes B c , u l r , t \mathcal B_{c,ul}^{r,t} B c , u l r , t 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 ( B c r , t ) ′ (\mathcal B_c^{r,t})' ( B c r , 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 ( h c r , t ) ′ (\boldsymbol h_c^{r,t})' ( h c r , t ) ′ . Conditioned on the pre-update state and sampling realizations, the original and retained-data randomized updates follow
P = N ( h c r , t , σ ρ 2 I b q ) , Q = N ( ( h c r , t ) ′ , σ ρ 2 I b q ) . P
=
\mathcal N
\left(
\boldsymbol h_c^{r,t},
\sigma_\rho^2 I_{bq}
\right),
\qquad
Q
=
\mathcal N
\left(
(\boldsymbol h_c^{r,t})',
\sigma_\rho^2 I_{bq}
\right). P = N ( h c r , t , σ ρ 2 I b q ) , Q = N ( ( h c r , t ) ′ , σ ρ 2 I b q ) .
Let p p p and q q q denote their densities. For the recorded realization h ~ c r , t \widetilde{\boldsymbol h}_c^{r,t} h c r , t , the rejection step accepts with probability
α c r , t = min { 1 , q ( h ~ c r , t ) p ( h ~ c r , t ) } . \begin{equation}
\alpha_c^{r,t}
=
\min\left\{
1,\,
\frac{
q(\widetilde{\boldsymbol h}_c^{r,t})
}{
p(\widetilde{\boldsymbol h}_c^{r,t})
}
\right\}. \tag*{(24)}
\end{equation} α c r , t = min { 1 , p ( h c r , t ) q ( h c r , t ) } . (24)
Equivalently,
α c r , t = min { 1 , exp ( ∥ h ~ c r , t − h c r , t ∥ 2 2 − ∥ h ~ c r , t − ( h c r , t ) ′ ∥ 2 2 2 σ ρ 2 ) } . \begin{equation}
\alpha_c^{r,t}
=
\min\left\{
1,\,
\exp\!\left(
\frac{
\|\widetilde{\boldsymbol h}_c^{r,t}
-\boldsymbol h_c^{r,t}\|_2^2
-
\|\widetilde{\boldsymbol h}_c^{r,t}
-(\boldsymbol h_c^{r,t})'\|_2^2
}{
2\sigma_\rho^2
}
\right)
\right\}. \tag*{(25)}
\end{equation} α c r , t = min { 1 , exp ( 2 σ ρ 2 ∥ h c r , t − h c r , t ∥ 2 2 − ∥ h c r , t − ( h c r , t ) ′ ∥ 2 2 ) } . (25)
If the test accepts, the recorded noisy coefficient vector is reused:
( h ~ c r , t ) ′ = h ~ c r , t . (\widetilde{\boldsymbol h}_c^{r,t})'
=
\widetilde{\boldsymbol h}_c^{r,t}. ( h c r , t ) ′ = h c r , t .
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
d c r , t = ( h c r , t ) ′ − h c r , t , m c r , t = h c r , t + ( h c r , t ) ′ 2 . \boldsymbol d_c^{r,t}
=
(\boldsymbol h_c^{r,t})'
-
\boldsymbol h_c^{r,t},
\qquad
\boldsymbol m_c^{r,t}
=
\frac{
\boldsymbol h_c^{r,t}
+
(\boldsymbol h_c^{r,t})'
}{2}. d c r , t = ( h c r , t ) ′ − h c r , t , m c r , t = 2 h c r , t + ( h c r , t ) ′ .
For d c r , t ≠ 0 \boldsymbol d_c^{r,t}\neq\boldsymbol0 d c r , t = 0 , define
e c r , t = d c r , t ∥ d c r , t ∥ 2 . \boldsymbol e_c^{r,t}
=
\frac{
\boldsymbol d_c^{r,t}
}{
\|\boldsymbol d_c^{r,t}\|_2
}. e c r , t = ∥ d c r , t ∥ 2 d c r , t .
The reflected coefficient vector is
( h ~ c r , t ) ′ = h ~ c r , t − 2 ⟨ h ~ c r , t − m c r , t , e c r , t ⟩ e c r , t . \begin{equation}
(\widetilde{\boldsymbol h}_c^{r,t})'
=
\widetilde{\boldsymbol h}_c^{r,t}
-
2
\left\langle
\widetilde{\boldsymbol h}_c^{r,t}
-
\boldsymbol m_c^{r,t},
\boldsymbol e_c^{r,t}
\right\rangle
\boldsymbol e_c^{r,t}. \tag*{(26)}
\end{equation} ( h c r , t ) ′ = h c r , t − 2 ⟨ h c r , t − m c r , t , e c r , t ⟩ e c r , t . (26)
If the two clean coefficient vectors coincide, then P = Q P=Q P = Q and the step is accepted directly.
The reflected vector is mapped to the fixed seed-coordinate space to obtain Δ a ~ c r , t \Delta\widetilde{\boldsymbol a}_c^{r,t} Δ a c r , t and is applied to the state immediately preceding ( r , t ) (r,t) ( r , t ) :
a c r , t = a c r , t − 1 + Δ a ~ c r , t , w c r , t = w c r , t − 1 − η ∑ k = 1 K Δ a ~ c , k r , t z k . \begin{align}
\boldsymbol a_c^{r,t}
&=
\boldsymbol a_c^{r,t-1}
+
\Delta\widetilde{\boldsymbol a}_c^{r,t}, \tag*{(27)}
\\
\boldsymbol w_c^{r,t}
&=
\boldsymbol w_c^{r,t-1}
-
\eta
\sum_{k=1}^{K}
\Delta\widetilde a_{c,k}^{r,t}\boldsymbol z_k. \tag*{(28)}
\end{align} a c r , t w c r , t = a c r , t − 1 + Δ a c r , t , = w c r , t − 1 − η k = 1 ∑ K Δ a c , k r , t z k . (27) (28)
The saved state of this local step is then replaced by
( ( B c r , t ) ′ , { S c , i r , t } x i ∈ ( B c r , t ) ′ , ( h ~ c r , t ) ′ , a c r , t ) , \left(
(\mathcal B_c^{r,t})',
\{\mathbb S_{c,i}^{r,t}\}_{x_i\in(\mathcal B_c^{r,t})'},
(\widetilde{\boldsymbol h}_c^{r,t})',
\boldsymbol a_c^{r,t}
\right), ( ( B c r , t ) ′ , { S c , i r , t } x i ∈ ( B c r , t ) ′ , ( h c r , t ) ′ , a c r , t ) ,
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 t=E t = E , the corrected local endpoint first replaces its original counterpart and the server recomputes
a r = a r − 1 + 1 m ∑ c ∈ C r a c r , E \boldsymbol a^r
=
\boldsymbol a^{r-1}
+
\frac{1}{m}
\sum_{c\in\mathcal C^r}
\boldsymbol a_c^{r,E} a r = a r − 1 + m 1 c ∈ C r ∑ a c r , E
before training proceeds from N e x t ( r , E ) = ( r + 1 , 1 ) \mathsf{Next}(r,E)=(r+1,1) 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 N e x t ( R u l , t u l ) \mathsf{Next}(R_{ul},t_{ul}) Next ( R u l , t u l ) . If a rejection occurs at ( r ⋆ , t ⋆ ) (r^\star,t^\star) ( r ⋆ , t ⋆ ) , training instead continues from N e x t ( r ⋆ , t ⋆ ) \mathsf{Next}(r^\star,t^\star) Next ( r ⋆ , t ⋆ ) using the corrected state. Algorithm algo:FedZOULNS summarizes the procedure.
Thus, FedZOUL-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.
\caption{\texttt{FedZOO-S}: Subsampling-Stable Federated ZOO}
\label{algo:FedZOOS}
\KwIn{$\boldsymbol w^0,R,E,K,q,b,m,\eta,\mu$.}
\KwOut{$\boldsymbol w^R$.}
Initialize fixed seed pool
$\mathbb S=\{s_1,\ldots,s_K\}$ and
$\boldsymbol a^0=\boldsymbol 0_K$\;
\For{$r=1,\ldots,R$}{
Sample $\mathcal C^r\subseteq[M]$, $|\mathcal C^r|=m$,
uniformly without replacement\;
\ForEach{$c\in\mathcal C^r$ \textbf{in parallel}}{
$\boldsymbol w_c^{r,0}\gets\mathsf{Rec}(\boldsymbol a^{r-1})$;
$\boldsymbol a_c^{r,0}\gets\boldsymbol 0_K$\;
\For{$t=1,\ldots,E$}{
Sample $\mathcal B_c^{r,t}$ and
$\{\mathbb S_{c,i}^{r,t}\}_{x_i\in\mathcal B_c^{r,t}}$\;
Compute $\Delta\boldsymbol a_c^{r,t}$
by Eqs.~\eqref{eq:fedzoos_scalar}--\eqref{eq:fedzoos_step_increment}\;
Update
$(\boldsymbol w_c^{r,t},\boldsymbol a_c^{r,t})$
by Eqs.~\eqref{eq:fedzoos_local_acc}--\eqref{eq:fedzoos_local_model}\;
$\mathsf{save}\!\left(
\mathcal B_c^{r,t},
\{\mathbb S_{c,i}^{r,t}\},
\boldsymbol a_c^{r,t}
\right)$\;
}
}
$\boldsymbol a^r
\gets
\boldsymbol a^{r-1}
+
\frac1m
\sum_{c\in\mathcal C^r}
\boldsymbol a_c^{r,E}$\;
$\mathsf{save}(\mathcal C^r,\boldsymbol a^r)$\;
}
\KwRet{$\mathsf{Rec}(\boldsymbol a^R)$}\;
\caption{\texttt{FedZOUL-S}: Exact Unlearning by Subsampling}
\label{algo:FedZOULS}
\KwIn{Deletion request
$\{\mathcal D_{c,ul}\}_{c\in\mathcal C_{ul}}$
after $(R_{ul},t_{ul})$; saved \texttt{FedZOO-S} states.}
\KwOut{Unlearned model $\boldsymbol w^R$.}
$\mathsf{affected}\gets\mathsf{false}$\;
\For{each $(r,t)\preceq(R_{ul},t_{ul})$ in chronological order}{
\ForEach{$c\in\mathcal C_{ul}\cap\mathcal C^r$ \textbf{in parallel}}{
$\mathsf{affected}_c
\gets
\mathbf 1\!\left\{
\mathcal B_c^{r,t}\cap\mathcal D_{c,ul}
\neq\varnothing
\right\}$\;
}
\If{$\bigvee_{c\in\mathcal C_{ul}\cap\mathcal C^r}
\mathsf{affected}_c$}{
$(r^\star,t^\star)\gets(r,t)$\;
$\mathsf{affected}\gets\mathsf{true}$\;
\textbf{break}\;
}
}
Remove $\mathcal D_{c,ul}$ from each affected local dataset\;
\eIf{$\mathsf{affected}$}{
Restore the saved state immediately before
$(r^\star,t^\star)$\;
Continue \texttt{FedZOO-S} from
$(r^\star,t^\star)$ on the retained datasets\;
}{
Continue \texttt{FedZOO-S} from
$\mathsf{Next}(R_{ul},t_{ul})$ using the current state\;
}
\KwRet{$\boldsymbol w^R$}\;
\caption{\texttt{FedZOO-NS}: Noise-Stable Federated ZOO}
\label{algo:FedZOONS}
\KwIn{$\boldsymbol w^0,R,E,K,q,b,m,\eta,\mu,C,\sigma_\rho$.}
\KwOut{$\boldsymbol w^R$.}
Initialize fixed seed pool
$\mathbb S=\{s_1,\ldots,s_K\}$
and $\boldsymbol a^0=\boldsymbol0_K$\;
\For{$r=1,\ldots,R$}{
Sample $\mathcal C^r\subseteq[M]$, $|\mathcal C^r|=m$,
uniformly without replacement\;
\ForEach{$c\in\mathcal C^r$ \textbf{in parallel}}{
$\boldsymbol w_c^{r,0}
\gets\mathsf{Rec}(\boldsymbol a^{r-1})$;
$\boldsymbol a_c^{r,0}\gets\boldsymbol0_K$\;
\For{$t=1,\ldots,E$}{
Sample $\mathcal B_c^{r,t}$ and
$\{\mathbb S_{c,i}^{r,t}\}_{x_i\in\mathcal B_c^{r,t}}$\;
Compute $\boldsymbol h_c^{r,t}$
by Eqs.~\eqref{eq:fedzoons_raw}--\eqref{eq:fedzoons_clean_coeff}\;
Draw
$\boldsymbol\xi_c^{r,t}
\sim\mathcal N(\boldsymbol0,\sigma_\rho^2I_{bq})$
and set
$\widetilde{\boldsymbol h}_c^{r,t}
\gets
\boldsymbol h_c^{r,t}+\boldsymbol\xi_c^{r,t}$\;
Map $\widetilde{\boldsymbol h}_c^{r,t}$ to
$\Delta\widetilde{\boldsymbol a}_c^{r,t}$\;
Update
$(\boldsymbol w_c^{r,t},\boldsymbol a_c^{r,t})$
by Eqs.~\eqref{eq:fedzoons_acc_update}--\eqref{eq:fedzoons_model_update}\;
$\mathsf{save}\!\left(
\mathcal B_c^{r,t},
\{\mathbb S_{c,i}^{r,t}\},
\widetilde{\boldsymbol h}_c^{r,t},
\boldsymbol a_c^{r,t}
\right)$\;
}
}
$\boldsymbol a^r
\gets
\boldsymbol a^{r-1}
+
\frac1m
\sum_{c\in\mathcal C^r}
\boldsymbol a_c^{r,E}$\;
$\mathsf{save}(\mathcal C^r,\boldsymbol a^r)$\;
}
\KwRet{$\mathsf{Rec}(\boldsymbol a^R)$}\;
\caption{\texttt{FedZOUL-NS}: Exact Unlearning by Rejection--Reflection}
\label{algo:FedZOULNS}
\KwIn{Deletion request
$\{\mathcal D_{c,ul}\}_{c\in\mathcal C_{ul}}$
after $(R_{ul},t_{ul})$; saved \texttt{FedZOO-NS} states.}
\KwOut{Unlearned model $\boldsymbol w^R$.}
$\mathsf{reject}\gets\mathsf{false}$\;
\For{each $(r,t)\preceq(R_{ul},t_{ul})$ in chronological order}{
\ForEach{$c\in\mathcal C_{ul}\cap\mathcal C^r$ \textbf{in parallel}}{
$\mathsf{reject}_c\gets\mathsf{false}$\;
$\mathcal B_{c,ul}^{r,t}
\gets
\mathcal B_c^{r,t}\cap\mathcal D_{c,ul}$\;
\If{$\mathcal B_{c,ul}^{r,t}\neq\varnothing$}{
Construct coupled mini-batch
$(\mathcal B_c^{r,t})'$
and its sample--seed correspondence\;
Recompute
$\boldsymbol h_c^{r,t}$ and
$(\boldsymbol h_c^{r,t})'$\;
Draw $u\sim\operatorname{Unif}(0,1)$\;
\eIf{$u\le\alpha_c^{r,t}$ in Eq.~\eqref{eq:rr_acceptance}}{
Replace the saved mini-batch and sample--seed
correspondence by the coupled realization\;
}{
Compute
$(\widetilde{\boldsymbol h}_c^{r,t})'$
by Eq.~\eqref{eq:rr_reflection}\;
Map
$(\widetilde{\boldsymbol h}_c^{r,t})'$
to
$\Delta\widetilde{\boldsymbol a}_c^{r,t}$\;
$\boldsymbol a_c^{r,t}
\gets
\boldsymbol a_c^{r,t-1}
+
\Delta\widetilde{\boldsymbol a}_c^{r,t}$\;
$\boldsymbol w_c^{r,t}
\gets
\boldsymbol w_c^{r,t-1}
-
\eta
\sum_{k=1}^{K}
\Delta\widetilde a_{c,k}^{r,t}\boldsymbol z_k$\;
$\mathsf{save}\!\left(
(\mathcal B_c^{r,t})',
\{\mathbb S_{c,i}^{r,t}\}_{x_i\in(\mathcal B_c^{r,t})'},
(\widetilde{\boldsymbol h}_c^{r,t})',
\boldsymbol a_c^{r,t}
\right)$\;
$\mathsf{reject}_c\gets\mathsf{true}$\;
}
}
}
\If{$\bigvee_{c\in\mathcal C_{ul}\cap\mathcal C^r}
\mathsf{reject}_c$}{
$(r^\star,t^\star)\gets(r,t)$;
$\mathsf{reject}\gets\mathsf{true}$\;
\textbf{break}\;
}
}
Remove $\mathcal D_{c,ul}$ from each affected local dataset\;
\eIf{$\mathsf{reject}$}{
\If{$t^\star=E$}{
Recompute $\boldsymbol a^{r^\star}$ from the corrected
local endpoints by Eq.~\eqref{eq:fedzoons_server}\;
}
Continue \texttt{FedZOO-NS} from
$\mathsf{Next}(r^\star,t^\star)$ using the corrected state\;
}{
Continue \texttt{FedZOO-NS} from
$\mathsf{Next}(R_{ul},t_{ul})$ using the current state\;
}
\KwRet{$\boldsymbol w^R$}\;
Theoretical Analysis
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 § 9 .
For reference, T = R E T=RE T = R E denotes the total number of local positions. For a deletion of x − x^- x − from client c − c^- c − , let n c − n_{c^-} n c − be that client’s data size immediately before deletion, and let n ‾ \underline n n be a lower bound on such local dataset sizes. If the request arrives after round R u l R_{ul} R u l and local step t u l t_{ul} t u l , then T u l = ( R u l − 1 ) E + t u l T_{ul}=(R_{ul}-1)E+t_{ul} T u l = ( R u l − 1 ) E + t u l positions have already been executed.
Stability, Exact Unlearning, and Cost
The analysis of FedZOO-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 / n c − ) (m/M)(b/n_{c^-}) ( m / M ) ( b / n c − ) , the probability of a hit within the first τ \tau τ positions is at most min { 1 , τ m b / ( M n c − ) } \min\{1,\tau mb/(Mn_{c^-})\} min { 1 , τ mb / ( M n c − )} . This gives the TV-stability result in Theorem 1 of Appendix § 9.1 ; in particular, T m b / ( M n ‾ ) ≤ ρ Tmb/(M\underline n)\le\rho T mb / ( M n ) ≤ ρ is sufficient for ρ \rho ρ -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 FedZOUL-S. Theorem 2 in Appendix § 9.1 proves exact unlearning for one deletion, and Corollary 1 in the same subsection extends the argument to a non-adaptive stream of deletions.
FedZOO-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 § 9.2 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
σ ρ = max { 2 C b q , 2 C n ‾ q ρ T m M } , \begin{equation}
\sigma_\rho
=
\max\left\{
\frac{2C}{b\sqrt q},
\frac{2C}{\underline n\sqrt q\,\rho}
\sqrt{\frac{Tm}{M}}
\right\}, \tag*{(29)}
\end{equation} σ ρ = max { b q 2 C , n q ρ 2 C M T m } , (29)
as stated in Corollary 2 of Appendix § 9.2 . The factor m / M \sqrt{m/M} m / M appears because client participation is sampled once per round and then shared across the E E E local steps.
For unlearning, this Gaussian overlap is used constructively. At an affected local step, FedZOUL-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 coupling produces an update with the correct retained-data law, and training continues from the next position. Theorem 4 in Appendix § 9.3 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 a request at T u l T_{ul} T u l ; under Eq. (29) , it is at most min { 1 , ρ T u l m / M / 2 π T } \min\{1,\rho T_{ul}\sqrt{m/M}/\sqrt{2\pi T}\} min { 1 , ρ T u l m / M / 2 π T } . This replay probability is different from the final-model TV parameter ρ \rho ρ : 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 FedZOUL-S, work is repeated only if the deleted sample was used, and replay begins at its first occurrence. For FedZOUL-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 § 9.4 give the corresponding loss-evaluation, 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.
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 ] \boldsymbol Z=[\boldsymbol z_1,\ldots,\boldsymbol z_K] Z = [ z 1 , … , z K ] and A = Z / K \boldsymbol A=\boldsymbol Z/\sqrt K A = Z / K . Every iterate can be written as w = w 0 + A u \boldsymbol w=\boldsymbol w^0+\boldsymbol A\boldsymbol u w = w 0 + A u for some u ∈ R K \boldsymbol u\in\mathbb R^K u ∈ R K . Hence the algorithm is optimizing the original objective on the affine space generated by the seed pool, with
∥ ∇ F Z ( u ) ∥ 2 = 1 K ∥ Z ⊤ ∇ f ( w ) ∥ 2 . \begin{equation}
\|\nabla F_{\boldsymbol Z}(\boldsymbol u)\|^2
=
\frac1K\|\boldsymbol Z^\top\nabla f(\boldsymbol w)\|^2. \tag*{(30)}
\end{equation} ∥∇ F Z ( u ) ∥ 2 = K 1 ∥ Z ⊤ ∇ f ( w ) ∥ 2 . (30)
The quantity on the right is therefore the gradient energy seen along the shared seed directions. Because the columns of Z \boldsymbol Z Z need not be orthogonal, it should not be interpreted as an orthogonal projection. Appendix § 9.5 gives the corresponding parameterization in detail.
The convergence proof then follows the actual seed-coordinate update produced at each local step. What matters is its conditional bias, its variance, and its second moment. For FedZOO-S, the bias comes from the two-point finite difference. For FedZOO-NS, clipping adds bias and the Gaussian perturbation adds variance. Appendix § 9.6 derives these quantities and states the required regularity conditions. Writing β A \beta_{\mathsf A} β A , ν A \nu_{\mathsf A} ν A , and G A G_{\mathsf A} G A for the corresponding uniform bounds, L Z L_{\boldsymbol Z} L Z for the smoothness constant in seed coordinates, ζ Z \zeta_{\boldsymbol Z} ζ Z for client heterogeneity, and χ m = ( M − m ) / ( m ( M − 1 ) ) \chi_m=(M-m)/(m(M-1)) χ m = ( M − m ) / ( m ( M − 1 )) for the finite-population client-sampling factor when M > 1 M>1 M > 1 (with χ m = 0 \chi_m=0 χ m = 0 for M = 1 M=1 M = 1 ), Theorem 6 in Appendix § 9.6 shows that, whenever 4 η L Z E ≤ 1 4\eta L_{\boldsymbol Z}E\le1 4 η L Z E ≤ 1 ,
1 R ∑ r = 1 R E [ 1 K ∥ Z ⊤ ∇ f ( w r − 1 ) ∥ 2 | Z ] ≤ 2 ( f ( w 0 ) − f ⋆ ) η E R + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + ν A 2 m ) + 2 L Z 2 η 2 E 2 G A 2 , \begin{align}
&\frac1R\sum_{r=1}^R
\mathbb E\left[
\frac1K\|\boldsymbol Z^\top\nabla f(\boldsymbol w^{r-1})\|^2
\,\middle|\,\boldsymbol Z
\right]
\notag\\
&\quad\le
\frac{2(f(\boldsymbol w^0)-f^\star)}{\eta ER}
+6\beta_{\mathsf A}^2
+8L_{\boldsymbol Z}\eta\left(
E\chi_m\zeta_{\boldsymbol Z}^2+\frac{\nu_{\mathsf A}^2}{m}
\right)
\notag\\
&\qquad
+2L_{\boldsymbol Z}^2\eta^2E^2G_{\mathsf A}^2, \tag*{(31)}
\end{align} R 1 r = 1 ∑ R E [ K 1 ∥ Z ⊤ ∇ f ( w r − 1 ) ∥ 2 Z ] ≤ η E R 2 ( f ( w 0 ) − f ⋆ ) + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + m ν A 2 ) + 2 L Z 2 η 2 E 2 G A 2 , (31)
where f ⋆ f^\star 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 FedZOO-NS, the noise required for stability enters the variance and second-moment terms, so the cost of making unlearning easier appears directly in the optimization bound.
For a fixed training horizon E R ER E R , the stepsize η \eta η balances the first term, which scales as 1 / ( η E R ) 1/(\eta ER) 1/ ( η E R ) , against the leading stochastic term, which grows linearly with η \eta η . Corollary 6 in Appendix § 9.6 gives the resulting balanced rate when the balancing choice also respects the stepsize condition above. Since χ m ≤ 1 / m \chi_m\le1/m χ m ≤ 1/ m , the leading stochastic term scales as O ( 1 / m E R ) \mathcal O(1/\sqrt{mER}) O ( 1/ m E R ) . Thus, for fixed E E 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 m m , local drift eventually matters, and FedZOO-NS incurs an additional variance floor from the Gaussian noise used for stability.
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 ) \boldsymbol Z^\top\nabla f(\boldsymbol w) Z ⊤ ∇ f ( w ) can be small even when ∇ f ( w ) \nabla f(\boldsymbol w) ∇ f ( w ) is not. To bridge the two, Appendix § 9.7 assumes that the seed directions capture the gradients encountered during training: for some κ Z > 0 \kappa_{\boldsymbol Z}>0 κ Z > 0 and ε c o v ≥ 0 \varepsilon_{\mathrm{cov}}\ge0 ε cov ≥ 0 ,
1 K ∥ Z ⊤ ∇ f ( w ) ∥ 2 ≥ κ Z ∥ ∇ f ( w ) ∥ 2 − ε c o v 2 . \begin{equation}
\frac1K\|\boldsymbol Z^\top\nabla f(\boldsymbol w)\|^2
\ge
\kappa_{\boldsymbol Z}\|\nabla f(\boldsymbol w)\|^2
-
\varepsilon_{\mathrm{cov}}^2. \tag*{(32)}
\end{equation} K 1 ∥ Z ⊤ ∇ f ( w ) ∥ 2 ≥ κ Z ∥∇ f ( w ) ∥ 2 − ε cov 2 . (32)
Corollary 7 in Appendix § 9.7 then converts the seed-subspace bound into a full-space guarantee, with the expected 1 / κ Z 1/\kappa_{\boldsymbol Z} 1/ κ Z scaling and additive coverage error ε c o v 2 / κ Z \varepsilon_{\mathrm{cov}}^2/\kappa_{\boldsymbol Z} ε cov 2 / κ 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 r r r -dimensional subspace chosen independently of the seed pool, Proposition 2 in Appendix § 9.7 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 K<d K < d : a rank-deficient seed span can make Z ⊤ ∇ f ( w ) = 0 \boldsymbol Z^\top\nabla f(\boldsymbol w)=0 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 § 9.8 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.
Experiments
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.
Table 1. Comparison of accuracy (% \% % ), runtime (s), and communication cost (MB) against zeroth-order baselines under varying levels of data heterogeneity on vision tasks. Our methods are shaded in gray, with the best accuracies in bold.
Table 2. Comparison of ROUGE-L scores (% \% % ), runtime (s), and communication cost (MB) with zeroth-order baselines under different split settings on TOFU. Our methods are shaded in gray, with the best ROUGE-L scores in bold.
Experimental Setup
Datasets and Models
We evaluate our methods on MNIST [4 ] , FashionMNIST [7 ] , SVHN [5 ] , CIFAR-10 [6 ] , and the TOFU benchmark for LLM unlearning [32 ] . Vision data are partitioned across clients using a Dirichlet distribution with α ∈ { 0.1 , 0.5 , 1.0 } \alpha\in\{0.1,0.5,1.0\} α ∈ { 0.1 , 0.5 , 1.0 } . To construct low-quality forget sets, we randomly select 20 % 20\% 20% of clients and flip the labels of 20 % 20\% 20% of their local samples. For TOFU, we use the standard Split99, Split95, and Split90, with retain/forget ratios of 99 % / 1 % 99\%/1\% 99%/1% , 95 % / 5 % 95\%/5\% 95%/5% , and 90 % / 10 % 90\%/10\% 90%/10% . Retain data are uniformly distributed across all clients, whereas forget data are uniformly assigned to 20 % 20\% 20% of clients. We use a two-hidden-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.2-1B-Instruct and Llama-3.2-3B-Instruct.
Baselines
We compare our methods with state-of-the-art baselines in federated optimization and unlearning. For optimization, we consider two zeroth-order baselines: FedKSeed Pro [1 ] uses a fixed seed pool and scalar-gradient accumulators; DeComFL [8 ] reconstructs client models from historical seeds and aggregated gradient scalars, making per-round uplink and downlink costs independent of model dimension. In vision unlearning: Re-optimization retrains from scratch; FATS-SU [3 ] replays training from the first step involving a target sample; FedRR [9 ] uses Fisher information for fast retraining; and FUDD [10 ] generates private synthetic data through knowledge distillation for server-side unlearning. For TOFU, we consider two baselines: re-optimization and Oblivionis [11 ] , which is a LoRA-based method that alternates between retain-set fine-tuning and forget-set unlearning.
Hyperparameters
The following settings are used unless otherwise specified: total number of clients M = 100 M=100 M = 100 , number of participating clients per round m = 10 m=10 m = 10 , accumulator size K = 4096 K=4096 K = 4096 , number of local steps E = 10 E=10 E = 10 , mini-batch size b = 32 b=32 b = 32 , and number of perturbation directions per sample q = 1 q=1 q = 1 . For vision tasks, we run R = 300 R=300 R = 300 communication rounds with perturbation scale μ = 10 − 3 \mu=10^{-3} μ = 1 0 − 3 and clipping threshold C = 50.0 C=50.0 C = 50.0 , and tune the learning rate η \eta η over { 10 − 5 , 3 × 10 − 5 , 10 − 4 , 3 × 10 − 4 , 10 − 3 , 3 × 10 − 3 } \{10^{-5},3\times10^{-5},10^{-4},3\times10^{-4},10^{-3},3\times10^{-3}\} { 1 0 − 5 , 3 × 1 0 − 5 , 1 0 − 4 , 3 × 1 0 − 4 , 1 0 − 3 , 3 × 1 0 − 3 } . For TOFU, the corresponding settings are R = 30 R=30 R = 30 , μ = 5 × 10 − 5 \mu=5\times10^{-5} μ = 5 × 1 0 − 5 , and C = 100.0 C=100.0 C = 100.0 ; we tune η \eta η over { 5 × 10 − 7 , 10 − 6 , 3 × 10 − 6 , 5 × 10 − 6 , 10 − 5 , 3 × 10 − 5 } \{5\times10^{-7},10^{-6},3\times10^{-6},5\times10^{-6},10^{-5},3\times10^{-5}\} { 5 × 1 0 − 7 , 1 0 − 6 , 3 × 1 0 − 6 , 5 × 1 0 − 6 , 1 0 − 5 , 3 × 1 0 − 5 } .
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 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.
Figure 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.
Figure 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-1B-Instruct. Right: Llama-3.2-3B-Instruct.
Experimental Results
We evaluate FedZOO-S and FedZOO-NS on four vision benchmarks, as well as TOFU. For FedZOO-NS, we consider multiple noise scales. We vary the degree of data heterogeneity on the vision benchmarks using α ∈ { 0.1 , 0.5 , 1.0 } \alpha\in\{0.1,0.5,1.0\} α ∈ { 0.1 , 0.5 , 1.0 } and evaluate TOFU under retain/forget splits of 99 % / 1 % 99\%/1\% 99%/1% , 95 % / 5 % 95\%/5\% 95%/5% , and 90 % / 10 % 90\%/10\% 90%/10% , using only the retain set for optimization. We compare our algorithms with two state-of-the-art baselines.
As shown in Table 1 , our methods match or outperform the baselines across all 12 vision settings, with accuracy gains of up to 9.13 9.13 9.13 percentage points. FedZOO-S achieves the best or tied-best accuracy in seven settings. These gains may partly arise from using b q E bqE b q E sample–direction pairs per participating client in each round, compared with E E E direction evaluations in FedKSeed Pro and DeComFL. For FedZOO-NS, the broader trend is that increasing the noise scale reduces accuracy. Nevertheless, it outperforms FedZOO-S in several settings, showing that moderate noise does not necessarily reduce model utility. Nevertheless, FedZOO-NS outperforms FedZOO-S in several settings, showing that moderate noise does not necessarily reduce model utility. With respect to data heterogeneity, FedZOO-S generally improves as α \alpha α increases and data heterogeneity decreases, whereas FedZOO-NS exhibits a non-monotonic trend, possibly due to noise-induced variation in its optimization trajectory. Table 2 reports the TOFU results. FedZOO-S achieves the highest ROUGE-L score for both model sizes across all splits. FedZOO-NS performs worse than FedZOO-S, with σ = 20 \sigma=20 σ = 20 consistently underperforming σ = 10 \sigma=10 σ = 10 . This contrasts with the mixed effect of noise on the vision tasks and suggests that LLM fine-tuning 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, Table 1 and Table 2 show that our methods trade additional local computation for improved utility while retaining dimension-independent communication. Their higher runtime stems from evaluating b q E bqE b q E sample–direction pairs per participating client in each round, compared with E E E direction evaluations in FedKSeed Pro and DeComFL. FedZOO-S and FedZOO-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.
Figure 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).
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. Figure 1 and Figure 2 summarize the performance on the vision tasks and TOFU under Split95, respectively. On the vision tasks, FedZOUL-S improves over FedZOO-S by up to 13.37 13.37 13.37 percentage points after removing low-quality target data, while its final accuracy remains within 2.77 2.77 2.77 percentage points of re-optimization across all four tasks. On TOFU, both variants reduce forget-set ROUGE-L after unlearning; although FedZOUL-S has higher forget-set scores than Oblivionis-U, it better preserves general knowledge, achieving 90.93 % 90.93\% 90.93% and 95.13 % 95.13\% 95.13% on Real Authors for the 1B and 3B models, compared with 58.08 % 58.08\% 58.08% and 64.13 % 64.13\% 64.13% for Oblivionis-U. FedZOUL-NS achieves competitive final accuracy on the vision tasks and forget-set performance similar to Oblivionis-U and re-optimization on TOFU. However, with the additional randomness introduced by noise injection, FedZOUL-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 FedZOO-NS in the federated optimization experiments.
Figure 4. Cumulative communication cost of FedZOUL-S/NS against re-optimization 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.
Figure 5. Cumulative communication cost of FedZOUL-S/NS against re-optimization and Oblivionis under stream unlearning requests on TOFU (Split95). Left: Llama-3.2-1B-Instruct, right: Llama-3.2-3B-Instruct.
To evaluate efficiency, we compare the cumulative runtime of FedZOUL-S and FedZOUL-NS with re-optimization in Figure 3 . At the final request, FedZOUL-S and FedZOUL-NS reduce runtime by 2.2 % 2.2\% 2.2% and 12.4 % 12.4\% 12.4% on CIFAR-10 and by 22.5 % 22.5\% 22.5% and 56.1 % 56.1\% 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 FedZOUL-NS. Figure 4 and Figure 5 show similar gains in communication. Unlike FATS-SU 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, FedZOUL-NS incurs 389.1 MB, which is 99.5 % 99.5\% 99.5% , 99.7 % 99.7\% 99.7% , 42.7 % 42.7\% 42.7% , and 5.7 % 5.7\% 5.7% lower than FATS-SU, FedRR, FUDD, and re-optimization, respectively. After five requests on TOFU with the 3B model, FedZOUL-S and FedZOUL-NS incur only 12.38 MB and 1.89 MB, compared with 27.08 GB for Oblivionis. Thus, FedZOUL-NS reduces communication by approximately four orders of magnitude, highlighting its 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 § 8.1 . Both FedZOUL-S and FedZOUL-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.
Impact of the Client Sampling Ratio m / M m/M m / M
Figure 6. Impact of the client sampling ratio (m / M m/M 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.
We study how the client sampling ratio m / M m/M m / M affects the utility and efficiency of FedZOO-S/NS and FedZOUL-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 m/M m / M from 0.1 0.1 0.1 to 0.3 0.3 0.3 improves optimization accuracy, while further increases provide limited gains. For unlearning, FedZOUL-S achieves its highest accuracy of 68.27 % 68.27\% 68.27% at m / M = 0.5 m/M=0.5 m / M = 0.5 , whereas FedZOUL-NS reaches 72.73 % 72.73\% 72.73% at 0.9 0.9 0.9 . These results show that greater participation generally improves model utility, although accuracy does not increase monotonically. Except at m / M = 0.1 m/M=0.1 m / M = 0.1 , FedZOO-NS and FedZOUL-NS achieve higher accuracy than FedZOO-S and FedZOUL-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 FedZOO-S/NS increases by a factor of 8.27 8.27 8.27 from m / M = 0.1 m/M=0.1 m / M = 0.1 to 0.9 0.9 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. FedZOUL-NS consistently uses less time and communication than FedZOUL-S: Gaussian coupling allows affected updates to be reused until the first rejection. However, its runtime and communication savings decrease from 24.3 % 24.3\% 24.3% and 15.9 % 15.9\% 15.9% at m / M = 0.1 m/M=0.1 m / M = 0.1 to 9.9 % 9.9\% 9.9% and 2.1 % 2.1\% 2.1% at 0.9 0.9 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.
Impact of Hyperparameters K K K and q q q
We examine the effects of K K K and q q q on FashionMNIST, with detailed results reported in the Appendix § 8.2 . Smaller seed pools generally favor FedZOO-S, whereas larger pools tend to benefit FedZOO-NS. Increasing q q q can improve accuracy for both methods, although the gains are not monotonic. Communication cost grows linearly with K K K and is independent of q q q , while runtime increases with both parameters.
Conclusion
We present a framework for efficient federated zeroth-order optimization and exact unlearning based on total variation stability. FedZOO-S obtains stability through subsampling, and FedZOUL-S reuses unaffected training computation to achieve efficient exact unlearning. Building on this design, FedZOO-NS incorporates Gaussian randomization, allowing FedZOUL-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.
Additional experimental results
GPU Memory cost of FedZOUL-S/NS
We evaluate peak GPU memory in Figure 7 . FedZOUL-S and FedZOUL-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 128.08 128.08 MB, 60.8 % 60.8\% 60.8% below FedRR and 54.0 % 54.0\% 54.0% below FUDD. On TOFU, their peak memory is 6.63 6.63 6.63 GB for the 3B model, compared with 11.15 11.15 11.15 GB for Oblivionis, and the reduction relative to Oblivionis increases from 24.3 % 24.3\% 24.3% for the 1B model to 40.5 % 40.5\% 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.
Figure 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).
Impact of Hyperparameters K K K and q q q
We investigate how the accuracy, communication cost, and time cost of FedZOO-S and FedZOO-NS vary with q q q and K K K on FashionMNIST, as shown in Figure 8 . For FedZOO-S, increasing q q q generally improves accuracy, although the gains are not monotonic. At K = 1024 K=1024 K = 1024 , accuracy increases from 64.46 % 64.46\% 64.46% at q = 1 q=1 q = 1 to 68.12 % 68.12\% 68.12% at q = 3 q=3 q = 3 , before decreasing to 67.71 % 67.71\% 67.71% at q = 4 q=4 q = 4 . FedZOO-NS also exhibits a non-monotonic response: increasing q q q from 1 to 2 improves accuracy for every tested K K K . Its best accuracy is attained at q = 2 q=2 q = 2 for K ∈ { 1024 , 2048 , 4096 } K\in\{1024,2048,4096\} K ∈ { 1024 , 2048 , 4096 } and at q = 3 q=3 q = 3 for K = 8192 K=8192 K = 8192 .
The effect of K K K differs between the two methods. FedZOO-S achieves its highest accuracy at K = 1024 K=1024 K = 1024 for q ∈ { 2 , 3 , 4 } q\in\{2,3,4\} q ∈ { 2 , 3 , 4 } , whereas K = 2048 K=2048 K = 2048 performs best at q = 1 q=1 q = 1 . Increasing K K K can reduce accuracy: at q = 3 q=3 q = 3 , accuracy falls from 68.12 % 68.12\% 68.12% to 64.29 % 64.29\% 64.29% as K K K increases from 1024 to 8192. For FedZOO-NS, larger seed pools generally yield higher accuracy, but the trend is not monotonic. For example, at q = 1 q=1 q = 1 , accuracy increases from 55.38 % 55.38\% 55.38% at K = 1024 K=1024 K = 1024 to 64.11 % 64.11\% 64.11% at K = 4096 K=4096 K = 4096 , then decreases to 60.19 % 60.19\% 60.19% at K = 8192 K=8192 K = 8192 .
In terms of system overhead, the per-round communication cost is independent of q q q and increases linearly with K K K , with identical costs for both methods. Each of the m = 10 m=10 m = 10 participating clients uploads a K K K -dimensional float32 accumulator, while the server broadcasts the global accumulator, resulting in a per-round communication cost of 4 ( m + 1 ) K = 44 K 4(m+1)K=44K 4 ( m + 1 ) K = 44 K bytes. The average per-round runtime increases with both q q q and K K K in all tested configurations. At K = 4096 K=4096 K = 4096 , increasing q q q from 1 to 2 improves FedZOO-NS accuracy from 64.11 % 64.11\% 64.11% to 71.26 % 71.26\% 71.26% , while increasing per-round runtime from 2.883 2.883 2.883 to 3.073 3.073 3.073 s and leaving communication cost unchanged. We use K = 4096 K=4096 K = 4096 as an intermediate pool size and q = 1 q=1 q = 1 to limit local computation.
Figure 8. Impact of the number of per-sample perturbation directions (q q q ) and the scalar gradient accumulator size (K K 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.
Complete Theoretical Analysis
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 FedZOO-S, a deletion has no effect unless the removed sample was actually selected during training. In FedZOO-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 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 = R E T=RE T = R E denote the total number of local positions, and index them in chronological order by
τ ( r , t ) = ( r − 1 ) E + t . \begin{equation}
\tau(r,t)=(r-1)E+t. \tag*{(33)}
\end{equation} τ ( r , t ) = ( r − 1 ) E + t . (33)
For a request arriving after ( R u l , t u l ) (R_{ul},t_{ul}) ( R u l , t u l ) , write T u l = τ ( R u l , t u l ) T_{ul}=\tau(R_{ul},t_{ul}) T u l = τ ( R u l , t u l ) . A position contains the local updates of the m m m participating clients and, when t = E t=E t = E , the corresponding server aggregation. Position zero denotes the initialization before the first client set is sampled.
For ∙ ∈ { S , N S } \bullet\in\{\mathsf S,\mathsf{NS}\} ∙ ∈ { S , NS } , let O ∙ [ τ ] ( D ) \mathcal O_{\bullet}^{[\tau]}(\mathcal D) O ∙ [ τ ] ( D ) denote the joint law of the optimization variables and all saved state after τ \tau τ positions when training on D \mathcal D D . We use O ∙ , o u t ( D ) \mathcal O_{\bullet,\mathrm{out}}(\mathcal D) O ∙ , out ( D ) for the marginal law of the final reconstructed model. With this notation, exact unlearning at T u l T_{ul} T u l means that the state produced after processing the deletion has law O ∙ [ T u l ] ( D − ) \mathcal O_{\bullet}^{[T_{ul}]}(\mathcal D^-) O ∙ [ T u l ] ( D − ) , and continuing training from that state must yield O ∙ [ T ] ( D − ) \mathcal O_{\bullet}^{[T]}(\mathcal D^-) O ∙ [ T ] ( D − ) . Whenever part of the trajectory is rerun, the newly generated state replaces the old saved state over that part of the execution.
FedZOO-S Stability and Exact Unlearning
We first consider FedZOO-S and its unlearning procedure FedZOUL-S.
A deleted sample can change a FedZOO-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.
Proof of Lemma 1 . Fix a size-b b b subset A ⊆ D − A\subseteq\mathcal D^{-} A ⊆ D − . The first branch outputs A A A precisely when B = A \mathcal B=A B = A , while the second branch is entered with probability b / n b/n b / n and then outputs A A A with probability 1 / ( n − 1 b ) 1/\binom{n-1}{b} 1/ ( b n − 1 ) . Hence
P ( B − = A ) = 1 ( n b ) + b n 1 ( n − 1 b ) = n − b n 1 ( n − 1 b ) + b n 1 ( n − 1 b ) = 1 ( n − 1 b ) . \begin{align}
\mathbb P(\mathcal B^{-}=A)
&=
\frac1{\binom nb}
+
\frac bn\frac1{\binom{n-1}{b}}
\notag\\
&=
\frac{n-b}{n}\frac1{\binom{n-1}{b}}
+
\frac bn\frac1{\binom{n-1}{b}}
=
\frac1{\binom{n-1}{b}}. \tag*{(36)}
\end{align} P ( B − = A ) = ( b n ) 1 + n b ( b n − 1 ) 1 = n n − b ( b n − 1 ) 1 + n b ( b n − 1 ) 1 = ( b n − 1 ) 1 . (36) Since the two mini-batches cannot agree on the second branch, the disagreement probability is b / n b/n b / n . ◻
When B − = B \mathcal B^{-}=\mathcal B B − = B , use the same independently sampled size-q q 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 FedZOO-S. Because seed sampling is independent of data sampling, the second execution has the correct joint mini-batch–seed marginal.
Consider one deletion x − ∈ D c − x^{-}\in\mathcal D_{c^{-}} x − ∈ D c − and write n c − = ∣ D c − ∣ n_{c^{-}}=|\mathcal D_{c^{-}}| n c − = ∣ D c − ∣ . At local position ( r , t ) (r,t) ( r , t ) , define
H r , t ( x − ) = { c − ∈ C r , x − ∈ B c − r , t } . \begin{equation}
\mathcal H_{r,t}(x^{-})
=
\{c^{-}\in\mathcal C^r,
\ x^{-}\in\mathcal B_{c^{-}}^{r,t}\}. \tag*{(37)}
\end{equation} H r , t ( x − ) = { c − ∈ C r , x − ∈ B c − r , t } . (37)
For the first τ \tau τ local positions, let
Λ S ( τ , c − ) = min { 1 , τ m b M n c − } . \begin{equation}
\Lambda_{\mathsf S}(\tau,c^{-})
=
\min\left\{
1,
\frac{\tau mb}{Mn_{c^{-}}}
\right\}. \tag*{(38)}
\end{equation} Λ S ( τ , c − ) = min { 1 , M n c − τ mb } . (38)
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 FedZOO-S on the retained data.
At any local position, a hit occurs with probability
m M b n c − . \begin{equation}
\frac{m}{M}\frac{b}{n_{c^{-}}}. \tag*{(39)}
\end{equation} M m n c − b . (39)
The same client set is reused within a round, so these events need not be independent. A union bound over the first τ \tau τ positions nevertheless gives
P ( the two states differ by position τ ) ≤ Λ S ( τ , c − ) . \begin{equation}
\mathbb P(\text{the two states differ by position }\tau)
\le
\Lambda_{\mathsf S}(\tau,c^{-}). \tag*{(40)}
\end{equation} 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 − ∈ D c − x^{-}\in\mathcal D_{c^{-}} x − ∈ D c − ,
TV ( O S , o u t ( D ) , O S , o u t ( D − ) ) ≤ Λ S ( T , c − ) . \begin{equation}
\operatorname{TV}\left(
\mathcal O_{\mathsf S,\mathrm{out}}(\mathcal D),
\mathcal O_{\mathsf S,\mathrm{out}}(\mathcal D^{-})
\right)
\le
\Lambda_{\mathsf S}(T,c^{-}). \tag*{(41)}
\end{equation} TV ( O S , out ( D ) , O S , out ( D − ) ) ≤ Λ S ( T , c − ) . (41) If a target 0 < ρ ≤ 1 0<\rho\le1 0 < ρ ≤ 1 is fixed before training and
T m b M n ‾ ≤ ρ , \begin{equation}
\frac{Tmb}{M\underline n}
\le
\rho, \tag*{(42)}
\end{equation} M n T mb ≤ ρ , (42) then FedZOO-S is ρ \rho ρ -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 \mathcal D D and D − \mathcal D^{-} D − . By Eq. (40) , their disagreement probability at τ = T \tau=T τ = T is at most Λ S ( T , c − ) \Lambda_{\mathsf S}(T,c^{-}) Λ S ( T , c − ) . Projecting the coupled states onto the final reconstructed model can only decrease total variation. Under (42) , n c − ≥ n ‾ n_{c^{-}}\ge\underline n n c − ≥ n gives Λ S ( T , c − ) ≤ ρ \Lambda_{\mathsf S}(T,c^{-})\le\rho Λ 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 m/M m / M , and conditional on participation, the deleted sample enters its mini-batch with probability b / n c − b/n_{c^{-}} b / n c − . 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 mini-batch, so training only needs to be rerun from that point. Let U S [ T u l ] \mathcal U_{\mathsf S}^{[T_{ul}]} U S [ T u l ] denote the state returned by FedZOUL-S at position T u l T_{ul} T u l after processing the deletion, and let U S T u l → T \mathcal U_{\mathsf S}^{T_{ul}\to T} U S T u l → T denote the state after the remaining training positions are completed.
Theorem 2 (Exact unlearning of FedZOUL-S). For every valid single-sample deletion x − ∈ D c − x^{-}\in\mathcal D_{c^{-}} x − ∈ D c − arriving after local position T u l T_{ul} T u l ,
U S [ T u l ] ( O S [ T u l ] ( D ) , { x − } ) = d O S [ T u l ] ( D − ) . \begin{equation}
\mathcal U_{\mathsf S}^{[T_{ul}]}
\left(
\mathcal O_{\mathsf S}^{[T_{ul}]}(\mathcal D),
\{x^{-}\}
\right)
\overset{d}{=}
\mathcal O_{\mathsf S}^{[T_{ul}]}(\mathcal D^{-}). \tag*{(43)}
\end{equation} U S [ T u l ] ( O S [ T u l ] ( D ) , { x − } ) = d O S [ T u l ] ( D − ) . (43) Consequently,
U S T u l → T ( O S [ T u l ] ( D ) , { x − } ) = d O S [ T ] ( D − ) , \begin{equation}
\mathcal U_{\mathsf S}^{T_{ul}\to T}
\left(
\mathcal O_{\mathsf S}^{[T_{ul}]}(\mathcal D),
\{x^{-}\}
\right)
\overset{d}{=}
\mathcal O_{\mathsf S}^{[T]}(\mathcal D^{-}), \tag*{(44)}
\end{equation} U S T u l → T ( O S [ T u l ] ( D ) , { x − } ) = d O S [ T ] ( D − ) , (44) where both equalities hold jointly over the model and every maintained state. If R e p l a y S \mathsf{Replay}_{\mathsf S} Replay S denotes the event that the deletion causes training to be rerun from an affected position, then
P ( R e p l a y S ) ≤ Λ S ( T u l , c − ) ≤ T u l m b M n c − . \begin{equation}
\mathbb P(\mathsf{Replay}_{\mathsf S})
\le
\Lambda_{\mathsf S}(T_{ul},c^{-})
\le
\frac{T_{ul}mb}{Mn_{c^{-}}}. \tag*{(45)}
\end{equation} P ( Replay S ) ≤ Λ S ( T u l , c − ) ≤ M n c − T u l mb . (45) Under (42) , this probability is at most ρ \rho ρ .
Proof of Theorem 2 . Use the same coupling as in the proof of Theorem 1 through position T u l T_{ul} T u l , and let ( r ⋆ , t ⋆ ) (r^\star,t^\star) ( 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 − x^{-} x − , FedZOUL-S keeps that state and continues from N e x t ( R u l , t u l ) \mathsf{Next}(R_{ul},t_{ul}) Next ( R u l , t u l ) . 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 ⋆ ) (r^\star,t^\star) ( 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 ⋆ ) (r^\star,t^\star) ( r ⋆ , t ⋆ ) on the retained datasets. The saved client set C r ⋆ \mathcal C^{r^\star} 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.
In both branches, the state returned at T u l T_{ul} T u l has law O S [ T u l ] ( D − ) \mathcal O_{\mathsf S}^{[T_{ul}]}(\mathcal D^{-}) O S [ T u l ] ( 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
( c j − , x j − , T u l ( j ) ) j = 1 k , 0 ≤ T u l ( 1 ) ≤ ⋯ ≤ T u l ( k ) ≤ T . \begin{equation}
\bigl(c_j^{-},x_j^{-},T_{ul}^{(j)}\bigr)_{j=1}^{k},
\qquad
0\le T_{ul}^{(1)}\le\cdots\le T_{ul}^{(k)}\le T. \tag*{(46)}
\end{equation} ( c j − , x j − , T u l ( j ) ) j = 1 k , 0 ≤ T u l ( 1 ) ≤ ⋯ ≤ T u l ( k ) ≤ T . (46)
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.
Let D ( 1 ) = D \mathcal D^{(1)}=\mathcal D D ( 1 ) = D , and let D ( j ) \mathcal D^{(j)} D ( j ) and D ( j + 1 ) \mathcal D^{(j+1)} D ( j + 1 ) be the datasets immediately before and after request j j j . Thus x j − ∈ D c j − ( j ) x_j^{-}\in\mathcal D_{c_j^{-}}^{(j)} x j − ∈ D c j − ( j ) is removed to form D c j − ( j + 1 ) \mathcal D_{c_j^{-}}^{(j+1)} D c j − ( j + 1 ) , while the other local datasets are unchanged. We keep the learning hyperparameters fixed throughout the stream and assume that every retained client dataset has size at least
n ‾ ≤ min 1 ≤ j ≤ k + 1 , c ∈ [ M ] ∣ D c ( j ) ∣ , n ‾ ≥ b . \begin{equation}
\underline n
\le
\min_{1\le j\le k+1,\,c\in[M]}|\mathcal D_c^{(j)}|,
\qquad
\underline n\ge b. \tag*{(47)}
\end{equation} n ≤ 1 ≤ j ≤ k + 1 , c ∈ [ M ] min ∣ D c ( j ) ∣ , n ≥ b . (47)
For a single request we use the actual pre-request dataset size; n ‾ \underline n 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 Eq. (46) , and let n j = ∣ D c j − ( j ) ∣ n_j=|\mathcal D_{c_j^{-}}^{(j)}| n j = ∣ D c j − ( j ) ∣ be the affected client’s pre-request data size. After every request j j j , the returned state at T u l ( j ) T_{ul}^{(j)} T u l ( j ) has law O S [ T u l ( j ) ] ( D ( j + 1 ) ) \mathcal O_{\mathsf S}^{[T_{ul}^{(j)}]}(\mathcal D^{(j+1)}) O S [ T u l ( j ) ] ( D ( j + 1 ) ) . If N S r e p N_{\mathsf S}^{\mathrm{rep}} N S rep is the number of requests that trigger replay, then
E [ N S r e p ] ≤ ∑ j = 1 k min { 1 , T u l ( j ) m b M n j } , P ( N S r e p ≥ 1 ) ≤ min { 1 , ∑ j = 1 k T u l ( j ) m b M n j } . \begin{align}
\mathbb E[N_{\mathsf S}^{\mathrm{rep}}]
&\le
\sum_{j=1}^{k}
\min\left\{
1,
\frac{T_{ul}^{(j)}mb}{Mn_j}
\right\}, \tag*{(48)}
\\
\mathbb P(N_{\mathsf S}^{\mathrm{rep}}\ge1)
&\le
\min\left\{
1,
\sum_{j=1}^{k}
\frac{T_{ul}^{(j)}mb}{Mn_j}
\right\}. \tag*{(49)}
\end{align} E [ N S rep ] P ( N S rep ≥ 1 ) ≤ j = 1 ∑ k min { 1 , M n j T u l ( j ) mb } , ≤ min { 1 , j = 1 ∑ k M n j T u l ( j ) mb } . (48) (49) Under (47) and (42) , these bounds are at most k ρ k\rho k ρ and min { 1 , k ρ } \min\{1,k\rho\} min { 1 , k ρ } , respectively.
Proof of Corollary 1 . Fix the request stream and the perturbation pool. Let X j − X_j^{-} X j − and X j + X_j^{+} X j + be the complete saved states immediately before and after processing request j j j , both at position T u l ( j ) T_{ul}^{(j)} T u l ( j ) . We prove by induction that
X j − = d O S [ T u l ( j ) ] ( D ( j ) ) , X j + = d O S [ T u l ( j ) ] ( D ( j + 1 ) ) . \begin{align}
X_j^{-}&\overset d=
\mathcal O_{\mathsf S}^{[T_{ul}^{(j)}]}(\mathcal D^{(j)}),
\notag\\
X_j^{+}&\overset d=
\mathcal O_{\mathsf S}^{[T_{ul}^{(j)}]}(\mathcal D^{(j+1)}). \tag*{(50)}
\end{align} X j − X j + = d O S [ T u l ( j ) ] ( D ( j ) ) , = d O S [ T u l ( j ) ] ( D ( j + 1 ) ) . (50) The first equality for j = 1 j=1 j = 1 follows from the initial learning run. Given its validity for request j j j , apply Theorem 2 with the fixed deletion x j − x_j^{-} x j − and fresh unlearning randomness to obtain the second equality. Continue with the retained-data learning kernels and fresh randomness until T u l ( j + 1 ) T_{ul}^{(j+1)} T u l ( j + 1 ) . This gives the first equality for request j + 1 j+1 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 I j I_j I j indicate whether request j j j triggers replay. Applying the single-request replay bound to the first marginal in Eq. (50) gives
E [ I j ] = P ( I j = 1 ) ≤ min { 1 , T u l ( j ) m b M n j } . \mathbb E[I_j]=\mathbb P(I_j=1)
\le\min\left\{1,\frac{T_{ul}^{(j)}mb}{Mn_j}\right\}. E [ I j ] = P ( I j = 1 ) ≤ min { 1 , M n j T u l ( j ) mb } . Since N S r e p = ∑ j = 1 k I j N_{\mathsf S}^{\mathrm{rep}}=\sum_{j=1}^{k}I_j N S rep = ∑ j = 1 k I j , linearity of expectation proves Eq. (48) ; a union bound proves Eq. (49) . Independence of the I j I_j I j is not needed. The bounds are uniform in the perturbation pool, so averaging over it preserves them. The calibrated bounds follow from n j ≥ n ‾ n_j\ge\underline n n j ≥ n and T u l ( j ) ≤ T T_{ul}^{(j)}\le T T u l ( j ) ≤ T . ◻
For FedZOO-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.
FedZOO-NS Stability
For probability measures P ≪ Q P\ll Q P ≪ Q , write
D K L ( P ∥ Q ) = ∫ log ( d P d Q ) d P , D 2 ( P ∥ Q ) = log ∫ ( d P d Q ) 2 d Q , \begin{align}
D_{\mathrm{KL}}(P\|Q)
&=
\int\log\left(\frac{dP}{dQ}\right)dP,
\notag\\
D_2(P\|Q)
&=
\log\int\left(\frac{dP}{dQ}\right)^2dQ, \tag*{(51)}
\end{align} D KL ( P ∥ Q ) D 2 ( P ∥ Q ) = ∫ log ( d Q d P ) d P , = log ∫ ( d Q d P ) 2 d Q , (51)
and let χ 2 ( P ∥ Q ) = exp ( D 2 ( P ∥ Q ) ) − 1 \chi^2(P\|Q)=\exp(D_2(P\|Q))-1 χ 2 ( P ∥ Q ) = exp ( D 2 ( P ∥ Q )) − 1 .
Lemma 2 (Single-deletion replacement coupling). Let D = D − ∪ { x − } \mathcal D=\mathcal D^{-}\cup\{x^{-}\} D = D − ∪ { x − } with ∣ D ∣ = n |\mathcal D|=n ∣ D ∣ = n and ∣ D − ∣ = n − 1 ≥ b |\mathcal D^{-}|=n-1\ge b ∣ D − ∣ = n − 1 ≥ b . Draw B \mathcal B B uniformly from the size-b b b subsets of D \mathcal D D and construct
B ′ = { B , x − ∉ B , ( B ∖ { x − } ) ∪ { Y } , x − ∈ B , \begin{equation}
\mathcal B'
=
\begin{cases}
\mathcal B,
&x^{-}\notin\mathcal B,\\
(\mathcal B\setminus\{x^{-}\})\cup\{Y\},
&x^{-}\in\mathcal B,
\end{cases} \tag*{(52)}
\end{equation} B ′ = { B , ( B ∖ { x − }) ∪ { Y } , x − ∈ / B , x − ∈ B , (52) where, on the second branch, Y Y Y is uniform on D − ∖ ( B ∖ { x − } ) \mathcal D^{-}\setminus(\mathcal B\setminus\{x^{-}\}) D − ∖ ( B ∖ { x − }) , independently of the seed sets and Gaussian noise. Then B ′ \mathcal B' B ′ is uniform over the size-b b b subsets of D − \mathcal D^{-} D − , conditional on either branch and unconditionally. Keeping the seed sets of retained samples and assigning the seed set of x − x^{-} x − to Y Y Y gives the joint mini-batch–seed law of a retained-data local step.
Proof of Lemma 2 . Conditional on x − ∉ B x^{-}\notin\mathcal B x − ∈ / B , the original mini-batch is already a uniform size-b b b subset of D − \mathcal D^{-} D − . Conditional on a hit, fix a size-b b b subset A ⊆ D − A\subseteq\mathcal D^{-} A ⊆ D − . For each y ∈ A y\in A y ∈ A , the output is A A A when B ∖ { x − } = A ∖ { y } \mathcal B\setminus\{x^{-}\}=A\setminus\{y\} B ∖ { x − } = A ∖ { y } and Y = y Y=y Y = y . Hence
P ( B ′ = A ∣ x − ∈ B ) = b ( n − 1 b − 1 ) ( n − b ) = 1 ( n − 1 b ) . \begin{equation}
\mathbb P(\mathcal B'=A\mid x^{-}\in\mathcal B)
=
\frac{b}{\binom{n-1}{b-1}(n-b)}
=
\frac1{\binom{n-1}{b}}. \tag*{(53)}
\end{equation} P ( B ′ = A ∣ x − ∈ B ) = ( b − 1 n − 1 ) ( n − b ) b = ( b n − 1 ) 1 . (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 b b resulting samples remain independent, each with the uniform size-q q q law on S \mathbb S 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 q q coefficients that belonged to the deleted sample can change. Since each clipped and normalized clean coefficient lies in [ − C / ( b q ) , C / ( b q ) ] [-C/(bq),C/(bq)] [ − C / ( b q ) , C / ( b q )] , the two clean vectors satisfy
∥ h − h ′ ∥ 2 ≤ 2 C b q . \begin{equation}
\|\boldsymbol h-\boldsymbol h'\|_2
\le
\frac{2C}{b\sqrt q}. \tag*{(54)}
\end{equation} ∥ h − h ′ ∥ 2 ≤ b q 2 C . (54)
Here h ′ \boldsymbol h' 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 n n be its local data size before deletion. Let P P P and Q Q Q be the conditional laws of the resulting seed-coordinate increment on D c \mathcal D_c D c and D c − \mathcal D_c^{-} D c − , respectively. Then
D K L ( P ∥ Q ) ≤ D 2 ( P ∥ Q ) ≤ ε s t e p ( n , σ ρ ) , \begin{equation}
D_{\mathrm{KL}}(P\|Q)
\le
D_2(P\|Q)
\le
\varepsilon_{\mathrm{step}}(n,\sigma_\rho), \tag*{(55)}
\end{equation} D KL ( P ∥ Q ) ≤ D 2 ( P ∥ Q ) ≤ ε step ( n , σ ρ ) , (55) where
ε s t e p ( n , σ ) = log [ 1 + ( b n ) 2 ( exp ( 4 C 2 / ( b 2 q ) σ 2 ) − 1 ) ] . \begin{equation}
\varepsilon_{\mathrm{step}}(n,\sigma)
=
\log\left[
1+
\left(\frac bn\right)^2
\left(
\exp\left(\frac{4C^2/(b^2q)}{\sigma^2}\right)-1
\right)
\right]. \tag*{(56)}
\end{equation} ε step ( n , σ ) = log [ 1 + ( n b ) 2 ( exp ( σ 2 4 C 2 / ( b 2 q ) ) − 1 ) ] . (56)
Proof of Lemma 3 . Let β = b / n \beta=b/n β = b / n , and let P 1 P_1 P 1 denote the law of the seed-coordinate increment conditional on x − x^{-} 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 + β P 1 . \begin{equation}
P=(1-\beta)Q+\beta P_1. \tag*{(57)}
\end{equation} P = ( 1 − β ) Q + β P 1 . (57) On a hit, couple the batches by Lemma 2 . Let λ \lambda λ collect the original batch, its replacement Y Y Y , and all sample-specific seed sets, and let π \pi π be their joint law conditional on the hit. Given λ \lambda λ , write both coefficient vectors in the original pair coordinates. Their Gaussian laws are
G λ = N ( h λ , σ ρ 2 I b q ) , G λ ′ = N ( h λ ′ , σ ρ 2 I b q ) . G_\lambda=\mathcal N(\boldsymbol h_\lambda,\sigma_\rho^2I_{bq}),
\qquad
G'_\lambda=\mathcal N(\boldsymbol h'_{\lambda},
\sigma_\rho^2I_{bq}). G λ = N ( h λ , σ ρ 2 I b q ) , G λ ′ = N ( h λ ′ , σ ρ 2 I b q ) . Define augmented measures P ‾ 1 ( d λ , d v ) = π ( d λ ) G λ ( d v ) \overline P_1(d\lambda,dv)=\pi(d\lambda)G_\lambda(dv) P 1 ( d λ , d v ) = π ( d λ ) G λ ( d v ) and Q ‾ ( d λ , d v ) = π ( d λ ) G λ ′ ( d v ) \overline Q(d\lambda,dv)=\pi(d\lambda)G'_\lambda(dv) Q ( d λ , d v ) = π ( d λ ) G λ ′ ( d v ) . They share the same latent measure. Conditional Gaussian integration gives
χ 2 ( P ‾ 1 ∥ Q ‾ ) = E λ ∼ π [ exp ( ∥ h λ − h λ ′ ∥ 2 2 σ ρ 2 ) − 1 ] ≤ exp ( 4 C 2 / ( b 2 q ) σ ρ 2 ) − 1. \begin{align}
\chi^2(\overline P_1\|\overline Q)
&=
\mathbb E_{\lambda\sim\pi}
\left[
\exp\!\left(
\frac{\|\boldsymbol h_\lambda-
\boldsymbol h'_{\lambda}\|_2^2}{\sigma_\rho^2}
\right)-1
\right]
\notag\\
&\le
\exp\!\left(\frac{4C^2/(b^2q)}{\sigma_\rho^2}\right)-1. \tag*{(58)}
\end{align} χ 2 ( P 1 ∥ Q ) = E λ ∼ π [ exp ( σ ρ 2 ∥ h λ − h λ ′ ∥ 2 2 ) − 1 ] ≤ exp ( σ ρ 2 4 C 2 / ( b 2 q ) ) − 1. (58) 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 Q Q . Data processing therefore yields
χ 2 ( P 1 ∥ Q ) ≤ exp ( 4 C 2 / ( b 2 q ) σ ρ 2 ) − 1. \begin{equation}
\chi^2(P_1\|Q)
\le
\exp\!\left(\frac{4C^2/(b^2q)}{\sigma_\rho^2}\right)-1. \tag*{(59)}
\end{equation} χ 2 ( P 1 ∥ Q ) ≤ exp ( σ ρ 2 4 C 2 / ( b 2 q ) ) − 1. (59) Writing u = d P 1 / d Q u=dP_1/dQ u = d P 1 / d Q , Eq. (57) implies
exp ( D 2 ( P ∥ Q ) ) = ∫ ( ( 1 − β ) + β u ) 2 d Q = 1 + β 2 χ 2 ( P 1 ∥ Q ) . \begin{align}
\exp(D_2(P\|Q))
&=
\int((1-\beta)+\beta u)^2dQ
\notag\\
&=
1+\beta^2\chi^2(P_1\|Q). \tag*{(60)}
\end{align} exp ( D 2 ( P ∥ Q )) = ∫ (( 1 − β ) + β u ) 2 d Q = 1 + β 2 χ 2 ( P 1 ∥ Q ) . (60) Combining this identity with Eq. (59) and D K L ≤ D 2 D_{\mathrm{KL}}\le D_2 D KL ≤ D 2 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 \mathcal D D and D − \mathcal D^{-} D − differing by the deletion of x − ∈ D c − x^{-}\in\mathcal D_{c^{-}} x − ∈ D c − , and let n c − = ∣ D c − ∣ n_{c^{-}}=|\mathcal D_{c^{-}}| n c − = ∣ D c − ∣ before deletion. Conditionally on the fixed seed pool,
TV ( O N S , o u t ( D ) , O N S , o u t ( D − ) ) ≤ min { 1 , T m 2 M ε s t e p ( n c − , σ ρ ) } . \begin{align}
&\operatorname{TV}\left(
\mathcal O_{\mathsf{NS},\mathrm{out}}(\mathcal D),
\mathcal O_{\mathsf{NS},\mathrm{out}}(\mathcal D^{-})
\right)
\notag\\
&\quad\le
\min\left\{
1,
\sqrt{
\frac{Tm}{2M}
\varepsilon_{\mathrm{step}}
(n_{c^{-}},\sigma_\rho)
}
\right\}. \tag*{(61)}
\end{align} TV ( O NS , out ( D ) , O NS , out ( D − ) ) ≤ min { 1 , 2 M T m ε step ( n c − , σ ρ ) } . (61) 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 \boldsymbol Z 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 r r . The client set C r \mathcal C^r C r has the same data-independent law in both executions. If c − ∉ C r c^{-}\notin\mathcal C^r c − ∈ / C r , all conditional transitions in this round are identical. If c − ∈ C r c^{-}\in\mathcal C^r c − ∈ C r , the KL chain rule and Lemma 3 give
D K L ( P r ∥ Q r ∣ C r , H r − 1 ) ≤ E ε s t e p ( n c − , σ ρ ) . \begin{equation}
D_{\mathrm{KL}}(P_r\|Q_r
\mid\mathcal C^r,\mathcal H_{r-1})
\le
E\varepsilon_{\mathrm{step}}
(n_{c^{-}},\sigma_\rho). \tag*{(62)}
\end{equation} D KL ( P r ∥ Q r ∣ C r , H r − 1 ) ≤ E ε step ( n c − , σ ρ ) . (62) Averaging over the common client-set law yields
D K L ( P r ∥ Q r ∣ H r − 1 ) ≤ m M E ε s t e p ( n c − , σ ρ ) . \begin{equation}
D_{\mathrm{KL}}(P_r\|Q_r\mid\mathcal H_{r-1})
\le
\frac mM
E\varepsilon_{\mathrm{step}}
(n_{c^{-}},\sigma_\rho). \tag*{(63)}
\end{equation} D KL ( P r ∥ Q r ∣ H r − 1 ) ≤ M m E ε step ( n c − , σ ρ ) . (63) Applying the KL chain rule over the R R R rounds gives
D K L ( P 1 : R ∥ Q 1 : R ) ≤ T m M ε s t e p ( n c − , σ ρ ) . \begin{equation}
D_{\mathrm{KL}}(P_{1:R}\|Q_{1:R})
\le
\frac{Tm}{M}
\varepsilon_{\mathrm{step}}
(n_{c^{-}},\sigma_\rho). \tag*{(64)}
\end{equation} D KL ( P 1 : R ∥ Q 1 : R ) ≤ M T m ε step ( n c − , σ ρ ) . (64) Data processing to the final model and Pinsker’s inequality prove (61) . The bound is uniform in Z \boldsymbol Z Z , so averaging over the pool gives the unconditional claim. ◻
Corollary 2 (Noise level for a target stability ρ \rho ρ ). Fix 0 < ρ ≤ 1 0<\rho\le1 0 < ρ ≤ 1 before training and choose the standard deviation of every normalized scalar-noise coordinate as
σ ρ = max { 2 C b q , 2 C n ‾ q ρ T m M } . \begin{equation}
\sigma_\rho
=
\max\left\{
\frac{2C}{b\sqrt q},
\frac{2C}{\underline n\sqrt q\,\rho}
\sqrt{\frac{Tm}{M}}
\right\}. \tag*{(65)}
\end{equation} σ ρ = max { b q 2 C , n q ρ 2 C M T m } . (65) Then FedZOO-NS is ρ \rho ρ -sample-level TV stable on the dataset class satisfying (47) . More precisely,
TV ( O N S , o u t ( D ) , O N S , o u t ( D − ) ) ≤ 2 C n c − q σ ρ T m M ≤ ρ . \begin{align}
&\operatorname{TV}\left(
\mathcal O_{\mathsf{NS},\mathrm{out}}(\mathcal D),
\mathcal O_{\mathsf{NS},\mathrm{out}}(\mathcal D^{-})
\right)
\notag\\
&\quad\le
\frac{2C}{n_{c^{-}}\sqrt q\,\sigma_\rho}
\sqrt{\frac{Tm}{M}}
\le
\rho. \tag*{(66)}
\end{align} TV ( O NS , out ( D ) , O NS , out ( D − ) ) ≤ n c − q σ ρ 2 C M T m ≤ ρ . (66)
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 e x − 1 ≤ 2 x e^x-1\le2x e x − 1 ≤ 2 x for 0 ≤ x ≤ 1 0\le x\le1 0 ≤ x ≤ 1 and log ( 1 + x ) ≤ x \log(1+x)\le x log ( 1 + x ) ≤ x gives
ε s t e p ( n , σ ρ ) ≤ 8 C 2 n 2 q σ ρ 2 . \begin{equation}
\varepsilon_{\mathrm{step}}(n,\sigma_\rho)
\le
\frac{8C^2}{n^2q\sigma_\rho^2}. \tag*{(67)}
\end{equation} ε step ( n , σ ρ ) ≤ n 2 q σ ρ 2 8 C 2 . (67) Substitution into Theorem 3 yields the first inequality in (66) . The second term in (65) , together with n c − ≥ n ‾ n_{c^{-}}\ge\underline n n c − ≥ 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 ρ \rho ρ .
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 E E local steps. The factor m / M m/M m / M therefore appears once for the whole round, rather than as an independent subsampling factor at every local position. This is why the sufficient noise scale depends on m / M \sqrt{m/M} 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 FedZOO-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 [33 ] , adapted here to the sample–seed coefficients and accumulators maintained by the federated algorithm.
FedZOUL-NS Exact Unlearning
Lemma 4 (Gaussian maximal coupling by hyperplane reflection). Let P = N ( μ , σ 2 I p ) P=\mathcal N(\boldsymbol\mu,\sigma^2I_p) P = N ( μ , σ 2 I p ) and Q = N ( ν , σ 2 I p ) Q=\mathcal N(\boldsymbol\nu,\sigma^2I_p) Q = N ( ν , σ 2 I p ) , with densities p p p and q q q . For μ ≠ ν \boldsymbol\mu\ne\boldsymbol\nu μ = ν , define
m = μ + ν 2 , e = ν − μ ∥ ν − μ ∥ 2 , R μ , ν ( x ) = x − 2 ⟨ x − m , e ⟩ e . \begin{align}
\boldsymbol m
&=
\frac{\boldsymbol\mu+\boldsymbol\nu}{2},
&
\boldsymbol e
&=
\frac{\boldsymbol\nu-\boldsymbol\mu}
{\|\boldsymbol\nu-\boldsymbol\mu\|_2},
\notag\\
\mathsf R_{\boldsymbol\mu,\boldsymbol\nu}(\boldsymbol x)
&=
\boldsymbol x
-2\langle\boldsymbol x-\boldsymbol m,\boldsymbol e\rangle
\boldsymbol e. \tag*{(68)}
\end{align} m R μ , ν ( x ) = 2 μ + ν , = x − 2 ⟨ x − m , e ⟩ e . e = ∥ ν − μ ∥ 2 ν − μ , (68) Draw X ∼ P X\sim P X ∼ P and U ∼ Unif ( 0 , 1 ) U\sim\operatorname{Unif}(0,1) U ∼ Unif ( 0 , 1 ) independently, and set
Y = { X , U ≤ min { 1 , q ( X ) / p ( X ) } , R μ , ν ( X ) , otherwise . \begin{equation}
Y
=
\begin{cases}
X,
&U\le\min\{1,q(X)/p(X)\},\\
\mathsf R_{\boldsymbol\mu,\boldsymbol\nu}(X),
&\text{otherwise}.
\end{cases} \tag*{(69)}
\end{equation} Y = { X , R μ , ν ( X ) , U ≤ min { 1 , q ( X ) / p ( X )} , otherwise . (69) Then Y ∼ Q Y\sim Q Y ∼ Q , and
P ( X ≠ Y ) = TV ( P , Q ) = 2 Φ ( ∥ μ − ν ∥ 2 2 σ ) − 1 ≤ ∥ μ − ν ∥ 2 2 π σ , \begin{align}
\mathbb P(X\ne Y)
&=
\operatorname{TV}(P,Q)
\notag\\
&=
2\Phi\left(
\frac{\|\boldsymbol\mu-\boldsymbol\nu\|_2}{2\sigma}
\right)-1
\notag\\
&\le
\frac{\|\boldsymbol\mu-\boldsymbol\nu\|_2}
{\sqrt{2\pi}\sigma}, \tag*{(70)}
\end{align} P ( X = Y ) = TV ( P , Q ) = 2Φ ( 2 σ ∥ μ − ν ∥ 2 ) − 1 ≤ 2 π σ ∥ μ − ν ∥ 2 , (70) where Φ \Phi Φ is the standard Gaussian CDF. If μ = ν \boldsymbol\mu=\boldsymbol\nu μ = ν , set Y = X Y=X Y = X .
Proof of Lemma 4 . The map R μ , ν \mathsf R_{\boldsymbol\mu,\boldsymbol\nu} 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 ) . \begin{equation}
p(\mathsf R_{\boldsymbol\mu,\boldsymbol\nu}(\boldsymbol x))
=
q(\boldsymbol x),
\qquad
q(\mathsf R_{\boldsymbol\mu,\boldsymbol\nu}(\boldsymbol x))
=
p(\boldsymbol x). \tag*{(71)}
\end{equation} p ( R μ , ν ( x )) = q ( x ) , q ( R μ , ν ( x )) = p ( x ) . (71) For any measurable set A A A , the accepted branch contributes ∫ A min { p , q } \int_A\min\{p,q\} ∫ A min { p , q } , while a change of variables in the reflected branch shows that it contributes ∫ A ( q − p ) + \int_A(q-p)_+ ∫ A ( q − p ) + . Their sum is Q ( A ) Q(A) Q ( A ) . The rejection probability is ∫ ( p − q ) + = TV ( P , Q ) \int(p-q)_+=\operatorname{TV}(P,Q) ∫ ( p − q ) + = TV ( P , Q ) . For distinct means, p ( x ) > q ( x ) p(\boldsymbol x)>q(\boldsymbol x) p ( x ) > q ( x ) precisely when ⟨ x − m , e ⟩ < 0 \langle\boldsymbol x-\boldsymbol m,\boldsymbol e\rangle<0 ⟨ 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 π \Phi(u)-1/2\le u/\sqrt{2\pi} Φ ( u ) − 1/2 ≤ u / 2 π . Importantly, the target law Q Q Q is obtained by combining the acceptance and reflection branches. Conditional on rejection, the reflected value instead has density ( q − p ) + / TV ( P , Q ) (q-p)_+/\operatorname{TV}(P,Q) ( q − p ) + / TV ( P , Q ) when this denominator is positive; it is not an independent draw from the full Q Q 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.
Lemma 5 (One-step exact transition for FedZOO-NS). Fix the seed pool, a local position ( r , t ) (r,t) ( 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 − ∈ D c − x^{-}\in\mathcal D_{c^{-}} x − ∈ D c − . 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 FedZOO-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 I b q ) , \mathcal N(\boldsymbol h,\sigma_\rho^2I_{bq}), N ( h , σ ρ 2 I b q ) , while the retained-data step requires
N ( h ′ , σ ρ 2 I b q ) . \mathcal N(\boldsymbol h',\sigma_\rho^2I_{bq}). N ( h ′ , σ ρ 2 I b q ) . 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. ◻
Let U N S [ T u l ] \mathcal U_{\mathsf{NS}}^{[T_{ul}]} U NS [ T u l ] denote the complete state returned by FedZOUL-NS at T u l T_{ul} T u l after processing the deletion, and let U N S T u l → T \mathcal U_{\mathsf{NS}}^{T_{ul}\to T} U NS T u l → T include completion of the horizon.
Theorem 4 (Exact unlearning of FedZOUL-NS). For every valid single-sample deletion x − ∈ D c − x^{-}\in\mathcal D_{c^{-}} x − ∈ D c − arriving after local position T u l T_{ul} T u l ,
U N S [ T u l ] ( O N S [ T u l ] ( D ) , { x − } ) = d O N S [ T u l ] ( D − ) . \begin{equation}
\mathcal U_{\mathsf{NS}}^{[T_{ul}]}
\left(
\mathcal O_{\mathsf{NS}}^{[T_{ul}]}(\mathcal D),
\{x^{-}\}
\right)
\overset{d}{=}
\mathcal O_{\mathsf{NS}}^{[T_{ul}]}(\mathcal D^{-}). \tag*{(72)}
\end{equation} U NS [ T u l ] ( O NS [ T u l ] ( D ) , { x − } ) = d O NS [ T u l ] ( D − ) . (72) Consequently,
U N S T u l → T ( O N S [ T u l ] ( D ) , { x − } ) = d O N S [ T ] ( D − ) . \begin{equation}
\mathcal U_{\mathsf{NS}}^{T_{ul}\to T}
\left(
\mathcal O_{\mathsf{NS}}^{[T_{ul}]}(\mathcal D),
\{x^{-}\}
\right)
\overset{d}{=}
\mathcal O_{\mathsf{NS}}^{[T]}(\mathcal D^{-}). \tag*{(73)}
\end{equation} U NS T u l → T ( O NS [ T u l ] ( D ) , { x − } ) = d O NS [ T ] ( 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 \sigma_\rho>0 σ ρ > 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 mini-batch, 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 ⋆ ) (r^\star,t^\star) ( r ⋆ , t ⋆ ) , the reflected coefficients give the correct retained-data update at that position. From N e x t ( r ⋆ , t ⋆ ) \mathsf{Next}(r^\star,t^\star) 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 t^\star=E t ⋆ = E , the server first recomputes the round aggregation from the corrected local endpoints, exactly as specified in Algorithm algo:FedZOULNS .
Applying this argument successively over the positions up to T u l T_{ul} T u l shows that the state returned after the deletion follows the same transition kernels, in the same order, as a fresh FedZOO-NS execution on D − \mathcal D^{-} D − . Hence it has law O N S [ T u l ] ( D − ) \mathcal O_{\mathsf{NS}}^{[T_{ul}]}(\mathcal D^{-}) O NS [ T u l ] ( D − ) . Continuing with the same retained-data kernels proves Eq. (73) . Finally, averaging over the independently generated seed pool removes the conditioning. ◻
Define
ϑ ρ = 2 Φ ( 2 C / ( b q ) 2 σ ρ ) − 1. \begin{equation}
\vartheta_\rho
=
2\Phi\left(
\frac{2C/(b\sqrt q)}{2\sigma_\rho}
\right)-1. \tag*{(74)}
\end{equation} ϑ ρ = 2Φ ( 2 σ ρ 2 C / ( b q ) ) − 1. (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.
Proposition 1 (Probability of replay). Let R e p l a y N S \mathsf{Replay}_{\mathsf{NS}} Replay NS denote the event that at least one verification test rejects. A rejection at T u l T_{ul} T u l 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 T u l T_{ul} T u l ,
P ( R e p l a y N S ) ≤ Γ N S ( T u l , c − ) : = min { 1 , T u l m b M n c − ϑ ρ } ≤ min { 1 , 2 C T u l m 2 π M n c − q σ ρ } . \begin{align}
\mathbb P(\mathsf{Replay}_{\mathsf{NS}})
&\le
\Gamma_{\mathsf{NS}}(T_{ul},c^{-})
\notag\\
&:=
\min\left\{
1,
\frac{T_{ul}mb}{Mn_{c^{-}}}\vartheta_\rho
\right\} \tag*{(75)}
\\
&\le
\min\left\{
1,
\frac{2CT_{ul}m}
{\sqrt{2\pi}Mn_{c^{-}}\sqrt q\,\sigma_\rho}
\right\}. \tag*{(76)}
\end{align} P ( Replay NS ) ≤ Γ NS ( T u l , c − ) := min { 1 , M n c − T u l mb ϑ ρ } ≤ min { 1 , 2 π M n c − q σ ρ 2 C T u l m } . (75) (76) Under (65) ,
P ( R e p l a y N S ) ≤ min { 1 , ρ T u l 2 π T m M } ≤ min { 1 , ρ T m 2 π M } . \begin{align}
\mathbb P(\mathsf{Replay}_{\mathsf{NS}})
&\le
\min\left\{
1,
\frac{\rho T_{ul}}{\sqrt{2\pi T}}
\sqrt{\frac mM}
\right\}
\notag\\
&\le
\min\left\{
1,
\rho\sqrt{\frac{Tm}{2\pi M}}
\right\}. \tag*{(77)}
\end{align} P ( Replay NS ) ≤ min { 1 , 2 π T ρ T u l M m } ≤ min { 1 , ρ 2 π M T 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 / n c − ) ϑ ρ (b/n_{c^{-}})\vartheta_\rho ( b / n c − ) ϑ ρ , 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 / n c − ) ϑ ρ (m/M)(b/n_{c^{-}})\vartheta_\rho ( m / M ) ( b / n c − ) ϑ ρ . Summing over the first T u l T_{ul} T u l 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 ≤ 2 C / ( b q ) \|\boldsymbol h-\boldsymbol h'\|_2\le 2C/(b\sqrt q) ∥ h − h ′ ∥ 2 ≤ 2 C / ( b q ) prove (76) . Substituting (65) , using n c − ≥ n ‾ n_{c^{-}}\ge\underline n n c − ≥ n , and then T u l ≤ T T_{ul}\le T T u l ≤ T gives (77) . ◻
Corollary 3 (Sequential deletion requests for FedZOUL-NS). Consider the valid non-adaptive single-sample request stream in Eq. (46) . After every request j j j , the state returned at T u l ( j ) T_{ul}^{(j)} T u l ( j ) has law O N S [ T u l ( j ) ] ( D ( j + 1 ) ) \mathcal O_{\mathsf{NS}}^{[T_{ul}^{(j)}]}(\mathcal D^{(j+1)}) O NS [ T u l ( j ) ] ( D ( j + 1 ) ) . In Γ N S ( T u l ( j ) , c j − ) \Gamma_{\mathsf{NS}}(T_{ul}^{(j)},c_j^{-}) Γ NS ( T u l ( j ) , c j − ) , evaluate the affected client’s pre-request data size as n j = ∣ D c j − ( j ) ∣ n_j=|\mathcal D_{c_j^{-}}^{(j)}| n j = ∣ D c j − ( j ) ∣ . If N N S r e p N_{\mathsf{NS}}^{\mathrm{rep}} N NS rep counts requests for which the rejection test fails, including a rejection at the request endpoint, then
E [ N N S r e p ] ≤ ∑ j = 1 k Γ N S ( T u l ( j ) , c j − ) , P ( N N S r e p ≥ 1 ) ≤ min { 1 , ∑ j = 1 k Γ N S ( T u l ( j ) , c j − ) } . \begin{align}
\mathbb E[N_{\mathsf{NS}}^{\mathrm{rep}}]
&\le
\sum_{j=1}^{k}
\Gamma_{\mathsf{NS}}(T_{ul}^{(j)},c_j^{-}), \tag*{(78)}
\\
\mathbb P(N_{\mathsf{NS}}^{\mathrm{rep}}\ge1)
&\le
\min\left\{
1,
\sum_{j=1}^{k}
\Gamma_{\mathsf{NS}}(T_{ul}^{(j)},c_j^{-})
\right\}. \tag*{(79)}
\end{align} E [ N NS rep ] P ( N NS rep ≥ 1 ) ≤ j = 1 ∑ k Γ NS ( T u l ( j ) , c j − ) , ≤ min { 1 , j = 1 ∑ k Γ NS ( T u l ( j ) , c j − ) } . (78) (79) Under (47) and (65) , define
Γ ‾ N S = min { 1 , ρ T m 2 π M } . \begin{equation}
\overline\Gamma_{\mathsf{NS}}
=
\min\left\{
1,
\rho\sqrt{\frac{Tm}{2\pi M}}
\right\}. \tag*{(80)}
\end{equation} Γ NS = min { 1 , ρ 2 π M T m } . (80) Then the two bounds are at most k Γ ‾ N S k\overline\Gamma_{\mathsf{NS}} k Γ NS and min { 1 , k Γ ‾ N S } \min\{1,k\overline\Gamma_{\mathsf{NS}}\} 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 X j − X_j^{-} X j − and X j + X_j^{+} X j + denote the complete states immediately before and after processing request j j j , then
X j − = d O N S [ T u l ( j ) ] ( D ( j ) ) , X j + = d O N S [ T u l ( j ) ] ( D ( j + 1 ) ) . \begin{align}
X_j^{-}&\overset d=
\mathcal O_{\mathsf{NS}}^{[T_{ul}^{(j)}]}(\mathcal D^{(j)}),
\notag\\
X_j^{+}&\overset d=
\mathcal O_{\mathsf{NS}}^{[T_{ul}^{(j)}]}(\mathcal D^{(j+1)}). \tag*{(81)}
\end{align} X j − X j + = d O NS [ T u l ( j ) ] ( D ( j ) ) , = d O NS [ T u l ( j ) ] ( 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 I j I_j I j indicate the first-rejection event for request j j j . Proposition 1 , applied to the pre-request marginal, gives
E [ I j ] = P ( I j = 1 ) ≤ Γ N S ( T u l ( j ) , c j − ) . \mathbb E[I_j]=\mathbb P(I_j=1)
\le\Gamma_{\mathsf{NS}}(T_{ul}^{(j)},c_j^{-}). E [ I j ] = P ( I j = 1 ) ≤ Γ NS ( T u l ( j ) , 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) . ◻
It is useful to distinguish the final-model stability guarantee from the probability that training must be rerun. The former is bounded by ρ \rho ρ . The latter comes from the sequential coupling of local updates and is bounded by a quantity of order ρ T m / M \rho\sqrt{Tm/M} ρ T m / M , capped at one. The two need not coincide because FedZOUL-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 \vartheta_\rho\le1 ϑ ρ ≤ 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 FedZOUL-S, rerunning starts from the first position that used the deleted sample. For FedZOUL-NS, affected updates are first checked through the Gaussian coupling, and later training is rerun only if one of these checks rejects.
Unlearning Cost
We count loss evaluations, model reconstruction, and communication separately. A loss evaluation is one call to ℓ ( w ; x ) \ell(\boldsymbol w;x) ℓ ( w ; x ) for one sample. One scalar central difference therefore uses two evaluations, so rerunning one local position across all m m m participating clients uses 2 m b q 2mbq 2 mb q loss evaluations. Rerunning all T u l T_{ul} T u l executed local positions uses
Q f u l l ( T u l ) = 2 m b q T u l . \begin{equation}
Q_{\mathrm{full}}(T_{ul})=2mbqT_{ul}. \tag*{(82)}
\end{equation} Q full ( T u l ) = 2 mb q T u l . (82)
These are aggregate oracle counts. They do not include restoring models, looking up saved coefficients, drawing replacement samples, or transferring checkpoints.
For FedZOUL-NS, checking an affected position does not require recomputing all b q bq b q coefficients. Under the sample–seed correspondence, only the q q q pairs attached to the deleted sample can change. Let J J J denote these coordinates and write d = h ′ − h \boldsymbol d=\boldsymbol h'-\boldsymbol h d = h ′ − h . Then d \boldsymbol d d is supported on J J J , and for the saved noisy vector h ~ \widetilde{\boldsymbol h} h with m = ( h + h ′ ) / 2 \boldsymbol m=(\boldsymbol h+\boldsymbol h')/2 m = ( h + h ′ ) /2 ,
log q ( h ~ ) p ( h ~ ) = ⟨ h ~ J − m J , d J ⟩ σ ρ 2 . \begin{equation}
\log\frac{q(\widetilde{\boldsymbol h})}{p(\widetilde{\boldsymbol h})}
=
\frac{\langle
\widetilde{\boldsymbol h}_{J}-\boldsymbol m_{J},
\boldsymbol d_{J}\rangle}{\sigma_\rho^2}. \tag*{(83)}
\end{equation} log p ( h ) q ( h ) = σ ρ 2 ⟨ h J − m J , d J ⟩ . (83)
The reflection direction is supported on the same coordinates. Hence the acceptance test and, when needed, the reflection use only the q q q original and q q q replacement central differences, for at most 4 q 4q 4 q loss evaluations and O ( q ) O(q) 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 4 b q 4bq 4 b q evaluations instead, but the two implementations are algebraically equivalent.
Let τ S ⋆ \tau_{\mathsf S}^{\star} τ S ⋆ be the first executed position at which the deleted sample is used, with τ S ⋆ = ∞ \tau_{\mathsf S}^{\star}=\infty τ S ⋆ = ∞ if no such position exists. Define
L S = ( T u l − τ S ⋆ + 1 ) 1 { τ S ⋆ ≤ T u l } . \begin{equation}
L_{\mathsf S}
=
(T_{ul}-\tau_{\mathsf S}^{\star}+1)
\mathbf1\{\tau_{\mathsf S}^{\star}\le T_{ul}\}. \tag*{(84)}
\end{equation} L S = ( T u l − τ S ⋆ + 1 ) 1 { τ S ⋆ ≤ T u l } . (84)
For FedZOUL-NS, let τ N S ⋆ \tau_{\mathsf{NS}}^{\star} τ NS ⋆ be the first rejected affected position and set
L N S = ( T u l − τ N S ⋆ ) 1 { τ N S ⋆ ≤ T u l } , \begin{equation}
L_{\mathsf{NS}}
=
(T_{ul}-\tau_{\mathsf{NS}}^{\star})
\mathbf1\{\tau_{\mathsf{NS}}^{\star}\le T_{ul}\}, \tag*{(85)}
\end{equation} L NS = ( T u l − τ NS ⋆ ) 1 { τ NS ⋆ ≤ T u l } , (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 N v e r N_{\mathrm{ver}} N ver 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 ≤ T u l ≤ T 1\le T_{ul}\le T 1 ≤ T u l ≤ T , using the sparse check above,
E [ L S ] ≤ ∑ u = 1 T u l Λ S ( u , c − ) ≤ min { T u l , m b T u l M n c − ( T u l + 1 ) 2 } , \begin{align}
\mathbb E[L_{\mathsf S}]
&\le
\sum_{u=1}^{T_{ul}}
\Lambda_{\mathsf S}(u,c^{-})
\notag\\
&\le
\min\left\{
T_{ul},
\frac{\frac{mbT_{ul}}{Mn_{c^{-}}}(T_{ul}+1)}{2}
\right\}, \tag*{(86)}
\end{align} E [ L S ] ≤ u = 1 ∑ T u l Λ S ( u , c − ) ≤ min { T u l , 2 M n c − mb T u l ( T u l + 1 ) } , (86) and the aggregate loss-evaluation cost of FedZOUL-S satisfies
E [ Q S ] = 2 m b q E [ L S ] ≤ Q f u l l ( T u l ) Λ S ( T u l , c − ) . \begin{align}
\mathbb E[Q_{\mathsf S}]
&=
2mbq\,\mathbb E[L_{\mathsf S}]
\notag\\
&\le
Q_{\mathrm{full}}(T_{ul})
\Lambda_{\mathsf S}(T_{ul},c^{-}). \tag*{(87)}
\end{align} E [ Q S ] = 2 mb q E [ L S ] ≤ Q full ( T u l ) Λ S ( T u l , c − ) . (87) Under (42) ,
E [ Q S ] ≤ ρ Q f u l l ( T u l ) . \begin{equation}
\mathbb E[Q_{\mathsf S}]
\le
\rho Q_{\mathrm{full}}(T_{ul}). \tag*{(88)}
\end{equation} E [ Q S ] ≤ ρ Q full ( T u l ) . (88) For FedZOUL-NS,
E [ N v e r ] ≤ m b T u l M n c − , E [ L N S ] ≤ ∑ u = 1 T u l − 1 Γ N S ( u , c − ) ≤ min { T u l − 1 , m b ϑ ρ M n c − T u l ( T u l − 1 ) 2 } . \begin{align}
\mathbb E[N_{\mathrm{ver}}]
&\le
\frac{mbT_{ul}}{Mn_{c^{-}}}, \tag*{(89)}
\\
\mathbb E[L_{\mathsf{NS}}]
&\le
\sum_{u=1}^{T_{ul}-1}
\Gamma_{\mathsf{NS}}(u,c^{-})
\notag\\
&\le
\min\left\{
T_{ul}-1,
\frac{\frac{mb\vartheta_\rho}{Mn_{c^{-}}}T_{ul}(T_{ul}-1)}{2}
\right\}. \tag*{(90)}
\end{align} E [ N ver ] E [ L NS ] ≤ M n c − mb T u l , ≤ u = 1 ∑ T u l − 1 Γ NS ( u , c − ) ≤ min ⎩ ⎨ ⎧ T u l − 1 , 2 M n c − mb ϑ ρ T u l ( T u l − 1 ) ⎭ ⎬ ⎫ . (89) (90) Its aggregate loss-evaluation cost satisfies
E [ Q N S ] ≤ 4 q m b T u l M n c − + 2 m b q ∑ u = 1 T u l − 1 Γ N S ( u , c − ) ≤ Q f u l l ( T u l ) [ 2 M n c − + Γ N S ( T u l , c − ) ] . \begin{align}
\mathbb E[Q_{\mathsf{NS}}]
&\le
4q\,\frac{mbT_{ul}}{Mn_{c^{-}}}
+
2mbq
\sum_{u=1}^{T_{ul}-1}
\Gamma_{\mathsf{NS}}(u,c^{-}) \tag*{(91)}
\\
&\le
Q_{\mathrm{full}}(T_{ul})
\left[
\frac{2}{Mn_{c^{-}}}
+
\Gamma_{\mathsf{NS}}(T_{ul},c^{-})
\right]. \tag*{(92)}
\end{align} E [ Q NS ] ≤ 4 q M n c − mb T u l + 2 mb q u = 1 ∑ T u l − 1 Γ NS ( u , c − ) ≤ Q full ( T u l ) [ M n c − 2 + Γ NS ( T u l , c − ) ] . (91) (92) Under (65) ,
E [ Q N S ] Q f u l l ( T u l ) ≤ 2 M n c − + min { 1 , ρ T u l 2 π T m M } . \begin{equation}
\frac{\mathbb E[Q_{\mathsf{NS}}]}
{Q_{\mathrm{full}}(T_{ul})}
\le
\frac{2}{Mn_{c^{-}}}
+
\min\left\{
1,
\frac{\rho T_{ul}}{\sqrt{2\pi T}}
\sqrt{\frac mM}
\right\}. \tag*{(93)}
\end{equation} Q full ( T u l ) E [ Q NS ] ≤ M n c − 2 + min { 1 , 2 π T ρ T u l M m } . (93) Finally, when comparing one request under the same realized client and mini-batch sampling schedule,
L N S ≤ L S pathwise . \begin{equation}
L_{\mathsf{NS}}
\le
L_{\mathsf S}
\qquad\text{pathwise}. \tag*{(94)}
\end{equation} L NS ≤ L S pathwise . (94) This compares replay lengths, not total query counts or running times. For T u l = 0 T_{ul}=0 T u l = 0 , all query and replay counts are zero; the ratios above are used only for T u l > 0 T_{ul}>0 T u l > 0 .
Proof of Theorem 5 . For FedZOUL-S,
L S = ∑ u = 1 T u l 1 { τ S ⋆ ≤ u } . \begin{equation}
L_{\mathsf S}
=
\sum_{u=1}^{T_{ul}}
\mathbf1\{\tau_{\mathsf S}^{\star}\le u\}. \tag*{(95)}
\end{equation} L S = u = 1 ∑ T u l 1 { τ S ⋆ ≤ u } . (95) Equation (40) gives P ( τ S ⋆ ≤ u ) ≤ Λ S ( u , c − ) \mathbb P(\tau_{\mathsf S}^{\star}\le u)
\le\Lambda_{\mathsf S}(u,c^{-}) P ( τ S ⋆ ≤ u ) ≤ Λ S ( u , c − ) . Taking expectations proves (86) . Also, L S ≤ T u l 1 { R e p l a y S } L_{\mathsf S}\le T_{ul}\mathbf1\{\mathsf{Replay}_{\mathsf S}\} L S ≤ T u l 1 { Replay S } , which gives (87) and then (88) .
For FedZOUL-NS, verification occurs only when the target client is selected and the target sample appears in its mini-batch. The expected number of such hits is m b T u l M n c − \frac{mbT_{ul}}{Mn_{c^{-}}} M n c − mb T u l , and stopping after the first rejection can only reduce it. The sparse calculation above gives the verification cost and gives the pathwise accounting inequality
Q N S ≤ 4 q N v e r + 2 m b q L N S . \begin{equation}
Q_{\mathsf{NS}}
\le 4qN_{\mathrm{ver}}+2mbqL_{\mathsf{NS}}. \tag*{(96)}
\end{equation} Q NS ≤ 4 q N ver + 2 mb q L NS . (96) The reflected position requires no further loss evaluations. Moreover,
L N S = ∑ u = 1 T u l − 1 1 { τ N S ⋆ ≤ u } . \begin{equation}
L_{\mathsf{NS}}
=
\sum_{u=1}^{T_{ul}-1}
\mathbf1\{\tau_{\mathsf{NS}}^{\star}\le u\}. \tag*{(97)}
\end{equation} L NS = u = 1 ∑ T u l − 1 1 { τ NS ⋆ ≤ u } . (97) Proposition 1 gives P ( τ N S ⋆ ≤ u ) ≤ Γ N S ( u , c − ) \mathbb P(\tau_{\mathsf{NS}}^{\star}\le u)
\le\Gamma_{\mathsf{NS}}(u,c^{-}) P ( τ NS ⋆ ≤ u ) ≤ Γ NS ( u , c − ) . This proves (90) and the first query bound. Monotonicity of Γ N S \Gamma_{\mathsf{NS}} Γ 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 FedZOUL-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 ρ \rho ρ fraction of rerunning all executed positions. FedZOUL-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 , 2 E , … E,2E,\ldots E , 2 E , … . Hence the expected number of completed aggregations repeated by FedZOUL-S is at most
∑ r = 1 ⌊ T u l / E ⌋ Λ S ( r E , c − ) , \begin{equation}
\sum_{r=1}^{\lfloor T_{ul}/E\rfloor}
\Lambda_{\mathsf S}(rE,c^{-}), \tag*{(98)}
\end{equation} r = 1 ∑ ⌊ T u l / E ⌋ Λ S ( r E , c − ) , (98)
and for FedZOUL-NS it is at most
∑ r = 1 ⌊ T u l / E ⌋ Γ N S ( r E , c − ) . \begin{equation}
\sum_{r=1}^{\lfloor T_{ul}/E\rfloor}
\Gamma_{\mathsf{NS}}(rE,c^{-}). \tag*{(99)}
\end{equation} r = 1 ∑ ⌊ T u l / E ⌋ Γ NS ( r E , c − ) . (99)
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
∑ r = 1 ⌊ T u l / E ⌋ Λ S ( r E , c − ) + 1 { E ∤ T u l } Λ S ( T u l , c − ) \begin{align}
&\sum_{r=1}^{\lfloor T_{ul}/E\rfloor}
\Lambda_{\mathsf S}(rE,c^{-})
+\mathbf1\{E\nmid T_{ul}\}\Lambda_{\mathsf S}(T_{ul},c^{-}) \tag*{(100)}
\end{align} r = 1 ∑ ⌊ T u l / E ⌋ Λ S ( r E , c − ) + 1 { E ∤ T u l } Λ S ( T u l , c − ) (100)
for FedZOUL-S, and by
∑ r = 1 ⌊ T u l / E ⌋ Γ N S ( r E , c − ) + 1 { E ∤ T u l } Γ N S ( T u l , c − ) \begin{align}
&\sum_{r=1}^{\lfloor T_{ul}/E\rfloor}
\Gamma_{\mathsf{NS}}(rE,c^{-})
+\mathbf1\{E\nmid T_{ul}\}\Gamma_{\mathsf{NS}}(T_{ul},c^{-}) \tag*{(101)}
\end{align} r = 1 ∑ ⌊ T u l / E ⌋ Γ NS ( r E , c − ) + 1 { E ∤ T u l } Γ NS ( T u l , c − ) (101)
for FedZOUL-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 K 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 m m clients, every visited round block needs at most one K K K -scalar global-accumulator download per client, and every completed aggregation that is repeated needs at most one K K K -scalar endpoint upload per client. Therefore, the expected additional accumulator communication of FedZOUL-S is at most
m K [ 2 ∑ r = 1 ⌊ T u l / E ⌋ Λ S ( r E , c − ) + 1 { E ∤ T u l } Λ S ( T u l , c − ) ] . \begin{align}
&mK\left[
2\sum_{r=1}^{\lfloor T_{ul}/E\rfloor}
\Lambda_{\mathsf S}(rE,c^{-})
+\mathbf1\{E\nmid T_{ul}\}\Lambda_{\mathsf S}(T_{ul},c^{-})
\right]. \tag*{(102)}
\end{align} m K 2 r = 1 ∑ ⌊ T u l / E ⌋ Λ S ( r E , c − ) + 1 { E ∤ T u l } Λ S ( T u l , c − ) . (102)
For FedZOUL-NS, the corresponding bound is
m K [ 2 ∑ r = 1 ⌊ T u l / E ⌋ Γ N S ( r E , c − ) + 1 { E ∤ T u l } Γ N S ( T u l , c − ) ] + K m b T u l M n c − . \begin{align}
&mK\left[
2\sum_{r=1}^{\lfloor T_{ul}/E\rfloor}
\Gamma_{\mathsf{NS}}(rE,c^{-})
+\mathbf1\{E\nmid T_{ul}\}\Gamma_{\mathsf{NS}}(T_{ul},c^{-})
\right]
+K\frac{mbT_{ul}}{Mn_{c^{-}}}. \tag*{(103)}
\end{align} m K 2 r = 1 ∑ ⌊ T u l / E ⌋ Γ NS ( r E , c − ) + 1 { E ∤ T u l } Γ NS ( T u l , c − ) + K M n c − mb T u l . (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,
w c r , t − 1 = w 0 − η ∑ k = 1 K ( a k r − 1 + a c , k r , t − 1 ) z k , \begin{equation}
\boldsymbol w_c^{r,t-1}
=\boldsymbol w^0-\eta\sum_{k=1}^{K}
\bigl(a_k^{r-1}+a_{c,k}^{r,t-1}\bigr)\boldsymbol z_k, \tag*{(104)}
\end{equation} w c r , t − 1 = w 0 − η k = 1 ∑ K ( a k r − 1 + a c , k r , t − 1 ) z k , (104)
and the expected number of affected updates checked is at most m b T u l M n c − \frac{mbT_{ul}}{Mn_{c^{-}}} M n c − mb T u l . If a common downlink broadcast is counted once rather than once per recipient, the factors multiplying the completed-round sums become ( m + 1 ) K (m+1)K ( m + 1 ) K instead of 2 m K 2mK 2 m K , while the partial-round download contributes only K K 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.
Corollary 4 (Cost over a request stream). Consider the valid non-adaptive single-sample request stream in Eq. (46) . Let T u l ( j ) T_{ul}^{(j)} T u l ( j ) be the executed horizon when request j j j arrives and let n j n_j n j be the affected client’s data size immediately before that request. Then the cumulative expected loss-evaluation costs satisfy
E [ Q S 1 : k ] ≤ 2 m b q ∑ j = 1 k ∑ u = 1 T u l ( j ) min { 1 , u m b M n j } , E [ Q N S 1 : k ] ≤ 4 q ∑ j = 1 k m b T u l ( j ) M n j + 2 m b q ∑ j = 1 k ∑ u = 1 T u l ( j ) − 1 min { 1 , u m b ϑ ρ M n j } . \begin{align}
\mathbb E[Q_{\mathsf S}^{1:k}]
&\le
2mbq\sum_{j=1}^{k}\sum_{u=1}^{T_{ul}^{(j)}}
\min\left\{1,\frac{umb}{Mn_j}\right\}, \tag*{(105)}
\\
\mathbb E[Q_{\mathsf{NS}}^{1:k}]
&\le
4q\sum_{j=1}^{k}
\frac{mbT_{ul}^{(j)}}{Mn_j}
\notag\\
&\quad+
2mbq\sum_{j=1}^{k}\sum_{u=1}^{T_{ul}^{(j)}-1}
\min\left\{1,\frac{umb\vartheta_\rho}{Mn_j}\right\}. \tag*{(106)}
\end{align} E [ Q S 1 : k ] E [ Q NS 1 : k ] ≤ 2 mb q j = 1 ∑ k u = 1 ∑ T u l ( j ) min { 1 , M n j u mb } , ≤ 4 q j = 1 ∑ k M n j mb T u l ( j ) + 2 mb q j = 1 ∑ k u = 1 ∑ T u l ( j ) − 1 min { 1 , M n j u mb ϑ ρ } . (105) (106) Empty sums are interpreted as zero.
With separate downlinks, the cumulative expected accumulator communication of FedZOUL-S is at most
m K ∑ j = 1 k [ 2 ∑ r = 1 ⌊ T u l ( j ) / E ⌋ min { 1 , r E m b M n j } + 1 { E ∤ T u l ( j ) } min { 1 , T u l ( j ) m b M n j } ] , \begin{align}
&mK\sum_{j=1}^{k}
\left[
2\sum_{r=1}^{\lfloor T_{ul}^{(j)}/E\rfloor}
\min\left\{1,\frac{rEmb}{Mn_j}\right\}
\right.
\notag\\[-0.2em]
&\hspace{7em}\left.
+\mathbf1\{E\nmid T_{ul}^{(j)}\}
\min\left\{1,\frac{T_{ul}^{(j)}mb}{Mn_j}\right\}
\right], \tag*{(107)}
\end{align} m K j = 1 ∑ k 2 r = 1 ∑ ⌊ T u l ( j ) / E ⌋ min { 1 , M n j r E mb } + 1 { E ∤ T u l ( j ) } min { 1 , M n j T u l ( j ) mb } ] , (107) while for FedZOUL-NS it is at most
m K ∑ j = 1 k [ 2 ∑ r = 1 ⌊ T u l ( j ) / E ⌋ min { 1 , r E m b ϑ ρ M n j } + 1 { E ∤ T u l ( j ) } min { 1 , T u l ( j ) m b ϑ ρ M n j } ] + K ∑ j = 1 k m b T u l ( j ) M n j . \begin{align}
&mK\sum_{j=1}^{k}
\left[
2\sum_{r=1}^{\lfloor T_{ul}^{(j)}/E\rfloor}
\min\left\{1,\frac{rEmb\vartheta_\rho}{Mn_j}\right\}
\right.
\notag\\[-0.2em]
&\hspace{7em}\left.
+\mathbf1\{E\nmid T_{ul}^{(j)}\}
\min\left\{1,\frac{T_{ul}^{(j)}mb\vartheta_\rho}{Mn_j}\right\}
\right]
\notag\\
&\qquad+
K\sum_{j=1}^{k}\frac{mbT_{ul}^{(j)}}{Mn_j}. \tag*{(108)}
\end{align} m K j = 1 ∑ k 2 r = 1 ∑ ⌊ T u l ( j ) / E ⌋ min { 1 , M n j r E mb ϑ ρ } + 1 { E ∤ T u l ( j ) } min { 1 , M n j T u l ( j ) mb ϑ ρ } ] + K j = 1 ∑ k M n j mb T u l ( j ) . (108) The corresponding broadcast bounds replace the factor 2 m K 2mK 2 m K on each completed-round sum by ( m + 1 ) K (m+1)K ( m + 1 ) K and the factor m K mK m K on each partial-round term by K K 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 above therefore apply to every request with its current horizon T u l ( j ) T_{ul}^{(j)} T u l ( j ) and affected-client size n j n_j n j . 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 K K shared directions costs O ( K d ) O(Kd) O ( K d ) operations in a direct implementation. Rerunning one local step costs O ( b q d + K ) O(bqd+K) O ( b q d + K ) beyond the loss evaluations, a sparse NS check costs O ( q d + q ) O(qd+q) O ( q d + q ) , and one server aggregation costs O ( m K ) O(mK) O ( m K ) . 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 ( b T u l ) O(bT_{ul}) O ( b T u l ) 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 2 b q 2bq 2 b q evaluations per rerun S step and 4 q 4q 4 q evaluations per checked NS update plus 2 b q 2bq 2 b q evaluations per rerun NS step. Model reconstruction, saved-state access, communication, and synchronization remain additional costs. In particular, the TV parameter ρ \rho ρ directly bounds the expected S query fraction under the chosen subsampling level, whereas for NS the final-model 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.
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 ] ∈ R d × K \begin{equation}
\boldsymbol Z
=
[\boldsymbol z_1,\ldots,\boldsymbol z_K]
\in\mathbb R^{d\times K} \tag*{(109)}
\end{equation} Z = [ z 1 , … , z K ] ∈ R d × K (109)
be the perturbation matrix generated by the shared seed pool S = { s 1 , … , s K } \mathbb S=\{s_1,\ldots,s_K\} S = { s 1 , … , s K } , where z k = P e r t u r b ( s k ) \boldsymbol z_k=\mathsf{Perturb}(s_k) z k = Perturb ( s k ) . Define the normalized seed matrix
A = 1 K Z . \begin{equation}
\boldsymbol A
=
\frac{1}{\sqrt K}\boldsymbol Z. \tag*{(110)}
\end{equation} A = K 1 Z . (110)
For the global and local accumulators in § 4.1 , define
u r = − η K a r , u c r , t = u r − 1 − η K a c r , t . \begin{align}
\boldsymbol u^r
&=
-\eta\sqrt K\,\boldsymbol a^r, \tag*{(111)}
\\
\boldsymbol u_c^{r,t}
&=
\boldsymbol u^{r-1}
-\eta\sqrt K\,\boldsymbol a_c^{r,t}. \tag*{(112)}
\end{align} u r u c r , t = − η K a r , = u r − 1 − η K a c r , t . (111) (112)
The reconstructed models are therefore
w r = w 0 + A u r , w c r , t = w 0 + A u c r , t . \begin{align}
\boldsymbol w^r
&=
\boldsymbol w^0+\boldsymbol A\boldsymbol u^r,
\notag\\
\boldsymbol w_c^{r,t}
&=
\boldsymbol w^0+\boldsymbol A\boldsymbol u_c^{r,t}. \tag*{(113)}
\end{align} w r w c r , t = w 0 + A u r , = w 0 + A u c r , t . (113)
Thus, every model lies in W Z = w 0 + range ( Z ) \mathcal W_{\boldsymbol Z}=\boldsymbol w^0+
\operatorname{range}(\boldsymbol Z) W Z = w 0 + range ( Z ) .
In these coordinates, the local and global objectives are simply
F Z , c ( u ) = f c ( w 0 + A u ) , F Z ( u ) = 1 M ∑ c = 1 M F Z , c ( u ) = f ( w 0 + A u ) . \begin{align}
F_{\boldsymbol Z,c}(\boldsymbol u)
&=
f_c(\boldsymbol w^0+\boldsymbol A\boldsymbol u),
\notag\\
F_{\boldsymbol Z}(\boldsymbol u)
&=
\frac1M\sum_{c=1}^{M}F_{\boldsymbol Z,c}(\boldsymbol u)
=
f(\boldsymbol w^0+\boldsymbol A\boldsymbol u). \tag*{(114)}
\end{align} F Z , c ( u ) F Z ( u ) = f c ( w 0 + A u ) , = M 1 c = 1 ∑ M F Z , c ( u ) = f ( w 0 + A u ) . (114)
Equation (114) is exactly the original federated objective restricted to the affine space W Z \mathcal W_{\boldsymbol Z} W Z . In particular,
inf u ∈ R K F Z ( u ) = inf w ∈ W Z f ( w ) . \begin{equation}
\inf_{\boldsymbol u\in\mathbb R^K}
F_{\boldsymbol Z}(\boldsymbol u)
=
\inf_{\boldsymbol w\in\mathcal W_{\boldsymbol Z}}
f(\boldsymbol w). \tag*{(115)}
\end{equation} u ∈ R K inf F Z ( u ) = w ∈ W Z inf f ( w ) . (115)
This fixed random-subspace interpretation is consistent with the finite-seed representation used by FedKSeed [1 ] .
By the chain rule,
∇ F Z , c ( u ) = A ⊤ ∇ f c ( w 0 + A u ) , ∇ F Z ( u ) = A ⊤ ∇ f ( w 0 + A u ) . \begin{align}
\nabla F_{\boldsymbol Z,c}(\boldsymbol u)
&=
\boldsymbol A^{\top}
\nabla f_c(\boldsymbol w^0+\boldsymbol A\boldsymbol u),
\notag\\
\nabla F_{\boldsymbol Z}(\boldsymbol u)
&=
\boldsymbol A^{\top}
\nabla f(\boldsymbol w^0+\boldsymbol A\boldsymbol u). \tag*{(116)}
\end{align} ∇ F Z , c ( u ) ∇ F Z ( u ) = A ⊤ ∇ f c ( w 0 + A u ) , = A ⊤ ∇ f ( w 0 + A u ) . (116)
If every f c f_c f c is L L L -smooth in model space, then every F Z , c F_{\boldsymbol Z,c} F Z , c is L Z L_{\boldsymbol Z} L Z -smooth in parameter space, where
L Z = L ∥ A ∥ o p 2 = L K ∥ Z ∥ o p 2 . \begin{equation}
L_{\boldsymbol Z}
=
L\|\boldsymbol A\|_{\mathrm{op}}^2
=
\frac{L}{K}\|\boldsymbol Z\|_{\mathrm{op}}^2. \tag*{(117)}
\end{equation} L Z = L ∥ A ∥ op 2 = K L ∥ Z ∥ op 2 . (117)
The gradient of the restricted objective has a direct full-space interpretation. At w = w 0 + A u \boldsymbol w=\boldsymbol w^0+\boldsymbol A\boldsymbol u w = w 0 + A u ,
∥ ∇ F Z ( u ) ∥ 2 = 1 K ∥ Z ⊤ ∇ f ( w ) ∥ 2 . \begin{equation}
\|\nabla F_{\boldsymbol Z}(\boldsymbol u)\|^2
=
\frac1K
\|\boldsymbol Z^{\top}\nabla f(\boldsymbol w)\|^2. \tag*{(118)}
\end{equation} ∥∇ F Z ( u ) ∥ 2 = K 1 ∥ Z ⊤ ∇ f ( w ) ∥ 2 . (118)
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 ∈ D c x\in\mathcal D_c x ∈ D c and k ∈ [ K ] k\in[K] k ∈ [ K ] , define the fixed-seed central difference
d μ , k ( u ; x ) = 1 2 μ [ ℓ ( w 0 + A u + μ z k ; x ) − ℓ ( w 0 + A u − μ z k ; x ) ] . \begin{equation}
\begin{aligned}
d_{\mu,k}(\boldsymbol u;x)
={}&\frac1{2\mu}\bigl[
\ell(\boldsymbol w^0+\boldsymbol A\boldsymbol u+\mu\boldsymbol z_k;x)
\\[-1mm]
&\qquad-
\ell(\boldsymbol w^0+\boldsymbol A\boldsymbol u-\mu\boldsymbol z_k;x)
\bigr].
\end{aligned} \tag*{(119)}
\end{equation} d μ , k ( u ; x ) = 2 μ 1 [ ℓ ( w 0 + A u + μ z k ; x ) − ℓ ( w 0 + A u − μ z k ; x ) ] . (119)
Because A e k = z k / K \boldsymbol A\boldsymbol e_k=\boldsymbol z_k/\sqrt K A e k = z k / K , a query along z k \boldsymbol z_k z k is exactly a coordinatewise central difference of the parameterized original loss, with coordinate step μ K \mu\sqrt K μ K .
Let
[ d μ ( u ; x ) ] k = d μ , k ( u ; x ) , d μ , c ( u ) = 1 n c ∑ x ∈ D c d μ ( u ; x ) . \begin{align}
[\boldsymbol d_{\mu}(\boldsymbol u;x)]_k
&=
d_{\mu,k}(\boldsymbol u;x),
\notag\\
\boldsymbol d_{\mu,c}(\boldsymbol u)
&=
\frac1{n_c}
\sum_{x\in\mathcal D_c}
\boldsymbol d_{\mu}(\boldsymbol u;x). \tag*{(120)}
\end{align} [ d μ ( u ; x ) ] k d μ , c ( u ) = d μ , k ( u ; x ) , = n c 1 x ∈ D c ∑ d μ ( u ; x ) . (120)
For FedZOO-NS, define the clipped counterparts by
[ d μ C ( u ; x ) ] k = clip C ( d μ , k ( u ; x ) ) , d μ , c C ( u ) = 1 n c ∑ x ∈ D c d μ C ( u ; x ) . \begin{align}
[\boldsymbol d_{\mu}^{C}(\boldsymbol u;x)]_k
&=
\operatorname{clip}_{C}
(d_{\mu,k}(\boldsymbol u;x)),
\notag\\
\boldsymbol d_{\mu,c}^{C}(\boldsymbol u)
&=
\frac1{n_c}
\sum_{x\in\mathcal D_c}
\boldsymbol d_{\mu}^{C}(\boldsymbol u;x). \tag*{(121)}
\end{align} [ d μ C ( u ; x ) ] k d μ , c C ( u ) = clip C ( d μ , k ( u ; x )) , = n c 1 x ∈ D c ∑ d μ C ( u ; x ) . (121)
The accumulator update already gives the corresponding step in these coordinates. If Δ a c r , t = a c r , t − a c r , t − 1 \Delta\boldsymbol a_c^{r,t}=\boldsymbol a_c^{r,t}-\boldsymbol a_c^{r,t-1} Δ a c r , t = a c r , t − a c r , t − 1 , then
u c r , t = u c r , t − 1 − η K Δ a c r , t . \begin{equation}
\boldsymbol u_c^{r,t}
=
\boldsymbol u_c^{r,t-1}
-
\eta\sqrt K\,\Delta\boldsymbol a_c^{r,t}. \tag*{(122)}
\end{equation} u c r , t = u c r , t − 1 − η K Δ a c r , t . (122)
For FedZOO-S, uniform mini-batch and seed sampling therefore gives
E [ K Δ a c r , t | F r , t − 1 , c , Z ] = 1 K d μ , c ( u c r , t − 1 ) , \begin{equation}
\mathbb E\!\left[
\sqrt K\,\Delta\boldsymbol a_c^{r,t}
\,\middle|\,\mathcal F_{r,t-1},c,\boldsymbol Z
\right]
=
\frac1{\sqrt K}
\boldsymbol d_{\mu,c}(\boldsymbol u_c^{r,t-1}), \tag*{(123)}
\end{equation} E [ K Δ a c r , t F r , t − 1 , c , Z ] = K 1 d μ , c ( u c r , t − 1 ) , (123)
where F r , t − 1 \mathcal F_{r,t-1} F r , t − 1 contains the fixed seed pool, the current client set, and everything revealed before this local step. For FedZOO-NS, clipping changes the mean to
E [ K Δ a c r , t | F r , t − 1 , c , Z ] = 1 K d μ , c C ( u c r , t − 1 ) . \begin{equation}
\mathbb E\!\left[
\sqrt K\,\Delta\boldsymbol a_c^{r,t}
\,\middle|\,\mathcal F_{r,t-1},c,\boldsymbol Z
\right]
=
\frac1{\sqrt K}
\boldsymbol d_{\mu,c}^{C}(\boldsymbol u_c^{r,t-1}). \tag*{(124)}
\end{equation} E [ K Δ a c r , t F r , t − 1 , c , Z ] = K 1 d μ , c C ( u c r , t − 1 ) . (124)
The added scalar Gaussian noises are independent and mean zero. After mapping them to seed coordinates, their contribution to the conditional second moment is K b q σ ρ 2 Kbq\sigma_\rho^2 K b q σ ρ 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
b μ , c ( u ) = 1 K d μ , c ( u ) − ∇ F Z , c ( u ) , b C , c ( u ) = 1 K ( d μ , c C ( u ) − d μ , c ( u ) ) . \begin{align}
\boldsymbol b_{\mu,c}(\boldsymbol u)
&=
\frac1{\sqrt K}
\boldsymbol d_{\mu,c}(\boldsymbol u)
-
\nabla F_{\boldsymbol Z,c}(\boldsymbol u), \tag*{(125)}
\\
\boldsymbol b_{C,c}(\boldsymbol u)
&=
\frac1{\sqrt K}
(\boldsymbol d_{\mu,c}^{C}(\boldsymbol u)
-
\boldsymbol d_{\mu,c}(\boldsymbol u)). \tag*{(126)}
\end{align} b μ , c ( u ) b C , c ( u ) = K 1 d μ , c ( u ) − ∇ F Z , c ( u ) , = K 1 ( d μ , c C ( u ) − d μ , c ( u )) . (125) (126)
If every sample loss is L L L -smooth, then
∥ b μ , c ( u ) ∥ 2 ≤ β μ , Z 2 , β μ , Z 2 = L 2 μ 2 4 K ∑ k = 1 K ∥ z k ∥ 4 . \begin{equation}
\|\boldsymbol b_{\mu,c}(\boldsymbol u)\|^2
\le
\beta_{\mu,\boldsymbol Z}^2,
\qquad
\beta_{\mu,\boldsymbol Z}^2
=
\frac{L^2\mu^2}{4K}
\sum_{k=1}^{K}\|\boldsymbol z_k\|^4. \tag*{(127)}
\end{equation} ∥ b μ , c ( u ) ∥ 2 ≤ β μ , Z 2 , β μ , Z 2 = 4 K L 2 μ 2 k = 1 ∑ K ∥ z k ∥ 4 . (127)
Indeed, the error of the k k k th central difference is at most L μ ∥ z k ∥ 2 / 2 L\mu\|\boldsymbol z_k\|^2/2 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.
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 \boldsymbol Z 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 FedZOO-S step starts from u \boldsymbol u u , then
E ∥ K Δ a c r , t − 1 K d μ , c ( u ) ∥ 2 = K − q b q K 1 n c ∑ x ∈ D c ∥ d μ ( u ; x ) ∥ 2 + n c − b b ( n c − 1 ) K 1 n c ∑ x ∈ D c ∥ d μ ( u ; x ) − d μ , c ( u ) ∥ 2 . \begin{align}
&\mathbb E
\left\|
\sqrt K\,\Delta\boldsymbol a_c^{r,t}
-
\frac1{\sqrt K}\boldsymbol d_{\mu,c}(\boldsymbol u)
\right\|^2
\notag\\
&\quad=
\frac{K-q}{bqK}
\frac1{n_c}
\sum_{x\in\mathcal D_c}
\|\boldsymbol d_{\mu}(\boldsymbol u;x)\|^2
\notag\\
&\qquad+
\frac{n_c-b}{b(n_c-1)K}
\frac1{n_c}
\sum_{x\in\mathcal D_c}
\|\boldsymbol d_{\mu}(\boldsymbol u;x)
-
\boldsymbol d_{\mu,c}(\boldsymbol u)\|^2. \tag*{(128)}
\end{align} E K Δ a c r , t − K 1 d μ , c ( u ) 2 = b q K K − q n c 1 x ∈ D c ∑ ∥ d μ ( u ; x ) ∥ 2 + b ( n c − 1 ) K n c − b n c 1 x ∈ D c ∑ ∥ d μ ( u ; x ) − d μ , c ( u ) ∥ 2 . (128)
The second term is zero when b = n c b=n_c b = n c , with the ratio interpreted as zero when n c = b = 1 n_c=b=1 n c = b = 1 . For FedZOO-NS, the same calculation applied before the Gaussian perturbation gives
E ∥ K Δ a c , c l i p r , t − 1 K d μ , c C ( u ) ∥ 2 ≤ C 2 b ( K − q q + n c − b n c − 1 ) . \begin{align}
&\mathbb E
\left\|
\sqrt K\,\Delta\boldsymbol a_{c,\mathrm{clip}}^{r,t}
-
\frac1{\sqrt K}\boldsymbol d_{\mu,c}^{C}(\boldsymbol u)
\right\|^2
\notag\\
&\quad\le
\frac{C^2}{b}
\left(
\frac{K-q}{q}
+
\frac{n_c-b}{n_c-1}
\right). \tag*{(129)}
\end{align} E K Δ a c , clip r , t − K 1 d μ , c C ( u ) 2 ≤ b C 2 ( q K − q + n c − 1 n c − b ) . (129)
Here Δ a c , c l i p r , t \Delta\boldsymbol a_{c,\mathrm{clip}}^{r,t} Δ a c , clip r , t denotes only the clipped finite-difference part of the accumulator increment at that step. Adding the independent Gaussian coefficients contributes another K b q σ ρ 2 Kbq\sigma_\rho^2 K b q σ ρ 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 \boldsymbol Z Z , the following hold for the learner A ∈ { S , N S } \mathsf A\in\{\mathsf S,\mathsf{NS}\} A ∈ { S , NS } .
(i) Every sample loss is L L L -smooth, and the original federated objective is lower bounded:
f ( w ) ≥ f ⋆ > − ∞ , w ∈ R d . \begin{equation}
f(\boldsymbol w)
\ge
f^\star> -\infty,
\qquad
\boldsymbol w\in\mathbb R^d. \tag*{(130)}
\end{equation} f ( w ) ≥ f ⋆ > − ∞ , w ∈ R d . (130) (ii) Client gradients in the fixed seed coordinates have bounded heterogeneity:
1 M ∑ c = 1 M ∥ ∇ F Z , c ( u ) − ∇ F Z ( u ) ∥ 2 ≤ ζ Z 2 , u ∈ R K . \begin{equation}
\frac1M
\sum_{c=1}^{M}
\|\nabla F_{\boldsymbol Z,c}(\boldsymbol u)
-
\nabla F_{\boldsymbol Z}(\boldsymbol u)\|^2
\le
\zeta_{\boldsymbol Z}^2,
\qquad
\boldsymbol u\in\mathbb R^K. \tag*{(131)}
\end{equation} M 1 c = 1 ∑ M ∥∇ F Z , c ( u ) − ∇ F Z ( u ) ∥ 2 ≤ ζ Z 2 , u ∈ R K . (131) (iii) When one local step starts from u \boldsymbol u u , let Δ a A , c ( u ) \Delta\boldsymbol a_{\mathsf A,c}(\boldsymbol u) Δ a A , c ( u ) be the random accumulator increment produced by that step. There exist finite constants β A , ν A , G A \beta_{\mathsf A},\nu_{\mathsf A},G_{\mathsf A} β A , ν A , G A such that, uniformly over clients and starting points,
The bounds above also give explicit choices for these constants. For FedZOO-S, the only systematic bias is the central-difference error, so
β S 2 ≤ β μ , Z 2 . \begin{equation}
\beta_{\mathsf S}^2
\le
\beta_{\mu,\boldsymbol Z}^2. \tag*{(133)}
\end{equation} β S 2 ≤ β μ , Z 2 . (133)
For FedZOO-NS, clipping adds another bias, and one may take
β N S 2 ≤ 2 β μ , Z 2 + 2 K sup c , u ∥ d μ , c C ( u ) − d μ , c ( u ) ∥ 2 . \begin{equation}
\beta_{\mathsf{NS}}^2
\le
2\beta_{\mu,\boldsymbol Z}^2
+
\frac{2}{K}
\sup_{c,\boldsymbol u}
\|\boldsymbol d_{\mu,c}^{C}(\boldsymbol u)
-
\boldsymbol d_{\mu,c}(\boldsymbol u)\|^2. \tag*{(134)}
\end{equation} β NS 2 ≤ 2 β μ , Z 2 + K 2 c , u sup ∥ d μ , c C ( u ) − d μ , c ( u ) ∥ 2 . (134)
Likewise, ν S 2 \nu_{\mathsf S}^2 ν S 2 can be chosen as the supremum of the right-hand side of Eq. (128) , while for FedZOO-NS one may use
ν N S 2 ≤ sup c , u C 2 b ( K − q q + n c − b n c − 1 ) + K b q σ ρ 2 . \begin{equation}
\nu_{\mathsf{NS}}^2
\le
\sup_{c,\boldsymbol u}
\frac{C^2}{b}
\left(
\frac{K-q}{q}
+
\frac{n_c-b}{n_c-1}
\right)
+
Kbq\sigma_\rho^2. \tag*{(135)}
\end{equation} ν NS 2 ≤ c , u sup b C 2 ( q K − q + n c − 1 n c − b ) + K b q σ ρ 2 . (135)
Because every clipped coefficient has magnitude at most C / ( b q ) C/(bq) C / ( b q ) , the noisy learner also satisfies the simple second-moment bound
G N S 2 ≤ K C 2 + K b q σ ρ 2 . \begin{equation}
G_{\mathsf{NS}}^2
\le
KC^2+Kbq\sigma_\rho^2. \tag*{(136)}
\end{equation} G NS 2 ≤ K C 2 + K b q σ ρ 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
1 M ∑ c = 1 M ∥ ∇ f c ( w ) − ∇ f ( w ) ∥ 2 ≤ ζ f 2 , \begin{equation}
\frac1M
\sum_{c=1}^{M}
\|\nabla f_c(\boldsymbol w)-\nabla f(\boldsymbol w)\|^2
\le
\zeta_f^2, \tag*{(137)}
\end{equation} M 1 c = 1 ∑ M ∥∇ f c ( w ) − ∇ f ( w ) ∥ 2 ≤ ζ f 2 , (137)
then
ζ Z 2 ≤ ∥ A ∥ o p 2 ζ f 2 = ∥ Z ∥ o p 2 K ζ f 2 . \begin{equation}
\zeta_{\boldsymbol Z}^2
\le
\|\boldsymbol A\|_{\mathrm{op}}^2\zeta_f^2
=
\frac{\|\boldsymbol Z\|_{\mathrm{op}}^2}{K}\zeta_f^2. \tag*{(138)}
\end{equation} ζ Z 2 ≤ ∥ A ∥ op 2 ζ f 2 = K ∥ Z ∥ op 2 ζ f 2 . (138)
A standard model-space gradient bound is sufficient for these moment conditions. If there is a finite G f G_f G f such that
then sample-wise smoothness gives
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 m m client sampling without replacement, define
χ m = { M − m m ( M − 1 ) , M > 1 , 0 , M = 1. \begin{equation}
\chi_m
=
\begin{cases}
\displaystyle
\frac{M-m}{m(M-1)},
&M>1,\\[1mm]
0,
&M=1.
\end{cases} \tag*{(141)}
\end{equation} χ m = ⎩ ⎨ ⎧ m ( M − 1 ) M − m , 0 , M > 1 , M = 1. (141)
Theorem 6 (Convergence in the fixed seed subspace). Fix a realized pool Z \boldsymbol Z Z and suppose Assumption 1 holds for A ∈ { S , N S } \mathsf A\in\{\mathsf S,\mathsf{NS}\} A ∈ { S , NS } . If
η > 0 , 4 η L Z E ≤ 1 , \begin{equation}
\eta>0,
\qquad
4\eta L_{\boldsymbol Z}E\le1, \tag*{(142)}
\end{equation} η > 0 , 4 η L Z E ≤ 1 , (142) then the corresponding learner satisfies
1 R ∑ r = 1 R E [ 1 K ∥ Z ⊤ ∇ f ( w r − 1 ) ∥ 2 | Z ] ≤ 2 ( f ( w 0 ) − f ⋆ ) η E R + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + ν A 2 m ) + 2 L Z 2 η 2 E 2 G A 2 . \begin{align}
&\frac1R
\sum_{r=1}^{R}
\mathbb E\left[
\frac1K\|\boldsymbol Z^{\top}\nabla f(\boldsymbol w^{r-1})\|^2
\,\middle|\,\boldsymbol Z\right]
\notag\\
&\quad\le
\frac{2(f(\boldsymbol w^0)-f^\star)}{\eta ER}
+
6\beta_{\mathsf A}^2
\notag\\
&\qquad+
8L_{\boldsymbol Z}\eta
\left(
E\chi_m\zeta_{\boldsymbol Z}^2
+
\frac{\nu_{\mathsf A}^2}{m}
\right)
+
2L_{\boldsymbol Z}^2\eta^2E^2G_{\mathsf A}^2. \tag*{(143)}
\end{align} R 1 r = 1 ∑ R E [ K 1 ∥ Z ⊤ ∇ f ( w r − 1 ) ∥ 2 Z ] ≤ η E R 2 ( f ( w 0 ) − f ⋆ ) + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + m ν A 2 ) + 2 L Z 2 η 2 E 2 G A 2 . (143) 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 / ( η E R ) 1/(\eta ER) 1/ ( η E R ) , whereas the finite-difference and clipping bias does not disappear merely by training longer. Averaging across participating clients reduces the centered local variation through ν A 2 / m \nu_{\mathsf A}^2/m ν A 2 / m . Increasing the number of local steps has a second effect, however: it also enlarges the contribution of client heterogeneity and local drift through E χ m ζ Z 2 E\chi_m\zeta_{\boldsymbol Z}^2 E χ m ζ Z 2 and E 2 G A 2 E^2G_{\mathsf A}^2 E 2 G A 2 . In FedZOO-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 H r − 1 \mathcal H_{r-1} H r − 1 contain Z \boldsymbol Z Z and the complete history through round r − 1 r-1 r − 1 , before sampling C r \mathcal C^r C r , and write E r [ ⋅ ] = E [ ⋅ ∣ H r − 1 ] \mathbb E_r[\cdot]=\mathbb E[\cdot\mid\mathcal H_{r-1}] E r [ ⋅ ] = E [ ⋅ ∣ H r − 1 ] . Fix r r r , put u = u r − 1 \boldsymbol u=\boldsymbol u^{r-1} u = u r − 1 and g = ∇ F Z ( u ) \boldsymbol g=\nabla F_{\boldsymbol Z}(\boldsymbol u) g = ∇ F Z ( u ) . Write v c r , t = K Δ a c r , t \boldsymbol v_c^{r,t}=\sqrt K\,\Delta\boldsymbol a_c^{r,t} v c r , t = K Δ a c r , t for the scaled accumulator increment at local step t t t . The bounds in Assumption 1 apply to these actual updates. The round recursion is
u r = u − η S r , S r = 1 m ∑ c ∈ C r ∑ t = 1 E v c r , t . \begin{equation}
\boldsymbol u^r
=
\boldsymbol u-
\eta\boldsymbol S_r,
\qquad
\boldsymbol S_r
=
\frac1m
\sum_{c\in\mathcal C^r}
\sum_{t=1}^{E}
\boldsymbol v_c^{r,t}. \tag*{(144)}
\end{equation} u r = u − η S r , S r = m 1 c ∈ C r ∑ t = 1 ∑ E v c r , t . (144) 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 \mathcal C^r C r is sampled, independently across clients, and then executing only the selected trajectories. This equivalent construction does not change the law of the algorithm, and every such trajectory starts from u \boldsymbol u u . The second-moment bound together with u c r , t − 1 − u = − η ∑ s < t v c r , s \boldsymbol u_c^{r,t-1}-\boldsymbol u=-\eta\sum_{s<t}\boldsymbol v_c^{r,s} u c r , t − 1 − u = − η ∑ s < t v c r , s therefore gives, for every client,
E r ∥ u c r , t − 1 − u ∥ 2 ≤ η 2 ( t − 1 ) 2 G A 2 . \begin{equation}
\mathbb E_r
\|\boldsymbol u_c^{r,t-1}-\boldsymbol u\|^2
\le
\eta^2(t-1)^2G_{\mathsf A}^2. \tag*{(145)}
\end{equation} E r ∥ u c r , t − 1 − u ∥ 2 ≤ η 2 ( t − 1 ) 2 G A 2 . (145) Let v ‾ r , t = m − 1 ∑ c ∈ C r v c r , t \overline{\boldsymbol v}^{r,t}
=m^{-1}\sum_{c\in\mathcal C^r}\boldsymbol v_c^{r,t} v r , t = m − 1 ∑ c ∈ C r v c r , t . Uniform client sampling, smoothness, Jensen’s inequality, and (145) imply
E r [ v ‾ r , t ] = g + e r , t , \begin{equation}
\mathbb E_r[\overline{\boldsymbol v}^{r,t}]
=
\boldsymbol g+\boldsymbol e_{r,t}, \tag*{(146)}
\end{equation} E r [ v r , t ] = g + e r , t , (146) where
∥ e r , t ∥ 2 ≤ 2 L Z 2 η 2 ( t − 1 ) 2 G A 2 + 2 β A 2 . \begin{equation}
\|\boldsymbol e_{r,t}\|^2
\le
2L_{\boldsymbol Z}^2\eta^2(t-1)^2G_{\mathsf A}^2
+
2\beta_{\mathsf A}^2. \tag*{(147)}
\end{equation} ∥ e r , t ∥ 2 ≤ 2 L Z 2 η 2 ( t − 1 ) 2 G A 2 + 2 β A 2 . (147) Using ⟨ a , b ⟩ ≥ − ∥ a ∥ 2 / 4 − ∥ b ∥ 2 \langle\boldsymbol a,\boldsymbol b\rangle
\ge-\|\boldsymbol a\|^2/4-\|\boldsymbol b\|^2 ⟨ a , b ⟩ ≥ − ∥ a ∥ 2 /4 − ∥ b ∥ 2 for the error term,
E r ⟨ g , v ‾ r , t ⟩ ≥ 3 4 ∥ g ∥ 2 − 2 L Z 2 η 2 ( t − 1 ) 2 G A 2 − 2 β A 2 . \begin{align}
\mathbb E_r
\langle\boldsymbol g,
\overline{\boldsymbol v}^{r,t}\rangle
&\ge
\frac34\|\boldsymbol g\|^2
-
2L_{\boldsymbol Z}^2\eta^2(t-1)^2G_{\mathsf A}^2
-
2\beta_{\mathsf A}^2. \tag*{(148)}
\end{align} E r ⟨ g , v r , t ⟩ ≥ 4 3 ∥ g ∥ 2 − 2 L Z 2 η 2 ( t − 1 ) 2 G A 2 − 2 β A 2 . (148) At a fixed local step, separate each update into its local gradient, its conditional bias, and the fresh randomness of that step. Define
b c ( x ) = E [ v c r , t ∣ u c r , t − 1 = x , Z ] − ∇ F Z , c ( x ) , \begin{equation}
\boldsymbol b_c(\boldsymbol x)
=
\mathbb E[\boldsymbol v_c^{r,t}\mid
\boldsymbol u_c^{r,t-1}=\boldsymbol x,\boldsymbol Z]
-\nabla F_{\boldsymbol Z,c}(\boldsymbol x), \tag*{(149)}
\end{equation} b c ( x ) = E [ v c r , t ∣ u c r , t − 1 = x , Z ] − ∇ F Z , c ( x ) , (149) so Assumption 1 gives ∥ b c ( x ) ∥ 2 ≤ β A 2 \|\boldsymbol b_c(\boldsymbol x)\|^2\le\beta_{\mathsf A}^2 ∥ b c ( x ) ∥ 2 ≤ β A 2 . With F r , t − 1 \mathcal F_{r,t-1} F r , t − 1 denoting the history available immediately before the sampling and Gaussian noise at local step t t t , define
ϵ c r , t = v c r , t − ∇ F Z , c ( u c r , t − 1 ) − b c ( u c r , t − 1 ) , E [ ϵ c r , t ∣ F r , t − 1 ] = 0 . \begin{align}
\boldsymbol\epsilon_c^{r,t}
&=\boldsymbol v_c^{r,t}
-\nabla F_{\boldsymbol Z,c}(\boldsymbol u_c^{r,t-1})
-\boldsymbol b_c(\boldsymbol u_c^{r,t-1}),
\notag\\
\mathbb E[\boldsymbol\epsilon_c^{r,t}\mid\mathcal F_{r,t-1}]&=\boldsymbol0. \tag*{(150)}
\end{align} ϵ c r , t E [ ϵ c r , t ∣ F r , t − 1 ] = v c r , t − ∇ F Z , c ( u c r , t − 1 ) − b c ( u c r , t − 1 ) , = 0 . (150) The difference between the full round update and E g E\boldsymbol g E g can then be written as four sources of error: client sampling, local drift, bias, and fresh stochastic variation,
S r − E g = A r + D r + B r + N r , \begin{equation}
\boldsymbol S_r-E\boldsymbol g
=
\boldsymbol A_r+
\boldsymbol D_r+
\boldsymbol B_r+
\boldsymbol N_r, \tag*{(151)}
\end{equation} S r − E g = A r + D r + B r + N r , (151) where
A r = E ( 1 m ∑ c ∈ C r ∇ F Z , c ( u ) − g ) , D r = 1 m ∑ c ∈ C r ∑ t = 1 E ( ∇ F Z , c ( u c r , t − 1 ) − ∇ F Z , c ( u ) ) , B r = 1 m ∑ c ∈ C r ∑ t = 1 E b c ( u c r , t − 1 ) , N r = ∑ t = 1 E 1 m ∑ c ∈ C r ϵ c r , t . \begin{align}
\boldsymbol A_r
&=E\left(\frac1m\sum_{c\in\mathcal C^r}
\nabla F_{\boldsymbol Z,c}(\boldsymbol u)-\boldsymbol g\right),
\notag\\
\boldsymbol D_r
&=\frac1m\sum_{c\in\mathcal C^r}\sum_{t=1}^E
\left(\nabla F_{\boldsymbol Z,c}(\boldsymbol u_c^{r,t-1})
-\nabla F_{\boldsymbol Z,c}(\boldsymbol u)\right),
\notag\\
\boldsymbol B_r
&=\frac1m\sum_{c\in\mathcal C^r}\sum_{t=1}^E
\boldsymbol b_c(\boldsymbol u_c^{r,t-1}),
\notag\\
\boldsymbol N_r
&=\sum_{t=1}^E\frac1m\sum_{c\in\mathcal C^r}
\boldsymbol\epsilon_c^{r,t}. \tag*{(152)}
\end{align} A r D r B r N r = E ( m 1 c ∈ C r ∑ ∇ F Z , c ( u ) − g ) , = m 1 c ∈ C r ∑ t = 1 ∑ E ( ∇ F Z , c ( u c r , t − 1 ) − ∇ F Z , c ( u ) ) , = m 1 c ∈ C r ∑ t = 1 ∑ E b c ( u c r , t − 1 ) , = t = 1 ∑ E m 1 c ∈ C r ∑ ϵ c r , t . (152) 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 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
E r ∥ A r ∥ 2 ≤ E 2 χ m ζ Z 2 , E r ∥ D r ∥ 2 ≤ L Z 2 η 2 E 4 3 G A 2 , E r ∥ B r ∥ 2 ≤ E 2 β A 2 , E r ∥ N r ∥ 2 ≤ E m ν A 2 . \begin{align}
\mathbb E_r\|\boldsymbol A_r\|^2
&\le
E^2\chi_m\zeta_{\boldsymbol Z}^2,
\notag\\
\mathbb E_r\|\boldsymbol D_r\|^2
&\le
\frac{L_{\boldsymbol Z}^2\eta^2E^4}{3}
G_{\mathsf A}^2,
\notag\\
\mathbb E_r\|\boldsymbol B_r\|^2
&\le
E^2\beta_{\mathsf A}^2,
\notag\\
\mathbb E_r\|\boldsymbol N_r\|^2
&\le
\frac{E}{m}\nu_{\mathsf A}^2. \tag*{(153)}
\end{align} E r ∥ A r ∥ 2 E r ∥ D r ∥ 2 E r ∥ B r ∥ 2 E r ∥ N r ∥ 2 ≤ E 2 χ m ζ Z 2 , ≤ 3 L Z 2 η 2 E 4 G A 2 , ≤ E 2 β A 2 , ≤ m E ν A 2 . (153) For the drift term, Cauchy–Schwarz gives L Z 2 E ∑ t = 1 E η 2 ( t − 1 ) 2 G A 2 L_{\boldsymbol Z}^2E\sum_{t=1}^E\eta^2(t-1)^2G_{\mathsf A}^2 L Z 2 E ∑ t = 1 E η 2 ( t − 1 ) 2 G A 2 . For the stochastic term, orthogonality of the martingale differences gives
E r ∥ N r ∥ 2 = ∑ t = 1 E E r ∥ 1 m ∑ c ∈ C r ϵ c r , t ∥ 2 ≤ E m ν A 2 . \begin{equation}
\mathbb E_r\|\boldsymbol N_r\|^2
=\sum_{t=1}^E\mathbb E_r
\left\|\frac1m\sum_{c\in\mathcal C^r}
\boldsymbol\epsilon_c^{r,t}\right\|^2
\le\frac{E}{m}\nu_{\mathsf A}^2. \tag*{(154)}
\end{equation} E r ∥ N r ∥ 2 = t = 1 ∑ E E r m 1 c ∈ C r ∑ ϵ c r , t 2 ≤ m E ν A 2 . (154) Only the new randomness generated at each local step is used here; the local trajectories themselves need not be independent across their E E E steps. Combining the four contributions yields
E r ∥ S r ∥ 2 ≤ 2 E 2 ∥ g ∥ 2 + 8 E 2 χ m ζ Z 2 + 8 E 2 β A 2 + 8 E m ν A 2 + 8 L Z 2 η 2 E 4 3 G A 2 . \begin{align}
\mathbb E_r\|\boldsymbol S_r\|^2
&\le
2E^2\|\boldsymbol g\|^2
+
8E^2\chi_m\zeta_{\boldsymbol Z}^2
+
8E^2\beta_{\mathsf A}^2
\notag\\
&\quad+
\frac{8E}{m}\nu_{\mathsf A}^2
+
\frac{8L_{\boldsymbol Z}^2\eta^2E^4}{3}
G_{\mathsf A}^2. \tag*{(155)}
\end{align} E r ∥ S r ∥ 2 ≤ 2 E 2 ∥ g ∥ 2 + 8 E 2 χ m ζ Z 2 + 8 E 2 β A 2 + m 8 E ν A 2 + 3 8 L Z 2 η 2 E 4 G A 2 . (155) We can now return to the objective. Smoothness of F Z F_{\boldsymbol Z} F Z applied to the round update in Eq. (144) , together with Eqs. (148) and (155) , gives a descent term plus the three error contributions above. Using ∑ t = 1 E ( t − 1 ) 2 ≤ E 3 / 3 \sum_{t=1}^{E}(t-1)^2\le E^3/3 ∑ t = 1 E ( t − 1 ) 2 ≤ E 3 /3 and the step-size condition 4 η L Z E ≤ 1 4\eta L_{\boldsymbol Z}E\le1 4 η L Z E ≤ 1 simplifies their coefficients, giving
E r [ F Z ( u r ) ] ≤ F Z ( u ) − η E 2 ∥ g ∥ 2 + 3 η E β A 2 + 4 L Z η 2 E 2 χ m ζ Z 2 + 4 L Z η 2 E m ν A 2 + L Z 2 η 3 E 3 G A 2 . \begin{align}
\mathbb E_r[F_{\boldsymbol Z}(\boldsymbol u^r)]
&\le
F_{\boldsymbol Z}(\boldsymbol u)
-
\frac{\eta E}{2}\|\boldsymbol g\|^2
+
3\eta E\beta_{\mathsf A}^2
\notag\\
&\quad+
4L_{\boldsymbol Z}\eta^2E^2
\chi_m\zeta_{\boldsymbol Z}^2
+
\frac{4L_{\boldsymbol Z}\eta^2E}{m}
\nu_{\mathsf A}^2
\notag\\
&\quad+
L_{\boldsymbol Z}^2\eta^3E^3G_{\mathsf A}^2. \tag*{(156)}
\end{align} E r [ F Z ( u r )] ≤ F Z ( u ) − 2 η E ∥ g ∥ 2 + 3 η E β A 2 + 4 L Z η 2 E 2 χ m ζ Z 2 + m 4 L Z η 2 E ν A 2 + L Z 2 η 3 E 3 G A 2 . (156) Since F Z ( u r ) = f ( w r ) ≥ f ⋆ F_{\boldsymbol Z}(\boldsymbol u^r)=f(\boldsymbol w^r)\ge f^\star F Z ( u r ) = f ( w r ) ≥ f ⋆ , summing over r r 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 J J is drawn independently and uniformly from { 0 , … , R − 1 } \{0,\ldots,R-1\} { 0 , … , R − 1 } , then the projected gradient at w J \boldsymbol w^J w J obeys the same bound in Eq. (143) . This random-checkpoint view is only an interpretation of the average: both algorithms still return w R \boldsymbol w^R w R , 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 ∥ o p \|\boldsymbol Z\|_{\mathrm{op}} ∥ 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 \boldsymbol Z Z are independent N ( 0 , I d ) \mathcal N(\boldsymbol0,I_d) N ( 0 , I d ) vectors. For 0 < δ < 1 0<\delta<1 0 < δ < 1 , set
L ‾ δ = L K ( d + K + 2 log ( 2 / δ ) ) 2 , E s p ( δ ) = { ∥ Z ∥ o p ≤ d + K + 2 log ( 2 / δ ) } . \begin{align}
\overline L_\delta
&=
\frac{L}{K}
\left(\sqrt d+\sqrt K+\sqrt{2\log(2/\delta)}\right)^2,
\notag\\
\mathcal E_{\mathrm{sp}}(\delta)
&=
\left\{\|\boldsymbol Z\|_{\mathrm{op}}
\le\sqrt d+\sqrt K+\sqrt{2\log(2/\delta)}\right\}. \tag*{(157)}
\end{align} L δ E sp ( δ ) = K L ( d + K + 2 log ( 2/ δ ) ) 2 , = { ∥ Z ∥ op ≤ d + K + 2 log ( 2/ δ ) } . (157) Assume utility regularity holds for every pool in E s p ( δ ) \mathcal E_{\mathrm{sp}}(\delta) E sp ( δ ) and choose the deterministic step size
0 < η ≤ 1 4 E L ‾ δ . \begin{equation}
0<\eta\le\frac1{4E\overline L_\delta}. \tag*{(158)}
\end{equation} 0 < η ≤ 4 E L δ 1 . (158) Then, with probability at least 1 − δ 1-\delta 1 − δ over the seed pool, Eq. (143) holds, with its expectation conditional on that pool.
Proof of Corollary 5 . The Gaussian singular-value bound [34 ] gives, for t ≥ 0 t\ge0 t ≥ 0 ,
P Z ( ∥ Z ∥ o p > d + K + t ) ≤ 2 e − t 2 / 2 . \begin{equation}
\mathbb P_{\boldsymbol Z}\!\left(
\|\boldsymbol Z\|_{\mathrm{op}}>\sqrt d+\sqrt K+t\right)
\le2e^{-t^2/2}. \tag*{(159)}
\end{equation} P Z ( ∥ Z ∥ op > d + K + t ) ≤ 2 e − t 2 /2 . (159) Thus P Z ( E s p ( δ ) ) ≥ 1 − δ \mathbb P_{\boldsymbol Z}(\mathcal E_{\mathrm{sp}}(\delta))
\ge1-\delta P Z ( E sp ( δ )) ≥ 1 − δ . On this event, L Z ≤ L ‾ δ L_{\boldsymbol Z}\le\overline L_\delta L Z ≤ L δ , so Eq. (158) implies Eq. (142) . Apply Theorem 6 separately for each such pool. ◻
Under the additional global moment condition (139) , the excluded pools can also be controlled. Using its explicit constants above, the joint expectation obeys
1 R ∑ r = 1 R E Z , a l g [ 1 K ∥ Z ⊤ ∇ f ( w r − 1 ) ∥ 2 ] ≤ E Z [ 1 E s p ( δ ) ( 2 ( f ( w 0 ) − f ⋆ ) η E R + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + ν A 2 m ) + 2 L Z 2 η 2 E 2 G A 2 ) ] + G f 2 δ ( d 2 + 2 d K ) . \begin{align}
&\frac1R\sum_{r=1}^R
\mathbb E_{\boldsymbol Z,\mathrm{alg}}
\left[\frac1K\|\boldsymbol Z^{\top}\nabla f(\boldsymbol w^{r-1})\|^2\right]
\notag\\
&\quad\le
\mathbb E_{\boldsymbol Z}\!\left[
\mathbf1_{\mathcal E_{\mathrm{sp}}(\delta)}
\left(
\frac{2(f(\boldsymbol w^0)-f^\star)}{\eta ER}
+6\beta_{\mathsf A}^2
+8L_{\boldsymbol Z}\eta\left(E\chi_m\zeta_{\boldsymbol Z}^2+\frac{\nu_{\mathsf A}^2}{m}\right)
+2L_{\boldsymbol Z}^2\eta^2E^2G_{\mathsf A}^2
\right)\right]
+G_f^2\sqrt{\delta\left(d^2+\frac{2d}{K}\right)}. \tag*{(160)}
\end{align} R 1 r = 1 ∑ R E Z , alg [ K 1 ∥ Z ⊤ ∇ f ( w r − 1 ) ∥ 2 ] ≤ E Z [ 1 E sp ( δ ) ( η E R 2 ( f ( w 0 ) − f ⋆ ) + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + m ν A 2 ) + 2 L Z 2 η 2 E 2 G A 2 ) ] + G f 2 δ ( d 2 + K 2 d ) . (160)
Indeed, ∥ ∇ f ( w ) ∥ 2 ≤ G f 2 \|\nabla f(\boldsymbol w)\|^2\le G_f^2 ∥∇ f ( w ) ∥ 2 ≤ G f 2 by Jensen’s inequality, so K − 1 ∥ Z ⊤ ∇ f ( w ) ∥ 2 ≤ G f 2 ∥ A ∥ o p 2 K^{-1}\|\boldsymbol Z^{\top}\nabla f(\boldsymbol w)\|^2
\le G_f^2\|\boldsymbol A\|_{\mathrm{op}}^2 K − 1 ∥ Z ⊤ ∇ f ( w ) ∥ 2 ≤ G f 2 ∥ A ∥ op 2 . On the complementary event, Cauchy–Schwarz and E ∥ A ∥ F 4 = d 2 + 2 d / K \mathbb E\|\boldsymbol A\|_{\mathrm F}^4=d^2+2d/K E ∥ A ∥ F 4 = d 2 + 2 d / K give the second term. The latter identity follows by expanding the square of the sum of d K dK d K independent squared standard Gaussians, divided by K 2 K^2 K 2 . On E s p ( δ ) \mathcal E_{\mathrm{sp}}(\delta) E sp ( δ ) , 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
E χ m ζ Z 2 + ν A 2 m > 0 , f ( w 0 ) > f ⋆ . E\chi_m\zeta_{\boldsymbol Z}^2+\frac{\nu_{\mathsf A}^2}{m}>0,
\qquad
f(\boldsymbol w^0)>f^\star. E χ m ζ Z 2 + m ν A 2 > 0 , f ( w 0 ) > f ⋆ . If
η = f ( w 0 ) − f ⋆ 4 L Z E R ( E χ m ζ Z 2 + ν A 2 / m ) ≤ 1 4 L Z E , \begin{equation}
\eta
=
\sqrt{
\frac{f(\boldsymbol w^0)-f^\star}
{4L_{\boldsymbol Z}ER\left(E\chi_m\zeta_{\boldsymbol Z}^2+\nu_{\mathsf A}^2/m\right)}
}
\le
\frac1{4L_{\boldsymbol Z}E}, \tag*{(161)}
\end{equation} η = 4 L Z E R ( E χ m ζ Z 2 + ν A 2 / m ) f ( w 0 ) − f ⋆ ≤ 4 L Z E 1 , (161) then
1 R ∑ r = 1 R E [ 1 K ∥ Z ⊤ ∇ f ( w r − 1 ) ∥ 2 ] ≤ 8 L Z ( f ( w 0 ) − f ⋆ ) ( E χ m ζ Z 2 + ν A 2 / m ) E R + 6 β A 2 + L Z E G A 2 ( f ( w 0 ) − f ⋆ ) 2 R ( E χ m ζ Z 2 + ν A 2 / m ) . \begin{align}
&\frac1R
\sum_{r=1}^{R}
\mathbb E
\left[\frac1K\|\boldsymbol Z^{\top}\nabla f(\boldsymbol w^{r-1})\|^2\right]
\notag\\
&\quad\le
8\sqrt{
\frac{
L_{\boldsymbol Z}\bigl(f(\boldsymbol w^0)-f^\star\bigr)
\left(E\chi_m\zeta_{\boldsymbol Z}^2+\nu_{\mathsf A}^2/m\right)
}{ER}
}
+6\beta_{\mathsf A}^2
\notag\\
&\qquad+
\frac{
L_{\boldsymbol Z}E G_{\mathsf A}^2\bigl(f(\boldsymbol w^0)-f^\star\bigr)
}{2R\left(E\chi_m\zeta_{\boldsymbol Z}^2+\nu_{\mathsf A}^2/m\right)}. \tag*{(162)}
\end{align} R 1 r = 1 ∑ R E [ K 1 ∥ Z ⊤ ∇ f ( w r − 1 ) ∥ 2 ] ≤ 8 E R L Z ( f ( w 0 ) − f ⋆ ) ( E χ m ζ Z 2 + ν A 2 / m ) + 6 β A 2 + 2 R ( E χ m ζ Z 2 + ν A 2 / m ) L Z E G A 2 ( f ( w 0 ) − f ⋆ ) . (162)
Proof of Corollary 6 . Substitute Eq. (161) into Eq. (143) . The first term and the term linear in η \eta η are then equal up to the displayed constants, while the η 2 \eta^2 η 2 term gives the final R − 1 R^{-1} R − 1 contribution. The upper bound on η \eta η is exactly the stepsize condition required by Theorem 6 . ◻
If the balancing choice in Eq. (161) is larger than 1 / ( 4 L Z E ) 1/(4L_{\boldsymbol Z}E) 1/ ( 4 L Z 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 m ( M − 1 ) ≤ 1 m , \chi_m=\frac{M-m}{m(M-1)}\le\frac1m, χ m = m ( M − 1 ) M − m ≤ m 1 ,
the quantity inside the square root is at most
E ζ Z 2 + ν A 2 m . \frac{E\zeta_{\boldsymbol Z}^2+\nu_{\mathsf A}^2}{m}. m E ζ Z 2 + ν A 2 .
Hence, when E E E , the seed pool, and the estimator moments are fixed, the leading term decreases as
O ( 1 m E R ) . \begin{equation}
\mathcal O\!\left(\frac1{\sqrt{mER}}\right). \tag*{(163)}
\end{equation} O ( m E R 1 ) . (163)
For fixed E E 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 m m grows, the R − 1 R^{-1} 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 \chi_M=0 χ M = 0 .
For FedZOO-S, this averaging gain is not affected by any stability noise. For FedZOO-NS, increasing m m 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 m E R mER m E R . In particular, when the horizon-dependent term in Eq. (65) determines σ ρ \sigma_\rho σ ρ ,
K b q σ ρ 2 m E R = 4 K b C 2 M n ‾ 2 ρ 2 . \begin{equation}
\frac{Kbq\sigma_\rho^2}{mER}
=
\frac{4KbC^2}{M\underline n^2\rho^2}. \tag*{(164)}
\end{equation} m E R K b q σ ρ 2 = M n 2 ρ 2 4 K b C 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 FedZOO-NS, the variance and second-moment bounds inherit the horizon dependence of σ ρ \sigma_\rho σ ρ and should not be treated as fixed asymptotic constants.
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 \kappa_{\boldsymbol Z}>0 κ Z > 0 and ε c o v ≥ 0 \varepsilon_{\mathrm{cov}}\ge0 ε cov ≥ 0 , fixed before the subsequent training randomness, such that every possible global checkpoint w \boldsymbol w w satisfies
1 K ∥ Z ⊤ ∇ f ( w ) ∥ 2 ≥ κ Z ∥ ∇ f ( w ) ∥ 2 − ε c o v 2 . \begin{equation}
\frac1K\|\boldsymbol Z^{\top}\nabla f(\boldsymbol w)\|^2
\ge
\kappa_{\boldsymbol Z}
\|\nabla f(\boldsymbol w)\|^2
-
\varepsilon_{\mathrm{cov}}^2. \tag*{(165)}
\end{equation} K 1 ∥ Z ⊤ ∇ f ( w ) ∥ 2 ≥ κ Z ∥∇ f ( w ) ∥ 2 − ε cov 2 . (165)
Corollary 7 (Full-space stationarity). Under the conditions of Theorem 6 and Assumption 2 ,
1 R ∑ r = 1 R E ∥ ∇ f ( w r − 1 ) ∥ 2 ≤ 1 κ Z [ 2 ( f ( w 0 ) − f ⋆ ) η E R + 6 β A 2 + ε c o v 2 + 8 L Z η ( E χ m ζ Z 2 + ν A 2 m ) + 2 L Z 2 η 2 E 2 G A 2 ] . \begin{align}
&\frac1R
\sum_{r=1}^{R}
\mathbb E\|\nabla f(\boldsymbol w^{r-1})\|^2
\notag\\
&\quad\le
\frac1{\kappa_{\boldsymbol Z}}
\left[
\frac{2(f(\boldsymbol w^0)-f^\star)}{\eta ER}
+
6\beta_{\mathsf A}^2
+
\varepsilon_{\mathrm{cov}}^2
\right.
\notag\\
&\qquad\left.
+
8L_{\boldsymbol Z}\eta
\left(
E\chi_m\zeta_{\boldsymbol Z}^2
+
\frac{\nu_{\mathsf A}^2}{m}
\right)
+
2L_{\boldsymbol Z}^2\eta^2E^2G_{\mathsf A}^2
\right]. \tag*{(166)}
\end{align} R 1 r = 1 ∑ R E ∥∇ f ( w r − 1 ) ∥ 2 ≤ κ Z 1 [ η E R 2 ( f ( w 0 ) − f ⋆ ) + 6 β A 2 + ε cov 2 + 8 L Z η ( E χ m ζ Z 2 + m ν A 2 ) + 2 L Z 2 η 2 E 2 G A 2 ] . (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 \boldsymbol z_1,\ldots,\boldsymbol z_K z 1 , … , z K are independent N ( 0 , I d ) \mathcal N(\boldsymbol0,I_d) N ( 0 , I d ) vectors. Let V ⊆ R d \mathcal V\subseteq\mathbb R^d V ⊆ R d be a fixed r r r -dimensional subspace chosen independently of the seed pool. Assume, for every pool under consideration, that all possible global checkpoints satisfy
∇ f ( w ) ∈ V . \begin{equation}
\nabla f(\boldsymbol w)
\in
\mathcal V. \tag*{(167)}
\end{equation} ∇ f ( w ) ∈ V . (167) For 0 < δ < 1 0<\delta<1 0 < δ < 1 , define
α K , r , δ = r + 2 log ( 2 / δ ) K . \begin{equation}
\alpha_{K,r,\delta}
=
\frac{
\sqrt r+\sqrt{2\log(2/\delta)}
}{\sqrt K}. \tag*{(168)}
\end{equation} α K , r , δ = K r + 2 log ( 2/ δ ) . (168) If α K , r , δ < 1 \alpha_{K,r,\delta}<1 α K , r , δ < 1 , then, with probability at least 1 − δ 1-\delta 1 − δ over the seed pool,
simultaneously for every g ∈ V \boldsymbol g\in\mathcal V g ∈ V . Consequently, Assumption 2 holds with
κ Z = ( 1 − α K , r , δ ) 2 , ε c o v = 0. \begin{equation}
\kappa_{\boldsymbol Z}
=
(1-\alpha_{K,r,\delta})^2,
\qquad
\varepsilon_{\mathrm{cov}}=0. \tag*{(170)}
\end{equation} κ Z = ( 1 − α K , r , δ ) 2 , ε cov = 0. (170)
Proof of Proposition 2 . Let U ∈ R d × r \boldsymbol U\in\mathbb R^{d\times r} U ∈ R d × r have orthonormal columns spanning V \mathcal V V . Then Z ⊤ U \boldsymbol Z^{\top}\boldsymbol U Z ⊤ U is a K × r K\times r 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 − δ 1-\delta 1 − δ ,
σ min ( A ⊤ U ) ≥ 1 − α K , r , δ , σ max ( A ⊤ U ) ≤ 1 + α K , r , δ . \begin{align}
\sigma_{\min}(\boldsymbol A^{\top}\boldsymbol U)
&\ge
1-\alpha_{K,r,\delta},
\notag\\
\sigma_{\max}(\boldsymbol A^{\top}\boldsymbol U)
&\le
1+\alpha_{K,r,\delta}. \tag*{(171)}
\end{align} σ m i n ( A ⊤ U ) σ m a x ( A ⊤ U ) ≥ 1 − α K , r , δ , ≤ 1 + α K , r , δ . (171) Applying these inequalities to g = U y \boldsymbol g=\boldsymbol U\boldsymbol y 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 0<\delta<1 0 < δ < 1 , α K , r , δ / 2 < 1 \alpha_{K,r,\delta/2}<1 α K , r , δ /2 < 1 , and choose a deterministic step size
0 < η ≤ 1 4 E L ‾ δ / 2 . \begin{equation}
0<\eta\le\frac1{4E\overline L_{\delta/2}}. \tag*{(172)}
\end{equation} 0 < η ≤ 4 E L δ /2 1 . (172) Assume utility regularity holds on E s p ( δ / 2 ) \mathcal E_{\mathrm{sp}}(\delta/2) E sp ( δ /2 ) . With probability at least 1 − δ 1-\delta 1 − δ over the seed pool,
1 R ∑ r = 1 R E [ ∥ ∇ f ( w r − 1 ) ∥ 2 ∣ Z ] ≤ 1 ( 1 − α K , r , δ / 2 ) 2 [ 2 ( f ( w 0 ) − f ⋆ ) η E R + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + ν A 2 m ) + 2 L Z 2 η 2 E 2 G A 2 ] . \begin{equation}
\frac1R\sum_{r=1}^{R}
\mathbb E\bigl[\|\nabla f(\boldsymbol w^{r-1})\|^2
\mid\boldsymbol Z\bigr]
\le
\frac{1}{(1-\alpha_{K,r,\delta/2})^2}
\left[
\frac{2(f(\boldsymbol w^0)-f^\star)}{\eta ER}
+6\beta_{\mathsf A}^2
+8L_{\boldsymbol Z}\eta\left(E\chi_m\zeta_{\boldsymbol Z}^2+\frac{\nu_{\mathsf A}^2}{m}\right)
+2L_{\boldsymbol Z}^2\eta^2E^2G_{\mathsf A}^2
\right]. \tag*{(173)}
\end{equation} R 1 r = 1 ∑ R E [ ∥∇ f ( w r − 1 ) ∥ 2 ∣ Z ] ≤ ( 1 − α K , r , δ /2 ) 2 1 [ η E R 2 ( f ( w 0 ) − f ⋆ ) + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + m ν A 2 ) + 2 L Z 2 η 2 E 2 G A 2 ] . (173)
Proof of Corollary 8 . Let E c o v ( δ / 2 ) \mathcal E_{\mathrm{cov}}(\delta/2) E cov ( δ /2 ) be the uniform embedding event in Proposition 2 , and set
E δ = E s p ( δ / 2 ) ∩ E c o v ( δ / 2 ) . \begin{equation}
\mathcal E_\delta
=
\mathcal E_{\mathrm{sp}}(\delta/2)
\cap\mathcal E_{\mathrm{cov}}(\delta/2). \tag*{(174)}
\end{equation} E δ = E sp ( δ /2 ) ∩ E cov ( δ /2 ) . (174) A union bound gives P Z ( E δ ) ≥ 1 − δ \mathbb P_{\boldsymbol Z}(\mathcal E_\delta)
\ge1-\delta P Z ( 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 (1-\alpha_{K,r,\delta/2})^2 ( 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
1 R ∑ r = 1 R E Z , a l g ∥ ∇ f ( w r − 1 ) ∥ 2 ≤ E Z [ 1 E δ ( 2 ( f ( w 0 ) − f ⋆ ) η E R + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + ν A 2 m ) + 2 L Z 2 η 2 E 2 G A 2 ) ] ( 1 − α K , r , δ / 2 ) 2 + δ G f 2 , \begin{align}
&\frac1R\sum_{r=1}^{R}
\mathbb E_{\boldsymbol Z,\mathrm{alg}}
\|\nabla f(\boldsymbol w^{r-1})\|^2
\notag\\
&\quad\le
\frac{\mathbb E_{\boldsymbol Z}\!\left[\mathbf1_{\mathcal E_\delta}
\left(
\frac{2(f(\boldsymbol w^0)-f^\star)}{\eta ER}
+6\beta_{\mathsf A}^2
+8L_{\boldsymbol Z}\eta\left(E\chi_m\zeta_{\boldsymbol Z}^2+\frac{\nu_{\mathsf A}^2}{m}\right)
+2L_{\boldsymbol Z}^2\eta^2E^2G_{\mathsf A}^2
\right)\right]}
{(1-\alpha_{K,r,\delta/2})^2}
+\delta G_f^2, \tag*{(175)}
\end{align} R 1 r = 1 ∑ R E Z , alg ∥∇ f ( w r − 1 ) ∥ 2 ≤ ( 1 − α K , r , δ /2 ) 2 E Z [ 1 E δ ( η E R 2 ( f ( w 0 ) − f ⋆ ) + 6 β A 2 + 8 L Z η ( E χ m ζ Z 2 + m ν A 2 ) + 2 L Z 2 η 2 E 2 G A 2 ) ] + δ G f 2 , (175)
because ∥ ∇ f ∥ 2 ≤ G f 2 \|\nabla f\|^2\le G_f^2 ∥∇ f ∥ 2 ≤ G f 2 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 \operatorname{rank}(\boldsymbol Z)<d rank ( Z ) < d , choose
f ( w ) = 1 2 ∥ w − w ⋆ ∥ 2 \begin{equation}
f(\boldsymbol w)=\frac12\|\boldsymbol w-\boldsymbol w^\star\|^2 \tag*{(176)}
\end{equation} f ( w ) = 2 1 ∥ w − w ⋆ ∥ 2 (176)
with w ⋆ − w 0 ∉ range ( Z ) \boldsymbol w^\star-\boldsymbol w^0\notin\operatorname{range}(\boldsymbol Z) w ⋆ − w 0 ∈ / range ( Z ) . The minimizer over W Z \mathcal W_{\boldsymbol Z} W Z is
w Z ⋆ = w 0 + Π Z ( w ⋆ − w 0 ) , \begin{equation}
\boldsymbol w_{\boldsymbol Z}^{\star}
=
\boldsymbol w^0+
\Pi_{\boldsymbol Z}(\boldsymbol w^\star-\boldsymbol w^0), \tag*{(177)}
\end{equation} w Z ⋆ = w 0 + Π Z ( w ⋆ − w 0 ) , (177)
where Π Z \Pi_{\boldsymbol Z} Π Z is the orthogonal projector onto range ( Z ) \operatorname{range}(\boldsymbol Z) range ( Z ) . Its gradient is orthogonal to that range, so
1 K ∥ Z ⊤ ∇ f ( w Z ⋆ ) ∥ 2 = 0 , ∥ ∇ f ( w Z ⋆ ) ∥ > 0. \begin{equation}
\frac1K\|\boldsymbol Z^{\top}\nabla f(\boldsymbol w_{\boldsymbol Z}^{\star})\|^2=0,
\qquad
\|\nabla f(\boldsymbol w_{\boldsymbol Z}^{\star})\|>0. \tag*{(178)}
\end{equation} K 1 ∥ Z ⊤ ∇ f ( w Z ⋆ ) ∥ 2 = 0 , ∥∇ f ( w Z ⋆ ) ∥ > 0. (178)
For an independent Gaussian pool with K < d K<d K < d , the same construction can be fixed before the pool is sampled: any nonzero w ⋆ − w 0 \boldsymbol w^\star-\boldsymbol w^0 w ⋆ − w 0 lies outside range ( Z ) \operatorname{range}(\boldsymbol Z) 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 j 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.
Utility After Unlearning
After request j j j , denote the retained local datasets by D c ( j + 1 ) \mathcal D_c^{(j+1)} D c ( j + 1 ) and write
f c ( j ) ( w ) = 1 ∣ D c ( j + 1 ) ∣ ∑ x ∈ D c ( j + 1 ) ℓ ( w ; x ) , f ( j ) ( w ) = 1 M ∑ c = 1 M f c ( j ) ( w ) . \begin{align}
f_c^{(j)}(\boldsymbol w)
&=
\frac1{|\mathcal D_c^{(j+1)}|}
\sum_{x\in\mathcal D_c^{(j+1)}}
\ell(\boldsymbol w;x),
\notag\\
f^{(j)}(\boldsymbol w)
&=
\frac1M\sum_{c=1}^{M}f_c^{(j)}(\boldsymbol w). \tag*{(179)}
\end{align} f c ( j ) ( w ) f ( j ) ( w ) = ∣ D c ( j + 1 ) ∣ 1 x ∈ D c ( j + 1 ) ∑ ℓ ( w ; x ) , = M 1 c = 1 ∑ M f c ( j ) ( w ) . (179)
The constants in Assumption 1 are evaluated for this retained objective and are denoted by β A , j \beta_{\mathsf A,j} β A , j , ν A , j \nu_{\mathsf A,j} ν A , j , G A , j G_{\mathsf A,j} G A , j , and ζ Z , j \zeta_{\boldsymbol Z,j} ζ Z , j ; also let f j ⋆ = inf w f ( j ) ( w ) > − ∞ f_j^\star=\inf_{\boldsymbol w}f^{(j)}(\boldsymbol w)>-\infty f j ⋆ = inf w f ( j ) ( w ) > − ∞ . The seed pool and algorithmic hyperparameters are inherited from the original run. The same sample-wise smoothness constant L L L therefore gives the same L Z L_{\boldsymbol Z} L Z . 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 j j , continue the state returned by the unlearning procedure on D ( j + 1 ) \mathcal D^{(j+1)} D ( j + 1 ) to the fixed horizon R R R with no further requests, and denote the resulting global trajectory by { w A r , ( j ) } r = 0 R \{\boldsymbol w_{\mathsf A}^{r,(j)}\}_{r=0}^{R} { w A r , ( j ) } r = 0 R . Suppose Assumption 1 holds for this retained dataset. Condition on a realized seed pool Z \boldsymbol Z Z , keep the original step size, and assume 4 η L Z E ≤ 1 4\eta L_{\boldsymbol Z}E\le1 4 η L Z E ≤ 1 . Then
1 R ∑ r = 1 R E [ 1 K ∥ Z ⊤ ∇ f ( j ) ( w A r − 1 , ( j ) ) ∥ 2 ] ≤ 2 ( f ( j ) ( w 0 ) − f j ⋆ ) η E R + 6 β A , j 2 + 8 L Z η ( E χ m ζ Z , j 2 + ν A , j 2 m ) + 2 L Z 2 η 2 E 2 G A , j 2 . \begin{equation}
\frac1R
\sum_{r=1}^{R}
\mathbb E
\left[\frac1K\|\boldsymbol Z^{\top}\nabla f^{(j)}
(\boldsymbol w_{\mathsf A}^{r-1,(j)})\|^2\right]
\le
\frac{2(f^{(j)}(\boldsymbol w^0)-f_j^\star)}{\eta ER}
+6\beta_{\mathsf A,j}^2
+8L_{\boldsymbol Z}\eta
\left(E\chi_m\zeta_{\boldsymbol Z,j}^2+\frac{\nu_{\mathsf A,j}^2}{m}\right)
+2L_{\boldsymbol Z}^2\eta^2E^2G_{\mathsf A,j}^2. \tag*{(180)}
\end{equation} R 1 r = 1 ∑ R E [ K 1 ∥ Z ⊤ ∇ f ( j ) ( w A r − 1 , ( j ) ) ∥ 2 ] ≤ η E R 2 ( f ( j ) ( w 0 ) − f j ⋆ ) + 6 β A , j 2 + 8 L Z η ( E χ m ζ Z , j 2 + m ν A , j 2 ) + 2 L Z 2 η 2 E 2 G A , j 2 . (180) 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 j j the returned state has exactly the law of the corresponding learner on D ( j + 1 ) \mathcal D^{(j+1)} 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 R 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 K ∥ Z ⊤ ∇ f ( j ) ( w ) ∥ 2 ≥ κ Z , j ∥ ∇ f ( j ) ( w ) ∥ 2 − ε c o v , j 2 \begin{equation}
\frac1K\|\boldsymbol Z^{\top}\nabla f^{(j)}(\boldsymbol w)\|^2
\ge
\kappa_{\boldsymbol Z,j}
\|\nabla f^{(j)}(\boldsymbol w)\|^2
-
\varepsilon_{\mathrm{cov},j}^2 \tag*{(181)}
\end{equation} K 1 ∥ Z ⊤ ∇ f ( j ) ( w ) ∥ 2 ≥ κ Z , j ∥∇ f ( j ) ( w ) ∥ 2 − ε cov , j 2 (181) for some κ Z , j > 0 \kappa_{\boldsymbol Z,j}>0 κ Z , j > 0 and ε c o v , j ≥ 0 \varepsilon_{\mathrm{cov},j}\ge0 ε cov , j ≥ 0 . Then, conditionally on the seed pool,
1 R ∑ r = 1 R E ∥ ∇ f ( j ) ( w A r − 1 , ( j ) ) ∥ 2 ≤ 1 κ Z , j [ 2 ( f ( j ) ( w 0 ) − f j ⋆ ) η E R + 6 β A , j 2 + 8 L Z η ( E χ m ζ Z , j 2 + ν A , j 2 m ) + 2 L Z 2 η 2 E 2 G A , j 2 + ε c o v , j 2 ] . \begin{equation}
\frac1R
\sum_{r=1}^{R}
\mathbb E
\|\nabla f^{(j)}
(\boldsymbol w_{\mathsf A}^{r-1,(j)})\|^2
\le
\frac{1}{\kappa_{\boldsymbol Z,j}}
\left[
\frac{2(f^{(j)}(\boldsymbol w^0)-f_j^\star)}{\eta ER}
+6\beta_{\mathsf A,j}^2
+8L_{\boldsymbol Z}\eta
\left(E\chi_m\zeta_{\boldsymbol Z,j}^2+\frac{\nu_{\mathsf A,j}^2}{m}\right)
+2L_{\boldsymbol Z}^2\eta^2E^2G_{\mathsf A,j}^2
+\varepsilon_{\mathrm{cov},j}^2
\right]. \tag*{(182)}
\end{equation} R 1 r = 1 ∑ R E ∥∇ f ( j ) ( w A r − 1 , ( j ) ) ∥ 2 ≤ κ Z , j 1 [ η E R 2 ( f ( j ) ( w 0 ) − f j ⋆ ) + 6 β A , j 2 + 8 L Z η ( E χ m ζ Z , j 2 + m ν A , j 2 ) + 2 L Z 2 η 2 E 2 G A , j 2 + ε cov , j 2 ] . (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. ◻