arXiv:2505.12378math.OCcs.LG2025-05ICML被引 6

提出随机子流形方法,让大规模正交约束优化更快更高效。

Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method

  • 每轮更新只在随机选的子流形上进行,降低计算开销。
  • 理论证明在非凸和随机优化下均收敛,适用范围广。
  • 适合处理大规模机器学习中的正交约束问题。

正交约束优化广泛存在于机器学习等领域。黎曼优化通过将约束集赋予黎曼流形结构,在流形上原生优化,但随着变量规模增大,重投影操作的计算成本过高,限制了其在大规模问题上的应用。为此,本文提出一种新方法:将每次更新限制在随机选取的子流形上,显著降低每轮迭代复杂度。设计了两种子流形采样策略,并对方法的收敛性进行了理论分析,涵盖一般非凸函数、满足黎曼Polyak-Łojasiewicz条件的函数及随机优化场景。此外,还展示了该方法可推广至由正交流形导出的商流形。大量实验验证了所提方法在多种问题上的有效性。

原文摘要 · Abstract (English)

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.

优化黎曼几何大规模

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。