A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints

Technical Summary: A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints

Problem Statement
The paper addresses the challenge of nonsmooth composite optimization under orthogonality constraints, formulated as:
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{s.t. } X^T X = I_r$$
where $n \ge r$, $f(X)$ is a smooth (potentially nonconvex) function, and $h(X)$ is a proper, lower semicontinuous, potentially nonsmooth function that is coordinate-wise separable. The feasible set is the Stiefel manifold $\mathcal{M} = \text{St}(n, r)$. This framework encompasses critical applications in statistical learning and data science, including sparse Principal Component Analysis (PCA) with $\ell_0$ or $\ell_1$ regularization, nonnegative PCA, deep neural network training with orthogonal constraints, and dictionary learning.

Existing methods face significant limitations: many rely on full gradient information (high computational cost), fail to handle coordinate-wise nonsmooth objectives effectively, lack true descent properties (often only achieving feasibility asymptotically), or provide weak optimality guarantees (converging only to standard critical points).

Methodology: The OBCD Algorithm
The authors propose OBCD (Orthogonal Block Coordinate Descent), a feasible method that updates $k$ rows of the solution matrix $X$ simultaneously, where $k \ge 2$.

1. Constraint-Preserving Update Scheme:
   Instead of projecting onto the manifold or using retractions, OBCD employs a specific update rule that maintains orthogonality by construction. For a working set of row indices $B$ (size $k$), the update is defined as:
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   where $U_B$ selects the rows in $B$, and $V \in \text{St}(k, k)$ is an orthogonal matrix solving a subproblem. Lemma 2.1 proves that if $X^t$ is feasible, $X^{t+1}$ remains feasible for any $V \in \text{St}(k, k)$.

2. Subproblem Formulation:
   In each iteration, OBCD solves a small-scale subproblem over the Stiefel manifold of dimension $k \times k$. Using a Majorization-Minimization (MM) approach, the smooth part $f(X)$ is approximated by a quadratic surrogate, while the nonsmooth part $h(X)$ is kept exact. The resulting subproblem is:
   $$\bar{V}_t \in \arg\min_{V \in \text{St}(k, k)} \left( \frac{1}{2} \|V - I_k\|_{\tilde{Q}}^2 + \langle V, P \rangle + h(V Z) \right)$$
   where $Z = U_B^T X^t$, $P$ involves the gradient of $f$, and $\tilde{Q}$ is a positive definite matrix derived from the Hessian of $f$ or a scalar proxy.

3. Solving Subproblems:

   • General $k$: The paper assumes the subproblem can be solved exactly or efficiently (e.g., via proximal-friendly structures).
   • Case $k=2$: The authors introduce a novel Breakpoint Search Method (BSM). By parameterizing $2 \times 2$ orthogonal matrices using Givens rotations ($V^{rot}_\theta$) and Jacobi reflections ($V^{ref}_\theta$), the subproblem is reduced to a one-dimensional optimization over $\theta$. The BSM identifies all breakpoints (critical points) of the objective function (including those arising from the nonsmooth term $h$) to find the global minimizer.

4. Working Set Selection:
   The algorithm supports both random and cyclic strategies for selecting the working set $B$.

Theoretical Contributions
The paper provides rigorous theoretical analysis regarding optimality and convergence:

• Completeness of Update Scheme: The authors prove that the proposed row-wise update scheme is complete. Specifically, any point on the Stiefel manifold can be reached from any other feasible point via a sequence of these $k$-row updates (Theorem 3.1, Corollary 3.2).
• Stronger Optimality Conditions: The paper defines Global Block-$k$ Stationary Points (BSk-points). A solution is a BSk-point if no improvement can be made by optimizing any block of $k$ rows. The authors establish a hierarchy of optimality:
  $$\{\text{Global Optima}\} \subseteq \{\text{BSk-points}\} \subseteq \{\text{BS(k+1)-points}\} \subseteq \{\text{Critical Points}\}$$
  This implies that BSk-points (for $k \ge 2$) satisfy a strictly stronger optimality condition than standard critical points, theoretically allowing the algorithm to escape poor local minima that trap standard methods.
• Iteration Complexity:
  • OBCD finds an $\epsilon$-block-$k$ stationary point with an iteration complexity of $O(1/\epsilon)$.
  • Under the Kurdyka–Łojasiewicz (KL) inequality assumption, the paper establishes non-ergodic (last-iterate) convergence rates. Depending on the KL exponent $\sigma$, the convergence is finite ($\sigma=0$), linear ($\sigma \in (0, 1/2]$), or sublinear ($\sigma \in (1/2, 1)$).

Experimental Results
The authors evaluate OBCD on L0-regularized Sparse PCA, L1-regularized Sparse PCA, and Nonnegative PCA using real-world datasets (e.g., MNIST, Gisette, 20News) and synthetic data.

• Performance: OBCD consistently outperforms state-of-the-art baselines, including Linearized ADMM (LADMM), Riemannian ADMM (RADMM), Penalty-based Splitting Method (PSM), and Manifold Proximal Gradient (ManPG).
• Objective Values: In terms of final objective value, OBCD achieves lower values than competing methods, often escaping local minima where others get trapped.
• Efficiency: While full-gradient methods may require fewer iterations, OBCD's lower per-iteration cost (partial gradient updates) results in superior performance when measured by CPU time.
• Feasibility: Unlike some infeasible methods (e.g., certain splitting methods) that only satisfy constraints in the limit, OBCD maintains strict orthogonality (and non-negativity in the Nonnegative PCA variant) throughout the optimization process.

Significance and Claims
The paper claims that OBCD offers a significant advancement by combining computational efficiency with strong theoretical guarantees. Its primary significance lies in:

1. Handling Nonsmoothness: It effectively addresses coordinate-wise nonsmooth objectives under orthogonality constraints, a setting where many existing manifold optimization methods struggle.
2. Stronger Optimality: By utilizing block updates ($k \ge 2$), the method targets BSk-points, which are theoretically superior to standard critical points, providing a mechanism to avoid suboptimal local minima.
3. Feasibility: It is a strictly feasible method, ensuring constraints are satisfied at every iteration, unlike penalty-based or infeasible splitting approaches.
4. Practical Efficiency: The algorithm is designed for large-scale problems where full gradient computations are prohibitive, offering a scalable alternative with proven convergence properties.