Mirror descent algorithms with logarithmic barriers
2026-08-24 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how two algorithms called mirror descent and proximal mirror descent behave when using a special tool called a logarithmic barrier, which helps keep solutions within certain limits. Normally, it's hard to prove these algorithms work well near the edge of the allowed area because some math parts become infinite. The authors show that under certain conditions, these algorithms still improve at a measured, predictable rate. They also develop a new way to handle the tricky infinite parts, fix a known problem in the theory, and compare their methods to other established techniques called interior-point methods.
mirror descentproximal mirror descentlogarithmic barrierBregman divergenceconvergence raterelative smoothnessinterior-point methodsoptimization algorithmsboundary solutions
Authors
Alberto De Marchi, Yura Malitsky, Adrien B. Taylor
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.