REVIEW 4 major objections 3 minor 2 cited by
Mirror Descent Under Generalized Smoothness
T0 review · 4 major / 3 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Section 4.2, Lemma 2; Appendix C] 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 5.2, Eq. (22)] 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.
- [Abstract and Section 7] 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 6.2, Eq. (108) and Lemma E.3] 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.
minor comments (3)
- [Appendix H.2, proof of Lemma H.4] 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.
- [Throughout] 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 5.2, Theorem 5] 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.
Circularity Check
No significant circularity: rates follow from derived constants and telescoping Bregman inequalities, not from assumptions equivalent to the conclusions.
full rationale
The paper's main derivation chain is self-contained in the relevant sense: the quantities G and L in (8) are defined from the problem data (the link function ℓ, the initial suboptimality gap f(x0)−f*, and the domain bound D), not fitted to the algorithm's outputs or to the claimed rates. Lemma 2 is presented as a consequence of Definition 1 and Lemma 1, and the subsequent gradient bounds are obtained by invoking Lemma 2 and the descent properties of the algorithms, so the convergence theorems are not merely restating their assumptions. The accelerated proof does rely on the self-cited geometric bound 2G/L ≤ 2√2D from Yu et al. (2024, Proposition A.6), and the stochastic proof similarly uses the cited diameter bound ∥x1−x2∥ ≤ 2√2D; however, these are auxiliary domain-geometry facts, not the paper's central smoothness-to-convergence equivalence, and they do not reduce any theorem to its own conclusion. No fitted parameter is relabeled as a prediction, and no uniqueness or ansatz result is imported to forbid alternatives. A separate possible correctness concern about Lemma 2 for bounded domains would be a flaw in the proof rather than a circularity, since the lemma is not assumed among the paper's hypotheses.
Assumptions & free parameters
free parameters (1)
- bL0, bL1, eL0, eL1 (affine smoothness-link fits) =
e.g., slope ratio eL1/bL1 ≈ 1.87 n^{-0.43} in Figure 2
assumptions (7)
- domain assumption Assumption 1: f is differentiable and closed on an open domain X.
- domain assumption Assumption 2: Bregman diameter of X is bounded by D².
- domain assumption Assumption 3: link function ℓ is non-decreasing, continuous, and sub-quadratic.
- domain assumption Assumption 4: noise satisfies ∥ϵt∥_* ≤ σ(∥∇f(xt)∥_*) almost surely for a polynomial σ.
- standard math Rademacher's theorem and a covering argument (via Li et al. 2023a, Proposition 3.2).
- standard math A generalized Gronwall inequality (Li et al., 2023a, Lemma A.3).
- domain assumption Geometric bound ∥x-y∥ ≤ 2√2D for x,y ∈ X, cited from Yu et al. (2024, Proposition A.6).
Cite this review
Pith. "Pith review of Mirror Descent Under Generalized Smoothness." pith.science (2026). https://pith.science/paper/KFWHDLGL
@misc{pith2026250200753,
author = {Pith},
title = {Pith review of: Mirror Descent Under Generalized Smoothness},
year = {2026},
howpublished = {\url{https://pith.science/paper/KFWHDLGL}},
note = {Machine review of arXiv:2502.00753}
}
abstract
Smoothness is crucial for attaining fast rates in first-order optimization. However, many optimization problems in modern machine learning involve non-smooth objectives. Recent studies relax the smoothness assumption by allowing the Lipschitz constant of the gradient to grow with respect to the gradient norm, which accommodates a broad range of objectives in practice. Despite this progress, existing generalizations of smoothness are restricted to Euclidean geometry with $\ell_2$-norm and only have theoretical guarantees for optimization in the Euclidean space. In this paper, we address this limitation by introducing a new $\ell*$-smoothness concept that measures the norm of Hessians in terms of a general norm and its dual, and establish convergence for mirror-descent-type algorithms, matching the rates under the classic smoothness. Notably, we propose a generalized self-bounding property that facilitates bounding the gradients via controlling suboptimality gaps, serving as a principal component for convergence analysis. Beyond deterministic optimization, we establish sharp convergence for stochastic mirror descent, matching state-of-the-art under classic smoothness. Our theory also extends to non-convex and composite optimization, which may shed light on practical usages of mirror descent, including pre-training and post-training of LLMs.
Figures
Forward citations
Cited by 2 Pith papers
-
Decentralized Stochastic Nonconvex Optimization under the $(L_0,L_1)$-Smoothness
DNSGD is a decentralized normalized stochastic gradient method for (L0,L1)-smooth nonconvex optimization, with complexity bounds that match standard smooth decentralized results when L1=0.
-
Open Problem: Is AdamW Effective Under Heavy-Tailed Noise?
The paper poses whether AdamW converges under heavy-tailed stochastic gradient noise and supplies a weighted-metric benchmark plus a corridor lower-bound showing how denominator memory can obscure large gradients.
Reference graph
Works this paper leans on
-
[1]
Finding solvable subproblems remains difficult
In practice, selecting a meaningful (L, h) is challenging even with complete problem infor- mation. Finding solvable subproblems remains difficult
-
[2]
exp(∥x∥2 2 /2). Thus the Hessian grows exponentially w.r.t.∥x∥2, render- ing polynomial-based characterization inadequate. However, since∥∇g(x)∥2 = ∥x∥2 exp(∥x∥2 2 /2), it follows that g is (0, ∥x∥2 +1)-smooth. Evidently, generalized smoothness can model this function class better than relative smoothness. Furthermore, the rest examples in Lu et al. (2018...
work page 2018
-
[3]
For real-world applications where only a first-order oracle of f is available (e.g., neural net- works), relative smoothness lacks an effective solution. In contrast, generalized smoothness remains applicable by empirically estimating the link function ℓ (Zhang et al., 2020b). Appendix B. The Gain of Algorithmic Adaptivity In this section, we present the ...
work page 2025
-
[4]
Invoke Rademacher’s Theorem (Evans, 2018) to show that f is twice differentiable almost everywhere within the ball B(x, r(∥∇f (x)∥∗))
work page 2018
-
[5]
Leverage the discretization as well as the covering technique to show that f is twice differen- tiable almost everywhere within the domain X . 41 YU JIANG WAN ZHANG Part 2. Under Assumption 1, Fℓ(∥·∥) ⊆ Feℓ,er(∥·∥) where eℓ(α) = ℓ(α + G), er(α) = G eℓ(α) for any G ∈ R++. First, we show that B(x, er(∥∇f (x)∥∗)) ⊆ Xfor any x ∈ Xby contradiction. For any ex ...
work page 2015
-
[6]
(bounded suboptimality gap) f (xt) − f ∗ ≤ f (x0) − f ∗
-
[7]
(bounded gradients) ∥∇f (xt)∥∗ ≤ G <∞, ∥∇f (yt)∥∗ ≤ 2G <∞
-
[8]
Proof We prove this lemma by induction
(bounded sequence) et ≤ G/L. Proof We prove this lemma by induction. Part 1. Base Case For t = 1, we clearly have y1 = z0 = x0 and thus ∥∇f (y1)∥∗ ≤ G. Also, we have ∥x1 − y1∥ = ∥z1 − z0∥ ≤η1 ∥∇f (z0)∥∗ ≤ G/(2L). In this scenario, the conditions of Lemma E.2 are satisfied, we immediately obtain η 2L [f (x1) − f (x0)] ≤ −B(z0, z1) ≤ 0, (107) by choosing x ...
work page 2024
Show all 13 references
-
[9]
(bounded suboptimality gap) f (yt) − f ∗ ≤ f (x0) − f ∗, f(xt) − f ∗ ≤ f (x0) − f ∗
-
[10]
(bounded gradients) ∥∇f (yt)∥∗ ≤ G <∞, ∥∇f (xt)∥∗ ≤ G <∞
-
[11]
Proof The proof resembles that of Lemma D.2, which involves induction
(tracking {yt}t∈N sequence) ∥yt − yt−1∥ ≤G L Pt s=1 γs ≤ γG (1−γ)L < G L . Proof The proof resembles that of Lemma D.2, which involves induction. For convenience, we denote L := ℓ(2G). Part 1. Base Case Consider the first round of (15). Similar to the proof of Lemma D.2, we ar...
2004
-
[12]
(descent property) f (xt) ≤ f (xt−1), f(yt) ≤ f (xt−1)
-
[13]
Proof We prove this lemma by induction
(bounded gradients) ∥∇f (yt)∥∗ ≤ G <∞, ∥∇f (xt)∥∗ ≤ G <∞. Proof We prove this lemma by induction. Part 1. Base Case We consider the case where t = 1. Similar to the proof of Lemma D.2, we argue that f (y0) − f ∗ = f (x0)−f ∗ < ∞. By Lemma 2, we have∥∇f (y0)∥∗ = ∥∇f (y0)∥∗ ≤ G ...
2023
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.