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

arXiv: https://arxiv.org/abs/2304.03641 · HTML: https://mlsanity.com/paper/2304.03641/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 79 references that are in the map.
- First posted on arXiv 7 Apr 2023.

## Builds on (most cited first, 23 of 23)

- [Reducing Overfitting in Deep Networks by Decorrelating Representations](https://mlsanity.com/paper/1511.06068/) (2015)
- [All You Need is Beyond a Good Init: Exploring Better Solution for Training Extremely Deep Convolutional Neural Networks with Orthonormality and Modulation](https://mlsanity.com/paper/1703.01827/) (2017)
- [Global Convergence of Block Coordinate Descent in Deep Learning](https://mlsanity.com/paper/1803.00225/) (2018)
- [Riemannian approach to batch normalization](https://mlsanity.com/paper/1709.09603/) (2017)
- [A Brief Introduction to Manifold Optimization](https://mlsanity.com/paper/1906.05450/) (2019)
- [Fast and accurate optimization on the orthogonal manifold without retraction](https://mlsanity.com/paper/2102.07432/) (2021)
- [Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2303.16510/) (2023)
- [On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization](https://mlsanity.com/paper/1603.00211/) (2016)
- [Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints](https://mlsanity.com/paper/1810.03930/) (2018)
- [Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds](https://mlsanity.com/paper/2010.06097/) (2020)
- [A Framework of Constraint Preserving Update Schemes for Optimization on Stiefel Manifold](https://mlsanity.com/paper/1301.0172/) (2013)
- [Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds](https://mlsanity.com/paper/1912.10627/) (2019)
- [Structured Quasi-Newton Methods for Optimization with Orthogonality Constraints](https://mlsanity.com/paper/1809.00452/) (2018)
- [Approximating Orthogonal Matrices with Effective Givens Factorization](https://mlsanity.com/paper/1905.05796/) (2019)
- [An exact penalty approach for optimization with nonnegative orthogonality constraints](https://mlsanity.com/paper/1907.12424/) (2019)
- [Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis](https://mlsanity.com/paper/1710.02236/) (2017)
- [A Block Decomposition Algorithm for Sparse Optimization](https://mlsanity.com/paper/1905.11031/) (2019)
- [Coordinate descent on the orthogonal group for recurrent neural network training](https://mlsanity.com/paper/2108.00051/) (2021)
- [Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2104.13782/) (2021)
- [Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methods](https://mlsanity.com/paper/1510.01025/) (2015)
- [Lp-norm regularization algorithms for optimization over permutation matrices](https://mlsanity.com/paper/1608.06695/) (2016)
- [Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2109.04228/) (2021)
- [Coordinate Descent Methods for Fractional Minimization](https://mlsanity.com/paper/2201.12691/) (2022)

## Built on by (most cited first, 2 of 2)

- [Riemannian coordinate descent algorithms on matrix manifolds](https://mlsanity.com/paper/2406.02225/) (2024)
- [Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method](https://mlsanity.com/paper/2505.12378/) (2025)

## Abstract (arXiv)

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.