{"id":"69a67a7d-9634-4fed-985e-f808ddaa0b07","arxiv_id":"2507.09823","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Accelerated GRAAL is the first adaptive first-order method that proves near-optimal accelerated complexity for convex L-smooth and (L0,L1)-smooth functions with geometric stepsize growth.","lead":"This paper introduces Accelerated GRAAL, an adaptive first-order method for convex optimization that combines Nesterov acceleration with a stepsize that grows geometrically as local curvature estimates improve. It proves near-optimal iteration complexity for smooth and generalized-smooth functions without line search or hyperparameter tuning.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised no-tuning property rests on an uncheckable initial-stepsize condition: Corollaries 2 and 3 require eta0 L <= 1 or eta0 L0 exp(L1 ||x0-x*||) <= 1, and no fixed default can certify this for all instances.","rationale":"I read the paper in good faith as making a substantive algorithmic contribution: an accelerated adaptive method whose stepsize can grow geometrically, with near-optimal complexity for L-smooth and (L0, L1)-smooth convex minimization. The proofs are extensive and largely coherent, and the geometric-growth mechanism is a real step beyond the sublinearly growing stepsizes of AC-FGM and AdaNAG. The soft spot I keep coming back to is the advertised 'no hyperparameter tuning' property, because the theorems are conditional on an inequality involving exactly the constants that a parameter-free method is supposed not to need. Choosing eta0 = 1e-10 is a reasonable heuristic, and the paper is honest that this adds a logarithmic factor, but the guarantee is not uniform over the problem class: for every fixed eta0 there exist problems whose L0 exp(L1 ||x0 - x*||) exceeds 1/eta0, and the proofs say nothing about those problems. The reader's weakest-assumption analysis identified the same condition, and I agree with that reading. The additional issue flagged by the reader in Corollary 3 is real but more localized: the bound on ||grad f(x0)|| follows from eq. (30) by Gronwall's inequality, not directly from eq. (31) as cited, and the fix is straightforward. I do not see reason to reject the paper or even to change the conditional verdict: the core construction is novel and the proof gaps appear repairable, but the scope of the no-tuning claim should be stated more carefully, and the initial-stepsize condition should be made explicit as a limitation rather than an automatic consequence of picking a very small constant.","tokens_in":28872,"tokens_out":20775,"duration_ms":229972,"concrete_test":"Re-derive Theorem 2 and Corollary 2 without assuming eta0 L <= 1, explicitly tracking the first-step overshoot and the recovery phase. If the resulting complexity degrades to poly(eta0 L) * sqrt(L D^2 / eps), or if the Case 2b step of the proof fails when eta1 < eta0, then the suggested default eta0 = 1e-10 cannot certify the claimed no-tuning guarantee for arbitrarily large L; if it yields sqrt(L D^2 / eps) + O(log(eta0 L)), the concern reduces to a harmless additive log. Separately, run Algorithm 1 on f(x) = L x^2 / 2 with L = 10^12 and eta0 = 1e-10 to check whether empirical iterations stay within the claimed form.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Algorithm 1 needs no line search and no hyperparameter tuning, but both convergence corollaries are stated under conditions that involve the unknown problem constants: Corollary 2 assumes eta0 L <= 1, and Corollary 3 assumes eta0 L0 exp(L1 ||x0 - x*||) <= 1. The paper suggests choosing eta0 = 1e-10 as a universal default, but for any fixed eta0 there are admissible instances with L0 exp(L1 ||x0 - x*||) > 1/eta0, so the theorem simply does not apply to them. Nothing in the algorithm verifies the condition from observable quantities; if the condition is violated, the first gradient step can overshoot by an arbitrarily large factor, and the proof gives no control on the recovery. Corollary 2's displayed logarithmic term also becomes negative in the violated regime, so the stated bound is not meaningful there. This is not an internal inconsistency, but it is the load-bearing point where the advertised 'no hyperparameter tuning' claim goes beyond what the proofs establish: the user must know an a priori upper bound on L, or on L0 exp(L1D), to certify the assumptions. A secondary, fixable proof gap exists in Corollary 3, where the bound on ||grad f(x0)|| is attributed to eq. (31) but needs the Gronwall argument from eq. (30); this does not change the main concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an accelerated version of GRAAL (Algorithm 1) that combines a local-curvature-based adaptive stepsize rule with Nesterov momentum via an additional coupling step. It establishes a Lyapunov descent inequality (Theorem 1) that holds for any convex differentiable function. For L-smooth objectives, it proves a lower bound on the cumulative stepsize (Theorem 2) that with eta0 L <= 1 yields iteration complexity O(sqrt(L ||x0-x*||^2/epsilon) + log(1/(eta0 L))) (Corollary 2). For (L0,L1)-smooth objectives, it proves a similar lower bound (Theorem 3), giving complexity O(sqrt(L0 D^2/epsilon) + (L1 D)^3 + (1+L1^2 D^2) log(1/(eta0 L0))) under eta0 L0 exp(L1 ||x0-x*||) <= 1 (Corollary 3). The paper argues this is the first adaptive accelerated method with geometric stepsize growth and near-optimal guarantee under generalized smoothness.","tokens_in":82,"tokens_out":6239,"duration_ms":88924,"significance":"The conceptual contribution is substantial: it resolves the open question of combining Nesterov acceleration with the GRAAL-type stepsize update without line search or a predefined stepsize sequence. The proof of the Lyapunov descent (Theorem 1) is carried out in detail, and the cumulative-stepsize lower bounds (Theorems 2 and 3) are nontrivial and mostly self-contained. The paper is explicit about the price of adaptation (logarithmic/additive terms), and the comparison with AC-FGM and AdaNAG is informative. The method is constructive and accompanied by a full proof apparatus, including machine-checkable-style lemmas and explicit statements of all constant conditions. However, the advertised 'no hyperparameter tuning' property is undermined by the initial-stepsize conditions in Corollaries 2 and 3, whose verification requires knowledge of problem-dependent constants. The result remains conditional and the claim should be revised accordingly.","major_comments":[{"comment":"The paper claims that choosing eta0 = 10^{-10} 'will only result in a small logarithmic additive factor' and that no hyperparameter tuning is needed. However, the theorem's hypothesis eta0 L <= 1 cannot be verified from observable quantities, and for every fixed eta0 > 0 there exist admissible instances with eta0 L > 1. In that regime the logarithmic term ln(1/(eta0 L)) in eq. (26) is negative and the displayed O(·) bound is vacuous, while the proof gives no fallback control (the first gradient step may overshoot by a factor eta0 L). The same issue appears in Corollary 3 with the condition eta0 L0 exp(L1 ||x0-x*||) <= 1. The theorem statements themselves are sound, but the central no-tuning claim goes beyond what is proven. Please either (a) restate the results as requiring a user-supplied upper bound on L, or on L0 exp(L1 ||x0-x*||), or (b) add a verification/certification mechanism (e.g., a doubling procedure for eta0) that makes the condition checkable without knowing the constants.","section":"§3.1, Corollary 2 and the paragraph after it; §4.1, Corollary 3"},{"comment":"In the chain of inequalities for D, step (c) is justified by 'uses eq. (31)'. Equation (31) alone gives ||grad f(x0)|| <= (L0 + L1 ||grad f(x0)||)(exp(L1 ||x0-x*||)-1)/L1, which cannot be rearranged to ||grad f(x0)|| <= (L0/L1)(exp(L1 ||x0-x*||)-1) without a Gronwall-type argument (or the equivalent lemma of Vankov et al., 2024). The paper cites the equivalence of eqs. (30) and (31) to Vankov et al., Lemma 2.5, but the proof here does not invoke the full lemma. Since the claim D = O(||x0-x*||) drives the additive-term order in Corollary 3, this step should be made explicit or replaced by a direct citation.","section":"§C.6, proof of Corollary 3 (derivation of D = O(||x0-x*||))"}],"minor_comments":[{"comment":"The variable x_{k+1} is assigned twice; line 6 sets it to the gradient step, then line 7 overwrites it. This notational collision is confusing; please use a temporary variable (e.g., gstep) for the gradient step to avoid ambiguity.","section":"§2.1, Algorithm 1, lines 6-7"},{"comment":"It would be helpful to provide one explicit admissible triple (theta, gamma, nu) instead of leaving existence to the reader. The paper says 'easy to verify', but a concrete value would make the method directly reproducible.","section":"§2.2, eq. (19)"},{"comment":"The abstract and contributions advertise `without hyperparameter tuning'; since eta0 is still a user-chosen parameter and the theorems require a condition on it, consider replacing `no hyperparameter tuning' by, for example, `no line search and no tuning of L-dependent parameters' to match the theorems.","section":"Abstract and §1.3"}],"recommendation":"major_revision","confidential_remarks":"The paper appears to be a technically serious contribution; the main proofs are detailed and mostly coherent. My primary concern is the mismatch between the advertised no-tuning property and the unverifiable initial-stepsize conditions in Corollaries 2 and 3. This is fixable in a revision by rephrasing the claims or adding a certification mechanism. The secondary gap in the proof of D = O(||x0-x*||) is also easily repaired. I would not reject over these issues, but they must be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the coupling step in Algorithm 1 is a real innovation and the paper is worth a serious referee. It gives the first accelerated adaptive method I know of that provably recovers the optimal sqrt(L/epsilon) rate under (L0,L1)-smoothness, with geometric stepsize growth rather than the sublinear growth that limited AC-FGM and AdaNAG. The Lyapunov proof is careful and mostly complete, and the comparison to prior adaptive methods is fair.\n\nThe soft spot is the initial-stepsize condition. Corollary 2 needs eta0 L <= 1, Corollary 3 needs eta0 L0 exp(L1||x0-x*||) <= 1. Neither condition is checkable from observable information, and no fixed default like eta0=1e-10 can certify it for all instances. If the condition fails, the stated bound is not meaningful and the proof gives no recovery guarantee. So the 'no line search, no hyperparameter tuning' claim is stronger than what the theorems establish. This is not a flaw in the coupling idea; it is a flaw in the presentation and should be fixed by stating the assumption explicitly, or by a two-phase argument that handles the first iterations separately.\n\nOne smaller proof point: the stress-test note flagged a gap in Corollary 3 about bounding ||grad f(x0)||. I do not think that gap is real. Equation (31) with x=x*, z=x0 gives exactly the bound used, since grad f(x*)=0; no Gronwall is needed. The undefined H_{-2} and non-explicit constants are minor readability issues.\n\nWho is this for? People working on adaptive first-order methods and generalized smoothness. The paper deserves peer review, with the expectation that the authors clarify the initial-stepsize assumption. I do not think the main result will break; this is a good paper with an overstated headline.","headline":"A genuinely new adaptive acceleration mechanism with a load-bearing but fixable overclaim about no tuning.","tokens_in":29749,"tokens_out":4623,"would_cite":true,"duration_ms":50492,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Accelerated GRAAL achieves near-optimal accelerated iteration complexity for convex L-smooth and (L0,L1)-smooth functions without line search or hyperparameter tuning, by letting the stepsize grow geometrically with local curvature…","keywords":["adaptive gradient method","Nesterov acceleration","convex optimization","local curvature estimation","GRAAL","(L0,L1)-smoothness","iteration complexity","adaptive stepsize"],"falsifier":"Run Algorithm 1 on the one-dimensional quadratic $f(x) = x^2/2$, with $x_0 = 10$, $x^* = 0$, initial stepsizes $\\eta_0 = 10^{-4}$ and $\\eta_0 = 10^{-10}$, and a sequence of accuracies $\\epsilon = 10^{-4}, 10^{-6}, 10^{-8}$, using any fixed constants satisfying eq. (19). If the number of iterations grows roughly like $1/\\epsilon$ instead of $\\sqrt{1/\\epsilon}$ up to a logarithmic term, or if the stepsize $\\eta_k$ fails to grow geometrically toward a value of order 1, then the central complexity and geometric-growth claims for $L$-smooth functions are wrong.","tokens_in":28674,"feed_emoji":"⚡","tokens_out":22836,"duration_ms":196609,"temperature":0.7,"pith_summary":"The paper tries to settle a question left open by prior adaptive methods: can a gradient method that chooses its stepsize from local curvature estimates, with no line search and no tuned parameters, also be accelerated to the optimal rate of accelerated gradient descent? It proposes Accelerated GRAAL, whose stepsize rule permits geometric growth, unlike earlier accelerated adaptive methods whose stepsize growth is restricted to a sublinear rate. The paper proves that for convex $L$-smooth functions with $\\eta_0 L \\leq 1$, the method reaches accuracy $\\epsilon$ in $O(1 + \\sqrt{L\\|x_0-x^*\\|^2/\\epsilon} + \\ln(1/(\\eta_0 L)))$ iterations, which is the optimal accelerated complexity up to an additive logarithmic factor. For $(L_0,L_1)$-smooth convex functions with $\\eta_0 L_0 \\exp(L_1\\|x_0-x^*\\|) \\leq 1$, it obtains the first near-optimal adaptive guarantee, with the same square-root dependence on the precision plus additive constant terms. A sympathetic reader would care because this is the first demonstration that full adaptivity to local curvature and accelerated momentum can coexist, which is what practitioners would need to run accelerated methods without knowing the smoothness constants.","feed_headline":"Accelerated gradient method hits optimal rate with no tuning","feed_subtitle":"Step sizes adapt to local curvature at a geometric rate, matching accelerated gradient complexity up to a log factor.","key_machinery":"The load-bearing object is the adaptive momentum-coupling step: at iteration $k$ the algorithm forms $\\tilde{x}_k = \\alpha_k \\hat{x}_k + (1-\\alpha_k)x_k$, takes the gradient step $x_{k+1} = x_k - \\eta_k \\nabla f(\\tilde{x}_k)$, then forms $x_{k+1} = \\beta_k \\tilde{x}_k + (1-\\beta_k)x_k$ with $\\beta_k = \\eta_k/(\\alpha_k H_k)$, where $H_k$ is the cumulative sum of stepsizes. Choosing $\\alpha_k = (1+\\gamma)\\eta_{k-1}/(H_{k-1} + (1+\\gamma)\\eta_{k-1})$ keeps $\\beta_k \\leq 1$ and satisfies $\\eta_k/(\\alpha_k\\beta_k) = H_k$. This avoids the constraint $\\eta_k/\\alpha_k \\leq \\eta_{k-1}/\\alpha_{k-1} + \\eta_k$ that forced prior methods (AC-FGM, AdaNAG) to predefine the momentum parameter and restrict stepsize growth. The curvature estimator $\\lambda_{k+1} = \\min\\{\\Lambda(x_{k+1}; \\tilde{x}_k), \\Lambda(x_{k+1}; \\tilde{x}_{k+1})\\}$ supplies the local Lipschitz information, and the Lyapunov function $\\Psi_k(x) = \\frac{1}{2}\\|x_k - x\\|^2 + H_{k-1}(f(x_k) - f(x)) + (\\theta\\eta_k\\eta_{k-1}/\\lambda_k)D_f(x_{k-1}; \\tilde{x}_{k-1}) + \\frac{\\gamma\\theta}{2}\\|x_k - x_{k-1}\\|^2$ telescopes across iterations, turning descent into a lower bound on $H_k$ that becomes the iteration complexity.","core_discovery":"Algorithm 1, called Accelerated GRAAL, combines accelerated momentum with the GRAAL idea of estimating the local inverse gradient Lipschitz constant. The curvature estimator is $\\Lambda(x; z) = 2D_f(x; z)/\\|\\nabla f(x) - \\nabla f(z)\\|^2$, and the stepsize update $\\eta_{k+1} = \\min\\{(1+\\gamma)\\eta_k, \\nu H_{k-1}\\lambda_{k+1}/\\eta_{k-1}\\}$ allows the stepsize to grow at a geometric rate. The central mechanism is an additional coupling step $x_{k+1} = \\beta_k \\tilde{x}_k + (1 - \\beta_k)x_k$ with $\\beta_k = \\eta_k/(\\alpha_k H_k)$, which decouples the momentum parameter from future curvature estimates and lets $\\alpha_k$ itself adapt to the stepsize history. The proofs establish a Lyapunov function $\\Psi_k$ and show that the cumulative stepsize $H_k$ grows at least as $c(k - m)/\\sqrt{L}$ for $L$-smooth functions, and at least as $c(k - |T_2(k)| - |T_4(k)| - 1)/\\sqrt{L_0}$ for $(L_0,L_1)$-smooth functions. These lower bounds, combined with the Lyapunov inequality, yield the near-optimal iteration complexities in Corollaries 2 and 3.","pith_inferences":["The practical recipe 'take $\\eta_0 = 10^{-10}$' is not certified by the theorems: Corollaries 2 and 3 condition on $\\eta_0$ being small relative to $L$, $L_0$, $L_1$, and $\\|x_0 - x^*\\|$, and the paper gives no way to check that condition from data alone.","The additive $(L_1 D)^3$ term in Corollary 3 is worse than the $(L_1 D)^{5/3}$ term of the non-adaptive near-optimal baseline, suggesting that the adaptive framework may still have room to tighten its additive dependence.","The same coupling-step construction might extend to stochastic gradients, composite objectives, or non-convex generalized-smooth problems, since it decouples the momentum schedule from future curvature information; these extensions are natural next steps that the paper does not take.","A computational check on ill-conditioned quadratics and on neural-network losses with $(L_0,L_1)$-smoothness could test whether geometric stepsize growth actually occurs in practice and whether the logarithmic penalty for a tiny initial stepsize is benign."],"forward_implications":["For convex $L$-smooth functions, choosing any initial stepsize $\\eta_0$ with $\\eta_0 L \\leq 1$ gives the optimal accelerated complexity up to a logarithmic additive term: $K = O(1 + \\sqrt{L\\|x_0 - x^*\\|^2/\\epsilon} + \\ln(1/(\\eta_0 L)))$ .","For $(L_0,L_1)$-smooth convex functions, the same algorithm is the first adaptive method with near-optimal complexity, reaching $K = O(1 + \\sqrt{L_0 D^2/\\epsilon} + L_1^3 D^3 + (1 + L_1^2 D^2)\\ln(1/(\\eta_0 L_0)))$ where $D = O(\\|x_0 - x^*\\|)$ .","The only user input is the initial stepsize; the constants $\\theta$, $\\gamma$, $\\nu$ are universal and fixed by eq. (19), so the method needs no line search and no hyperparameter tuning.","Because the stepsize can grow geometrically rather than at the sublinear rate $(1 + 1/k)$, a deliberately small initial stepsize costs only a logarithmic additive factor, whereas the paper shows AC-FGM and AdaNAG pay factors of $1/\\sqrt{\\eta_0 L}$ or $\\eta_0 L$.","Under $(L_0,L_1)$-smoothness the geometric stepsize growth is the feature that avoids exponential factors from drifting local Lipschitz constants; the paper conjectures that the restricted-growth methods cannot reach near-optimal complexity in this class."],"supporting_citations":[{"why":"supplies the GRAAL algorithm and the local-curvature stepsize idea that Algorithm 1 accelerates.","marker":"Malitsky (2020)"},{"why":"establishes the non-accelerated GRAAL complexity on L-smooth functions that the paper improves to the optimal accelerated rate.","marker":"Alacaoglu et al. (2023)"},{"why":"defines the target optimal accelerated complexity that Corollary 2 matches up to log factors.","marker":"Nesterov (1983)"},{"why":"contributes the AdGD stepsize rule and the suggestion of a tiny initial stepsize (1e-10) that the paper adopts.","marker":"Malitsky and Mishchenko (2020)"},{"why":"provides the rescaled-function interpretation of acceleration used to motivate the adaptive choice of the momentum parameter.","marker":"Kovalev and Borodich (2024)"},{"why":"is the AC-FGM baseline whose restricted stepsize growth is contrasted with the geometric growth of Algorithm 1.","marker":"Li and Lan (2025)"},{"why":"is the AdaNAG baseline with limited curvature adaptivity, used as the comparison in Section 3.2.","marker":"Suh and Ma (2025)"},{"why":"introduced the (L0,L1)-smoothness assumption under which Corollary 3 gives the near-optimal adaptive guarantee.","marker":"Zhang et al. (2019)"},{"why":"supplies technical lemmas used in the curvature lower bounds for (L0,L1)-smooth functions and the non-adaptive near-optimal baseline in Table 1.","marker":"Vankov et al. (2024)"},{"why":"is the concurrent non-adaptive near-optimal method for (L0,L1)-smooth functions that Algorithm 1 is compared against.","marker":"Tyurin (2025)"}],"fun_headline_variants":["Tuneless acceleration hits optimal rate","GRAAL gains Nesterov speed, keeps zero tuning","Adaptive stepsize hits accelerated complexity","Accelerated GRAAL: near-optimal, zero tuning","No line search, no tuning: Nesterov-accelerated GRAAL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence theorems require the initial stepsize $\\eta_0$ to be small enough relative to how curved the function is and, in the generalized-smooth case, how far the starting point is from the solution; the paper suggests picking a tiny value but gives no way to verify the needed inequality without already knowing those quantities.","fun_headline_variants_meta":{"raw":{"variants":["Tuneless acceleration hits optimal rate","GRAAL gains Nesterov speed, keeps zero tuning","Adaptive stepsize hits accelerated complexity","Accelerated GRAAL: near-optimal, zero tuning","No line search, no tuning: Nesterov-accelerated GRAAL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001049,"raw_usage":{"total_tokens":4507,"prompt_tokens":1143,"completion_tokens":3364,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":759,"completion_tokens_details":{"reasoning_tokens":3283}},"tokens_in":759,"tokens_out":3364,"duration_ms":27503,"temperature":1.0,"reasoning_tokens":3283,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:48:27.219892+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on the one-dimensional quadratic $f(x) = x^2/2$, with $x_0 = 10$, $x^* = 0$, initial stepsizes $\\eta_0 = 10^{-4}$ and $\\eta_0 = 10^{-10}$, and a sequence of accuracies $\\epsilon = 10^{-4}, 10^{-6}, 10^{-8}$, using any fixed constants satisfying eq. (19). If the number of iterations grows roughly like $1/\\epsilon$ instead of $\\sqrt{1/\\epsilon}$ up to a logarithmic term, or if the stepsize $\\eta_k$ fails to grow geometrically toward a value of order 1, then the central complexity and geometric-growth claims for $L$-smooth functions are wrong.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"establishes the non-accelerated GRAAL complexity on L-smooth functions that the paper improves to the optimal accelerated rate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines the target optimal accelerated complexity that Corollary 2 matches up to log factors."}],"review_version":1}