Convergence analysis of the transformed gradient projection algorithms on compact matrix manifolds

Wentao Ding, Jianze Li, Shuzhong ZhangarXiv 2024 · DOI · arXiv

Abstract

Optimization on compact matrix manifolds, such as the Stiefel and Grassmann manifolds, is central to various applications in machine learning and signal processing. While retraction-based methods have established theoretical foundations, projection-based methods—which utilize the surrounding Euclidean space—have lacked a unified convergence theory for general search directions. This paper introduces the Transformed Gradient Projection (TGP) framework, providing a rigorous theoretical basis for these methods. We establish global convergence under nonmonotone line search conditions and demonstrate that TGP generalizes several existing algorithms while offering superior global search capabilities in nonconvex settings.

1. Introduction

Many optimization problems in scientific computing and machine learning are subject to constraints that define a curved geometric space, or manifold. Common examples include requiring a matrix to have orthonormal columns (Stiefel manifold) or identifying optimal subspaces (Grassmann manifold). Algorithms for these problems generally fall into two categories:

  1. Retraction-based methods: These move along a flat tangent space and then "snap" back to the manifold using a mapping called a retraction.
  2. Projection-based methods: These take a step in the ambient Euclidean space and then project the result back onto the manifold.

Despite the practical utility of projection-based methods (ProjLS), their theoretical properties—particularly when using adaptive stepsizes or non-gradient search directions—have remained under-studied. This work bridges this gap by introducing the Transformed Gradient Projection (TGP) framework, providing a unified theory for projection-based manifold optimization.

2. The Transformed Gradient Projection (TGP) Framework

The TGP algorithm updates the current iterate $X_k$ using the following core update rule: $$X_{k+1} = \mathcal{P}_{\mathcal{M}}(X_k - \tau_k H_k)$$ where $\mathcal{P}_{\mathcal{M}}$ denotes the projection onto the manifold $\mathcal{M}$, $\tau_k$ is the stepsize, and $H_k$ is the search direction.

2.1 Search Direction Components

A key innovation of TGP is the flexibility of the search direction $H_k$. It is defined by three primary components:

  • Scaling Matrices ($L$ and $R$): These allow for left and right transformations of the gradient, enabling the framework to encompass various classical algorithms like the Euclidean Gradient Projection (EGP) and the Shifted Power Method.
  • Normal Component ($N$): Unlike traditional Riemannian methods that operate strictly within the tangent space, TGP incorporates a component normal to the manifold. This allows the algorithm to effectively "jump" across the manifold's curvature, facilitating the escape from local minima that might trap purely tangential methods.

2.2 Geometric Analysis

The authors derive new inequalities regarding the "reach" and stability of projections on compact manifolds. They establish that the projection operator is a $C^{k-1}$ smooth retraction on a compact $C^k$ manifold. This stability property is essential for proving that the algorithm remains well-behaved as it traverses the curved surface.

3. Convergence Analysis

The paper provides the first global convergence proofs for projection-based methods using the Zhang-Hager nonmonotone Armijo stepsize in nonconvex settings. This stepsize strategy allows the objective function value to increase occasionally, which is a critical mechanism for avoiding stagnation in local optima.

Key theoretical results include:

  • Iteration Complexity: TGP is proven to achieve a first-order $\epsilon$-stationary point within $O(\epsilon^{-2})$ iterations, matching the best-known rates for first-order manifold methods.
  • Unified Framework: The authors demonstrate that by choosing specific values for $L, R,$ and $N$, TGP encompasses several existing algorithms, providing them with a newfound theoretical grounding.

4. Numerical Evaluation

The TGP framework was evaluated using numerical experiments on standard benchmark problems in manifold optimization, including Inhomogeneous Quadratic Optimization, Jointly Approximate Symmetric Matrix Diagonalization (JAMD-S), and Jointly Approximate Symmetric Tensor Diagonalization (JATD-S). These tests were conducted on Stiefel and Grassmann manifolds, comparing TGP against established solvers in the manopt MATLAB package.

4.1 Key Results

  • Superior Global Search: In ill-conditioned quadratic problems, TGP variants utilizing the normal component reached the global optimum in 418 out of 500 instances, significantly outperforming standard Riemannian Gradient Descent (RGD), which succeeded in only 346 instances.
  • Computational Efficiency: For tensor diagonalization, TGP with a fixed stepsize (TGP-F) was significantly faster than standard BFGS or Conjugate Gradient methods, achieving lower CPU times while maintaining high solution quality.

5. Conclusion and Future Work

The TGP framework provides a robust theoretical and practical foundation for projection-based manifold optimization. While highly effective, the authors note that performance depends on the choice of scaling matrices and the normal component, which currently require problem-specific tuning. Future research may explore incorporating second-order Riemannian Hessian information to further accelerate convergence and extending the theory to non-compact manifolds, such as the set of positive definite matrices.

Summary updated

BibTeX
@misc{ding2024convergence,
  author = {Wentao Ding and Jianze Li and Shuzhong Zhang},
  title = {{Convergence analysis of the transformed gradient projection algorithms on compact matrix manifolds}},
  year = {2024},
  eprint = {2404.19392},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.19392},
}
Figure