Mirror descent algorithms with logarithmic barriers

DOI10.48550/arXiv.2608.22834MaRDI QIDQ7285004arXivFDO

Authors Yura Malitsky, Adrien B. Taylor, Alberto De Marchi

Publication date 24 August 2026

Published in arXiv

Tldr We derive convergence guarantees for mirror descent and proximal mirror descent algorithms with logarithmic barriers as distance-generating functions, resolving a long-standing issue in optimization literature where standard approaches break down at the boundary. Our key contribution is an O(log k / k) rate, which is also tight in a specific setting, using a new technique to handle blow-up of Bregman divergence and resolving a gap in relative smoothness theory.

Full work available at URL https://doi.org/10.48550/arXiv.2608.22834

arXiv classification

cs.LGmath.NAmath.OC

Cites work

• A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
• An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
• An elementary approach to tight worst case complexity analysis of gradient based methods
• An interior point-proximal method of multipliers for convex quadratic programming
• An Interior Proximal Algorithm and the Exponential Multiplier Method for Semidefinite Programming
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Entropic Proximal Mappings with Applications to Nonlinear Programming
• Interior point methods in the year 2025
• Interior-point methods for optimization
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Modified barrier functions (theory and methods)
• Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
• On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
• On the convergence of the exponential multiplier method for convex programming
• Optimal complexity and certification of Bregman first-order methods
• Performance of first-order methods for smooth convex minimization: a novel approach
• Relatively smooth convex optimization by first-order methods, and applications
• Smooth strongly convex interpolation and exact worst-case performance of first-order methods

This page was built for publication: Mirror descent algorithms with logarithmic barriers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7285004)