Paying Privacy Once: Zero-Cost Architecture Search from Private Moment Summaries

Choosing a neural network architecture for data you are not allowed to see is costly in two ways. It costs compute, because comparing candidate networks normally means training them. It also costs privacy, because every look at the private data leaks a little more about it. Federated learning makes both costs worse. In federated learning, a shared model is trained across many devices, each holding its own data, and that data usually differs from device to device. Zero-cost proxies attack the compute problem. These are scores computed from one forward and backward pass of an untrained network on a single minibatch, and they rank candidate networks without training them. Every data-dependent proxy, however, needs a real minibatch for every candidate it scores. Under differential privacy, the standard guarantee that bounds how much any single training example can change what is released, scoring thousands of candidates means thousands of separate data accesses, and the privacy budget runs out.

We propose that each client, or group of similar clients, release one differentially private summary of its data: per-class counts, per-class means, and a low-rank per-class covariance in a fixed, public, data-independent basis. This is the same kind of statistic that Privately Customizing Prefinetuning to Better Match User Data in Federated Learning releases once to compute a private Fréchet distance. The server then uses that single release twice. It compares summaries to group clients with similar data. It also draws synthetic labeled "moment batches" from each group's summary and computes data-dependent zero-cost proxies on them for as many candidate architectures as it likes. Differential privacy is closed under post-processing, so the total privacy cost is fixed at release time and does not grow with the size of the search. The question the note asks is whether proxy rankings computed on moment batches keep the information that real data provides beyond data-free scores.

Core Claim

Our hypothesis is that the data-dependence of the useful zero-cost proxies is mostly carried by low-order statistics of the inputs and labels. The candidates are jacob_cov, which measures how correlated activations are across inputs; nwot, which measures overlap of activation patterns across inputs; and snip/fisher, which depend on the loss and therefore on the labels. If that hypothesis holds, two things follow. First, class-conditional Gaussian samples that match a client group's DP-released moments should reproduce that group's proxy ranking closely. Second, they should do so much better than either data-free proxies or isotropic noise inputs. The result would be architecture search for heterogeneous private data whose privacy cost is constant in the number of candidates evaluated and whose compute cost is that of zero-cost proxies.

The release itself is simple. Client $c$ holds examples $(x_i, y_i)$ and projects each input onto a public basis $B$ of $k$ low-frequency discrete cosine directions to get $z_i = B^\top x_i$, clipped to norm at most $C$. For each class $y$, the client releases noisy versions of

$$ n_y = \sum_{i: y_i = y} 1, \qquad s_y = \sum_{i: y_i=y} z_i, \qquad S_y = \sum_{i:y_i=y} z_i z_i^\top . $$

Gaussian noise is calibrated to the clipped sensitivity, and secure aggregation is used when a group of clients pools its statistics. The server forms means $\hat\mu_y = \tilde s_y/\tilde n_y$ and covariances $\hat\Sigma_y$, projected back onto the positive semidefinite cone. It samples $z \sim \mathcal{N}(\hat\mu_y, \hat\Sigma_y)$ with labels drawn in proportion to the noisy counts $\tilde n_y$, and reconstructs images as $Bz$ plus the public mean residual. The same quantities give a Fréchet distance between clients, $\lVert \mu_a-\mu_b\rVert^2 + \mathrm{tr}(\Sigma_a+\Sigma_b-2(\Sigma_a\Sigma_b)^{1/2})$, which we use for grouping.

Relation to Prior Work

The closest work splits into two halves that have not been joined. Neural Architecture Search From Fréchet Task Distance uses a Fisher-information task distance to restrict the search to architectures that worked on the nearest known task. It is centralized and needs raw data. It also uses similarity only to look up a neighbor, never to score candidates. The FreD paper supplies our privacy mechanism, a one-time DP release of means and covariances, but it applies the statistic only to choosing public text corpora for pretraining. Adaptive Personalized Federated Learning via Multi-task Averaging of Kernel Mean Embeddings shows that compressed distribution summaries, there random Fourier feature kernel embeddings, recover cluster structure among clients. We borrow that idea for grouping, but use moments because we need a summary we can sample from.

On the search side, Zero-Cost Proxies for Lightweight NAS and NAS-Bench-Suite-Zero supply the scoring method and the evaluation protocol. Both evaluate proxies only on centralized, balanced, real minibatches. NAS-Bench-Suite-Zero also constrains the design: it reports that many proxies largely track parameter count and FLOPs, and that flops is among the most robust single proxies. Any gain we claim must therefore be measured against flops, not only against weaker proxies.

The federated architecture search papers motivate the work rather than supply its method. Differentially-private Federated Neural Architecture Search runs a differentiable supernet under DP over evenly split data, and pays privacy and communication every round. Heterogeneity-Aware Personalized Federated Neural Architecture Search shows that non-IID data can break federated supernet ranking, but it offers no formal privacy guarantee and trains each client's performance predictor in isolation. Cross-device Federated Architecture Search groups devices by FLOPS alone and leaves DP to future work. None of these computes proxies on private data at a privacy cost that stays fixed as the search grows.

Research Program

The work has three stages, ordered so that the cheapest test can kill the idea.

The first stage asks whether moment batches preserve proxy rankings at all, using centralized data with no privacy. On NAS-Bench-201's CIFAR-10, CIFAR-100 and ImageNet-16-120 splits, we compute each data-dependent proxy in NASLib (jacob_cov, nwot, snip, grasp, fisher, grad_norm) under three input conditions: real minibatches, noise-free moment batches at basis sizes $k \in \{16, 64, 256\}$, and isotropic noise with matched pixel mean and variance. The benchmark's 15,625 trained architectures provide ground truth for free.

The second stage adds noise. We sweep the privacy level ε from 0.5 to 8 and measure how rank correlation degrades as the per-class sample count shrinks. Small classes are where noisy covariances become unreliable, so this sweep also tells us how many clients must be pooled before release.

The third stage is federated. CIFAR-10/100 are split with a Dirichlet distribution over labels, and FEMNIST is split by writer using LEAF. Clients release fingerprints and are grouped by noisy Fréchet distance. Groups then pool their statistics through secure aggregation, and the server scores candidates for each group.

Ground truth for each group requires training. We sample 300 NAS-Bench-201 cells and train each on each group's pooled data on a short, fixed schedule. This costs a few hundred short runs per dataset, which is affordable on a small cluster. The top architectures selected for each group are then retrained with FedAvg inside that group and compared on the group's held-out test accuracy.

Baselines

The naive reference point is a single architecture for everyone. We use the NAS-Bench-201 cell that is best on full centralized CIFAR, trained with FedAvg within each group. Its reported accuracies are 94.37% on CIFAR-10 and 73.51% on CIFAR-100 (NAS-Bench-201). To beat it, a group's selected architectures must reach higher held-out accuracy at equal training compute.

The strongest privacy-free competitor is a data-free score: synflow, flops, and their combination, computed on the same candidate pool. These spend no privacy budget, so they are the real threat. To beat them, moment-batch proxies must achieve higher Spearman rank correlation with the per-group ground truth, and the difference must be significant across groups and seeds.

The strongest data-dependent competitor is the real-data proxy ensemble of synflow, jacob_cov and snip. Zero-Cost Proxies for Lightweight NAS reports a Spearman rank correlation of 0.82 for this ensemble on NAS-Bench-201. We treat it as a non-private ceiling, and success means coming within a small margin of it. We run its private counterpart as well: each candidate's proxy is computed on real client data and released with the Gaussian mechanism, with the privacy loss composed over all candidates. This is matched to our total ε, using the same candidates and the same per-group data.

For a federated search reference, DP-FNAS reports 3.4% CIFAR-10 test error with 8 IID parties. No reported result was found on Lacuna for DP federated architecture search under non-IID partitions. We also include a learned-predictor baseline in the style of HAPFNAS, a random forest per group trained on a small set of evaluated architectures, with its training compute counted against it.

Two ablations isolate the key ingredient. Isotropic noise batches test whether matching the data's moments matters at all. Mean-plus-labels batches with identity covariance test whether second-order structure matters beyond the label skew alone. Every method gets the same candidate pool and the same 300-architecture ground truth. Any proxy-combining surrogate gets the same tuning budget.

Why not just…?

Why not just use data-free proxies like synflow or flops and skip privacy altogether? This is the most serious threat. NAS-Bench-Suite-Zero finds flops among the most robust proxies. If architecture rankings barely change across client groups, nothing in the data is worth paying privacy for. The decisive measurement is the per-group rank-correlation gap between moment batches and the data-free scores. If that gap is near zero at realistic ε, the paper reports a negative result: on these search spaces, data-dependent ranking adds nothing under DP. That is still useful to a field that assumes the opposite.

Why not just release DP proxy scores computed on real data, one per candidate? The privacy loss composes over candidates, and the noise scale grows roughly with the square root of the number of queries under advanced composition. Thousands of candidates should therefore swamp a scalar score whose differences between architectures are small. The matched-ε baseline tests this directly. For a few dozen candidates it may win, and we expect a crossover point in candidate count, which we will report.

Why not just transfer the best architecture from the most similar public task, as TA-NAS does? Retrieval is limited to whatever the library already contains. The groups that most need a different architecture, those with severe label skew, may have no close public neighbor. We run DP-Fréchet retrieval over a library of NAS-Bench-201 tasks and CIFAR superclass subsets as an additional baseline. If retrieval matches scoring, the simpler method should be preferred.

Why not just run DP federated differentiable search? DP-FNAS pays privacy and communication every round. HAPFNAS reports that federated supernet training under heterogeneity can yield a Spearman correlation of −0.1614. Our method needs one release and no supernet training.

Decisive Checks

The idea survives only if three results hold. In stage one, noise-free moment batches must recover most of the real-batch rank correlation on NAS-Bench-201, and clearly more than the isotropic noise ablation does. In stage three, at ε ≤ 4, moment-batch proxies must beat flops/synflow in per-group rank correlation on Dirichlet-split CIFAR-100 and FEMNIST. And the architectures chosen for each group must beat the single-architecture reference in FedAvg accuracy. If the first check fails, the low-order-statistics hypothesis is wrong and we stop. If only the second fails, the paper reports how far DP noise can be pushed before data-dependent proxy ranking stops being useful.