{"id":"baf1c929-c96e-4925-9ae4-5b227aac0aa6","arxiv_id":"2412.14637","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"Armijo backtracking variants are shown to achieve optimal first-order complexity under (L0,L1) smoothness and on analytic functions, with no hyperparameter tuning required.","lead":"This paper derives iteration complexity bounds for Armijo backtracking optimizers under two assumptions suited to deep learning: (L0,L1) smoothness and analyticity. It reports that a memory-based Armijo variant reaches optimal epsilon-dependence without hyperparameter tuning, and that a new explicit-implicit Armijo condition reaches O(1/epsilon) on analytic functions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.1 relies on the step-size lower bound eta_n >= eta_tilde_n/f1, but Algorithm 1 can accept an arbitrarily small memory step without backtracking; there is no such uniform bound and the complexity claim fails for small eta_init.","rationale":"The strongest claim of the paper is Theorem 2.1, which asserts an optimal complexity for the memory Armijo algorithm under (L0,L1)-smoothness without hyperparameter tuning. The proof's central estimate is the uniform lower bound eta_n >= eta_tilde_n/f1. This bound is not true for Algorithm 1: the memory step is not reset, so a step that is already admissible is accepted without division, and eta_n can be arbitrarily small. The counterexample in concrete_test exhibits a concrete (L0,L1)-smooth function and initialization for which the claimed iteration bound is violated, so the theorem is not merely missing a detail; as written it is false. Section 3's EIA acceleration result also depends on the author's unpublished preprint [11] for the asymptotic step lower bound and convergence, which limits independent verification, but the Section 2 gap is the single most load-bearing issue. The paper contains plausible ideas and a repair may be possible with an initialization or warm-up condition, but the submitted central claims are not supported. Thus the reader's REJECT verdict is appropriate and no change is needed.","tokens_in":21494,"tokens_out":5890,"duration_ms":46286,"concrete_test":"Run Algorithm 1 with the one-dimensional function R(x)=0.5*x^2 (so L0=1, L1=0.001 to fit the (L0,L1)-smooth framework), lambda=1/2, f1=2, f2=2, epsilon=0.1, and eta_init=2^{-1000}. Theorem 2.1 with f1=2, lambda=1/2 predicts min_{0<=k<=n} |nabla R(x_k)| <= epsilon once n >= 8*L0*Delta/epsilon^2 = 8*0.5/0.01 = 400. Simulate 400 iterations: the memory step grows as eta_k=2^{-1000+k}, so even at k=400 the step is 2^{-600}; the iterate is essentially unchanged and the gradient remains approximately 1, far above epsilon. This directly checks the missing step-size lower bound and falsifies the theorem's conclusion.","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing step in Section 2.3 is the assertion 'At iteration n, the time step found by the backtracking satisfies eta_n >= eta_tilde_n/f1'. This is used to lower-bound every Armijo decrease by a positive constant depending only on epsilon, then to telescope the function gap. In Algorithm 1, however, the current step eta_n is the memory value carried from the previous iteration (line 15) and is not reset before the inner loop. If this eta_n already satisfies the Armijo condition, the 'repeat' loop exits immediately at line 14 with no division by f1, so the accepted step can be arbitrarily small compared with eta_tilde_n. Since eta_tilde_n is only an upper threshold for sufficient decrease, eta_n could be as small as the user-supplied eta_init or any fraction of it that was admitted in earlier iterations. Consequently the per-iteration lower bound and the telescoping sum in the proof are invalid. Theorem 2.1 is false as stated: for any fixed L0, L1, lambda, f1, f2, Delta, and epsilon, choosing eta_init sufficiently small leaves the step size tiny for more than the claimed complexity bound's number of iterations, keeping the gradient norm above epsilon. The claimed optimal clipping-GD-like acceleration is therefore not established. A warm-up assumption (e.g., eta_init >= eta_tilde_0/f1) or a modification that forces backtracking from a sufficiently large step each iteration would be needed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies two Armijo-type line-search methods in the deep-learning-relevant settings of (L0,L1)-smoothness and analyticity. Section 2 analyses a 'memory' backtracking Armijo variant (Algorithm 1) and claims in Theorem 2.1 that, after n ≥ f1 L1 Δ / (λ ε ln((L0+L1(2-λ)ε)/(L0+L1 ε))) iterations, the iterates satisfy min_{0≤k≤n} ||∇R(θ_k)|| ≤ ε; this is asymptotic to 8 L0 Δ / ε² for the practical choice f1=2, λ=1/2, matching clipping gradient descent without hyperparameter tuning. Section 3 introduces an Explicit-Implicit Armijo (EIA) method, derives a global Łojasiewicz inequality, and claims O(ε^{-1}) complexity for analytic radially unbounded functions (Corollary 3.1) together with o(n^{-1}) decay of the minimal gradient (Corollary 3.2). The paper also compares total evaluation counts with clipping GD, using estimates from the author's own thesis and preprints.","tokens_in":21808,"tokens_out":21436,"duration_ms":154352,"significance":"If the results were correct, they would be significant: they would show that Armijo-like line search can retain the parameter-free character of classical backtracking while achieving clipping-GD-like acceleration under generalized smoothness and an optimal ε-dependence for analytic functions. The paper has some strengths: explicit constants in the main bound, a Lambert-type sufficient step-size argument, and an attempt to account for function evaluations. However, the central theorem rests on a false invariant about accepted step sizes, and Section 3 inherits the same structural problem while also relying on load-bearing results from an unpublished preprint. The advertised claims are therefore not established in the present form.","major_comments":[{"comment":"The proof uses the assertion 'At iteration n, the time step found by the backtracking satisfies η_n ≥ \\tilde η_n / f1'. In Algorithm 1 the trial step η is carried over from the previous outer iteration and is multiplied by f2 only after an accepted step (line 15). If the carried η already satisfies the Armijo condition, the repeat-until loop exits immediately without any division by f1, so η_n can be arbitrarily small compared with \\tilde η_n. In particular, the lower bound η_n ≥ \\tilde η_n / f1 is not valid without an additional assumption such as η_init ≥ \\tilde η_0 / f1 or a reset of the trial step at each iteration. Choosing η_init sufficiently small (for example, exponentially small in 1/ε on a strongly convex quadratic) can keep the step size tiny for many more than O(1/ε²) iterations, so the gradient norm need not reach ε within the claimed bound. Thus Theorem 2.1 is false as stated, and the telescoping argument in §2.3 does not establish the advertised clipping-GD-like acceleration.","section":"§2.3, Theorem 2.1"},{"comment":"The lower bound η_n ≥ η* = 2(1-λ)/(f1(1+2λ)L) is asserted by combining Lemma 3.1 with Proposition 1 of [11]. Lemma 3.1 provides only a sufficient upper bound on η for inequality (8); it does not imply that the step produced by Algorithm 1's memory backtracking is bounded below. A carried-over η that already satisfies (2) and (8) is accepted without division, so the same flaw as in §2.3 occurs. Moreover, the convergence of EIA and the step lower bound are imported from Proposition 1 and Theorem 6 of the author's preprint [11] without statement or proof. Since these results are load-bearing for Corollary 3.1, the paper is not self-contained; the authors should either prove these results or formulate them explicitly in the manuscript.","section":"§3.2"},{"comment":"The claim that EIA achieves the optimal O(ε^{-1}) complexity on analytic functions is not established. The bound in Corollary 3.1 involves constants \\tilde s, L, M, and φ that depend on the whole trajectory K0 and on the Łojasiewicz data of the specific function; it is not a uniform complexity over a class of functions with fixed smoothness and initial gap. Nesterov's lower bound cited in Remark 3.4 is for smooth convex functions and does not directly yield a lower bound for the class of general nonconvex analytic functions considered here. A precise statement of the function class and a matching lower bound are needed before concluding optimality.","section":"§3.6, Remark 3.4"}],"minor_comments":[{"comment":"The displayed inequality in Lemma 2.2 has an erroneous coefficient: the term multiplying ||y2-y1|| should be (L0 + L1||∇R(y1)||)/L1, not (L0 + L1||∇R(y1)||). The integral in the proof and the subsequent use in §2.3 are consistent with the corrected version, so this appears to be a typo, but it should be fixed.","section":"§2.2, Lemma 2.2"},{"comment":"The statement writes 'min_{0≤k≤n} ∇R(θ_k) ≤ ε' where clearly the norm ||∇R(θ_k)|| is intended; there is also a typo 'tyhat' for 'that'. Please correct these.","section":"§2.3, Theorem 2.1"},{"comment":"In the proof of Lemma 3.3, case 1, equation (14) states \\tilde R(θ_k) = R_i - R(θ_k), but for an interval of the form ](R_i+R_{i+1})/2, R_{i+1}[ the correct identity is \\tilde R(θ_k) = R_{i+1} - R(θ_k). The argument goes through with the corrected index, but the displayed equation should be amended.","section":"§3.4, Lemma 3.3"},{"comment":"The definitions of r0 and r1 in Parts 2 and 3 appear to have an inverted factor: the expressions (1-d)/(2 λ η_min ε²) should likely be (1-d) λ η_min ε² / 2. Although the proof only needs some positive radius, the displayed formulas should be corrected for clarity.","section":"§3.4, Lemma 3.4"},{"comment":"The upper bound on function evaluations per iteration is quoted from the author's own thesis [10] and preprint [12] with no statement or proof. Since this bound is used to compare the total cost with clipping GD, it should be stated precisely and either proved or clearly identified as an external heuristic.","section":"§2.3, evaluation count"}],"recommendation":"reject","confidential_remarks":"The decisive issue is the invalid step-size lower bound in Theorem 2.1: without an assumption on η_init or a modification of Algorithm 1, the advertised parameter-free acceleration is unsupported. If the authors repair the backtracking procedure (for instance, by resetting the trial step each iteration) and re-derive the evaluation counts, a resubmission could be considered. The heavy reliance on the author's own preprint [11] and thesis [10] should also be resolved, ideally by including the missing statements and proofs in the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper has a genuinely interesting idea — showing that memory Armijo backtracking can adapt to (L0,L1) smoothness and analytic functions without tuning — but the central complexity theorem in Section 2 is not proven and as stated is false. The Section 3 results are plausible but lean heavily on the author's own unpublished preprint [11].\n\nWhat's good: The (L0,L1) smoothness analysis in Lemmas 2.1–2.2 is new and clean. The global Lojasiewicz lemma (3.2) is carefully constructed and well motivated. The explicit-implicit Armijo condition (8) is a nice extension of [11], and the O(ε^{-1}) bound for analytic functions would be a strong result if the details check out. The paper is honest about what comes from other sources: the backtracking algorithm is from [10], and the convergence theory of EIA is quoted from [11].\n\nThe soft spot is a big one. The proof of Theorem 2.1 hinges on the assertion that the accepted step satisfies η_n ≥ η̃_n/f1. That is false for the memory backtracking. In Algorithm 1, the trial step at the start of the inner loop is the memory value from the previous iteration. If that step already satisfies the Armijo condition, the repeat loop exits without ever dividing by f1. So the accepted step can be arbitrarily small — the algorithm never tries larger steps within the iteration. For any fixed problem, you can take η_init tiny and the claimed complexity bound fails. The proof needs either η_init ≥ η̃_0/f1, a warm-up argument, or a different invariant. The same structural issue reappears in Section 3: the lower bound η_n ≥ η* is imported from [11] but the memory backtracking does not guarantee it unless the initial step is large enough.\n\nSection 3 also relies on the unpublished preprint [11] for convergence and step-size lower bounds, and the function-evaluation counts come from [10,12]. That makes it hard to verify the work without tracking down those sources. The paper's own experiments are not included, so the only evidence is theoretical.\n\nWho gets value from this? A researcher in nonconvex optimization theory might find the (L0,L1) descent lemmas useful, and the explicit-implicit Armijo idea is worth thinking about. The paper is not a waste of time to read because it clearly identifies a gap in the literature and proposes concrete mechanisms. But as a contribution, the main claims are not supported.\n\nRecommendation: I would not accept this as is. The step-size issue is load-bearing and fixable, so I'd tell the author to add a warm-up assumption or modify the algorithm, and make Section 3 self-contained. If a revised version addresses that, I'd be happy to see it. For now, I'd only send it to a referee if the editor believes the fix is plausible; otherwise a desk reject with an explanation is fine.","headline":"Main complexity theorem for memory Armijo rests on a false step-size lower bound; Section 3 leans on an unpublished preprint, but the ideas are promising.","tokens_in":22331,"tokens_out":6280,"would_cite":false,"duration_ms":48546,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K10","90C26","65Y20","26E05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a memory-backtracking Armijo algorithm reaches optimal worst-case rates on deep-learning-relevant smoothness classes, and that an explicit-implicit variant reaches the optimal $\\varepsilon^{-1}$ complexity on…","keywords":["Armijo backtracking","generalized smoothness","(L0,L1)-smoothness","analytic functions","Lojasiewicz inequality","nonconvex optimization complexity","parameter-free optimization","deep learning optimization"],"falsifier":"Run Algorithm 1 with a large initial step $\\eta_{\\mathrm{init}}$ on a one-dimensional $(L_0,L_1)$-smooth function with $L_1>0$ and record, for each iteration, whether the accepted step is below $\\tilde\\eta_n/f_1$ when the first trial is already admissible. If such an iteration occurs, the per-iteration decrease can fall below $\\lambda \\tilde\\eta_n \\|\\nabla R(\\theta_n)\\|^2/f_1$, breaking the telescoping sum that produces Theorem 2.1; the claim would then be settled by exhibiting the corresponding iteration count exceeding $8L_0\\Delta/\\varepsilon^2$.","tokens_in":21255,"feed_emoji":"📉","tokens_out":10693,"duration_ms":85507,"temperature":0.7,"pith_summary":"This paper tries to establish that Armijo-style line-search algorithms, which require no learning-rate tuning, achieve optimal worst-case complexity under assumptions tailored to deep-learning losses. For an $(L_0,L_1)$-smooth objective, meaning the Hessian norm is bounded by $L_0$ plus $L_1$ times the gradient norm, the memory-backtracking Armijo variant reaches a gradient norm below $\\varepsilon$ in at most $f_1 L_1 \\Delta/(\\lambda \\varepsilon \\ln((L_0+L_1(2-\\lambda)\\varepsilon)/(L_0+L_1\\varepsilon)))$ iterations, which behaves like $8L_0\\Delta/\\varepsilon^2$ at the practical parameter values $f_1=2$, $\\lambda=1/2$. That matches the acceleration of clipping gradient descent while removing the need to tune the step size and clipping threshold. For analytic radially unbounded objectives, the explicit-implicit Armijo algorithm reaches $\\varepsilon$-stationarity in $O(\\varepsilon^{-1})$ iterations, the optimal $\\varepsilon$-dependence, and its complexity changes from linear in the initial gap $\\Delta$ to roughly $\\sqrt{\\Delta}$ once $\\Delta$ is small relative to the gaps between critical values. The practical upshot is that a parameter-free first-order method can theoretically match the best tuned optimizers on nonconvex problems relevant to deep learning.","feed_headline":"Armijo backtracking hits optimal complexity with no tuning","feed_subtitle":"A parameter-free line search matches clipping gradient descent's speed under (L0,L1)-smoothness, then reaches ε⁻¹ on analytic losses.","key_machinery":"The argument runs through two mechanisms. For generalized smoothness, Lemma 2.2 replaces the standard quadratic upper model of smooth optimization with an exponential bound coming from a Gronwall estimate on the gradient, and Lemma 2.3 solves the resulting Lambert-type inequality to give an explicit step-size formula $\\tilde\\eta_n = \\ln((L_0+L_1(2-\\lambda)\\|\\nabla R(\\theta_n)\\|)/(L_0+L_1\\|\\nabla R(\\theta_n)\\|))/(L_1\\|\\nabla R(\\theta_n)\\|)$. The backtracking must accept a step at least $\\tilde\\eta_n/f_1$, so each iteration decreases the function by at least $\\lambda \\tilde\\eta_n \\|\\nabla R(\\theta_n)\\|^2/f_1$, and monotonicity of the logarithm allows replacing the per-iteration gradient norm by $\\varepsilon$ and telescoping the gaps. For analytic functions, the explicit-implicit Armijo condition $R(\\theta_{n+1})-R(\\theta_n) \\le -\\lambda \\eta_n \\|\\nabla R(\\theta_n)\\|\\,\\|\\nabla R(\\theta_{n+1})\\|$ couples the step to the next gradient; a global Lojasiewicz inequality (Lemma 3.2) built from the finitely many critical values of the analytic function provides $\\varphi'(\\tilde R(\\theta))\\|\\nabla R(\\theta)\\| \\ge 1$ on compact sets, and the interval $[R(\\theta_n), R(\\theta_0)]$ is cut at critical values and their midpoints so that iterate-length sums telescope on each critical-value-free piece. The lower bound $\\eta_* = 2(1-\\lambda)/(f_1(1+2\\lambda)L)$, with $L$ the local Lipschitz constant of $\\nabla R$, converts the path-length bound into an iteration count.","core_discovery":"The paper's central claim is Theorem 2.1: for a twice-differentiable, lower-bounded function satisfying $\\|\\nabla^2R(\\theta)\\| \\le L_0 + L_1\\|\\nabla R(\\theta)\\|$, the memory-backtracking Armijo algorithm guarantees $\\min_{0\\le k\\le n} \\|\\nabla R(\\theta_k)\\| \\le \\varepsilon$ as soon as $n \\ge f_1 L_1 \\Delta/(\\lambda \\varepsilon \\ln((L_0+L_1(2-\\lambda)\\varepsilon)/(L_0+L_1\\varepsilon)))$, with asymptotic form $f_1 L_0 \\Delta/(\\lambda(1-\\lambda)\\varepsilon^2)$ as $\\varepsilon\\to 0$ and $8L_0\\Delta/\\varepsilon^2$ for $f_1=2$, $\\lambda=1/2$. Unlike plain gradient descent under this assumption, the bound contains no dependence on $M=\\sup_S\\|\\nabla R\\|$, so the algorithm has the same form of acceleration as clipping gradient descent, but without any tuned step size or clipping threshold. The second central claim, Corollary 3.1, says that for analytic radially unbounded functions, the explicit-implicit Armijo algorithm reaches $\\min \\|\\nabla R\\| \\le \\varepsilon$ in $O(\\varepsilon^{-1})$ iterations, which is the optimal $\\varepsilon$-dependence for first-order methods and matches the best known rate for smooth convex optimization despite the objective being nonconvex. The proof also produces a path-length bound that makes the dependence on the initial gap $\\Delta$ conditional on $\\Delta/(s+1)$, where $s$ is the number of critical values, yielding a phase transition: for small gaps the complexity depends on $\\Delta^\\alpha$ with $\\alpha\\le 1/2$ rather than on $\\Delta$.","pith_inferences":["If the $\\Delta$-bifurcation is real, worst-case complexity for analytic nonconvex problems can improve by a square root simply because the initial gap is small relative to critical-value spacing; that is a qualitative prediction about optimization landscape geometry that could be tested on synthetic analytic functions with known critical values.","The explicit-implicit condition is a semi-implicit discretization of the Lyapunov inequality for gradient flow; the same stabilization idea could be applied to stochastic or Adam-like updates, and whether the $O(\\varepsilon^{-1})$ rate survives noise is a natural open extension the paper does not address.","A practical testable extension is to compare Algorithm 1 against tuned clipping gradient descent and Adam on a small neural-network training task in terms of wall-clock gradient evaluations; the paper's bounds predict the Armijo variant should match clipping's acceleration per gradient evaluation.","The reliance on finite critical values and a global Lojasiewicz function suggests the analytic-rate result may extend to any function whose critical values are finite on compact sets and whose gradients satisfy a global Lojasiewicz inequality, even outside analyticity; the paper notes this structural possibility but does not pursue it."],"forward_implications":["On $(L_0,L_1)$-smooth objectives, the memory Armijo algorithm reaches $\\varepsilon$-stationarity in at most $8L_0\\Delta/\\varepsilon^2$ iterations at the standard parameters, independent of the global gradient bound $M$ and without tuning.","Counting backtracking function evaluations, the total gradient evaluations for Algorithm 1 stay within a factor of the iteration bound stated in the paper, roughly $4[1+\\log(f_2)/\\log(f_1)]L_0\\Delta/\\varepsilon^2 + 8L_0\\Delta/\\varepsilon^2$, so the improvement over clipping gradient descent is not erased by the line search.","For analytic radially unbounded functions, the explicit-implicit Armijo algorithm attains $O(\\varepsilon^{-1})$ iteration complexity, matching the optimal first-order rate for smooth convex functions despite nonconvexity.","The same analytic-function analysis gives $\\min_{0\\le k\\le n-1}\\|\\nabla R(\\theta_k)\\| = o(n^{-1})$, the same asymptotic speed as analyses of o-minimal or definable functions, but without requiring any tuned step size.","The complexity exhibits a bifurcation in the initial gap $\\Delta$: when $\\Delta/(s+1)$ is below a threshold set by the critical-value gaps, the dependence is $\\Delta^\\alpha$ with $\\alpha\\le 1/2$, which becomes $\\sqrt{\\Delta}$ for Morse functions, instead of linear $\\Delta$."],"supporting_citations":[{"why":"Supplies the $(L_0,L_1)$-smoothness assumption and the clipping-GD baseline that motivates the acceleration claim.","marker":"[26]"},{"why":"Gives the improved clipping-GD complexity that Section 2's bound is compared against and the lower-bound context it must match.","marker":"[69]"},{"why":"Implements Algorithm 1 with the memory backtracking and supplies the per-iteration evaluation count used to convert iteration complexity to gradient evaluations.","marker":"[10]"},{"why":"Supports the convergence of the iterates and the claim that the memory backtracking needs fewer function evaluations.","marker":"[12]"},{"why":"Provides the convergence-in-iterates framework for Armijo line searches under the Kurdyka-Lojasiewicz inequality, used in Section 3.","marker":"[50]"},{"why":"Provides the abstract Lyapunov interpretation and the convergence result that the explicit-implicit Armijo condition builds on.","marker":"[11]"},{"why":"Gives the $o(n^{-1})$ rate for definable functions that the analytic-function rate matches without tuning.","marker":"[28]"},{"why":"The classical Armijo condition that the algorithms extend and whose parameter-free advantage is the paper's starting point.","marker":"[4]"},{"why":"Provides the worst-case analytic function establishing optimality of the $\\varepsilon^{-1}$ dependence.","marker":"[48]"}],"fun_headline_variants":["No tuning needed: Armijo matches clipping speed","Armijo achieves optimal complexity without hyperparameters","Parameter-free Armijo: optimal complexity for nonconvex","Armijo without tuning: optimal rate on analytic losses"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every accepted backtracking step is no smaller than a fixed fraction $1/f_1$ of the explicit admissible step $\\tilde\\eta_n$ derived from the smoothness constants; the memory variant can exit its inner loop on the first trial step, before any division, so that inequality is not guaranteed, and the Section 3 lower bound $\\eta_*$ has the same vulnerability.","fun_headline_variants_meta":{"raw":{"variants":["No tuning needed: Armijo matches clipping speed","Armijo achieves optimal complexity without hyperparameters","Parameter-free Armijo: optimal complexity for nonconvex","Armijo without tuning: optimal rate on analytic losses"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000709,"raw_usage":{"total_tokens":3233,"prompt_tokens":1024,"completion_tokens":2209,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":640,"completion_tokens_details":{"reasoning_tokens":2148}},"tokens_in":640,"tokens_out":2209,"duration_ms":15019,"temperature":1.0,"reasoning_tokens":2148,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:04:49.291147+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 with a large initial step $\\eta_{\\mathrm{init}}$ on a one-dimensional $(L_0,L_1)$-smooth function with $L_1>0$ and record, for each iteration, whether the accepted step is below $\\tilde\\eta_n/f_1$ when the first trial is already admissible. If such an iteration occurs, the per-iteration decrease can fall below $\\lambda \\tilde\\eta_n \\|\\nabla R(\\theta_n)\\|^2/f_1$, breaking the telescoping sum that produces Theorem 2.1; the claim would then be settled by exhibiting the corresponding iteration count exceeding $8L_0\\Delta/\\varepsilon^2$.","supporting_citations":[{"cited_title":"Zhang and T","cited_arxiv_id":null,"evidence_quote":"Supplies the $(L_0,L_1)$-smoothness assumption and the clipping-GD baseline that motivates the acceleration claim."},{"cited_title":"In: Neural Information Processing Systems (NeurIPS) (2020)","cited_arxiv_id":null,"evidence_quote":"Gives the improved clipping-GD complexity that Section 2's bound is compared against and the lower-bound context it must match."},{"cited_title":"Theses, Universit´ e de Bordeaux (2024)","cited_arxiv_id":null,"evidence_quote":"Implements Algorithm 1 with the memory backtracking and supplies the per-iteration evaluation count used to convert iteration complexity to gradient evaluations."},{"cited_title":"In: Arxiv (2024)","cited_arxiv_id":null,"evidence_quote":"Supports the convergence of the iterates and the claim that the memory backtracking needs fewer function evaluations."},{"cited_title":"Springer Proceedings in Mathematics and Statis- tics 50 (2013)","cited_arxiv_id":null,"evidence_quote":"Provides the convergence-in-iterates framework for Armijo line searches under the Kurdyka-Lojasiewicz inequality, used in Section 3."},{"cited_title":"Arxiv (2024)","cited_arxiv_id":null,"evidence_quote":"Provides the abstract Lyapunov interpretation and the convergence result that the explicit-implicit Armijo condition builds on."},{"cited_title":"Mathematical Programming 202, 385 (2023)","cited_arxiv_id":null,"evidence_quote":"Gives the $o(n^{-1})$ rate for definable functions that the analytic-function rate matches without tuning."},{"cited_title":"Pacific Journal of Mathematics 16(1), 1 – 3 (1966)","cited_arxiv_id":null,"evidence_quote":"The classical Armijo condition that the algorithms extend and whose parameter-free advantage is the paper's starting point."}],"review_version":1}