Pith. sign in

REVIEW 2 major objections 3 minor 39 references

The paper claims that adaptive and non-adaptive mirror descent methods, splitting steps into productive and non-productive, solve non-smooth quasar-convex problems with convex inequality constraints in O(1/ε²) iterations, producing points t

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-02 14:00 UTC pith:ZGIUHFAS

load-bearing objection A useful deterministic extension of mirror descent to quasar-convex problems with functional constraints, but the adaptive stochastic convergence claims rest on an unjustified expectation step and need fixing. the 2 major comments →

arxiv 2607.22551 v1 pith:ZGIUHFAS submitted 2026-05-14 math.OC

Mirror Descent Methods for Quasar Convex Optimization Problems With Non-Smooth Inequality Constraints

Mohammad Alkousa This is my paper
classification math.OC MSC 90C2690C2590C15
keywords quasar convexitymirror descentnon-smooth optimizationfunctional constraintsstochastic optimizationadaptive step sizesproductive/non-productive stepsconvergence rates
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper claims that mirror descent—the non-Euclidean generalization of gradient descent—works for constrained optimization problems whose objective is not convex but quasar-convex, a weaker property that still captures several machine-learning objectives. The authors propose two families of algorithms, standard and modified, for both deterministic and stochastic settings, where each iteration is labelled productive if the current point is feasible within tolerance ε, and non-productive otherwise. They prove that all variants stop within O(Θ₀²M²(1+1/γ)²/ε²) iterations and return a point whose objective gap and constraint violation are both at most ε. If correct, this extends the classical ε-complexity of mirror descent from convex to quasar-convex objectives while respecting inequality constraints.

Core claim

The central claim is a transfer of the classical mirror-descent convergence rate from convex to quasar-convex objectives in the presence of non-smooth inequality constraints. The transfer works by classifying every iterate as productive, meaning g(x_k) ≤ ε, or non-productive, meaning g(x_k) > ε. On productive steps, the γ-quasar inequality lower-bounds the relevant inner product by γ(f(x_i) − f(x*)); on non-productive steps, convexity of the constraint lower-bounds it by g(x_i) − g(x*) > ε. Summing these charges with Bregman-divergence telescoping and an adaptive step size h_i = Θ₀(Σ_{j≤i} M_j²)^{-1/2} yields a bound that forces enough productive steps to make the best feasible iterate ε-opt

What carries the argument

The productive/non-productive ledger. Each iteration is labelled by feasibility: I collects iterates with g(x_k) ≤ ε, and J collects the rest. The proof lower-bounds the mirror-descent inner product ⟨∇_i, x_i − x*⟩ by γ(f(x_i) − f(x*)) on I and by g(x_i) − g(x*) > ε on J, then telescopes the Bregman potential V(x*, x_k) against the adaptive step size h_k = Θ₀(Σ M_i²)^{-1/2} (or the fixed h = γε/M² in the second group). The mirror map Mirr_x(h∇) converts each subgradient update into a controlled potential decrease, and the stopping rule is a threshold on cumulative squared subgradient norms designed so that |I| is forced large enough to absorb the constant Θ₀M/γ.

Load-bearing premise

The stochastic convergence theorems assume that the noise terms β_i, even after division by the random number of productive steps |I|, have zero expectation despite |I| being correlated with the same noise; if this cancellation is not valid, the adaptive stochastic rates do not follow.

What would settle it

Run Algorithm 3 on a one-dimensional problem with Q = [0,1], objective f(x) = 1−x (star-convex with γ = 1), constraint g(x) = x, and a stochastic constraint oracle whose noise has zero mean overall but nonzero mean on the random set of non-productive steps—for example, add a mean-zero random variable whose sign depends on whether g(x_k) > ε. Check whether the empirically averaged objective error at the advertised stopping time is ≤ ε. If the bound fails for small ε, the adaptive stochastic claim is false; if it holds, the proof needs a substitute for the unjustified E[β_i/|I|] = 0 step.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If the deterministic theorems are correct, any non-smooth γ-quasar-convex objective under a convex Lipschitz constraint inherits the O(1/ε²) oracle complexity of classical mirror descent, replacing convexity with the much weaker quasar inequality.
  • The stochastic variants claim the same rate using only unbiased bounded subgradient oracles, with no decreasing noise schedule and no variance-reduction mechanism.
  • The many-constraint modifications evaluate only one violated constraint per non-productive step, so the per-iteration cost of feasibility restoration no longer scales with the number of constraints m.
  • For machine-learning problems known to be quasar-convex—such as linear dynamical system identification, phase retrieval, and generalized linear models—the results give a first-order, constraint-aware method with a formal ε guarantee.
  • The stopping criterion is concrete: run until the cumulative squared subgradient norm crosses a threshold, then read off the best feasible iterate; no line search or tuned step size beyond Θ₀ and the Lipschitz constants is required.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The adaptive stochastic theorems hinge on a cancellation, E[Σ β_i/|I|] = 0, that is not automatic when |I| is the random number of productive steps and is correlated with the same noise that produces β_i; this is the natural place to probe the proof.
  • A plausible repair is to replace the adaptive stochastic step with the fixed step of the non-adaptive stochastic algorithm, whose proof avoids dividing by |I|; the paper itself notes that the adaptive variant in the second group cannot be analyzed stochastically, suggesting the same difficulty may be latent in the first group.
  • The productive/non-productive ledger is essentially a certificate that feasibility violations, not just objective suboptimality, are converted into drift; this template should extend to strongly quasar-convex objectives, which the paper names as future work, and to composite objectives with minimal changes.
  • If the noise-cancellation gap is real, Algorithm 3 should show systematic bias in the empirical objective error at small ε whenever early infeasible steps are frequent; this is directly checkable by simulation.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper studies mirror descent for minimizing a non-smooth γ-quasar-convex objective subject to non-smooth convex functional inequality constraints. It proposes two groups of algorithms based on switching between productive and non-productive steps. Group I consists of an adaptive deterministic mirror descent (Algorithms 1–2) and an adaptive stochastic version (Algorithms 3–4). Group II consists of an adaptive deterministic algorithm (Algorithms 4.1, 4.3), a non-adaptive deterministic algorithm (Algorithm 4.5), and a non-adaptive stochastic algorithm (Algorithm 4.7). The claimed results are O(ε^{-2}) iteration bounds and ε-solution guarantees, with expected objective error in the stochastic cases. The paper credits the algorithm designs to prior work and claims new convergence analyses, especially for quasar-convex objectives.

Significance. If the stochastic adaptive convergence results were valid, the paper would meaningfully extend the mirror-descent-with-functional-constraints framework of [4] to a class of non-convex (quasar-convex) objectives. Some parts are solid: the deterministic Group II proofs (Theorems 4.2, 4.4, 4.6) are largely coherent, and the non-adaptive stochastic proof (Theorem 4.8) uses a legitimate expectation argument because the stopping time is not present in the denominator of the noise term. The paper is also honest in §4.4 that adaptive stochastic convergence is not evident for its Group II algorithm. However, the two central adaptive stochastic theorems (Theorems 3.5 and 3.6) contain a load-bearing expectation error, and the deterministic adaptive proof has a small-ε gap. These issues leave the paper's main contribution—stochastic adaptive mirror descent for quasar-convex constrained problems—unsupported as written.

major comments (2)
  1. [§3.3–3.4, Theorems 3.5/3.6, Eqs. (3.44)–(3.56)]
  2. [§3.1–3.2, Theorems 3.1/3.3, Eqs. (3.13)–(3.16)]
minor comments (3)
  1. [§3.3]
  2. [§4.2]
  3. [§4.3–4.4]

Circularity Check

0 steps flagged

No significant circularity: the claimed convergence is derived from standard mirror-descent inequalities and explicit external lemmas, not from a self-referential construction or fitted parameter.

full rationale

The paper's derivation chain is not circular. The algorithms are credited to prior work ([36], [28], [1]) and the convergence proofs proceed by pathwise summation of the Bregman-divergence inequality (Lemmas 2.2 and 3.4) followed by the stopping rule; no parameter is fitted to the target quantity, and the output's feasibility g(hat x) <= epsilon is by selection, not by a constructed identity. The author's self-citations ([1], [28], [29], [30], [31], [34], [35]) appear as algorithm credits and related-work pointers and do not carry the load of the central theorems. The only external result that is load-bearing in the stochastic adaptive proofs, 'since Σ E[β_i/|I|]=0 (see [5])', is not a self-citation and is a martingale-type cancellation claim, not a restatement of the theorem being proved. Whether that cancellation is valid when |I| is a random future-dependent count is a genuine correctness concern, and Section 4.4 flags the same difficulty for Algorithm 4.1 by stating 'Unfortunately, it is not evident how to prove convergence for a stochastic version of the adaptive Algorithm 4.1.' Such an admitted limitation is evidence against circularity: the paper does not obtain its stochastic adaptive claim by defining the target into existence, but by invoking an external lemma that may or may not apply. Thus no circular step is exhibited; the correct verdict is no significant circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No fitted constants or invented entities. The paper's free inputs are the standard function-class parameters (γ, M_f, M_g, Θ0). The main unverified load-bearing assumption is the stochastic noise-cancellation lemma cited to [5].

axioms (5)
  • domain assumption The objective f is γ-quasar convex with known γ∈(0,1] (Definition 2.1)
    Central function class; all theorems assume it.
  • domain assumption f and g are Lipschitz with known bounds M_f, M_g, and stochastic subgradients are unbiased and a.s. bounded ((2.5)-(2.6), (3.27)-(3.28))
    Used for step sizes, stopping rules, and boundedness of norm sums.
  • domain assumption Bregman divergence is uniformly bounded: sup_{x,y∈Q} V(y,x) ≤ Θ0² (2.7)
    Needed to bound telescope sums in every convergence proof.
  • domain assumption Feasibility in the interior: exists x0∈Q° with g(x0)≤0 (Section 2)
    Slater-type condition ensures constraint steps are meaningful and g(x*)≤0.
  • ad hoc to paper E[ Σ_i β_i / |I| ] = 0, as asserted from [5] in Theorems 3.5/3.6
    Load-bearing step in the stochastic adaptive proofs; not stated or proven in this paper, and the randomness of |I| makes it non-obvious.

pith-pipeline@v1.3.0-alltime-deepseek · 21724 in / 18656 out tokens · 148206 ms · 2026-08-02T14:00:30.956710+00:00 · methodology

0 comments
read the original abstract

In this paper, we consider constraint optimization problems subject to non-smooth convex functional (inequality-type) constraints, wherein the objective function is non-smooth and quasar convex. We propose and analyze two groups of algorithms, each consisting of a standard version and a modified variant, that operate by switching between two types of iteration points: productive and non-productive. Within each group, we develop distinct mirror descent-type algorithms for both deterministic and stochastic settings, and we establish their convergence rates.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 4 canonical work pages

  1. [1]

    Alkousa, M.S. (2020). On Modification of an Adaptive Stochastic Mirror Descent Algorithm for Convex Optimization Problems with Functional Constraints. In: Zei- dan, D., Padhi, S., Burqan, A., Ueberholz, P. (eds) Computational Mathematics and Applications. Forum for Interdisciplinary Mathematics. Springer, Singapore. https://doi.org/10.1007/978-981-15-8498-5_3

    doi:10.1007/978-981-15-8498-5_3 2020

  2. [2]

    On some stochastic mirror descent methods for constrained online op- timization problems

    Alkousa M.S. On some stochastic mirror descent methods for constrained online op- timization problems. Computer Research and Modeling, 2019, vol. 11, no. 2, pp. 205-217.https://doi.org/10.20537/2076-7633-2019-11-2-205-217

    work page doi:10.20537/2076-7633-2019-11-2-205-217 2019

  3. [3]

    Ahookhosh, J

    M. Ahookhosh, J. de Brito, A. Kabgani, F. Lara, and J. Yuan, Quasar-convex op- timization: Fundamental properties and high-order proximal-point methods, arXiv: 2604.26735, (2026)

    Pith/arXiv arXiv 2026

  4. [4]

    Bayandina, P

    A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin, A. Titov: Mirror descent and convex optimization problems with non-smooth inequality constraints. In: Large- Scale and Distributed Optimization, Springer, Cham pp. 181–213, 2018

    2018

  5. [5]

    Bayandina: Adaptive Stochastic Mirror Descent for Constrained Optimization

    A. Bayandina: Adaptive Stochastic Mirror Descent for Constrained Optimization. 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V. F. Demyanov) (CNSA), pp. 40–43, 2017

    2017

  6. [6]

    Ben-Tal, A

    A. Ben-Tal, A. Nemirovski: Robust truss topology design via semidefinite program- ming. SIAM J. Optim. 7(4), 991–1016 (1997)

    1997

  7. [7]

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

    2010

  8. [8]

    de Brito, F

    J. de Brito, F. Lara, and D. Liu, Extending linear convergence of the proximal point algorithm: The quasar-convex case, arXiv preprint arXiv:2509.04375, (2025)

    Pith/arXiv arXiv 2025

  9. [9]

    T. T. Doan, S. Bose, D. H. Nguyen, C. L. Beck: Convergence of the Iterates in Mirror Descent Methods. IEEE Control Systems Letters,3(1), pp. 114–119, 2019. 29

    2019

  10. [10]

    A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip

    Mathieu Even, Raphael Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massouli´ e, and Adrien Taylor. “A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip”. In: Advances in Neural Information Processing Systems. 2021, pp. 1–32

    2021

  11. [11]

    A. A. Farzin, Y.-M. Pun, P. Braun, and I. Shames, Minimisation of quasar-convex functions using random zeroth-order oracles, arXiv preprint arXiv:2505.02281, (2025)

    Pith/arXiv arXiv 2025

  12. [12]

    Fercoq, A

    O. Fercoq, A. Alacaoglu, I. Necoara, V. Cevher: Almost surely constrained convex optimization. Proceedings of the 36th International Conference on Machine Learning, PMLR 97, pp. 1910–1919, 2019

    1910

  13. [13]

    Uniform Convergence of Gradients for Non-Convex Learning and Optimization

    Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan. “Uniform Convergence of Gradients for Non-Convex Learning and Optimization”. In: Advances in Neural In- formation Processing Systems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr´ eal, Canada. 2018, pp. 8759–8770

    2018

  14. [14]

    Guminov, A

    S. Guminov, A. Gasnikov, and I. Kuruzov, Accelerated methods for weakly-quasi- convex optimization problems: S. guminov et al., Computational Management Sci- ence, 20 (2023), p. 36

    2023

  15. [15]

    Hardt, T

    M. Hardt, T. Ma, and B. Recht, Gradient descent learns linear dynamical systems, Journal of Machine Learning Research, 19 (2018), pp. 1–44

    2018

  16. [16]

    Hermant, J.-F

    J. Hermant, J.-F. Aujol, C. Dossal, and A. Rondepierre, Study of the behaviour of Nesterov accelerated gradient in a non convex setting: the strongly quasar convex case, arXiv preprint arXiv:2405.19809, (2024)

    arXiv 2024

  17. [17]

    Hinder, A

    O. Hinder, A. Sidford, and N. Sohoni, Near-optimal methods for minimizing star- convex functions and beyond, in Proceedings of Thirty Third Conference on Learn- ing Theory, J. Abernethy and S. Agarwal, eds., vol. 125 of Proceedings of Machine Learning Research, PMLR, 2020, pp. 1894–1938

    2020

  18. [18]

    On the convergence of first order methods for quasar-convex optimization

    Jin, Jikai. On the convergence of first order methods for quasar-convex optimization. arXiv:2010.04937 (2020)https://arxiv.org/abs/2010.04937

    Pith/arXiv arXiv 2010

  19. [19]

    arXiv:2605.08474v1https://arxiv.org/pdf/2605.08474v1

    Alireza Kabgani, Felipe Lara, Masoud Ahookhosh: Robust Learning Meets Quasar-Convex Optimization: Inexact High-Order Proximal-Point Methods. arXiv:2605.08474v1https://arxiv.org/pdf/2605.08474v1

    Pith/arXiv arXiv

  20. [20]

    Accelerated Mirror De- scent for Non-Euclidean Star-convex Functions

    Cl´ ement Lezane, Sophie Langer, and Wouter M Koolen. “Accelerated Mirror De- scent for Non-Euclidean Star-convex Functions”. In: arXiv preprint arXiv:2405.18976 (2024)

    Pith/arXiv arXiv 2024

  21. [21]

    G. Lan, Z. Zhou: Algorithms for stochastic optimization with functional or expecta- tion constraints. Comput Optim Appl 76, 461-–498 (2020)

    2020

  22. [22]

    J. C. Lee and P. Valiant, Optimizing star-convex functions, in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 603–614

    2016

  23. [23]

    arXiv:2510.01943v2https://arxiv.org/abs/2510.01943v2

    David Mart ´ ınez-Rubio: Smooth Quasar-Convex Optimization with Constraints. arXiv:2510.01943v2https://arxiv.org/abs/2510.01943v2

    Pith/arXiv arXiv

  24. [24]

    Cubic regularization of Newton method and its global performance

    Yurii Nesterov and Boris Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming 108 (2006), pp. 177–205

    2006

  25. [25]

    Nemirovskii: Efficient methods for large-scale convex optimization problems

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

    1979

  26. [26]

    Nemirovsky, D

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

    1983

  27. [27]

    Polyak: A general method of solving extremum problems

    B. Polyak: A general method of solving extremum problems. Soviet Mathematics Doklady. 1967. Vol. 8, No. 3. P. 593–597 (in Russian)

    1967

  28. [28]

    S., Alkousa, M

    Stonyakin, F. S., Alkousa, M. S., Stepanov, A.N., and Barinov, M.A., Adaptive Mirror Descent Algorithms in Convex Programming Problems with Lipschitz Constraints, Trudy Inst. Mat. i Mekh. UrO RAN, 2018, vol. 24, no. 2, pp. 266–279 (Russian)

    2018

  29. [29]

    F. S. Stonyakin, M. S. Alkousa, A. N. Stepanov, M. A. Barinov: Adaptive mirror de- scent algorithms in convex programming problems with Lipschitz constraints. Trudy 30 Instituta Matematiki i Mekhaniki UrO RAN, 2018, Volume 24, Number 2, Pages 266–279

    2018

  30. [30]

    F. S. Stonyakin, M. Alkousa, A. N. Stepanov, A. A. Titov: Adaptive Mirror Descent Algorithms for Convex and Strongly Convex Optimization Problems with Functional Constraints. J. Appl. Ind. Math. 13, 557–574 (2019)

    2019

  31. [31]

    Stonyakin, F.S., Alkousa, M.S., Titov, A.A., Piskunova, V.V. (2019). On Some Meth- ods for Strongly Convex Optimization Problems with One Functional Constraint. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science, vol 11548. Springer, Cham.https://doi.org...

    work page doi:10.1007/978-3-030-22629-9_7 2019

  32. [32]

    Shpirko, Yu

    S. Shpirko, Yu. Nesterov: Primal-dual subgradient methods for huge-scale linear conic problem. SIAM J. Optim. 24(3), 1444–1457 (2014)

    2014

  33. [33]

    Shor N. Z. Generalized gradient descent with application to block programming. Kibernetika. 1967. Vol. 3, No. 3. P. 53–55

    1967

  34. [34]

    On some mirror descent methods for strongly convex programming problems with Lipschitz functional constraints

    O. S. Savchuk, M. S. Alkousa, F. S. Stonyakin, “On some mirror descent methods for strongly convex programming problems with Lipschitz functional constraints”, Computer Research and Modeling, 16:7 (2024), 1727–1746.https://doi.org/10. 20537/2076-7633-2024-16-7-1727-1746

    2024

  35. [35]

    Titov, A.A., Stonyakin, F.S., Gasnikov, A.V., Alkousa, M.S. (2019). Mirror Descent and Constrained Online Optimization Problems. In: Evtushenko, Y., Ja´ cimovi´ c, M., Khachay, M., Kochetov, Y., Malkova, V., Posypkin, M. (eds) Optimization and Ap- plications. OPTIMA 2018. Communications in Computer and Information Science, vol 974. Springer, Cham.https://...

    work page doi:10.1007/978-3-030-10934-9_5 2019

  36. [36]

    Valdivia Viscarra, O.S., Stonyakin, F. (2026). On the Convergence of First-Order Methods for Quasar Convex Functions. In: Olenev, N., Evtushenko, Y., Ja´ cimovi´ c, M., Khachay, M., Malkova, V. (eds) Optimization and Applications. OPTIMA 2025. Lecture Notes in Computer Science, vol 16426. Springer, Cham.https://doi.org/ 10.1007/978-3-032-15791-1_7

    work page doi:10.1007/978-3-032-15791-1_7 2026

  37. [37]

    C. Wang, Q. Ye, P. Luo, N. Ye, and L. Fu, Robust capped L1-norm twin support vector machine, Neural Networks, 114 (2019), pp. 47–59

    2019

  38. [38]

    Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization

    Jun-Kun Wang and Andre Wibisono. “Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization”. In: The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenRe- view.net, 2023

    2023

  39. [39]

    Xu: Primal-dual stochastic gradient method for convex programs with many func- tional constraints

    Y. Xu: Primal-dual stochastic gradient method for convex programs with many func- tional constraints. SIAM Journal on OptimizationVol. 30, Iss. 2 (2020) (M. S. Alkousa)Innopolis University, Russia. Email address:m.alkousa@innopolis.ru

    2020