Fixing Normalization Statistics to Rank Architectures in Federated Search

Searching for a neural network design across many devices, without moving their private data, usually works like this. Train one large "supernet" whose weights are shared by thousands of candidate sub-networks. Then rank the candidates by reading off how well each one performs using those shared weights. This proposal argues that, when the devices hold different kinds of data, much of what goes wrong in that ranking step has a narrower cause than usually assumed. The supernet weights are not necessarily bad. The problem is the batch normalization layers, which rescale each layer's activations using a mean and variance. Those statistics are computed on the wrong data. Each candidate needs its own statistics, and in a federated setting the "right" statistics are the ones pooled over all clients, which no single client can compute.

We propose a cheap, forward-only procedure that fixes this at evaluation time. It runs for a chosen number of communication rounds. In each round, every client pushes all candidate sub-networks through a small amount of local data and reports per-channel sums and sums of squares. The server adds these up into exact global statistics. Iterating this makes the statistics exact one layer deeper per round, and it is shared across all candidates at once. The research question is whether a few rounds of this recover ranking quality close to what centralized search would achieve. A second question is how much of the known gap between federated and centralized architecture search turns out to be a normalization problem rather than a problem with the shared weights.

Core Claim

In federated weight-sharing search under non-IID data (data that differs in distribution from client to client), we expect the ranking error between candidate architectures to have two separable sources: the shared weights, and the normalization statistics used to evaluate each candidate. The second source should be large under label skew and removable at a communication cost of a few forward-only rounds. Two consequences would follow if this holds. First, a federated supernet could rank NAS-Bench-201 candidates close to as well as a centrally trained one. Second, the recalibration budget, which is a number of rounds, would become an explicit knob trading communication against ranking quality.

Where This Sits in Prior Work

Evidence that the gap exists. Why Batch Normalization Damage Federated Learning on Non-IID Data? shows that batch normalization (BN) fails in federated training through a "dual mismatch": client-specific forward statistics and contradictory backward gradients. FedAvg (the standard averaging of client models) with BN drops to 45.9% on extreme non-IID CIFAR-10. Their fix, FedTAN, recovers 87.6% by synchronizing means and then variances with the server inside every training iteration. We reuse the idea that global moments can be assembled exactly from client sums. We apply it only at evaluation time, forward-only, and for many candidates in one exchange, rather than at every training step for one model.

NAS-Bench-201 reports that, even in centralized search, whether candidates are evaluated with batch statistics or tracked running statistics changes their rank order. That makes normalization a first-order factor in ranking. Neither paper studies the two effects together.

Federated search methods that leave normalization unexamined. Three systems define the federated search setting:

  • FedNAS jointly aggregates architecture weights and network weights. It reaches 81.24% versus 77.78% for FedAvg on non-IID CIFAR-10.
  • FedorAS trains a supernet with single-path sampling, aggregation weighted by how often each operator was used, and an evolutionary search per device tier.
  • SuperFedNAS decouples supernet training from search. It ranks with a learned predictor fit to supernet evaluations.

All three evaluate or predict candidate quality from supernet forward passes, and none says how normalization statistics are set for each candidate under client skew. Our work does not replace their training procedures. It measures and repairs the evaluation step they all depend on. If their evaluations use mismatched statistics, the repair should improve all of them.

Methods we reuse, and constraints on the design.

  • FedBN keeps BN local per client. This works under feature shift (about 71% vs 62% on SVHN), but the dual-mismatch paper reports it falls below 20% under extreme label skew. This rules out "just use local statistics" as an evaluation rule in the label-skew regime.
  • FIXBN freezes globally accumulated statistics halfway through training (76.56% vs 53.97% for standard BN and 59.69% for Group Normalization on extreme non-IID CIFAR-10). In a supernet, however, the accumulated statistics mix over all sampled sub-networks, so they are correct for none of them in particular. FIXBN is therefore a natural training-side baseline that our evaluation-side fix should complement.
  • BN-NAS ranks sub-networks by summed BN scale parameters, with no forward pass. That is the cheapest possible competitor, but it was validated only on centralized IID data, where the scale parameters are not absorbing client bias.

Research Program

The recalibration procedure. Fix a trained supernet and a set of $K$ candidate sub-networks to be ranked. Each client $c$ holds $n_c$ local evaluation samples. In round $r$, client $c$ runs every candidate forward, normalizing each BN layer $\ell$ with the current server statistics. Layers the server has not yet resolved use local batch statistics. The client returns, for each candidate and channel, the sum $S^{(1)}_{c,\ell}$ and the sum of squares $S^{(2)}_{c,\ell}$ of that layer's pre-normalization activations. The server then forms

$$\mu_\ell = \frac{\sum_c S^{(1)}_{c,\ell}}{\sum_c n_c}, \qquad \sigma^2_\ell = \frac{\sum_c S^{(2)}_{c,\ell}}{\sum_c n_c} - \mu_\ell^2,$$

which are the exact pooled mean and variance of layer $\ell$'s inputs, given the statistics used upstream.

Exactness propagates one layer per round. Layer 1's statistics are exact after round 1, because its inputs do not depend on any normalization. If layers $1,\dots,r-1$ already have exact statistics, then layer $r$'s inputs are exactly what centralized evaluation would produce, so its pooled moments are exact after round $r$. A network with $L$ BN layers is therefore exactly recalibrated after $L$ rounds. The empirical question is how fast the ranking error falls for $r \ll L$.

Cost. Each round costs every client one forward pass per candidate on a few hundred samples. It uploads $2K$ times the total channel count in floats. Candidates that share a prefix of layers share the computation for that prefix. Because the server only needs sums, the exchange is compatible with secure aggregation, so per-client moments need not be revealed.

The decomposition study. For a supernet trained federatedly under a given partition, we compare its rankings under four ways of setting the statistics:

  • client-local statistics;
  • server-averaged running statistics, which is the FedAvg default;
  • an oracle that recalibrates on the pooled data in simulation;
  • our method at budgets $r \in \{1, 2, 4, L\}$.

We also train the same supernet centrally on IID data and evaluate it with oracle statistics. Two gaps then separate the error sources. The gap between the centrally trained supernet and the federated supernet, both under oracle statistics, is the weight effect. The gap between oracle and naive statistics on the federated supernet is the normalization effect.

Baselines

Naive reference point: FedAvg running statistics. This is what a supernet trained with ordinary FedAvg uses by default: candidates are evaluated with server-averaged running BN statistics. It is the "do nothing" reference. Any useful method must beat its rank correlation by a margin larger than the seed-to-seed variation across three supernet seeds.

Zero-cost proxy ensemble. The strongest existing training-free competitor is the voting ensemble of synflow, jacob_cov and snip from Zero-Cost Proxies for Lightweight NAS. It reports a Spearman rank correlation of 0.82 on NAS-Bench-201 in the centralized setting. We will run it federatedly in two variants: scores computed on each client's local batch and averaged, and scores computed with pooled gradients. Both use the same per-client sample budget as our method.

This is the most serious threat to the proposal. A supernet costs training and the proxies do not, so the federated supernet is only worth its cost if our recalibrated ranking clearly exceeds the federated proxy ensemble. It should also be at least competitive with the 0.82 centralized reference.

BN-NAS indicator. The BN-NAS scale-parameter indicator is applied to a federatedly trained frozen-weight supernet. It isolates whether a forward-free normalization signal survives client skew. No reported result was found on Lacuna for BN-NAS on NAS-Bench-201 or in any federated setting.

FIXBN-trained supernet. A supernet trained with FIXBN-style frozen global statistics and evaluated with those frozen statistics tests whether fixing statistics during training makes evaluation-time repair unnecessary. As a combined arm, we also apply our recalibration on top of FIXBN training.

Strongest federated search system. We will retrain SuperFedNAS's predictor-based ranking, and FedorAS's evolutionary search, on supernet evaluations with naive and recalibrated statistics. This tests whether the fix transfers to their pipelines. No reported rank-correlation result was found on Lacuna for either system. Their reported gains (up to 37.7% accuracy and +11.6% respectively) are end-accuracy comparisons on their own spaces, so they are not directly comparable.

Ablation of the key ingredient. The ablation varies the round budget $r$. The $r=1$ arm is plain one-shot moment averaging, which is exact only at the first layer. The oracle arm bounds what any statistics fix can achieve.

Fairness controls. Every arm uses the same trained supernet weights, the same partitions, the same per-client evaluation sample count and the same set of candidate sub-networks. Communication and client compute are reported for each arm.

Why not just…?

Why not just replace BN with Group or Layer Normalization throughout the search space? These normalizations compute statistics within each sample rather than across a batch, so client skew cannot corrupt them. But they change the search space whose rankings we want, and NAS-Bench-201 shows that normalization treatment alone reorders candidates. FIXBN also reports Group Normalization at 59.69% against 76.56% for frozen BN on extreme non-IID CIFAR-10. We will still run a Group Normalization supernet as an arm, scored against its own centrally trained ground truth on a 200-architecture sample. If it ranks as well as recalibrated BN at no communication cost, that is a legitimate negative result for our method and we will report it as such.

Why not just remove normalization, as FedWon does? FedWon replaces normalization with standardized convolution weights plus adaptive gradient clipping, and reaches 75.6% versus 71.4% for FedBN on Office-Caltech-10. It has not been shown to train stably across a mixed operation space with skip, pooling and convolution branches. Its accuracies also do not correspond to NAS-Bench-201's ground truth, which assumes BN. We include it only in the 200-architecture side study, where it is judged against its own ground truth.

Why not just average clients' running statistics once? This is the strongest cheap alternative. It is exact at the first layer and approximate below. If a single round matches the oracle, the multi-round procedure adds nothing, and the contribution reduces to the decomposition finding plus "average moments once." The round-budget curve settles this directly. We expect a gap mainly under label skew, where deeper-layer activations are class-specific, and little gap under mild Dirichlet skew. Reporting where the $r=1$ arm suffices is part of the deliverable rather than a threat to hide.

Why not just use a data-free proxy such as synflow? It cannot be corrupted by client data, but for that same reason it cannot reflect the task. Abdelfattah et al. find single proxies trail the 0.82 ensemble. Our federated proxy arm measures the cost of this blindness directly.

Proposed Experiments

Setting. The search space is NAS-Bench-201, with its precomputed accuracies on CIFAR-10, CIFAR-100 and ImageNet-16-120 as ground truth (the best cell reaches 94.37%, 73.51% and 47.31% respectively). We train single-path supernets with 20 and 100 clients and partial participation. Partitions are Dirichlet label skew at concentration 0.1, 0.5 and 100, plus the extreme two-classes-per-client split used in the BN papers.

Metrics. We report:

  • Kendall and Spearman correlation against ground truth over 1,000 sampled candidates;
  • the ground-truth accuracy of the top-1 and top-10 selected candidates, as regret from the best cell;
  • upload volume and client forward passes per ranking.

Feature skew. For feature skew we build a Digits federation with one domain per client. Because NAS-Bench-201 has no Digits ground truth, we centrally train 200 sampled cells to obtain one.

Decisive checks. Three results determine the outcome:

  1. The normalization effect, measured as oracle minus naive correlation on the federated supernet, should be large under label skew and small near IID. If it is small everywhere, the core claim is false.
  2. A budget of $r \le 4$ should reach most of the oracle's correlation.
  3. Recalibrated supernet rankings should exceed the federated zero-cost ensemble, and should improve the candidates SuperFedNAS-style predictors select when those predictors are refit on recalibrated evaluations.

Failing the third check would mean federated weight sharing is not worth its training cost for ranking, even with correct statistics. That is a finding worth publishing as well.