A Riemannian ADMM

Jiaxiang Li, Shiqian Ma, Tejes SrivastavaarXiv 2022 · OpenReview

TL;DR

This paper introduces a novel Riemannian Alternating Direction Method of Multipliers (RADMM) designed to efficiently solve optimization problems involving both smooth and nonsmooth functions on manifolds. This new algorithm offers easily computable steps and theoretical guarantees for finding approximate solutions, addressing a significant gap in existing ADMM methods that struggle with such combined challenges.

What Problem Does This Paper Address?

Many real-world problems in machine learning and statistics, such as sparse principal component analysis, sparse spectral clustering, and orthogonal dictionary learning, can be formulated as optimization problems with an objective function that is a sum of a smooth part and a nonsmooth part, all constrained to lie on a Riemannian manifold. Existing optimization methods, including ADMM, often fail when faced with this combination: standard ADMM struggles with nonconvex constraints (like manifolds), while other ADMM variants either don't handle nonsmooth objectives or don't allow for nonconvex constraint sets. This paper tackles the challenge of developing an ADMM-like algorithm that can effectively handle both nonsmooth objectives and manifold constraints simultaneously.

Methods

The core contribution is the development of a Riemannian ADMM (RADMM). The approach is built upon the idea of Moreau envelope smoothing, which transforms the nonsmooth term into a smooth one by adding a quadratic proximal term. This allows the problem to be reformulated and then tackled with an ADMM framework. The key innovation lies in how RADMM handles the subproblems:

  • Manifold Constraint: The algorithm uses retraction operations to stay on the manifold, a standard technique in Riemannian optimization.
  • Nonsmooth Objective: The nonsmooth part is handled via its proximal mapping, which is efficiently computable for many common nonsmooth functions (like L1-norm).

Unlike some existing methods that require solving complex subproblems (e.g., using semi-smooth Newton methods), RADMM's steps are designed to be "easily computable," making it practical for implementation. The paper also provides a theoretical analysis of the algorithm's iteration complexity for finding an $\epsilon$-stationary point under mild assumptions.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated for the following applications:

  • Sparse Principal Component Analysis (PCA): Data matrices are generated with standard Gaussian entries.
  • Orthogonal Dictionary Learning (ODL) and Dual Principal Component Pursuit (DPCP): Data is constructed to simulate inliers and outliers, with specific parameters for the number of dimensions and components.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully bridges the gap between ADMM for convex/Euclidean problems and the more complex realm of nonsmooth optimization on manifolds.
  • Moreau Envelope as a Unifier: Using the Moreau envelope is a powerful technique to "smooth out" the nonsmooth term, making it amenable to ADMM-like splitting strategies even on manifolds.
  • Practicality through Simplicity: The emphasis on "easily computable steps" is crucial for the practical applicability of the algorithm, especially for large-scale problems where complex subproblem solvers can be prohibitive.
  • Theoretical Guarantees: Providing convergence analysis for an ADMM on nonconvex sets with nonsmooth objectives is a significant theoretical contribution.

Key Results

The paper demonstrates the effectiveness of RADMM through numerical experiments on Sparse PCA and ODL/DPCP.

  • Sparse PCA: RADMM consistently outperforms Riemannian Subgradient (RSG) and Manifold Proximal Gradient (ManPG) methods in terms of speed (often 10-20 times faster than ManPG) and objective value. While RSG struggles to decrease the objective, RADMM and ManPG achieve lower objective values, with RADMM being more efficient. RADMM also generates sparse solutions comparable to ManPG, whereas RSG does not.
  • ODL and DPCP: RADMM is shown to be significantly faster than SOC, MADMM, and other related methods (like IRLS, PSGM, ManPPA) in terms of CPU time, while achieving comparable or better objective function values. The constraint violation for RADMM is reported to be small.
  • Convergence: The theoretical analysis shows that RADMM generates an $\epsilon$-stationary point in $O(\epsilon^{-4})$ iterations, providing a solid theoretical foundation.

Limitations and Future Work

  • Smoothing Assumption: The current RADMM relies on the Moreau envelope smoothing technique. The authors acknowledge that designing ADMM for problem (1) without smoothing remains an open question for future work. This suggests that the current method might not be optimal for all types of nonsmooth functions or might have limitations where smoothing is not ideal.
  • Parameter Tuning: While the paper mentions parameter choices and grid searches, the sensitivity of RADMM to parameter choices (like $\rho$ and $\gamma$) might be a practical limitation in real-world applications.
  • Specific Manifolds: The theoretical analysis and experiments focus on specific types of manifolds (e.g., Stiefel manifold). Extending the analysis and demonstrating performance on a wider range of Riemannian manifolds could be a future direction.

Summary updated

Abstract

We consider a class of Riemannian optimization problems where the objective is the sum of a smooth function and a nonsmooth function, considered in the ambient space. This class of problems finds important applications in machine learning and statistics such as the sparse principal component analysis, sparse spectral clustering, and orthogonal dictionary learning. We propose a Riemannian alternating direction method of multipliers (ADMM) to solve this class of problems. Our algorithm adopts easily computable steps in each iteration. The iteration complexity of the proposed algorithm for obtaining an $\epsilon$-stationary point is analyzed under mild assumptions. Existing ADMM for solving nonconvex problems either does not allow nonconvex constraint set, or does not allow nonsmooth objective function. Our algorithm is the first ADMM type algorithm that minimizes a nonsmooth objective over manifold -- a particular nonconvex set. Numerical experiments are conducted to demonstrate the advantage of the proposed method.
BibTeX
@misc{li2022riemannian,
  author = {Jiaxiang Li and Shiqian Ma and Tejes Srivastava},
  title = {{A Riemannian ADMM}},
  year = {2022},
  eprint = {2211.02163},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.02163},
}
Figure