Efficient Exact Unlearning for Federated Zeroth-Order Optimization

A. Federated Zeroth-Order Optimization

• FedZOO avoids backpropagation and can communicate perturbation seeds and scalar coefficients, addressing memory and bandwidth constraints in edge training.Backpropagation can require substantial intermediate-activation memory, while tensor-valued updates can be costly over bandwidth-constrained networks.Source: §I · p. 1

B. Federated Unlearning

• Existing FedZOO methods do not address machine unlearning, and deleting samples from storage alone cannot remove their effects already incorporated into the global model.Exact unlearning requires distributional equivalence to rerunning the learner on retained data, while retraining from scratch is computationally expensive.Source: §I · p. 1

I. INTRODUCTION

• The paper asks how to make federated zeroth-order learning TV-stable while retaining FedZOO’s memory and communication advantages.TV stability makes neighboring-data output distributions overlap, creating an opportunity for coupling-based computation reuse.Source: §I · p. 2
• FEDZOO-S uses client and mini-batch subsampling so FEDZOUL-S can preserve unaffected updates and replay from the first affected step.FEDZOO-NS adds Gaussian randomization; FEDZOUL-NS uses rejection–reflection coupling to reuse some affected updates.Source: §I · p. 2

B. Federated Unlearning

• Prior stability-based exact-unlearning methods target gradient-based training and model- or curvature-level states, motivating procedures built around compact seed-encoded update histories.The paper also situates its work alongside zeroth-order methods that use random seeds and scalar gradients for dimension-independent communication.Source: B. Federated Unlearning · p. 2, A. Federated Zeroth-Order Optimization · p. 2

C. Total Variation Stability

• For sample-level adjacent datasets, ρ-sample-level TV stability bounds the distance between the learner’s model-output distributions; smaller ρ means greater overlap for coupling-based reuse.The stability definition concerns the marginal model output, not the auxiliary internal state.Source: C. Total Variation Stability · pp. 3–4

A. Seed-Encoded Zeroth-Order Updates

• A fixed shared seed pool represents zeroth-order updates through scalar coefficients in a K-dimensional accumulator, with the model reconstructed from that state.The seed pool remains fixed throughout training, allowing accumulated coefficients associated with the same perturbation to be combined.Source: A. Seed-Encoded Zeroth-Order Updates · p. 4

B. Subsampling-Stable Learning and Unlearning

• FEDZOO-S obtains stability through client and mini-batch subsampling, so a sample changes the realized trajectory only if selected into an update.FEDZOUL-S preserves the unaffected prefix and replays from the first local step containing a deleted sample.Source: B. Subsampling-Stable Learning and… · pp. 4–5
• FEDZOUL-S produces a model and saved state distributed as a FEDZOO-S run on retained data by preserving the unaffected prefix and regenerating from the first affected step.The theoretical analysis considers a single deletion; multiple requests are handled sequentially.Source: B. Subsampling-Stable Learning and… · p. 5
• Once a deleted sample contributes to a FEDZOO-S update, the trajectory must be replayed from that update onward.The noise-stable pair is introduced to allow some affected updates to be reused.Source: B. Subsampling-Stable Learning and… · p. 5

C. Noise-Stable Learning and Unlearning

• FEDZOO-NS randomizes local zeroth-order updates with Gaussian noise so neighboring-data update distributions overlap and affected updates can sometimes be reused through coupling.The Gaussian noise is independent of client, mini-batch, and perturbation-seed sampling.Source: C. Noise-Stable Learning and Unlearning · p. 5
• FEDZOUL-NS couples an affected mini-batch to a uniform retained-data mini-batch, replacing deleted samples while retaining the seeds for retained samples.Replacement samples inherit the seed sets of the deleted samples they replace.Source: C. Noise-Stable Learning and Unlearning · p. 6
• When rejection sampling accepts, FEDZOUL-NS reuses the recorded noisy coefficient vector and leaves the local model and accumulator unchanged.Only the saved mini-batch and its sample–seed correspondence are replaced.Source: C. Noise-Stable Learning and Unlearning · p. 6
• A rejected coupling is reflected to produce a retained-data transition, and subsequent states are regenerated from the corrected endpoint.If all affected steps are accepted, the realized optimization state remains unchanged; otherwise, replay begins after the first rejection.Source: C. Noise-Stable Learning and Unlearning · p. 6

V. THEORETICAL ANALYSIS

• The analysis asks whether deletion can recover exactly the retained-data training state without restarting from the beginning, and what optimization guarantee holds with a finite reused seed pool.The complete statements and proofs are located in Appendix B.Source: §V · p. 6
• The analysis denotes the total number of local positions by T = RE and counts executed positions before a request as Tul = (Rul−1)E+tul.It also defines n as a lower bound on client dataset sizes before deletion.Source: §V · p. 6
• The listed FedZOO-S and FedZOUL-S procedures take the initial model and training parameters as inputs, initialize a fixed seed pool, and output the trained or unlearned model.The parameter list includes R, E, K, q, b, m, η, and µ.Source: §V · p. 7

• Tmb/(Mn) ≤ ρ is sufficient for FedZOO-S to be ρ-TV stable, based on the chance that a deleted sample is selected for a local update.The stability analysis couples executions until the first event where the deleted sample is selected.Source: A. Stability, Exact Unlearning, and Cost · p. 7
• FedZOUL-S preserves the unaffected prefix and regenerates computation only after the deleted sample’s first occurrence, with exact unlearning proved for one deletion and a non-adaptive deletion stream.If the sample was never used, the state is already distributed as training on retained data.Source: A. Stability, Exact Unlearning, and Cost · p. 7
• FedZOO-NS uses Gaussian overlap between transition laws to check whether a previously generated noisy update remains valid after deletion; rejected updates are regenerated by reflection coupling.The passage describes rejection and reflection as the update-generation mechanism.Source: A. Stability, Exact Unlearning, and Cost · p. 7
• FedZOUL-NS produces an update with the correct retained-data law and exactly unlearns the complete maintained state, with a stated extension to non-adaptive deletion streams.Its replay probability is bounded in Proposition 1, though the bound is incomplete in the supplied passage.Source: A. Stability, Exact Unlearning, and Cost · p. 8
• FedZOUL-S replays from the first use of the deleted sample, whereas FedZOUL-NS checks affected updates and replays only after the first rejection, so computation may still be retained after the sample appears.The cost analysis also gives loss-evaluation, communication, and request-stream bounds; savings come from exact reuse rather than approximate retraining.Source: A. Stability, Exact Unlearning, and Cost · p. 8

• Seed reuse leaves the federated objective unchanged but restricts model movement to the affine space generated by the shared seed pool.The iterates have the form w = w0 + Au; the corresponding gradient quantity is not an orthogonal projection when seed columns are nonorthogonal.Source: B. Optimization with a Finite Seed Pool · p. 8
• The convergence analysis bounds finite-horizon error, finite-difference or clipping bias, stochastic variation with client heterogeneity, and drift across local steps.For FedZOO-NS, stability noise also enters the variance and second-moment terms; the stated stepsize condition is 4ηLZE ≤ 1.Source: B. Optimization with a Finite Seed Pool · pp. 8–9
• For fixed E and while the leading stochastic term dominates, increasing participating clients gives linear speedup in communication rounds, but bias, local drift, and FedZOO-NS noise limit the improvement.The passage states the leading stochastic term scales as O(1/mER).Source: B. Optimization with a Finite Seed Pool · p. 9

• A small gradient along shared seed directions need not imply a small full gradient when the seed span misses a gradient component.The full-space conversion therefore assumes the seed directions capture gradients encountered during training.Source: C. From Seed-Subspace to Full-Space… · p. 9
• Under the coverage condition, the full-space guarantee has 1/κZ scaling and additive coverage error ε2 cov/κZ; sufficiently many Gaussian seed directions yield a uniform near-isometry on a fixed independent r-dimensional subspace.The passage also notes a rank-deficient seed span can have zero seed-direction gradient with nonzero full gradient when K < d.Source: C. From Seed-Subspace to Full-Space… · p. 9
• After deletion, the returned state has the same law as a fresh run on retained data, so no separate optimization error is introduced by unlearning.Convergence analysis applies again when the retained objective meets the same regularity conditions and the inherited stepsize remains valid.Source: C. From Seed-Subspace to Full-Space… · p. 9

1) Datasets and Models:

• The evaluation spans four vision datasets and TOFU, uses multiple heterogeneity and retain/forget settings, and compares against zeroth-order and unlearning baselines.Vision models include an MLP, CNNs, and ResNet-18; TOFU uses Llama-3.2-1B-Instruct and 3B-Instruct.Source: 1) Datasets and Models · p. 9, 2) Baselines · p. 9

1) Performance of FedZOO-S and FedZOO-NS:

• Across 12 vision settings, the learning methods match or outperform baselines, with accuracy gains up to 9.13 percentage points; FEDZOO-S is best or tied-best in seven settings.On TOFU, FEDZOO-S has the highest ROUGE-L score across both model sizes and all splits; FEDZOO-NS performs worse, with σ = 20 consistently below σ = 10.Source: 1) Performance of FedZOO-S and FedZOO-NS · pp. 10–11, Table I · p. 10, Table II · p. 10
• Both methods use more local computation than FedKSeed Pro and DeComFL while retaining dimension-independent communication; their scalar-gradient accumulator communication matches FedKSeed Pro but exceeds DeComFL.The comparison attributes higher runtime to evaluating bqE sample–direction pairs per client per round rather than E direction evaluations.Source: 1) Performance of FedZOO-S and FedZOO-NS · p. 11

2) Performance of FedZOUL-S and FedZOUL-NS:

• On vision tasks, FEDZOUL-S improves over FEDZOO-S by up to 13.37 percentage points and finishes within 2.77 points of re-optimization; TOFU results show trade-offs in forget-set and general-knowledge scores.FEDZOUL-S retains higher Real Authors scores than Oblivionis-U, while FEDZOUL-NS has greater general-knowledge degradation, particularly for the 1B model.Source: 2) Performance of FedZOUL-S and… · p. 11, Figure 1 · p. 11, Figure 2 · p. 11
• After five TOFU requests with the 3B model, FEDZOUL-S and FEDZOUL-NS use 12.38 MB and 1.89 MB, respectively, versus 27.08 GB for Oblivionis.On CIFAR-10 after 15 requests, FEDZOUL-NS uses 389.1 MB, 5.7% less than re-optimization; the paper reports up to approximately four orders of magnitude less communication overall.Source: 2) Performance of FedZOUL-S and… · p. 11, Figure 5 · p. 12

2) Performance of FedZOUL-S and FedZOOL-NS:

• At the final request, FEDZOUL-S and FEDZOUL-NS cut cumulative runtime by 2.2% and 12.4% on CIFAR-10, and by 22.5% and 56.1% on TOFU with the 3B model.The reported savings arise because only some requests trigger suffix replay, with noise and rejection sampling reducing replay further for FEDZOUL-NS.Source: 2) Performance of FedZOUL-S and… · p. 11, Figure 3 · p. 11

2) Performance of FedZOUL-S and FedZOUL-NS:

• Increasing client sampling from 0.1 to 0.3 improves optimization accuracy, while further increases bring limited gains; unlearning accuracy is not monotonic and peaks at different ratios for the two variants.FEDZOUL-S reaches 68.27% at m/M = 0.5, and FEDZOUL-NS reaches 72.73% at 0.9.Source: 3) Impact of the Client Sampling Ratio… · p. 12, Figure 6 · p. 12
• Higher client participation increases communication and generally increases unlearning runtime, while FEDZOUL-NS's time and communication savings over FEDZOUL-S shrink at higher participation.The reported savings decrease from 24.3% and 15.9% at m/M = 0.1 to 9.9% and 2.1% at 0.9.Source: 3) Impact of the Client Sampling Ratio… · p. 12

A. GPU Memory cost of FedZOUL-S/NS

• 128.08 MB on CIFAR-10 is 60.8% below FedRR and 54.0% below FUDD; on TOFU, both methods use 6.63 GB versus Oblivionis’s 11.15 GB for the 3B model.Peak memory is reported as lowest across all tasks, with the reduction relative to Oblivionis increasing from 24.3% for the 1B model to 40.5% for the 3B model.Source: A. GPU Memory cost of FedZOUL-S/NS · p. 15, Figure 7 · p. 15

B. Impact of Hyperparameters K and q

• At K = 4096, increasing q from 1 to 2 raises FEDZOO-NS accuracy from 64.11% to 71.26% and runtime from 2.883 to 3.073 s, while communication stays unchanged.Communication is independent of q and increases linearly with K; the study uses K = 4096 and q = 1 to limit local computation.Source: B. Impact of Hyperparameters K and q · p. 15, Figure 8 · p. 16

APPENDIX B COMPLETE THEORETICAL ANALYSIS

• FedZOO-S stability comes from subsampling: a deletion changes its trajectory only if the target client participates and the deleted sample enters a local mini-batch.The analysis frames exact unlearning as matching the joint distribution of the model and all maintained state to retained-data retraining.Source: Appendix B · pp. 16–17

A. FedZOO-S Stability and Exact Unlearning

• Theorem 1 establishes sample-level TV stability for FedZOO-S under the stated dataset and parameter conditions.The stability bound follows a coupling of the complete training states and bounds their disagreement probability.Source: A. FedZOO-S Stability and Exact… · p. 18
• FedZOUL-S keeps the unaffected trajectory prefix and replays from the first affected mini-batch, yielding the retained-data state law after deletion.If no hit occurs before the request, the existing state can be kept; sequential guarantees cover non-adaptive single-sample request streams.Source: A. FedZOO-S Stability and Exact… · p. 18
• For sequential FedZOUL-S requests, the expected number of replays is bounded by the sum of request-specific trigger bounds, and the probability of any replay is bounded by their union bound.Under the stated conditions, these bounds are at most kρ and min{1, kρ}, respectively.Source: A. FedZOO-S Stability and Exact… · p. 19

B. FedZOO-NS Stability

• Only the q clean coefficients associated with the deleted sample can change under matched sample–seed ordering, and each lies in [−C/(bq), C/(bq)].The comparison tracks the seed-coordinate increment because model and accumulator updates are deterministic once that increment is fixed.Source: B. FedZOO-NS Stability · p. 20
• Theorem 3 establishes an output total-variation stability bound for FedZOO-NS, conditionally on the seed pool and also after averaging over it.The proof accumulates one-step divergence across rounds before applying data processing and Pinsker’s inequality.Source: B. FedZOO-NS Stability · p. 21
• The noise-level corollary chooses Gaussian noise to achieve target sample-level TV stability ρ under its stated dataset conditions.The bound reflects both the chance the affected client participates and the deleted sample enters its mini-batch, and the overlap of the resulting noisy updates.Source: B. FedZOO-NS Stability · pp. 21–22
• When a deleted sample changes an update, Gaussian noise leaves overlap between the old and retained-data update distributions, allowing coupling to keep executions together.At an affected step, rejection sampling first tries to preserve the old noisy coefficients; reflection supplies the correct retained-data update if rejection occurs.Source: B. FedZOO-NS Stability · p. 22

C. FedZOUL-NS Exact Unlearning

• At an affected step, rejection–reflection coupling gives the noisy coefficients the retained-data transition law, leaving the model and accumulator unchanged when the test accepts.The retained mini-batch and seed assignments are coupled as well, so the resulting saved local information and post-update variables have the correct law.Source: C. FedZOUL-NS Exact Unlearning · p. 23
• Theorem 4 guarantees that after a valid single-sample deletion, the complete returned state jointly matches the distribution from retraining FedZOO-NS on retained data, for every σρ > 0.The joint guarantee covers the reconstructed model, accumulators, sampled clients and mini-batches, sample–seed correspondences, noisy coefficients, and all other maintained state.Source: C. FedZOUL-NS Exact Unlearning · p. 23
• The replay probability is bounded by summing per-position first-rejection probabilities, with the bound applying before current Gaussian noise and the acceptance uniform are exposed.A rejection at the deletion endpoint is included because that endpoint may still require correction.Source: C. FedZOUL-NS Exact Unlearning · pp. 23–24
• For a valid non-adaptive stream of k deletion requests, Corollary 3 bounds expected rejections by kΓNS and the probability of any rejection by min(1, kΓNS).A rejection includes one at the request endpoint, even when no later position remains to rerun.Source: C. FedZOUL-NS Exact Unlearning · p. 24

D. Unlearning Cost

• Sparse FedZOUL-NS verification uses at most 4q loss evaluations per checked affected position, versus up to 4bq for literal full-vector recomputation.Only the q deleted-sample and q replacement central-difference pairs can change under the sample–seed correspondence.Source: D. Unlearning Cost · p. 25
• Gaussian acceptance can avoid rerunning an affected update and all subsequent training, although verification adds cost and replay length alone does not determine communication.FEDZOUL-NS may check affected updates without rejecting, incurring checkpoint downloads with no training-step replay; a final-round rejection can require correcting aggregation even without later local steps.Source: D. Unlearning Cost · pp. 26–27
• Per-operation arithmetic includes O(Kd) model reconstruction, O(bqd + K) local-step reruns, O(qd + q) sparse NS checks, and O(mK) server aggregation.Combining these costs with expected checked updates, rerun positions, visited round blocks, and repeated aggregations gives aggregate expected arithmetic work; direct chronological search can take O(bTul) comparisons.Source: D. Unlearning Cost · p. 28
• Replay-length and oracle-cost comparisons alone do not establish which method has lower total unlearning time.Aggregate work also includes model reconstruction, saved-state access, communication, and synchronization; the S TV parameter bounds expected query fraction, while NS final-model TV and transitionwise replay probability are different quantities.Source: D. Unlearning Cost · p. 28
• The finite shared seed pool confines updates to the span of its perturbation directions, prompting convergence analysis in seed coordinates and conditions for controlling the full model-space gradient.The objective being evaluated remains unchanged.Source: D. Unlearning Cost · p. 28

E. Fixed-Seed Parameterization

• Every model lies in the affine space generated by the shared seed directions, restricting reachable models rather than changing the federated objective.The accumulated seed coefficients serve as optimization variables in this parameterization.Source: E. Fixed-Seed Parameterization · pp. 28–29
• The convergence quantity is the squared full gradient measured along the shared seed directions, with no separate surrogate objective.The restricted-objective gradient has a direct full-space interpretation.Source: E. Fixed-Seed Parameterization · p. 29
• A query along a fixed seed direction is a coordinatewise central difference of the parameterized original loss.The shared seed pool defines the perturbation directions, and the accumulator update gives the corresponding step in these coordinates.Source: E. Fixed-Seed Parameterization · pp. 28–29
• For FedZOO-NS, independent mean-zero scalar Gaussian noises contribute to the conditional second moment without cross terms from repeated seed coordinates.Clipping adds bias in the noisy learner, while finite-difference error is bounded under sample-wise smoothness.Source: E. Fixed-Seed Parameterization · pp. 29–30

F. Convergence in the Seed Subspace

• The analysis assumes smooth sample losses, a lower-bounded objective, bounded client-gradient heterogeneity, and bounded update bias, variance, and second moment.The result concerns the full gradient projected onto the shared seed span.Source: F. Convergence in the Seed Subspace · pp. 30–31
• The convergence result controls average projected stationarity across training checkpoints for either learner under the stated utility regularity conditions.The guarantee is conditional on the realized seed pool; the theorem does not establish the same bound for the final iterate or an adaptively chosen checkpoint.Source: F. Convergence in the Seed Subspace · pp. 30, 31, 33
• The bound includes an optimization term that decreases with more rounds and local steps, while finite-difference and clipping bias do not vanish through longer training.Averaging over participating clients reduces centered local variation, while more local steps can increase heterogeneity and local-drift terms; Gaussian noise also enters the last two quantities for FedZOO-NS.Source: F. Convergence in the Seed Subspace · pp. 32, 34
• For a Gaussian seed pool, the deterministic step-size corollary guarantees the bound with probability at least 1 − δ over the pool, conditional on that pool.An unconditional expectation additionally requires the global moment condition; without it, the result is not a high-probability statement about training noise.Source: F. Convergence in the Seed Subspace · pp. 33–34

+ LZEG2

• The balanced stepsize equates the leading finite-horizon and stochastic terms, subject to the stepsize condition.If the balancing choice exceeds 1/(4LZE), the boundary value can be used instead.Source: + LZEG2 · p. 34
• For fixed E, the leading stochastic term gives linear client speedup in communication rounds while it dominates bias and higher-order local drift.The speedup is not a global asymptotic statement; local drift and nonvanishing bias eventually become limiting.Source: + LZEG2 · p. 34
• Full client participation removes the client-sampling heterogeneity term because χM = 0.Source: + LZEG2 · p. 34
• For FEDZOO-NS, Gaussian variance required for stability can leave a residual that does not shrink with mER.The variance and second-moment bounds inherit the horizon dependence of σρ and should not be treated as fixed asymptotic constants.Source: + LZEG2 · p. 35

G. From Seed-Subspace to Full-Space Guarantees

• For an independent Gaussian pool and fixed gradient subspace, Proposition 2 gives simultaneous coverage with probability at least 1 −δ when αK,r,δ < 1.The guarantee applies uniformly over the subspace, including when optimization iterates depend on the same seed pool.Source: G. From Seed-Subspace to Full-Space… · p. 35
• A rank-deficient seed span cannot guarantee full-space stationarity for arbitrary smooth objectives; gradient coverage along the training trajectory is necessary.A low-dimensional seed span may be orthogonal to a nonzero component of the full gradient.Source: G. From Seed-Subspace to Full-Space… · pp. 35–36
• After unlearning, the returned state has the law of a fresh run on retained data, so the convergence theorem applies without a separate unlearning-error term.Only the objective and its data-dependent constants change after deletion.Source: G. From Seed-Subspace to Full-Space… · p. 36

H. Utility After Unlearning

• Utility after unlearning requires assumptions and gradient coverage for the retained-data trajectory; the original objective’s coverage alone is insufficient.The seed pool and hyperparameters are inherited, while other constants may change after deletion.Source: H. Utility After Unlearning · pp. 36–37