Cover Image

Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fradin, Adrien, Sadiev, Abdurakhmon, Condat, Laurent, Richtárik, Peter
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

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)

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

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

Convergence Analysis of the PAGE Stochastic Algorithm for Weakly Convex Finite-Sum Optimization
by: Condat, Laurent, et al.
Published: (2025)

A Unified Theory of Stochastic Proximal Point Methods without Smoothness
by: Richtárik, Peter, et al.
Published: (2024)

High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise
by: Gorbunov, Eduard, et al.
Published: (2023)

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

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

Differentially Private Random Block Coordinate Descent
by: Maranjyan, Artavazd, et al.
Published: (2024)

SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learning
by: Karagulyan, Avetik, et al.
Published: (2024)

Better LMO-based Momentum Methods with Second-Order Information
by: Khirirat, Sarit, et al.
Published: (2025)

Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise
by: Wang, Menglian, et al.
Published: (2026)

Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise
by: Wu, Yidong, et al.
Published: (2026)

Local SGD and Federated Averaging Through the Lens of Time Complexity
by: Fradin, Adrien, et al.
Published: (2025)

Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similarity
by: Tovmasyan, Zhirayr, et al.
Published: (2025)

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

Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method
by: Sadiev, Abdurakhmon, et al.
Published: (2026)

Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping
by: Liu, Zijian, et al.
Published: (2024)

Bernoulli-LoRA: A Theoretical Framework for Randomized Low-Rank Adaptation
by: Sokolov, Igor, et al.
Published: (2025)

TAMUNA: Doubly Accelerated Distributed Optimization with Local Training, Compression, and Partial Participation
by: Condat, Laurent, et al.
Published: (2023)

Improved Convergence in Parameter-Agnostic Error Feedback through Momentum
by: Sadiev, Abdurakhmon, et al.
Published: (2025)

Decentralized Nonconvex Optimization under Heavy-Tailed Noise: Normalization and Optimal Convergence
by: Yu, Shuhua, et al.
Published: (2025)

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

LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression
by: Condat, Laurent, et al.
Published: (2024)

Distributed Stochastic Optimization under Heavy-Tailed Noises
by: Sun, Chao, et al.
Published: (2023)

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

Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise
by: Bakkali, Taha El, et al.
Published: (2026)

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

Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises
by: Zhu, Tianxi, 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)

Stochastic Gradient Methods with Preconditioned Updates
by: Sadiev, Abdurakhmon, et al.
Published: (2022)

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

Distributed Stochastic Optimization for Non-Smooth and Weakly Convex Problems under Heavy-Tailed Noise
by: Hu, Jun, et al.
Published: (2025)

Unified Compression Algorithm for Distributed Nonconvex Optimization: Generalized to 1-Bit, Saturation, and Bounded Noise
by: Wang, Haonan, et al.
Published: (2026)

A Novel Unified Parametric Assumption for Nonconvex Optimization
by: Riabinin, Artem, et al.
Published: (2025)

CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization
by: Condat, Laurent, et al.
Published: (2022)

Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise
by: Dang, Thanh, 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)

Consensus-Based Optimization with Truncated Noise
by: Fornasier, Massimo, et al.
Published: (2023)