# Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 74 references that are in the map.
- First posted on arXiv 18 May 2025.

## Builds on (most cited first, 30 of 39)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Controlling Text-to-Image Diffusion by Orthogonal Finetuning](https://mlsanity.com/paper/2306.07280/) (2023)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group](https://mlsanity.com/paper/1901.08428/) (2019)
- [Orthogonal Convolutional Neural Networks](https://mlsanity.com/paper/1911.12207/) (2019)
- [Parameter-Efficient Orthogonal Finetuning via Butterfly Factorization](https://mlsanity.com/paper/2311.06243/) (2023)
- [Continual Learning in Low-rank Orthogonal Subspaces](https://mlsanity.com/paper/2010.11635/) (2020)
- [Orthogonal Recurrent Neural Networks with Scaled Cayley Transform](https://mlsanity.com/paper/1707.09520/) (2017)
- [Efficient Riemannian Optimization on the Stiefel Manifold via the Cayley Transform](https://mlsanity.com/paper/2002.01113/) (2020)
- [Orthogonal Deep Neural Networks](https://mlsanity.com/paper/1905.05929/) (2019)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016)
- [Projection Robust Wasserstein Distance and Riemannian Optimization](https://mlsanity.com/paper/2006.07458/) (2020)
- [Fast and accurate optimization on the orthogonal manifold without retraction](https://mlsanity.com/paper/2102.07432/) (2021)
- [A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance](https://mlsanity.com/paper/2012.05199/) (2020)
- [From Nesterov's Estimate Sequence to Riemannian Acceleration](https://mlsanity.com/paper/2001.08876/) (2020)
- [Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2303.16510/) (2023)
- [Adaptive regularization with cubics on manifolds](https://mlsanity.com/paper/1806.00065/) (2018)
- [Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints](https://mlsanity.com/paper/1810.03930/) (2018)
- [A stochastic subspace approach to gradient-free optimization in high dimensions](https://mlsanity.com/paper/2003.02684/) (2020)
- [Block Coordinate Descent on Smooth Manifolds: Convergence Theory and Twenty-One Examples](https://mlsanity.com/paper/2305.14744/) (2023)
- [Riemannian Hamiltonian methods for min-max optimization on manifolds](https://mlsanity.com/paper/2204.11418/) (2022)
- [Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transport](https://mlsanity.com/paper/2205.14173/) (2022)
- [O-ViT: Orthogonal Vision Transformer](https://mlsanity.com/paper/2201.12133/) (2022)
- [Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm](https://mlsanity.com/paper/2202.06950/) (2022)
- [Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds](https://mlsanity.com/paper/1912.10627/) (2019)
- [Optimization without Retraction on the Random Generalized Stiefel Manifold](https://mlsanity.com/paper/2405.01702/) (2024)
- [Riemannian stochastic recursive momentum method for non-convex optimization](https://mlsanity.com/paper/2008.04555/) (2020)
- [Fast convergence to non-isolated minima: four equivalent conditions for C2 functions](https://mlsanity.com/paper/2303.00096/) (2023)
- [Riemannian accelerated gradient methods via extrapolation](https://mlsanity.com/paper/2208.06619/) (2022)

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

- [An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale](https://mlsanity.com/paper/2602.14656/) (2026)
- [Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.20399/) (2026)
- [LOFT: Low-Rank Orthogonal Fine-Tuning via Task-Aware Support Selection](https://mlsanity.com/paper/2605.11872/) (2026)

## Abstract (arXiv)

Optimization with orthogonality constraints frequently arises in various fields such as machine learning. Riemannian optimization offers a powerful framework for solving these problems by equipping the constraint set with a Riemannian manifold structure and performing optimization intrinsically on the manifold. This approach typically involves computing a search direction in the tangent space and updating variables via a retraction operation. However, as the size of the variables increases, the computational cost of the retraction can become prohibitively high, limiting the applicability of Riemannian optimization to large-scale problems. To address this challenge and enhance scalability, we propose a novel approach that restricts each update on a random submanifold, thereby significantly reducing the per-iteration complexity. We introduce two sampling strategies for selecting the random submanifolds and theoretically analyze the convergence of the proposed methods. We provide convergence results for general nonconvex functions and functions that satisfy Riemannian Polyak-Lojasiewicz condition as well as for stochastic optimization settings. Additionally, we demonstrate how our approach can be generalized to quotient manifolds derived from the orthogonal manifold. Extensive experiments verify the benefits of the proposed method, across a wide variety of problems.