Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problems

Dmitry Bylinkin, Sergey Skorik, Dmitriy Bystrov, Leonid Berezin, Aram Avetisyan, Aleksandr BeznosikovSubmission to ICLR 2026 · Rejected

Abstract

Heterogeneity within data distribution is an issue encountered in many modern federated learning tasks. We formalize it as an optimization problem with a computationally heavy composite under data similarity. Using different sets of assumptions, we present several approaches to construct communication-efficient methods. An optimal algorithm is proposed for a convex composite. The constructed theory is validated through a series of experiments on various problems such as classification of CIFAR-10 with ResNet-18.
BibTeX
@misc{bylinkin2026accelerated,
  author = {Dmitry Bylinkin and Sergey Skorik and Dmitriy Bystrov and Leonid Berezin and Aram Avetisyan and Aleksandr Beznosikov},
  title = {{Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problems}},
  year = {2026},
  eprint = {2601.08614},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.08614},
}
Figure