Abstract
In this paper, we present two novel manifold inexact augmented Lagrangian methods, ManIAL for deterministic settings and StoManIAL for stochastic settings, solving nonsmooth manifold optimization problems. By using the Riemannian gradient method as a subroutine, we establish an $\mathcal{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 $\tilde{\mathcal{O}}(\epsilon^{-3.5})$, which surpasses the best-known $\mathcal{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 nonsmooth manifold optimization problems.
Introduction
Many modern data science problems involve optimization on manifolds—mathematical spaces that locally resemble Euclidean space but possess a curved global structure, such as spheres or the set of orthogonal matrices. When these problems incorporate nonsmooth components, such as $L_1$ regularization for sparsity, they present significant computational challenges. While the Augmented Lagrangian Method (ALM) is a standard tool for constrained optimization in Euclidean space, its application to manifolds has historically lacked rigorous theoretical complexity guarantees or has resulted in suboptimal oracle complexities. This paper bridges this gap by introducing a manifold ALM framework with provable, state-of-the-art complexity bounds.
Proposed Algorithms: ManIAL and StoManIAL
The authors introduce two primary frameworks designed to handle the unique challenges of manifold constraints and nonsmooth objectives:
- ManIAL (Manifold Inexact Augmented Lagrangian): Designed for deterministic optimization. It handles nonsmoothness by transforming the problem into a sequence of smooth subproblems via the Moreau envelope. A key innovation is "Option II" for subproblem termination, which employs a fixed, geometrically increasing number of iterations ($2^k$) for the inner Riemannian Gradient Descent solver. This scheduling enables the algorithm to achieve optimal complexity without the logarithmic overhead typical in other proofs.
- StoManIAL (Stochastic ManIAL): Tailored for stochastic settings where the objective is an expectation. It integrates a modified Riemannian Stochastic Recursive Momentum (RSRM) method as the inner solver. This variance-reduction approach allows the algorithm to handle noisy gradients more efficiently than traditional subgradient methods.
Theoretical Breakthroughs and Complexity Analysis
The primary contribution of this work is the establishment of superior oracle complexities. As shown in the comparison table below, the proposed methods either match or exceed the performance of existing algorithms across various constraint types.
Specifically, ManIAL achieves an oracle complexity of $\mathcal{O}(\epsilon^{-3})$, matching the theoretical best for deterministic nonsmooth manifold problems. In the stochastic regime, StoManIAL achieves a complexity of $\tilde{\mathcal{O}}(\epsilon^{-3.5})$, a significant improvement over the previously best-known $\mathcal{O}(\epsilon^{-4})$. These results are made possible by two critical design choices: the geometric scheduling of inner iterations and the use of an adaptive dual step size ($\beta_k$) that ensures the boundedness of Lagrangian multipliers.
Experimental Validation
The researchers evaluated ManIAL and StoManIAL on Sparse Principal Component Analysis (SPCA) and Sparse Canonical Correlation Analysis (SCCA) using both synthetic data and real-world benchmarks like MNIST and COIL-100. Empirical results confirm the theoretical findings: StoManIAL converged significantly faster than the Riemannian subgradient method (Rsub). For instance, in SPCA tasks on the MNIST dataset, the proposed methods reached lower objective gaps in a fraction of the CPU time required by competitors.
Conclusion and Future Work
This work provides the first complexity results for augmented Lagrangian methods in the context of nonsmooth manifold optimization. By carefully balancing penalty parameters and subproblem accuracy, the authors have set new benchmarks for both deterministic and stochastic settings. While the current framework assumes a compact manifold, future research may explore extending these results to non-compact manifolds or integrating second-order methods to further accelerate local convergence.
Summary updated