Tier-Aware Noise Allocation for Private Federated Learning on Heterogeneous Devices

Federated learning trains one model across many phones or sensors without collecting their data. Cheap devices cannot hold a large model, so methods such as ordered dropout train nested sub-models: weak devices update only the first slice of every layer, and flagship devices update the whole thing. Federated learning also needs formal privacy, because model updates can be inverted to recover training images and text. The standard tool is differential privacy (DP): each client's update is clipped to a maximum size, and Gaussian noise is added to the sum. We argue that these two fixes interfere in a predictable way. Clipping and noise designed for one uniform model treat a weak device's small update and a flagship's large update with a single threshold and a single noise level. As a result, the parameters only a few clients touch get drowned in noise, and the clipping threshold is set by the big updates. The privacy mechanism ends up quietly re-excluding the devices that sub-model training was built to include.

We propose to split the privacy mechanism along the same nesting the model already has. Each nested block gets its own clipping threshold and noise level. The noise levels come from a closed-form rule that keeps the total privacy guarantee fixed and minimizes error given how many clients actually contribute to each block. The rule replaces a hand-tuned grid of per-tier thresholds with private estimates of block norms, so it also targets the brittleness of tuning private federated learning. We evaluate it on three questions: utility, accuracy on the devices most at risk of exclusion, and leakage measured by gradient-inversion attacks at matched privacy levels.

Core Claim

In nested sub-model training under user-level DP, the noise and clipping applied to block $b$ should depend on three quantities: the number of clients updating that block, the block's dimension, and the typical norm of its updates. The current practice is one threshold for the whole vector. Let blocks $b=1,\dots,L$ be the nested width levels. Here $d_b$ is the number of parameters in block $b$, $n_b$ is the expected number of sampled clients that update it in a round, $C_b$ is the clipping threshold applied to each client's block-$b$ update, and $\sigma_b$ is the standard deviation of Gaussian noise added to the block-$b$ sum.

Block $b$ is averaged over its $n_b$ contributors, so its per-coordinate noise variance is $\sigma_b^2/n_b^2$. For a worst-case client touching every block, the Gaussian mechanism's privacy depends only on the whitened sensitivity $\sum_b C_b^2/\sigma_b^2$, which we fix to $1/z^2$ for a target effective noise multiplier $z$. Minimizing total noise variance under that constraint has a closed form:

$$\min_{\sigma_b}\ \sum_b \frac{d_b\,\sigma_b^2}{n_b^2}\quad\text{s.t.}\quad \sum_b \frac{C_b^2}{\sigma_b^2}=\frac{1}{z^2}\qquad\Longrightarrow\qquad \sigma_b^2\ \propto\ \frac{C_b\,n_b}{\sqrt{d_b}}.$$

The proportionality follows from the Lagrange condition. The $C_b$ themselves are set each round to a privately estimated quantile of block-$b$ update norms, in the spirit of adaptive clipping. The privacy accounting is unchanged from standard DP-FedAvg with client sampling. What changes is where the noise lands. The inner blocks are shared by every tier, carry most of the signal, and are the only part weak devices can improve, so they receive proportionally less noise per coordinate. The outer blocks, with few contributors, receive more noise in absolute terms but are no longer amplified by an unmatched shared threshold.

The claim is falsifiable on three fronts. First, at matched $(\epsilon,\delta)$, weak-tier accuracy should improve without lowering flagship accuracy. Second, the gap to a privately trained small model that every device can fit should shrink or reverse. Third, the method should need fewer tuned hyperparameters than the per-tier grid search it replaces.

Relation to Prior Work

Two lines of work motivate the proposal. The first builds nested or rolling sub-models: FjORD extracts nested width-$p$ sub-models by ordered dropout, and FedRolex slides a window over the global model so every parameter gets coverage. FedRolex reports 56.57% on CIFAR-100 under high heterogeneity, against 52.38% for HeteroFL. Neither paper applies any privacy mechanism. We reuse their sub-model schemes unchanged and change only how updates are clipped and noised.

The second line studies how DP harms some participants more than others. Disparate Impact in Differential Privacy from Gradient Misalignment shows that per-sample clipping rotates the average gradient toward the majority, and its direction-preserving DPSGD-Global-Adapt lifts minority-class accuracy on Unbalanced MNIST from 26.3% to 65.5%. That analysis is centralized and assumes all updates share one parameter space. Our setting has a structural cause of misalignment, namely tiers updating different coordinate subsets, which a global scale factor alone does not address. R-DPCFL mitigates DP disparity in federated learning by clustering clients, but it requires full models and an initial full-batch round that low-memory devices cannot run.

One paper supplies the adaptive-threshold method. AdaptDP-FedAvg sets the clipping radius each round from a privatized root-mean-square of client norms and proves gains for convex objectives. We use its estimator per block rather than globally. Applied globally, the estimate would be dominated by the full-width flagship updates, whose norms grow with dimension.

Resource-Adaptive Federated Text Generation with Differential Privacy is the closest existing work linking device capacity and DP. It lets weak clients avoid training altogether by casting private votes on synthetic text. We instead keep weak clients in parameter training.

The leakage literature sets the evaluation threat. Deep Leakage from Gradients inverts raw gradients by matching dummy gradients and finds that pruning more than 20% of gradients blocks its attack. Gradient Inversion with Generative Image Prior uses a generative image prior to reconstruct batches of 32 and to cope with 99% missing gradient values, and shows a prior can be meta-learned from the stream of updates. Together these constrain the design. We cannot assume that sending only a sub-model slice is protective, which is exactly the hope a practitioner might have about FjORD's weak tiers.

Research Program

The work has three parts.

The first is analysis. We derive the allocation above, together with a clipping-bias term for each block. We prove that whitened-sensitivity accounting composes with Poisson client sampling exactly as in DP-FedAvg. We characterize the condition under which the single-threshold mechanism over-noises inner blocks: roughly, when flagship update norms dominate the root-mean-square estimate and $n_b$ falls steeply across width levels.

The second is the algorithm. Each client clips each block separately. The server estimates block-norm quantiles privately, spending a small fixed share of the budget as in AdaptDP-FedAvg, recomputes $\sigma_b$ every round, and averages each block over its own contributors. We implement it for both ordered-dropout nesting and rolling windows. Under rolling windows, $n_b$ becomes the expected coverage of each block in each round.

The third is a hyperparameter-sensitivity study. Following the protocol spirit of A Practical Recipe for Federated Learning Under Statistical Heterogeneity, we sweep learning rate, local epochs per tier, and clipping quantile. We report the spread of final accuracy across the sweep, not only the best point. One case gets explicit attention: weak devices that can afford one local epoch while flagships run several. In that case drift and noise compound, and the gap analysis predicts static configurations break.

Baselines

The naive reference point is non-private FjORD and FedRolex, together with DP-FedAvg applied to them with one fixed clipping threshold and isotropic noise. The non-private runs bound utility from above. The single-threshold DP run is the failure we claim exists.

The strongest existing competitor for the privacy mechanism is AdaptDP-FedAvg's adaptive global clipping applied on top of the same sub-model scheme. It is the published remedy for clipping sensitivity in private federated learning. If per-block allocation adds nothing over a well-estimated global radius, our mechanism claim fails.

We also run a direction-preserving variant in the style of DPSGD-Global-Adapt, applying global update scaling at the client level. It is the strongest existing answer to DP disparate impact, and it tests whether misalignment rather than noise placement is the real problem.

The baseline we consider most dangerous is the lowest-common-denominator model: a small network that every tier can fit, trained with adaptive-clipping DP-FedAvg, and optionally followed by local fine-tuning. That recipe found tuned FedAvg with fine-tuning competitive with far more complex methods.

The ablation that isolates the key ingredient keeps per-block clipping but sets $\sigma_b$ uniform. A second ablation uses per-tier thresholds chosen by grid search instead of the closed form. This separates three effects: block-wise clipping, the noise allocation, and the tuning savings.

Fairness controls are the same for every method. All methods share the same data partitions, tier assignments, client sampling rate, rounds, and total $(\epsilon,\delta)$, including the budget spent on norm estimation. All get the same tuning budget, counted in full training runs, and grid-search baselines are charged for their extra runs.

Beating a baseline means the following at matched $(\epsilon,\delta)$ over three seeds. Weak-tier accuracy rises by more than the seed spread. Global and flagship accuracy are not lower. The accuracy spread across the hyperparameter sweep is narrower. We note that no reported result was found on Lacuna for FjORD or FedRolex under differential privacy, so these baselines will be run by us. The only cited reference numbers are non-private: 56.57% on CIFAR-100 for FedRolex, and the centralized 26.3% versus 65.5% minority result for DPSGD-Global-Adapt.

Why not just…?

Why not just train a small model everyone can fit? This is a real threat. With fewer parameters, isotropic noise does less damage, and at strong privacy levels a small model may win outright. Against it, FedRolex shows that capacity beyond any single device's memory buys accuracy in the non-private regime, at 56.57% versus lower-capacity heterogeneous baselines on CIFAR-100. Nothing in the file says that advantage survives DP. We therefore treat this as an empirical question and sweep $\epsilon$. If the small model dominates at every $\epsilon$ we test, we will report that sub-model training is not worth doing under DP, which is itself a useful negative result.

Why not just apply adaptive clipping to the whole update? AdaptDP-FedAvg sets one radius from a root-mean-square over clients. Update norms grow with the number of parameters each client trains, so flagship clients set the radius, and that radius is loose for weak clients' compact updates. The resulting noise is then spread uniformly, including over inner blocks that every tier shares. The per-block clipping with uniform noise ablation, compared against global adaptive clipping, measures exactly how much of the gain comes from per-block thresholds versus noise allocation.

Why not just tune a clipping threshold per tier by grid search? This would probably recover much of the utility. However, it multiplies the hyperparameter search, which is already the dominant hidden cost in federated optimization. Done honestly, it also either consumes privacy budget or relies on public validation data. We include it as an ablation charged for its tuning runs. Our claim is that the closed form matches its best point at a fraction of the tuning cost, and that it degrades less when tier proportions shift between tuning and deployment.

Why not just drop the weak devices? The file documents that device capability correlates with demographics and data distribution. We nonetheless test this directly with a flagship-only DP run. We report accuracy on held-out weak-tier clients, whose data comes from distributions coupled to their tier, rather than accuracy averaged over all clients.

Why not rely on sending only a sub-model slice as protection against inversion? Gradient pruning stops basic DLG but not prior-based inversion, which tolerates 99% missing gradient values. We therefore audit leakage empirically rather than assume it away.

Proposed Experiments

Data and tiers. We use CIFAR-10 and CIFAR-100 split across 500 clients with Dirichlet label skew, FEMNIST partitioned by writer, Shakespeare, and Stack Overflow; the last three are naturally user-partitioned and have enough clients for meaningful user-level DP. Tiers have widths 0.2, 0.5, and 1.0. They are assigned either independently of the data or correlated with each client's label distribution, which mimics the coupling between hardware and data that the exclusion literature reports. We use ResNet18 and CNNs for images and LSTMs for text, as in FjORD.

Metrics. We report global accuracy, per-tier accuracy, and the 10th-percentile client accuracy in the style of LEAF, each at $\epsilon\in\{1,3,8\}$. We also report the variance of final accuracy across the hyperparameter sweep.

Leakage audit. We run DLG and the generative-prior attack (GIAS), plus multi-round GIML-style prior learning, against weak-tier and flagship updates on CIFAR-10 and on FFHQ at 32×32, with batch sizes 1 to 32. We report reconstruction MSE and PSNR. For scale, the file reports DLG reaching roughly 0.0069 MSE and the generative-prior attack 15.58 dB PSNR on undefended targets.

Decisive checks. Three results decide the proposal. The first: at matched $\epsilon$, does tier-aware allocation raise weak-tier accuracy over global adaptive clipping by more than the seed spread under data-correlated tiers, while the effect shrinks under independent tiers? That pattern would confirm the mechanism rather than a tuning artifact. The second: does it close or reverse the gap to the small all-device model at moderate $\epsilon$? The third: at the same $\epsilon$, are weak-tier updates no easier to invert than flagship updates? If they are easier, the noise allocation trades exclusion for leakage, and the rule must place a floor on inner-block noise.