{"id":"14134493-5f0d-4981-ab79-d50d915238e7","arxiv_id":"2412.13473","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"Under a new sum-of-distances cost function, gradient descent step sizes are claimed (C+ε,δ)-learnable with O~(H^3/ε^2) samples and a momentum-based two-parameter method with O~(H^4/ε^2) samples.","lead":"This paper proposes a new cost function for tuning step sizes in optimization algorithms and gives sample-size bounds for gradient descent and a two-parameter method it calls conjugate gradient. The relevance is a PAC-style guarantee for algorithm configuration, but the proof has internal inconsistencies and the analyzed method is not classic conjugate gradient.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4's 'conjugate gradient' recurrence z_{n+1}=z_n-ρ∇f(z_n)-η(z_n-z_{n-1}) with fixed ρ,η is the heavy-ball method, not CG; the paper's headline 'first learning complexity for CG' does not follow.","rationale":"The paper's central advertised contribution is the first learning-complexity bound for a CG algorithm set. Section 4, however, defines its 'CG' method as z_{n+1}=z_n-ρ∇f(z_n)-η(z_n-z_{n-1}) with fixed ρ and η across all iterations. This is the heavy-ball/momentum iteration, not the conjugate-gradient family (Hestenes-Stiefel, Fletcher-Reeves, Polak-Ribiere, Dai-Yuan) that the Introduction cites. In those methods, the conjugate parameter is a per-iteration scalar β_k computed from gradient inner products, and the step length is set by a line search; neither is present here. Because the object analyzed is a different algorithm class, Theorems 6-9 are not about 'conjugate gradient' and the headline claim fails independently of the additional sample-complexity and assumption issues that the reader identifies. A simple two-variable quadratic check of d_i^T A d_j = 0 for the paper's directions settles the matter. I therefore agree with the rejection, but for a more fundamental reason than the reader's weakest_assumption (Assumption 1.4/2.4), which is a real technical gap but could in principle be repaired; the CG misidentification cannot be repaired without rewriting the paper's core analysis. The verdict remains REJECT; no adjustment is needed.","tokens_in":22362,"tokens_out":9060,"duration_ms":73985,"concrete_test":"Run the Section 4 recurrence on the two-variable quadratic f(x)=0.5(x1^2+2 x2^2) (A=diag(1,2)) from z0=(1,1), with fixed ρ=1 and η=0.5, for 10 iterations; compute the search directions d_k = z_k - z_{k-1} and the A-inner products d_k^T A d_{k-1} for k=2,...,10. If any product is nonzero (it will be), the analyzed algorithm is not conjugate-gradient under the standard definition used in the paper's own references, proving the central CG claim is out of scope. Alternatively, compare the update to the Fletcher-Reeves formula β_k=||∇f(z_{k+1})||^2/||∇f(z_k)||^2 cited in Section 1 and observe that the recurrence does not implement it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 (Assumption 2 and the update in the first paragraph) analyzes iterations z1 = z0 - ρ∇f(z0), z_{n+1} = z_n - ρ∇f(z_n) - η(z_n - z_{n-1}) with constant parameters ρ,η. This recurrence is the two-step heavy-ball / momentum method with constant coefficients, not the Hestenes-Stiefel / Fletcher-Reeves / Dai-Yuan conjugate-gradient algorithms that the Introduction cites. In genuine nonlinear CG, the conjugate parameter β_k is recomputed at every iteration from inner products of gradients (e.g., β_k = ||g_{k+1}||^2/||g_k||^2) and the step length is chosen by line search; neither feature appears in the update analyzed. Consequently, Lemmas 3-8 and Theorems 6-9 establish uniform-convergence and sample-complexity guarantees for a fixed-parameter momentum class, not for any conjugate-gradient algorithm group. The central contribution claimed in the Abstract and Section 4 ('generalize our findings ... to the conjugate gradient algorithm group for the first time') is therefore not supported by the proofs. This is a definitional/correctness failure, not merely a naming preference: for a quadratic with Hessian A, the successive search directions d_k = z_{k+1}-z_k satisfy d_k = -ρ g_k + η d_{k-1}, which does not enforce A-conjugacy d_i^T A d_j = 0 for i≠j, the defining property of CG, except in degenerate cases.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies sample-complexity guarantees for tuning the parameters of gradient descent and of an algorithm it calls conjugate gradient, within the PAC algorithm-selection framework of Gupta and Roughgarden. It introduces a new cost function that sums, over iterations, the distance of each iterate to the optimum. The authors claim an improved GD bound, m = O~(H^3/eps^2), and the first learning-complexity bound for a CG family, m = O~(H^4/eps^2). The CG analysis is built on a two-step recurrence z_{n+1} = z_n - rho grad f(z_n) - eta (z_n - z_{n-1}) with constant rho and eta.","tokens_in":22725,"tokens_out":6504,"duration_ms":55409,"significance":"The new cost function is a reasonable performance measure and, if the bounds were correct, the GD part would be a useful incremental extension of Gupta-Roughgarden. However, the paper's central new claim regarding conjugate gradient is not about conjugate gradients: the recurrence analyzed in Section 4 is the heavy-ball / momentum method with constant coefficients, not a conjugate-gradient method with a recomputed beta_n and a line search. In addition, the stated sample bounds do not follow from the stated pseudo-dimension bounds, because the factor H in the pseudo-dimension is dropped when applying the uniform-convergence theorem. These two issues directly undermine the abstract and the two main theorems. The paper does provide a detailed, self-contained derivation of error-estimation lemmas for the heavy-ball family, but this does not compensate for the fact that the advertised contribution is not established.","major_comments":[{"comment":"The sample bound m = O~(H^3/eps^2) in Theorem 5 does not follow from the stated pseudo-dimension bound. In Section 3.2 the paper sets the pseudo-dimension of the discretized GD class to at most H log|N|, where H = log(nu/LZ)/log(1-beta), and log|N| ~ O(H). Theorem 1 with range [0,H] then gives m = O((H^2/eps^2)(H log|N| + ln(1/delta))) = O~(H^3 log|N|/eps^2) = O~(H^4/eps^2), not O~(H^3/eps^2). Appendix D ignores the factor H in the pseudo-dimension. The same issue occurs in Theorem 9: the pseudo-dimension is H log|N_rho| log|N_eta|, so the uniform-convergence theorem yields m = O~(H^2 * H * H * H / eps^2) = O~(H^5/eps^2), not O~(H^4/eps^2).","section":"Theorem 5 and Appendix D"},{"comment":"The recurrence analyzed in Section 4, z_1 = z_0 - rho grad f(z_0), z_{n+1} = z_n - rho grad f(z_n) - eta (z_n - z_{n-1}) with constant rho and eta, is the heavy-ball (momentum) method, not a conjugate gradient method. In CG, the search direction is d_n = -grad f(z_n) + beta_n d_{n-1} with beta_n recomputed from gradient inner products (e.g., Fletcher-Reeves), and the step length is chosen by a line search. Neither element appears in the paper's update. Consequently, Lemmas 3-8 and Theorems 6-9 establish results for a fixed-parameter two-step gradient family, not for any conjugate-gradient algorithm. The abstract and Section 4 claim a first learning-complexity result for the 'conjugate gradient algorithm group'; this claim is not supported by the proofs.","section":"Section 4, first paragraph"},{"comment":"Assumption 1.4, and its two-parameter analogue Assumption 2.4, require the iteration map to be a uniform contraction, ||z - rho grad f(z)|| <= (1-beta)||z|| for every rho in [rho_l, rho_u] (and, for Assumption 2.4, for every rho, eta in the respective intervals). Appendix B demonstrates only that a single step size, rho = 2/(m+L), satisfies the condition for a strongly convex objective; it does not justify the interval-wide condition used in Theorems 4-9. Since the net construction and the iteration-error estimates depend on the contraction holding for all parameters in the intervals, the stated learning guarantees apply only to a limited, unspecified subclass of problems and parameter ranges. The paper should either restrict the algorithm class to parameters satisfying the contraction condition as an explicit definitional assumption for the whole scope of the theorems, or provide a proof that the condition holds on the full intervals.","section":"Assumptions 1.4 and 2.4; Appendix B"}],"minor_comments":[{"comment":"The abstract and contribution 3 state 'prove the existence a learning algorithm'; it should be 'prove the existence of a learning algorithm'.","section":"Abstract"},{"comment":"The new cost function is defined as c(A_rho,x) = sum_{j=1}^M ||z* - g_j(z0,rho)||, but in Section 4 the analogous sum is written as sum_{i=0}^M. Please use a consistent indexing convention.","section":"Section 3.2"},{"comment":"The expression for K in the statement of Theorem 4 uses D(rho_u) while the condition preceding it uses D(rho); clarify the relationship between the condition on eta - rho and the net spacing K, and state which D entry appears in each place.","section":"Theorem 4"},{"comment":"In the display of the recurrence for A_n, the text writes 'A_n = [D(rho)+eta] A_{n-1} + A_{n-2}', but the characteristic equation and the surrounding equations use eta A_{n-2}. This appears to be a typo.","section":"Appendix F, Corollary 2 proof"},{"comment":"In the proof of Lemma 4 there is a stray bracket in '||grad f(z'_j)]||'; the closing bracket after the norm is a typo.","section":"Appendix G"},{"comment":"Lemma 7 and Lemma 8 define R* and R*' with absolute values, but the preceding derivations of the coefficients c1 and c2 already rely on signs; please make the sign conventions explicit and verify the inequalities are strict when r1=1 (if that case can occur under Assumption 2).","section":"Appendix K and L"}],"recommendation":"reject","confidential_remarks":"The paper has a clear presentation of the learning-complexity framework, but the load-bearing errors are not patchable within the scope of the manuscript: the CG section analyzes an algorithm that is not conjugate gradient, and the sample-complexity claims drop factors of H. The second issue could be corrected by restating the bounds as O~(H^4) and O~(H^5), but the first issue requires replacing the analyzed family or rewriting the contribution. Given that the main advertised contribution is the CG result, I recommend rejection. The GD section alone, if corrected, might be a modest incremental work, but the paper as submitted does not support its abstract."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper before reading it closely. First, the claimed sample-complexity bounds do not follow from the paper's own pseudo-dimension statements: Theorem 5's O~(H^3/eps^2) contradicts the pseudo-dimension bound H log N ~ H^2, which would give O~(H^4/eps^2) via uniform convergence; Theorem 9 has the analogous problem, with H log N_rho log N_eta ~ H^3 giving O~(H^5/eps^2). Second, the 'conjugate gradient' method analyzed in Section 4 is the constant-coefficient heavy-ball/momentum recurrence z_{n+1} = z_n - rho grad f(z_n) - eta(z_n - z_{n-1}). There is no conjugacy condition, no recomputed beta_k, no line search. Calling that a first learning-complexity result for CG is not a naming quibble; the analyzed class is not the class the introduction and abstract advertise.\n\nGive credit where it is due: the sum-of-distances cost function is a legitimate change to the Gupta-Roughgarden framework, and the paper is the first to push this learning-theoretic treatment to a two-parameter update family. The proofs are elaborate and mostly self-contained, and the authors are explicit about their assumptions. The idea of using a primal-dual-integral-style cost is worth keeping.\n\nThe soft spots are load-bearing, not cosmetic. Besides the pseudo-dimension mismatch and the CG mislabeling, Assumption 1.4/2.4 asks for a uniform contraction with the same beta across the entire step-size interval, but Appendix B only demonstrates a single step size for strongly convex functions. That does not justify the interval-wide condition used in Theorems 5 and 9. If that assumption fails, the net arguments and the H terms collapse.\n\nWho is this paper for? A reader working on data-driven algorithm design might skim it for the cost-function idea, but the main theorems should not be cited as established. The paper deserves a serious referee — it is substantive enough to warrant careful review — but the current version should be rejected. The authors need to fix the sample bounds, rescope Section 4 to constant-parameter momentum, and either prove the interval-wide contraction from reasonable conditions or replace it with something that is actually available. My recommendation is: send it to review, and let the referees say what I just said, because the errors are identifiable and the cost-function idea has some value.","headline":"Real idea (new cost function), but the sample bounds are internally inconsistent and the 'CG' section analyzes heavy-ball, not conjugate gradients.","tokens_in":23227,"tokens_out":2236,"would_cite":false,"duration_ms":23841,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","90C25","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Gradient descent and conjugate gradient step sizes can be learned from finite samples with arbitrarily small error under a new sum-of-distances cost.","keywords":["algorithm selection","learning complexity","pseudo-dimension","gradient descent","conjugate gradient","sample complexity","step size tuning","data-driven algorithm design"],"falsifier":"Run the discretization test on a convex $L$-smooth function whose contraction ratio is not uniformly bounded below $1$ over $[\\rho_l,\\rho_u]$ — for example, a strongly convex quadratic with step sizes approaching the upper stability limit $2/L$, where the ratio $\\|z-\\rho\\nabla f(z)\\|/\\|z\\|$ tends to $1$ along the largest-curvature eigenvector. If such a family admits no $\\beta\\in(0,1)$ satisfying Assumption 1.4, then the theorem's premise is violated; measuring $|c(A_\\rho,x)-c(A_\\eta,x)|$ for two step sizes at the proposed net spacing on that family shows whether the claimed $C$-error bound still holds or fails.","tokens_in":22132,"feed_emoji":"🎯","tokens_out":10713,"duration_ms":94540,"temperature":0.7,"pith_summary":"Algorithm selection — choosing the step size for gradient descent, or the step size and conjugate parameter for conjugate gradient — is treated as a statistical learning problem with an unknown distribution over optimization instances. This paper introduces a new cost function that sums, at every iteration, the distance from the current iterate to the optimum, a continuous analogue of the primal-dual integral used in integer programming. Using this cost, the authors prove that the optimal gradient-descent step size can be $(C+\\varepsilon,\\delta)$-learned from $m=\\widetilde{O}(H^3/\\varepsilon^2)$ samples for any $C>0$, and that the optimal conjugate-gradient parameters can be $(C+\\varepsilon,\\delta)$-learned from $m=\\widetilde{O}(H^4/\\varepsilon^2)$ samples. These are the first sample-complexity guarantees of this kind for conjugate gradient methods, and they improve the learning-error constant of the earlier iteration-count cost from $1$ to an arbitrarily small $C$.","feed_headline":"Sample bounds prove step-size tuning for GD and CG","feed_subtitle":"Sum-of-distances cost makes algorithm selection learnable: cubic-in-H samples for GD, quartic-in-H for CG.","key_machinery":"The driving object is the sum-of-distances cost function $c(A_\\rho,x)=\\sum_{j=1}^{M}\\|z^*-g^j(z_0,\\rho)\\|$, which is bounded by $H\\|z_0\\|$ and Lipschitz-continuous in the step size under Assumption 1.4. Around this cost, the paper builds a $K$-net of step sizes: if the step-size gap is at most $K$, the cost difference is at most $C$, and the net's size is polynomial in $1/K$. The pseudo-dimension of the finite net is bounded by $\\widetilde{O}(H)$, and an empirical-risk-minimization algorithm on the net inherits the uniform-convergence sample bound. For conjugate gradient, the same structure runs through the second-order homogeneous linear recurrence $x_n=[D(\\rho)+\\eta]x_{n-1}+\\eta x_{n-2}$; its root formula delivers the Lipschitz constants $G^*$ and $H^*$ that control the cost error and hence the net size.","core_discovery":"The central claim is that a cost function defined by $c(A_\\rho,x)=\\sum_{j=1}^{M}\\|z^*-g^j(z_0,\\rho)\\|$ makes the family of gradient descent algorithms learnable with error $C+\\varepsilon$ using $\\widetilde{O}(H^3/\\varepsilon^2)$ samples, and that the analogous two-parameter family of conjugate gradient algorithms is learnable with $\\widetilde{O}(H^4/\\varepsilon^2)$ samples. The authors show that nearby step sizes produce nearby costs: the cost difference between two algorithms is controlled by the parameter gap times a constant that depends on the contraction factor $\\beta$, the smoothness $L$, the horizon $H$, and the bounded initial distance $Z$. Discretizing the parameter interval into a net fine enough to keep this cost difference below $C$ reduces the infinite family to a finite one, whose pseudo-dimension is $\\widetilde{O}(H)$; uniform convergence then yields the sample bounds. For conjugate gradient, the iteration error is propagated through a second-order linear recurrence, giving explicit bounds $G^*$ and $H^*$ that make the same net argument work.","pith_inferences":["Beyond the paper's stated claims, the same net argument would likely extend to stochastic-gradient variants if Assumption 1.4 were relaxed to an on-average contraction; testing this is a natural next step.","The new cost function is a smooth aggregate over the trajectory, so it could be used as a meta-learning objective for step-size prediction, where the iteration count is discontinuous.","The sample bounds are existence results: the paper does not give an efficient way to search the parameter net, so an open question is whether the optimum can be found in time polynomial in $H$ and $1/\\varepsilon$."],"forward_implications":["With $\\widetilde{O}(H^3/\\varepsilon^2)$ samples, a data-driven learner can select a gradient descent step size whose expected sum-of-distances cost is within $C+\\varepsilon$ of the best step size in the family, for any tolerance $C>0$.","For conjugate gradient, $\\widetilde{O}(H^4/\\varepsilon^2)$ samples suffice to tune both the step size and the conjugate parameter, giving the first learning-complexity guarantee for conjugate gradient in this setting.","Because the new cost can be evaluated from early-terminated runs, the sample guarantees hold even when optimization is stopped before convergence, unlike cost functions based on iteration counts.","The learning error is no longer floored at $1$ by the integrality of iteration counts; the cost difference between two algorithms can be made arbitrarily small by choosing step sizes close enough."],"supporting_citations":[{"why":"Supplies the PAC algorithm-selection setting, the iteration-count cost baseline, and the H-net argument this paper refines.","marker":"Gupta and Roughgarden (2016)"},{"why":"Provides the uniform-convergence theorem used to convert pseudo-dimension bounds into sample-complexity guarantees.","marker":"Anthony and Bartlett (1999)"},{"why":"Defines pseudo-dimension, the complexity measure used for the algorithm classes.","marker":"Pollard (1984)"},{"why":"Introduces the primal-dual integral whose structure motivates the paper's new sum-of-distances cost function.","marker":"Berthold (2013)"},{"why":"Supplies the general solution for second-order linear recurrences used to propagate conjugate-gradient iteration errors.","marker":"Epp (2010)"},{"why":"Defines the conjugate-gradient iteration whose parameters are being learned in the paper's CG family.","marker":"Hestenes and Stiefel (1952)"},{"why":"Gives the $(\\varepsilon,\\delta)$-learning definition that frames the sample-complexity guarantees.","marker":"Kearns and Vazirani (1994)"}],"fun_headline_variants":["Sample bounds prove GD and CG tuning is learnable","Cubic and quartic sample bounds for picking the best optimizer","Algorithm selection becomes learnable via pseudo-dimension","Finite sample complexity for step-size tuning in GD and CG","Pseudo-dimension analysis yields sample bounds for GD and CG"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 1.4, and its CG analogue Assumption 2.4: there is a single $\\beta\\in(0,1)$ such that every step size in the allowed interval shrinks the distance to the optimum by a factor at most $1-\\beta$, uniformly for all iterates; without this interval-wide contraction, the cost bounds, the net discretization, and the sample-complexity theorems do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Sample bounds prove GD and CG tuning is learnable","Cubic and quartic sample bounds for picking the best optimizer","Algorithm selection becomes learnable via pseudo-dimension","Finite sample complexity for step-size tuning in GD and CG","Pseudo-dimension analysis yields sample bounds for GD and CG"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000738,"raw_usage":{"total_tokens":3308,"prompt_tokens":966,"completion_tokens":2342,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":2275}},"tokens_in":582,"tokens_out":2342,"duration_ms":16256,"temperature":1.0,"reasoning_tokens":2275,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:06:36.317392+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the discretization test on a convex $L$-smooth function whose contraction ratio is not uniformly bounded below $1$ over $[\\rho_l,\\rho_u]$ — for example, a strongly convex quadratic with step sizes approaching the upper stability limit $2/L$, where the ratio $\\|z-\\rho\\nabla f(z)\\|/\\|z\\|$ tends to $1$ along the largest-curvature eigenvector. If such a family admits no $\\beta\\in(0,1)$ satisfying Assumption 1.4, then the theorem's premise is violated; measuring $|c(A_\\rho,x)-c(A_\\eta,x)|$ for two step sizes at the proposed net spacing on that family shows whether the claimed $C$-error bound still holds or fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the PAC algorithm-selection setting, the iteration-count cost baseline, and the H-net argument this paper refines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the uniform-convergence theorem used to convert pseudo-dimension bounds into sample-complexity guarantees."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines pseudo-dimension, the complexity measure used for the algorithm classes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the general solution for second-order linear recurrences used to propagate conjugate-gradient iteration errors."},{"cited_title":"R.; and Stiefel, E","cited_arxiv_id":null,"evidence_quote":"Defines the conjugate-gradient iteration whose parameters are being learned in the paper's CG family."},{"cited_title":"J.; and Vazirani, U","cited_arxiv_id":null,"evidence_quote":"Gives the $(\\varepsilon,\\delta)$-learning definition that frames the sample-complexity guarantees."}],"review_version":1}