Cover Image

Local SGD and Federated Averaging Through the Lens of Time Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fradin, Adrien, Richtárik, Peter, Tyurin, Alexander
Format:	Preprint
Published:	2025
Subjects:	Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity
by: Tyurin, Alexander, et al.
Published: (2024)

On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization
by: Tyurin, Alexander, et al.
Published: (2024)

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
by: Maranjyan, Artavazd, et al.
Published: (2025)

Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations
by: Tyurin, Alexander, et al.
Published: (2024)

A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting
by: Tyurin, Alexander, et al.
Published: (2022)

Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise
by: Fradin, Adrien, et al.
Published: (2025)

Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity
by: Gruntkowska, Kaja, et al.
Published: (2024)

Birch SGD: A Tree Graph Framework for Local and Asynchronous SGD Methods
by: Tyurin, Alexander, et al.
Published: (2025)

LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging
by: Maziane, Yassine, et al.
Published: (2026)

Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
by: Tyurin, Alexander
Published: (2024)

Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity
by: Maranjyan, Artavazd, et al.
Published: (2025)

Tighter Performance Theory of FedExProx
by: Anyszka, Wojciech, et al.
Published: (2024)

On the Convergence of DP-SGD with Adaptive Clipping
by: Shulgin, Egor, et al.
Published: (2024)

MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times
by: Maranjyan, Artavazd, et al.
Published: (2024)

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
by: Tyurin, Alexander
Published: (2024)

Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods
by: Begunov, Grigory, et al.
Published: (2026)

Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness
by: Tyurin, Alexander
Published: (2025)

Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits
by: Begunov, Grigory, et al.
Published: (2026)

MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes
by: Sokolov, Igor, et al.
Published: (2024)

Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration
by: Tyurin, Alexander
Published: (2025)

Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity
by: Mahran, Ammar, et al.
Published: (2026)

Optimality in Decentralized Optimization under Bandwidth Constraints
by: Tyurin, Alexander
Published: (2026)

Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle
by: Richtárik, Peter, et al.
Published: (2026)

The Power of Extrapolation in Federated Learning
by: Li, Hanmin, et al.
Published: (2024)

Speeding up Stochastic Proximal Optimization in the High Hessian Dissimilarity Setting
by: Gasanov, Elnur, et al.
Published: (2024)

A Simple Linear Convergence Analysis of the Point-SAGA Algorithm
by: Condat, Laurent, et al.
Published: (2024)

Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction
by: Tyurin, Alexander
Published: (2025)

GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity
by: Maranjyan, Artavazd, et al.
Published: (2022)

Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
by: Sadiev, Abdurakhmon, et al.
Published: (2025)

Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descent
by: Richtárik, Peter, et al.
Published: (2024)

BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training
by: Condat, Laurent, et al.
Published: (2026)

Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions
by: Sadchikov, Andrey, et al.
Published: (2024)

A Simplified Analysis of SGD for Linear Regression with Weight Averaging
by: Meterez, Alexandru, et al.
Published: (2025)

Sparse-ProxSkip: Accelerated Sparse-to-Sparse Training in Federated Learning
by: Meinhardt, Georg, et al.
Published: (2024)

Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization
by: Demidovich, Yury, et al.
Published: (2024)

Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction
by: Tovmasyan, Zhirayr, et al.
Published: (2026)

The Stochastic Multi-Proximal Method for Nonsmooth Optimization
by: Condat, Laurent, et al.
Published: (2025)

A Unified Primal-Dual Recipe for Accelerating Three-Operator Splitting Methods
by: Sadiev, Abdurakhmon, et al.
Published: (2026)

A Nesterov-Accelerated Primal-Dual Splitting Algorithm for Convex Nonsmooth Optimization
by: Condat, Laurent, et al.
Published: (2026)

Stochastic Proximal Point Methods for Monotone Inclusions under Expected Similarity
by: Sadiev, Abdurakhmon, et al.
Published: (2024)