Online Learning in The Manifold of Low-Rank Matrices

Uri Shalit, Daphna Weinshall, Gal Chechik

TL;DR

LORETA is a new online learning algorithm that optimizes models over the manifold of low-rank matrices. By replacing expensive Singular Value Decompositions (SVD) with an efficient "retraction" operation, it achieves the regularization benefits of low-rank constraints with a fraction of the computational cost. This makes it ideal for high-dimensional tasks like document retrieval and large-scale image classification.

What Problem Does This Paper Address?

In many machine learning tasks—such as metric learning, collaborative filtering, and multi-task learning—models are represented as large matrices. To prevent overfitting and save memory, researchers often enforce a low-rank constraint. This means the matrix can be compressed into a product of two much smaller matrices.

However, maintaining this low-rank structure during "online" learning (where the model updates one example at a time) is difficult:

  1. Computational Cost: The standard way to enforce low rank is to perform an SVD after every update, which is prohibitively slow for large matrices.
  2. Numerical Instability: A common shortcut is to factor the matrix into $W = AB^T$ and optimize $A$ and $B$ separately. Unfortunately, this often leads to unstable optimization and poor convergence.

The authors seek a middle ground: an algorithm that is as stable as full-matrix optimization but as efficient as factored models.

Methods

To achieve this, the authors turn to Riemannian Optimization. Instead of treating the matrix as a flat grid of numbers, they treat the set of all rank-$k$ matrices as a smooth "manifold" (a curved surface in high-dimensional space).

Illustration of a gradient step in the tangent space followed by a retraction back to the manifold.

The core of their algorithm, LORETA (Low-Rank Efficient Tangent-space Algorithm), involves two main steps:

  1. Riemannian Gradient Step: Instead of taking a standard gradient step that might "fly off" the manifold, they project the gradient onto the tangent space of the current low-rank matrix.
  2. Second-Order Retraction: To bring the model back onto the manifold of low-rank matrices, they use a "retraction" instead of a full projection (SVD). They derive a specific second-order retraction that can be computed very efficiently.

For the common case of rank-one gradients (typical in bilinear similarity and multi-label tasks), LORETA achieves a runtime and memory complexity of $O((n + m)k)$, where $n \times m$ are the matrix dimensions and $k$ is the rank. This is a massive improvement over the $O(nm \cdot \min(n,m))$ cost of standard SVD-based approaches.

Datasets

The authors evaluated LORETA on two distinct high-dimensional problems:

  • 20 Newsgroups: A classic text dataset used here to learn a bilinear similarity measure between documents. Documents were represented as high-dimensional vectors based on word counts.
  • ImageNet (2010 Challenge subset): Used for a multi-label image ranking task involving 1,661 classes. Images were represented using a "bag of words" approach on SIFT features.

Key Insights and Ideas

  • Retraction vs. Projection: The "aha moment" is that you don't actually need the closest point on the manifold (the projection) to ensure convergence. Any "retraction"—an operation that moves you back to the manifold in the right general direction—is sufficient. This opens the door to much faster formulas.
  • Stability through Geometry: By treating the optimization as occurring on a manifold, LORETA avoids the "exploding" gradients and instabilities often seen when simply multiplying two matrices $A$ and $B$ and updating them independently.
  • Adaptive Regularization: LORETA essentially learns a linear projection of the data into a lower-dimensional space that is specifically tailored to the task at hand, rather than relying on pre-selected features (like PCA).

Key Results

Performance of LORETA compared to baselines on 20 Newsgroups and ImageNet datasets. Source, p. 8

Performance of LORETA compared to baselines on 20 Newsgroups and ImageNet datasets.
  • Document Similarity: On the 20 Newsgroups task, LORETA improved mean average precision (mAP) by 33% compared to a full-rank model trained on a pre-selected subset of features with the same memory footprint. It also significantly outperformed standard "Passive-Aggressive" factored models.
  • Image Ranking: In the ImageNet task, LORETA showed consistent improvements over standard methods like the Matrix Perceptron. It scaled gracefully to over 1,600 classes, proving that low-rank optimization is a viable path for "extreme" classification problems.
  • Efficiency: The algorithm maintained a linear scaling relationship with the number of features and classes, making it practical for real-world, large-scale systems.

Limitations and Future Work

  • Fixed Rank: The rank $k$ is a hyperparameter that must be chosen in advance. The paper does not discuss a way to automatically determine or adapt the rank during training.
  • Gradient Assumptions: While the $O((n+m)k)$ complexity is impressive, it relies on the gradients being low-rank (specifically rank-one). While common in many ML losses (like hinge loss or squared loss on vectors), it might not apply to all optimization problems.
  • Future Directions: The authors suggest that this manifold approach could be extended to other types of constraints, such as positive semi-definite (PSD) matrices, which are common in kernel learning.

Summary updated

Abstract

When learning models that are represented in matrix forms, enforcing a low-rank constraint can dramatically improve the memory and run time complexity, while providing a natural regularization of the model. However, naive approaches for minimizing functions over the set of low-rank matrices are either prohibitively time consuming (repeated singular value decomposition of the matrix) or numerically unstable (optimizing a factored representation of the low rank matrix). We build on recent advances in optimization over manifolds, and describe an iterative online learning procedure, consisting of a gradient step, followed by a second-order retraction back to the manifold. While the ideal retraction is hard to compute, and so is the projection operator that approximates it, we describe another second-order retraction that can be computed efficiently, with run time and memory complexity of O((n+m)k) for a rank-k matrix of dimension m x n, given rank one gradients. We use this algorithm, LORETA, to learn a matrix-form similarity measure over pairs of documents represented as high dimensional vectors. LORETA improves the mean average precision over a passive- aggressive approach in a factorized model, and also improves over a full model trained over pre-selected features using the same memory requirements. LORETA also showed consistent improvement over standard methods in a large (1600 classes) multi-label image classification task.
BibTeX
@inproceedings{shalit2010online,
  author = {Uri Shalit and Daphna Weinshall and Gal Chechik},
  title = {{Online Learning in The Manifold of Low-Rank Matrices}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
}
Figure