Research map / Learning theory and algorithms / Matrix and tensor methods
Optimization without Retraction on the Random Generalized Stiefel Manifold
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 a stochastic "landing" method that optimizes over the random generalized Stiefel manifold {X: X^T B X = I} using only random estimates of B, avoiding retractions and matrix factorizations, with convergence guarantees to critical points.
Problem
Optimizing over {X: X^T B X = I_p} when B is only available through random estimates, where retractions and full-matrix factorizations are costly or infeasible.
Approach
Infeasible landing iteration whose field sums a relative ascent direction (using sampled B) and an orthogonal penalty-gradient term, analyzed with a smooth Fletcher augmented Lagrangian merit function so it converges in expectation even under noisy constraints.
Key results
- On the deterministic GEVP (n=1000, p=500), the landing method with Psi_B(X) converges fastest in time among compared methods, being more robust to step-size and omega than PLAM.
- In stochastic CCA on split MNIST, the online landing method outperforms averaged Riemannian gradient descent in objective value after the first epoch while using O(n(p+r)) memory instead of O(n^2).
- The landing iteration achieves the same O(1/K) rate as deterministic Riemannian gradient descent and O(1/sqrt(K)) rate in expectation under stochastic constraints.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the landing update with Ψ_B(X) instead of Riemannian steepest descent, PLAM, or landing with Ψ^R_B(X) | GEVP · GEVP (n = 1000, p = 500) | time to convergence | Helped |
| Use the landing update with Ψ_B(X) instead of PLAM | GEVP · GEVP (n = 1000, p = 500) | robustness to parameter choice | Helped |
| Use online landing instead of averaged Riemannian gradient descent | Stochastic CCA · Split MNIST | objective value | Helped |
| Use the averaged method after its first pass through the data rather than online landing | Stochastic CCA · Split MNIST | constraint violation, 𝒩(X) | Helped |
| Use the averaged method rather than online landing | Stochastic ICA · Synthetic dataset | Amari distance | Mixed |
| Replace retractions with the landing formula | Generalized Stiefel optimization · Generalized Stiefel manifold | per-iteration complexity: \mathcal{O}(n^2p) -> \min\{ \mathcal{O}(n^2p), \mathcal{O}(npr)\} | Helped |
| Use online landing without forming the full covariance matrix | Stochastic CCA · Split MNIST | memory complexity: \mathcal{O}(n^2) -> \mathcal{O}(n(p+r)) | Helped |
| Use stochastic landing with a diminishing step-size | Generalized Stiefel optimization · Stochastic constraints | convergence rate: \mathcal{O}(1/K) -> \mathcal{O}(1/\sqrt{K}) | Helped |
Limitations
- Convergence in the stochastic case requires line segments between iterates to remain in the safe region with probability one, which is not guaranteed in general.
- Requires bounded relative ascent direction and bounded multiplier derivative assumptions on a compact safe region.
- Method is sensitive to choice of step-size eta and penalty omega, though less than PLAM.
Experimental setup
Datasets: MNIST synthetic Laplace ICA data random GEVP matrices
Benchmarks: generalized eigenvalue problem (n=1000, p=500) stochastic CCA on split MNIST stochastic ICA on synthetic data
Metrics: objective value constraint violation N(X) wall-clock time Amari distance
Baselines: Riemannian gradient descent with Cholesky-QR retraction PLAM Riemannian gradient descent with rolling averaged covariance
Builds on: landing method Fletcher's augmented Lagrangian Riemannian gradient descent PLAM
Closest papers by meaning
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.87)
- Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold (ICML 2025 · similarity 0.86)
- StelLA: Subspace Learning in Low-rank Adaptation using Stiefel Manifold (NeurIPS 2025 · similarity 0.85)
- Riemannian coordinate descent algorithms on matrix manifolds (ICML 2024 · similarity 0.85)
- Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds (NeurIPS 2025 · similarity 0.85)
- SERENA: A Unified Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-Convex Optimization (ICML 2025 · similarity 0.85)
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.