# Block Coordinate Descent on Smooth Manifolds: Convergence Theory and Twenty-One Examples

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2023.

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

- [Scalable 3D Registration via Truncated Entry-wise Absolute Residuals](https://mlsanity.com/paper/2404.00915/) (2024)
- [Efficient and Robust Point Cloud Registration via Heuristics-guided Parameter Search](https://mlsanity.com/paper/2404.06155/) (2024)
- [Continual Reinforcement Learning by Planning with Online World Models](https://mlsanity.com/paper/2507.09177/) (2025)
- [Distributional Counterfactual Explanations With Optimal Transport](https://mlsanity.com/paper/2401.13112/) (2024)
- [LeanVec: Searching vectors faster by making them fit](https://mlsanity.com/paper/2312.16335/) (2023)
- [An Overview of the Burer-Monteiro Method for Certifiable Robot Perception](https://mlsanity.com/paper/2410.00117/) (2024)
- [Riemannian coordinate descent algorithms on matrix manifolds](https://mlsanity.com/paper/2406.02225/) (2024)
- [Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective](https://mlsanity.com/paper/2501.18282/) (2025)
- [Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method](https://mlsanity.com/paper/2505.12378/) (2025)
- [Importance-Aware Semantic Communication in MIMO-OFDM Systems Using Vision Transformer](https://mlsanity.com/paper/2508.07696/) (2025)
- [DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming](https://mlsanity.com/paper/2603.25442/) (2026)
- [Manifold-based Algorithms for the Hadamard Decomposition](https://mlsanity.com/paper/2605.28980/) (2026)
- [Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms](https://mlsanity.com/paper/2405.03073/) (2024)
- [On Barycenter Computation: Semi-Unbalanced Optimal Transport-based Method on Gaussians](https://mlsanity.com/paper/2410.08117/) (2024)
- [Making Rotation Averaging Fast and Robust with Anisotropic Coordinate Descent](https://mlsanity.com/paper/2506.01940/) (2025)
- [Directed Graph Topology Inference via Graph Filter Identification](https://mlsanity.com/paper/2606.27455/) (2026)

## Abstract (arXiv)

Block coordinate descent is an optimization paradigm that iteratively updates one block of variables at a time, making it quite amenable to big data applications due to its scalability and performance. Its convergence behavior has been extensively studied in the (block-wise) convex case, but it is much less explored in the non-convex case. In this paper we analyze the convergence of block coordinate methods on non-convex sets and derive convergence rates on smooth manifolds under natural or weaker assumptions than prior work. Our analysis applies to many non-convex problems, including ones that seek low-dimensional structures (e.g., maximal coding rate reduction, neural collapse, reverse engineering adversarial attacks, generalized PCA, alternating projection); ones that seek combinatorial structures (homomorphic sensing, regression without correspondences, real phase retrieval, robust point matching); ones that seek geometric structures from visual data (e.g., essential matrix estimation, absolute pose estimation); and ones that seek inliers sparsely hidden in a large number of outliers (e.g., outlier-robust estimation via iteratively-reweighted least-squares). While our convergence theory applies to all these problems, yielding novel corollaries, it also applies to other, perhaps more familiar, problems (e.g., optimal transport, matrix factorization, Burer-Monteiro factorization), recovering previously known results.