Cover Image

Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kovalev, Dmitry, Borodich, Ekaterina, Gasnikov, Alexander, Feoktistov, Dmitrii
Format:	Preprint
Published:	2024
Subjects:	Optimization and Control Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
by: Borodich, Ekaterina, et al.
Published: (2025)

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates
by: Kovalev, Dmitry, et al.
Published: (2025)

Stochastic Decentralized Optimization of Non-Smooth Convex and Convex-Concave Problems over Time-Varying Networks
by: Divilkovskiy, Maxim, et al.
Published: (2025)

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients
by: Kovalev, Dmitry
Published: (2026)

Decentralized Finite-Sum Optimization over Time-Varying Networks
by: Metelev, Dmitry, et al.
Published: (2024)

Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness
by: Kornilov, Nikita, et al.
Published: (2025)

Decentralized Personalized Federated Learning for Min-Max Problems
by: Borodich, Ekaterina, et al.
Published: (2021)

High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
by: Gorbunov, Eduard, et al.
Published: (2021)

Optimal Projection-Free Adaptive SGD for Matrix Optimization
by: Kovalev, Dmitry
Published: (2026)

Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms
by: Beznosikov, Aleksandr, et al.
Published: (2020)

Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization
by: Kovalev, Dmitry
Published: (2025)

Optimal Decentralized Smoothed Online Convex Optimization
by: Bhuyan, Neelkamal, et al.
Published: (2024)

Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
by: Crawshaw, Michael, et al.
Published: (2025)

Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms
by: Lobanov, Aleksandr, et al.
Published: (2025)

Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
by: Jiang, Ruichen, et al.
Published: (2024)

New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
by: Saad, El Mehdi, et al.
Published: (2025)

Decentralized Optimization with Coupled Constraints
by: Yarmoshik, Demyan, et al.
Published: (2024)

DIGing--SGLD: Decentralized and Scalable Langevin Sampling over Time--Varying Networks
by: Bajwa, Waheed U., et al.
Published: (2025)

Decentralized Federated Learning with Gradient Tracking over Time-Varying Directed Networks
by: Nguyen, Duong Thuy Anh, et al.
Published: (2024)

Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
by: Bai, Cedar Site, et al.
Published: (2024)

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

Optimal Data Splitting in Distributed Optimization for Machine Learning
by: Medyakov, Daniil, et al.
Published: (2024)

Prediction-Correction Algorithm for Time-Varying Smooth Non-Convex Optimization
by: Iwakiri, Hidenori, et al.
Published: (2024)

SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration
by: Kovalev, Dmitry
Published: (2025)

Dual Smoothing for Decentralized Optimization
by: Rogozin, Alexander, et al.
Published: (2025)

Learning-Augmented Decentralized Online Convex Optimization in Networks
by: Li, Pengfei, et al.
Published: (2023)

Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
by: Wu, Yuman, et al.
Published: (2026)

Projection-Free Online Convex Optimization with Time-Varying Constraints
by: Garber, Dan, et al.
Published: (2024)

Time-Varying Convex Optimization with $O(n)$ Computational Complexity
by: Rostami, M., et al.
Published: (2024)

Gradient-Type Methods For Decentralized Optimization Problems With Polyak-Łojasiewicz Condition Over Time-Varying Networks
by: Kuruzov, Ilya, et al.
Published: (2022)

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
by: Fazla, Arda, et al.
Published: (2026)

Provably Convergent Decentralized Optimization over Directed Graphs under Generalized Smoothness
by: Bo, Yanan, et al.
Published: (2026)

Optimal Algorithms for Online Convex Optimization with Adversarial Constraints
by: Sinha, Abhishek, et al.
Published: (2023)

Adaptive Stepsize Selection in Decentralized Convex Optimization
by: Kuruzov, Ilya, et al.
Published: (2025)

Smooth Quasar-Convex Optimization with Constraints
by: Martínez-Rubio, David
Published: (2025)

Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
by: Ji, Kaiyi
Published: (2025)

Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization
by: Zhang, Liang, et al.
Published: (2023)

Automatic Differentiation of Optimization Algorithms with Time-Varying Updates
by: Mehmood, Sheheryar, et al.
Published: (2024)

Strengthening the finite characterizations of smooth min-max games
by: Krivchenko, Valery, et al.
Published: (2026)