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 \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 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 \textbf{OBCD}, referred to as global block-\(k\) stationary points, offer stronger optimality than standard critical points. Furthermore, we show that \textbf{OBCD} finds an \(\epsilon\)-block-\(k\) stationary point with an iteration complexity of \(\mathcal{O}(1/\epsilon)\). Additionally, under the Kurdyka--Lojasiewicz (KL) inequality, we establish the non-ergodic convergence rate of \textbf{OBCD}. We also demonstrate how novel breakpoint search methods can be used to solve the subproblems arising in \textbf{OBCD}. Empirical results show that our approach consistently outperforms existing methods.
| Comments: | Future versions of this paper can be found at arXiv:2304.03641 |
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG); Numerical Analysis (math.NA) |
| Cite as: | arXiv:2304.03641 [math.OC] |
| (or arXiv:2304.03641v4 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2304.03641 arXiv-issued DOI via DataCite |
Submission history
From: Ganzhao Yuan [view email]
[v1]
Fri, 7 Apr 2023 13:44:59 UTC (2,397 KB)
[v2]
Tue, 12 Nov 2024 02:34:46 UTC (4,949 KB)
[v3]
Mon, 2 Dec 2024 00:54:47 UTC (4,963 KB)
[v4]
Thu, 14 May 2026 16:19:47 UTC (1,749 KB)