From Oja's Algorithm to the Multiplicative Weights Update Method with Applications

Dan GarberarXiv 2023 · DOI · arXiv

Abstract

Oja’s algorithm is a foundational method for online Principal Component Analysis (PCA), providing a memory-efficient way to estimate the leading eigenvector of a matrix stream. Despite its widespread use, its analysis has traditionally been viewed through the lens of specialized linear algebra. This paper establishes a fundamental connection between Oja’s algorithm and the Multiplicative Weights Update (MWU) method. By demonstrating that Oja’s updates are mathematically equivalent to MWU when applied to matrices sharing common eigenvectors, we derive a simple, "gap-free" regret analysis. Furthermore, this framework enables a memory-efficient algorithm for solving a broad class of non-convex optimization problems over the unit sphere, achieving global optima where standard first-order methods often fail.

Introduction

In machine learning and data science, finding the dominant direction of a dataset—eigenvector computation—is a primary task for dimensionality reduction, spectral clustering, and ranking algorithms. While the Power Method and Lanczos algorithms are standard for static datasets, Oja’s algorithm has long been the preferred "online" alternative. It allows for the iterative update of an eigenvector estimate as new data points arrive, without the need to store the entire covariance matrix.

However, the convergence analysis of Oja’s algorithm has historically been considered "brittle." Traditional proofs often rely on a "spectral gap"—the difference between the largest and second-largest eigenvalues. When this gap is small, convergence guarantees weaken significantly. This paper, authored by Dan Garber, provides a fresh perspective by bridging Oja’s algorithm with the Multiplicative Weights Update (MWU) method, a cornerstone of theoretical computer science. This connection not only simplifies the analysis but also extends the utility of Oja-style updates to complex non-convex optimization tasks.

The Core Connection: Oja as MWU

The central insight of this work is a mapping between the dynamics of Oja’s algorithm and the weights in MWU. Consider a sequence of symmetric matrices $A_1, \dots, A_T$ that share a common set of eigenvectors. Oja’s algorithm updates a unit vector $x_t$ as follows:

$$x_{t+1} \leftarrow \frac{(I + \eta A_t)x_t}{\|(I + \eta A_t)x_t\|}$$

Garber demonstrates that if one tracks the squared projection of the iterates $x_t$ onto the shared eigenvectors, these values evolve identically to the weights in the MWU algorithm. In this context, the normalization step in Oja’s algorithm—the denominator—functions as the "partition function" in MWU. This transformation shifts the problem from geometric updates on a sphere to a probabilistic update over eigenvalues, allowing researchers to apply the robust regret bounds of MWU to the problem of eigenvector estimation.

Gap-Free Regret Analysis

One of the most significant outcomes of this connection is the derivation of "gap-free" convergence rates. Traditional Power Method analyses are sensitive to the spectral structure of the matrix. In contrast, the MWU-based analysis provides a regret bound that does not depend on the spectral gap.

Specifically, for a sequence of matrices with eigenvalues in the range $[-1, 1]$, the regret scales with $\sqrt{T \log n}$. This ensures that Oja’s algorithm achieves an $\epsilon$-additive approximation of the leading eigenvalue in $O(\epsilon^{-2} \ln(n/\delta))$ iterations, regardless of how close the top eigenvalues are to one another.

Applications to Non-Convex Optimization

The paper extends these findings to solve a class of non-convex problems: minimizing a convex function of quadratic forms over the unit sphere. Standard first-order methods like gradient descent typically only guarantee convergence to a stationary point in non-convex settings. However, many of these problems possess a "tight" semidefinite relaxation, meaning the global optimum of the relaxation is a rank-one matrix.

The author introduces a hybrid algorithm (Algorithm 3) that combines Oja-style updates with subgradient descent. This method implicitly solves the semidefinite relaxation using only $O(n)$ space. This is a significant improvement over standard Matrix Multiplicative Weights (MMW) algorithms, which require $O(n^2)$ space to store and update full matrices. Theorem 4 of the paper proves that this hybrid approach converges to the global minimum of these non-convex problems with high probability.

Limitations and Future Directions

While the connection to MWU is powerful, it currently relies on the "Common Eigenvector Assumption." This assumes that the input matrices $A_t$ share the same eigenvectors, which is true for a static matrix but may not hold for arbitrary sequences of different matrices. The author conjectures that without this assumption, Oja’s algorithm might incur linear regret in an oblivious online setting—an open question for future research.

Additionally, the current analysis focuses on the top eigenvector. Extending this framework to find the top-$k$ eigenvectors (the principal subspace) remains a challenge, as the QR-decomposition typically used in subspace iteration does not map cleanly to the MWU framework.

Conclusion

By revealing that Oja’s algorithm is a disguised form of Multiplicative Weights Update, this work provides an elementary and unified framework for understanding online PCA. This bridge not only yields more robust, gap-free theoretical guarantees but also provides a memory-efficient path toward solving complex non-convex optimization problems in high-dimensional spaces.

Summary updated

Abstract

Oja's algorithm is a well known online algorithm studied mainly in the context of stochastic principal component analysis. We make a simple observation, yet to the best of our knowledge a novel one, that when applied to a any (not necessarily stochastic) sequence of symmetric matrices which share common eigenvectors, the regret of Oja's algorithm could be directly bounded in terms of the regret of the well known multiplicative weights update method for the problem of prediction with expert advice. Several applications to optimization with quadratic forms over the unit sphere in $\reals^n$ are discussed.
BibTeX
@misc{garber2023from,
  author = {Dan Garber},
  title = {{From Oja's Algorithm to the Multiplicative Weights Update Method with Applications}},
  year = {2023},
  eprint = {2310.15559},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.15559},
}
Figure