Faster Randomized Methods for Orthogonality Constrained Problems

Boris Shustin, Haim Avron

Abstract

Recent literature has advocated the use of randomized methods for accelerating the solution of various matrix problems arising throughout data science and computational science. One popular strategy for leveraging randomization is to use it as a way to reduce problem size. However, methods based on this strategy lack sufficient accuracy for some applications. Randomized preconditioning is another approach for leveraging randomization, which provides higher accuracy. The main challenge in using randomized preconditioning is the need for an underlying iterative method, thus randomized preconditioning so far have been applied almost exclusively to solving regression problems and linear systems. In this article, we show how to expand the application of randomized preconditioning to another important set of problems prevalent across data science: optimization problems with (generalized) orthogonality constraints. We demonstrate our approach, which is based on the framework of Riemannian optimization and Riemannian preconditioning, on the problem of computing the dominant canonical correlations and on the Fisher linear discriminant analysis problem. For both problems, we evaluate the effect of preconditioning on the computational costs and asymptotic convergence, and demonstrate empirically the utility of our approach.

Introduction

In modern machine learning and data science, many fundamental tasks—such as Canonical Correlation Analysis (CCA), Fisher Linear Discriminant Analysis (FDA), and Principal Component Analysis (PCA)—require finding a set of vectors that satisfy orthogonality constraints. Mathematically, these problems involve optimization over the Stiefel Manifold, the set of all matrices with orthonormal columns.

As datasets grow to include millions of samples ($n$) and thousands of features ($d$), traditional "direct" solvers (e.g., Eigendecompositions) become computationally prohibitive, typically scaling at $O(nd^2)$. While randomized "sketch-and-solve" techniques have emerged to reduce problem size, they often hit an accuracy ceiling. This paper introduces a framework that bridges the gap between the speed of randomization and the high precision of iterative solvers through Randomized Riemannian Preconditioning.

Methodology

The proposed approach leverages the geometry of the optimization landscape to accelerate convergence. The framework consists of four primary components:

  1. Riemannian Optimization: Rather than treating orthogonality as a hard constraint to be managed via penalties, the authors treat the solution space as a smooth, curved manifold. Optimization is performed by "walking" along this surface, ensuring constraints are naturally satisfied.
  2. Randomized Preconditioning via Sketching: The convergence speed of iterative solvers is dictated by the "conditioning" of the data. The authors use matrix sketching techniques—specifically CountSketch or the Subsampled Randomized Hadamard Transform (SRHT)—to create a compressed, representative version of the data.
  3. Metric Selection: This sketch is used to define a new Riemannian metric (a way of measuring distance) on the manifold. By effectively stretching the coordinate system, the optimization landscape is transformed from a narrow, difficult-to-navigate valley into a more uniform, circular bowl. This allows iterative methods like Conjugate Gradient to converge significantly faster.
  4. Warm-Starting: To further boost efficiency, the algorithm uses a fast, low-accuracy "sketch-and-solve" result as the initial starting point for the high-accuracy iterative process.

Theoretical and Empirical Results

Independence from Data Conditioning

A key theoretical insight of this work is that the preconditioned Hessian (the matrix describing local curvature) has a condition number bounded by a small constant. This implies that the algorithm's performance is largely independent of how "messy" or ill-conditioned the input data is, providing a "Las Vegas" type guarantee: the method is almost always fast and always returns a high-accuracy solution.

Performance Benchmarks

The authors evaluated the framework on several large-scale and synthetic datasets, including MNIST, MEDIANILL, and COVTYPE (over 581,000 samples). Key findings include:

  • Rapid Convergence: On complex problems where un-preconditioned methods failed to converge within 1,000 iterations, the randomized preconditioned approach reached solutions in fewer than 25 iterations.
  • Scalability: On the COVTYPE dataset, the iterative method achieved high precision significantly faster than standard direct solvers.
  • Robustness: In tests using synthetic, highly ill-conditioned matrices (condition numbers up to $10^{14}$), the preconditioned method maintained steady convergence while traditional solvers plateaued or failed entirely.

Conclusion and Future Work

This framework demonstrates that randomized preconditioning is not limited to linear systems and regression but is a powerful tool for constrained manifold optimization. By changing the underlying geometry of the problem space rather than just the solver, the authors achieve significant speedups without sacrificing accuracy.

Future research directions include the development of "non-constant" preconditioners that account for the specific cost function being optimized, as well as extending the framework to other types of equality constraints beyond the Stiefel manifold. Additionally, moving from MATLAB prototypes to low-level C++ or BLAS-optimized implementations is expected to further widen the performance gap over traditional methods.

Summary updated

Abstract

Recent literature has advocated the use of randomized methods for accelerating the solution of various matrix problems arising throughout data science and computational science. One popular strategy for leveraging randomization is to use it as a way to reduce problem size. However, methods based on this strategy lack sufficient accuracy for some applications. Randomized preconditioning is another approach for leveraging randomization, which provides higher accuracy. The main challenge in using randomized preconditioning is the need for an underlying iterative method, thus randomized preconditioning so far have been applied almost exclusively to solving regression problems and linear systems. In this article, we show how to expand the application of randomized preconditioning to another important set of problems prevalent across data science: optimization problems with (generalized) orthogonality constraints. We demonstrate our approach, which is based on the framework of Riemannian optimization and Riemannian preconditioning, on the problem of computing the dominant canonical correlations and on the Fisher linear discriminant analysis problem. For both problems, we evaluate the effect of preconditioning on the computational costs and asymptotic convergence, and demonstrate empirically the utility of our approach.
BibTeX
@misc{shustin2021faster,
  author = {Boris Shustin and Haim Avron},
  title = {{Faster Randomized Methods for Orthogonality Constrained Problems}},
  year = {2021},
  eprint = {2106.12060},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.12060},
}
Figure