A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints
This addresses a computationally expensive problem in statistical learning and data science, offering a feasible method with improved convergence guarantees, though it appears incremental as it builds on block coordinate descent techniques.
The paper tackles nonsmooth composite optimization under orthogonality constraints, which is challenging due to nonsmooth objectives and non-convex constraints, by proposing OBCD, a block coordinate descent method that updates k rows per iteration and proves convergence to stronger optimality points with an ergodic rate of O(1/ε).
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, non-convex constraints. In this paper, we propose a new approach called \textbf{OBCD}, which leverages Block Coordinate Descent to address these challenges. \textbf{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 that the limiting points of \textbf{OBCD}, referred to as (global) block-$k$ stationary points, offer stronger optimality than standard critical points. Furthermore, we show that \textbf{OBCD} converges to $ε$-block-$k$ stationary points with an ergodic convergence rate of $\mathcal{O}(1/ε)$. Additionally, under the Kurdyka-Lojasiewicz (KL) inequality, we establish the non-ergodic convergence rate of \textbf{OBCD}. We also extend \textbf{OBCD} by incorporating breakpoint searching methods for subproblem solving and greedy strategies for working set selection. Comprehensive experiments demonstrate the superior performance of our approach across various tasks.