Mirror descent algorithms with logarithmic barriers

When solving convex optimization problems where the feasible set features a complicated constraint region, researchers frequently employ mirror descent and proximal mirror descent algorithms. To enforce domain constraints, these methods often use a logarithmic barrier as a distance-generating function that defines the underlying Bregman divergence. A major theoretical hurdle has persisted for decades: standard analyses break down when the true optimal solution lies on the relative boundary of the constraint set, causing the Bregman divergence and classical convergence bounds to blow up to infinity. This paper investigates whether rigorous convergence guarantees can still be established for mirror descent and proximal mirror descent under logarithmic barriers when solutions reside on the boundary.

The authors develop a novel analytical technique to bypass the boundary blow-up issue by leveraging the exp-concavity property of logarithmic barriers rather than relying solely on standard convexity. By formulating specialized Lyapunov functions and properly accumulating terms across iterations, the authors establish rigorous convergence rates for both proximal mirror descent and standard mirror descent under relative smoothness. They analyze different stepsize schedules, including constant stepsizes and geometric stepsize strategies, and compare the Bregman proximal perspective with classical interior-point methods.

The paper proves that both proximal mirror descent and mirror descent attain a sublinear convergence rate of O(log k / k), which the authors further demonstrate to be tight. This resolves a long-standing gap in the theory of relative smoothness, providing the first quantitative convergence guarantees for mirror descent in settings such as D-optimal design and Poisson linear inverse problems. Furthermore, the analysis clarifies that proximal mirror descent can serve as a direct, principled alternative to interior-point methods.