Lipschitz-Free Mirror Descent Methods for Non-Smooth Optimization Problems

Bowen Yuan; Mohammad S. Alkousa

REVIEW 3 major objections 3 minor 15 references

Lipschitz-Free Mirror Descent Methods for Non-Smooth Optimization Problems

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Mirror descent reaches the optimal $O(1/\sqrt{N})$ rate without assuming the objective is Lipschitz.

desk verdict A valid correction to the Nesterov step-size analysis and a useful Lipschitz-free mirror descent extension, with a fixable index typo in the central proof. read the letter →

arxiv 2506.01681 v1 pith:P27MOVNF submitted 2025-06-02 math.OC

Bowen Yuan , Mohammad S. Alkousa This is my paper

classification math.OC MSC 90C2590C30

keywords mirrordescentweakergodicconvergencetime-varyingstepsizeLipschitz-freeoptimizationnonsmoothconvexoptimalrateBregmandivergencecomposite

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that mirror descent can achieve the optimal $O(1/\sqrt{N})$ convergence rate for nonsmooth convex optimization even when no Lipschitz constant for the objective is known or assumed. It first points out a flaw in an earlier adaptive step-size analysis: the Nesterov-type rule $\gamma_k=\sqrt{2\sigma}/(\|\nabla f(x_k)\|_*\sqrt{k})$ is not necessarily non-increasing, and a one-dimensional quadratic example shows the failure. The correction replaces that rule with $\gamma_k=\sqrt{2\sigma R}/(G_k k^{a/2})$, where $G_k$ is the running maximum of the observed subgradient norms scaled by $k^{(1-a)/2}$, which is non-increasing by construction. On the averaged weak-ergodic iterate, the method satisfies $f(\bar x)-f(x^*)\le 3\sqrt{R/(2\sigma)}\,N^{-1/2}\max_{k\le N}\|\nabla f(x_k)\|_*$, so the usual optimal rate survives with the maximum observed subgradient norm in place of a global Lipschitz bound. The same treatment is extended to composite objectives, where the separable nonsmooth term contributes only an $O(1/N)$ term.

What carries the argument

The key object is the weak ergodic weighting scheme, which averages the iterates with weights instead of taking the last iterate, combined with a running-max step-size rule. Define $G_k=\max_{j\le k}\|\nabla f(x_j)\|_* j^{(1-a)/2}$ and $\gamma_k=\sqrt{2\sigma R}/(G_k k^{a/2})$; monotonicity holds by construction because $G_k k^{a/2}$ is non-decreasing. The proof telescopes the Bregman divergence terms $V_\psi(x^*,x_k)-V_\psi(x^*,x_{k+1})$ via the three-point identity and the non-Euclidean second prox theorem, bounding the cumulative sum by $R$, while the Fenchel-Young inequality turns the inner-product term into $\gamma_k\|\nabla f(x_k)\|_*^2/(2\sigma)$, which the running-max $G_k$ absorbs into the final maximum subgradient norm.

What would settle it

Run Algorithm 1 with $\psi(x)=x^2/2$, $R=0.2$, $a=0$, $m=0$, starting at $x_1=0.05$ on $f(x)=x\log x$ over $Q=[0,1]$, whose subgradients $f'(x)=\log x+1$ are unbounded near $x=0$ but whose projected iterates stay in the subdifferentiable region; for large $N$, compare $f(\bar x_N)-f(e^{-1})$ with $3\sqrt{0.2/2}\,N^{-1/2}\max_{k\le N}|f'(x_k)|$. A run where the empirical error exceeds the bound by a fixed margin would refute Corollary 1, while persistent agreement supports the claimed Lipschitz-free rate.

Watch

Extended reading notes

Core claim

The central claim is that the mirror descent update $x_{k+1}=\arg\min_{x\in Q}\{\langle x,\nabla f(x_k)\rangle+\gamma_k^{-1}V_\psi(x,x_k)\}$ achieves weak ergodic convergence at the optimal $O(N^{-1/2})$ rate for any convex continuous $f$, provided only that a finite bound $R$ on the Bregman divergence $V_\psi(x^*,x)$ over $Q$ is known. The step sizes are $\gamma_k=\sqrt{2\sigma R}/(G_k k^{a/2})$ with $G_k=\max_{j\le k}\|\nabla f(x_j)\|_* j^{(1-a)/2}$, and for the mean iterate $\bar x=(1/N)\sum_{k=1}^N x_k$ the paper proves $f(\bar x)-f(x^*)\le 3\sqrt{R/(2\sigma)}N^{-1/2}\max_{k\le N}\|\nabla f(x_k)\|_*$. This removes the bounded-subgradient (Lipschitz) assumption from the mirror descent convergence theory, and the proof also repairs the earlier claim that the Nesterov step sizes are non-increasing by constructing a step rule that is non-increasing by design.

Load-bearing premise

The step sizes require a known finite number $R$ that bounds the Bregman distance from the optimum to every feasible point, and if no such $R$ is available the method cannot be started as stated.

Editorial extensions

If this is right

With $m=0$, the arithmetic average of the iterates satisfies $f(\bar x)-f(x^*)\le 3\sqrt{R/(2\sigma)}N^{-1/2}\max_{k\le N}\|\nabla f(x_k)\|_*$, matching the optimal $O(N^{-1/2})$ rate using only observed subgradient norms.
For composite problems $\min f+h$, the bound becomes the same term plus $h(x_1)/N$, so the separable nonsmooth part does not degrade the main rate and the earlier requirement $h(x_1)=0$ is unnecessary.
Because no bounded-subgradient assumption is used, the method applies to convex functions whose subgradients grow without bound on the feasible set, as long as a known $R$ bounds the Bregman distance to the optimum.
The corrected step rule is adaptive and online: $G_k$ is computed from quantities available at iteration $k$, so neither a Lipschitz constant nor future information is needed.
The theorem covers any fixed $a\in[0,1]$ and any $m\ge -1$, giving a family of step-size and weighting choices with $m=0$ as the clean optimal-rate case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the maximum observed subgradient norm grows like $N^p$ along a run, the displayed bound degrades to $O(N^{p-1/2})$, so monitoring $G_k$ online would give a practical certificate of the rate actually attained.
The running-max construction is a generic repair for monotonicity failures of adaptive step rules, and the same idea could be carried over to other proximal or stochastic first-order methods that scale steps by per-iteration gradient norms.
Because the composite bound isolates the $h(x_1)/N$ term, a natural testable extension is to choose the starting point that minimizes $h$ alone, possibly obtaining a faster $O(1/N)$ tail for the nonsmooth component.
The paper leaves open whether the factor $\max_k\|\nabla f(x_k)\|_*$ is necessary; constructing a convex function where the observed maximum genuinely controls the error would show the bound is tight rather than merely convenient.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The paper does two solid things. First, it exposes a genuine flaw in Alkousa et al.'s adaptive step-size analysis: the Nesterov rule gamma_k = sqrt(2 sigma)/(||grad f(x_k)||_* sqrt(k)) is not necessarily non-increasing, and the convergence proof required non-increasing steps. The one-dimensional quadratic counterexample is clean and convincing. The proposed fix, replacing the instantaneous norm with a running maximum G_k, restores monotonicity and is correct.

Second, it extends Xia-Zhu-Zhang's Lipschitz-free projected subgradient result to mirror descent, and adds a composite-problem version. The telescoping argument is the standard one, and the bounds in (21) and (30) are the right generalizations. The composite result's O(1/N) term for h(x1) is a genuine extra. This is a solid extension, not a revolution.

The soft spots are real but manageable. The proof of Theorem 1 as printed misapplies Lemma 2: the displayed (13) and (14) have x* - x_k on the left, but the correct application of the prox theorem gives x* - x_{k+1} in both places. The stress-test note is right that (13) does not follow from the cited lemma as written. But the fix is purely index-based: swap the arguments, and the three-point identity yields exactly the intended inequality (15). The rest of the proof goes through unchanged. It is a typo, not a missing idea, though referees should insist on the correction. The same slip appears in the proof of Theorem 2.

Two further qualifications. The "Lipschitz-free" label is a bit generous: the final rate involves max_{k<=N} ||grad f(x_k)||_*, a trajectory-dependent quantity. For genuinely non-Lipschitz functions that max can grow, so this is not a standard fixed-constant O(1/sqrt(N)) guarantee. Also, the step rule (8) requires a known global bound R on the Bregman divergence from the optimum over Q. That is a different assumption from Lipschitz continuity, not no assumption. Both are stated explicitly, but they should temper the marketing.

Overall: the correction to [1] is valid, the extension is useful, and the flaws are typos and needed qualifications rather than load-bearing errors. I would send it to a serious referee, expecting minor revision.

Referee Report

3 major / 3 minor

Summary. The paper corrects an error in Alkousa et al. [1] concerning the monotonicity of the Nesterov step size for mirror descent, and extends the Lipschitz-free projected subgradient result of Xia et al. [13] to mirror descent. The main result, Theorem 1, states a weak ergodic convergence bound of order O(1/√N) up to the maximum observed subgradient norm, under step sizes (8) that depend on the running maximum of subgradient norms, without assuming Lipschitz continuity of the objective. A composite version is given in Theorem 2. The proof uses the standard mirror descent argument with a three-point identity and a telescoping sum, but the printed proof contains several typographical errors that obscure the argument.

Significance. If the proof is properly corrected, the paper provides a useful and modest generalization: it removes the Lipschitz assumption on the objective at the cost of a geometric bound on the Bregman divergence (Assumption 1), which for compact Q is automatically finite. The counterexample in Example 1 clearly demonstrates the non-monotonicity of the Nesterov step size (6), and the proposed modification (8) is a reasonable fix. The paper also correctly notes that the composite method can handle h(x1) ≠ 0, removing a restrictive condition in [1]. However, the central proof as printed is not verifiable, and the numerous subscript errors in the key equations require a careful rewrite.

major comments (3)

[Section 3.2, proof of Theorem 1, Eq. (13)] Equation (13) does not follow from Lemma 2 as stated. In Algorithm 1, x_{k+1} is the minimizer of φ(x) + V_ψ(x, x_k), so in Lemma 2 one must take b = x_k, a = x_{k+1}, not a = x_k, b = x_{k+1} as written. The resulting inequality is ⟨∇ψ(x_k) − ∇ψ(x_{k+1}), x* − x_{k+1}⟩ ≤ γ_k⟨∇f(x_k), x* − x_{k+1}⟩. Consequently, the left-hand sides of (13) and (14) must contain x* − x_{k+1} instead of x* − x_k. The subsequent combination leading to (15) is correct once these corrections are made, but as printed the displayed (13) is not a consequence of the cited lemma.
[Section 3.2, proof of Theorem 1, Eq. (20)] The telescoping sum in (20) contains incorrect indices. The difference term should be ω_k/γ_k − ω_{k−1}/γ_{k−1}, not ω_k/γ_k − ω_k/γ_{k−1}. In addition, the final negative Bregman term should be V_ψ(x*, x_{N+1}), not V_ψ(x*, x_N). As printed, the telescoping identity is invalid, although the correct version is readily recovered from (17) and (18).
[Section 4, proof of Theorem 2, Eq. (24)] The same misapplication of Lemma 2 as in (13) appears in (24). Since Algorithm 2 defines x_{k+1} as the minimizer of the prox objective, the first inner product should be ⟨∇ψ(x_k) − ∇ψ(x_{k+1}), x* − x_{k+1}⟩, not ⟨∇ψ(x_k) − ∇ψ(x_{k+1}), x* − x_k⟩. This error propagates into (25) and the rest of the proof. The correction is straightforward but necessary for the proof to be valid.

minor comments (3)

[Section 3.1, Assumption 1] For a compact set Q and a finite-valued prox-function ψ that is differentiable on Q, the Bregman divergence V_ψ(x*, x) is continuous and hence bounded; thus Assumption 1 is automatically satisfied for some finite R. The authors could state this observation explicitly to justify the assumption.
[Section 3.2, Corollary 1] The constant 3 in (22) follows from the estimate (N^{1/2} + ∑_{k=1}^N k^{-1/2})/N ≤ 3/N^{1/2}, but this step is not shown. A short justification would improve readability.
[Section 3.2, Eq. (21)] The algebra in the second half of (21) for the case m > 0 is quite compressed; the authors should expand the derivation, especially the step involving G_k^{-1} k^{(m-a)/2}.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the adaptive step-size bound is derived from textbook prox lemmas with an explicit bounded-divergence assumption; the self-citation to [1] is to the work being corrected and is not load-bearing.

full rationale

The derivation of Theorem 1 and Corollary 1 is self-contained and does not assume the target result. Assumption 1 (V_psi(x*,x) <= R) is a stated geometric input, not a consequence of the convergence inequality; the step sizes (8) are adaptive but are not fitted to the objective suboptimality, and the appearance of max_k ||grad f(x_k)||_* on the right-hand side of (22) is a path-dependent bound of an adaptive subgradient method, not a fitted parameter renamed as a prediction. The proof relies on Lemma 1 and Lemma 2 from Beck's textbook and the Fenchel-Young inequality, and it explicitly corrects [1] (Example 1) rather than importing [1]'s claims as support, so the self-citation via co-author Alkousa is not load-bearing. The legitimate concern in the manuscript is a proof-correctness gap, not a circularity: the printed (13) claims to follow from Lemma 2 with a=x_k, b=x_{k+1}, but in Algorithm 1 x_{k+1} is the minimizer in the second argument of V_psi, so Lemma 2 should be applied with the roles reversed. That is a substantive mathematical gap in the printed derivation, but it is not an instance of the theorem's conclusion being assumed, fitted, or obtained through a self-citation chain. No circular step is exhibited, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted parameters; the only user choices are a and m, over which the bounds are uniform. The algorithm is adaptive in the subgradient norms it observes. No invented entities.

assumptions (5)

domain assumption Assumption 1: V_psi(x*,x) <= R < infinity for all x in Q (existence of a known finite Bregman-radius bound).
Needed for the telescoping bound (20) and to define the step size (8); stated in Section 3.1.
domain assumption f is convex and continuous on Q, with subgradients available at every iterate.
Used for the subgradient inequality (12) and Jensen's inequality; continuity ensures subdifferentiability on the relative interior.
standard math psi is sigma-strongly convex, proper, closed, differentiable over dom(d psi), and psi + I_Q is sigma-strongly convex for the prox step.
Standard mirror descent framework, used in Lemma 2 and the strong convexity estimate (1).
domain assumption h is non-negative and convex in the composite problem.
Non-negativity is used to drop the telescoped h terms in (29); this is a real restriction.
standard math Bregman divergence, Fenchel-Young inequality, three-point identity, non-Euclidean second prox theorem.
Treated as established background from Beck 2017.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Lipschitz-Free Mirror Descent Methods for Non-Smooth Optimization Problems." pith.science (2026). https://pith.science/paper/P27MOVNF

@misc{pith2026250601681,
  author       = {Pith},
  title        = {Pith review of: Lipschitz-Free Mirror Descent Methods for Non-Smooth Optimization Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P27MOVNF}},
  note         = {Machine review of arXiv:2506.01681}
}

read the original abstract

The part of the analysis of the convergence rate of the mirror descent method that is connected with the adaptive time-varying step size rules due to Alkousa et al. (MOTOR 2024, pp. 3-18) is corrected. Moreover, a Lipschitz-free mirror descent method that achieves weak ergodic convergence is presented, generalizing the convergence results of the mirror descent method in the absence of the Lipschitz assumption.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

[1]

Alkousa, M., Stonyakin, F., Abdo, A., Alcheikh, M. (2024). Optimal Convergence Rate for Mirror Descent Methods with Special Time-Varying Step Sizes Rules. In: Ere- meev, A., Khachay, M., Kochetov, Y., Mazalov, V., Pardalos, P. (eds) Mathemat- ical Optimization Theory and Operations Research: Recent Trends. MOTOR 2024. Communications in Computer and Inform...

work page doi:10.1007/978-3-031-73365-9 2024
[13]

Y. Xia, Y. Zhang, Z. Zhu, Lipschitz-free Projected Subgradient Method with Time- varying Step-size, 2024. https://optimization-online.org/?p=27932. arXiv:2410.22336

work page arXiv 2024
[2]

Nemirovsky, A., Yudin D.: Problem Complexity and Method Efficiency in Optimization. J. Wiley & Sons, New York 1983

work page 1983
[3]

Ekonomika i Matematicheskie Metody, 1979

Nemirovskii, A.: Efficient methods for large-scale convex optimization problems. Ekonomika i Matematicheskie Metody, 1979. (in Russian)

1979
[4]

Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett., 31(3), pp. 167–175, 2003

work page 2003
[5]

IEEE Control Systems Letters, 3(1), pp

Doan, T.T., Bose, S., Nguyen, D.H., Beck, C.L.: Convergence of the Iterates in Mirror Descent Methods. IEEE Control Systems Letters, 3(1), pp. 114–119, 2019. Lipschitz-Free Mirror Descent Methods for Non-Smooth Optimization Problems 13

work page 2019
[6]

Operations Research Letters, 38(6), pp

Beck, A., Ben-Tal, A., Guttmann-Beck, N., Tetruashvili, L.: The comirror algorithm for solving nonsmooth constrained convex problems. Operations Research Letters, 38(6), pp. 493–498, 2010

work page 2010
[7]

SIAM Journal on Optimization, 12(1), pp

Ben-Tal, A., Margalit, T., Nemirovski, A.: The Ordered Subsets Mirror Descent Op- timization Method with Applications to Tomography. SIAM Journal on Optimization, 12(1), pp. 79–108, 2001

work page 2001

Show all 15 references

[8]

European Control Conference (ECC) June, pp

Nazin, A., Anulova, S., Tremba, A.: Application of the Mirror Descent Method to Min- imize Average Losses Coming by a Poisson Flow. European Control Conference (ECC) June, pp. 24–27, 2014

2014
[9]

Nesterov, Introductory lectures on convex optimization: A basic course, Springer Sci- ence & Business Media, 2004

Y. Nesterov, Introductory lectures on convex optimization: A basic course, Springer Sci- ence & Business Media, 2004

2004
[10]

Nesterov, Lectures on convex optimization, volume 137, Springer, 2018

Y. Nesterov, Lectures on convex optimization, volume 137, Springer, 2018

2018
[11]

Bubeck, Convex optimization: Algorithms and complexity

S. Bubeck, Convex optimization: Algorithms and complexity. Foundations and Trends Trends® in Machine Learning, 8(3-4): 231-357, 2015

2015
[12]

Z. Zhu, Y. Zhang, Y. Xia, Convergence rate of projected subgradient method with time- varying step-sizes, Optim Lett 19, 1027–1031 (2025). https://doi.org/10.1007/s11590- 024-02142-9

2025 doi
[14]

Society for Industrial and Applied Math- ematics, 2017

A.Beck, First-order methods in optimization. Society for Industrial and Applied Math- ematics, 2017

2017
[15]

Lan, First-order and Stochastic Optimization Methods for Machine Learning, Springer-Nature, 2020

G. Lan, First-order and Stochastic Optimization Methods for Machine Learning, Springer-Nature, 2020

2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Alkousa, M., Stonyakin, F., Abdo, A., Alcheikh, M. (2024). Optimal Convergence Rate for Mirror Descent Methods with Special Time-Varying Step Sizes Rules. In: Ere- meev, A., Khachay, M., Kochetov, Y., Mazalov, V., Pardalos, P. (eds) Mathemat- ical Optimization Theory and Operations Research: Recent Trends. MOTOR 2024. Communications in Computer and Inform...

work page doi:10.1007/978-3-031-73365-9 2024

[2] [13]

Y. Xia, Y. Zhang, Z. Zhu, Lipschitz-free Projected Subgradient Method with Time- varying Step-size, 2024. https://optimization-online.org/?p=27932. arXiv:2410.22336

work page arXiv 2024

[3] [2]

Nemirovsky, A., Yudin D.: Problem Complexity and Method Efficiency in Optimization. J. Wiley & Sons, New York 1983

work page 1983

[4] [3]

Ekonomika i Matematicheskie Metody, 1979

Nemirovskii, A.: Efficient methods for large-scale convex optimization problems. Ekonomika i Matematicheskie Metody, 1979. (in Russian)

1979

[5] [4]

Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett., 31(3), pp. 167–175, 2003

work page 2003

[6] [5]

IEEE Control Systems Letters, 3(1), pp

Doan, T.T., Bose, S., Nguyen, D.H., Beck, C.L.: Convergence of the Iterates in Mirror Descent Methods. IEEE Control Systems Letters, 3(1), pp. 114–119, 2019. Lipschitz-Free Mirror Descent Methods for Non-Smooth Optimization Problems 13

work page 2019

[7] [6]

Operations Research Letters, 38(6), pp

Beck, A., Ben-Tal, A., Guttmann-Beck, N., Tetruashvili, L.: The comirror algorithm for solving nonsmooth constrained convex problems. Operations Research Letters, 38(6), pp. 493–498, 2010

work page 2010

[8] [7]

SIAM Journal on Optimization, 12(1), pp

Ben-Tal, A., Margalit, T., Nemirovski, A.: The Ordered Subsets Mirror Descent Op- timization Method with Applications to Tomography. SIAM Journal on Optimization, 12(1), pp. 79–108, 2001

work page 2001