REVIEW 3 major objections 5 minor 1 cited by
Explicit and Implicit Graduated Optimization in Deep Neural Networks
T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read A noise schedule gives momentum SGD a global-optimum guarantee
desk verdict The central convergence theorem is not proven as written, though the paper's empirical check of polynomial decay schedules is useful. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the stochastic-noise level $\delta_{\mathrm{SHB}}$ and the expectation identity that connects it to smoothing: $\mathbb{E}[y_{t+1}] = \mathbb{E}[y_t] - \eta \nabla \hat{f}_{\delta_{\mathrm{SHB}}}(y_t)$, where $\hat{f}_\delta$ is the function $f$ smoothed by noise of radius $\delta$. The new $\sigma$-nice condition is the pair of requirements that each smoothed function is $\sigma$-strongly convex inside a neighborhood of the global minimizer and that the minimizer moves by less than the noise decrease between stages. The polynomial schedule $\gamma_m = ((M-m)/(M-m+1))^p$ makes the noise levels telescope to $\delta_M = \delta_1 \alpha_0 \epsilon$ at the last stage, which converts the strongly-convex convergence of each inner optimization into an $\epsilon$-accuracy guarantee with total query count $O(1/\epsilon^{1/p})$.
What would settle it
Run Algorithm 6 exactly as written—calling the inner SGD optimizer on the smoothed objective—on Rastrigin's function with the theoretical polynomial schedule and check whether the final value lands below $\epsilon$; separately, measure the sample variance of the SHB gradient estimator on a quadratic and compare it with $\delta_{\mathrm{SHB}}^2$. A mismatch in either check would show the convergence guarantee does not apply to the implemented algorithm.
Extended reading notes
Core claim
The paper claims that implicit graduated optimization extends from SGD to stochastic heavy ball (SHB) and normalized stochastic heavy ball (NSHB). Under Assumptions A1--A5, the SHB update is, in expectation, gradient descent on a smoothed objective with smoothing radius $\delta_{\mathrm{SHB}} = \eta \sqrt{(1+\hat{\beta}) C^2/b + \hat{\beta} K^2}$, and the same holds for NSHB with $\delta_{\mathrm{NSHB}} = \eta \sqrt{C^2 / ((1-\beta) b)}$. Theorem 2 states that when the objective is a new $\sigma$-nice function, Algorithm 6 reaches an $\epsilon$-neighborhood of the global optimal solution in $O(1/\epsilon^{1/p})$ rounds. The paper further claims that Rastrigin's function is a new $\sigma$-nice function (Theorem 1), that explicit graduated optimization with the optimal noise schedule beats genetic algorithms and particle swarm optimization on several classical benchmarks but is not effective for deep networks, and that the theoretically optimal polynomial learning-rate decay with $p \in (0,1]$ yields the lowest training loss for momentum SGD on CIFAR-100 and ImageNet.
Load-bearing premise
The proof assumes the stochastic noise of the momentum update is exactly $\delta_{\mathrm{SHB}} = \eta \sqrt{(1+\hat{\beta}) C^2/b + \hat{\beta} K^2}$ with known constants $C^2$ and $K^2$, and that the pseudocode's inner SGD call is the same update the analysis treats as SHB.
Editorial extensions
If this is right
- Momentum SGD with a decaying learning rate, decaying momentum, and increasing batch size is guaranteed to reach an $\epsilon$-neighborhood of the global optimum on new $\sigma$-nice functions.
- The optimal noise decay is polynomial with power $p \leq 1$, so the optimal learning-rate scheduler for momentum SGD has the same shape; experiments on ImageNet confirm that polynomial decay with small $p$ gives the lowest training loss.
- The Algorithm 6 schedule outperforms vanilla stochastic heavy ball in test accuracy and training loss on ResNet18 and WideResNet-28-10 on CIFAR-100.
- Because $\delta_{\mathrm{SHB}}$ depends on the momentum factor, decaying momentum toward zero participates in global convergence, not just local convergence.
- Explicit graduated optimization with the optimal schedule is competitive on classical benchmark functions but is not beneficial for deep networks with about 11.2 million parameters.
Reading between the lines
- If the SHB-noise identity is correct, any hyperparameter schedule that shrinks $\eta$, shrinks $\beta$, or grows $b$ is a form of noise annealing; this gives a testable prediction that the effective smoothing radius, not the learning rate itself, is the quantity that should follow the polynomial decay.
- An implication left implicit is that the same argument should extend to adaptive optimizers (Adam-type methods) if their stochastic-noise variance can be written as a known function of hyperparameters; the paper's method provides a template for deriving such schedules.
- The pseudocode of Algorithm 6 calls an inner SGD optimizer, while the theorem analyzes the SHB update; if the intended implementation is true SHB, the convergence proof as written may not cover the algorithm as stated, and an empirical comparison of the two implementations would settle whether this matters.
- The negative result for explicit graduated optimization on deep networks suggests that explicit noise injection becomes ineffective at very high dimension, while implicit noise tied to the optimizer's own variance may scale better; a direct comparison controlling for compute would test that conjecture.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies graduated optimization in two forms. For the explicit form, it claims that Rastrigin's function is a 'new σ-nice' function (Theorem 1), reports benchmark experiments comparing the optimal polynomial noise schedule with geometric schedules and with GA/PSO, and reports that explicit smoothing does not help ResNet training. For the implicit form, it extends the authors' previous implicit graduated optimization framework from SGD to SGD with momentum (SHB and NSHB), states a convergence guarantee for Algorithm 6 (Theorem 2) with O(1/ε^{1/p}) rounds to an ε-neighborhood of a global optimum, and validates the method on CIFAR-100 and ImageNet with ResNet architectures. The central theoretical contributions are Theorem 1 and Theorem 2.
Significance. If the main results were correct, Theorem 2 would be a noteworthy guarantee: momentum-based SGD with a prescribed hyperparameter schedule would reach a global optimum on the 'new σ-nice' function class. The paper also has useful empirical content: the negative result for explicit graduated optimization on ResNet is honestly reported, the ImageNet comparison of polynomial learning-rate schedules with power p ≤ 1 is a concrete external prediction, and the code is publicly linked. However, the theoretical core is not sound in its current form: the proof of Theorem 2 contains an algebraic error in the round-count bound, and Theorem 1 is proved for a different smoothing than the one in Definition 1. These issues are load-bearing because the global-convergence claim is the paper's main theoretical contribution.
major comments (3)
- [Appendix C, proof of Theorem 2] The total-query count is not valid. The proof defines T_F := H4/(ϵ_m − H3η_m) and derives ϵ_M = σ²δ_M²/2 with δ_M = δ_1 α0 ε. Substituting M^p = 1/(α0ε) gives a final denominator σ²δ_1²α0²ε²/2 − H3η_M. Since Algorithm 6 has η_M ≤ η_1 and the 'only learning-rate decayed' schedule used in Appendix D has η_M = η_1α0ε, this denominator is negative for all sufficiently small ε whenever H3 > 0. The proof then multiplies by M^{2p} and later replaces (α0ε)^{1/p+2} by (α0ε)^{1/p} in the denominator; because the −H3η1(α0ε)^{1/p} term is present and (α0ε)^{1/p+2} ≤ (α0ε)^{1/p}, the inequality direction is reversed. Hence T_F is undefined for small ε, and the claimed O(1/ε^{1/p}) bound is not established.
- [Appendix A, proof of Theorem 1] The proof uses a different smoothing than the paper's Definition 1. Definition 1 defines f̂δ(x) = E_{u∼B(0;1)}[f(x−δu)], while the proof computes a Gaussian convolution with u∼N(0, I_D/√D) and uses variance δ² in the computation. The strong-convexity radius and the location of the smoothed minimum can differ between uniform-ball and Gaussian smoothing, and the proof does not verify condition (ii) of Definition 2 for the uniform-ball-smoothed Rastrigin function. Consequently Theorem 1, as stated, is not proved for the smoothing used by Algorithm 1.
- [Algorithm 6 and Theorem 2] The analyzed iteration is not the claimed method. Algorithm 6's inner loop is the line x_{m+1} := SGD(T_F, x_m, f̂_{δ_m}, η_m, b_m), i.e., plain SGD, whereas the section title and the theorem claim an implicit graduated optimization algorithm using SHB. The proof of Theorem 2 invokes Theorem 3, which is a convergence theorem for SGD on a strongly convex function; it never analyzes the SHB update of Algorithm 4. The theorem statement also says 'Suppose that we apply Algorithm 3' rather than Algorithm 6. Thus the convergence guarantee for momentum-based SGD is not established.
minor comments (5)
- [Theorem 2 statement] The theorem says 'Suppose that we apply Algorithm 3' and then 'after O(1/ε^{1/p}) rounds' without completing the sentence; it should refer to Algorithm 6 and be reworded for grammatical completeness.
- [Figure 1 caption] The caption states that the figure is a direct quotation from prior work; reuse of a figure in this form requires explicit permission, and the caption should be rewritten in the authors' own words.
- [Appendix D] The 'only momentum decayed' schedule requires solving a cubic equation for β_{m+1}; the text does not state which root is used or what numerical procedure is applied.
- [Table 1] The reported value 2.44E+127 for Rosenbrock's function under EGO(nice) is not discussed; a reader cannot tell whether this is a divergence, a numerical artifact, or a legitimate optimum value.
- [Acknowledgements] The sentence thanking 'Program Chairs, Area Chairs, and anonymous reviewers for helping us improve the original manuscript' appears to be leftover text from a submission venue and should be removed from the publicly posted version.
Circularity Check
No circular reduction; the derivation imports prior self-cited lemmas as independent evidence, and the main empirical predictions are externally tested.
full rationale
The paper's convergence argument for Algorithm 6 is not self-contained: it imports the new sigma-nice condition and the optimal noise schedule from (Sato and Iiduka 2023), the SHB/NSHB noise-level formulas from (Sato and Iiduka 2024), and the inner SGD convergence theorem from (Sato and Iiduka 2023, Theorem 3). These are self-citations, and they are load-bearing for Theorem 2. However, they are auxiliary results with stated assumptions that do not include the target theorem: the prior theorem concerns SGD on a strongly convex smooth function, and the noise formula is an independent derivation about the SHB update, not a restatement of the graduated-optimization guarantee. Under the rule that such citations are real evidence, their presence does not constitute circularity. The paper also supplies independent content: a proof that Rastrigin's function is new sigma-nice, an explicit construction of the SHB noise-decay schedule, and external benchmark experiments on CIFAR and ImageNet. The ImageNet claim that polynomial decay with p <= 1 achieves lowest loss is an empirical prediction generated from the prior sufficient condition, not a fitted parameter renamed as a prediction. The Appendix C round-count proof does contain a formal gap: the denominator epsilon_M - H3 eta_M can become negative for fixed eta_1 and sufficiently small epsilon, so the O(1/epsilon^(1/p)) bound is not established as written. That is a correctness concern, not a circularity, because the claimed rate is not equivalent to an input by construction. No self-definitional, fitted-input, or renaming reduction is exhibited in the paper, so no significant circularity is found.
Assumptions & free parameters
free parameters (5)
- initial noise level delta_1 =
0.25 in Theorem 1 proof; 0.1/0.01/0.001 in DNN experiments
- decay power p =
p=0.9 in most experiments
- per-function learning rate factors in Table 2 =
various (e.g., 5*delta_m, 0.01*delta_m)
- variance constants C^2_SHB and K^2_SHB =
not specified
- batch size increase factor lambda_m =
lambda_m = ((M-m)/(M-m+1))^{-0.747} in Appendix D
assumptions (5)
- standard math f is Lg-smooth and Lf-Lipschitz (A1, A2)
- standard math The stochastic gradient satisfies unbiasedness and variance bounds (A3, A4, A5)
- ad hoc to paper The loss function in DNN experiments is a new sigma-nice function
- domain assumption The SHB noise formula from Sato and Iiduka 2024 exactly characterizes the smoothing level delta_SHB
- ad hoc to paper Uniform ball smoothing and Gaussian smoothing produce the same strong-convexity properties (implicit in Theorem 1 proof)
Cite this review
Pith. "Pith review of Explicit and Implicit Graduated Optimization in Deep Neural Networks." pith.science (2026). https://pith.science/paper/DBG5AVIR
@misc{pith2026241211501,
author = {Pith},
title = {Pith review of: Explicit and Implicit Graduated Optimization in Deep Neural Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/DBG5AVIR}},
note = {Machine review of arXiv:2412.11501}
}
read the original abstract
Graduated optimization is a global optimization technique that is used to minimize a multimodal nonconvex function by smoothing the objective function with noise and gradually refining the solution. This paper experimentally evaluates the performance of the explicit graduated optimization algorithm with an optimal noise scheduling derived from a previous study and discusses its limitations. It uses traditional benchmark functions and empirical loss functions for modern neural network architectures for evaluating. In addition, this paper extends the implicit graduated optimization algorithm, which is based on the fact that stochastic noise in the optimization process of SGD implicitly smooths the objective function, to SGD with momentum, analyzes its convergence, and demonstrates its effectiveness through experiments on image classification tasks with ResNet architectures.
Figures
Figures from the paper (8 more)
Forward citations
Cited by 1 Pith paper
-
Regularizing quantum loss landscapes by noise injection
Noise injection into each parameterized Pauli gate exponentially suppresses high-frequency Fourier components of a quantum loss function, smoothing the landscape and improving optimization quality in numerical tests.
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Ackley, D. H. 1987. A connectionist machine for genetic hillclimbing. Kluwer Academic Publishers
work page 1987
-
[4]
Antonante, P.; Tzoumas, V.; Yang, H.; and Carlone, L. 2022. Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications. IEEE Transactions on Robotics , 38(1): 281--301
work page 2022
-
[5]
B \" a ck, T.; and Schwefel, H. 1993. An Overview of Evolutionary Algorithms for Parameter Optimization. Evolutionary Computation, 1(1): 1--23
work page 1993
-
[6]
Bengio, Y. 2009. Learning Deep Architectures for AI . Foundations and Trends in Machine Learning, 2(1): 1--127
work page 2009
-
[7]
Beyer, H.-G.; and Finck, S. 2012. HappyCat -- A Simple Function Class Where Well-Known Direct Search Algorithms Do Fail. In Parallel Problem Solving from Nature - PPSN XII, 367--376. Springer Berlin Heidelberg
work page 2012
-
[8]
Blake, A.; and Zisserman, A. 1987. Visual Reconstruction. MIT Press
work page 1987
Show all 47 references
-
[9]
Chapelle, O.; Chi, M.; and Zien, A. 2006. A continuation method for semi-supervised SVM s. In Proceedings of the 23rd International Conference on Machine Learning, volume 148, 185--192
2006
-
[10]
Chapelle, O.; Sindhwani, V.; and Keerthi, S. S. 2008. Optimization Techniques for Semi-Supervised Support Vector Machines. Journal of Machine Learning Research, 9: 203--233
2008
-
[11]
Deng, J.; Dong, W.; Socher, R.; Li, L.; Li, K.; and Fei - Fei, L. 2009. Image N et: A large-scale hierarchical image database. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition , 248--255
2009
-
[12]
Dixon, L. C. W.; and Mills, D. J. 1994. Effect of rounding errors on the variable metric method. Journal of Optimization Theory and Applications, 80(1): 175--179
1994
-
[13]
C.; Bartlett, P
Duchi, J. C.; Bartlett, P. L.; and Wainwright, M. J. 2012. Randomized Smoothing for Stochastic Optimization. SIAM Journal on Optimization , 22(2): 674--701
2012
-
[14]
Gitman, I.; Lang, H.; Zhang, P.; and Xiao, L. 2019. Understanding the Role of Momentum in Stochastic Gradient Methods. In Advances in Neural Information Processing Systems, volume 32, 9630--9640
2019
-
[15]
Griewank, A. O. 1981. Generalized descent for global optimization. Journal of Optimization Theory and Applications, 34(1): 11--39
1981
-
[16]
Hazan, E.; Yehuda, K.; and Shalev - Shwartz, S. 2016. On Graduated Optimization for Stochastic Non-Convex Problems. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, 1833--1841
2016
-
[17]
He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016. Deep Residual Learning for Image Recognition. In IEEE Conference on Computer Vision and Pattern Recognition , 770--778
2016
-
[18]
Ho, J.; Jain, A.; and Abbeel, P. 2020. Denoising Diffusion Probabilistic Models. In Proceedings of the 34th Conference on Neural Information Processing Systems
2020
-
[19]
Holland, J. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press
1975
-
[20]
Iwakiri, H.; Wang, Y.; Ito, S.; and Takeda, A. 2022. Single Loop Gaussian Homotopy Method for Non-convex Optimization. In Proceedings of the 36th Conference on Neural Information Processing Systems
2022
-
[21]
Kennedy, J.; and Eberhart, R. 1995. Particle swarm optimization. In Proceedings of ICNN'95 - International Conference on Neural Networks, volume 4, 1942--1948
1995
-
[22]
Li, D.; Wu, J.; and Zhang, Q. 2023. Stochastic Gradient Descent in the Viewpoint of Graduated Optimization. https://arxiv.org/abs/2308.06775
2023 arXiv
-
[23]
Marcin Molga, C. S. 2005. Test functions for optimization needs. https://robertmarks.org/Classes/ENGR5358/Papers/functions.pdf
2005
-
[24]
Mobahi, H.; and Fisher III, J. W. 2015. A Theoretical Analysis of Optimization by Gaussian Continuation. In Proceedings of the 39th AAAI Conference on Artificial Intelligence , 1205--1211
2015
-
[25]
Peng, L.; K \" u mmerle, C.; and Vidal, R. 2023. On the Convergence of IRLS and Its Variants in Outlier-Robust Estimation. In IEEE/CVF Conference on Computer Vision and Pattern Recognition , 17808--17818
2023
-
[26]
Plevris, V.; and Solorzano, G. 2022. A Collection of 30 Multidimensional Functions for Global Optimization Benchmarking. Data, 7(4)
2022
-
[27]
R.; and Salama, M
Rahnamayan, S.; Tizhoosh, H. R.; and Salama, M. M. A. 2007. A novel population initialization method for accelerating evolutionary algorithms. Computers and Mathematics with Applications, 53(10): 1605--1614
2007
-
[28]
Robbins, H.; and Monro, S. 1951. A stochastic approximation method. The Annals of Mathematical Statistics, 22: 400--407
1951
-
[29]
Rombach, R.; Blattmann, A.; Lorenz, D.; Esser, P.; and Ommer, B. 2022. High-Resolution Image Synthesis with Latent Diffusion Models. In IEEE/CVF Conference on Computer Vision and Pattern Recognition
2022
-
[30]
Rosenbrock, H. H. 1960. An Automatic Method for Finding the Greatest or Least Value of a Function. Computer Journal, 3(3): 175--184
1960
-
[31]
Rudolph, G. 1990. Globale optimierung mit parallelen evolutionsstrategien. Ph.D. thesis, Universit\" a t Dortmund Fachbereich Informatik
1990
-
[32]
Salomon, R. 1996. Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms. Biosystems, 39(3): 263--278
1996
-
[33]
Sato, N.; and Iiduka, H. 2023. Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimization with Optimal Noise Scheduling. https://arxiv.org/abs/2311. 08745
2023
-
[34]
Sato, N.; and Iiduka, H. 2024. Role of Momentum in Smoothing Objective Function and Generalizability of Deep Neural Networks. https://arxiv.org/abs/2402.02325
2024 arXiv
-
[35]
Schaffer, J. D. 1985. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. In Proceedings of the 1st International Conference on Genetic Algorithms, 93--100
1985
-
[36]
D.; Caruana, R
Schaffer, J. D.; Caruana, R. A.; Eshelman, L. J.; and Das, R. 1989. A study of control parameters affecting online performance of genetic algorithms for function optimization. In Proceedings of the 3rd International Conference on Genetic Algorithms, 51--60
1989
-
[37]
Schumer, M.; and Steiglitz, K. 1968. Adaptive step size random search. IEEE Transactions on Automatic Control, 13(3): 270--276
1968
-
[38]
Schwefel, H.-P. 1981. Numerical Optimization of Computer Models. John Wiley & Sons, Inc
1981
-
[39]
S.; and Chapelle, O
Sindhwani, V.; Keerthi, S. S.; and Chapelle, O. 2006. Deterministic annealing for semi-supervised kernel machines. In Proceedings of the 23rd International Conference on Machine Learning, volume 148, 841--848
2006
-
[40]
A.; Maheswaranathan, N.; and Ganguli, S
Sohl - Dickstein, J.; Weiss, E. A.; Maheswaranathan, N.; and Ganguli, S. 2015. Deep Unsupervised Learning using Nonequilibrium Thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, 2256--2265
2015
-
[41]
Song, Y.; and Ermon, S. 2019. Generative Modeling by Estimating Gradients of the Data Distribution. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 11895--11907
2019
-
[42]
Song, Y.; and Ermon, S. 2020. Improved Techniques for Training Score-Based Generative Models. In Proceedings of the 34th Conference on Neural Information Processing Systems
2020
-
[43]
P.; Kumar, A.; Ermon, S.; and Poole, B
Song, Y.; Sohl - Dickstein, J.; kingma, D. P.; Kumar, A.; Ermon, S.; and Poole, B. 2021. Score-Based Generative Modeling through Stochastic Differential Equations. In Proceedings of the 9th International Conference on Learning Represantations
2021
-
[44]
Tan, Y. 2016. GPU -based Parallel Implementation of Swarm Intelligence Algorithms . Morgan Kaufmann Publishers Inc
2016
-
[45]
A.; and Zilinskas, A
T \" o rn, A. A.; and Zilinskas, A. 1989. Global Optimization, volume 350 of Lecture Notes in Computer Science. Springer
1989
-
[46]
Yang, H.; Antonante, P.; Tzoumas, V.; and Carlone, L. 2020. Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection. IEEE Robotics and Automation Letters , 5(2): 1127--1134
2020
-
[47]
Yang, X.-S. 2010. Engineering Optimization: An Introduction with Metaheuristic Applications. John Wiley & Sons, Inc
2010
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.