{"id":"b3a76378-08e0-4b5a-88f5-8ea6033e34d0","arxiv_id":"2508.06884","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"New accelerated gradient methods attain the near-optimal rate O(√ℓ(0) R / √ε) under generalized ℓ-smoothness, with the (L0, L1) case provably optimal for small ε and free of non-constant multiplicative factors.","lead":"The paper introduces new accelerated gradient algorithms achieving O(√ℓ(0) R / √ε) oracle complexity for convex optimization under the generalized ℓ-smoothness condition ||∇²f(x)|| ≤ ℓ(||∇f(x)||). This resolves an open question by removing extra factors and subroutines that plagued prior extensions to (L0, L1)-smoothness.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Correctness of new Lyapunov function controlling both gap and gradient norm without initial-gradient or exp(L1 R) terms","rationale":"The reader's weakest_assumption already isolates the same unverified step; the full-text analysis confirms that no other assumption (e.g., twice-differentiability, knowledge of ℓ, or strong convexity) is more load-bearing for the small-ε claim.","tokens_in":1836,"tokens_out":387,"duration_ms":27327,"concrete_test":"Extract the explicit definition of the Lyapunov function V_k and the step-size rule from the proof of the main theorem; substitute the ℓ-smoothness inequality directly into the one-step progress lemma and verify that V_{k+1} ≤ (1 - c √ℓ(0) / R) V_k + O(ε) holds with c independent of ||∇f(x0)|| and of L1 R for the small-ε regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline O(√ℓ(0) R / √ε) rate for arbitrary ℓ (and the optimal O(√L0 R / √ε) for (L0,L1)-smoothness) is obtained only after introducing a new Lyapunov function in the proof of the main convergence theorem. This potential must simultaneously bound f(x)-f* and ||∇f(x)|| while using the ℓ-smoothness inequality ||∇²f(x)|| ≤ ℓ(||∇f(x)||) to produce a telescoping decrease whose leading factor is √ℓ(0) and whose remainder terms contain neither ||∇f(x0)|| nor exponential factors in L1 R. If the decrease inequality fails to close for the chosen step-size schedule (or if an auxiliary term re-introduces the forbidden dependencies when ℓ is non-constant), the claimed removal of all non-constant multiplicative factors does not hold.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript claims to resolve an open question on accelerated gradient methods for convex optimization under the generalized ℓ-smoothness condition ||∇²f(x)|| ≤ ℓ(||∇f(x)||). It achieves O(√ℓ(0) R / √ε) oracle complexity for small ε under virtually any such ℓ, and specifically the optimal O(√L0 R / √ε) rate for (L0, L1)-smoothness that removes all non-constant multiplicative factors, initial-gradient dependence, and exponential terms in L1 R, via a new Lyapunov function and new algorithm designs.","tokens_in":2033,"tokens_out":437,"duration_ms":33438,"significance":"If the central claims hold, the work would be significant for optimization theory: it extends accelerated gradient descent to a broad class of generalized smoothness conditions while attaining near-optimal rates free of the extra factors present in prior extensions. The new Lyapunov construction that jointly controls function gap and gradient norm under the ℓ-smoothness inequality is a technical strength that could enable cleaner analyses for first-order methods beyond standard L-smoothness.","major_comments":[{"comment":"Proof of the main convergence theorem: the new Lyapunov function is asserted to control both f(x)-f* and ||∇f(x)|| simultaneously via the ℓ-smoothness inequality ||∇²f(x)|| ≤ ℓ(||∇f(x)||) and to produce a telescoping decrease whose leading factor is √ℓ(0) with no residual dependence on ||∇f(x0)|| or exponential factors in L1 R. The step-size schedule must be shown to close this inequality without re-introducing the forbidden terms when ℓ is non-constant; otherwise the claimed removal of all non-constant multiplicative factors does not hold.","section":"Proof of the main convergence theorem"}],"minor_comments":[{"comment":"The abstract and introduction could more explicitly reference the theorem number and section containing the Lyapunov function definition to improve readability for readers focused on the technical novelty.","section":"Abstract and Introduction"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and for recognizing the potential significance of the results. We address the single major comment below.","responses":[{"response":"We appreciate the referee drawing attention to the core of the analysis. The manuscript constructs a Lyapunov function that simultaneously upper-bounds the function gap and the squared gradient norm; the generalized smoothness inequality is then applied directly to the gradient step, yielding a one-step decrease whose dominant term is proportional to √ℓ(0) times the current gap. Because the Lyapunov already controls ||∇f(x_k)||, any remainder that would otherwise depend on ℓ(||∇f(x_k)||) – ℓ(0) is absorbed without introducing a factor that grows with the initial gradient or with L1 R. The step-size is set to a constant multiple of 1/√ℓ(0) (independent of the current gradient norm), and the proof verifies that this choice closes the inequality for any non-decreasing ℓ without reintroducing the undesired terms; the small-ε regime then ensures that transient dependence on x0 vanishes in the final bound. The full algebraic verification appears in the proof of the main theorem. If the referee finds the telescoping step insufficiently highlighted, we are prepared to insert a short clarifying lemma that isolates the step-size closure argument.","revision_made":"partial","referee_comment":"[Proof of the main convergence theorem] Proof of the main convergence theorem: the new Lyapunov function is asserted to control both f(x)-f* and ||∇f(x)|| simultaneously via the ℓ-smoothness inequality ||∇²f(x)|| ≤ ℓ(||∇f(x)||) and to produce a telescoping decrease whose leading factor is √ℓ(0) with no residual dependence on ||∇f(x0)|| or exponential factors in L1 R. The step-size schedule must be shown to close this inequality without re-introducing the forbidden terms when ℓ is non-constant; otherwise the claimed removal of all non-constant multiplicative factors does not hold."}],"tokens_in":1495,"tokens_out":430,"duration_ms":38526,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that this paper claims to resolve the open question of whether an AGD-style method can hit the optimal O(√ℓ(0) R / √ε) oracle complexity for small ε under the ℓ-smoothness condition, including the (L0, L1) case, without the extra initial-gradient dependence, exponential factors, or auxiliary subroutines seen in earlier extensions. It does so by designing a new Lyapunov function that is supposed to bound both the function gap and the gradient norm together, then using the inequality ||∇²f(x)|| ≤ ℓ(||∇f(x)||) to produce a telescoping decrease whose leading term is √ℓ(0) and whose remainders stay controlled for virtually any ℓ. For (L0, L1)-smoothness this yields the clean O(√L0 R / √ε) bound that the abstract calls optimal in the small-ε regime. If the derivation works as stated, that is a concrete technical step that removes the non-constant penalties documented in prior work on the same setting. The algorithm itself appears to be a direct modification of standard accelerated gradient descent with a tailored step-size schedule tied to the new potential. That is the part worth crediting: a focused attempt to close a specific gap rather than another incremental tweak. The soft spot is exactly where the stress test flags it. The entire rate rests on the Lyapunov decrease inequality closing cleanly for the chosen steps without reintroducing forbidden terms when ℓ is non-constant. Without the full proof or any numerical checks, it is impossible to tell whether the construction avoids those dependencies or whether some auxiliary term was adjusted to make the bound hold. The abstract states the result and optimality claim, but the central derivation is not visible here, so the soundness cannot be assessed beyond the high-level outline. This is aimed at optimization researchers who work on rates under relaxed smoothness conditions that appear in certain ML losses. A reader already following the literature on generalized smoothness would get direct value from the algorithm and the Lyapunov idea, assuming the math checks. The paper shows clear engagement with the prior results it cites and poses a well-defined technical question. It deserves a serious referee to examine the proof of the main convergence theorem and the lower-bound argument for optimality.","headline":"Tyurin gives a candidate clean optimal accelerated rate for generalized smoothness via a new Lyapunov, but that construction is the part that needs the closest look.","tokens_in":2489,"tokens_out":525,"would_cite":false,"duration_ms":43651,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean","rs_theorem":"reality_from_one_distinction","paper_passage":"We resolve this open question. Leveraging a new Lyapunov function and designing new algorithms, we achieve O(√ℓ(0)R/√ε) oracle complexity..."}],"headline":"Convex optimization rates under ℓ-smoothness; no RS cost or forcing structure","alignment":"orthogonal","rationale":"Paper develops AGD variants and a Lyapunov function Vk = f(yk)−f∗ + Γk/2‖uk−x∗‖² for convergence under the ℓ-smoothness assumption ‖∇²f(x)‖ ≤ ℓ(‖∇f(x)‖). All results are standard first-order complexity bounds (O(√ℓ(0)R/√ε)) with no reference to reciprocal cost J, golden-ratio identities, recognition ladders, 8-tick periodicity, or any RS forcing theorem. Domain is purely algorithmic analysis in math.OC.","tokens_in":68235,"confidence":"high","tokens_out":247,"duration_ms":10236,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Accelerated gradient methods achieve the rate O(√ℓ(0) R / √ε) under generalized ℓ-smoothness.","keywords":["accelerated gradient descent","ℓ-smoothness","(L0, L1)-smoothness","oracle complexity","Lyapunov function","convex optimization","near-optimal rates"],"falsifier":"A concrete counterexample function satisfying (L0, L1)-smoothness on which the new accelerated method requires asymptotically more than O(√L0 R / √ε) gradient evaluations to reach small ε would disprove the claimed rate.","tokens_in":2740,"feed_emoji":"","tokens_out":697,"duration_ms":49732,"temperature":0.7,"pith_summary":"The paper establishes that accelerated gradient methods can reach the optimal oracle complexity O(√ℓ(0) R / √ε) for convex problems satisfying the generalized ℓ-smoothness condition, which includes both standard L-smoothness and (L0, L1)-smoothness. A sympathetic reader would care because earlier extensions to these broader smoothness classes added dependence on the initial gradient, exponential factors, or required extra sub-routines, leaving the question open whether a clean AGD-style bound is possible for small error tolerances. By introducing a new Lyapunov function and accompanying algorithms, the work shows the bound holds for virtually any ℓ and is provably optimal without extra multiplicative factors in the (L0, L1) case.","feed_headline":"Accelerated gradients achieve optimal rate under general smoothness","feed_subtitle":"New analysis removes extra factors from prior bounds and proves optimality for small errors under (L0, L1)-smoothness.","key_machinery":"New Lyapunov function that simultaneously controls the function value gap and the gradient norm under the ℓ-smoothness inequality without dependence on the initial gradient or exponential terms.","core_discovery":"Leveraging a new Lyapunov function and designing new algorithms, we achieve O(√ℓ(0) R / √ε) oracle complexity for small-ε and virtually any ℓ. For (L0, L1)-smoothness, our bound O(√L0 R / √ε) is provably optimal in the small-ε regime and removes all non-constant multiplicative factors present in prior accelerated algorithms.","pith_inferences":["Similar Lyapunov constructions could be tested in stochastic first-order methods where gradient-dependent smoothness also arises.","Implementations might simplify by dropping the auxiliary steps that earlier methods needed for non-standard smoothness.","The optimality result implies that further rate gains in the small-ε regime would need techniques outside standard first-order acceleration."],"forward_implications":["The bound O(√L0 R / √ε) is optimal for (L0, L1)-smoothness in the small-ε regime.","All non-constant multiplicative factors from prior accelerated algorithms are eliminated.","The complexity result applies to virtually any ℓ in the generalized smoothness condition.","The new algorithms work directly with the Lyapunov analysis without auxiliary sub-routines."],"fun_headline_variants":["Optimal rates for AGD under generalized smoothness","Near-optimal AGD convergence under (L0, L1)-smoothness","Optimal small error complexity for AGD under general smoothness","AGD bounds remove non-constant factors under (L0, L1)-smoothness"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The analysis depends on the existence of a new Lyapunov function that controls both the function value gap and gradient norm directly from the ℓ-smoothness condition without extra terms tied to initial values.","fun_headline_variants_meta":{"raw":{"variants":["Optimal rates for AGD under generalized smoothness","Near-optimal AGD convergence under (L0, L1)-smoothness","Optimal small error complexity for AGD under general smoothness","AGD bounds remove non-constant factors under (L0, L1)-smoothness"]},"model":"grok-4.3","cost_usd":0.020984,"raw_usage":{"total_tokens":8801,"prompt_tokens":761,"num_sources_used":0,"completion_tokens":71,"cost_in_usd_ticks":209840500,"prompt_tokens_details":{"text_tokens":761,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":7969,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":761,"tokens_out":71,"duration_ms":84726,"temperature":1.0,"reasoning_tokens":7969,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-22T13:23:11.905157+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete counterexample function satisfying (L0, L1)-smoothness on which the new accelerated method requires asymptotically more than O(√L0 R / √ε) gradient evaluations to reach small ε would disprove the claimed rate.","supporting_citations":[],"review_version":1}