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

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

Source: arXiv cs.LG | 2026-05-15