Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-11
Main Authors: Qin, Lianke, Mitra, Saayan, Zhao, Song, Yang, Yuanyuan, Zhou, Tianyi
Format: Article
Language:English
Subjects:
Algorithms
Neural networks
Training
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422