The Agreement Cone: When Can One Server Step Improve Every Client in Federated Learning?

Federated learning aggregates client updates into a single server step. In heterogeneous data, this step can decrease the average objective while increasing the loss of individual clients. Existing analyses describe heterogeneity with scalar summaries, such as mean pairwise gradient cosine, gradient variance, and bounded-dissimilarity constants. These summaries track progress on the average objective. They do not determine whether some direction decreases every client objective at once, nor how robust such a common improvement is to aggregation noise. We introduce the agreement cone, the set of directions that give a first-order decrease for every client's loss. We characterize it by its normalized Gaussian volume ${\alpha }_t$ and by the statistical dimension ${\Delta }_t$ of the cone generated by the client gradients. Both quantities depend only on the Gram matrix of the $n\times n$ client grade, not on the dimension of the model. We prove that scalar heterogeneity summaries can rank client populations in the wrong order: for every $n\ge 10$, they prefer a population with no common descent direction over one that admits it. Under spherically symmetric aggregation noise, we show that the probability of improving all clients is lower-bounded by the volume of a margin-shrunken agreement cone, and that this bound becomes exact in the noise-dominated limit. Because this volume can be exponentially small in $n$, we derive an unbiased Monte Carlo estimator of ${\Delta }_t$ whose sample complexity is independent of the model dimension. On FMNIST and CIFAR-10 with Dirichlet label skew, the cone statistics track the fraction of improved clients under strong heterogeneity, at a strength comparable to mean cosine, and add a small signal beyond it, as our analysis predicts. The proposed work of this paper provides a geometric complement to average-case heterogeneity measures and multi-objective feasibility diagnostics.