Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training
This work addresses a computational bottleneck in neural network training, offering a speedup for practitioners, but it is incremental as it builds on existing problems and methods.
The paper tackles the heavy inner product identification problem, a generalization of the Light Bulb problem, by providing an algorithm that runs in O(n^{2ω/3+o(1)}) time to find k pairs with inner products above a threshold, which speeds up neural network training with ReLU activation.
In this paper, we consider a heavy inner product identification problem, which generalizes the Light Bulb problem~(\cite{prr89}): Given two sets $A \subset \{-1,+1\}^d$ and $B \subset \{-1,+1\}^d$ with $|A|=|B| = n$, if there are exact $k$ pairs whose inner product passes a certain threshold, i.e., $\{(a_1, b_1), \cdots, (a_k, b_k)\} \subset A \times B$ such that $\forall i \in [k], \langle a_i,b_i \rangle \geq ρ\cdot d$, for a threshold $ρ\in (0,1)$, the goal is to identify those $k$ heavy inner products. We provide an algorithm that runs in $O(n^{2 ω/ 3+ o(1)})$ time to find the $k$ inner product pairs that surpass $ρ\cdot d$ threshold with high probability, where $ω$ is the current matrix multiplication exponent. By solving this problem, our method speed up the training of neural networks with ReLU activation function.