{"id":"0e6e21dd-c717-4563-a726-f4ec3652507a","arxiv_id":"2412.11501","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"The paper extends implicit graduated optimization, which views SGD noise as smoothing, to momentum-based SGD, gives a convergence analysis, and reports empirical gains on image classification, but the analysis has a load-bearing mismatch with the pseudocode.","lead":"This paper tests graduated optimization, a smoothing trick for finding global solutions in bumpy problems, on neural networks. It extends the method to a popular momentum-based training technique, proves a convergence result under a restrictive condition, and reports experiments on image classification tasks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's proof breaks in the round-count bound: for fixed η1 and sufficiently small ε, the final-stage denominator ε_M − H3η_M is negative, so T_F is undefined and the O(1/ε^(1/p)) guarantee does not follow.","rationale":"The reader's weakest assumption correctly notes that Algorithm 6's pseudocode calls SGD rather than SHB and that the noise constants are unspecified; those are real concerns about whether the analyzed algorithm matches the claimed momentum method. However, the more fundamental and directly load-bearing problem is in the proof of Theorem 2 itself: the bound on total iterations is invalid because the final-stage denominator can be negative for small ε, and the algebra used to extract O(1/ε^(1/p)) reverses an inequality. This failure does not depend on whether the inner loop is SGD or SHB; it invalidates the theorem even for Algorithm 6 exactly as written. The empirical results may be plausible and consistent with prior work, but they do not compensate for the missing theoretical guarantee. I therefore agree with the reader's reject verdict, but for a slightly different reason than the one highlighted as the weakest assumption. A corrected proof would need either to impose a lower bound on ε_M relative to H3η_M (e.g., by requiring η_1 = O(ε) or a stronger decay of η_m), or to revisit the entire round-complexity argument; neither is present in the current manuscript.","tokens_in":32232,"tokens_out":17677,"duration_ms":146692,"concrete_test":"Take the 'only learning-rate decayed' schedule used in the paper: κ_m = γ_m = (M−m)^p/(M−m+1)^p, ρ_m = 1, λ_m = 1, with p<1, and choose any η_1 > 0. Use the theorem's constants and set ε small enough that H3η_1α0ε > σ²δ_1²α0²ε²/2, e.g., ε = 10^-6. Compute the final-stage requirement ε_M − H3η_M with η_M = η_1/M^p = η_1α0ε and ε_M = σ²δ_1²/(2M^(2p)) = σ²δ_1²α0²ε²/2. This quantity is negative, so T_F = H4/(ε_M − H3η_M) is negative or undefined under the algorithm's own formulas. Alternatively, independently re-derive Appendix C's T_total inequality without replacing (α0ε)^(1/p+2) by (α0ε)^(1/p); the claimed O(1/ε^(1/p)) bound does not survive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 2's guarantee that Algorithm 6 reaches an ε-neighborhood of the global optimum in O(1/ε^(1/p)) rounds. The Appendix C proof fails at the point where it counts total queries. With the proof's own notation, ε_m = σ²δ_m²/2, δ_M = δ_1/M^p, and M^p = 1/(α0ε). The final stage requires T_F = H4/(ε_M − H3η_M) iterations, so the denominator must be positive. But ε_M − H3η_M = σ²δ_1²α0²ε²/2 − H3η_M. For any admissible schedule in Algorithm 6, η_M ≤ η_1; in the 'only learning-rate decayed' schedule used in the experiments (Appendix D), η_M = η_1/M^p = η_1α0ε. Hence for fixed η_1 and sufficiently small ε, the linear term −H3η_1α0ε dominates and the denominator is negative. The subsequent algebra multiplies by M^(2p) and replaces (α0ε)^(1/p+2) with (α0ε)^(1/p) in the denominator; the inequality direction is wrong once the second term is present. Therefore T_F is undefined for small ε, and the claimed O(1/ε^(1/p)) total-round bound is not established. This is a proof-of-theorem failure, not merely a pseudocode typo.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":32623,"tokens_out":9895,"duration_ms":79761,"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":[{"comment":"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.","section":"Appendix C, proof of Theorem 2"},{"comment":"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.","section":"Appendix A, proof of Theorem 1"},{"comment":"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.","section":"Algorithm 6 and Theorem 2"}],"minor_comments":[{"comment":"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.","section":"Theorem 2 statement"},{"comment":"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.","section":"Figure 1 caption"},{"comment":"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.","section":"Appendix D"},{"comment":"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.","section":"Table 1"},{"comment":"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.","section":"Acknowledgements"}],"recommendation":"reject","confidential_remarks":"The main theorem is the only theoretical justification for the claimed global-convergence guarantee, and the proof defects are not local: they concern the object being analyzed (SGD versus SHB) and the sign of a denominator in the complexity bound. I therefore recommend rejection. The experimental scheduler comparison may still be of interest, but the theoretical framing would need to be substantially reworked before the manuscript meets the standards of the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main takeaway: the central theorem is not proven. In Appendix C, the total-round count requires the final-stage denominator ε_M − H3η_M to be positive. Under the algorithm's own schedule, δ_M = δ_1 α0 ε and η_M ≤ η_1 (typically η_1 α0 ε), so for fixed η_1 and sufficiently small ε the denominator is negative, T_F is undefined, and the claimed O(1/ε^{1/p}) bound does not follow. The algebra after that also changes the inequality direction by dropping terms in the denominator. This is a proof-of-theorem failure, not a typo.\n\nWhat is genuinely new: the attempt to prove Rastrigin's function is new σ-nice is a useful concrete example, and the ImageNet comparison of polynomial decay versus cosine annealing is a legitimate external check of the predicted p ≤ 1 schedule. The experiments come with public code. The negative result for explicit graduated optimization on ResNet is honest and worth knowing.\n\nThe momentum extension is a natural step from the authors' prior SGD work, but the analysis does not actually cover the implemented algorithm. Algorithm 6 calls SGD as the inner optimizer, while the implicit-smoothing argument is for SHB, and Theorem 2's statement even says \"apply Algorithm 3.\" Theorem 1's proof also uses Gaussian smoothing where Definition 1 uses uniform-ball noise, so that theorem as stated is not established either.\n\nSoft spots: the benchmark comparison uses per-function learning-rate factors, so it is not a clean head-to-head; the constants in the noise bounds (C², K², H3, H4) are unspecified, making the guarantee non-actionable; and the theoretical core is largely adapted from the authors' own previous papers. The ImageNet result is plausible but based on three runs.\n\nFor whom: readers interested in graduated optimization and learning-rate schedule theory. A careful referee would find the issues quickly. I would not send this to peer review as is; the main theorem's proof is broken and the remaining contributions are not enough for a full paper. The authors should fix the proof or substantially weaken the claim, align the pseudocode with the analysis, and resubmit.","headline":"The central convergence theorem is not proven as written, though the paper's empirical check of polynomial decay schedules is useful.","tokens_in":33108,"tokens_out":8406,"would_cite":false,"duration_ms":76545,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A noise schedule gives momentum SGD a global-optimum guarantee","keywords":["graduated optimization","implicit smoothing","stochastic heavy ball","momentum SGD","new sigma-nice function","global convergence","learning-rate scheduling","image classification"],"falsifier":"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.","tokens_in":32029,"feed_emoji":"🎯","tokens_out":8106,"duration_ms":68953,"temperature":0.7,"pith_summary":"The paper is trying to establish that the smoothing effect of stochastic noise, already used to turn plain SGD into an implicit graduated optimization method, also works for SGD with momentum. Its central theorem says that if the loss is a 'new $\\sigma$-nice' function—a multimodal function whose noise-smoothed versions become strongly convex near the global minimizer—then stochastic heavy ball with a polynomial decay of learning rate, momentum, and batch size reaches an $\\epsilon$-neighborhood of the global minimum in $O(1/\\epsilon^{1/p})$ rounds. If right, this turns common deep-learning practice into a principled annealing schedule: the optimal decay shape is polynomial with power $p \\leq 1$, and momentum should be decayed toward zero along with the learning rate. The paper also proves Rastrigin's function is new $\\sigma$-nice, shows explicit smoothing works on classical benchmarks but not on deep networks, and reports that the scheduled momentum method beats vanilla heavy ball on CIFAR-100 and ImageNet.","feed_headline":"A noise schedule gives momentum SGD a global-optimum guarantee","feed_subtitle":"Decaying learning rate, momentum, and batch size provably lands stochastic heavy ball near the global minimum.","key_machinery":"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})$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the new $\\sigma$-nice function class, the implicit graduated optimization framework for SGD, and the optimal noise decay schedule that Algorithm 6 extends to momentum.","marker":"(Sato and Iiduka 2023)"},{"why":"Supplies the exact stochastic-noise levels $\\delta_{\\mathrm{SHB}}$ and $\\delta_{\\mathrm{NSHB}}$ for stochastic heavy ball and normalized stochastic heavy ball that Theorem 2 relies on.","marker":"(Sato and Iiduka 2024)"},{"why":"Introduces $\\sigma$-nice functions and the graduated-optimization convergence framework that the paper extends.","marker":"(Hazan, Yehuda, and Shalev-Shwartz 2016)"},{"why":"Provides the randomized smoothing viewpoint that justifies treating noise-smoothed functions as the objects being optimized.","marker":"(Duchi, Bartlett, and Wainwright 2012)"},{"why":"References for Rastrigin's function, the function proved new $\\sigma$-nice in Theorem 1.","marker":"(Törn and Zilinskas 1989; Rudolph 1990)"},{"why":"Source of the GA and PSO benchmark results that explicit graduated optimization is compared against in Table 1.","marker":"(Plevris and Solorzano 2022)"},{"why":"Supplies the ResNet architectures used in the CIFAR-100 and ImageNet experiments that validate the proposed schedules.","marker":"(He et al. 2016)"},{"why":"Provides the ImageNet dataset used to test the theoretically optimal polynomial learning-rate decay for momentum SGD.","marker":"(Deng et al. 2009)"}],"fun_headline_variants":["Momentum SGD gets a global optimum guarantee","Noise schedule provably lands momentum SGD near global optimum","Graduated optimization extends to momentum SGD with proof","Implicit smoothing gives momentum SGD a global-minimum guarantee","Momentum SGD provably finds global minima via noise decay"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Momentum SGD gets a global optimum guarantee","Noise schedule provably lands momentum SGD near global optimum","Graduated optimization extends to momentum SGD with proof","Implicit smoothing gives momentum SGD a global-minimum guarantee","Momentum SGD provably finds global minima via noise decay"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000524,"raw_usage":{"total_tokens":2508,"prompt_tokens":899,"completion_tokens":1609,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":1530}},"tokens_in":515,"tokens_out":1609,"duration_ms":9761,"temperature":1.0,"reasoning_tokens":1530,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:52:38.328998+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the new $\\sigma$-nice function class, the implicit graduated optimization framework for SGD, and the optimal noise decay schedule that Algorithm 6 extends to momentum."},{"cited_title":"Momentum Does Not Reduce Stochastic Noise in Stochastic Gradient Descent","cited_arxiv_id":"2402.02325","evidence_quote":"Supplies the exact stochastic-noise levels $\\delta_{\\mathrm{SHB}}$ and $\\delta_{\\mathrm{NSHB}}$ for stochastic heavy ball and normalized stochastic heavy ball that Theorem 2 relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces $\\sigma$-nice functions and the graduated-optimization convergence framework that the paper extends."},{"cited_title":"C.; Bartlett, P","cited_arxiv_id":null,"evidence_quote":"Provides the randomized smoothing viewpoint that justifies treating noise-smoothed functions as the objects being optimized."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the GA and PSO benchmark results that explicit graduated optimization is compared against in Table 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the ImageNet dataset used to test the theoretically optimal polynomial learning-rate decay for momentum SGD."}],"review_version":1}