Deep learning has been widely used in many fields, but the model training process usually consumes massive computational resources and time. Therefore, designing an efficient neural network training method with a provable convergence guarantee is a fundamental and important research question. In this paper, we present a static half-space report data structure that consists of a fully connected two-layer neural network for shifted ReLU activation to enable activated neuron identification in sublinear time via geometric search. We also prove that our algorithm can converge in O(M2/ϵ2) time with network size quadratic in the coefficient norm upper bound M and error term ϵ.

In this paper, we consider a heavy inner product identification problem, which generalizes the Light Bulb problem ([1]): 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., $\{\left(a_{1}, b_{1}\right), \cdots,\left(a_{k}, b_{k}\right)\} \subset A \times B$ such that $\forall i \in[k],\left\langle a_{i}, b_{i}\right\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.