Learning Where to Perturb: Shared-History Subspaces for Seed-Based Federated Zeroth-Order Fine-Tuning

Fine-tuning a language model on phones or IoT gateways runs into two limits. Backpropagation needs to store every intermediate activation, and federated averaging sends the full model, of dimension $d$, every round. Zeroth-order methods remove both limits. They estimate a gradient from two forward passes along a random direction, so no activations are stored. If every device generates that direction from a shared random seed, a device only needs to upload one number per step. DeComFL used this idea to cut communication for OPT-1.3B on SST-2 from 1.27 TB under FedAvg to 0.24 MB. The cost is noise. A random direction in a billion-dimensional space carries very little information about the gradient, so zeroth-order training needs many more steps than backpropagation. The "dimension-free" guarantees rescue this only when the loss has low effective dimension, meaning only a few directions actually matter.

This note proposes to find those few directions without spending any extra communication. Every device in a seed-based federated system already holds the same public record: the list of seeds and the scalar gradient projection returned for each. That record is a randomized sketch of the gradient history. Each device can therefore compute, deterministically and identically, a small left and right subspace for each weight matrix. Future random directions are then drawn mostly inside that subspace. Communication stays at a few scalars per round. Only the shape of the random directions changes: they stop being isotropic and follow the low-rank structure that the Muon analyses suggest weight-matrix gradients have.

Core Claim

Isotropic perturbations pay for the full dimension $d$ even when the gradient lives in a small subspace. That subspace can be estimated from the shared seed/scalar history alone, at zero added communication. Drawing perturbations from it should make the number of rounds to a target accuracy close to independent of model size, which current seed-based methods only promise under an assumption. Concretely, for a weight matrix $W \in \mathbb{R}^{m\times n}$ the perturbation is

$$ P = \sqrt{1-\alpha}\; U A V^\top + \sqrt{\alpha}\; Z , $$

where $U \in \mathbb{R}^{m\times k}$ and $V \in \mathbb{R}^{n\times k}$ are orthonormal bases computed from the shared history, $A$ is a $k\times k$ Gaussian matrix drawn from the round's seed, $Z$ is a full $m\times n$ Gaussian drawn from the same seed, and $\alpha$ is the fraction of the budget kept for exploring directions outside the subspace. The gradient estimate is the usual two-point difference $\big(f(W+\mu P)-f(W-\mu P)\big)/(2\mu)$ times $P$, with smoothing radius $\mu$.

The analysis aims to show a stationarity bound in which the dimension term is $\sum_\ell k^2$ over layers, not $d$, plus a bias term. The bias term is proportional to $\epsilon$, the fraction of gradient energy lying outside the current subspace, and the isotropic fraction $\alpha$ keeps it from becoming permanent.

The approach has a real weakness, which the experiments must measure: finding the subspace has a warm-up cost. The sum $\sum_t s_t Z_t$ of past scalar-weighted directions has signal of size about $T\|G\|_{op}$ after $T$ samples. Its noise has spectral norm about $\sqrt{T}(\sqrt m+\sqrt n)\|G\|_F$, because a Gaussian $m\times n$ matrix has spectral norm near $\sqrt m+\sqrt n$. The top singular vectors are therefore recoverable roughly once

$$ T \gtrsim (m+n)\,\rho, \qquad \rho = \|G\|_F^2/\|G\|_{op}^2 , $$

where $G$ is the matrix gradient and $\rho$ its stable rank. For a 2048×2048 matrix with stable rank 4, this is about 16k scalar samples. That is far fewer than the $mn \approx 4$M a dense method implicitly needs. It is also large enough that pooling across clients and rounds matters, and that gradient drift between rounds could defeat the method.

Relation to Prior Work

Three papers motivate the proposal by showing that the gradient has exploitable low-dimensional structure. Unlocking Black-Box Prompt Tuning Efficiency via Zeroth-Order Optimization proves that zeroth-order SGD depends on an effective dimension, and measures it as low as 131 against an ambient dimension of 38,400. On the Convergence of Muon and Beyond and Convergence of Muon with Newton-Schulz analyze an optimizer that treats each weight matrix as a matrix rather than a flat vector, and show bounds that depend on matrix rank rather than $d$ (an $r^{1/4}$ versus $r^{1/2}$ improvement over momentum SGD). Those results assume first-order gradients on server GPUs. This proposal borrows their matrix view to design perturbations, not updates.

Two lines of work supply the protocol and set the bar. DeComFL supplies the seed-and-scalar federated protocol and the trick of rebuilding the model on-device by replaying history. It uses isotropic directions and treats low effective rank as an assumption rather than something to exploit. HO-SFL reduces the dimension penalty differently: it puts the heavy layers on a server trained with backpropagation, so zeroth-order noise only scales with the client layers. That requires sending cut-layer activations upstream and running a capable server.

Three methods reduce dimension with a fixed or heuristic choice of what to perturb, which is what this proposal replaces with a learned choice. Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization perturbs a random sparse subset of coordinates and freezes the rest, so its bound depends on the subset size. ZOTTA picks layers by how well their features cluster across domains. PseuZO uses the analytic gradient of the loss with respect to model outputs, together with a zeroth-order estimate of the output Jacobian. It needs about twice MeZO's runtime and has not been tested in a federated setting.

Two results constrain the design. On-Device Fine-Tuning via Backprop-Free Zeroth-Order Optimization reports that MeZO depends heavily on good prompts to land in a low-effective-rank basin, so all experiments use prompted fine-tuning. On the Convergence Rate of LoRA Gradient Descent shows that factorized $BA$ parameterizations lose smoothness and converge only at $O(1/\log T)$. This is why the proposal perturbs the full weight matrix inside a subspace, rather than training a factorized adapter.

Research Program

The algorithm has three parts. The first is the per-round protocol, inherited from DeComFL: the server broadcasts a seed, clients return scalar projections, and every party appends them to the shared history.

The second is a subspace refresh, run every $R$ rounds. Each device runs a few steps of randomized power iteration on the implicit momentum matrix $M = \sum_t \beta^{T-t} s_t P_t$ for each weight matrix, over a sliding window. A product $Mx$ is computed by regenerating each $P_t$ from its seed and accumulating $s_t P_t x$ column-block by column-block, so $M$ is never stored. Peak memory beyond inference is about $k(m+n)$ per matrix, which is smaller than a rank-$k$ LoRA adapter. Because the input is identical everywhere, every device computes bit-identical $U,V$, which requires fixed-order reduction and deterministic random-number generation. The refresh can also run once on the server's CPU and be checked against clients' copies by hash.

The third is the convergence analysis. It extends the DeComFL proof to the mixed perturbation above, separates the in-subspace variance term from the out-of-subspace bias, and formalizes the warm-up threshold.

Two edge-specific questions are studied alongside. One is replay cost for clients that reconnect after missing rounds: they must replay the scalars and also recompute any refreshes they missed. We will measure whether storing only the latest $U,V$ checkpoint, downloaded once at $O(k(m+n))$ cost, beats full replay. The other is whether the method still works when forward passes run in INT8 as in ZOTTA. That test is secondary, and we report it only if the main result holds.

Baselines

The naive reference point is DeComFL itself: isotropic Gaussian seeds, the same number of clients, perturbations per step $P$, rounds, and forward-pass budget. The file reports its communication (0.24 MB versus FedAvg's 1.27 TB on SST-2 with OPT-1.3B) but only says its accuracy is "comparable"; no reported accuracy number was found on Lacuna for DeComFL. We will therefore rerun it. Beating it means reaching the same final accuracy in at least 2× fewer rounds, or higher accuracy at equal rounds, with communication per round unchanged.

The strongest single-device dimension-reduction competitor is PseuZO. The file reports 91.2% on SST-2 with OPT-1.3B against MeZO's 82.4% under identical computation time PseuZO. We will port PseuZO's estimator into the seed protocol with the same wall-clock budget and the same tuning budget, a fixed grid of 12 configurations per method. Because its sliding window stores output tensors, we will report peak memory alongside accuracy. Matching PseuZO's accuracy at lower runtime, or exceeding it at equal runtime, counts as a win; losing to it at equal runtime is a negative result we will report.

The strongest split-architecture competitor is HO-SFL, which the file reports at 4.14 GB VRAM for LLaMA-3.2-1B against 4.01 GB for inference. It is run with its own server-side backpropagation. Since it uses strictly more infrastructure, the fair comparison is accuracy per byte of upstream traffic, with activation traffic counted.

Zeroth-order training on LoRA adapters, with seed sharing, gets the same rank $k$ and tuning grid. No reported result was found on Lacuna for this combination.

Two ablations isolate the key ingredient. The first draws $U,V$ fresh at random at each refresh instead of from history; this separates "perturb a low-rank matrix subspace" from "perturb the right subspace." The second uses an oracle $U,V$ computed from true backpropagation gradients, which bounds how much the history estimate leaves on the table. A sweep over $\alpha$ and $k$ completes the set.

Why not just…?

Why not just run zeroth-order updates on LoRA adapters? This is the most serious threat. It also cuts the perturbed dimension to $k(m+n)$ per matrix and needs no subspace estimation. The difference is that the LoRA subspace is set at initialization and never moves toward the gradient. Its factorized form is also non-smooth, which slowed even first-order convergence to $O(1/\log T)$ in On the Convergence Rate of LoRA Gradient Descent. If zeroth-order LoRA matches history-shaped perturbations at equal $k$, the claim fails and we will say so. The random-subspace ablation shows whether any gain comes from where the subspace points rather than its size.

Why not just use more perturbations per step? Variance falls like $d/P$, so multiplying $P$ works, but the forward-pass cost grows linearly. ZOTTA already needs about 10 forward passes per step, and that latency is the edge bottleneck. We will plot accuracy against total forward passes. History-shaped perturbations must sit strictly above the isotropic curve at every $P$; otherwise the cheaper fix wins.

Why not just choose layers or coordinates heuristically, as ZOTTA and sparse perturbation methods do? These cut dimension without estimation cost, and on CIFAR-10 sparse perturbation shrank the active space from 4.3M to about 62k parameters while beating dense baselines Sparse Perturbations. But they select whole coordinates or layers, while the Muon analyses point to low-rank structure inside each matrix that coordinate masks cannot capture. We will run sparse perturbation with the same number of perturbed degrees of freedom; the comparison settles which structure matters for language-model fine-tuning.

Why not just add Adam preconditioning to zeroth-order estimates? DeComFL lists this as open. But coordinate-wise second moments of isotropic zeroth-order estimates are dominated by perturbation noise. A Tale of Two Geometries also argues that dimension-free behavior comes from matching the noise model to the geometry, not from per-coordinate scaling. We include ZO-Adam with replay-computed state as an extra baseline, at a cost of $2d$ device memory, to test this directly.

Proposed Experiments

The main testbed follows DeComFL and the MeZO line. We fine-tune prompted OPT-125M, OPT-1.3B and OPT-6.7B, plus LLaMA-3.2-1B, on SST-2, BoolQ, MultiRC and RTE. We use 8 to 64 simulated clients, with IID splits and Dirichlet-skewed label splits. Metrics are accuracy against rounds, accuracy against total forward passes, bytes per round, peak device memory, and replay time for reconnecting clients. Device-side timing is measured on an NVIDIA AGX Orin, the edge board used by AsyncFGD.

The first decisive check is a scaling test. We hold the task fixed and grow the model from 125M to 6.7B parameters, then plot rounds-to-target-accuracy. Dimension-free behavior predicts a flat curve for history-shaped perturbations and a rising one for isotropic DeComFL. If both are flat, the low-rank structure is already free and the proposal adds little.

The second check tests the mechanism. We log the out-of-subspace energy fraction $\epsilon$, using occasional offline backpropagation probes, and the measured warm-up length. We then test whether the gap to DeComFL shrinks where $\epsilon$ is large and whether warm-up follows the $(m+n)\rho$ prediction.

The third check covers skewed client data. The shared subspace pools all clients' gradients, so it may help by averaging out or hurt by suiting no one. We compare it against a variant that keeps a per-client subspace and uploads a few extra scalars.

The fourth check is ImageNet-C test-time adaptation with ViT-Base under ZOTTA's protocol, where ZOTTA reports 66.6%. It tests whether the idea transfers to vision. We run it only after the language results are settled.