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

arXiv: https://arxiv.org/abs/2601.08614 · HTML: https://mlsanity.com/paper/2601.08614/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 47 references that are in the map.
- First posted on arXiv 13 Jan 2026.

## Builds on (most cited first, 30 of 31)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [On the Ineffectiveness of Variance Reduced Optimization for Deep Learning](https://mlsanity.com/paper/1812.04529/) (2018)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond](https://mlsanity.com/paper/1908.02246/) (2019)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/1802.03866/) (2018)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [On Accelerated Methods for Saddle-Point Problems with Composite Structure](https://mlsanity.com/paper/2103.09344/) (2021)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalities](https://mlsanity.com/paper/2206.09446/) (2022)
- [Accelerated gradient sliding for structured convex optimization](https://mlsanity.com/paper/1609.04905/) (2016)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimization](https://mlsanity.com/paper/1911.10645/) (2019)
- [Oracle Complexity Separation in Convex Optimization](https://mlsanity.com/paper/2002.02706/) (2020)
- [Adaptive Third-Order Methods for Composite Convex Optimization](https://mlsanity.com/paper/2202.12730/) (2022)
- [Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis](https://mlsanity.com/paper/2501.04443/) (2025)
- [On the Optimal Combination of Tensor Optimization Methods](https://mlsanity.com/paper/2002.01004/) (2020)
- [Mirror-prox sliding methods for solving a class of monotone variational inequalities](https://mlsanity.com/paper/2111.00996/) (2021)
- [Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similarity](https://mlsanity.com/paper/2412.16414/) (2024)
- [The Mirror-Prox Sliding Method for Non-smooth decentralized saddle-point problems](https://mlsanity.com/paper/2210.06086/) (2022)

## Abstract (arXiv)

Heterogeneity within data distribution poses a challenge in many modern federated learning tasks. We formalize it as an optimization problem involving a computationally heavy composite under data similarity. By employing different sets of assumptions, we present several approaches to develop communication-efficient methods. An optimal algorithm is proposed for the convex case. The constructed theory is validated through a series of experiments across various problems.