Mirror descent algorithms with logarithmic barriers
Alberto De Marchi, Yura Malitsky, Adrien B. Taylor
math.OC cs.LG math.NA
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.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.