Generalizations of Matrix Multiplication can solve the Light Bulb Problem

Josh Alman, Hengjie Zhang

The Light Bulb Problem: A Computational Challenge

The Light Bulb Problem, posed by Leslie Valiant in 1988, is a fundamental challenge in computational learning theory. Given $2n$ vectors of dimension $d$ chosen uniformly at random, the goal is to identify a single "planted pair" that possesses a correlation $\rho > 0$. While a naive search requires quadratic time ($O(n^2)$), researchers have historically split into two camps to optimize this:

  1. Locality-Sensitive Hashing (LSH): Highly effective for large correlations but slows toward $O(n^2)$ as $\rho$ approaches zero.
  2. Fast Matrix Multiplication (FMM): Provides sub-quadratic performance (currently around $O(n^{1.582})$) using algebraic identities, but its speed is independent of the correlation strength.

Until now, these two techniques remained largely separate, and FMM-based approaches were strictly constrained by the rank of standard matrix multiplication tensors.

Bridging the Gap: Efficacy and Imperfect Tensors

This paper introduces a breakthrough by demonstrating that exact matrix multiplication is not a prerequisite for solving the Light Bulb Problem. Instead, the authors propose using bilinear tensors that may be faster but less accurate. To evaluate these tensors, they introduce a new metric: efficacy ($\text{eff}$).

Efficacy measures the "signal-to-noise ratio" of a tensor. A tensor with high efficacy can distinguish the signal of the planted pair from random noise, even if the tensor omits certain terms or includes extraneous ones. This shift in perspective—from perfect multiplication to effective detection—allows for the use of tensors with lower ranks than those required for standard matrix multiplication.

The $T_{2112}$ Breakthrough

A centerpiece of this work is the design of a specific new tensor, $T_{2112}$, for $2 \times 2$ matrices. In standard algebraic complexity, Strassen’s algorithm is the benchmark for $2 \times 2$ multiplication with a rank of 7. The $T_{2112}$ tensor, however, has a rank of only 5. While it is an "imperfect" tensor, its high efficacy makes it superior for detection tasks.

Comparison of tensors, ranks, and resulting complexity bounds for the Light Bulb Problem.

By combining this tensor with bit-sampling LSH, the algorithm "steers" vectors into buckets such that the planted pair is more likely to land in high-efficacy tensor positions. This is the first algorithm to successfully merge the algebraic power of FMM with the probabilistic advantages of hashing.

Key Results and Implications

  • Performance Gains: For small tensors, the previous best complexity was $O(n^{1.872})$ (via Strassen). The $T_{2112}$ tensor improves this to $O(n^{1.797})$.
  • Correlation Sensitivity: Unlike traditional FMM, this hybrid approach actually accelerates as the correlation $\rho$ increases, inheriting the best properties of LSH.
  • A New Objective Function: The speed of these algorithms is determined by the ratio $\frac{\log(\text{rank})}{\log(\text{eff})}$. This provides a clear target for future tensor research.

Conclusion

This work proves that precision is often secondary to speed in detection tasks. By prioritizing efficacy over exactness, the authors have unlocked a new class of algorithms for the Light Bulb Problem. Future work may involve applying this "efficacy" framework to more complex methods like the "Laser Method," potentially setting new world records for algorithmic speed in high-dimensional data analysis.

Summary updated

Abstract

In the light bulb problem, one is given as input vectors $x_{1}, \ldots, x_{n}, y_{1}, \ldots, y_{n} \in\{-1,1\}^{d}$ which are all uniformly random. They are all chosen independently except for a planted pair $\left(x_{i^{*}}, y_{j^{*}}\right)$ which is chosen to have correlation $\rho$ for some constant $\rho\gt 0$. The goal is to find the planted pair. The light bulb problem was introduced over 30 years ago by L. Valiant, and is known to have many applications in data analysis, statistics, and learning theory. The naive algorithm runs in $\Omega\left(n^{2}\right)$ time, and algorithms based on Locality-Sensitive Hashing approach quadratic time as $\rho \rightarrow 0$. In 2012, G. Valiant gave a breakthrough algorithm running in time $O\left(n^{(5-\omega)} /(4-\omega)\right)\lt O\left(n^{1.615}\right)$, no matter how small $\rho\gt 0$ is, by making use of fast matrix multiplication. This was subsequently refined by Karppa, Kaski, and Kohonen in 2016 to running time $O\left(n^{2 \omega / 3}\right)\lt $ $O\left(n^{1.582}\right)$, but is essentially the only known approach for this important problem. In this paper, we propose a new approach based on replacing fast matrix multiplication with other variants and generalizations of matrix multiplication, which can be computed faster than matrix multiplication, but which may omit some terms one is supposed to compute, and include additional error terms. Our new approach can make use of a wide class of tensors which previously had no known algorithmic applications, including tensors which arise naturally as intermediate steps in border rank methods and in the Laser method. We further show that our approach can be combined with locality-sensitive hashing to design an algorithm whose running time improves as $\rho$ gets larger. To our knowledge, this is the first algorithm which combines fast matrix multiplication with hashing for the light bulb problem or any closest pair problem, and it leads to faster algorithms for small $\rho\gt 0$. We then focus on tensors for “multiplying“ $2 \times 2$ matrices; using such small tensors is typically required for practical algorithms. In this setting, the best prior algorithm, using Strassen’s algorithm for matrix multiplication, yields a running time of only $O\left(n^{1.872}\right)$. We introduce a new such low-rank tensor we call $T_{2112}$, which has omissions and errors compared to matrix multiplication, and using it, we design a new algorithm for the light bulb problem which runs in time $O\left(n^{1.797}\right)$. We also explain why we are optimistic that this approach could yield asymptotically faster algorithms for the light bulb problem.
BibTeX
@inproceedings{alman2023generalizations,
  author = {Josh Alman and Hengjie Zhang},
  title = {{Generalizations of Matrix Multiplication can solve the Light Bulb Problem}},
  booktitle = {FOCS},
  year = {2023},
  url = {https://openreview.net/forum?id=XYY3shENDY},
}
Figure