改进镜面下降算法在边界解情况下的收敛性，实现对数级速率
Mirror descent algorithms with logarithmic barriers
- 用对数障碍函数替代传统距离生成函数
- 在边界点仍保持O(log k / k)收敛速率且紧致
- 适合优化含边界约束的凸问题研究者
本文为镜面下降及近端镜面下降算法在使用对数障碍函数作为距离生成函数时提供收敛性保证。传统方法在解位于边界时失效，因Bregman散度发散。本文证明，在特定设定下，两种方法均达到O(log k / k)的收敛速率，且该速率紧致。贡献包括：(i) 处理发散问题的新技术；(ii) 解决相对光滑性理论中的一个空白；(iii) 将所提方法与内点法进行比较。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。