{"id":"cdbacb0d-d699-4ac5-93e0-752d3a8d8a28","arxiv_id":"2607.21579","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"For every dimension n≥4, open families of strictly convex quadratics and starting points exist where BB1 converges no faster than a fixed geometric rate, ruling out superlinear convergence on a positive-measure set.","lead":"Barzilai–Borwein, a widely used gradient method that picks its step size from recent curvature, is shown to converge only at a fixed geometric rate on an open family of simple quadratic problems in every dimension n≥4, so the hoped-for superlinear speed is ruled out there. The paper gives the first rigorous, positive-measure lower-rate construction for BB1, backed by a computer-assisted proof of an attracting seven-cycle.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The existence and stability of the seven-cycle rest entirely on Certificate 5.1; as printed, interval_cert.py is not runnable (RSTR/PSTR contain line-break artifacts) and no independent run is reported, so a transcription error in R or P would invalidate Theorem 2.1.","rationale":"I read the paper as attempting to prove a robust lower-rate result for BB1 by constructing a certified attracting seven-cycle in dimension four and lifting it by continuity to open sets in every n≥4. For the central claim to hold, three ingredients are needed: (i) the exact zero u* exists, (ii) the seven-cycle is attracting with the certified rate constants, and (iii) the analytic continuation/lifting is valid. Ingredient (iii) is handled by standard IFT, Floquet, and continuity arguments that are clearly written and appear correct. Ingredients (i) and (ii) are entirely delegated to Certificate 5.1 and the Python script. I examined the script and the manuscript's own limitations: the paper says the script 'contains all entries of the rational preconditioner and Lyapunov matrices,' but the printed RSTR/PSTR strings are corrupted by line-break markers, and no output log or independent verification is included. The certificate could be perfectly correct—the displayed constraints are numerically plausible and self-consistent—but the current evidence is insufficient to certify them. This is a mechanical gap, not a detected mathematical inconsistency. The reader identified exactly this weakest assumption; I agree. The natural remedy is the concrete test above: reconstruct and run the script, then reimplement the interval computations independently. Passing that check would upgrade the verdict to ACCEPT. Since the reader already set CONDITIONAL and my concern does not move beyond that, I leave the verdict unchanged.","tokens_in":26210,"tokens_out":25309,"duration_ms":239666,"concrete_test":"Obtain the arXiv source of Appendix A, remove the line-wrap artifacts to reconstruct interval_cert.py verbatim, and run it under CPython (decimal module, precision 120). Verify every printed assertion and compare it to Certificate 5.1: Krawczyk ratios <3.876379e-20; contraction <7.200691e-27; Z minima >0.1516357118221540 and >0.0009510722601452239; separation minima (including the ν-box) >1.3886903675e-4 and >7.5691389311e-2; LDLT pivots above the four positive bounds in (43); Q7 diagonal-dominance margins above the four values in (44); τ(ν)∈(0.0230006289035345, 0.0482036188628888); and a0−a1>0.1782019618055700634. Then independently reimplement the same interval Newton and the P/Q7 checks in a different interval-arithmetic library (e.g., Julia IntervalArithmetic) using the exact rational constants; if any assertion fails in either run, Certificate 5.1 is invalid and Theorem 2.1 loses it","verdict_should_be":"UNCHANGED","load_bearing_attack":"The key step is the computer-assisted proof of a root u* of the eight rational equations G(u)=0 and the strict inequalities in Certificate 5.1 (C1)-(C7). Everything downstream—existence of the seven-cycle, Schur stability via P−A7ᵀPA7≻0, separation bounds, transverse Floquet multipliers, and hence the open family in Theorem 2.1—consumes these inequalities as black boxes. The certificate is implemented by interval_cert.py in Appendix A, which hard-codes the 8×8 preconditioner R and Lyapunov matrix P as decimal literals. As rendered in the preprint, that script is not directly executable: RSTR and PSTR are broken across lines with inserted '↪→' and '⌋' artifacts, so the exact rational entries intended by the authors are not unambiguously recoverable from the printed appendix. Moreover, no independent run or cross-check of the script is reported, and the paper states no formal verification (e.g., Coq/Lean) of the interval arithmetic. Because the interval Newton proof depends on the exact values of R and P—a single mistyped digit in R could destroy the contraction bound (C2), and a wrong entry in P could destroy P≻0 or Q7≻0—the center of Theorem 2.1 is exactly as secure as the unverified script. The analytic reductions in §§4-9 are standard and appear sound; the weakness is entirely at this certificate.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every dimension n≥4 and every linear term b, there exists a nonempty open set of strictly convex quadratic problems and initial points on which the Barzilai–Borwein method BB1 converges, but every spectral component of the gradient decays at a two-sided geometric rate with explicit constants 10^{-6} and 0.61. Consequently liminf ||g_k||^{1/k} ≥ 10^{-6}, ruling out root-superlinear and Q-superlinear convergence on a positive-measure family. The proof reduces BB1 on quadratics to a projective rational map, certifies by interval arithmetic an attracting seven-cycle with an exact fifteen-step admissible connection in dimension four, proves Schur stability via a Lyapunov inequality, translates the spectrum to obtain the rate constants, continues the construction by the implicit-function theorem, embeds it into every n>4 via transverse Floquet bounds, and finally lifts the projective family to problem data by changes of variables. Theorem 2.1 states the result; Sections 4–9 supply the proof.","tokens_in":26627,"tokens_out":28879,"duration_ms":291962,"significance":"If the computer-assisted certificate is correct, this is a substantial negative answer to the almost-everywhere superlinearity question for BB1 on strictly convex quadratics. The paper identifies a robust dynamical mechanism — an attracting nonresonant seven-cycle — rather than a null-measure exceptional example, and it gives explicit, if conservative, rate constants. The analytic parts of the proof are careful and mostly standard: the reduction to the projective map, the translation conjugacy, the IFT continuation, and the Floquet embedding into higher dimensions are coherent and appear sound. A particular strength is the honest statement of limitations and the explicit acknowledgement that the construction is an existence result, not a universal rate formula. The main weakness is entirely at the computer-assisted certificate: the supplied script is the sole evidence for the strict inequalities that feed every later implication, and as printed it is not reproducible. The paper also discloses AI-assisted proof development, which is not a scientific defect but increases the need for machine-checkable artifacts.","major_comments":[{"comment":"The central claim of Theorem 2.1 is conditional on the interval certificate in §5.2. As printed, the script is not executable: the triple-quoted strings RSTR and PSTR contain line-break artifacts ('↪→' and '⌋') and split numeric literals across lines, so the intended exact entries of the preconditioner R and Lyapunov matrix P cannot be recovered unambiguously. No output transcript is included. A single digit error in R could destroy the contraction bound (38), and an error in P could destroy P≻0 or P−A7ᵀPA7≻0. The certificate therefore currently functions as an unverifiable black box. Please supply a clean ancillary source file and the full output of the script (Krawczyk ratios, contraction bound, LDLT pivots, Gershgorin margins, separation values, and the transverse τ interval).","section":"Appendix A, interval_cert.py; Certificate 5.1(C1)–(C7)"},{"comment":"The rigorous existence and stability of the seven-cycle depend on strict inequalities that are asserted from the script but not independently reproduced. In particular, P≻0 and P−A7ᵀPA7≻0 are certified by interval LDLT pivots and Gershgorin margins, and the transverse Floquet bound (45) is certified by one interval computation, but the paper does not report the script's actual printed values for these quantities. Because every downstream conclusion — the open basin, the rate bounds, and the n>4 embedding — consumes these inequalities as black boxes, the authors should either include a full verification transcript or an independent cross-check (e.g., interval arithmetic in another language or a formal proof assistant) before the theorem can be considered established.","section":"§5.2, (C5)–(C7); §6, Lemma 6.2"}],"minor_comments":[{"comment":"The two rate constants are both rendered as ρ in several places; in the main text they are denoted with under/overbars. Please ensure the final PDF clearly distinguishes \\underline{\\rho}=10^{-6} from \\overline{\\rho}=0.61.","section":"Abstract; Eq. (6)"},{"comment":"The caption of Fig. 1 states that the transient minimum of the one-step multiplier is approximately 1.7×10^{-5}, while Certificate 5.1(C4) reports a separation lower bound of 1.388×10^{-4}. This is not contradictory if Fig. 1 refers to the shifted spectrum and to the ratio |a_k−λ_i|/a_k, but the captions should say so explicitly to avoid apparent inconsistency.","section":"Figs. 1 and 3"},{"comment":"The statement that Li and Sun's 'generic initialization' question is 'answered in the negative on an open set of matrices' could be misread as disproving almost-everywhere fast convergence for a fixed matrix. The theorem actually gives a positive-measure set of joint (A,x0) pairs. Please phrase this as 'on a positive-measure set of joint problem-data pairs' to match the theorem. The LLM prompt in Appendix B is long and not part of the mathematical proof; consider moving it to supplementary material or an acknowledgments note.","section":"§1; Appendix B"}],"recommendation":"major_revision","confidential_remarks":"My assessment is that the analytic structure of the paper is sound and the result is significant if the certificate holds. The sole reason for major revision, rather than acceptance, is that the computer-assisted certificate is not verifiable from the manuscript as it stands: the script is not runnable as printed and no output is provided. I would be willing to accept after the authors provide a clean, runnable implementation together with a complete transcript of all asserted inequalities, or an independent verification. The AI-assisted development disclosure does not itself concern me, but it reinforces the need for machine-checkable artifacts."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper answers a question that has been open for a while: for every n≥4, there is a nonempty open set of strictly convex quadratics and initializations where BB1 converges only linearly, with each spectral component between 10^-6 and 0.61 per step, so superlinear convergence fails on a positive-measure family. That is genuinely new — Li and Sun's lower-rate example was Lebesgue-null, and Dai and Fletcher's dimension-four transition was asymptotic and numerical. If correct, it settles the almost-everywhere superlinearity question negatively on an open set.\n\nThe analytic machinery is well built. The reduction of BB1 to a projective rational map, the certified seven-cycle via interval Newton, attraction via a Lyapunov inequality, continuation by the implicit-function theorem, embedding into higher dimensions with transverse Floquet bounds, and the lift to original problem data are all standard moves, and I could not find a gap in the pen-and-paper parts. The paper is also appropriately scoped and transparent about its constants and limitations.\n\nThe soft spot is exactly the certificate. Theorem 2.1's existence, stability, and openness all rest on Certificate 5.1's strict inequalities, which come from interval_cert.py in Appendix A. As printed, that script is not runnable: the long string constants RSTR and PSTR are broken across lines with inserted arrow and guillemet artifacts, so the exact rational entries of the preconditioner and Lyapunov matrix are not unambiguously recoverable. No independent run is reported, and there is no formal verification. A single mistyped digit in R or P would destroy the contraction or the positive-definiteness and collapse the proof. That is a mechanical red flag, not a detected mathematical error, but it is load-bearing. The paper's disclosure that a language model produced the initial sketch is honest and beside the point; it just makes a clean, versioned certificate more necessary.\n\nMinor notes: the rate constants are conservative and the result is an existence theorem, both stated clearly. The reference list is appropriate.\n\nWho should read it: optimization researchers interested in BB methods or in computer-assisted proofs of dynamical systems. It deserves a serious referee, but only if the certificate is supplied as a clean, runnable, versioned artifact and ideally independently checked. I wouldn't cite it in my own work until that happens, and I'd suggest the authors provide the script and outputs as supplementary material. Engage with the work — this is the strongest lower bound on BB1's generic behavior I've seen — but engage with the certificate first.","headline":"A real answer to a long-open BB question, but the entire proof leans on a single interval-arithmetic certificate that, as printed, is not independently runnable.","tokens_in":27094,"tokens_out":3108,"would_cite":false,"duration_ms":28736,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K05","90C30","37N40","37C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"BB1 gradient method provably loses superlinear convergence on an open, positive-measure family of quadratics in every dimension n≥4, via a certified attracting seven-cycle.","keywords":["Barzilai-Borwein","BB1","superlinear convergence","strictly convex quadratics","periodic orbit","computer-assisted proof","interval arithmetic","positive measure"],"falsifier":"Re-run the supplied interval_cert.py script in arbitrary-precision interval arithmetic and check that the printed Krawczyk containment, contraction bound <7.200691e-27, positive pivots of P, positive diagonal-dominance margins of Q_7, and all separation and denominator certificates reproduce exactly; a single violated assertion would falsify the certified root and with it the theorem. Independently, a long high-precision BB1 simulation on the central translated spectrum with the described initial weights should show the four gradient components decaying in parallel between the two geometric en","tokens_in":26103,"feed_emoji":"","tokens_out":3094,"duration_ms":26572,"temperature":0.7,"pith_summary":"This paper tries to settle a long-standing question: does the Barzilai–Borwein (BB1) gradient method converge superlinearly for almost every strictly convex quadratic problem and initialization? The authors answer no by constructing, for every dimension n≥4, a nonempty open (hence positive-Lebesgue-measure) set of quadratics and initial points on which BB1 converges but only at a guaranteed linear rate, with gradient components bounded between 10^{-6k} and 0.61^k times their initial values. The slow behavior is not a fragile exception: it persists under perturbations of both the Hessian spectrum and the starting point. The proof identifies a concrete dynamical mechanism—a nonresonant, attracting period-seven orbit of the projectivized BB dynamics in dimension four, validated by a computer-assisted interval-arithmetic certificate—and then uses stability, translation, and eigenvalue-clustering arguments to lift the example to every finite dimension.","feed_headline":"BB1 method provably stalls at linear rate on open set","feed_subtitle":"A certified attracting seven-cycle rules out almost-everywhere superlinear convergence for the Barzilai–Borwein method in every dimension n≥","key_machinery":"The engine of the proof is a certified nonresonant attracting seven-cycle of the projectivized BB1 dynamics in dimension four. The projective state (a_k, p_k), where a_k is the reciprocal step size and p_k the normalized squared spectral weights, evolves under a rational map F_λ; the authors find an exact root of eight rational equations—a seven-cycle F^7(z)=z together with a fifteen-step landing F^{15}(D(r))=z from admissible initial data—by interval Newton/Banach contraction inside a 10^{-55} box. A Lyapunov pair P≻0, P−A_7^T P A_7≻0 proves the cycle is Schur stable and hence attracting in an open basin; a translation by four makes the spectral width small enough to force the 0.61 upper ra","core_discovery":"The central claim, Theorem 2.1, is that for every n≥4 and every b∈R^n there exist nonempty open sets A_n⊂S^n_{++} of simple-spectrum strictly convex quadratics and open sets X_n(A) of initial points such that every admissibly initialized BB1 trajectory satisfies the two-sided geometric bound 10^{-6k}∥Π_i(A)g_0∥ ≤ ∥Π_i(A)g_k∥ ≤ 0.61^k∥Π_i(A)g_0∥ for each spectral component i and all k. Consequently the gradient norm, energy norm of the error, and objective gap all decay at a rate bounded below by a positive geometric sequence, giving liminf ∥g_k∥^{1/k} ≥ 10^{-6} > 0. This rules out root-superlinear and Q-superlinear convergence and refutes any almost-everywhere superlinearity statement for BB","pith_inferences":["Because the construction is open in joint problem-data space (A,x_0), a natural testable extension would be to check whether small random perturbations of the certified spectrum and initial point, in simulations of BB1 on n=4 quadratics, actually display the predicted geometric decay with the certified seven-cycle as an attractor.","The same projective-attractor mechanism may explain observed slow phases of BB-type steps in nonquadratic problems and in spectral/safeguarded variants: wherever the delayed Rayleigh quotient locks onto a resonant cycle of step sizes, superlinear escape is precluded.","The gap between the certified lower rate 10^{-6} and the observed asymptotic factor β^{1/7}≈0.144 along the cycle suggests the true obstruction may be stronger than the conservative theorem states; sharper constants might be obtained by optimizing the Lyapunov certificate.","The translation trick reveals how the lower rate emerges from separation (nonresonance) while the upper rate emerges from spectral width; this split may transfer to other spectral gradient rules whose projective dynamics is translation-invariant."],"forward_implications":["If correct, the longstanding conjecture of almost-everywhere superlinear convergence for BB1 on strictly convex quadratics is false in every dimension n≥4; the slow behavior is open and positive-measure, not a null-set exception.","Linear-rate behavior for BB1 is caused by a stable recurrent attractor (a period-seven orbit), not merely by invariance of coordinate subspaces; four spectral modes remain active, producing a seven-periodic normalized spectral measure rather than collapse to two endpoint modes.","The construction answers the specific open question raised by prior R-linear upper bound work: generic initialization does not automatically accelerate BB1, even on an open set of spectra.","The rate constants 10^{-6} and 0.61 are uniform across all finite dimensions n≥4, even though the size of the open neighborhood is dimension-dependent, so the obstruction to superlinearity is authentically n-dimensional.","The method of proof—computer-assisted certification of a periodic orbit plus analytic continuation—offers a template for proving robust lower bounds on convergence rates in other history-dependent gradient methods."],"fun_headline_variants":["BB1 superlinear fail proven on open sets for n≥4","BB1 cannot superconverge on open set for any n≥4","Barzilai-Borwein linear-only on an open set of quadratics","Open set of quadratics traps BB1 in linear decay for n≥4","Certified seven-cycle blocks BB1 superlinearity for all n≥4"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole theorem rests on the computer-assisted certificate (Certificate 5.1): the interval-arithmetic script must genuinely prove that the exact root exists, that the cycle is attracting (P≻0 and P−A_7^T P A_7≻0), and that the separation bounds hold; any error in the hard-coded rational preconditioner, Lyapunov matrix, or arithmetic evaluation would collapse the open-family construction.","fun_headline_variants_meta":{"raw":{"variants":["BB1 superlinear fail proven on open sets for n≥4","BB1 cannot superconverge on open set for any n≥4","Barzilai-Borwein linear-only on an open set of quadratics","Open set of quadratics traps BB1 in linear decay for n≥4","Certified seven-cycle blocks BB1 superlinearity for all n≥4"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001015,"raw_usage":{"total_tokens":4165,"prompt_tokens":828,"completion_tokens":3337,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":3235}},"tokens_in":572,"tokens_out":3337,"duration_ms":22979,"temperature":1.0,"reasoning_tokens":3235,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T07:01:23.482039+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the supplied interval_cert.py script in arbitrary-precision interval arithmetic and check that the printed Krawczyk containment, contraction bound <7.200691e-27, positive pivots of P, positive diagonal-dominance margins of Q_7, and all separation and denominator certificates reproduce exactly; a single violated assertion would falsify the certified root and with it the theorem. Independently, a long high-precision BB1 simulation on the central translated spectrum with the described initial weights should show the four gradient components decaying in parallel between the two geometric en","supporting_citations":[],"review_version":1}