Cover Image

Understanding the Influence of Digraphs on Decentralized Optimization: Effective Metrics, Lower Bound, and Optimal Algorithm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Liang, Liyuan, Huang, Xinmeng, Xin, Ran, Yuan, Kun
Format:	Preprint
Published:	2023
Subjects:	Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Decentralized Optimization over Time-Varying Row-Stochastic Digraphs
by: Liang, Liyuan, et al.
Published: (2025)

On the Linear Speedup of the Push-Pull Method for Decentralized Optimization over Digraphs
by: Liang, Liyuan, et al.
Published: (2025)

Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression
by: He, Yutong, et al.
Published: (2023)

Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks
by: Liang, Liyuan, et al.
Published: (2025)

A Mathematics-Inspired Learning-to-Optimize Framework for Decentralized Optimization
by: He, Yutong, et al.
Published: (2024)

Decentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity
by: Kong, Boao, et al.
Published: (2024)

SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization
by: Zhu, Shuchen, et al.
Published: (2024)

Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks
by: Kovalev, Dmitry, et al.
Published: (2024)

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

Distributed Bilevel Optimization with Communication Compression
by: He, Yutong, et al.
Published: (2024)

Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?
by: He, Yutong, et al.
Published: (2023)

Decentralized Min-Max Optimization with Gradient Tracking
by: You, Runze, et al.
Published: (2025)

Momentum Benefits Non-IID Federated Learning Simply and Provably
by: Cheng, Ziheng, et al.
Published: (2023)

Understanding the Variance Dichotomy in Continuous Simulation Optimization: A Minimax Lower Bound Perspective
by: Du, Jianzhong, et al.
Published: (2026)

Optimal Gradient Tracking for Decentralized Optimization
by: Song, Zhuoqing, et al.
Published: (2021)

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
by: Kovalev, Dmitry, et al.
Published: (2024)

A Decentralized Proximal Gradient Tracking Algorithm for Composite Optimization on Riemannian Manifolds
by: Wang, Lei, et al.
Published: (2024)

Optimal Decentralized Composite Optimization for Convex Functions
by: Ye, Haishan, et al.
Published: (2023)

Distributed Optimization with Coupled Constraints over Time-Varying Digraph
by: Kim, Yeong-Ung, et al.
Published: (2026)

A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization
by: Dagréou, Mathieu, et al.
Published: (2023)

Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations
by: Agafonov, Artem, et al.
Published: (2024)

Distributed and Decentralized Optimization Algorithms via Consensus ALADIN
by: Du, Xu, et al.
Published: (2026)

Prox-DBRO-VR: A Unified Analysis on Byzantine-Resilient Decentralized Stochastic Composite Optimization with Variance Reduction and Non-Asymptotic Convergence Rates
by: Hu, Jinhui, et al.
Published: (2023)

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

A Unified Algorithm for Nonconvex Decentralized Nonlinear Optimization
by: Wu, Hao, et al.
Published: (2025)

A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints
by: Wang, Lei, et al.
Published: (2022)

Intrinsic Decentralized Stochastic Riemannian Optimization on Manifolds with Bounded Sectional Curvature
by: Nguyen, Duc Toan, et al.
Published: (2026)

A Parameter-free Decentralized Algorithm for Composite Convex Optimization
by: Chen, Xiaokai, et al.
Published: (2025)

An Accelerated Primal Dual Algorithm with Backtracking for Decentralized Constrained Optimization
by: Xu, Qiushui, et al.
Published: (2025)

The Error in Multivariate Linear Extrapolation with Applications to Derivative-Free Optimization
by: Cao, Liyuan, et al.
Published: (2023)

Gradient Descent Is Optimal Under Lower Restricted Secant Inequality And Upper Error Bound
by: Guille-Escuret, Charles, et al.
Published: (2022)

NPGA: A Unified Algorithmic Framework for Decentralized Constraint-Coupled Optimization
by: Li, Jingwang, et al.
Published: (2022)

Towards Scalable Semidefinite Programming: Optimal Metric ADMM with A Worst-case Performance Guarantee
by: Ran, Yifan, et al.
Published: (2024)

A Two-timescale Primal-dual Algorithm for Decentralized Optimization with Compression
by: Liu, Haoming, et al.
Published: (2025)

Discretized Distributed Optimization over Dynamic Digraphs
by: Doostmohammadian, Mohammadreza, et al.
Published: (2023)

Lower Bounds on the Haraux Function
by: Combettes, Patrick L., et al.
Published: (2025)

Bayesian Optimization with Lower Confidence Bounds for Minimization Problems with Known Outer Structure
by: Baumgärtner, Katrin, et al.
Published: (2025)

Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization
by: Basu, Amitabh, et al.
Published: (2025)

A Passivity Analysis for Nonlinear Consensus on Digraphs
by: Yue, Feng-Yu, et al.
Published: (2025)

Guaranteeing Both Consensus and Optimality in Decentralized Nonconvex Optimization with Multiple Local Updates
by: Liu, Jie, et al.
Published: (2025)