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 OBCD, which leverages block coordinate descent to address these challenges. OBCD is a feasible method with a small computational footprint. In each iteration, it updates (k) rows of the solution matrix, where (k ≥ 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 OBCD, referred to as global block-(k) stationary points, offer stronger optimality than standard critical points. Furthermore, we show that OBCD finds an (ε)-block-(k) stationary point with an iteration complexity of (O(1/ε)). Additionally, under the Kurdyka--Lojasiewicz (KL) inequality, we establish the non-ergodic convergence rate of OBCD. We also demonstrate how novel breakpoint search methods can be used to solve the subproblems arising in OBCD. Empirical results show that our approach consistently outperforms existing methods.