Few-Shot Data-Driven Algorithms for Low Rank Approximation

Piotr Indyk, Tal Wagner, David WoodruffNeurIPS 2021 · OpenReview

TL;DR

This paper introduces highly efficient "few-shot" algorithms for Low Rank Approximation (LRA) that learn optimal sketching matrices from just one or a few training examples. By replacing heavy black-box optimization with analytic closed-form solutions and a simplified loss function, the authors achieve up to a 10x reduction in training time while maintaining or exceeding the accuracy of state-of-the-art data-driven methods.

What Problem Does This Paper Address?

Low Rank Approximation (LRA) is a cornerstone of modern data science, used to compress massive datasets while preserving their essential structure. While the Singular Value Decomposition (SVD) provides the mathematically perfect LRA, it is computationally prohibitive for "big data."

To solve this, researchers use sketching: multiplying a large matrix $A$ by a smaller, sparse matrix $S$ to reduce its dimensions before processing. Traditionally, $S$ was chosen randomly (data-oblivious). Recently, "data-driven" methods like IVY began using machine learning to optimize $S$ based on past data. However, these methods have a high "training tax": they require massive amounts of data, specialized GPU hardware, and differentiable SVD implementations, which are slow and complex.

The authors ask: Can we get the accuracy gains of data-driven LRA without the massive computational overhead?

Methods

The paper proposes two primary algorithms that move away from "black-box" learning toward analytic, mathematically grounded techniques:

  1. 1Shot2Vec (Closed-Form): This algorithm requires no iterative learning. It takes a single training matrix, partitions it into blocks (matching the sparsity pattern of the sketching matrix), and extracts the top singular vectors of those blocks to set the weights of $S$. It is entirely "closed-form," meaning it requires no GPUs or gradient descent.
  2. FewShotSGD: For cases where a little learning is preferred, the authors designed a new loss function. Unlike previous methods that require differentiating through an SVD (a slow process), this loss function is a low-degree polynomial that is independent of the sketching variables during the SVD step. This allows the model to converge to a local minimum in just 2 or 3 steps of Stochastic Gradient Descent (SGD).

Both methods can be "safeguarded" by concatenating a standard random sketching matrix to the learned one, ensuring they never perform significantly worse than classical randomized algorithms.

Datasets

The authors evaluated their methods on three publicly available datasets commonly used in LRA research:

  • Logo: A video dataset.
  • Eagle: Another video-based dataset.
  • Hyper: Hyperspectral images (1024 x 768).

These datasets were chosen to allow direct comparison with previous baselines like IVY and Butterfly.

Key Insights and Ideas

  • Analytic over Black-Box: The most significant insight is that the "optimal" sketching matrix has a clear mathematical meaning. Instead of letting a neural network guess the weights, we can extract them directly from the singular vectors of the training data.
  • Interpretability: Unlike previous learned matrices which look like random noise, the matrices produced by 1Shot2Vec are interpretable—their entries are literally the "heavy" directions (principal components) of the data blocks.
  • Decoupling the SVD: By redesigning the loss function to compute the SVD on the input matrix $A$ (which is independent of the sketching matrix $S$) rather than on the sketched matrix $SA$, the authors eliminated the need for "AutoGrad" and differentiable SVDs, which were the primary bottlenecks in previous work.
  • The Power of Few-Shot: The paper demonstrates that LRA structure is consistent enough that seeing just 1 to 3 examples is often sufficient to outperform data-oblivious methods.

Key Results

Performance comparison on Logo, Eagle, and Hyper datasets.
  • Training Speed: The proposed methods are significantly faster to train. As seen in the performance graphs above, 1Shot2Vec (green triangle) and FewShotSGD (red/blue markers) achieve target errors almost instantly. For example, on the Logo dataset, 1Shot2Vec reaches its target error in ~10 seconds, while the previous state-of-the-art (IVY) took over 143 seconds to reach the same level.
  • Sample Efficiency: In the "few-shot" regime (training on only 1-3 matrices), the new algorithms consistently outperformed baselines like IVY and Butterfly, which typically require dozens of matrices to generalize well.
  • Inference Speedup: All sketch-based methods (including the authors') provided an average 11.6x speedup over exact SVD during the testing phase.
  • Hybrid Potential: Using 1Shot1Vec to initialize the weights of a many-shot learner (like IVY) led to faster convergence and better final accuracy than starting from random weights.

Limitations and Future Work

  • Fixed Sparsity Pattern: The algorithms currently optimize the values within the sketching matrix but keep the locations of non-zero entries fixed (chosen at random). Learning the optimal sparsity pattern itself remains a difficult, discrete optimization problem.
  • Sparsity Constraints: The experiments primarily focused on matrices with only one non-zero entry per column. While the appendix explores higher sparsity (e.g., 8 entries per column), more work is needed to see how these analytic methods scale with very dense sketches.
  • Data Bias: As with all data-driven methods, there is a risk of the algorithm over-fitting to a specific dataset, though the authors' "safeguard" mechanism partially mitigates this.

Summary updated

Abstract

Recently, data-driven and learning-based algorithms for low rank matrix approximation were shown to outperform classical data-oblivious algorithms by wide margins in terms of accuracy. Those algorithms are based on the optimization of sparse sketching matrices, which lead to large savings in time and memory during testing. However, they require long training times on a large amount of existing data, and rely on access to specialized hardware and software. In this work, we develop new data-driven low rank approximation algorithms with better computational efficiency in the training phase, alleviating these drawbacks. Furthermore, our methods are interpretable: while previous algorithms choose the sketching matrix either at random or by black-box learning, we show that it can be set (or initialized) to clearly interpretable values extracted from the dataset. Our experiments show that our algorithms, either by themselves or in combination with previous methods, achieve significant empirical advantage over previous work, improving training times by up to an order of magnitude toward achieving the same target accuracy.
BibTeX
@inproceedings{indyk2021few,
  author = {Piotr Indyk and Tal Wagner and David Woodruff},
  title = {{Few-Shot Data-Driven Algorithms for Low Rank Approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=6dUJPrPPUau},
}
Figure