Pith. sign in

REVIEW 30 references

Mirror descent algorithms with logarithmic barriers

T0 review · reviewed 2026-08-28 · deepseek-v4-flash

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

Pith's one-line read Mirror descent and proximal mirror descent with logarithmic barriers achieve a tight O(log k / k) convergence rate when the optimum lies on the feasible boundary.

desk verdict The paper delivers a genuinely new O(log k / k) rate for mirror descent with log-barriers at boundary optima, but as printed Lemma 2 is false and the proof of Theorem 1 relies on a corrected version that is never stated. read the letter →

arxiv 2608.22834 v1 pith:6VNUI6EB submitted 2026-08-24 math.OC cs.LGcs.NAmath.NA

Alberto De Marchi , Yura Malitsky , Adrien B. Taylor This is my paper · ORCID
classification math.OCcs.LGcs.NAmath.NA
keywords descentmirroralgorithmslogarithmicmethodswhenadditionapplied
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

Optimization algorithms often use a mirror function to measure distance, and a popular family of mirror functions consists of logarithmic barriers that grow to infinity at the boundary of the feasible region. When the optimal solution lies exactly on that boundary, the standard distance term in the algorithm's error bound also becomes infinite, so the usual proof gives no rate of convergence. The authors show that a property of logarithmic barriers called exp-concavity can be exploited instead, yielding a rigorous O(log k / k) error after k steps for both mirror descent and its proximal variant.

The proof accumulates Bregman divergence terms between consecutive iterates and uses exp-concavity to bound a troublesome error term at every step. The paper also constructs a two-dimensional example showing that the logarithmic factor cannot be removed, so the rate is tight for the proximal method. For the relative smoothness setting, this yields the first quantitative guarantees for problems such as D-optimal design and Poisson inverse problems, where the optimum is typically on the boundary. A final section compares proximal mirror descent with interior-point methods in an idealized setting and finds that the proximal method pays an extra logarithmic factor in Newton-iteration complexity, while being applicable under weaker assumptions.

Extended reading notes

Core claim

Theorem 1 states that for iterates of proximal mirror descent with a ν-log-barrier, f(x_k) - f* is at most (⟨∇h(x0), x0 - x*⟩ + 2ν + (ν/4) log(A_k / A_1)) / A_k, where A_k = Σ_{i=1}^k α_i. If this claim is correct, constant-stepsize proximal mirror descent converges at the O(log k / k) rate even when the optimum lies on the boundary, and Theorem 3 shows this rate is tight up to constants.

Load-bearing premise

Assumption 2 in Section 2: for every stepsize α > 0 and every y ∈ ri(C), the Bregman subproblems min_{x∈S} {αf(x) + h(x) - ⟨∇h(y), x⟩} and min_{x∈S} {⟨α∇f(y) - ∇h(y), x⟩ + h(x)} admit minimizers, and solutions automatically lie in ri(C). The entire Lyapunov analysis of Lemma 3 and Theorem 1 collapses if these subproblems fail to have minimizers or if an iterate reaches the boundary, where h is infinite.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

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

No fitted parameters; ν is the barrier complexity constant treated as an input. The paper's rate is a theorem, not a fit. The main assumptions are exp-concavity, well-posedness, and relative smoothness for the MD variant.

assumptions (4)
  • domain assumption h is a ν-log-barrier of C, meaning ν-exp-concavity and h tending to +∞ on the boundary
    This is the central structural assumption in Section 2; Theorems 1 and 3 invoke exp-concavity through Lemma 1.
  • domain assumption Assumption 2: Bregman subproblems in (MD) and (proxMD) admit minimizers in ri(C) for every stepsize
    Used in Lemma 3 to ensure iterates exist and the optimality condition (5) holds; see Section 2.
  • domain assumption f is L-relatively smooth with respect to h for the mirror descent result
    Definition 1 in Section 4.1; used in Lemma 4 and Theorem 2 to control f(x_{k+1}) - f(x_k).
  • standard math Max-of-affines and negation-log composition give convex f and 1-exp-concave h interpolation
    Used in Section 5 for the tightness construction; based on interpolation results from [22] and subdifferential calculus [12].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Mirror descent algorithms with logarithmic barriers." pith.science (2026). https://pith.science/paper/6VNUI6EB

@misc{pith2026260822834,
  author       = {Pith},
  title        = {Pith review of: Mirror descent algorithms with logarithmic barriers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6VNUI6EB}},
  note         = {Machine review of arXiv:2608.22834}
}
abstract

This work derives convergence guarantees for mirror descent and proximal mirror descent algorithms when a logarithmic barrier is used as a distance-generating function. Standard approaches cannot be applied when the solution lies on the boundary, where the Bregman divergence blows up. We show that, in a specific setting, both methods enjoy an $O(\log k / k)$ rate, which is also tight. In addition, our contributions include: (i) a new technique for handling the blow-up; (ii) a resolution of a gap in the theory of relative smoothness; and (iii) a comparison of the proposed approach with interior-point methods.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [5]

    De Marchi, Y

    A. De Marchi, Y. Malitsky, and A. B. Taylor. Mirror performance estimation with composed distance- generating functions, 2026. In preparation

    work page 2026

  2. [1]

    H. H. Bauschke, J. Bolte, and M. Teboulle. A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications.Mathematics of Operations Research, 42(2):330–348, 2017. doi:10.1287/moor.2016.0817

    work page arXiv 2017

  3. [2]

    Mirror descent and nonlinear projected subgradient methods for convex optimization

    A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimiza- tion.Operations Research Letters, 31(3):167–175, 2003. doi:10.1016/S0167-6377(02)00231-6

    work page doi:10.1016/s0167-6377(02)00231-6 2003

  4. [3]

    Birnbaum, N

    B. Birnbaum, N. R. Devanur, and L. Xiao. Distributed algorithms via gradient descent for Fisher markets. InProceedings of the 12th ACM conference on Electronic commerce, pages 127–136, New York, NY, USA,

    work page

  5. [4]

    Cipolla and J

    S. Cipolla and J. Gondzio. Proximal stabilized interior point methods and low-frequency-update pre- conditioning techniques.Journal of Optimization Theory and Applications, 197(3):1061–1103, 2023. doi:10.1007/s10957-023-02194-4

    work page doi:10.1007/s10957-023-02194-4 2023

  6. [6]

    Doljansky and M

    M. Doljansky and M. Teboulle. An interior proximal algorithm and the exponential multi- plier method for semidefinite programming.SIAM Journal on Optimization, 9(1):1–13, 1998. doi:10.1137/S1052623496309405

    work page doi:10.1137/s1052623496309405 1998

  7. [7]

    Dragomir.Bregman gradient methods for relatively-smooth optimization

    R.-A. Dragomir.Bregman gradient methods for relatively-smooth optimization. PhD thesis, UT1 Capitole,

    work page

  8. [8]

    Dragomir, A

    R.-A. Dragomir, A. B. Taylor, A. d’Aspremont, and J. Bolte. Optimal complexity and certification of Bregman first-order methods.Mathematical Programming, 194(1):41–83, 2022. doi:10.1007/s10107-021- 01618-1

    work page doi:10.1007/s10107-021- 2022

Show all 30 references
  1. [9]

    Drori and M

    Y. Drori and M. Teboulle. Performance of first-order methods for smooth convex minimization: a novel approach.Mathematical Programming, 145(1):451–482, 2014. doi:10.1007/s10107-013-0653-0

    2014 doi

  2. [10]

    Eckstein

    J. Eckstein. Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming.Mathematics of Operations Research, 18(1):202–226, 1993. doi:10.1287/moor.18.1.202

    1993 doi

  3. [11]

    J. Gondzio. Interior point methods in the year 2025.EURO Journal on Computational Optimization, 13:100105, 2025. doi:10.1016/j.ejco.2025.100105. 17

    2025

  4. [12]

    Hiriart-Urruty and C

    J.-B. Hiriart-Urruty and C. Lemar´ echal.Convex analysis and minimization algorithms I: Fundamentals, volume 305. Springer science & business media, 2013. doi:10.1007/978-3-662-02796-7

    2013 doi

  5. [13]

    H. Lu, R. M. Freund, and Y. Nesterov. Relatively smooth convex optimization by first-order methods, and applications.SIAM Journal on Optimization, 28(1):333–354, 2018. doi:10.1137/16M1099546

    2018 doi

  6. [14]

    R. D. Monteiro and B. F. Svaiter. On the complexity of the hybrid proximal extragradient method for the it- erates and the ergodic mean.SIAM Journal on Optimization, 20(6):2755–2787, 2010. doi:10.1137/090753127

    2010 doi

  7. [15]

    R. D. Monteiro and B. F. Svaiter. An accelerated hybrid proximal extragradient method for convex opti- mization and its implications to second-order methods.SIAM Journal on Optimization, 23(2):1092–1125,

  8. [16]

    A. S. Nemirovski and M. J. Todd. Interior-point methods for optimization.Acta Numerica, 17:191–234,

  9. [17]

    A. S. Nemirovskii and D. B. Yudin.Problem complexity and method efficiency in optimization. Wiley, New York, 1983. doi:10.1137/1027074

    1983 doi

  10. [18]

    Nesterov.Lectures on Convex Optimization, volume 137

    Y. Nesterov.Lectures on Convex Optimization, volume 137. Springer, 2nd edition, 2018. doi:10.1007/978- 3-319-91578-4

    2018 doi

  11. [19]

    R. Polyak. Modified barrier functions (theory and methods).Mathematical programming, 54(1):177–222,

  12. [20]

    Pougkakiotis and J

    S. Pougkakiotis and J. Gondzio. An interior point-proximal method of multipliers for convex quadratic programming.Computational Optimization and Applications, 78(2):307–351, 2021. doi:10.1007/s10589-020- 00240-9

    2021 doi

  13. [21]

    R. T. Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming.Mathematics of operations research, 1(2):97–116, 1976. doi:10.1287/moor.1.2.97

    1976 doi

  14. [22]

    A. B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods.Mathematical Programming, 161(1):307–345, 2017. doi:10.1007/s10107- 016-1009-3

    2017 doi

  15. [23]

    Teboulle

    M. Teboulle. Entropic proximal mappings with applications to nonlinear programming.Mathematics of Operations Research, 17(3):670–690, 1992. doi:10.1287/moor.17.3.670

    1992 doi

  16. [24]

    Teboulle and Y

    M. Teboulle and Y. Vaisbourd. An elementary approach to tight worst case complexity analysis of gradient based methods.Mathematical Programming, 201:63–96, 2023. doi:10.1007/s10107-022-01899-0

    2023 doi

  17. [25]

    Tseng and D

    P. Tseng and D. P. Bertsekas. On the convergence of the exponential multiplier method for convex pro- gramming.Mathematical Programming, 60(1):1–19, 1993. doi:10.1007/BF01580598. 18

    1993 doi

  18. [1992]

    doi:10.1007/BF01586050

    doi

  19. [2008]

    doi:10.1017/S0962492906370018

    doi

  20. [2011]

    doi:10.1145/1993574.1993594

    Association for Computing Machinery. doi:10.1145/1993574.1993594

  21. [2013]

    doi:10.1137/110833786

    doi

  22. [2021]

    URLhttps://inria.hal.science/tel-03389344

Pith tools

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