Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness

2025/07/11 by Qi He, He, Qi, Peng Yu +5
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2507.08913

openalex publication_date 2025/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance. Despite extensive development of convergence guarantees under various assumptions in recent years, most require the Lipschitz smoothness condition, which is often not met in common machine learning models. We highlight this issue with specific counterexamples. To address this gap, we revisit the convergence rates of shuffling-type gradient methods without assuming Lipschitz smoothness. Using our stepsize strategy, the shuffling-type gradient algorithm not only converges under weaker assumptions but also match the current best-known convergence rates, thereby broadening its applicability. We prove the convergence rates for nonconvex, strongly convex, and non-strongly convex cases, each under both random reshuffling and arbitrary shuffling schemes, under a general bounded variance condition. Numerical experiments further validate the performance of our shuffling-type gradient algorithm, underscoring its practical efficacy.

Citations

• Convex and Non-convex Optimization Under Generalized Smoothness
• Convergence of Adam Under Relaxed Assumptions
• Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
• Variance-reduced Clipping for Non-convex Optimization
• Robustness to Unbounded Smoothness of Generalized SignSGD
• Provable Adaptivity of Adam under Non-uniform Smoothness
• Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• Large-Scale Methods for Distributionally Robust Optimization
• Improved Analysis of Clipping Algorithms for Non-convex Optimization
• SGD with shuffling: optimal rates without component convexity and large epoch requirements
• Random Reshuffling: Simple Analysis with Vast Improvements
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• Lower Bounds for Non-Convex Stochastic Optimization
• How Good is SGD with Random Shuffling?
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Random Shuffling Beats SGD after Finite Epochs
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Deep Residual Learning for Image Recognition
• Efficient Distributed SGD with Variance Reduction
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• MGDA Converges under Generalized Smoothness, Provably
• Reinforcement Learning: An Introduction

Related

• On the Last-Iterate Convergence of Shuffling Gradient Methods
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms
• SMG: A Shuffling Gradient-Based Method with Momentum
• Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization