{"id":"bd191cc7-3a18-4c9f-a9ba-1fb879cb0952","arxiv_id":"2506.17145","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For smooth convex functions, relatively inexact gradient descent has a three-regime worst-case one-step rate, and the largest provably safe stepsize is 2/(1+delta).","lead":"The paper derives worst-case convergence rates for gradient descent when each gradient carries a relative error bounded by a fraction of the true gradient norm. It shows the method converges for stepsizes up to a sharp threshold, with an exact rate for one step and computable bounds for many steps.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exactness claim for the one-step rate rests on the unproven Conjecture 2.6 in the intermediate stepsize regime; this is the load-bearing gap.","rationale":"The paper provides a careful PEP-based analysis with explicit multiplier constructions, open code, and proven tightness for the left and right regimes. However, the strongest novelty claim — 'exact worst-case behavior after one step' — depends on the intermediate regime being tight, and that tightness is explicitly left as Conjecture 2.6. This is exactly the weakest assumption identified by the reader. The gap is load-bearing because if the conjecture is false, the central claim is an overstatement: the contribution reduces to a proven upper bound plus tightness in two of three regimes. I do not see a more fundamental internal inconsistency in the upper-bound proofs; the delegation of lengthy symbolic verification to SymPy/Mathematica is standard in the PEP literature, and the multi-step lower-bound sketch in Theorem 3.2 is a plausible direct generalization of the one-step constructions. Therefore the reader's conditional verdict is appropriate, and no adjustment is needed.","tokens_in":22986,"tokens_out":6875,"duration_ms":76011,"concrete_test":"For a fixed δ = 0.5 and h set to the midpoint of the intermediate interval, solve the one-step PEP with the added constraint that the interpolating function has dimension 2 using the nonconvex formulation of [33], certified to global optimality via branch-and-bound or an exact sum-of-squares relaxation. Repeat for a fine grid of h covering the intermediate regime. If the certified optimum equals C(h, δ) at every grid point, Conjecture 2.6 is verified; if a strict gap is certified at any h, the abstract must be weakened to state that the one-step rate is an upper bound with tightness proven only in the left and right regimes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract claims the authors 'derive the exact worst-case behavior of the method after one step.' This exactness claim is only fully proven for the left and right regimes of Theorem 2.3 (Theorem 2.4 gives explicit Huber and quadratic worst-case functions). For the intermediate regime, the lower bound is not proven: Conjecture 2.6 states tightness and bivariate worst-case structure, but the paper provides only numerical PEP evidence and a two-dimensional construction that matches the bound 'specifically at the optimal stepsize' (Section 2.4). No analytical worst-case function or certified lower-bound certificate is given for the whole intermediate interval. Consequently, the central headline claim is not currently a theorem for h in the intermediate regime. The multi-step Theorem 3.2 is a sketch, but its construction appears to be a direct N-step adaptation of Theorem 2.4, so the more substantive risk is the one-step exactness claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript analyzes constant-stepsize gradient descent with relative gradient inexactness on L-smooth convex functions. Using the Performance Estimation Problem (PEP) framework, it derives a one-step worst-case upper bound C(h, delta) with three stepsize regimes (Theorem 2.3), proves tightness of the left and right regimes via explicit Huber and quadratic worst-case functions (Theorem 2.4), and conjectures tightness of the intermediate regime (Conjecture 2.6). It then extends the analysis to several steps with an upper bound (Theorem 3.1), a lower bound (Theorem 3.2), and numerical observations on optimal stepsizes. The abstract advertises an 'exact worst-case' one-step result, but the intermediate-regime tightness is not proven.","tokens_in":23116,"tokens_out":4448,"duration_ms":50261,"significance":"If the intermediate-regime conjecture were resolved, the paper would provide the exact one-step worst-case rate for relatively inexact gradient descent on smooth convex functions, with a clean three-regime structure and explicit worst-case functions in the two outer regimes. The proven upper bound also yields an admissible stepsize range h in [0, 2/(1+delta)] that improves on previous bounds such as those of Vasin. The use of PEP with explicit multiplier constructions, computer-assisted symbolic algebra, and openly available code is a strength: the derivation is self-contained and reproducible. However, the advertised exactness claim for the one-step rate is only fully proven in the left and right regimes; the intermediate regime rests on numerical evidence, so the significance of the central claim is currently conditional.","major_comments":[{"comment":"The abstract and Section 1.3 claim that the paper derives 'the exact worst-case behavior of the method after one step.' This exactness claim is not established for the whole one-step stepsize range. Theorem 2.3 provides an upper bound, and Theorem 2.4 proves tightness only in the left and right regimes. For h in the intermediate interval [3/(2(1+delta)), (3delta+2-sqrt(4-3delta^2))/(2delta(delta+1))], the lower bound is Conjecture 2.6, supported by numerical PEP solutions and a bivariate construction that matches the bound only at the optimal stepsize (Section 2.4, Figure 2.6). The manuscript should either supply a certified analytical lower-bound certificate for the whole intermediate interval or amend the abstract and introduction to state the result as a proven upper bound with a conjectured matching lower bound.","section":"Section 2.4; Conjecture 2.6"},{"comment":"The lower-bound theorem for N steps is not fully proved. The proof defines f1 and f2 and then says the result follows 'using an argument similar to that in Theorem 2.4, adapted to the N-steps case.' This adaptation is nontrivial: one must verify that the iterates stay in the appropriate linear/quadratic regions for all N steps, that the max of the two candidate lower bounds is valid for every h in [0, 2/(1+delta)], and that the boundary between the regimes is handled. As written, this is a proof sketch rather than a complete proof; it should be expanded or the statement should be marked as conditional.","section":"Section 3.2; Theorem 3.2"},{"comment":"Remark 3.3 asserts that a sharper upper bound, matching the lower bound 2(1-h(1+delta))^{-2N}, holds for all h >= h_tilde(N), where h_tilde(N) is defined implicitly as a root of a polynomial whose degree increases with N. No proof or even outline is provided for this claim. Since this remark is used to support the statement that the multi-step rate is tight on [h_tilde(N), 2/(1+delta)), it should be proved, or explicitly labeled as a conjecture. The definition of h_tilde(N) also needs a uniqueness/validity statement.","section":"Section 3.2; Remark 3.3"}],"minor_comments":[{"comment":"In the proof of Theorem 2.1, 'previsously' should read 'previously.'","section":"Section 2.1"},{"comment":"The axis labels for lambda(h) are garbled: expressions such as 'right = 2 h(1 + ) / h(1 + ) 1' are missing delta and are hard to read. Please render the formulas with proper symbols.","section":"Figure 2.2"},{"comment":"The sentence 'whereas the worse 1D constructions fall short' is grammatically unclear; it should be 'whereas the 1D constructions fall short' or a similar correction.","section":"Section 2.4"},{"comment":"The statement that an explicit worst-case function is provided 'for nearly all values of the stepsize' is accurate, but it would help the reader if the exceptional values were identified explicitly as the intermediate regime, consistent with Conjecture 2.6.","section":"Section 1.5"},{"comment":"Definition 2.2 defines lambda-tilde as the largest real root of a cubic, but the text does not state explicitly that this root is unique and positive over the relevant parameter range. A short lemma or explicit verification would make the definition more robust.","section":"Definition 2.2"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the scope of mathematical optimization journals and the upper-bound results are credible. The main issue is the overstatement of the one-step exactness claim: the intermediate regime is a conjecture, and the multi-step lower-bound theorem is sketched. I do not recommend rejection because the proven portions are valuable and the conjecture is plausibly true, but the manuscript requires either a proof of Conjecture 2.6 or a careful rewording of the claims. The editorial process should also verify that the companion code reproduces the symbolic results claimed in the proof of Theorem 2.3."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should read this as a conditional accept, not a reject. The core new result is real: the one-step worst-case rate for relatively inexact gradient descent on smooth convex functions splits into three regimes, and the sharp stepsize threshold h_max = 2/(1+δ) improves Vasin's earlier bound substantially. The left and right regimes are proven tight with explicit Huber and quadratic worst-case functions, and the worst-case-error-as-stepsize-miscalibration interpretation is a nice insight. The upper-bound proof uses explicit multiplier constructions and ships code, so it is reproducible, and the paper is clear about what is and is not proven.\n\nThe main soft spot is exactly where the reader and the stress-test note put it. The abstract says the authors 'derive the exact worst-case behavior of the method after one step', but that is only true in the left and right regimes. In the intermediate regime, tightness is Conjecture 2.6, supported by numerical PEP evidence and a bivariate construction that matches the bound only at the optimal stepsize, not across the whole interval. The authors are honest about this in the body—they label it a conjecture and say no explicit worst-case instance was found—so the problem is in the framing, not the mathematics. The abstract and introduction should be brought in line with what is actually proven.\n\nThe multi-step lower bound (Theorem 3.2) is sketchy: the proof says 'argument similar to that in Theorem 2.4' without spelling out the N-step construction. It looks plausible, and the functions are given, but a referee will want a complete argument. Remark 3.3 also asserts a sharper bound 'it can be shown' without proof. These are fixable, but they need to be addressed.\n\nOn the positive side, the derivation is self-contained, the cubic defining λ⎯ is structural rather than fitted, and the numerical experiments are clearly separated from the analytical results. The citation pattern looks fine—building on the authors' own earlier PEP work is normal here, and the comparison with [12] is useful.\n\nMy bottom line: send it to peer review. A good referee can push for either a proof of Conjecture 2.6 or a corrected abstract that limits the 'exact' claim to the proven regimes. With that revision, this is a solid contribution to the PEP and inexact-optimization literature.","headline":"The one-step three-regime rate and the sharp h_max = 2/(1+δ) are solid and useful, but the 'exact worst-case' claim rests on an unproven intermediate-regime conjecture.","tokens_in":23653,"tokens_out":2070,"would_cite":true,"duration_ms":25294,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that for smooth convex functions, relatively inexact gradient descent converges for every stepsize $h\\in[0,\\tfrac{2}{1+\\delta}]$ and that the one-step worst-case rate is given by an explicit three-regime formula, with…","keywords":["inexact gradient descent","relative gradient error","smooth convex optimization","worst-case convergence","performance estimation","stepsize selection","semidefinite programming"],"falsifier":"Take $\\delta=0.5$ and a stepsize $h$ strictly inside the intermediate regime, such as the near-optimal value shown in Figure 2.3, and compute a certified upper bound on the one-step worst-case rate using a branch-and-bound performance-estimation method. If the certified value lies strictly below the formula $C(h,\\delta)$ of Theorem 2.3, then the intermediate regime is not tight; if it exceeds it, the upper bound itself fails. A single such gap would settle whether the claimed exact one-step rate is correct.","tokens_in":22754,"feed_emoji":"📉","tokens_out":7534,"duration_ms":82000,"temperature":0.7,"pith_summary":"Gradient descent normally assumes exact gradients, but in practice gradients come with errors. This paper studies a relative error model where the approximate gradient $d$ satisfies $\\|d-\\nabla f(x)\\|\\le \\delta\\|\\nabla f(x)\\|$ for a fixed $\\delta<1$, so the error automatically shrinks near the optimum. The central claim is that on smooth convex functions the worst-case one-step contraction of the squared gradient norm is exactly the explicit three-regime formula stated in Theorem 2.3, and that convergence is guaranteed precisely for stepsizes $h\\le 2/(1+\\delta)$ while larger stepsizes can fail. If correct, the method is far more robust to relative noise than previous bounds suggested, and the optimal constant stepsize becomes nearly independent of the number of iterations once $\\delta$ is moderate. The upper bound is proven for all regimes; the matching lower bound in the middle regime depends on a conjecture supported by numerical performance-estimation evidence.","feed_headline":"Gradient noise shrinks safe step size to 2/(1+δ)","feed_subtitle":"Exact worst-case rates split into three step-size regimes; many small steps beat a few large ones under relative gradient error.","key_machinery":"The central object is the performance-estimation formulation of worst-case analysis: the worst-case rate is posed as an optimization over gradients, iterates, and function values subject to the smooth-convex interpolation inequalities $f_i \\ge f_j + \\langle g_j, x_i-x_j\\rangle + \\tfrac{1}{2L}\\|g_i-g_j\\|^2$ and the relative inexactness constraint $\\|d_0-g_0\\|^2 \\le \\delta^2\\|g_0\\|^2$. The one-step argument takes a nonnegative linear combination of the interpolation inequalities and the inexactness constraint, then reduces the resulting $3\\times 3$ matrix positivity condition, via a Schur complement, to a scalar optimization over a multiplier $\\lambda$; the optimal multiplier is the largest real root $\\tilde\\lambda$ of the cubic in Definition 2.2. This machinery produces the three-regime formula and, in the left and right regimes, the explicit univariate worst-case functions that certify tightness.","core_discovery":"The paper's discovery is that one step of relatively inexact gradient descent on an $L$-smooth convex function has a worst-case behavior split into three stepsize regimes, instead of the two regimes of exact gradient descent. In the left short-step regime $h\\le \\tfrac{3}{2(1+\\delta)}$ the rate for the squared gradient norm in terms of the initial objective gap is $\\frac{1}{h(1-\\delta)}+\\frac12$; in the right long-step regime $h\\ge \\tfrac{3\\delta+2-\\sqrt{4-3\\delta^2}}{2\\delta(1+\\delta)}$ it is $2\\bigl(1-h(1+\\delta)\\bigr)^2$; in the middle regime the rate is $\\frac{2\\tilde\\lambda}{h\\tilde\\lambda^2+(2h-1)\\tilde\\lambda+h-1}$, where $\\tilde\\lambda$ is the largest real root of a cubic equation. The left and right rates are tight, attained by univariate worst-case functions (a Huber-like function and a quadratic), and the worst-case inexact direction is $d=(1\\pm\\delta)\\nabla f(x)$, meaning the worst relative error acts exactly like a miscalibrated stepsize. The intermediate regime is conjectured to be tight with a bivariate worst-case function, for which the paper gives a partial two-dimensional construction and strong numerical evidence but no full analytical proof.","pith_inferences":["If Conjecture 2.6 is correct, the intermediate regime shows that one-dimensional worst-case examples miss the true difficulty of relative inexactness: the error must rotate around the gradient, so analyses restricted to univariate functions systematically understate the worst case.","The near-independence of the optimal stepsize from the iteration count suggests a practical design rule for low-precision training: choose the stepsize near the right end of the intermediate regime once the relative error level is known, and do not increase it as the training horizon grows.","Because the worst-case relative error is equivalent to stepsize miscalibration, accelerated methods with momentum, which are more sensitive to stepsize, may suffer disproportionately under relative inexactness; this is a testable conjecture for a performance-estimation analysis of accelerated variants.","The numerical observation that the worst-case error becomes orthogonal to the gradient at the optimal stepsize hints at a general principle for designing inexact oracles: aligning the error budget perpendicular to the gradient may be the least harmful way to spend an inexactness allowance."],"forward_implications":["For any relative error level $\\delta\\in[0,1)$, convergence to a minimizer is guaranteed for every constant stepsize $h\\le \\tfrac{2}{1+\\delta}$, and this threshold is tight: no larger constant stepsize retains the guarantee.","In the short-step regime the rate per step is scaled by the factor $1-\\delta$, while in the long-step regime the effective stepsize is $h(1+\\delta)$, so relative noise behaves like a deliberate mistuning of the stepsize rather than an arbitrary perturbation.","The optimal stepsize for the worst-case one-step rate lies inside the narrow intermediate regime and, for moderate to large $\\delta$, depends very little on the number of iterations, in contrast to the exact case where the optimal stepsize grows with the iteration count.","For multiple steps, the upper and lower bounds coincide in the left regime, giving a tight $O(1/N)$ rate with the same $\\delta$-dependent prefactor, and a sharper tight subinterval exists in the right regime.","Using a stepsize at the right end of the intermediate regime, $h=\\tfrac{3\\delta+2-\\sqrt{4-3\\delta^2}}{2\\delta(1+\\delta)}$, yields near-optimal worst-case performance across a wide range of iteration counts and inexactness levels."],"supporting_citations":[{"why":"Supplies the exact-case worst-case rate of gradient descent for all constant stepsizes, which the paper extends to the relatively inexact setting.","marker":"[24]"},{"why":"Provides the smooth-convex interpolation conditions and the semidefinite performance-estimation machinery used to formulate and prove the bounds.","marker":"[11]"},{"why":"Gives the earlier tight linear convergence analysis of relatively inexact gradient descent in the strongly convex case, the setting this paper removes.","marker":"[9]"},{"why":"Establishes the prior convergence guarantee for relatively inexact gradient descent that the improved threshold $h\\le 2/(1+\\delta)$ is compared against.","marker":"[12]"},{"why":"Introduces the performance-estimation problem formulation that underlies the numerical lower-bound evidence and proof derivations.","marker":"[10]"},{"why":"The authors' earlier conference version initiated the convex-setting analysis and left it incomplete; this paper completes it.","marker":"[22]"},{"why":"Provides the branch-and-bound technique for fixed-dimension performance estimation used to support the numerical evidence for the intermediate-regime conjecture.","marker":"[33]"}],"fun_headline_variants":["Exact worst-case rates reveal three regimes under gradient noise","Worst-case inexact gradient equals miscalibrated step size","Three-step-size regime split for gradient descent with relative error","Tight bounds for noisy gradient descent: short vs long step split"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that the one-step rate is exactly the stated formula in the intermediate regime rests on Conjecture 2.6, which asserts tightness of the bound and bivariate worst-case structure, but is supported only by numerical performance-estimation evidence and a partial two-dimensional construction, not by an analytical worst-case function.","fun_headline_variants_meta":{"raw":{"variants":["Exact worst-case rates reveal three regimes under gradient noise","Worst-case inexact gradient equals miscalibrated step size","Three-step-size regime split for gradient descent with relative error","Tight bounds for noisy gradient descent: short vs long step split"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00021,"raw_usage":{"total_tokens":1423,"prompt_tokens":971,"completion_tokens":452,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":587,"completion_tokens_details":{"reasoning_tokens":381}},"tokens_in":587,"tokens_out":452,"duration_ms":5245,"temperature":1.0,"reasoning_tokens":381,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T23:30:00.752868+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $\\delta=0.5$ and a stepsize $h$ strictly inside the intermediate regime, such as the near-optimal value shown in Figure 2.3, and compute a certified upper bound on the one-step worst-case rate using a branch-and-bound performance-estimation method. If the certified value lies strictly below the formula $C(h,\\delta)$ of Theorem 2.3, then the intermediate regime is not tight; if it exceeds it, the upper bound itself fails. A single such gap would settle whether the claimed exact one-step rate is correct.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the smooth-convex interpolation conditions and the semidefinite performance-estimation machinery used to formulate and prove the bounds."},{"cited_title":"De Klerk, F","cited_arxiv_id":null,"evidence_quote":"Gives the earlier tight linear convergence analysis of relatively inexact gradient descent in the strongly convex case, the setting this paper removes."},{"cited_title":"Gradient directions and relative inexactness in optimization and machine learning","cited_arxiv_id":"2407.00667","evidence_quote":"Establishes the prior convergence guarantee for relatively inexact gradient descent that the improved threshold $h\\le 2/(1+\\delta)$ is compared against."},{"cited_title":"Drori, M","cited_arxiv_id":null,"evidence_quote":"Introduces the performance-estimation problem formulation that underlies the numerical lower-bound evidence and proof derivations."},{"cited_title":"Vernimmen, F","cited_arxiv_id":null,"evidence_quote":"The authors' earlier conference version initiated the convex-setting analysis and left it incomplete; this paper completes it."},{"cited_title":"Das Gupta, B","cited_arxiv_id":null,"evidence_quote":"Provides the branch-and-bound technique for fixed-dimension performance estimation used to support the numerical evidence for the intermediate-regime conjecture."}],"review_version":1}