An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale

• URL: http://arxiv.org/abs/2602.14656v1
• Date: Mon, 16 Feb 2026 11:27:04 GMT
• Title: An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale
• Abstract summary: This work revisits and improves on the ideas behind Landing, enabling the inclusion of modern adaptives.<n>Remarkably, these improvements come at little to no cost, and reduce the number of required hyperparemeters.<n>Our algorithm POGO is fast and GPU-friendly, consisting of only 5 matrix products.
• Score: 17.725823339805697
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Orthogonality constraints are ubiquitous in robust and probabilistic machine learning. Unfortunately, current optimizers are computationally expensive and do not scale to problems with hundreds or thousands of constraints. One notable exception is the Landing algorithm (Ablin et al., 2024) which, however comes at the expense of temporarily relaxing orthogonality. In this work, we revisit and improve on the ideas behind Landing, enabling the inclusion of modern adaptive optimizers while ensuring that orthogonal constraints are effectively met. Remarkably, these improvements come at little to no cost, and reduce the number of required hyperparemeters. Our algorithm POGO is fast and GPU-friendly, consisting of only 5 matrix products, and in practice maintains orthogonality at all times. On several challenging benchmarks, POGO greatly outperforms recent optimizers and shows it can optimize problems with thousands of orthogonal matrices in minutes while alternatives would take hours. As such, POGO sets a milestone to finally exploit orthogonality constraints in ML at scale. A PyTorch implementation of POGO is publicly available at https://github.com/adrianjav/pogo.

Related papers

• GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra [13.9407640377773]
  This paper introduces rlaopt, a PyTorch-based package for large-scale optimization and scientific computing using randomized numerical linear algebra (RandNLA)<n>Rlaopt addresses this gap by providing GPU-enabled solvers for positive-definite linear systems and convex empirical risk minimization with constraints and regularizers.<n>Rlaopt automatically checks compatibility with the selected solver and performs the required problem decomposition.
  arXiv  Detail & Related papers  (2026-09-08T02:14:05Z)
• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  We show how to use cryptography to improve the time complexity of solving computational problems.<n>We show that under standard cryptographic assumptions, we can design algorithms that are determinantally faster than existing ones.
  arXiv  Detail & Related papers  (2025-02-18T17:08:59Z)
• Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization [2.0052993723676895]
  We construct an analogous relax-then-round strategy for low-rank optimization problems.<n>For a given $n times m$ semi-orthogonal matrix, we derive a purely multiplicative approximation ratio for our algorithm.<n>We extend our approach to generic low-rank optimization problems by developing new semidefinite relaxations.
  arXiv  Detail & Related papers  (2025-01-06T11:31:41Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  This article provides new practical and theoretical developments for the landing algorithm. First, the method is extended to the Stiefel manifold. We also consider variance reduction algorithms when the cost function is an average of many functions.
  arXiv  Detail & Related papers  (2023-03-29T07:36:54Z)
• FastDOG: Fast Discrete Optimization on GPU [23.281726932718232]
  We present a massively parallel Lagrange decomposition method for solving 0-1 integer linear programs occurring in structured prediction. Our primal and dual algorithms require little synchronization between subproblems and optimization over BDDs. We come close to or outperform some state-of-the-art specialized algorithms while being problem agnostic.
  arXiv  Detail & Related papers  (2021-11-19T15:20:10Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.