Oracle Complexities of Augmented Lagrangian Methods for Nonsmooth Composite Optimization on a Compact Submanifold

• 成果类型: Article; Early Access
• 署名作者: Deng, Kangkang; Hu, Jiang; Wu, Jiayuan; Wen, Zaiwen
• 署名单位: National University of Defense Technology - China; Tsinghua University; Peking University; Peking University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0498
• 发表日期: 2025
• 关键词: iteration-complexity; algorithm

摘要

In this paper, we present two novel manifold inexact augmented Lagrangian methods, ManIAL for deterministic settings and StoManIAL for stochastic settings, solving non-smooth composite optimization problems on a compact submanifold embedded in the Euclidean space. By using the Riemannian gradient method as a subroutine, we establish an O(epsilon-3) oracle complexity result of ManIAL, matching the best-known complexity result. Our algorithm relies on the careful selection of penalty parameters and the precise control of termination criteria for subproblems. Moreover, for cases where the smooth term follows an expectation form, our proposed StoManIAL utilizes a Riemannian recursive momentum method as a subroutine and achieves an oracle complexity of O(epsilon-3:5), which surpasses the best-known O(epsilon-4) result. Numerical experiments conducted on sparse principal component analysis and sparse canonical correlation analysis demonstrate that our proposed methods outperform an existing method with the previously best-known complexity result. To the best of our knowledge, these are the first complexity results of the augmented Lagrangian methods for solving non-smooth manifold optimization problems.