Predicting Which Architectures Survive Private Federated Training, Before Training Them

In federated learning, many devices train one model together by sending model updates instead of raw data. Those updates still leak data, so the standard defense is differential privacy (DP): each person's gradient is clipped to a maximum length and random noise is added before averaging. The noise costs accuracy. A known and underused fact is that the size of that cost depends heavily on the network's architecture. DPNAS showed that architectures which rank well in ordinary training do not rank well under DP training. Its search, which used a reinforcement-learning controller, found a network reaching 68.33% on CIFAR-10 at privacy budget $(\epsilon,\delta)=(3,10^{-5})$, beating NASNet and DARTS cells by 15–20% under the same constraint. That search, however, trained every candidate in full with noise. In a federated setting, training each candidate also spends the clients' privacy budget, not just GPU hours.

This note proposes a score computed on an untrained network that predicts how well an architecture will train under DP noise and federated averaging. The score is the signal-to-noise ratio of the very first private update. It measures how strongly the clipped per-example gradients agree, compared with the noise DP will add, given the network's parameter count and the clipping threshold. Because a coarse version of the score needs one gradient pass per candidate, it can be estimated from clients at a small, explicitly accounted privacy cost. Architecture search then becomes something a federation can afford in both compute and privacy.

Core Claim

Training-free scores, called zero-cost proxies, already exist. EZNAS evolves formulas over statistics of untrained networks and reaches Kendall's $\tau=0.65$ against trained accuracy on NAS-Bench-201, compared with 0.57 for both NASWOT and Synflow. All of these proxies predict non-private accuracy, which DPNAS shows is the wrong target under DP. None of them refers to the clipping threshold, the noise level, or how gradients from different clients relate.

Our claim is that a large share of the DP utility loss is set at initialization by a single quantity. Let $\bar g_i(a)$ be the clipped gradient of example $i$ for architecture $a$, with clipping norm $C$. Let $B$ be the number of examples aggregated per round, $\sigma$ the noise multiplier, and $P$ a fixed random orthonormal projection to $k$ dimensions. The score is

$$S(a) = \frac{\big\|P\,\tfrac{1}{B}\sum_{i=1}^{B}\bar g_i(a)\big\|^2}{k\,\sigma^2 C^2 / B^2},$$

the expected squared length of the averaged clipped signal divided by the expected squared length of the DP noise in the same $k$ coordinates. The projection approximately preserves the signal's length (by a Johnson–Lindenstrauss argument), so $S$ ranks architectures by how much of the first private step is signal. When clients hold different label distributions, the numerator sums over clients. It therefore rewards architectures whose clipped gradients agree across clients and not only within one client.

The prediction we can falsify is this. Because $\sigma$ appears in the score, $S$ predicts ranking crossovers: specific pairs of architectures should swap order as $\epsilon$ tightens. Non-private proxies cannot predict such swaps by construction. If the score shows no advantage over Synflow, NASWOT or EZNAS at matched cost, the claim fails.

We expect two parts of $S$ to matter most:

  • Clipping. It equalizes per-example contributions, so architectures whose per-example gradients point in many unrelated directions lose more signal.
  • Parameter count. It enters through how much of the noise lands on directions that matter to the update.

This may explain DPNAS's unexplained finding that SELU (an activation that keeps negative values) and max pooling resist noise. Testing that explanation is part of the program.

Relation to Prior Work

The closest work falls into three groups.

Search under privacy that pays full training cost. DPNAS (centralized, reinforcement learning) runs full DP-SGD per candidate and names zero-cost search as open. DPFNAS runs a genetic algorithm with Bayesian hyperparameter tuning locally on each edge client, then shares noised features. It reports 47.28% on non-IID CIFAR-100, 6.82% above PerFedRLNAS, but at the price of repeated local training on constrained devices. DP-FNAS makes differentiable supernet search private using Gaussian DP accounting. It reports 3.4% test error with 8 parties against 2.8% centralized non-private, in 0.59 GPU days, on largely IID splits.

Our proposal does not train candidates, does not train a supernet, and does not search on devices. It replaces all three with a single-pass score whose privacy cost is accounted for.

Search with no privacy at all. FedNAS reaches 81.24% against FedAvg's 77.78% on non-IID CIFAR-10. FedorAS handles device tiers but treats DP as orthogonal. They motivate the federated setting but say nothing about noise.

Work that constrains the design. GI-NAS shows that a training-free architecture score can strengthen gradient inversion even through Gaussian noise. Any client statistic we release must therefore itself be formally private, not merely low-dimensional. This is why the score estimate passes through the DP mechanism instead of relying on obscurity.

NAS-Bench-201 documents that differentiable search collapses toward skip connections. We expect DP noise to make this collapse worse, which is a further reason to avoid supernets here.

Research Program

The program has four parts.

1. A private ground truth. No benchmark reports accuracy under DP-federated training. We will build one on the NAS-Bench-201 cell space with three changes:

  • BatchNorm is replaced by GroupNorm, following DPNAS.
  • The activation becomes a searchable choice among ReLU, SELU and Tanh.
  • Each candidate is trained with DP-FedAvg on CIFAR-10 split across 50 clients by Dirichlet label skew, at $\epsilon\in\{1,3,8\}$ and without DP.

We will sample roughly 1,000 architectures stratified by NAS-Bench-201 non-private rank. This sample also answers, at scale, whether the non-private rank survives DP, which DPNAS showed only on a handful of models. A second, smaller ground truth uses federated PathMNIST and DermaMNIST from MedMNIST, a privacy-relevant domain where a plain ResNet-18 is known to be hard to beat.

2. Scoring with an explicit privacy cost. Each sampled client clips its per-example gradients for a candidate, projects them with a shared random $P$, and contributes to a securely aggregated sum with Gaussian noise. The server subtracts the known expected noise energy to obtain an unbiased estimate of the numerator of $S$. Because the projected sensitivity is still $C$ and the release has only $k$ dimensions, one release per candidate is cheap. Releases compose across candidates under Gaussian DP, as in DP-FNAS.

To keep the number of releases small, a data-free pass prunes the space first. We will use Synflow, which needs no client data, as that pass. Only the top few hundred candidates then receive a private score. The final model is trained with whatever privacy budget remains. We report the total $\epsilon$, so search and training are compared on one privacy bill.

3. Mechanism. On the ground truth we will separate the numerator into within-client and cross-client agreement and check which predicts DP accuracy under label skew. We will also test whether SELU's advantage over ReLU appears in $S$ at initialization.

4. A boundary test. If $S$ ranks well only in the top-heavy middle and fails among the best 10% of candidates, the same weakness EZNAS reports, we will check whether a two-stage design closes the gap at modest extra privacy cost. That design re-scores survivors with a few private training steps.

Baselines

The naive reference is a fixed handcrafted network with DP-friendly choices: a ResNet-18 and a small CNN with GroupNorm and SELU or Tanh, trained with DP-FedAvg using the same clients, rounds, total $\epsilon$ and hyperparameter grid. Unlike every search method, it spends its whole budget on training. Beating it means higher final accuracy at equal total $\epsilon$, averaged over three seeds and the three Dirichlet skew levels.

The strongest existing training-free competitors are Synflow, NASWOT and EZNAS-A, computed on the same candidates. EZNAS-A's reported non-private Kendall's $\tau$ of 0.65 on NAS-Bench-201 CIFAR-10 is the best figure in the file. We will measure their $\tau$ against our DP ground truth. Beating them means a higher $\tau$ and a higher top-10% hit rate at every $\epsilon\le 3$.

The strongest search-based competitors are DPNAS's searched cell transplanted into the federated setting, and DP-FNAS. For DPNAS the reference is 68.33% on CIFAR-10 at $\epsilon=3$, centralized. For DP-FNAS the reference is 3.4% error with 8 parties, but the $\epsilon$ for that figure is not given in the material we have. We will therefore rerun DP-FNAS on our non-IID splits at matched total $\epsilon$ rather than quote it. Beating them means matching or exceeding their final accuracy at equal total $\epsilon$ with at least ten times less search compute.

Budget-matched short training is the multi-fidelity idea from Rethinking Performance Estimation in Neural Architecture Search: rank candidates after a few private federated rounds. It will be given exactly the search $\epsilon$ that $S$ uses.

Two ablations isolate the key ingredient. The first computes the same gradient-agreement statistic without clipping and without the noise term in the denominator, which tests whether modeling DP is what helps. The second drops the cross-client part of the numerator, which tests whether federated heterogeneity matters.

Why not just…?

Why not just use a handcrafted DP-friendly network? This is a serious threat, especially on MedMNIST, where ResNet-18 already competes with AutoML pipelines. DPNAS's searched network beat handcrafted DP baselines on centralized CIFAR-10, but that result has not been shown in federated non-IID settings. Our main comparison charges the search's privacy cost against final accuracy. If the handcrafted network wins at equal total $\epsilon$, we report that search under DP is not worth its budget at this scale. That would itself be a useful finding.

Why not just use existing zero-cost proxies? DPNAS's central observation is that non-private rank does not carry over to DP training, and these proxies were built to predict non-private rank. Our ground truth measures this directly. If Synflow or EZNAS already reach comparable $\tau$ under DP, the clipping-and-noise terms add nothing, and the first ablation will show it.

Why not just train each candidate briefly under DP? This may predict as well as $S$. It is weaker on privacy cost, since each private round composes and a few rounds per candidate cost several times more $\epsilon$ than one projected release. The budget-matched baseline settles the question. We will also report the crossover point at which extra private rounds start paying for themselves.

Why not just run random search? NAS-Bench-201 shows random search often matches complex methods. Under DP, though, every evaluated candidate spends privacy, so random search buys little per unit of $\epsilon$. We include random search at matched $\epsilon$ and compute as a floor.

Decisive Checks

Three results decide the proposal:

  • Rank correlation. $S$ must achieve higher Kendall's $\tau$ and top-10% recall than EZNAS-A, Synflow and NASWOT against DP-FedAvg accuracy at $\epsilon\in\{1,3\}$, on both CIFAR-10 and the MedMNIST tasks.
  • Crossovers. Pairs of architectures that swap rank between $\epsilon=8$ and $\epsilon=1$ in the ground truth must be predicted, at better than chance, by the swaps in $S$ when $\sigma$ changes.
  • End to end. Pruning with $S$ and then training must beat the handcrafted DP network and match DP-FNAS at equal total $\epsilon$, with search cost measured in GPU hours and in $\epsilon$ spent.

Failing the first check falsifies the core claim. Passing the first two but failing the third means the score is scientifically informative but not yet practically worth its privacy cost.