Accelerating SGDM via Learning Rate and Batch Size Schedules: A Lyapunov-Based Analysis

2025/08/05 by Yuichi Kondo, Kondo, Yuichi, Hideaki Iiduka +1
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #cs.LG

paper · pdf · doi:10.48550/arxiv.2508.03105

Accepted at TMLR (Jul. 2026)

arxiv created 2026/07/30 · arxiv updated 2026/07/31

Abstract

We analyze the convergence behavior of stochastic gradient descent with momentum (SGDM) under dynamic learning-rate and batch-size schedules by introducing a novel and simpler Lyapunov function. We extend the existing theoretical framework to cover three practical scheduling strategies commonly used in deep learning: a constant batch size with a decaying learning rate, an increasing batch size with a decaying learning rate, and an increasing batch size with an increasing learning rate. Our results reveal a clear hierarchy in convergence: a constant batch size does not guarantee convergence of the expected gradient norm under our Lyapunov-based analysis, whereas an increasing batch size does, and simultaneously increasing both the batch size and learning rate achieves a provably faster decay. Empirical results validate our theory, showing that dynamically scheduled SGDM significantly outperforms its fixed-hyperparameter counterpart in convergence speed. We also evaluated a warmup schedule in experiments, which empirically outperformed all other strategies in convergence behavior.

Citations

• Both Asymptotic and Non-Asymptotic Convergence of Quasi-Hyperbolic Momentum using Increasing Batch Size
• Increasing Batch Size Improves Convergence of Stochastic Gradient Descent with Momentum
• On the Performance Analysis of Momentum Method: A Frequency Domain Perspective
• Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descent
• Iteration and Stochastic First-order Oracle Complexities of Stochastic Gradient Descent using Constant and Decaying Learning Rates
• Existence and Estimation of Critical Batch Size for Training Generative Adversarial Networks with Two Time-Scale Update Rule
• On the Hyperparameters in Stochastic Gradient Descent with Momentum
• Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization
• An Improved Analysis of Stochastic Gradient Descent with Momentum
• Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization
• Understanding the Role of Momentum in Stochastic Gradient Methods
• Demon: Improved Neural Network Training with Momentum Decay
• On the insufficiency of existing momentum schemes for Stochastic\n Optimization
• Don't Decay the Learning Rate, Increase the Batch Size
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Coupling Adaptive Batch Sizes with Learning Rates
• Stochastic Heavy Ball
• SGDR: Stochastic Gradient Descent with Warm Restarts
• Optimization Methods for Large-Scale Machine Learning
• Optimization Methods for Large-Scale Machine Learning
• A Stochastic Approximation Method

Related

• Optimal Growth Schedules for Batch Size and Learning Rate in SGD that Reduce SFO Complexity
• Increasing Batch Size Improves Convergence of Stochastic Gradient Descent with Momentum
• Adaptive Batch Size and Learning Rate Scheduler for Stochastic Gradient Descent Based on Minimization of Stochastic First-order Oracle Complexity
• Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descent
• Don't Decay the Learning Rate, Increase the Batch Size