{"id":"3a7e4711-3df1-4145-9429-781b0b23edd7","arxiv_id":"2502.00753","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper introduces ℓ*-smoothness, a norm-dual generalization of ℓ-smoothness, and proves classical O(1/T), O(1/T²), and Õ(1/√t) rates for mirror descent, accelerated mirror descent, optimistic mirror descent, mirror prox, and stochastic mirror descent.","lead":"This paper extends the concept of smoothness to work with arbitrary norms instead of the Euclidean norm, then proves convergence rates for several mirror descent algorithms under this weaker assumption. The main value is a theory that brings generalized smoothness, previously limited to gradient descent in Euclidean spaces, to non-Euclidean settings used throughout machine learning.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Self-bounding Lemma 2 is false for bounded domains: for f(x)=e^{wx} on X=(-1,1) with ℓ(α)=wα, w=0.01, ‖∇f(0)‖² exceeds 2ℓ(2‖∇f(0)‖)(f(0)-f*), so the gradient bounds and every convergence proof relying on Lemma 2 collapse.","rationale":"The reader identified the cited geometric bound 2G/L ≤ 2√2D in the accelerated proof as the weakest assumption. That bound is downstream of a more fundamental flaw: the self-bounding inequality of Lemma 2 is used in every algorithm's analysis to convert suboptimality gaps into gradient bounds. The proof of Lemma 2 depends on Lemma 1(i), which depends on Proposition 1's claim that F_ℓ ⊆ F_{ℓ~,r~} with r~(α)=G/ℓ(α+G). That claim requires the ball B(x, G/ℓ(‖∇f(x)‖_*+G)) to lie inside X. For bounded domains this is not a consequence of ℓ*-smoothness; the exponential example satisfies the definition, but the required ball extends outside X, and at the boundary-adjacent point x=0 the self-bounding inequality is violated. Consequently, G defined in (8) can be much smaller than ‖∇f(x0)‖_*, and the proofs' central step ‖x_{t+1}-x_t‖ ≤ G/L is unsupported. Since the paper's advertised setting includes bounded domains (Assumption 2), this is not a corner case. The fix would require adding an explicit assumption that the domain contains the local smoothness balls (or equivalently that the self-bounding inequality holds), which is absent. As written, the central claim is not proven; a major revision is needed. I therefore move the reader's CONDITIONAL verdict to REJECT.","tokens_in":52230,"tokens_out":15667,"duration_ms":159071,"concrete_test":"Evaluate Lemma 2 at x=0 for f(x)=e^{wx} on X=(-1,1) with ψ(x)=x²/2 and w=0.01: the left-hand side is w² = 1e-4; the right-hand side is 2·ℓ(2w)·(f(0)-f*) = 4w²(1-e^{-w}) ≈ 3.98e-6. Since 1e-4 > 3.98e-6, the claimed inequality fails. Also verify that the h chosen in the proof, h = -∇f(0)/ℓ(2‖∇f(0)‖_*) = -50, is not in X, so the domain-inclusion step breaks. This one-line numerical check settles whether Lemma 2 holds under the paper's assumptions.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 2 claims ‖∇f(x)‖_*² ≤ 2ℓ(2‖∇f(x)‖_*)(f(x)-f*) for every x∈X. The proof chooses v = u·‖∇f(x)‖_*/ℓ(2‖∇f(x)‖_*) and applies Lemma 1, which requires B(x, ‖∇f(x)‖_*/ℓ(2‖∇f(x)‖_*)) ⊆ X. This containment is not guaranteed by Assumptions 1–3. Counterexample: X=(-1,1), ψ(x)=x²/2, w=0.01, f(x)=e^{wx}. Then ℓ(α)=wα gives f∈F_ℓ, f(0)-f*=1-e^{-w}, ‖∇f(0)‖_*=w, ℓ(2w)=2w², so Lemma 2 would require w² ≤ 4w²(1-e^{-w}), i.e., 1 ≤ 4(1-e^{-w}), which is false for small w. Indeed, the vector -∇f(0)/ℓ(2‖∇f(0)‖_*) = -1/(2w) = -50 lies outside X, so the proof's step is not admissible. Proposition 1(ii), which implies B(0, G/ℓ(2G)) ⊆ X, is also false for this function. Lemma 2 is used through Lemma C.3 in Lemma D.2, Lemma F.2, Lemma G.2, and Lemma H.4 to bound all gradients; without it, G in (8) is not an upper bound on ‖∇f(x0)‖_*, and the local-smoothness reductions fail. Thus the central claim is not established for general bounded domains as stated.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces an ℓ*-smoothness condition for mirror descent in general normed spaces, replacing the Euclidean ℓ2-based generalized smoothness of Li et al. (2023a) by a Hessian bound measured with a primal-dual norm pair. It then claims O(1/T) rates for mirror descent, optimistic mirror descent and mirror prox, an O(1/T²) rate for accelerated mirror descent, and an anytime Õ(1/√t) high-probability rate for stochastic mirror descent under a generalized bounded noise assumption. The proof strategy centers on a generalized self-bounding inequality (Lemma 2), which is supposed to bound dual gradient norms by suboptimality gaps, and on a constant G defined in (8) from this inequality. The paper also presents dimension-dependent examples showing advantages of ℓ*-smoothness over ℓ-smoothness.","tokens_in":52653,"tokens_out":10298,"duration_ms":107808,"significance":"If the main claims were correct, the paper would be a useful step toward non-Euclidean generalized smoothness: the ℓ*-smoothness definition is natural, the local reduction to L-smooth analysis via G and L is elegant, and the dimension-dependent improvements in Appendix B are concrete and potentially relevant. The deterministic proof structure for mirror descent variants is detailed and contains several reusable lemmas, and the stochastic anytime result would improve on stopping-time analyses. However, the central self-bounding lemma is false on bounded domains under the stated assumptions, and all gradient-bound statements and convergence theorems rely on it. The abstract also promises non-convex and composite extensions that do not appear in the body, and the stochastic step size in (22) depends on quantities that the algorithm cannot observe. These issues are load-bearing rather than cosmetic.","major_comments":[{"comment":"Lemma 2 is false under Assumptions 1–3. Take X=[-1,1], ψ(x)=x²/2, f(x)=e^{wx} with w=0.01, and ℓ(α)=wα. Then f∈F_ℓ(∥·∥) with ∥·∥=|·|, and at x=0 we have ‖∇f(0)‖_*=w, ℓ(2w)=2w², and f(0)-f*=1-e^{-w}. Lemma 2 would require w² ≤ 4w²(1-e^{-w}), i.e. 1 ≤ 4(1-e^{-w}), which is false for small w. The proof of Lemma 2 chooses h = u·‖∇f(x)‖_*/ℓ(2‖∇f(x)‖_*) and applies Lemma 1, but for this example that vector has length 1/(2w)=50 and leaves the domain. Lemma 1(i) and Proposition 1(ii) only provide containment of a ball whose radius is controlled by G/ℓ(‖∇f(x)‖_*+G), not the larger radius needed here; the proof of Proposition 1(ii) itself assumes f diverges at the boundary, which is not implied by Assumption 1. Since Lemma C.3 and Lemmas D.2, F.2, G.2, and H.4 all use Lemma 2, the gradient bounds in Theorems 1–5 are not established. The manuscript needs either a repaired self-bounding argument under a suitable ball-containment or boundary-growth condition, or a restatement of the main theorems.","section":"Section 4.2, Lemma 2; Appendix C"},{"comment":"The step size schedule in (22) is not implementable as an algorithm: η_t is required to depend on ‖∇f(x_{t-1})‖_* and on σ(‖∇f(x_{t-1})‖_*), both of which are unknown to the learner. The theorem is therefore a statement about the existence of a step-size sequence rather than a convergence guarantee for a computable stochastic mirror descent method. Please either provide a step-size rule using only quantities available to the algorithm (e.g. stochastic gradient norms and computable bounds), or clearly state that the result is an existence/impossibility-style guarantee and explain why that is the intended contribution.","section":"Section 5.2, Eq. (22)"},{"comment":"The abstract states that the theory extends to non-convex and composite optimization, including pre-training and post-training of LLMs, but the body contains no non-convex results, no composite optimization results, and no LLM experiments or analysis. Section 7 also makes no mention of non-convex or composite settings. This claim should be removed or the corresponding results should be added.","section":"Abstract and Section 7"},{"comment":"The proof of Theorem 2 relies on the inequality 2G/L ≤ 2√2D, cited as Yu et al. (2024, Proposition A.6), to justify the time-partition argument in Lemma E.3. This is a nontrivial coupling between the link function ℓ, the initial gap, and the domain geometry, and it is load-bearing for the accelerated mirror descent result. Please state the precise version of this geometric inequality used here and prove it or give a complete reference with a proof; a citation alone is insufficient for this step, especially since G and L are defined through the new ℓ*-smoothness framework.","section":"Section 6.2, Eq. (108) and Lemma E.3"}],"minor_comments":[{"comment":"In the display after (188), the notation “(6)” appears to reference Assumption 2, but equation (6) is the bounded-domain assumption, not the bound on η_s²σ_s² used there; the reference should be corrected.","section":"Appendix H.2, proof of Lemma H.4"},{"comment":"The paper uses “open domain” in Assumption 1 while also requiring prox-mappings on X; the topological assumptions on X (open vs. closed, and whether boundary points are included for minimizers) should be stated consistently, since the counterexample in the major comments turns on this point.","section":"Throughout"},{"comment":"The theorem states Õ(1/√t) with constants hidden in eO notation, but the displayed rate contains expressions such as eLmax_{t-1} and σmax_{t-1} that depend on t; please clarify which of these are actually eO(1) under the proof's high-probability event before hiding them in the final rate.","section":"Section 5.2, Theorem 5"}],"recommendation":"major_revision","confidential_remarks":"The false Lemma 2 is the central issue: it invalidates the gradient bounds in every main theorem as stated. The paper can be repaired only by adding a genuinely new structural assumption (e.g., a ball containment or a valid self-bounding condition) and re-deriving the main results, or by substantially narrowing the scope. If the authors cannot provide such a repair while preserving the claimed applications, the paper should be rejected rather than published in its current form. The stochastic step-size feasibility problem and the unsupported abstract claims would also need to be addressed in any revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, here's my take on arXiv:2502.00753.\n\nThe new definition, ℓ*-smoothness, is a sensible dual-norm extension of Li et al. (2023a), and for deterministic convex problems the mirror descent, optimistic mirror descent, and mirror prox analyses are careful and give the expected O(1/T) rates. The dimension-dependent examples on the simplex are a nice touch. If the paper's gradient-control lemma were true, it would be a solid contribution.\n\nThe problem is that Lemma 2 is false for bounded domains. The proof needs the ball B(x, ||∇f(x)||_*/ℓ(2||∇f(x)||_*)) to lie in X, which Assumption 1 does not guarantee. The counterexample f(x)=e^{wx} on X=(-1,1) with ℓ(α)=wα satisfies the stated assumptions (it is differentiable, continuous on the open domain, and Hessian-bounded in the required sense) but fails Lemma 2 at x=0. The gradient bound then collapses, and with it the G used to define the step sizes and the local smoothness reductions in all four deterministic theorems. This is not a minor gap: the central convergence proofs are built on this lemma.\n\nThere are two more issues. The abstract promises extensions to non-convex and composite optimization, but the body only treats convex deterministic and stochastic cases; that should be corrected. And the stochastic step size in (22) uses ||∇f(x_{t-1})||_*, which the algorithm cannot observe, so the anytime bound is not practically implementable as stated. The cited geometric bound 2G/L ≤ 2√2D from Yu et al. (2024) is fine to rely on if the source is correct; I didn't find an issue there.\n\nThe stress-test's counterexample also exposes ambiguity in Assumption 1. If 'closed' means the epigraph is closed in the ambient space, then the paper's own examples like e^{w·x} on a ball are excluded. If it means lower semicontinuity on the open domain, Proposition 1(ii) and Lemma 2 fail. Either way the paper needs to fix its assumptions or its main lemma.\n\nWho should read this: anyone working on generalized smoothness. The ℓ*-smoothness framework is worth discussing, and the counterexample is instructive. But as it stands, the main theorems are not established.\n\nMy recommendation: send it to review, because the core idea and the deterministic analysis are worth the community's attention, but the referee should require a corrected Lemma 2 or an additional assumption that makes it true before acceptance.","headline":"A promising dual-norm generalization of smoothness, but the self-bounding lemma is false on bounded domains as stated, so the main convergence theorems are currently unsupported.","tokens_in":53172,"tokens_out":8991,"would_cite":false,"duration_ms":83605,"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":"deepseek-v4-flash","headline":"The paper introduces $\\ell^*$-smoothness for arbitrary norms and proves that mirror descent, accelerated mirror descent, and stochastic mirror descent all keep their classical convergence rates.","keywords":["mirror descent","generalized smoothness","self-bounding property","accelerated mirror descent","optimistic mirror descent","mirror prox","stochastic mirror descent","convex optimization"],"falsifier":"Run accelerated mirror descent (12) with the step-size prescription (13) on a convex function satisfying Assumptions 1–3 for which $2G/L > 2\\sqrt{2}D$, and check whether $T^2(f(x_T)-f^*)$ stays bounded as $T$ grows; if it diverges, the claimed $O(1/T^2)$ rate is false, and if it stays bounded, the cited geometric bound is not the true bottleneck.","tokens_in":52049,"feed_emoji":"📉","tokens_out":15915,"duration_ms":140791,"temperature":0.7,"pith_summary":"The paper asks whether generalized smoothness, in which the Hessian norm may grow with the gradient norm, can be used outside Euclidean geometry. It defines $\\ell^*$-smoothness, where $\\|\\nabla^2 f(x)h\\|_* \\le \\ell(\\|\\nabla f(x)\\|_*)\\|h\\|$ for a general norm and its dual, and claims that mirror descent, accelerated mirror descent, optimistic mirror descent, and mirror prox all recover their classical rates in this setting. A generalized self-bounding inequality turns bounded suboptimality gaps into bounded gradient dual norms, which is the key step that lets the analysis treat each function as locally $L$-smooth. If correct, the paper shows that the geometry of mirror descent and the flexibility of generalized smoothness are compatible, with no extra convergence-rate penalty.","feed_headline":"Mirror descent keeps classical rates under generalized smoothness","feed_subtitle":"A norm-aware smoothness condition restores classical mirror descent rates in non-Euclidean settings.","key_machinery":"The generalized self-bounding property (Lemma 2) is the central object: it controls $\\|\\nabla f(x)\\|_*$ through $f(x)-f^*$ and the link function $\\ell$, removing the need to track whether gradient dual norms decrease monotonically along a mirror descent trajectory. A companion local smoothness lemma upgrades $\\ell^*$-smoothness on a ball of radius $G/L$ to the familiar quadratic upper bound of an $L$-smooth function, and this reduction is what converts the mirror descent update inequalities into the classical telescoping arguments behind Theorems 1–5.","core_discovery":"The central claim is that $\\ell^*$-smoothness is the correct non-Euclidean analogue of the previous $\\ell$-smoothness condition, and that under it the standard mirror-descent family loses none of the rates available under ordinary $L$-smoothness: $O(1/T)$ for mirror descent, optimistic mirror descent, and mirror prox, $O(1/T^2)$ for accelerated mirror descent, and an anytime $\\widetilde{O}(1/\\sqrt{t})$ for stochastic mirror descent. The proof's engine is the generalized self-bounding inequality $\\|\\nabla f(x)\\|_*^2 \\le 2\\ell(2\\|\\nabla f(x)\\|_*)(f(x)-f^*)$, which bounds the gradient dual norm by the suboptimality gap. Combined with a local smoothness lemma, it turns $\\ell^*$-smoothness into ordinary $L$-smoothness on a small ball around each iterate, so classical Bregman-divergence arguments apply directly.","pith_inferences":["The paper's evidence is convex; a testable extension is to check whether the same self-bounding reduction yields anytime rates for stochastic accelerated mirror descent, which is not analyzed here.","If the cited geometric inequality $2G/L \\le 2\\sqrt{2}D$ fails for some valid function, the accelerated $O(1/T^2)$ theorem may still be true with a different coupling argument; the bound is a proof device rather than a demonstrated lower limit.","An empirical check of Assumption 4 on logistic-type losses is to scatter-plot noise norms against gradient norms; polynomial growth would confirm the model, while super-polynomial scatter would fall outside it.","The proof never uses the Euclidean inner product, so the same machinery should transfer to Bregman proximal algorithms and mirror maps with explicit dual structure, where dimension constants can disappear."],"forward_implications":["Mirror descent converges at $O(1/T)$ for both the average iterate and the last iterate under $\\ell^*$-smoothness, matching the classical convex rate.","Accelerated mirror descent converges at $O(1/T^2)$, the optimal rate for first-order convex optimization, with a last-iterate guarantee.","Optimistic mirror descent and mirror prox each converge at $O(1/T)$ in the average iterate, with the usual one- versus two-gradient-query trade-off.","Stochastic mirror descent attains an anytime high-probability rate of $\\widetilde{O}(1/\\sqrt{t})$ under a generalized bounded noise condition that includes bounded and affine noise as special cases.","Choosing a norm adapted to the problem, such as the $\\ell^1$ norm on the simplex, can shrink the effective link function by dimension-dependent factors and improve the convergence constants."],"supporting_citations":[{"why":"introduces the $\\ell$-smoothness class and self-bounding template that $\\ell^*$-smoothness generalizes.","marker":"Li et al. (2023a)"},{"why":"introduces $(L_0,L_1)$-smoothness, the motivating case where local smoothness grows with the gradient norm.","marker":"Zhang et al. (2020b)"},{"why":"defines mirror descent and the Bregman-divergence framework used throughout.","marker":"Beck and Teboulle (2003)"},{"why":"supplies the accelerated mirror descent update analyzed in Theorem 2.","marker":"Lan (2020)"},{"why":"supplies the mirror prox update and prox-mapping inequalities used in Theorems 3 and 4.","marker":"Nemirovski (2004)"},{"why":"provides the average-iterate-to-last-iterate conversion behind the stochastic anytime bound.","marker":"Orabona (2020)"},{"why":"provides the geometric inequality $2G/L \\le 2\\sqrt{2}D$ cited in the accelerated mirror descent proof.","marker":"Yu et al. (2024)"},{"why":"defines classical $L$-smoothness and the optimal first-order rates the paper aims to match.","marker":"Nesterov et al. (2018)"}],"fun_headline_variants":["Mirror descent rates hold under generalized smoothness","Norm-aware smoothness preserves mirror descent rates","Generalized smoothness no barrier for mirror descent","ℓ*-smoothness keeps mirror descent classical rates","Mirror descent unchanged by non-Euclidean smoothness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The accelerated mirror descent proof leans on a geometric bound that ties the local radius where the function is smooth to the diameter of the domain measured by the Bregman divergence; the paper cites this bound rather than deriving it, and the gradient-bounding argument collapses if the coupling fails.","fun_headline_variants_meta":{"raw":{"variants":["Mirror descent rates hold under generalized smoothness","Norm-aware smoothness preserves mirror descent rates","Generalized smoothness no barrier for mirror descent","ℓ*-smoothness keeps mirror descent classical rates","Mirror descent unchanged by non-Euclidean smoothness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000275,"raw_usage":{"total_tokens":1648,"prompt_tokens":952,"completion_tokens":696,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":623}},"tokens_in":568,"tokens_out":696,"duration_ms":6229,"temperature":1.0,"reasoning_tokens":623,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T17:49:32.392352+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run accelerated mirror descent (12) with the step-size prescription (13) on a convex function satisfying Assumptions 1–3 for which $2G/L > 2\\sqrt{2}D$, and check whether $T^2(f(x_T)-f^*)$ stays bounded as $T$ grows; if it diverges, the claimed $O(1/T^2)$ rate is false, and if it stays bounded, the cited geometric bound is not the true bottleneck.","supporting_citations":[],"review_version":1}