acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 and by the statistical dimension of the cone generated by the client gradients. Both quantities depend only on the Gram matrix of the 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 , 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 , we derive an unbiased Monte Carlo estimator of 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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Federated learning, Multi-objective optimization, Gradient geometry, Conic integral geometry, Fairness in federated optimization, Client heterogeneity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_SMHtOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether a single server update can improve all participating clients in federated learning. It introduces the agreement cone and characterizes its geometry using cone volume and statistical dimension. The paper also derives results relating cone volume to simultaneous client improvement under aggregation noise and evaluates the proposed diagnostics on FMNIST and CIFAR-10.

Critical strengths
  1. The motivating example clearly illustrates why scalar heterogeneity measures such as mean cosine cannot determine whether a strict common-descent direction exists.

  2. The Gram-matrix formulation and statistical-dimension estimator provide a computationally explicit characterization of the proposed geometry without sampling in the full model dimension.

Critical weaknesses
  1. The central descent-cone framing substantially overlaps with earlier multi-objective optimization work. Brown and Smith (2005, Section 2.3.1) describe common-descent directions through intersecting objective-wise descent half-spaces and qualitatively relate cone size to the probability that a random direction improves all objectives. FedMGDA+ also tests common-descent feasibility. The paper's distinct contribution must therefore lie in its quantitative Gram/orthant formulation, statistical-dimension diagnostics, and noise analysis, whose incremental value is not adequately established.

  2. The experiments do not establish the added value of these diagnostics in the structured-conflict regime where they should differ most from simpler measures. After controlling for cosine and training round, the AUROC gain is at most 0.018, with all estimable confidence intervals containing zero (Appendix F.8). The paper reports small within-cosine-quintile differences, but these do not translate into statistically supported held-out AUROC gains. Moreover, Theorem 5 concerns improvement of all clients, whereas the main empirical target is the improved-client fraction.

Questions for authors

Can the authors demonstrate that the proposed cone statistics provide additional predictive value over mean cosine and the FedMGDA+ min-norm diagnostic in a federated setting with structured client conflict? The current experiments do not evaluate this distinguishing regime, while Appendix F.8 shows limited held-out AUROC gains beyond cosine.

2 comments
AuthorsOpenReview ↗

We introduce controlled structured-conflict experiments, demonstrate the predictive value of the proposed metric under equal-norm aggregation, and clarify its limitations under ordinary aggregation and nonlinear prediction models.

Dear Reviewer SMHt, thank you for your comments. Our answer to your question follows.

Q1: We agree that the original Appendix F.8 did not establish added predictive value. We removed that claim about the Dirichlet experiments and added structured-conflict experiments (Section 6.2 and Appendix E.3).

On FMNIST and CIFAR-10, five of 100100 clients have permuted labels within a near-IID partition. Matched controls retain the original labels and share the partition, sampling, and local-SGD streams. The target is strict loss decrease for every sampled client, rather than the improved-client fraction.

The logistic baseline contains mean cosine, round, min-norm magnitude, and log update variance. The augmented model adds log⁡αt\log\alpha_t. Models and preprocessing are fitted on seeds 00--44 and evaluated without refitting on seeds 1010--1414.

DatasetUpdatesBaseline+log⁡αt+\log\alpha_tGain [95% CI]
CIFAR-10Equal norm0.7050.741+0.0354 [0.0133, 0.0576]
FMNISTEqual norm0.6640.689+0.0249 [0.0034, 0.0463]
CIFAR-10Ordinary0.8410.844+0.0026 [0.0003, 0.0049]
FMNISTOrdinary0.8590.853-0.0059 [-0.0174, 0.0056]

AUROCs are averaged across confirmation seeds. Gains use unrounded values and are paired within seed. Intervals are approximate 95%95\% tt-intervals across five seed-level gains, conditional on the fitted models. Equal-norm gains are positive in all five CIFAR-10 seeds and four of five FMNIST seeds.

Equal-norm aggregation rescales updates to the round's median norm; this common norm still varies across rounds. The condition was motivated by exploratory results and subsequently evaluated on held-out seeds. Matched-control gains are smaller; the largest is +0.0023+0.0023 [0.0002, 0.0043].

We also tested cubic B-spline expansions of every feature in both models, fitted only on development data. The structured equal-norm gains then shrink to +0.0008+0.0008 [−0.0010-0.0010, 0.00260.0026] on CIFAR-10 and +0.0009+0.0009 [−0.0022-0.0022, 0.00400.0040] on FMNIST.

The results support added predictive value for the specified linear model under equal-norm structured conflict. They do not establish a general advantage under ordinary aggregation or across prediction models. Section 6.2 states this limitation; Appendix E.3 reports controls, per-seed results, and nonlinear comparisons.

Thank you for the rebuttal and additional experiments. While some concerns have been addressed, the core idea substantially overlaps with existing common-descent theory, and the significance of its quantitative extension remains insufficiently established. The additional experiments show only limited incremental value beyond existing diagnostics, particularly under ordinary aggregation and nonlinear baselines. The practical utility also remains unclear. Therefore, I maintain my original rating.

Reviewer_pmXVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether a single aggregated update in federated learning can simultaneously improve all clients, rather than just the average objective. The paper proposes agreement cone, the set of update directions that decrease every client's loss, and characterize it using its geometric volume and statistical dimension, both derived from the client-gradient Gram matrix. They also derive a probabilistic guarantee for simultaneous client improvement under aggregation noise and propose a dimension-independent Monte Carlo estimator for the statistical dimension. Experimental results show that the proposed metrics correlate with client improvement under strong data heterogeneity.

Critical strengths

+) Solid theoretical analysis. The paper establishes a connection between agreement cone volume, Gaussian orthant probabilities, and simultaneous client improvement under aggregation noise, with formal guarantees.

+) Interesting geometric formulation. The agreement cone provides an interesting way to characterize common descent directions.

Critical weaknesses

-) Experiments do not justify the primary theoretical motivation. The key theoretical advantage arises under structured gradient conflicts, particularly when a minority of clients systematically opposes the majority. However, the experiments do not explicitly produce such conflicts.

-) Practical utility is not clear. The approach is primarily diagnostic and does not propose an optimization algorithm that uses agreement cone statistics to improve training, or convergence.

Questions for authors

a) Could you evaluate settings with explicitly conflicting client objectives, such as minority clients whose gradients systematically oppose the majority, to demonstrate the practical advantage of the agreement cone?

b) How the proposed agreement cone being used to improve practical utility in federated learning grads updates?

1 comment
AuthorsOpenReview ↗

We add structured-conflict experiments, establish the distinct diagnostic value of the proposed metric, clarify its limitations, and identify optimization-based improvements as future work.

Dear Reviewer pmXV, thank you for your comments. We revised the paper and answer both questions below. They also cover the two weaknesses in your review.

Q1: Yes. We added this setting on FMNIST and CIFAR-10 (Section 6.2, Appendix E.3). In Particular, we start from a near-IID partition with 100100 clients and permute the labels of five minority clients by y↦(y+5) mod 10y\mapsto(y+5)\bmod10. Matched controls keep the original labels and share the partition, client sampling, and local-SGD randomness.

The conflict has a clear effect. Under ordinary aggregation on FMNIST, the rate at which all sampled clients improve falls from 0.4260.426 to 0.2420.242, and the rate of majority harm rises from 00 to 0.2160.216 (Table 7).

We then predict whether every sampled client's loss decreases. Models are fitted on seeds 00--44 and evaluated, without refitting, on seeds 1010--1414. The baseline uses cosine, round, min-norm magnitude, and log update variance.

When updates are rescaled to the round's median norm, adding log⁡αt\log\alpha_t gives AUROC gains of +0.0354+0.0354 [0.0133, 0.0576] on CIFAR-10 and +0.0249+0.0249 [0.0034, 0.0463] on FMNIST. The intervals summarize five paired seed-level gains.

We state the limits clearly. The equal-norm condition was motivated by exploratory results. Ordinary-update gains are small or uncertain. With a cubic B-spline baseline, the gains shrink to +0.0008+0.0008 and +0.0009+0.0009, and both intervals include zero. So the benefit is shown for the specified linear model under equal-norm structured conflict.

Separately, Proposition 19 proves that volume is a different quantity: two populations with the same mean cosine, min-norm magnitude, and per-client alignment have volumes 1/41/4 and 1/221/22 at n=20n=20.

Q2: We thank the reviewer for this insightful comment. However, we submit that the current contribution is diagnostic. We have not demonstrated improved training accuracy or convergence from modifying updates using these statistics. The revision makes this limitation explicit.

Under the Gaussian model of Proposition 20,

$Pr[\langle g_i,u\rangle>0\ \forall i]=\Phi_n(\gamma/\sigma;G), \qquad \gamma_i=\langle\hat g_i,\bar g\rangle$

Given the true-gradient geometry, mean aggregate, and noise scale, this computes the probability of common first-order descent before drawing the noise. It is not a finite-step improvement probability, and its application requires the stated noise model.

The structured-conflict experiment provides empirical evidence for predicting simultaneous loss improvement, within the limits described above. Using these diagnostics to select server updates or step sizes, and demonstrating improved client outcomes, remains future work.

Reviewer_V38rOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies which server directions can decrease every participating client's loss to first order. It measures the size of this agreement cone and estimates the statistical dimension of the cone generated by client gradients. It gives a counterexample to common scalar summaries, analyzes noisy aggregation, and evaluates the statistics on Fashion-MNIST and CIFAR-10.

Critical strengths
  1. The separation example is clear and useful. Measuring how much common-descent space remains adds a geometric view beyond checking whether any common direction exists. The Gram-matrix reduction and the main Monte Carlo concentration argument seem correct.

  2. The experiments include five seeds, checks against known geometric values, and analyses controlling for cosine and training round.

Critical weaknesses
  1. Novelty is limited. MGDA and FedMGDA+ already study common descent. This paper mainly applies existing geometric tools to analyze FL.

  2. The theory uses current gradients, but experiments use updates after five local epochs. Their angular error is uncontrolled (Appendix D.14). Theorem 5's noise and alignment assumptions are also untested.

  3. Two claims may need narrowing. An empty cone rules out a common first-order descent direction, but curvature may still let every client's nonconvex loss decrease (page 4). Theorem 5(iii) proves a limiting cone-entry probability. Because directions outside this sufficient cone may also improve every client, the actual loss-decrease probability need not equal the cone volume.

  4. The experiments omit the motivating majority-minority conflict. Mean cosine performs similarly or better, with no clear classification gain in Table 8. Training details and timing results are also missing.

Questions for authors
  1. How large is the angular difference between local updates and exact current gradients? Do the results hold with one local step and with diagnostics computed from exact gradients?

  2. Please restrict page 4's impossibility claim to first-order descent. For Theorem 5(iii), please distinguish exact cone-entry probability from the lower bound on actual improvement.

  3. Can you test structured minority conflict in FL and directly test Theorem 5 under controlled noise? Please report the full training protocol and measured diagnostic overhead.

2 comments
AuthorsOpenReview ↗

We address the reviewer’s concerns by clarifying the novelty of the proposed volume metric, correcting theoretical claims, adding experiments and validation, and revising unsupported claims.

Response to weaknesses: We thank the reviewer for highlighting these critical weaknesses. These comments have broadened our perspective and provided valuable insights for improving the manuscript. Furthermore, we acknowledge that the concept of common descent itself is not new. The MGDA/FedMGDA+ min-norm value measures the best common first-order margin (Section 3.2). Our volume measures the fraction of all directions that give common descent. Proposition 19 (new) shows that they differ: two populations with the same mean cosine, min-norm magnitude, and per-client alignment have volumes 1/41/4 and 1/221/22 at n=20n=20.

Next, we provide the responses of the questions asked:

Q1: The median angle is 39.7∘39.7^\circ on FMNIST and 48.2∘48.2^\circ on CIFAR-10 (Section 6.3, Appendix E.2). The same aggregate passes the common-descent test in 0.0%0.0\% and 10.3%10.3\% of checkpoint rounds with exact gradients, but in 12.8%12.8\% and 41.0%41.0\% with updates. With one full-batch step, Gh=GG^h=G. On CIFAR-10, correlations with the improved-client fraction are 0.2640.264 [0.150, 0.378] for volume, 0.2720.272 [0.161, 0.384] for min-norm, and 0.1540.154 [0.100, 0.208] for cosine (Table 5). These intervals do not show a significant difference between diagnostics.

Q2: Both are corrected. Section 3.2 now restricts the claim to strict first-order descent. For F±(x,y)=2±sin⁡x+cos⁡yF_\pm(x,y)=2\pm\sin x+\cos y, the cone at the origin is empty, yet the step to (0,η)(0,\eta) lowers both losses when 0<η<π0<\eta<\pi. Theorem 5(iii) now gives the limit of the cone-entry probability, followed by a separate lim inf⁡\liminf lower bound on actual improvement. The abstract no longer says that the bound becomes exact.

Q3: We agree that Table 8 showed no clear gain, and removed that claim. Section 6.2 adds five minority clients with permuted labels, with matched controls, on both datasets. Models fitted on seeds 00--44 are tested on seeds 1010--1414. Beyond cosine, round, min-norm, and log variance, volume gives equal-norm AUROC gains of +0.0354+0.0354 [0.0133, 0.0576] on CIFAR-10 and +0.0249+0.0249 [0.0034, 0.0463] on FMNIST. Ordinary-update gains are small or uncertain, and the gain is not established with a spline baseline.

Appendix E.1 tests 168168 quadratic cells with known LL and 10510^5 draws each, aligned and misaligned. No draw entered the margin cone without lowering all losses. In all 126126 aligned cells the improvement frequency was at least the margin volume. Another 810810 neural cells (10310^3 draws each, with an estimated L^\hat L) also show no cone-entry failure. All 405405 full-space neural cells recorded zero cone entries (95%95\% upper limit about 0.0030.003).

Table 2 gives the full protocol. Gram construction plus the three diagnostics costs about 1111,ms against 0.660.66--0.700.70,s of five-epoch training (1.51.5--1.7%1.7\%). With one full-batch step it costs 5858--6969,ms against 1414,ms of training (Table 6).

I would like to thank the authors for the response. Most of my concerns are addressed. My remaining concern is the practical value. Gains are mainly shown with equal-norm updates, remain uncertain for ordinary updates, and are not established against the spline baseline. The full-space neural noise tests also have no cone entries, so they provide limited evidence of practical usefulness.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.