{"id":"b4c1fd7d-293a-410c-bbbd-298afa554ea1","arxiv_id":"1908.07111","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"For a family of gradient methods on quadratics, the iterates asymptotically zigzag between the extreme eigenvectors; a new stepsize converging to 1/λn breaks the zigzag and yields a competitive periodic method.","lead":"This paper proves that a broad family of gradient step sizes, including steepest descent and minimal gradient methods, all asymptotically bounce between the same two directions when minimizing quadratic functions, and it derives the exact convergence rates. It then introduces a new step size that converges to the reciprocal of the largest curvature, and a periodic method using it, which beats several recent gradient methods in numerical tests.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Repeated-eigenvalue case breaks the stated two-vector zigzag conclusion; Assumption (2.1) is load-bearing, not cosmetic.","rationale":"The reader's weakest assumption identifies exactly the point I find most load-bearing: the strict distinct-eigenvalue Assumption (2.1) is required for the proof that the limiting support is precisely the two eigenvectors ξ1 and ξn. My own reading of the proof in Section 2 confirms that strict distinctness enters in a substantive way, via the equality case of Lemma 2.1 and the contradiction argument in Theorem 2.4, and not merely as a notational convenience. With a repeated extreme eigenvalue, the convergence to a span of two eigenspaces may still hold, but the theorem as stated is not valid, and the abstract's unqualified statement is too broad. This does not change the reader's CONDITIONAL verdict: the distinct-eigenvalue limitation is a scope issue rather than an internal inconsistency of the main theorem under its stated assumptions, and the paper still needs the convergence guarantee of Algorithm 3.1 to be either proved or labeled empirical. I did not find evidence that the algebraic derivations are wrong within the stated assumption; the concern is about unqualified applicability, and the proposed numerical experiment would settle whether the limitation is real.","tokens_in":31653,"tokens_out":21544,"duration_ms":215758,"concrete_test":"Run the minimal gradient method (Ψ(A) = A) on the quadratic with A = diag(1, 1, κ), κ = 100, and initial gradient g0 = (1, 1, 1). Record q_k^(i) = (μ_k^(i))^2 / ||g_k||^2 for i = 1, 2, 3. Because the two unit eigenvalue components share the same factor (1 - α_k) at every step, q_k^(2)/q_k^(1) is constant; if q_k^(2) does not tend to 0, Theorem 2.4's two-vector conclusion fails under a repeated extreme eigenvalue. As a perturbation check, repeat with A = diag(1, 1 + 10^(-12), κ); q_k^(2) should decay only on a timescale governed by 10^(-12), confirming the discontinuity of the stated conclusion as the distinct-eigenvalue assumption is relaxed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central asymptotic result, Theorem 2.4 (with Corollary 2.5 and the rate formulas in Theorems 2.7 and 2.9), is proved only under Assumption (2.1), which requires 0 < λ1 < λ2 < ... < λn. This is not a harmless generic assumption: the proof of Lemma 2.1 uses the strict distinctness to conclude that the equality case of the Cauchy-Schwarz argument can involve at most two indices. If an extreme eigenvalue is repeated, several eigenvectors of the same eigenvalue evolve with identical factors (1 - α_k λ_i), so their ratios are invariant. Consequently, the normalized squared gradient components q_k need not concentrate on the two single vectors ξ1 and ξn as stated in (2.29)-(2.30). For example, with A = diag(1, 1, κ) and Ψ(A) = A (the minimal gradient method), the two eigenvectors with eigenvalue 1 maintain a constant ratio of squared components, so q_k^(2) cannot tend to 0 when g0^(2) ≠ 0. Thus the abstract's claim that 'each method in the family will asymptotically zigzag between two directions' is an overgeneralization: it holds only when the extreme eigenvalues are simple. Theorems 2.7, 2.9, and 3.1 inherit this restriction because they all rely on the limiting two-index set {1, n} identified in Theorem 2.4. The paper does not provide an eigenspace-grouped version that would cover repeated eigenvalues, so the applicability of the central theory to general quadratics is narrower than the abstract suggests.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies gradient methods for strongly convex quadratics whose stepsize is the weighted Rayleigh quotient α_k = g_k^T Ψ(A) g_k / (g_k^T Ψ(A) A g_k), covering steepest descent (Ψ = I) and minimal gradient (Ψ = A) as special cases. Under the assumption that the Hessian has n strictly distinct eigenvalues, the authors prove that the normalized squared gradient components asymptotically concentrate on the two extreme eigenvectors and alternate between them (Theorem 2.4), derive asymptotic rates for the objective value and gradient norm (Theorems 2.7 and 2.9), and give a bound on the underlying alternation constant (Theorem 2.13). In Section 3, a new stepsize α̃_k is derived from a finite-termination condition in two dimensions and is proved to converge to 1/λ_n along the iterates of any method in the family (Theorem 3.1). The paper then proposes a periodic gradient method that mixes BB steps, the family stepsize, and the new short stepsize, and reports numerical comparisons on random quadratics.","tokens_in":31956,"tokens_out":13216,"duration_ms":128008,"significance":"If the results hold as stated, the paper significantly generalizes the classical Akaike and Forsythe analysis of steepest descent to a broad parametric family and provides explicit asymptotic rate formulas that were previously unavailable for the minimal gradient method. The proofs are detailed and largely self-contained, with hypotheses stated precisely; the new stepsize α̃_k and its spectral limit 1/λ_n are potentially useful tools for breaking the zigzagging pattern. The numerical section is reproducible in design and shows consistent gains over the compared methods. The importance of the contribution is real, but the advertised scope is too broad because the central theorem requires strictly distinct eigenvalues and the proof of Theorem 3.1 glosses over an alternating-parity issue; both are fixable, but they are load-bearing.","major_comments":[{"comment":"The paper claims in Section 2 that one can assume 'without loss of generality' that 0 < λ1 < λ2 < ... < λn, but strict distinctness is not a harmless normalization. It is used essentially in Lemma 2.1 to conclude that the Cauchy-Schwarz equality case involves at most two indices with distinct eigenvalues, and in Theorem 2.4 to force the limiting set to be {1,n}. If an extreme eigenvalue is repeated, the conclusion (2.29)-(2.30) fails: for A = diag(1,1,κ) with Ψ(A) = A, the squared components of g_k along the two eigenvectors of eigenvalue 1 keep a constant ratio, so q_k^(2) cannot tend to 0 when g_0^(2) ≠ 0. The abstract's statement that 'each method in the family will asymptotically zigzag between two directions' therefore overstates the proven results. The assumption must either be stated explicitly in the abstract and main claims, or the theory must be extended to an eigenspace-grouped version covering repeated eigenvalues.","section":"Section 2, Assumption (2.1) and Theorem 2.4"},{"comment":"In the proof of Theorem 3.1, the displayed limits for H^k_11 and H^k_22 are asserted for all k, but H^k_11 uses g_{k-1} and therefore alternates between the limits (2.29) and (2.30) of Theorem 2.4. For example, when Ψ(A) = I and r = 0, H^k_11 takes the two values λ1(1+c^2κ)/(1+c^2) and λ1(c^2+κ)/(1+c^2) on the even and odd subsequences, which are different for c^2 ≠ 1. The displayed algebra appears to compute only one parity; the other parity follows by symmetry, and the final combined limit for α̃_k may still be correct, but the proof as written is incomplete because it does not justify the existence of the individual limits used in (3.16)-(3.18). This gap is load-bearing for the central claim (3.15) and needs a two-subsequence argument.","section":"Section 3.2, proof of Theorem 3.1"},{"comment":"The finite-termination derivation divides by Γ and concludes that α1 must satisfy the quadratic equation (3.8), but if Γ = 0 the condition (3.7) imposes no constraint on α1. The degenerate case Γ = 0 occurs when g1 is an eigenvector of A, in which case choosing α1 = 1/λ2 still leads to termination; hence the gap is fixable by a short case distinction. As written, however, the argument that (3.8) follows from (3.7) is not valid in all cases, and the derivation of the new stepsize (3.12) is not fully justified.","section":"Section 3.1, derivation around Eq. (3.7)-(3.8)"}],"minor_comments":[{"comment":"The abstract and the introduction state the zigzag result without the strict-distinct-eigenvalue condition; the condition should be moved from the proof section to the statements of the main results.","section":"Abstract and Theorem 2.4"},{"comment":"The symbol v appears in the displayed formula for lim(H^k_12)^2 ('Ψ^{2+2v}') without ever being defined; it should be r or another explicitly defined exponent.","section":"Section 3.2, proof of Theorem 3.1"},{"comment":"The sentence claiming that α̃_k is 'asymptotically be smaller than α_k^SD independent of r' is imprecise because Theorem 3.1 states a limit, not an inequality for finite k; rephrase to avoid suggesting a finite-k comparison.","section":"Section 3.2, after Eq. (3.14)"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid contribution to the asymptotic analysis of gradient methods, but the central theorem's scope is narrower than the abstract claims and the proof of Theorem 3.1 needs a parity handling. Both issues are local and fixable in a revision, so I recommend major revision rather than rejection. The repeated-eigenvalue concern is substantive: if the authors wish to retain the current generality claim, they need an eigenspace-grouped version or an explicit restriction in the abstract. The numerical study is extensive but mostly compares against methods from the same group; the editor may wish to check how much overlap exists with the authors' companion paper [21]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one. The paper gives a clean unified proof that a whole family of gradient stepsizes—steepest descent, minimal gradient, and everything in between—asymptotically zigzags in the two-dimensional span of the extreme eigenvectors, with explicit rates for objective values, gradient norms, and stepsizes. That genuinely generalizes Akaike, Forsythe, Nocedal et al., and the algebra in Theorems 2.4–2.13 checks out.\n\nThe second half is also worth something: the new stepsize (3.12) generalizes Yuan's steplength to the family, and the proof that it converges to 1/λ_n is direct and clean. The numerical section is thorough, and the proposed periodic method is competitive on their test set.\n\nSoft spots, in proportion:\n\n1. Assumption (2.1) — strictly distinct eigenvalues — is doing real work. The proof of Lemma 2.1 uses distinctness to force the two limiting indices to be {1,n}. If an extreme eigenvalue is repeated, e.g. A = diag(1,1,κ) for minimal gradient, the two eigenvectors with the same eigenvalue keep their component ratio forever, so the squared gradient components cannot concentrate on two unit vectors as claimed in Theorem 2.4. The abstract's statement that 'each method in the family will asymptotically zigzag between two directions' is therefore too strong; it needs the qualifier that the extreme eigenvalues are simple. A grouped-eigenvalue version would fix this and should be added.\n\n2. The finite-termination derivation in Section 3.1: equation (3.7) effectively requires Γ ≠ 0, but that case is not discussed. If Γ = 0 the argument collapses. I suspect Γ is nonzero generically, but it isn't stated.\n\n3. The R-linear convergence claim for Algorithm 3.1 is asserted by reference to [5]/[7], not proved for this algorithm. It's probably true, but the paper should either prove it or label it empirical.\n\n4. Algorithm parameters Kb, Km, Ks are tuned to the benchmark. That's normal in this literature, but the paper could be more transparent.\n\nCitation pattern is fine. No circularity: the limit results are derived from the stepsize definition and spectral assumptions, not assumed.\n\nBottom line: the core theory is sound under the stated assumption, and the paper is a real contribution to the gradient-method literature. The abstract overgeneralizes, and the repeated-eigenvalue case needs handling or explicit exclusion. Send it to peer review; a careful referee should ask for a revision rather than reject.","headline":"Solid unified analysis of zigzag for a family of gradient stepsizes; main theorems are sound under distinct eigenvalues, but the abstract oversells the result to repeated eigenvalues.","tokens_in":32561,"tokens_out":2813,"would_cite":true,"duration_ms":28270,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C20","90C25","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Gradient methods provably zigzag; new stepsize breaks cycle","keywords":["gradient methods","asymptotic convergence","zigzag phenomenon","spectral properties","steepest descent","minimal gradient","Barzilai-Borwein method","quadratic optimization"],"falsifier":"For a quadratic with distinct eigenvalues, e.g., $A = \\mathrm{diag}(1,3,10)$, run the minimal-gradient method from a starting point whose gradient has nonzero components on all three eigenvectors; measure $1/\\alpha_{2k}+1/\\alpha_{2k+1}$ over many iterations. If it does not converge to $\\lambda_1+\\lambda_n = 11$, the central theorem is wrong.","tokens_in":1925,"feed_emoji":"🌀","tokens_out":4421,"duration_ms":84003,"temperature":0.7,"pith_summary":"This paper proves that every gradient method whose stepsize is a weighted Rayleigh quotient, $\\alpha_k = g_k^T \\Psi(A) g_k / (g_k^T \\Psi(A) A g_k)$, eventually confines its search to the two-dimensional subspace spanned by the eigenvectors of the smallest and largest eigenvalues of the Hessian. This family includes steepest descent ($\\Psi(A)=I$) and the minimal gradient method ($\\Psi(A)=A$). The authors derive explicit limits for the objective-value ratios, gradient-norm ratios, and stepsizes on even and odd iterates, showing a two-step alternating cycle. They also construct a new stepsize, chosen to terminate exactly on two-dimensional quadratics, and prove that it converges to $1/\\lambda_n$, the reciprocal of the largest eigenvalue. A periodic method that alternates Barzilai-Borwein steps, the family stepsize, and the new stepsize is shown numerically to outperform several recent gradient methods.","feed_headline":"Gradient methods provably zigzag; new stepsize breaks cycle","feed_subtitle":"Proof that steepest descent and similar methods collapse to two eigen-directions, plus a stepsize that targets the largest eigenvalue.","key_machinery":"The argument is carried by a nonlinear transformation $T$ on the normalized squared-gradient vector $p$, defined by $(Tp)^{(i)} = (\\lambda_i - \\gamma(p))^2 p^{(i)} / \\sum_j(\\lambda_j - \\gamma(p))^2 p^{(j)}$, where $\\gamma(p) = \\sum_i \\Psi(\\lambda_i)\\lambda_i p^{(i)} / \\sum_i \\Psi(\\lambda_i)p^{(i)}$. A monotone quantity $\\Theta(p)$ increases under $T$, forcing the even and odd subsequences to converge to a two-point cycle supported on two eigenvalues; a ratio argument then forces those indices to be $1$ and $n$. The acceleration uses a new stepsize derived from a finite-termination condition on two-dimensional quadratics, expressed through a $2\\times2$ matrix $H^k$ built from the current and previous gradients.","core_discovery":"Under a strictly ordered spectrum $0<\\lambda_1<\\cdots<\\lambda_n$ and an initial gradient with nonzero components on both extreme eigenvectors, the normalized squared-gradient components converge on even and odd subsequences to two-point limits supported on the indices $1$ and $n$, with explicit formulas (2.29) and (2.30). Consequently, the stepsize $\\alpha_k$ converges to one of two limits, (2.33) and (2.34), and the sum identity $\\lim_{k\\to\\infty}(1/\\alpha_{2k}+1/\\alpha_{2k+1}) = \\lambda_1+\\lambda_n$ holds. The newly derived stepsize $\\tilde\\alpha_k$ in (3.12) converges to $1/\\lambda_n$ along the iterates of any method in the family, thereby eliminating the largest-eigenvalue component and breaking the zigzag pattern.","pith_inferences":["The strict distinct-eigenvalue assumption is likely not just technical: with repeated eigenvalues, the collapse to the two extreme eigenvectors may be replaced by a cycle supported on any pair of eigenvalues selected by the initial data, so the explicit rate formulas would need reformulation.","The spectral property of $\\tilde\\alpha_k$ suggests a practical heuristic for general smooth optimization: estimate the local largest eigenvalue of the Hessian periodically and take a short step to damp the corresponding gradient component, a strategy that may accelerate Newton-free and quasi-Newton frameworks.","The new stepsize formula (3.12) generalizes a known two-dimensional finite-termination construction; the same derivation could be adapted to terminate on three-dimensional subspaces, potentially yielding a family of stepsizes converging to reciprocals of selected interior eigenvalues.","The proof that $\\tilde\\alpha_k \\to 1/\\lambda_n$ relies only on the asymptotic two-point cycle, so the same acceleration should work for any method in the family, including variants with $\\Psi$ chosen to reduce the cost of computing the step."],"forward_implications":["Every method in the family (1.11) has the same worst-case two-step asymptotic rate $((\\kappa-1)/(\\kappa+1))^4$, independent of the choice of $\\Psi$.","The odd and even subsequences of objective values and gradient norms converge at the same two-step speed, while the consecutive-step ratios may converge at different speeds unless $\\Psi(\\lambda_n)=\\Psi(\\lambda_1)$ or a similar symmetry holds.","The new stepsize $\\tilde\\alpha_k$ converges to $1/\\lambda_n$, so periodically inserting it into the iteration removes the largest-eigenvalue component and provably breaks the zigzag pattern.","The proposed periodic gradient method (Algorithm 3.1) converges R-linearly on quadratics and, in the reported experiments, consistently outperforms the BB, DY, ABBmin2, and SDC methods on 630 random test instances.","The asymptotic formulas in Theorems 2.7 and 2.9 give testable predictions for the convergence ratios of any method in the family on generic quadratics with distinct eigenvalues."],"supporting_citations":[{"why":"Establishes the asymptotic alternation of steepest descent between two directions, which this paper generalizes.","marker":"[1]"},{"why":"Generalizes Akaike's result to the optimum s-gradient method, providing a template for the two-direction limit.","marker":"[18]"},{"why":"Provides the behavioral analysis of steepest descent on function values, stepsizes, and gradient norms that Theorems 2.7, 2.9, and Corollary 2.5 extend.","marker":"[26]"},{"why":"Introduces a family of P-gradient methods similar to (1.11), though without the asymptotic objective, gradient-norm, and stepsize analysis given here.","marker":"[27]"},{"why":"Derives the original two-dimensional finite-termination stepsize for steepest descent, generalized by the new stepsize.","marker":"[30]"},{"why":"Shows that a specific stepsize converges to the reciprocal of the largest eigenvalue during steepest descent, motivating the acceleration strategy.","marker":"[12]"},{"why":"Introduces the Barzilai-Borwein stepsizes that the periodic method incorporates.","marker":"[2]"},{"why":"Develops a prior gradient method exploiting spectral properties to accelerate the AOPT method, a direct predecessor of the acceleration technique.","marker":"[21]"}],"fun_headline_variants":["Gradient methods collapse to zigzag; new stepsize targets largest eigenvalue","Proof: gradient methods zigzag; stepsize that kills largest eigenvalue","New stepsize eliminates zigzag in gradient methods","Gradient methods zigzag provably; stepsize targets largest eigen","Zigzag proof for gradient methods; stepsize breaks cycle via largest eigenvalue"],"cache_read_input_tokens":34560,"weakest_assumption_plain":"The Hessian must have strictly distinct eigenvalues, ordered $0<\\lambda_1<\\cdots<\\lambda_n$; if two eigenvalues coincide, the proof that the iterates collapse onto the two extreme eigenvectors no longer goes through.","fun_headline_variants_meta":{"raw":{"variants":["Gradient methods collapse to zigzag; new stepsize targets largest eigenvalue","Proof: gradient methods zigzag; stepsize that kills largest eigenvalue","New stepsize eliminates zigzag in gradient methods","Gradient methods zigzag provably; stepsize targets largest eigen","Zigzag proof for gradient methods; stepsize breaks cycle via largest eigenvalue"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000603,"raw_usage":{"total_tokens":2782,"prompt_tokens":880,"completion_tokens":1902,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":496,"completion_tokens_details":{"reasoning_tokens":1812}},"tokens_in":496,"tokens_out":1902,"duration_ms":12721,"temperature":1.0,"reasoning_tokens":1812,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:26:34.328644+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a quadratic with distinct eigenvalues, e.g., $A = \\mathrm{diag}(1,3,10)$, run the minimal-gradient method from a starting point whose gradient has nonzero components on all three eigenvectors; measure $1/\\alpha_{2k}+1/\\alpha_{2k+1}$ over many iterations. If it does not converge to $\\lambda_1+\\lambda_n = 11$, the central theorem is wrong.","supporting_citations":[{"cited_title":"Akaike , On a successive transformation of probability distributio n and its application to the analysis of the optimum gradient method , Ann","cited_arxiv_id":null,"evidence_quote":"Establishes the asymptotic alternation of steepest descent between two directions, which this paper generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Generalizes Akaike's result to the optimum s-gradient method, providing a template for the two-direction limit."},{"cited_title":"Nocedal, A","cited_arxiv_id":null,"evidence_quote":"Provides the behavioral analysis of steepest descent on function values, stepsizes, and gradient norms that Theorems 2.7, 2.9, and Corollary 2.5 extend."},{"cited_title":"Pronzato, H","cited_arxiv_id":null,"evidence_quote":"Introduces a family of P-gradient methods similar to (1.11), though without the asymptotic objective, gradient-norm, and stepsize analysis given here."},{"cited_title":"Yuan , A new stepsize for the steepest descent method , J","cited_arxiv_id":null,"evidence_quote":"Derives the original two-dimensional finite-termination stepsize for steepest descent, generalized by the new stepsize."},{"cited_title":"De Asmundis, D","cited_arxiv_id":null,"evidence_quote":"Shows that a specific stepsize converges to the reciprocal of the largest eigenvalue during steepest descent, motivating the acceleration strategy."},{"cited_title":"Gradient methods exploiting spectral properties","cited_arxiv_id":"1905.03870","evidence_quote":"Develops a prior gradient method exploiting spectral properties to accelerate the AOPT method, a direct predecessor of the acceleration technique."}],"review_version":1}