acceptodds
Under review as a conference paper at ICLR 2027

Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression

Abstract

Agnostic federated learning (AFL) seeks a model that performs reliably across heterogeneous workers, but communication remains a bottleneck. We improve communication efficiency by reducing the number of synchronization rounds via faster convergence and the communication cost per round via compression. We first propose AFL-BR, which updates the dual weights over workers using online mirror ascent with KL divergence and blockwise restarts. It achieves an stationarity rate after update rounds, reducing the -dependence of the synchronization rounds required for convergence from polynomial to logarithmic order. Building on AFL-BR, we develop AFL-Com by applying bidirectional compression with error feedback (EF). Instead of compressing local gradients, workers apply EF to their dual-weighted gradients, enabling direct control of the aggregated compression error under time-varying weights. We then establish an stationarity rate for AFL-Com under general -approximate compressors and improve the -dependence from to for additive-and-idempotent compressors with shared randomness (SR). With suitable compression levels, AFL-Com retains the same convergence rate as AFL-BR at a lower per-round communication cost, yielding reductions in total communication complexity by factors of with Top- and with Rand- and SR. Experiments validate the improved synchronization and communication efficiency of our methods.

Primary area:
optimization
Keywords:
agnostic federated learning, nonconvex minimax optimization, communication compression, error feedback

Reviews

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

This paper studies communication efficiency in nonconvex agnostic federated learning (AFL). The authors propose AFL-BR, which updates the dual weights using KL-based online mirror ascent with blockwise restarts, reducing the dependence of synchronization rounds on the number of workers mm from polynomial to logarithmic order. Building on AFL-BR, the authors further develop AFL-COM by incorporating bidirectional compression with error feedback applied to dual-weighted gradients. They establish convergence guarantees under general δ\delta-approximate compressors and obtain a sharper dependence on δ\delta for additive-and-idempotent compressors with shared randomness. Experiments demonstrate the improved synchronization efficiency of AFL-BR and further communication savings achieved by AFL-COM.

Critical strengths
  1. The paper provides substantial theoretical improvements for nonconvex AFL. AFL-BR reduces the mm-dependence of synchronization rounds from polynomial to logarithmic order, and AFL-COM reduces total communication complexity with convergence guarantees under general compressors and sharper results under additional compressor properties and shared randomness.

  2. The theoretical analysis is well-supported by detailed proofs. The authors also revisit the convergence guarantees of SGDA and DRFA, making their hidden mm-dependence explicit.

Critical weaknesses

The theoretical analysis relies on relatively strong assumptions, including uniformly bounded local gradients (Assumption 3) and sub-Gaussian stochastic loss noise (Assumption 4). The strong assumptions may limit the generality of the theoretical guarantees.

Questions for authors
  1. The convergence analysis relies on uniformly bounded local gradients (Assumption 3) and sub-Gaussian stochastic loss noise (Assumption 4). Could the authors clarify why these assumptions are needed in the theoretical analysis and discuss whether there are potential ways to relax either of them?

  2. Both AFL-BR and AFL-COM consider full participation. Could the authors briefly discuss how partial participation may affect the convergence guarantees of the proposed methods?

2 comments

We thank the reviewer for the constructive review and positive assessment of our paper. We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.


Q1. The bounded-gradient and sub-Gaussian loss-noise assumptions may limit the generality of the guarantees. Why are these assumptions needed, and whether there are potential ways to relax either of them?

Response. We thank the reviewer for raising this point. These assumptions serve different purposes in our convergence analysis.

For the primal variable w\mathbf w, Assumption 3 ensures that local risks are Lipschitz in the model, allowing us to control the effect of changes in the worst-case worker distribution as the model evolves. It also controls the accumulated error-feedback residuals. For the dual variable q\mathbf q, the sub-Gaussian condition in Assumption 4 controls stochastic loss fluctuations in the KL-based mirror-ascent analysis, allowing us to bound the stochastic terms without requiring uniformly bounded losses in the full-participation setting.

These assumptions may be relaxed, but typically at the cost of additional structural conditions or algorithmic modifications. For w\mathbf{w}, possible alternatives to bounded gradients include strong convexity with sample-wise smoothness (Nguyen et al., 2018) or expected smoothness (Khaled and Richtárik, 2023). For q\mathbf{q}, robust or clipped estimators offer a potential route to handling heavy-tailed loss noise under weaker moment assumptions (Liu et al., 2024). Establishing comparable guarantees under these relaxations remains an interesting direction for future work.


Q2. Both AFL-BR and AFL-COM consider full participation. Could the authors briefly discuss how partial participation may affect the convergence guarantees of the proposed methods?

Response. We thank the reviewer for this question. We have added partial-participation algorithms for both methods in Algorithm 3 (Appendix G.1) and established their convergence in Theorem 4 (Appendix G.2) under an additional bounded-local-risk assumption. Partial participation introduces additional sampling noise whose variance depends on the magnitudes of local expected losses, which Assumption 4 alone does not control. We therefore introduce bounded local expected losses (Assumption 5), which is also used by Deng et al., (2020).

Empirically, we have added partial-participation experiments in Figure 8 of the revised manuscript. With 30 Fashion-MNIST workers, AFL-Com(T) achieves 70.51 ± 1.90% accuracy at 50% participation versus 71.86 ± 1.40% at full participation, while reducing communication by 30.18%. At 16.7% participation, it achieves 68.54 ± 3.47% with a 71.87% communication reduction. These results provide empirical evidence that our methods support partial participation, maintaining competitive worst-worker accuracy while substantially reducing communication.


Yuyang Deng, Mohammad Mahdi Kamani, Mehrdad Mahdavi. Distributionally Robust Federated Averaging. NeurIPS 2020.

Lam Nguyen, PHUONG HA NGUYEN, Marten Dijk, Peter Richtarik, Katya Scheinberg, Martin Takac. SGD and Hogwild! Convergence Without the Bounded Gradients Assumption. ICML 2018.

Ahmed Khaled, Peter Richtárik. Better Theory for SGD in the Nonconvex World. TMLR 2023.

Langqi Liu, Yibo Wang, Lijun Zhang. High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails. ICML 2024.

Thank you for the detailed response. I maintain the positive score.

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

The paper improves communication efficiency in nonconvex agnostic federated learning. The paper improves communication efficiency in two directions:

  1. Fewer synchronization rounds: AFL-BR uses online mirror ascent with KL divergence and blockwise restarts to improve convergence.
  2. Lower communication cost per round: AFL-COM uses bidirectional compression with error feedback on dual-weighted gradients.
Critical strengths
  1. The improved worker dependence is a meaningful theoretical result. The KL analysis and blockwise restarts handle the changing maximizer without assuming uniformly bounded losses.
  2. Applying EF to dual-weighted gradients is a useful construction. AFL-COM applies error feedback to dual-weighted gradients, handling changing worker weights and obtaining sharper guarantees with shared randomness.
Critical weaknesses
  1. Incomplete ablation studies: The experiments do not isolate the benefits of restarts, dual-weighted EF, and shared randomness, and omit the closest compressed AFL baseline.
  2. The FEMNIST experiment isn't a clean test of scaling with m. Selecting the top-m writers changes the data composition as m grows, and the target worst-worker accuracy is chosen separately for each m
  3. The related compressed AFL method of ADI[1] is missing
Questions for authors
  1. Under the same partitions, tuning budget and compression fraction, how much does each of blockwise restarts, dual-weighted EF and SR contribute?
  2. Under the same participation and tuning budget, how does AFL-COM compare with ADI[1]?
1 comment

We thank the reviewer for the constructive review and positive assessment of our paper. We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.


Q1. The experiments do not isolate the benefits of restarts, dual-weighted EF, and shared randomness, and omit the closest compressed AFL baseline.

Response. Thank you for these suggestions. We have evaluated the components on three datasets under matched data partitions, tuning budgets, and compression rates within each ablation. Figures 4–6 in Appendix D.3 of the revised manuscript report the results.

  1. Mirror ascent and restart. KL mirror ascent improves final worst-worker accuracy over projected gradient ascent on CIFAR-10 and CIFAR-100. Adding restart further improves accuracy by 0.70 and 4.84 percentage points, respectively, while maintaining comparable accuracy on Fashion-MNIST (Figure 4).
  2. Dual-weighted EF. Removing error feedback (EF) leads to pronounced fluctuations on CIFAR-10 and slower progress on Fashion-MNIST and CIFAR-100 (Figure 5). Applying EF to qiq_i-weighted gradients improves accuracy over naive EF by 5.59, 5.23, and 1.53 percentage points on Fashion-MNIST, CIFAR-10, and CIFAR-100, respectively.
  3. Shared randomness. Without SR, training exhibits pronounced fluctuations on Fashion-MNIST and slower progress on CIFAR-10 and CIFAR-100 (Figure 6). With Rand-kk retaining 10% of the coordinates, SR improves final accuracy by 8.22 and 27.91 percentage points on Fashion-MNIST and CIFAR-100, respectively, while achieving comparable final accuracy on CIFAR-10.

These results support the effectiveness of the algorithmic components of AFL-BR and AFL-Com.


Q2. The related compressed AFL method of ADI is missing. Under the same participation and tuning budget, how does AFL-COM compare with ADI?

Response. Thank you for raising this point. We have added ADI (Parfenov et al., 2026) to the comparisons on Fashion-MNIST, CIFAR-10, and CIFAR-100 (Figures 2–3), with full participation for all methods. Consistent with ADI’s compressor requirement, we use unbiased Rand-kk on the uplink, retaining 10% of the coordinates, while leaving the downlink uncompressed. The table below reports worst-worker accuracy and maximum worker CE under the same communication budgets. The hyperparameter selection protocol is described in Appendix D.2.

Dataset / budgetMethodAccuracy (%)Maximum CE
Fashion-MNIST / 100 GbitAFL-BR61.13 ± 1.770.8897 ± 0.0387
AFL-Com(T)65.43 ± 1.830.8061 ± 0.0419
AFL-Com(R)73.23 ± 3.070.6335 ± 0.0548
ADI65.99 ± 1.940.8871 ± 0.0124
CIFAR-10 / 70 GbitAFL-BR37.40 ± 1.391.6604 ± 0.0127
AFL-Com(T)40.50 ± 0.531.6142 ± 0.0117
AFL-Com(R)49.63 ± 1.501.3985 ± 0.0363
ADI39.07 ± 0.811.6272 ± 0.0099
CIFAR-100 / 20 TbitAFL-BR16.35 ± 2.533.5009 ± 0.1095
AFL-Com(T)22.40 ± 1.633.1892 ± 0.1422
AFL-Com(R)49.21 ± 1.261.9387 ± 0.0738
ADI14.57 ± 1.453.6737 ± 0.0892

At each communication budget, AFL-Com(R) improves accuracy over ADI by 7.24, 10.57, and 34.64 percentage points and lowers maximum CE by 0.2536, 0.2287, and 1.7350, respectively. These results demonstrate the benefit of our communication design relative to ADI.


Q3. The FEMNIST experiment isn't a clean test of scaling with mm. Selecting the top-mm writers changes the data composition as mm grows, and the target worst-worker accuracy is chosen separately for each mm.

Response. Thank you for highlighting this point. We acknowledge that selecting different writer populations changes the data distribution and optimization difficulty, which motivated our use of different worst-worker accuracy targets across worker counts. We have clarified the focus of synchronization efficiency across methods at each fixed mm in Section 5.1. Given the limited rebuttal period, we will take your insight as an important direction for future work and explore experimental designs that better isolate mm from changes in the underlying heterogeneous learning problem.

Reviewer_1y3VOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the communication efficiency in Agnostic Federated Learning (AFL), breaking the problem into two aspects:

  • AFL-BR: Improves convergence guarantees and reduces the number of required synchronization rounds by using KL-based Mirror Ascent and periodic restarts.

  • AFL-Com: On top of AFL-BR, applies bidirectional compression and Error Feedback (EF) to weighted gradients, reducing the amount of data transmitted per round.

The ultimate goal is to simultaneously reduce the number of synchronization rounds and the communication overhead per round, without sacrificing AFL's focus on the worst-case client performance.

Critical strengths
  1. The paper addresses an important problem of communication efficiency in heterogeneous federated learning.

  2. The theoretical analysis is relatively comprehensive, providing convergence guarantees for both proposed algorithms and different classes of compressors.

  3. The use of error feedback on dual-weighted gradients is an interesting design for handling time-varying aggregation weights.

  4. The paper is well written and organized, with numerical experiments supporting the theoretical findings.

Critical weaknesses
  1. The algorithmic components, including mirror ascent, periodic restarts, and error feedback, are mostly established techniques. Although the theoretical analysis provides improvements, the individual contributions of these components are not sufficiently demonstrated experimentally. Corresponding ablation studies are expected.

  2. The experimental evaluation of AFL-Com is limited to 10 workers and relatively small neural networks. Considering that the main theoretical advantage depends on the number of workers, experiments with larger client populations and models are expected.

  3. The proposed algorithms require full client participation in every communication round. This is a relatively strong requirement for practical federated learning systems, especially with large numbers of clients and limited device availability.

  4. The compression experiments use fixed sparsity ratios of 30% for Top-k and 10% for Rand-k, without investigating different compression levels. A sensitivity analysis and comparisons under matched communication budgets would better demonstrate the efficiency of the proposed approach.

  5. The baseline comparisons could be more comprehensive. In particular, existing compressed AFL methods are discussed in the related work but not directly evaluated.

Questions for authors

See weaknesses.

5 comments
AuthorsOpenReview ↗

To Reviewer 1y3V (1/2)

We thank the reviewer for the constructive suggestions. We have carefully considered your comments and uploaded our revised paper, with the changes highlighted in blue for ease of reference.


Q1. Although the theoretical analysis provides improvements, the individual contributions of algorithmic components are not sufficiently demonstrated experimentally.

Response. Thank you for this suggestion. We have evaluated the components on three datasets and report the results in Figures 4–6 of Appendix D.3 in the revised manuscript.

  1. Mirror ascent and restart. KL mirror ascent improves final worst-worker accuracy over projected gradient ascent on CIFAR-10 and CIFAR-100. Adding restart further improves accuracy by 0.70 and 4.84 percentage points, respectively, while maintaining comparable accuracy on Fashion-MNIST (Figure 4).
  2. Dual-weighted EF. Removing error feedback (EF) leads to pronounced fluctuations on CIFAR-10 and slower progress on Fashion-MNIST and CIFAR-100 (Figure 5). Applying EF to qiq_i-weighted gradients improves accuracy over naive EF by 5.59, 5.23, and 1.53 percentage points on Fashion-MNIST, CIFAR-10, and CIFAR-100, respectively.
  3. Shared randomness. Without SR, training exhibits pronounced fluctuations on Fashion-MNIST and slower progress on CIFAR-10 and CIFAR-100 (Figure 6). With Rand-kk retaining 10% of the coordinates, SR improves final accuracy by 8.22 and 27.91 percentage points on Fashion-MNIST and CIFAR-100, respectively, while achieving comparable final accuracy on CIFAR-10.

These results support the effectiveness of the algorithmic components of AFL-BR and AFL-Com.


Q2. The experimental evaluation of AFL-Com is limited to 10 workers and relatively small neural networks. Experiments with larger client populations and models are expected.

Response. We thank the reviewer for raising this concern. Figures 2 and 3 add CIFAR-100 with ResNet-18 and 20 workers. At 10,000 updates, the results over three runs are:

MethodWorst-worker accuracy (%)Maximum CE
AFL45.70 ± 1.352.0221 ± 0.0271
AFL-BR52.25 ± 0.971.9576 ± 0.0242
AFL-Com(T)47.21 ± 1.611.9580 ± 0.0181
AFL-Com(R)44.27 ± 1.732.0220 ± 0.0347
ADI49.43 ± 1.321.9696 ± 0.0233

Within a communication budget of 20 Tbit, AFL-Com(R) achieves 49.21 ± 1.26% worst-worker accuracy, compared with 16.35 ± 2.53% for AFL-BR and 14.57 ± 1.45% for ADI. These results support the optimization efficiency of AFL-BR and the communication efficiency of AFL-Com(R) on a larger client population and model.


Q3. The proposed algorithms require full client participation in every communication round.

Response. Thank you for highlighting this point. We have added partial-participation variants of AFL-BR and AFL-Com in Algorithm 3 (Appendix G.1) and convergence guarantees in Theorem 4 (Appendix G.2) under an additional bounded-local-risk assumption, which is standard in related work (Deng et al., 2020). At each round, we sample b<mb<m workers uniformly without replacement from the mm workers. The expected Moreau-envelope gradient norm converges at rate O(T−1/8)O(T^{-1/8}), with an additional factor p−1/2p^{-1/2} relative to the full-participation bounds, where p=b/m∈(0,1)p=b/m\in(0,1).

We also evaluate partial participation on Fashion-MNIST with 30 workers and b∈5,10,15,20,25,30b\in\\{5,10,15,20,25,30\\} participants per round (Figure 8, Appendix D.5). At 1,000 updates, the results over three runs are:

MethodParticipantsAccuracy (%)Communication (Gbit)
AFL-BR30/3071.75 ± 1.40391.98
AFL-BR15/3070.51 ± 1.72245.09
AFL-BR5/3068.33 ± 3.3092.76
AFL-Com(T)30/3071.86 ± 1.40235.28
AFL-Com(T)15/3070.51 ± 1.90164.27
AFL-Com(T)5/3068.54 ± 3.4766.19

These results support partial participation in practice, showing that both methods maintain competitive worst-worker accuracy while reducing communication as fewer workers participate.


Yuyang Deng, Mohammad Mahdi Kamani, Mehrdad Mahdavi. Distributionally Robust Federated Averaging. NeurIPS 2020.

AuthorsOpenReview ↗

To Reviewer 1y3V (2/2)

Q4. A sensitivity analysis and comparisons under matched communication budgets would better demonstrate the efficiency of the proposed approach.

Response. Thank you for this suggestion. We evaluate four compression levels (5%, 10%, 30%, and 50%) on Fashion-MNIST in Figure 7 with a fixed step size for each compressor. At a common 16 Gbit budget, worst-worker accuracy over three runs is:

Compression levelsAFL-Com(T)AFL-Com(R)
5%65.89 ± 1.53%66.56 ± 0.35%
10%61.38 ± 0.35%63.89 ± 1.30%
30%51.00 ± 3.48%56.38 ± 1.06%
50%46.21 ± 0.83%49.04 ± 1.42%

These results show that retaining fewer coordinates yields higher worst-worker accuracy under the same communication budget, indicating improved communication efficiency.


Q5. The baseline comparisons could be more comprehensive.

Response. Thank you for this suggestion. We have added ADI (Parfenov et al. 2026) to the comparisons on Fashion-MNIST, CIFAR-10, and CIFAR-100 (Figures 2–3). Consistent with ADI’s compressor requirement, we use unbiased Rand-kk on the uplink, retaining 10% of the coordinates, while leaving the downlink uncompressed. The table below reports worst-worker accuracy and maximum worker CE under the same communication budgets.

Dataset / budgetMethodAccuracy (%)Maximum CE
Fashion-MNIST / 100 GbitAFL-BR61.13 ± 1.770.8897 ± 0.0387
AFL-Com(T)65.43 ± 1.830.8061 ± 0.0419
AFL-Com(R)73.23 ± 3.070.6335 ± 0.0548
ADI65.99 ± 1.940.8871 ± 0.0124
CIFAR-10 / 70 GbitAFL-BR37.40 ± 1.391.6604 ± 0.0127
AFL-Com(T)40.50 ± 0.531.6142 ± 0.0117
AFL-Com(R)49.63 ± 1.501.3985 ± 0.0363
ADI39.07 ± 0.811.6272 ± 0.0099
CIFAR-100 / 20 TbitAFL-BR16.35 ± 2.533.5009 ± 0.1095
AFL-Com(T)22.40 ± 1.633.1892 ± 0.1422
AFL-Com(R)49.21 ± 1.261.9387 ± 0.0738
ADI14.57 ± 1.453.6737 ± 0.0892

At each communication budget, AFL-Com(R) improves accuracy over ADI by 7.24, 10.57, and 34.64 percentage points and lowers maximum CE by 0.2536, 0.2287, and 1.7350, respectively. These results demonstrate the benefit of our communication design relative to ADI.

Dear Reviewer 1y3V,

Thank you again for your time and careful consideration of our work. We would like to kindly follow up on our response. If you have any remaining questions or concerns, we would be happy to provide further clarification before the discussion period concludes.

Best regards,

Authors

Comments on the paper

1 comment

We thank the reviewers for their constructive comments, which helped us improve our paper. We have added experiments, partial-participation algorithms, and their convergence guarantees to the revised manuscript, with revisions highlighted in blue.

Component ablations. Figures 4–6 evaluate mirror ascent updates, restart, dual-weighted EF, and shared randomness on Fashion-MNIST, CIFAR-10, and CIFAR-100.

A new baseline and a larger model. Figures 2–3 include ADI and extend the evaluation to CIFAR-100 with ResNet-18 and 20 workers.

Compression and participation. Figure 7 evaluates four compression levels, and Figure 8 evaluates partial participation with 30 workers. Appendix G adds partial-participation algorithms and convergence guarantees (Algorithm 3 and Theorem 4).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.