Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization

This paper establishes the asymptotic convergence and $\widetilde{O}(\epsilon^{-2})$ iteration complexity of block majorization-minimization algorithms for smooth nonconvex optimization problems with block constraints on Riemannian manifolds, demonstrating their broad applicability and superior performance over standard Euclidean approaches.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy, and incredibly complex landscape. This landscape isn't flat like a soccer field (Euclidean space); it's curved, twisted, and has strange rules, like the surface of a sphere or a hyperbolic saddle. This is what mathematicians call a Riemannian Manifold.

Your goal is to find the absolute lowest valley (the global minimum) to solve a difficult problem, like organizing a massive dataset or training an AI. However, the terrain is so rugged that you can't see the bottom from where you stand. You have to take steps, feel the ground, and guess your way down.

This paper introduces a new, smarter way to take those steps, called Block Majorization-Minimization (BMM), specifically adapted for these curved landscapes.

Here is the breakdown of the paper using simple analogies:

1. The Problem: The "Curved" Maze

In standard math problems, the world is flat. If you want to go downhill, you just walk in the direction of the steepest slope. But in this paper, the "ground" is curved.

• The Analogy: Imagine trying to walk down a hill on a giant, rotating globe. If you just walk "straight" (like on a flat map), you might end up walking off the edge or in a circle. You have to follow the curves of the earth (geodesics).
• The Constraint: Furthermore, you aren't allowed to walk anywhere you want. You are confined to specific paths or shapes (like staying on the surface of a sphere or keeping your steps orthogonal). This is the "Constrained" part.

2. The Old Way: The "One-Step-at-a-Time" Hiker

Traditional methods often try to move all your variables at once. It's like trying to steer a giant ship by turning the rudder, adjusting the sails, and shifting the cargo all simultaneously while the ship is rocking in a storm. It's hard, slow, and often gets stuck.

3. The New Method: The "Block-by-Block" Navigator

The authors propose a method called Block Majorization-Minimization (BMM).

• The Analogy: Imagine you are navigating a ship with a crew of 5 people (5 different "blocks" of variables). Instead of asking everyone to move at once, you ask one person to adjust their position while everyone else stands perfectly still.
  • Step 1 (Majorization): You don't know the exact shape of the hill under your feet right now. So, you build a safety net (a "surrogate") that sits above the real terrain. You know for a fact that the real ground is below this net.
  • Step 2 (Minimization): You ask the first crew member to find the lowest point under that safety net. Since the net is a simple, easy shape (like a bowl), finding the bottom is easy.
  • Step 3 (Repeat): Once that person is settled, you freeze them. Then you ask the second person to adjust their position based on a new safety net, while the first person stays put. You go down the line, one by one, cycling through the crew.

4. Why This Paper is Special

While this "one-by-one" strategy is known for flat ground, doing it on a curved, constrained surface is incredibly hard. The authors solved three major headaches:

• The "Curved" Math: They figured out how to build those "safety nets" (surrogates) on curved surfaces without getting lost in complex geometry. They showed that even if you use simple, flat approximations (Euclidean) on a curved surface, it still works surprisingly well.
• The "Imperfect" Steps: In the real world, you can't always find the exact bottom of the safety net. Maybe you get 99% close. The authors proved that even if your steps are slightly "inexact" (you don't find the perfect spot every time), the algorithm will still eventually find the bottom of the valley.
• The Speed Guarantee: They didn't just say "it works." They proved how fast it works. They showed that to get very close to the solution (within a tiny error margin $\epsilon$), the algorithm takes a specific, predictable number of steps. It's like saying, "No matter how foggy the hill is, you will reach the bottom in roughly $1/\epsilon^2$ steps."

5. Real-World Applications (The "Why Should I Care?")

The authors tested this on several real-world problems where data naturally lives on curved surfaces:

• Robust PCA (Cleaning Data): Imagine a photo that is mostly clear but has huge, random scratches (noise). This method helps separate the clean image from the scratches, even when the data is messy.
• Subspace Tracking: Imagine tracking a moving object (like a drone) where the camera angle changes constantly. This method helps predict the object's path smoothly, even as the "ground" (the camera's perspective) curves.
• Dictionary Learning: Think of this as teaching a computer to recognize patterns (like faces or sounds) by breaking them down into basic building blocks. This method makes that learning process faster and more accurate.

The Bottom Line

This paper is like a new GPS for curved, tricky terrains.
Before, navigating these complex, constrained problems was like hiking in the dark with a broken compass. The authors have given us a reliable map and a step-by-step strategy that guarantees you will reach the destination, even if you take imperfect steps along the way. They proved it works mathematically and showed that it's faster than the old ways of doing things.

In short: They took a smart, step-by-step optimization trick, taught it how to walk on curved surfaces without falling off, and proved it gets you to the finish line quickly and reliably.

Technical Summary

Here is a detailed technical summary of the paper "Convergence and Complexity of Block Majorization-Minimization for Constrained Block-Riemannian Optimization" by Li, Balzano, Needell, and Lyu.

1. Problem Statement

The paper addresses the minimization of a smooth, non-convex objective function $f$ defined over a product of constraint sets, where each set is a subset of a Riemannian manifold. The optimization problem is formulated as:
$$\min_{\theta} f(\theta) \quad \text{s.t.} \quad \theta = [\theta^{(1)}, \dots, \theta^{(m)}], \quad \theta^{(i)} \in \Theta^{(i)} \subseteq \mathcal{M}^{(i)}$$
where:

• $\mathcal{M}^{(i)}$ are Riemannian manifolds (e.g., Stiefel manifolds, Hadamard manifolds, Euclidean spaces).
• $\Theta^{(i)}$ are closed subsets of these manifolds (allowing for constrained optimization, not just optimization over the manifold itself).
• The objective $f$ is generally non-convex.

The goal is to find a stationary point (a point satisfying first-order optimality conditions) and to establish the iteration complexity required to reach an $\epsilon$-stationary point.

2. Methodology: Riemannian Block Majorization-Minimization (RBMM)

The authors propose and analyze RBMM, a generalization of the Block Majorization-Minimization (BMM) algorithm to the Riemannian setting.

Algorithm Overview:
At each iteration $n$, the algorithm cycles through blocks $i = 1, \dots, m$. For the $i$-th block, it:

1. Majorization: Constructs a surrogate function $g_n^{(i)}$ that upper-bounds the marginal objective $f_n^{(i)}$ (the objective with other blocks fixed) and touches it at the current iterate $\theta_n^{(i-1)}$.
   $$g_n^{(i)}(\theta) \geq f_n^{(i)}(\theta) \quad \forall \theta \in \Theta^{(i)}, \quad g_n^{(i)}(\theta_n^{(i-1)}) = f_n^{(i)}(\theta_n^{(i-1)})$$
2. Minimization: Updates the block by minimizing the surrogate:
   $$\theta_n^{(i)} \in \arg\min_{\theta \in \Theta^{(i)}} g_n^{(i)}(\theta)$$
   The paper allows for inexact minimization, provided the optimality gap decays sufficiently fast.

Key Surrogate Types Analyzed:
The paper investigates three specific types of surrogates to derive different convergence guarantees:

1. $g$-smooth surrogates: Surrogates that are geodesically smooth (Lipschitz continuous Riemannian gradient).
2. Riemannian Proximal Surrogates: $g_n^{(i)}(\theta) = f_n^{(i)}(\theta) + \frac{\lambda_n}{2} d^2(\theta, \theta_n^{(i-1)})$, where $d$ is the geodesic distance. These are particularly effective on Hadamard manifolds.
3. Euclidean Proximal Surrogates: $g_n^{(i)}(\theta) = f_n^{(i)}(\theta) + \frac{\lambda_n}{2} \|\theta - \theta_n^{(i-1)}\|^2$, using the ambient Euclidean distance. This is computationally simpler and applicable when manifolds are embedded in Euclidean space (e.g., Stiefel manifolds).

3. Key Contributions

The paper makes several novel theoretical contributions:

• Constrained Optimization on Manifolds: Unlike previous works that often assume unconstrained optimization (where the constraint set is the entire manifold), this framework explicitly handles closed subsets $\Theta^{(i)} \subseteq \mathcal{M}^{(i)}$.
• Iteration Complexity Bounds: While asymptotic convergence of block coordinate methods on manifolds was known, this paper provides the first iteration complexity bounds for RBMM in the non-convex, constrained Riemannian setting.
  • For Riemannian/Euclidean proximal surrogates, the complexity to reach an $\epsilon$-stationary point is $\tilde{O}(\epsilon^{-2})$.
  • For $g$-smooth surrogates, the complexity is generally $\tilde{O}(\epsilon^{-4})$, but improves to $\tilde{O}(\epsilon^{-2})$ if the surrogate gap satisfies a quadratic growth condition (similar to the proximal case).
• Robustness to Inexactness: The analysis explicitly accounts for inexact solutions to the sub-problems, requiring only that the optimality gaps are summable.
• Bridging Euclidean and Riemannian Smoothness: A crucial technical insight is that for Stiefel manifolds, Euclidean smoothness (Lipschitz gradient in the ambient space) implies geodesic smoothness ($g$-smoothness) on the manifold. This allows the authors to apply their general Riemannian results to algorithms using standard Euclidean surrogates (like prox-linear updates) on Stiefel manifolds.

4. Main Results

Theoretical Guarantees:

• Asymptotic Convergence: Under mild assumptions (summable optimality gaps, lower-bounded injectivity radius), the sequence of iterates generated by RBMM converges asymptotically to the set of stationary points for any number of blocks $m \geq 1$.
• Complexity for Proximal Methods: For Riemannian or Euclidean proximal surrogates, the algorithm achieves an $\epsilon$-stationary point in $\tilde{O}(\epsilon^{-2})$ iterations. This result holds even when the constraint sets are not geodesically convex, provided the surrogates satisfy specific distance-regularizing properties.
• Complexity for Stiefel Manifolds: The paper establishes that block MM methods on Stiefel manifolds using Euclidean surrogates (e.g., Euclidean prox-linear updates) achieve $\tilde{O}(\epsilon^{-2})$ complexity. This resolves a gap in the literature where such methods were used but lacked complexity guarantees due to the non-convexity of the Stiefel manifold in Euclidean space.

Applications Validated:
The authors apply their framework to several specific problems, deriving new complexity results for:

1. Geodesically Constrained Subspace Tracking: A block MM algorithm with proximal regularization is shown to converge with $\tilde{O}(\epsilon^{-2})$ complexity.
2. Optimistic Likelihood Estimation: Using Riemannian proximal updates on the manifold of Positive Definite Matrices (a Hadamard manifold), achieving $\tilde{O}(\epsilon^{-2})$ complexity.
3. Riemannian CP-Dictionary Learning: Proving asymptotic convergence for alternating minimization on low-rank and Stiefel manifolds.
4. Robust PCA: Analyzing an alternating minimization algorithm for RPCA with hard rank constraints.

5. Significance and Impact

• Unification: The paper unifies various existing algorithms (Euclidean BMM, Riemannian Proximal Point, Block PGD, MM on Stiefel manifolds) under a single theoretical framework.
• Practicality: By validating the use of Euclidean surrogates (which are computationally cheaper and easier to differentiate) on Riemannian manifolds (specifically Stiefel manifolds) while retaining rigorous convergence guarantees, the work bridges the gap between theoretical optimality and practical implementation.
• New Benchmarks: The $\tilde{O}(\epsilon^{-2})$ complexity result for block methods on Stiefel manifolds sets a new theoretical benchmark for non-convex optimization in signal processing and machine learning applications involving orthogonality constraints.
• Experimental Validation: Numerical experiments on subspace tracking and dictionary learning demonstrate that the proposed RBMM algorithms converge faster or more robustly than standard Euclidean approaches applied naively to Riemannian problems.

In summary, this paper provides a rigorous foundation for block optimization on manifolds, proving that simple majorization-minimization strategies are not only asymptotically convergent but also possess optimal iteration complexity rates comparable to their Euclidean counterparts, even in the presence of complex geometric constraints.