Where Projection Breaks Cooperation: Bias-Aware Weights for Diffusion Learning with Feasible Messages

Networks of learning agents, such as sensors, robots or hospitals, often estimate a shared parameter by alternating two steps. Each agent first nudges its estimate using its own noisy data, and then averages that estimate with its neighbours' estimates. The classical result is that this cooperation divides the error by roughly the number of agents $N$, provided the averaging weights trust low-noise agents more. In practice agents often must also keep their estimates inside a bounded set before sending them. Two reasons are common. Messages sent through a fixed-range quantizer must be bounded. Differential privacy (a guarantee that the shared message reveals little about any single data point) needs bounded messages so that the calibrated noise can mask any individual contribution. Clamping a vector back into a set is called projection. We argue that projecting each agent's estimate before it is shared quietly breaks the $1/N$ law whenever the true parameter sits on or near the boundary of the set. Projection pushes every agent's error inward, in the same direction, so averaging cannot cancel it. The size of each agent's push grows with that agent's noise level.

This matters because it makes informativeness-based weights actively misleading. The usual trust rules set an agent's weight inversely to its noise variance. A heavily clamped noisy agent looks less variable than it really is, because its estimates pile up on the boundary. Any rule that learns trust from observed fluctuations should therefore over-trust exactly the agents whose errors are most biased. We propose to characterize this failure, derive the weights that trade the new bias against variance, and build a decentralized rule that estimates them from a quantity each agent can observe for free: how far its own estimate was moved by projection.

Core Claim

Consider adapt-project-combine diffusion. Each agent $k$ takes a local stochastic gradient step with step size $\mu$, projects onto a convex set $\Theta$, and then forms a weighted average of its neighbours' projected estimates. Suppose the optimum $\theta^\star$ lies on the boundary of $\Theta$. Each agent's projected estimate then carries an inward bias $b_k$ that scales like $\sqrt{\mu}\,\sigma_k$, where $\sigma_k$ is agent $k$'s noise level. The scaling comes from the mean shift of a zero-centred Gaussian fluctuation of width about $\sqrt{\mu}\sigma_k$ that is clamped at a boundary, as in a half-normal distribution. To first order, the steady-state network error then splits into two parts:

$$\text{MSD} \approx c_1 \Big(\sum_k \pi_k \sigma_k\Big)^2 \mu \;+\; c_2\, \mu \sum_k \pi_k^2 \sigma_k^2 .$$

Here MSD is the mean-square deviation from $\theta^\star$, $\pi_k$ is agent $k$'s long-run influence (the Perron vector of the combination matrix), and $c_1, c_2$ depend on the data covariance and the local shape of the boundary. The second term is the familiar variance term, which shrinks as $1/N$. The first term is a bias floor, and it does not shrink with $N$ at all. Minimizing the sum over $\pi$ yields weights of the form $\pi_k \propto (\lambda - 2c_1 S\sigma_k)/\sigma_k^2$, where $\lambda$ is a normalizing Lagrange multiplier and $S=\sum_j \pi_j\sigma_j$ is the network's current influence-weighted noise level. These weights penalize noisy agents more steeply than the relative-variance rule does, and they can even exclude the noisiest agents entirely. This equation is a hypothesis to be proven. It is not an established result.

The claim is therefore threefold. First, under adapt-project-combine, cooperation stops helping beyond a network size set by the ratio $c_2/c_1$. Second, variance-based trust rules are suboptimal there, and fluctuation-based rules are predicted to be worse than static ones. Third, an agent can estimate its own bias from the running average of its projection displacement $d_k = \psi_k - \Pi_\Theta(\psi_k)$, where $\psi_k$ is the pre-projection estimate. That estimate is enough to recover near-optimal weights and to apply a correction after combining.

Relation to Prior Work

The motivation comes from the diffusion literature. Performance Limits for Distributed Estimation Over LMS Adaptive Networks shows that noise-adapted (Hastings) weights let diffusion beat centralized block LMS. Excess-Risk of Distributed Stochastic Learners shows that diffusion gets an $N$-fold speedup, with long-run behaviour governed by the Perron vector. Gramian-Based Adaptive Combination Policies for Diffusion Learning Over Networks learns weights online from the empirical covariance of agents' errors and converges to the relative-variance rule. All three assume unconstrained parameters. That assumption is exactly what makes zero-mean errors cancel. We keep their Perron-vector machinery but add a bias term that does not cancel. Optimal Aggregation Strategies for Social Learning Over Graphs and Discovering Influencers in Opinion Formation over Social Graphs make the broader point that influence should track informativeness rather than network position. Our contribution is that projection changes what "informative" means.

The closest existing work is Privacy-Preserving Distributed Projection LMS for Linear Multitask Networks. It projects neighbours' privacy-noised estimates onto affine subspaces, using weights that trust noisier neighbours less. Projection onto an affine subspace is linear, so it removes noise without creating bias. Our setting is projection onto compact sets such as balls and boxes, where the projection is nonlinear and clamping creates systematic bias. That bias is the phenomenon we study.

Asymptotic Behaviors of Projected Stochastic Approximation: A Jump Diffusion Perspective and Complete Asymptotic Analysis for Projected Stochastic Approximation and Debiased Variants supply a method we reuse. They show that infrequent projection creates a drift bias, and their debiased variant (DLPSA) estimates that drift online and subtracts it. They work with linear constraints and homogeneous clients. We import the "estimate the drift from displacement" idea, apply it agent by agent under heterogeneous noise, and couple it with the choice of weights. On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression and Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization constrain our design. They show that single-agent projected SGD can reach optimal rates, so any loss of cooperative gain we observe must come from projecting before averaging, not from projection itself. Dyn-D^2P: Dynamic Differentially Private Decentralized Learning with Provable Utility Guarantee reports sublinear $1/\sqrt{N}$ scaling under privacy noise. We do not claim clamping explains that result. We do treat private decentralized learning as the main setting where bounded shared messages are mandatory.

Research Program

The analysis has three stages. The first is a clean linear-regression model with a box or $\ell_2$-ball constraint, small constant step size, and white regressors, matching the assumptions of the diffusion LMS papers. In this model we derive the bias and variance terms above, including the dependence on boundary curvature. For a ball, curvature should shrink the bias because tangential noise is partly preserved. The second stage derives the bias-aware optimal Perron vector and the left-stochastic combination matrix that realizes it. The third stage analyzes the fluctuation-based trust rule under adapt-project-combine. It tests whether the Gramian rule's error covariance underestimates the error of heavily clamped agents and hence over-weights them. Diminishing step sizes are treated separately, since the bias and variance terms then decay at different rates.

The algorithm is displacement-tracked diffusion. Each agent keeps an exponential average $\bar d_k$ of its projection displacement. It uses $\|\bar d_k\|$, together with a local variance estimate, as a plug-in estimate of $b_k$, and adjusts its outgoing weights toward the bias-aware optimum. After combining, each agent adds the influence-weighted average of its neighbours' $\bar d$ values and then projects once more. A slowly varying $\bar d_k$ is broadcast infrequently. It is a smoothed, deterministic-looking quantity rather than an instantaneous data-dependent message, so its bounded-sensitivity cost is small. Quantifying that privacy cost is part of the work. The ablations separate reweighting from correction.

Baselines

The naive reference is non-cooperative projected LMS: each agent runs alone and projects every step. It sets the floor that cooperation must beat. As the bandit result in Combining Diverse Information for Coordinated Action: Stochastic Bandit Algorithms for Heterogeneous Agents warns, badly weighted cooperation can fall below it. We also run adapt-project-combine with uniform and Metropolis weights, the simplest decentralized choice.

The strongest existing competitor is adapt-project-combine with the adaptive Hastings / relative-variance rule. It is the rule proven optimal without constraints. In the unconstrained 20-node setting, Performance Limits for Distributed Estimation Over LMS Adaptive Networks reports roughly a 7 dB steady-state EMSE (excess mean-square error) improvement over centralized block LMS. Excess-Risk of Distributed Stochastic Learners reports a 14 dB improvement over non-cooperative learning in a 25-node network. The Gramian policy is the strongest adaptive competitor. No reported numerical MSD for it was found on Lacuna, only the qualitative statement that it converges faster than Metropolis and Hastings. We implement both inside adapt-project-combine with oracle and estimated noise variances.

Two reference points bracket the problem. Adapt-combine-project, which projects only after averaging and therefore shares unbounded messages, is the unconstrained-message oracle. A centralized fusion center running projected SGD with weighted averaging, following On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression, is the pooled-data reference. That paper reports an empirical error ratio of about 1.31 to batch ERM (empirical risk minimization) in 25 dimensions.

All methods share the same topology, data stream, step-size grid and number of tuning trials. Step sizes are matched so that all methods have equal initial convergence rate, following the matched-rate protocol of the diffusion LMS papers. The two ablations are bias-aware reweighting without the post-combine correction, and correction with Hastings weights. Our method beats the field if three things hold under adapt-project-combine with a boundary optimum. Its steady-state MSD must be lower than Hastings by a margin that grows with $N$. It must continue to improve with $N$ where Hastings plateaus. It must come within a few dB of the adapt-combine-project oracle.

Why not just…?

Why not just project after combining (adapt-combine-project)? This alternative is a real threat, and our own analysis predicts it keeps the $1/N$ law, because averaging happens before clamping. If shared messages may be unbounded, it is the right answer, and the proposal says so. It fails when bounded messages are required. With bounded messages, the sensitivity-based noise of private schemes like those in Privacy-Preserving Distributed Projection LMS for Linear Multitask Networks and Dyn-D^2P: Dynamic Differentially Private Decentralized Learning with Provable Utility Guarantee must scale with the message range, and fixed-range quantizers saturate. We run adapt-combine-project with privacy noise calibrated to its empirically observed message range. This tests whether its accuracy advantage survives once the privacy cost of unbounded messages is paid.

Why not just enlarge the set agents project onto before sharing? Inflating the local radius shrinks the clamping bias. It is cheap, and it may recover much of the gap. The cost is that message sensitivity, and therefore privacy noise, grows with the radius. We sweep the inflation factor at a fixed privacy budget and report the resulting accuracy frontier. If inflation matches displacement tracking at every budget, we will conclude that the simple fix suffices.

Why not just keep variance-based trust weights, since they already down-weight noisy agents? In our model, any strictly positive weight on a biased agent leaves an $N$-independent floor. We predict that learned fluctuation-based weights actually move trust toward clamped agents. Both effects show up directly in the MSD-versus-$N$ curves. They also show up in a diagnostic comparing each agent's learned weight against its true post-projection MSE.

Why not just use the debiased projection scheme (DLPSA) at every agent? DLPSA corrects drift for linear constraints under homogeneous clients. It does not address how corrected estimates should be weighted across agents with different noise levels. It is included in the "correction with Hastings weights" ablation.

Proposed Experiments

The primary testbed reproduces the 20-node heterogeneous-noise LMS network of the Hastings and Gramian papers. We add a box constraint and place $\theta^\star$ either on a face, at a vertex, or strictly inside the box. The interior placement is the decisive control. If our mechanism is right, all methods there should behave as in the unconstrained literature, with bias-aware weights reducing to relative-variance weights. We then scale the same construction from 10 to 200 nodes on the 25-node regression setup of Excess-Risk of Distributed Stochastic Learners, plotting steady-state MSD against $N$. The core prediction is falsified if adapt-project-combine with Hastings weights keeps decreasing like $1/N$ for boundary optima. We also measure how MSD depends on $\mu$ and on noise spread, which checks the predicted $\sqrt{\mu}\,\sigma_k$ bias scaling, and we compare box with ball constraints to test the curvature prediction.

For real data, we split YearPredictionMSD across agents with synthetic heterogeneous label noise, under physically motivated box constraints, to test the regression case. We also run $\ell_2$-ball-constrained logistic regression on LIBSVM ijcnn1 over the 50-node network used in Local Adapt-Then-Combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration. Here the radius is chosen so that the unconstrained solution lies outside the ball. No reported accuracy numbers for ijcnn1 under that method were found on Lacuna, so we rerun it ourselves as the communication-matched reference. Metrics are steady-state MSD or test loss, the MSD-versus-$N$ slope, transient convergence time, the privacy budget at matched accuracy, and the weight-versus-true-MSE diagnostic.