Research map / Optimization / Optimizers
Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RSDM, which updates Stiefel-manifold iterates on a random submanifold via permutation or orthogonal sampling, cutting retraction cost from O(np^2) to O(nr^2) or O(npr), with convergence analyses in several settings.
Problem
Riemannian optimization on the Stiefel manifold (orthogonality constraints) becomes bottlenecked by retraction cost, which is at least O(np^2) per iteration, limiting scalability to large n and p.
Approach
Parameterize the update as X_{k+1}=U_k X_k with U_k = P_k^T diag(Y, I) P_k for a random orthogonal P_k and small Y in O(r), so only an r-dimensional retraction is needed per iteration; two sampling schemes (uniform permutation and uniform orthogonal) are studied, generalizing random subspace descent and recovering Riemannian coordinate descent as a special case.
Key results
- Per-iteration cost reduced from O(np^2) to O(nr^2) (permutation) or O(npr) (orthogonal) sampling, with the retraction on O(r) only.
- Convergence rate for general nonconvex functions matches RGD up to an extra n^2/r^2 factor in expectation; permutation sampling has a binomial factor in high-probability bounds.
- On PCA (n=2000, p=1500), RSDM converges fastest among baselines in runtime and switches to linear convergence near the optimum.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RSDM instead of RGD | Stiefel optimization · PCA | convergence speed | Helped |
| Use RSDM instead of the baselines | Stiefel optimization · Quadratic assignment (QUAD), n = 1000 | convergence speed | Helped |
| Use RSDM-O instead of RSDM-P | RSDM · Quadratic assignment (QUAD), n = 1000 | convergence speed | Helped |
| Use RSDM instead of RGD | Orthogonal FFN · MNIST and CIFAR10 | early-iteration convergence speed in runtime | Helped |
| Use RSDM-P instead of RGD | Orthogonal ViT · MNIST and CIFAR10 | test accuracy | Helped |
| Use RSDM instead of RGD | Stiefel optimization · Procrustes problem, n = p = 200 and n = p = 2000 | runtime convergence | No clear effect |
| Use RSDM instead of RGD | Stiefel optimization · Procrustes problem | convergence speed by iteration count | Hurt |
| Use RSDM instead of RGD | Orthogonal neural networks · MNIST and CIFAR10 | convergence speed by iteration count | Hurt |
| Vary the submanifold dimension r (ablation) | RSDM · PCA | performance robustness | No clear effect |
| Vary the random seed (ablation) | RSDM · PCA | performance robustness | No clear effect |
| Use different retractions (ablation) | RSDM · PCA | convergence performance versus RGD | Helped |
Surprising findings
- Permutation sampling gives a high-probability bound with a factor binom(n,r), making it much weaker than orthogonal sampling in theory despite its lower per-iteration cost.
Limitations
- Matches RGD complexity only when p = Omega(n); the advantage vanishes when p << n.
- Permutation sampling's high-probability bounds degrade by a binomial factor, requiring many more iterations.
- Analysis is restricted to RGD as the base solver; combinations with momentum, line search, or preconditioning are left for future work.
Experimental setup
Datasets: MNIST CIFAR10
Benchmarks: Procrustes problem PCA quadratic assignment problem MNIST CIFAR10
Metrics: optimality gap test accuracy runtime iterations to convergence
Baselines: RGD RCD TSD PCAL Landing
Builds on: Riemannian gradient descent random subspace gradient descent Riemannian coordinate descent on Stiefel manifold
Closest papers by meaning
- Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds (NeurIPS 2025 · similarity 0.91)
- Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds (ICML 2024 · similarity 0.90)
- Riemannian coordinate descent algorithms on matrix manifolds (ICML 2024 · similarity 0.89)
- Implicit Riemannian Optimism with Applications to Min-Max Problems (ICML 2025 · similarity 0.88)
- A Framework for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2024 · similarity 0.88)
- SERENA: A Unified Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-Convex Optimization (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.