{"id":"357b577b-7cac-4fb6-bbb5-777b515fea89","arxiv_id":"2506.09730","paper_version":3,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Shortening step sizes by a factor of 1/(1+δ) improves the worst-case and practical robustness of long-step and accelerated first-order methods under relative gradient inexactness, with FGM emerging as empirically robust.","lead":"This paper studies how well common first-order optimization methods hold up when gradient computations are slightly inaccurate, as when using low-precision arithmetic on GPUs. It introduces a simple step-size shortening rule and shows, through worst-case computations and experiments on logistic regression, that the rule helps and that accelerated methods are more robust than theory predicts.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The empirical claim that FGM is unusually robust rests on a single adversarial corruption model ('away from x*') that is not necessarily worst-case for FGM; this weakens the central recommendation to prefer FGM.","rationale":"The reader's weakest assumption focuses on the shortening factor. I agree the empirical base is thin, but the shortening factor has two independent lines of evidence: the PEP worst-case rates in Figure 2b are computed over all smooth convex functions (not one dataset) and show consistent improvement, and the experiments on two datasets (one shown) agree. So the 'shortening helps' claim is less fragile than the reader suggests. The FGM-robustness claim, by contrast, is contradicted by the same PEP worst-case analysis and is supported only by the Section 3 experiments, where the corruption is a specific heuristic. The phrase 'adversarial' in Section 3.2 is misleading: the error is chosen to move away from x*, not to maximize the damage to the particular algorithm. For FGM, whose momentum term places y_k ahead of x_k, a perturbation directed away from x* may partly cancel or be less harmful. Thus the central surprise of the paper—accelerated methods much more robust than theory predicts—rests on a single corruption model. A targeted local worst-case perturbation test would settle whether FGM's robustness is real or an artifact. If the claim is an artifact, the recommendation to prefer FGM should be downgraded; if it survives, the paper's thesis is strengthened. Either way the paper should remain conditional until this is tested, so I do not change the reader's verdict.","tokens_in":9371,"tokens_out":12421,"duration_ms":145840,"concrete_test":"Run the Section 3.2 experiment on the same logistic dataset and δ values, but replace the 'away from x*' error with the locally worst perturbation: at each step choose d_k on the boundary of {‖d − ∇f(y_k)‖ ≤ δ‖∇f(y_k)‖} that maximizes ‖∇f(x_{k+1}(d))‖² (for FGM; analogous for gradient descent), computed by a small local search over the boundary direction. Compare FGM's mean min-gradient-norm and test accuracy over the same 6 starts and N = 100. If FGM degrades toward its Figure 2a worst-case behavior under this targeted corruption, the 'much more robust than expected' claim is an artifact of the chosen direction; if it stays close to Figure 4, the claim is supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3.2 the 'adversarial' corruption is constructed by adding the longest allowed error vector pointing away from the true minimizer x*. This is a valid relative-error perturbation, but it is only one point on the boundary of the allowed δ-ball, and it is not chosen adversarially with respect to the algorithm. For FGM, whose extrapolated point y_k can overshoot x*, a perturbation aligned with 'away from x*' may be relatively benign. The PEP worst-case results in Figure 2a, which are adversarial over both the function and the error sequence, show FGM degrading substantially for δ ≥ 0.4. The paper's headline surprise that FGM is 'much more robust than expected' therefore depends on a specific corruption heuristic rather than on a demonstration of robustness to relative inexactness in general. Since the practical recommendation is to prefer FGM, this is load-bearing: if FGM's robustness disappears under a more targeted perturbation, the central surprise and a key recommendation lose support. The reader's shortening-factor concern is real but partially mitigated by the PEP rates in Figure 2b, which are not limited to one dataset; the FGM claim has no such independent support.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the behavior of four first-order optimization methods—constant step-size gradient descent, dynamic step sizes, Silver step sizes, and Nesterov's fast gradient method (FGM)—when gradients are subject to relative inexactness of the form ||d_k - ∇f(x_k)|| ≤ δ||∇f(x_k)||. Using the Performance Estimation Problem (PEP) methodology, the authors numerically compute worst-case convergence rates in squared gradient norm for N = 50 iterations and find that long-step and accelerated methods degrade as δ grows. They then propose a 'shortening factor' 1/(1+δ), motivated by a divergence threshold for constant-step gradient descent on a quadratic, and show via PEP that shortened schedules have substantially better worst-case rates. The empirical part considers a logistic regression problem with two inexactness models: compressed mantissa gradients and an 'adversarial' corruption that adds the longest perturbation pointing away from the optimizer. The reported experiments indicate that compression is largely harmless, that FGM is surprisingly robust under the corruption model, and that shortening helps the long-step methods in that model. The paper recommends FGM, or shortened Silver steps when a memoryless method is needed.","tokens_in":9603,"tokens_out":5737,"duration_ms":66316,"significance":"If the claims are validated, the paper offers practically relevant guidance for using low-precision or compressed gradients on GPUs, and it demonstrates how PEP can be used to diagnose robustness issues beyond standard convergence-rate analysis. The authors release their code, which is a genuine strength, and the shortening-factor idea is natural and potentially useful. However, the central empirical claims are currently supported by a narrow experimental base—one dataset shown, six initial points, no error bars—and by a corruption model that is adversarial only in a limited sense. The PEP results are numerical SDP outcomes rather than certified proofs. The paper's contribution is therefore promising but not yet fully established; the gap between the strength of the recommendations and the evidence is the main issue.","major_comments":[{"comment":"The headline empirical finding that FGM is 'much more robust than expected' and the recommendation to prefer FGM rest entirely on the corruption model that adds the longest feasible perturbation pointing away from x*. That perturbation is one specific point on the boundary of the relative-inexactness ball and is not chosen adversarially with respect to FGM; for a method whose extrapolated point y_k can overshoot x*, this direction may be comparatively benign. The PEP worst-case rates in Figure 2a, which are adversarial over both the function and the error sequence, show FGM degrading substantially for δ ≥ 0.4. To make the robustness claim load-bearing, the authors should add corruption directions that are adversarial for each method (for example, aligned with the momentum or extrapolation direction) or report the worst performance over randomized boundary perturbations.","section":"Section 3.2, Figures 2a and 4"},{"comment":"The shortening factor 1/(1+δ) is introduced from a divergence threshold h > 2/(1+δ) for constant-step gradient descent on the quadratic f(x)=Lx^2/2, citing references [15,16]. Its extension to the Silver, dynamic, and FGM schedules is an assumption rather than a derived result. The PEP rates in Figure 2b provide numerical support for worst-case rates, but the practical recommendation that shortened Silver is a robust memoryless method is validated only on one logistic regression dataset, with only a mention of a phishing dataset and no shown results. The authors should either provide additional datasets, give a theoretical justification for why the factor transfers to these schedules, or explicitly restrict the claim to the tested setting.","section":"Section 2, shortening factor paragraph"},{"comment":"The abstract states that 'the shortening factor significantly helps the long-step methods,' but this is observed only in the adversarial corruption experiment of Section 3.2. In the compressed-gradient experiment of Section 3.1, the text explicitly says that shortened schedules 'do not seem to make much difference' (page 9). The conclusions should distinguish between the two inexactness models, because the current wording overgeneralizes the evidence.","section":"Abstract and Sections 3.1–3.2"},{"comment":"The paper refers to the PEP results as 'exact convergence rates' and states that long-step and accelerated methods are 'shown to be theoretically not robust.' These rates are outputs of a semidefinite program solved numerically with MOSEK, and no solver tolerance or certificate verification is reported. The authors should state the numerical nature of these results and either verify them with a rigorous post-processing step or soften the wording from 'shown' to something like 'numerically observed.'","section":"Section 2, Figures 2a–2b"},{"comment":"All empirical curves are means over six initial points on a single dataset, with no error bars, no per-seed results, and no statistical tests. The claims that compression 'does not seem to cause any significant harm' and that shortening 'greatly improves' performance are quantitative; without variability information, the reader cannot assess how robust these conclusions are to initialization or to the choice of dataset. The authors should report error bars or additional dataset results before drawing practical recommendations.","section":"Section 3, Figures 3 and 4"}],"minor_comments":[{"comment":"The axis labels in the submitted figures are visually corrupted (for example, 'Mean of min k ∈[N] --∇(f(x_k)--' and 'Mean of be() )rainin accuracie('). The figures should be regenerated with proper mathematical notation.","section":"Figures 3 and 4"},{"comment":"The smoothness constant L used for normalized step sizes is estimated numerically, whereas the theoretical PEP analysis assumes L is known exactly. The paper should state clearly that the experiments use an estimate, and discuss how errors in this estimate interact with the relative inexactness level δ.","section":"Section 3"},{"comment":"The qualitative ratings (✗, ∼, ✓) in Table 1 are presented without explicit thresholds or a precise definition of when a method is considered 'bad,' 'intermediate,' or 'good.' A short criterion would make the table more informative.","section":"Table 1"},{"comment":"The derivation of the divergence threshold h > 2/(1+δ) referenced to [15,16] is not reproduced. Since this threshold is the motivation for the central shortening factor, a brief proof sketch in an appendix would improve the self-containedness of the paper.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is clearly written and the code release is commendable. The main risk to the paper's central claims is the gap between the strong practical recommendation (prefer FGM or shortened Silver) and the limited empirical support. In particular, the FGM robustness result could be overturned by a different corruption model, which matters because the PEP worst-case results already show FGM degrading at larger δ. I would like to see the authors either strengthen the experiments (more datasets, error bars, more targeted corruption directions) or temper the claims in the abstract and conclusion. The self-citations appear relevant and appropriate, as the shortening factor builds directly on the authors' prior work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading. It gives the first PEP-based worst-case curves I know of for long-step and accelerated methods under relative gradient inexactness, and it introduces a simple shortening factor, 1/(1+δ), that makes the worst-case rates substantially better for Silver, dynamic, and constant-step schedules. The motivation from the divergence threshold h > 2/(1+δ) on a quadratic is clean and independently checkable. The authors are honest that the factor is semi-heuristic, and the GitHub code makes the numerics reproducible in principle. The compression experiments are also useful: they show that mantissa truncation barely hurts any method, which is a practically relevant observation for large-scale GPU training.\n\nThe main soft spot is the empirical claim that FGM is \"much more robust than expected.\" In the adversarial corruption experiment, the error is chosen to point away from x*, which is a valid perturbation but not chosen adversarially with respect to FGM. For an accelerated method that overshoots, that direction can be benign. The paper's own PEP worst-case curves in Figure 2a show FGM degrading substantially for δ ≥ 0.4, so the empirical robustness is a statement about a specific attack, not about worst-case behavior. The authors do phrase it as \"this kind of adversarial error,\" which limits the overclaim, but the practical recommendation to prefer FGM leans on this experiment. The shortening-factor recommendation is on firmer ground because Figure 2b provides independent PEP evidence for long-step methods; the same cannot be said for FGM.\n\nThe empirical section is otherwise thin in the usual ways: one presented dataset, six initial points, no error bars, and a second dataset mentioned only in parentheses. That is acceptable for a first look but not enough to support strong practical preferences. The compression results even show compression sometimes helping, which the authors attribute to truncation effectively shrinking step sizes; that is plausible but worth a more careful test.\n\nOverall, the central idea is sound, the writing is clear, and the weaknesses are in the empirical support rather than in the logic. This deserves a serious referee and probably a conditional accept after the authors either strengthen the FGM robustness evidence or soften the recommendation. I would cite this paper for the shortening factor and the PEP methodology application, and I would bring it to a reading group as a good example of computer-aided analysis done honestly.\n\nSend it to peer review.","headline":"Useful, honest paper on relative inexactness; the shortening factor is plausible and partly supported by PEP curves, but the headline claim that FGM is robust rests on one specific corruption model and needs stronger empirical support.","tokens_in":10100,"tokens_out":1783,"would_cite":true,"duration_ms":22252,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"Dividing every step size by 1/(1+δ) makes long-step and accelerated gradient methods robust to relative gradient error.","keywords":["performance estimation","relative inexactness","compressed gradient descent","long-step methods","silver stepsize","accelerated gradient method","smooth convex optimization","robustness"],"falsifier":"Run the shortened Silver and dynamic schedules on a different smooth convex problem with an adversarial relative error at δ=0.5 and compare accuracy against the unshortened versions; if shortening no longer improves accuracy, or if PEP worst-case rates for shortened FGM exceed those of the unshortened method, the uniform-repair claim loses support.","tokens_in":9177,"feed_emoji":"🧮","tokens_out":7689,"duration_ms":63077,"temperature":0.7,"pith_summary":"This paper asks whether first-order optimization methods keep their convergence guarantees when gradient computations are only relatively accurate, meaning the error in each gradient is bounded by a fraction δ of the gradient norm. Using worst-case performance estimation, it shows that long-step schedules (dynamic and Silver) and the accelerated fast gradient method lose robustness quickly as δ grows, sometimes producing a worst-case rate worse than taking no iteration at all. The paper then proposes a semi-heuristic repair: divide every step size by the shortening factor 1/(1+δ), a value motivated by a divergence threshold for constant-step gradient descent. In worst-case rates this recovers useful convergence, and in experiments on a logistic regression problem the shortened schedules, especially Silver steps, become competitive again, while FGM proves far more robust empirically than the worst-case theory predicts.","feed_headline":"Step-size fix rescues gradient methods from relative inexactness","feed_subtitle":"Dividing steps by 1+δ restores long-step robustness; accelerated FGM beats its worst-case bound in practice.","key_machinery":"The carrying mechanism is the performance estimation problem (PEP), a reformulation of worst-case analysis as a semidefinite program that computes tight convergence rates for a given algorithm and function class; the relative inexactness condition ‖d_k−∇f(x_k)‖≤δ‖∇f(x_k)‖ is added as an extra constraint. The second key object is the shortening factor 1/(1+δ), which rescales every step size of a schedule. It is motivated by the observation that constant-step gradient descent with step h>2/(1+δ) diverges on the one-dimensional quadratic f(x)=Lx²/2, while the standard proof of convergence on smooth convex functions survives as long as h≤2/(1+δ). Applying this uniform rescaling to the dynamic, Silver, and FGM schedules is the semi-heuristic repair whose worst-case and empirical effects the paper measures.","core_discovery":"On the paper's own terms, the central discovery is that the factor 1/(1+δ) acts as a uniform repair for step-size schedules under relative gradient inexactness, and that accelerated methods are much more robust in practice than their worst-case guarantees suggest. The performance-estimation analysis shows that without shortening, Silver and dynamic schedules degrade sharply as δ increases, and even FGM's rate worsens; with every step size divided by 1+δ, worst-case rates improve substantially. In the compressed-gradient experiment, no method is significantly harmed by mantissa truncation, and the exact-case ordering of methods persists. In the adversarial-corruption experiment, FGM keeps high accuracy even at large δ, and shortened Silver steps rival FGM for δ≤0.3, while the shortening factor slightly hurts constant-step and FGM. The paper concludes with a robustness ranking that recommends FGM, and shortened Silver steps when a memoryless method is wanted.","pith_inferences":["If the shortening heuristic transfers beyond logistic regression, the same 1/(1+δ) rescaling could be applied to other fixed-schedule methods, such as restarted or adaptive variants, with similar robustness gains; this is a testable extension the paper does not perform.","The large empirical gap between FGM's observed robustness and its worst-case rate suggests the relative-inexactness model is pessimistic for realistic compression, pointing toward stochastic or average-case analyses of compressed gradients.","A natural next experiment is to measure the actual δ induced by mantissa truncation in neural-network training; the paper's bound δ=(1/2)^{nbit+1} likely overstates typical error, implying that even larger memory savings could be safe.","The stability threshold h≤2/(1+δ) offers a rule of thumb for any gradient method: keep effective step sizes below the inexactness-adjusted limit, which may also explain why some adaptive methods tolerate low-precision gradients."],"forward_implications":["Shortening by 1/(1+δ) turns the theoretically fragile long-step schedules into methods with usable worst-case rates, making them candidates for memory-limited inexact settings.","Compressed gradient descent with mantissas truncated to a few bits can reduce gradient storage by more than a factor of three without harming empirical convergence, since the induced relative error stays below the robustness threshold.","The practical ordering FGM beats Silver beats dynamic and constant-step (matching $O(1/N^2)$, $O(1/N^{1.27})$, and $O(1/N)$) persists under compression, so method choice in inexact settings can follow the exact-case ranking.","Under adversarial corruption the paper recommends FGM as the default, with shortened Silver steps as the memoryless alternative.","Worst-case analysis, although pessimistic for accelerated methods, retains value because it is what suggested the shortening factor that later proved useful empirically."],"supporting_citations":[{"why":"establishes that constant-step gradient descent with h>2/(1+δ) diverges, providing the threshold behind the shortening factor.","marker":"[15]"},{"why":"shows the convergence proof for gradient descent on smooth convex functions survives when h≤2/(1+δ), motivating the 1/(1+δ) rescaling.","marker":"[16]"},{"why":"introduces the Silver step-size schedule that the paper analyzes and shortens.","marker":"[2]"},{"why":"introduces the performance estimation methodology used to compute exact worst-case rates.","marker":"[7]"},{"why":"supplies the interpolation conditions and the optimal constant-step baseline for the PEP reformulation.","marker":"[13]"},{"why":"defines the fast gradient method (FGM) that serves as the accelerated baseline.","marker":"[10]"},{"why":"defines the dynamic step-size schedule analyzed as a long-step method.","marker":"[14]"},{"why":"supplies the software toolbox used for the numerical worst-case computations.","marker":"[8]"},{"why":"shows how to incorporate inexact gradient constraints into performance estimation for smooth convex optimization.","marker":"[5]"}],"fun_headline_variants":["Shortening factor restores robustness in long-step methods","Accelerated methods exceed worst-case robustness bounds","Shorten steps to stay robust under gradient inexactness","Divide steps by 1+delta to fix long-step methods"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The shortening factor is derived from a divergence threshold for constant-step gradient descent, and the paper assumes that dividing every step size of the Silver, dynamic, and FGM schedules by 1+δ preserves or restores their convergence; this is validated experimentally only on one logistic-regression dataset with six starting points.","fun_headline_variants_meta":{"raw":{"variants":["Shortening factor restores robustness in long-step methods","Accelerated methods exceed worst-case robustness bounds","Shorten steps to stay robust under gradient inexactness","Divide steps by 1+delta to fix long-step methods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001563,"raw_usage":{"total_tokens":6221,"prompt_tokens":899,"completion_tokens":5322,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":5257}},"tokens_in":515,"tokens_out":5322,"duration_ms":45157,"temperature":1.0,"reasoning_tokens":5257,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:41:55.834389+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the shortened Silver and dynamic schedules on a different smooth convex problem with an adversarial relative error at δ=0.5 and compare accuracy against the unshortened versions; if shortening no longer improves accuracy, or if PEP worst-case rates for shortened FGM exceed those of the unshortened method, the uniform-repair claim loses support.","supporting_citations":[{"cited_title":"Tight convergence analysis of exact a nd inexact gradient meth- ods with constant and silver schedules","cited_arxiv_id":null,"evidence_quote":"establishes that constant-step gradient descent with h>2/(1+δ) diverges, providing the threshold behind the shortening factor."},{"cited_title":"Acceleration by st epsize hedging: Silver stepsize schedule for smooth convex optimization","cited_arxiv_id":null,"evidence_quote":"introduces the Silver step-size schedule that the paper analyzes and shortens."},{"cited_title":"Performance of first-order m ethods for smooth convex minimization: a novel approach","cited_arxiv_id":null,"evidence_quote":"introduces the performance estimation methodology used to compute exact worst-case rates."},{"cited_title":"Smooth strongly con- vex interpolation and exact worst-case performance of first -order methods","cited_arxiv_id":null,"evidence_quote":"supplies the interpolation conditions and the optimal constant-step baseline for the PEP reformulation."},{"cited_title":"A method for unconstrained convex minim ization problem with the rate of convergence O(1/k 2)","cited_arxiv_id":null,"evidence_quote":"defines the fast gradient method (FGM) that serves as the accelerated baseline."},{"cited_title":"An elementary approa ch to tight worst case complexity analysis of gradient based methods","cited_arxiv_id":null,"evidence_quote":"defines the dynamic step-size schedule analyzed as a long-step method."},{"cited_title":"Pepit: computer-assisted worst-case analyses of first-order optimization methods in python","cited_arxiv_id":null,"evidence_quote":"supplies the software toolbox used for the numerical worst-case computations."},{"cited_title":"W orst-case convergence analysis of inexact gradient and newton methods through sem idefinite program- ming performance estimation","cited_arxiv_id":null,"evidence_quote":"shows how to incorporate inexact gradient constraints into performance estimation for smooth convex optimization."}],"review_version":1}