Federated learning asks clients to train a shared model by sending updates to a coordinating server, and this design fails in two well-documented ways at once. The updates themselves leak: because a network is a deterministic differentiable machine, an adversary who sees a client's gradient can run it backwards and reconstruct the client's training images or text — a gradient inversion attack. And the server is a single point of failure: it can drop updates, poison the model, or reconstruct data itself. Zeroth-order (ZO) optimization — training using only forward passes and random parameter nudges, never backpropagation — looks like a fix for both, since a client can compress its entire round of work into a few scalar loss numbers. But two problems block this route in practice: random-direction search degrades sharply as parameter count grows (the curse of dimensionality), and every existing federated ZO system still funnels those scalars through a central server.
This proposal argues that the missing piece is architectural. Networks built entirely from additions and multiplications — "fully polynomial" networks, developed so that encrypted computation can run them — have an algebraic rigidity that standard ReLU or GELU networks lack: for a fixed input, every weight gradient in such a network provably lives in a tiny subspace that can be computed during the forward pass and then thrown away. That fact lets us confine ZO search to that subspace, largely escaping the dimensionality curse; it collapses each client's federated payload to a handful of scalars independent of model size; and scalars, unlike gradient vectors, can be averaged by peers gossiping with each other, with no server at all. The result is one system in which the architecture fixes the optimizer, the optimizer fixes the communication, and the communication fixes the trust model.
Core Claim
The claim has three parts, and the first is a structural theorem. Take the polynomial feedforward block used in Activation-Free Backbones for Image Recognition, which builds PolyNeXt — a vision network with no pointwise non-linearities, where a feedforward layer is a Hadamard product of two linear projections. For the layer $y = W_o(u \odot v)$ with $u = W_a x$, $v = W_b x$, and error signal $\delta_i = \partial \mathcal{L}/\partial y_i$ on training sample $i$ of a local batch of size $B$, the weight gradient is
$$\frac{\partial \mathcal{L}}{\partial W_a}=\sum_{i=1}^{B}\big(W_o^{\top}\delta_i\odot v_i\big)\,x_i^{\top},$$
a sum of at most $B$ rank-one matrices. The same holds for $W_b$ and $W_o$: every weight gradient in a multilinear network has its row and column spaces confined to spans of forward-pass activations, of dimension at most $B$ — the local batch size — regardless of parameter count $d$. AGZO proved this confinement for plain linear layers but must fall back to isotropic random noise at every non-linear site (GELU, LayerNorm, softmax), which is where most transformer parameters sit; a fully polynomial network has no such sites, so the confinement covers the entire model. The ZO consequence is that two-point finite-difference estimates taken along random directions inside these activation subspaces have estimation error scaling with the subspace dimension, on the order of $B^2$, rather than with $d$ — the standard dimension-scaling barrier documented for isotropic ZO methods by Huang et al. and Liu et al.. Smoothness helps twice over: ReLU kinks inject noise into finite differences, while polynomial networks are infinitely differentiable.
The second part is a systems claim. Because the perturbation directions are derived from shared pseudo-random seeds and activation sketches, each client transmits only scalar loss differences plus a small sketch — a payload of $O(1)$ in $d$ per round, in the regime DeComFL opened (0.24 MB total transfer versus roughly 1.27 Terabytes per client for FedAvg on SST-2 with OPT-1.3B). Scalars this small can be averaged by gossip over a peer-to-peer graph rather than collected by a curator, importing the privacy amplification that Muffliato established for gossip averaging, or sharded across several aggregators in the manner of ERIS so that no single aggregator sees the full stream.
The third part is deliberately uncomfortable. We do not claim the scalar stream is private by construction: On the Inherent Privacy of Zeroth-Order Projected Gradient Descent proves that ZO randomness provides no differential privacy whatsoever, and Gradient Inversion Attacks Beyond SGD shows that any algorithmic transformation of gradients — momentum, adaptive moments — can be inverted by an adversary who tracks the optimizer state. An aggregator who knows the seeds and observes the scalars can in principle pose exactly this kind of update-matching inverse problem. Whether that attack succeeds in practice, and how sharding and gossip blunt it, is an open empirical question this proposal sets out to answer, not to assume away.
Research Program
The first thrust builds the optimizer. We formalize the confinement theorem above for the PolyMLP, PolyConv, and PolyAttn blocks of PolyNeXt, which supplies the architecture (and reports 82.7% top-1 ImageNet accuracy for its fully polynomial BatchNorm variant, plus 30–45% lower peak GPU memory than comparable MetaFormer models — our first-order accuracy ceiling). One honest technical wrinkle: normalization sites. PolyNeXt's polynomial-compatible BatchNorm replaces the divisions in standard normalization with factorized arithmetic; we prove exact confinement for all multilinear sites and bound the perturbation-coverage error attributable to the normalization approximations. On top of the theorem we build Poly-ZO: extract each layer's activation subspace by an on-the-fly power iteration during the forward pass (as AGZO does), discard the activations immediately, and draw two-point finite-difference directions only within the combined row/column spans. Peak memory should match inference, as it does for AGZO.
The second thrust builds the aggregation layer. Two designs, both serverless. In the gossip design, clients exchange and average their small coefficient vectors over a random peer graph across rounds, for which Muffliato provides the mixing and amplification analysis. In the sharded design, the seed schedule itself is split across $A$ aggregators so each sees scalars for only its share of perturbation directions — the ERIS idea (mutual information leakage bounded inversely in $A$) transplanted from gradient shards to seed shards. Non-IID client drift, the known weakness of decentralized training, is handled by adapting HiSo's periodic model-reset mechanism, in which clients periodically resynchronize to a state reconstructed from the shared scalar history; HiSo shows this style of history replay supports dimension-independent convergence in the centralized case.
The third thrust runs the attacks. First, a motivation study: SoK: On Gradient Leakage in Federated Learning proves via Input-Gradient Smoothness Analysis that smoother input-gradient landscapes make inversion easier, and polynomial networks are maximally smooth — so polynomial backbones probably leak more than ReLU networks when trained first-order. We measure this directly, because it is the strongest argument for never sending gradients from such networks at all. Second, the scalar-stream inversion attack: an honest-but-curious aggregator with full seed knowledge reconstructs dummy inputs whose simulated scalar sequence matches the observed one, using the update-matching objective of Gradient Inversion Attacks Beyond SGD (which reports up to 6.5 dB PSNR improvement over prior attacks on Adam updates, effective to batch size 16) and, for larger batches, generative priors in the style of Gradient Inversion with Generative Image Prior. We evaluate sharding degree, gossip mixing, and optional calibrated noise on the scalars as defenses, and we state the collusion assumption inherited from ERIS openly: colluding aggregators who pool shards are outside the threat model, exactly as they are for ERIS.
For language models, where no pretrained fully polynomial network exists, we produce one by HEAT-style co-adaptation: HEAT demonstrates that weights can be retrained to absorb polynomial-approximation error cheaply (encrypted GPT-2 124M co-adapted in under seven hours on one A100 with under 2% of the pretraining corpus, raising plaintext top-1 logit agreement from 74% to 83%). We co-adapt OPT at 125M and 1.3B scale, acknowledging that this retrofit, rather than a natively polynomial LLM, is the weakest link in the program; piecewise-spline retrofit alternatives like PUMA do not serve our purpose because their interval selectors reintroduce the non-smooth sites that break subspace confinement.
Baselines
The do-nothing reference is classical FedAvg with first-order backpropagation and no defense: it is simultaneously the accuracy reference, the communication worst case (the 1.27 Terabytes-per-client figure from the DeComFL paper on SST-2 with OPT-1.3B), and the maximal-leakage reference, since raw gradients are the inversion attacker's ideal input.
The strongest existing competitor on the convergence-and-communication question is HiSo, the Hessian-informed scalar-only federated ZO method, which reports a 1.4× to 5.4× speedup in communication rounds over DeComFL and roughly 2.2× faster wall-clock execution than its closest competitor on an H100 GPU. HiSo treats the loss as a black box, so it runs unchanged on any architecture; to make the comparison isolate our architectural ingredient rather than our tuning effort, we run HiSo twice — on a standard-activation network and on our polynomial network — with identical client counts, non-IID partitions, per-round query budgets, and tuning sweeps. Beating HiSo means matching or exceeding its accuracy-per-communication-round curve at equal query budget while additionally removing the central server it requires.
DeComFL is the communication-floor baseline (0.24 MB total transfer on SST-2/OPT-1.3B); we must not exceed its byte budget by more than a small constant while being serverless. For the serverless comparison itself, ERIS is the strongest existing system: it matches FedAvg accuracy while sharding gradients across aggregators, reducing data-reconstruction attacks to unrecognizable noise under two-aggregator sharding (no reported accuracy number found on Lacuna for its CIFAR-10 or MNIST runs). ERIS is first-order, so the fair comparison holds clients, data, and local epochs fixed and asks whether we match its attack resilience while eliminating activation caching and cutting upload size to the scalar regime. On the attack side, the strongest baseline is the update-matching gradient inversion attack with its reported 6.5 dB PSNR gain over HFGI/IG-style attacks on adaptive-optimizer updates, applied to every defense we test. Finally, the key ablation runs Poly-ZO with isotropic perturbations on the same polynomial network — same architecture, same memory, no subspace confinement — which isolates whether the confinement theorem, rather than the architecture or the smoothness alone, is doing the work.
Why not just…?
Why not just use DP-SGD? Differential privacy gives a provable guarantee, and ZO randomness gives none — the inherent-privacy analysis of ZO-PGD is explicit that zero-preserving oracles fail $(\epsilon,\delta)$-DP outright, so we agree and make no such claim. But DP-SGD requires backpropagation and its activation memory: MeZO documents a 12× memory reduction from forward-only training (a 30B model on one 80GB GPU), and standard backprop runs out of memory at the billion-parameter scales we target. Calibrated noise on the scalar stream is complementary, not competing: we include it as one defense configuration in the attack experiments and report the privacy-utility curve it buys.
Why not just quantize gradients to 2 bits and take multiple local steps? This is the most serious alternative, and it may win in some regimes. The SoK on gradient leakage shows 2-bit quantization blocks state-of-the-art inversion attacks at under 5% accuracy cost, and multiple local updates push reconstructions past LPIPS 0.1. If the threat model is a curious-but-otherwise-benign central server and bandwidth is unconstrained, that combination may suffice, and we will report the regime where it does. But it does not address either structural problem: bandwidth remains linear in parameter count (even zkFL's ciphertext expansion, from 497 MB to roughly 982 MB per round for ResNet-50, illustrates the scale; its 55-minute proof generation per aggregation illustrates the cryptographic alternative's cost), and the central server remains a single point of failure for update dropping, poisoning, and outages.
Why not just run MeZO or AGZO on standard networks? MeZO's own success — within 1% of Adam fine-tuning on 7 of 11 tasks at OPT-13B — is explained by the empirically low effective dimension of pretrained loss landscapes (Chen et al.), so isotropic search already works there, given good prompts and many more forward passes than backprop would need. AGZO improves this with linear-layer confinement but reverts to isotropic noise at every non-linear site. This is the threat we take most seriously, and our ablations are designed to settle it rather than argue around it: we measure the fraction of parameters each method's subspace actually covers, and if AGZO-on-GELU matches Poly-ZO's gradient cosine similarity and downstream accuracy at equal query budget and memory, the architectural change is unnecessary and the honest conclusion is that confinement matters only where AGZO's coverage is poor. What the polynomial network offers that the low-effective-dimension argument cannot is a deterministic, architecture-derived guarantee rather than a landscape property that MeZO itself notes is fragile to prompting.
Proposed Experiments and Decisive Checks
The optimization claim is tested first in the centralized setting: Poly-ZO versus MeZO, AGZO, an isotropic-perturbation ablation, and first-order backpropagation (the ceiling, with PolyNeXt's 82.7% ImageNet top-1 for the fully polynomial variant) on CIFAR-10 scratch training and ImageNet-1K fine-tuning of PolyNeXt models. Metrics are top-1 accuracy at matched query budget, cosine similarity between the ZO estimate and the true gradient on held-out batches, and peak GPU memory. No reported result found on Lacuna for ZO training of any polynomial architecture, so this comparison is entirely new ground. The language feasibility check repeats this on the co-adapted polynomial OPT models over SST-2 and SuperGLUE tasks, where the MeZO paper's within-1%-of-Adam result on 7 of 11 tasks serves as the first-order reference.
The systems claim is tested in federated simulation with one hundred clients under Dirichlet non-IID partitions of CIFAR-10 and SST-2, comparing serverless Poly-ZO gossip and sharded variants against FedAvg, DeComFL, HiSo, and ERIS, measuring accuracy per communication round, total bytes transferred, and client peak memory. The privacy question runs throughout: first-order gradient inversion on polynomial versus ReLU backbones (we predict polynomial networks leak more, per the smoothness analysis in the SoK), then scalar-stream inversion against sharding degree, gossip mixing, and scalar noise, with the 2-bit quantization defense as the reference point.
Three checks decide the proposal. Poly-ZO's gradient cosine similarity should substantially exceed AGZO's at matched memory and should stay roughly flat as model width grows, confirming that the confinement, not the ambient dimension, sets the difficulty. Serverless Poly-ZO should match HiSo's rounds-to-accuracy while cutting client memory far below ERIS's backprop requirements and keeping total transfer in DeComFL's megabyte regime. And scalar-stream inversion should degrade measurably as the number of aggregators grows — if instead a seed-knowing aggregator reconstructs inputs as faithfully from scalars as from raw gradients, the privacy story fails, and the contribution narrows honestly to the optimizer and the trust topology.
References
- Activation-Free Backbones for Image Recognition: Polynomial Alternatives for Spatial and Channel Mixing
- AGZO: Activation-Guided Zeroth-Order Optimization for LLM Fine-Tuning
- Zeroth-Order Stochastic Alternating Direction Method of Multipliers for Nonconvex Nonsmooth Optimization
- ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
- Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimization
- Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging
- ERIS: Enhancing Privacy and Communication Efficiency in Serverless Federated Learning
- On the Inherent Privacy of Zeroth-Order Projected Gradient Descent
- Gradient Inversion Attacks Beyond SGD
- Converge Faster, Talk Less: Hessian-Informed Federated Zeroth-Order Optimization
- SoK: On Gradient Leakage in Federated Learning
- Gradient Inversion with Generative Image Prior
- HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation
- PUMA: Secure Inference of LLaMA-7B in Five Minutes
- Fine-Tuning Language Models with Just Forward Passes
- Unlocking Black-Box Prompt Tuning Efficiency via Zeroth-Order Optimization