Fast Heavy Inner Product Identification Between Weights and Inputs in
  Neural Network Training
Lianke Qin Saayan Mitra Zhao Song Yuanyuan Yang Tianyi Zhou
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 \rho \cdot d$, for a threshold $\rho \in
(0,1)$, the goal is to identify those $k$ heavy inner products. We provide an
algorithm that runs in $O(n^{2 \omega / 3+ o(1)})$ time to find the $k$ inner
product pairs that surpass $\rho \cdot d$ threshold with high probability,
where $\omega$ is the current matrix multiplication exponent. By solving this
problem, our method speed up the training of neural networks with ReLU
activation function.