Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimization
Not on the map. Why?
Abstract (arXiv)
The graduated optimization approach is a method for finding global optimal solutions for nonconvex functions by using a function smoothing operation with stochastic noise. This paper makes three contributions regarding graduated optimization. First, we extend the definition of function smoothing that is traditionally achieved through convolution with Gaussian noise and characterize for the first time function smoothing with heavy-tailed noise. Second, we show that light- or heavy-tailed stochastic noise in stochastic gradient descent (SGD) has the effect of smoothing the objective function, the degree of which is determined by the learning rate, batch size, and the moment of the stochastic noise. Using this finding, we propose and analyze a new graduated optimization algorithm that varies the degree of smoothing by varying the learning rate and batch size. Third, we relax the σ-nice property, a standard but restrictive condition in the analysis of graduated optimization. Our refinement enables convergence guarantees for a broader class of non-convex functions, thereby bridging the gap between theoretical assumptions and practical optimization landscapes.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 68 of its 129 references that are in the map. First posted on arXiv 15 Nov 2023.
Builds on
68 of 129 references.
References · 68
- 2015Deep Residual Learning for Image Recognitioncited by 52,096
- 2014Adam: A Method for Stochastic Optimizationcited by 37,240
- 2020Denoising Diffusion Probabilistic Modelscited by 21,076
- 2021High-Resolution Image Synthesis with Latent Diffusion Modelscited by 18,863
- 2020Denoising Diffusion Implicit Modelscited by 9,781
- 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 9,122
- 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
- 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
- 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 5,045
- 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,101
- 2016DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFscited by 3,241
- 2016Wide Residual Networkscited by 3,070
38 more
- 2016Pyramid Scene Parsing Networkcited by 2,479
- 2017Rethinking Atrous Convolution for Semantic Image Segmentationcited by 2,161
- 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,492
- 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
- 2018Averaging Weights Leads to Wider Optima and Better Generalizationcited by 1,209
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
- 2017Visualizing the Loss Landscape of Neural Netscited by 1,130
- 2020Improved Techniques for Training Score-Based Generative Modelscited by 1,043
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 674
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
- 2017Don't Decay the Learning Rate, Increase the Batch Sizecited by 320
- 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
- 2021ASAM: Adaptive Sharpness-Aware Minimization for Scale-Invariant Learning of Deep Neural Networkscited by 293
- 2017How to Escape Saddle Points Efficientlycited by 285
- 2017Train longer, generalize better: closing the generalization gap in large batch training of neural networkscited by 279
- 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
- 2023On the Importance of Noise Scheduling for Diffusion Modelscited by 194
- 2015ParseNet: Looking Wider to See Bettercited by 177
- 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 177
- 2018On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimizationcited by 174
- 2017Receptive Field Block Net for Accurate and Fast Object Detectioncited by 141
- 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
- 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
- 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 126
- 2020The Heavy-Tail Phenomenon in SGDcited by 124
- 2015Path-SGD: Path-Normalized Optimization in Deep Neural Networkscited by 120
- 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
- 2023Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Becited by 114
- 2018A Closer Look at Deep Learning Heuristics: Learning rate restarts, Warmup and Distillationcited by 110
- 2017Fisher-Rao Metric, Geometry, and Complexity of Neural Networkscited by 100
- 2022A Generalist Framework for Panoptic Segmentation of Images and Videoscited by 99
- 2019Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejectioncited by 94
- 2023A Modern Look at the Relationship between Sharpness and Generalizationcited by 92
- 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
- 2018Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networkscited by 90
- 2020Relative Flatness and Generalizationcited by 88
50 most cited of 68 All 68 (JSON)
Built on by
Citing papers per year: 2024: 2.
2 papers.