Cover Image

Tight Analysis of Decentralized SGD: A Markov Chain Perspective

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Versini, Lucas, Mangold, Paul, Dieuleveut, Aymeric
Format:	Preprint
Published:	2026
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
by: Mangold, Paul, et al.
Published: (2025)

Refined Analysis of Federated Averaging and Federated Richardson-Romberg
by: Mangold, Paul, et al.
Published: (2024)

A Tight Theory of Error Feedback Algorithms in Distributed Optimization
by: Thomsen, Daniel Berg, et al.
Published: (2026)

Tight analyses of first-order methods with error feedback
by: Thomsen, Daniel Berg, et al.
Published: (2025)

Compressed and distributed least-squares regression: convergence rates with applications to Federated Learning
by: Philippenko, Constantin, et al.
Published: (2023)

Unified Breakdown Analysis for Byzantine Robust Gossip
by: Gaucher, Renaud, et al.
Published: (2024)

Stability and Generalization for Decentralized Markov SGD
by: Wang, Jiahuan, et al.
Published: (2026)

Byzantine-Robust Gossip: Insights from a Dual Approach
by: Gaucher, Renaud, et al.
Published: (2024)

From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity
by: Gaucher, Renaud, et al.
Published: (2026)

Scalable Utility-Aware Multiclass Calibration
by: Hegazy, Mahmoud, et al.
Published: (2025)

Proving Linear Mode Connectivity of Neural Networks via Optimal Transport
by: Ferbach, Damien, et al.
Published: (2023)

Random features models: a way to study the success of naive imputation
by: Ayme, Alexis, et al.
Published: (2024)

Federated Majorize-Minimization: Beyond Parameter Aggregation
by: Dieuleveut, Aymeric, et al.
Published: (2025)

Topology-aware Generalization of Decentralized SGD
by: Zhu, Tongtian, et al.
Published: (2022)

Valid Selection among Conformal Sets
by: Hegazy, Mahmoud, et al.
Published: (2025)

Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds
by: Ruan, Boyuan, et al.
Published: (2026)

Unveiling High-Probability Generalization in Decentralized SGD
by: Wang, Jiahuan, et al.
Published: (2026)

Heavy-Tail Phenomenon in Decentralized SGD
by: Gurbuzbalaban, Mert, et al.
Published: (2022)

Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm
by: Bars, Batiste Le, et al.
Published: (2023)

High-Probability Convergence Guarantees of Decentralized SGD
by: Armacki, Aleksandar, et al.
Published: (2025)

Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization
by: Armacki, Aleksandar, et al.
Published: (2026)

Refined Analysis of Entropy-Regularized Actor-Critic
by: Labbi, Safwan, et al.
Published: (2026)

PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python
by: Goujaud, Baptiste, et al.
Published: (2022)

Sliced-Wasserstein Estimation with Spherical Harmonics as Control Variates
by: Leluc, Rémi, et al.
Published: (2024)

Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis
by: Cortild, Daniel, et al.
Published: (2025)

Safety Alignment Depth in Large Language Models: A Markov Chain Perspective
by: Kao, Ching-Chia, et al.
Published: (2025)

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
by: Li, Qiang, et al.
Published: (2024)

Tight Group-Level DP Guarantees for DP-SGD with Sampling via Mixture of Gaussians Mechanisms
by: Ganesh, Arun
Published: (2024)

Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework
by: Zhou, Yijie, et al.
Published: (2025)

Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents
by: Mangold, Paul, et al.
Published: (2025)

Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds
by: van Dijk, Marten, et al.
Published: (2026)

Convergence and concentration properties of constant step-size SGD through Markov chains
by: Merad, Ibrahim, et al.
Published: (2023)

Controlling Exploration-Exploitation in GFlowNets via Markov Chain Perspectives
by: Chen, Lin, et al.
Published: (2026)

Convergence Analysis of SGD under Expected Smoothness
by: Kawamoto, Yuta, et al.
Published: (2025)

Distances for Markov Chains, and Their Differentiation
by: Brugère, Tristan, et al.
Published: (2023)

Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains
by: Makkuva, Ashok Vardhan, et al.
Published: (2024)

Slow Feature Analysis on Markov Chains from Goal-Directed Behavior
by: Schüler, Merlin, et al.
Published: (2025)

Optimal Condition for Initialization Variance in Deep Neural Networks: An SGD Dynamics Perspective
by: Horii, Hiroshi, et al.
Published: (2025)

Exact Mean Square Linear Stability Analysis for SGD
by: Mulayoff, Rotem, et al.
Published: (2023)

Pairwise Markov Chains for Volatility Forecasting
by: Azeraf, Elie
Published: (2024)