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 $\mathcal{O}({ϵ}^{-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 $\tilde{\mathcal{O}}({ϵ}^{-3.5})$, which surpasses the best-known $\mathcal{O}({ϵ}^{-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.

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.