Oracle Complexities of Augmented Lagrangian Methods for Nonsmooth Composite Optimization on a Compact Submanifold
提出了两种新的流形非精确增广拉格朗日方法，用于求解嵌入欧氏空间的紧子流形上的非光滑复合优化问题，在确定性和随机性设置下均取得了优于已知最优的预言机复杂度，并通过稀疏主成分分析和稀疏典型相关分析实验验证了有效性。
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 [Formula: see text] 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 [Formula: see text], which surpasses the best-known [Formula: see text] 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. Funding: K. Deng was supported by the National Natural Science Foundation of China [Grant 12401419]. Z. Wen was supported in part by the National Natural Science Foundation of China [Grants 12331010 and 12288101], and National Key Research and Development Program of China [Grant 2024YFA1012903]. J. Hu gratefully acknowledges support from Mass General Hospital [Fund 237799] under the supervision of Prof. Quanzheng Li during his appointment at MGH.