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

Nonsmooth composite optimization with orthogonality constraints has a wide range of applications in statistical learning and data science. However, this problem is challenging due to its nonsmooth objective and computationally expensive nonconvex constraints. In this paper, we propose a new approach called $\mathbf{\text{OBCD}}$, which leverages block coordinate descent to address these challenges. $\mathbf{\text{OBCD}}$ is a feasible method with a small computational footprint. In each iteration, it updates $k$ rows of the solution matrix, where $k\ge 2$, by globally solving a small nonsmooth optimization problem under orthogonality constraints. We prove the completeness of the proposed update scheme, showing that row-wise orthogonal updates can reach any feasible point from any feasible initialization. We further prove that the limit points generated by $\mathbf{\text{OBCD}}$, referred to as global block-$k$ stationary points, offer stronger optimality than standard critical points. Furthermore, we show that $\mathbf{\text{OBCD}}$ finds an $\epsilon$-block-$k$ stationary point with an iteration complexity of $\mathcal{O}(1\mathrm{/}\epsilon )$. Additionally, under the Kurdyka–Lojasiewicz (KL) inequality, we establish the non-ergodic convergence rate of $\mathbf{\text{OBCD}}$. We also demonstrate how novel breakpoint search methods can be used to solve the subproblems arising in $\mathbf{\text{OBCD}}$. Empirical results show that our approach consistently outperforms existing methods.