{"id":"8849c24b-a01d-429b-9ec4-081d750400f6","arxiv_id":"2607.26969","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"Comparison-oracle variants of NGD and Polyak GD converge for convex (L0, L1)-smooth objectives when the normalized-gradient error δ is bounded by explicit O(√ε)-scale thresholds.","lead":"The paper proves that Normalized Gradient Descent and Polyak-step methods still converge for convex (L0, L1)-smooth problems when only a noisy comparison-based estimate of the gradient direction is available. That matters for ML settings where exact gradients are expensive and classical Lipschitz smoothness fails.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The paper’s strongest claim is a clean, self-contained extension of known NGD/Polyak analyses to the comparison-oracle + (L0,L1) setting. The proofs supply explicit, checkable δ-thresholds and do not rely on classical Lipschitz smoothness or exact gradients. The practical limitations listed by the reader (unknown R0/M, synthetic-only experiments, unanalyzed adaptive Polyak) correctly keep the verdict at CONDITIONAL, but they are limitations of scope and usability rather than cracks in the central argument. Because the mathematics as written appears sound and the reader already flagged the only material caveat, no verdict adjustment is warranted.","tokens_in":13124,"tokens_out":435,"duration_ms":9399,"concrete_test":"Independently re-derive the key distance recursion (12) and the subsequent bound on v*_N in §6.2 from Assumptions 1–3 and Lemma 2 alone (without consulting the paper’s intermediate steps); confirm that the same sufficient condition δ ≤ (1/(4R0)) min{3/(2L1), √(ε/L0), …} and the Q(ε) iteration complexity emerge.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims (Theorems 1–2) rest on standard convexity, the (L0,L1) inequality, and an absolute-error unit-vector oracle (Assumption 3). The proofs in §§6.2–6.4 derive the stated δ-thresholds and rates from these ingredients via elementary expansions, induction on R_k, and the auxiliary Lemmas 2–5; the algebra appears internally consistent and the δ = O(√ε) message is correctly obtained. The reader’s weakest-assumption note (that δ must meet problem-dependent thresholds involving R0, L0, L1, ε, M) is accurate as a practical caveat but is already explicit in the theorems and does not undermine the mathematical statements. No hidden inconsistency or load-bearing gap in the argument was found.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies unconstrained convex minimization of (L0,L1)-smooth objectives when the only first-order information is a Comparison Oracle that returns a unit vector within absolute error δ of the true normalized gradient. It proposes fixed-horizon Normalized Gradient Descent (Algorithm 1) with steps β_k=β̂/√(N+1) and Polyak-step Gradient Descent (Algorithm 2) that uses a uniform gradient-norm bound M, together with an unanalyzed adaptive-Polyak variant (Algorithm 3). Under convexity and the (L0,L1) assumption, Theorems 1–2 give explicit upper bounds on admissible δ (of order O(√ε) for NGD) that guarantee min_k f(x_k)−f*≤ε, together with corresponding iteration complexities; a partial linear-rate statement is obtained under strong convexity. The analysis rests on an improved integral remainder (Lemma 2) and standard distance-to-optimum expansions. Synthetic experiments on a separable quartic illustrate the predicted sensitivity to L1, δ and initialization.","tokens_in":13306,"tokens_out":1109,"duration_ms":41613,"significance":"The work supplies the first convergence guarantees for classical normalized and Polyak first-order methods under (L0,L1)-smoothness when only an inexact normalized direction is available. The explicit, non-asymptotic δ-thresholds and the sharpened remainder of Lemma 2 (which improves on twice-differentiable bounds in the literature) are concrete technical contributions. If the Comparison Oracle of Zhang & Li can be realized at the stated linear cost, the results enlarge the set of practical oracles for which generalized-smooth convex optimization is provably tractable. The adaptive Polyak heuristic, while unanalyzed, is shown empirically to be less conservative than the uniform-M version. Overall the paper is a solid, self-contained incremental advance rather than a conceptual breakthrough.","major_comments":[{"comment":"Abstract and Introduction claim that convergence rates are derived “for all proposed methods.” Algorithm 3 (adaptive Polyak) is presented as a proposed method and is the strongest performer in Figures 1–2, yet Section 4 explicitly states that no convergence analysis is given. Either a proof (or a clear counter-example showing why the same δ-thresholds fail) should be supplied, or the abstract/claims should be restricted to Algorithms 1–2 and Algorithm 3 labelled a heuristic.","section":"Abstract, §4, Algorithm 3"},{"comment":"The admissible δ in Theorem 1 and Lemma 4/Eq. (6) depends on the unknown quantities R0=∥x0−x*∥, L0, L1 and (for Polyak) max_k(f(xk)−f*) or the a-priori bound M. While Remark 1 removes the trajectory-max dependence, the remaining constants are still unavailable to the user who must choose the oracle accuracy before the run. A short discussion of how these thresholds can be estimated or replaced by doubling schedules would make the guarantees operational rather than purely existential.","section":"Theorem 1, Lemma 4, Remark 1"}],"minor_comments":[{"comment":"The synthetic test function F̂ is claimed (L0,L1)-smooth for every L0,L1>0; the short Hessian argument in §6.5 is correct but would be clearer if the precise statement of Proposition 2.4.2 of Vankov et al. were recalled.","section":"§5, §6.5"},{"comment":"Figures 1–2 lack axis labels for the vertical scale (function gap versus iteration) and do not report the dimension d or the precise realization of the Comparison Oracle; both affect reproducibility.","section":"§5, Fig. 1–2"},{"comment":"Typographical inconsistencies: “Polyak Stepizes” (section title), “inueqalities”, “guaranty”, and the repeated “Title Suppressed Due to Excessive Length” running head.","section":"§4 title, §6.2–6.3"},{"comment":"The constant ν satisfying νe^ν=1 is introduced without a numerical value; stating ν≈0.567 (the Omega-constant) would aid implementers.","section":"Lemma 5, Theorem 2"},{"comment":"Related-work paragraph could briefly contrast the absolute-error unit-vector model (Assumption 3) with the relative-error or stochastic-gradient models already studied for (L0,L1)-smooth optimization.","section":"§1"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically sound and the proofs check out; the main novelty is the combination of the Comparison Oracle with (L0,L1) analysis rather than a new algorithmic idea. Suitable for a solid specialized journal or a conference proceedings track; borderline for a top-tier venue unless the adaptive analysis or a realistic ML experiment is added. No integrity concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing worth knowing is that this is the first place that gives explicit admissible δ and iteration complexities for normalized GD and Polyak steps when the objective is only (L0,L1)-smooth and you only get a unit vector within absolute error δ of the true normalized gradient (the Zhang–Li comparison oracle). That combination is new; the pieces are not.\n\nWhat they do well is the error bookkeeping. Lemma 2 tightens the integral remainder without needing twice differentiability, and Theorems 1–2 push the inexact direction through the usual distance-to-optimum expansions and get concrete thresholds of the form δ = O(√ε) (and analogous bounds for Polyak that also involve M and a gradient-norm floor c). The algebra in §§6.2–6.4 looks internally consistent; the stress-test note is right that there is no hidden load-bearing gap. The synthetic quartic experiments line up with the predicted sensitivity to L1, x0, and δ, and the adaptive-Mk Polyak variant (Algorithm 3) clearly beats the conservative uniform M in practice.\n\nSoft spots, in proportion: Algorithm 3 has no proof, only plots. Everything is synthetic; no code. Several of the δ and M conditions need R0 or a trajectory max-gap, which a user may not know a priori (they flag the N-independent surrogate in Remark 1, but it is looser). Novelty is a careful marriage of Chen/Gorbunov/Vankov-style (L0,L1) analysis with the comparison oracle, not a new principle. None of that breaks the main claims.\n\nThis is for people already working on generalized smoothness or comparison/zeroth-order first-order methods. A serious editor should send it to referees; the math is real enough to deserve that time. I would bring it to reading group only if we are in that sub-area this month. Worth keeping on the shelf as a reference for inexact normalized methods under (L0,L1).","headline":"Clean first rates for NGD and Polyak under (L0,L1)-smoothness with only a comparison-oracle direction; solid proofs, incremental novelty, synthetic-only experiments.","tokens_in":13964,"tokens_out":519,"would_cite":false,"duration_ms":21307,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","65K05"],"pacs":[],"model":"grok-4.5","headline":"Comparison-oracle variants of normalized GD and Polyak steps converge for convex (L0, L1)-smooth problems once the direction error is below explicit, problem-dependent thresholds.","keywords":["generalized smoothness","(L0, L1)-smoothness","Comparison Oracle","normalized gradient descent","Polyak stepsizes","inexact gradients","convex optimization"],"falsifier":"On a known convex (L0, L1)-smooth test function, run the stated NGD or Polyak iteration with a Comparison Oracle whose error deliberately exceeds the δ-threshold of Theorem 1 or Lemma 4; if the best function value still drops below ε at the predicted N, the claimed necessity of those thresholds is false.","tokens_in":13978,"feed_emoji":"↓","tokens_out":1158,"duration_ms":24094,"temperature":0.7,"pith_summary":"Many modern machine-learning objectives are not classically smooth: their gradients grow with the gradient itself. This paper studies convex problems that satisfy the weaker (L0, L1)-smoothness condition and that can be queried only through a Comparison Oracle. That oracle returns a unit vector within absolute error δ of the true normalized gradient, using a linear number of function-value comparisons. The authors construct two first-order methods that use only these inexact directions—Normalized Gradient Descent with a fixed iteration budget and Gradient Descent with Polyak step-sizes (plus an adaptive Polyak variant that estimates a local gradient-norm bound on the fly). They prove explicit upper bounds on δ that still guarantee convergence, and they derive the corresponding rates. The results do not need classical Lipschitz gradients or exact gradient access. Synthetic experiments match the predicted dependence on L1, initialization, and oracle accuracy.","feed_headline":"Inexact directions still converge for (L0,L1)-smooth convex problems","feed_subtitle":"Explicit error thresholds let comparison-oracle NGD and Polyak steps reach any accuracy ε","key_machinery":"The Comparison Oracle (Assumption 3) together with the refined (L0, L1) estimates of Lemma 2: ∥∇f(y)−∇f(x)∥ ≤ (1/L1)((L0+L1∥∇f(x)∥)exp(L1∥y−x∥)−1) and the corresponding integral bound involving φ(t)=et−t−1. These replace classical smoothness and let the authors control the distance decrease when the update uses only an approximate unit direction.","core_discovery":"For convex (L0, L1)-smooth objectives, Normalized Gradient Descent driven by a Comparison Oracle with step sizes βk = β̂/√(N+1) drives the best function value below any ε once N exceeds an explicit Q(ε) and the direction error δ stays below a concrete threshold of order O(√ε) that depends only on R0, L0 and L1. Parallel explicit δ-thresholds and rates hold for Polyak steps (and a strongly convex linear-rate regime), again without exact gradients.","pith_inferences":["Because the Comparison Oracle costs only O(d log(d/δ)) function comparisons, the total work to reach ε scales as roughly that factor times the iteration complexity Q(ε), giving a concrete zeroth-order complexity for (L0, L1)-smooth convex minimization.","The same δ-threshold technique should extend immediately to clipped or momentum variants already analyzed under exact (L0, L1) gradients.","When f*=0 is known (over-parameterized models), the Polyak variant becomes a practical drop-in replacement for normalized SGD that never needs an exact gradient."],"forward_implications":["Normalized first-order methods remain theoretically justified for (L0, L1)-smooth convex problems even when only approximate gradient directions are available.","The admissible oracle error need only be O(√ε), so coarser oracles can still be used for moderate accuracy.","An adaptive Polyak step that solves a local quadratic for the gradient-norm bound can replace a global M and often converges faster in practice.","The same comparison-oracle template can be attached to other normalized or Polyak-style schemes once matching δ-bounds are derived."],"fun_headline_variants":["Comparison-oracle NGD hits any ε on convex (L0,L1)-smooth problems","Explicit δ=O(√ε) lets inexact normalized steps converge without exact grads","Polyak and NGD rates hold under Comparison Oracle for (L0,L1)-smooth convex","Inexact normalized gradients suffice once error stays below R0,L0,L1 threshold","Comparison Oracle drives NGD and Polyak to ε on (L0,L1)-smooth convex objectives"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The oracle must return a unit vector whose absolute error δ from the true normalized gradient stays below explicit thresholds that shrink with the target accuracy, the distance to the optimum, and the smoothness parameters; if δ cannot be made that small, the guarantees do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Comparison-oracle NGD hits any ε on convex (L0,L1)-smooth problems","Explicit δ=O(√ε) lets inexact normalized steps converge without exact grads","Polyak and NGD rates hold under Comparison Oracle for (L0,L1)-smooth convex","Inexact normalized gradients suffice once error stays below R0,L0,L1 threshold","Comparison Oracle drives NGD and Polyak to ε on (L0,L1)-smooth convex objectives"]},"model":"grok-4.5","effort":"low","cost_usd":0.004353,"raw_usage":{"total_tokens":1300,"prompt_tokens":753,"num_sources_used":0,"completion_tokens":123,"cost_in_usd_ticks":43528000,"prompt_tokens_details":{"text_tokens":753,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":424,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":753,"tokens_out":123,"duration_ms":8872,"temperature":1.0,"reasoning_tokens":424,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T15:26:02.679845+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a known convex (L0, L1)-smooth test function, run the stated NGD or Polyak iteration with a Comparison Oracle whose error deliberately exceeds the δ-threshold of Theorem 1 or Lemma 4; if the best function value still drops below ε at the predicted N, the claimed necessity of those thresholds is false.","supporting_citations":[],"review_version":1}