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

arXiv: https://arxiv.org/abs/2311.11429 · HTML: https://mlsanity.com/paper/2311.11429/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 56 of its 94 references that are in the map.
- First posted on arXiv 19 Nov 2023.

## Builds on (most cited first, 30 of 56)

- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Faster Dynamic Matrix Inverse for Faster LPs](https://mlsanity.com/paper/2004.07470/) (2020)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [A Faster Small Treewidth SDP Solver](https://mlsanity.com/paper/2211.06033/) (2022)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [SEGA: Variance Reduction via Gradient Sketching](https://mlsanity.com/paper/1809.03054/) (2018)
- [Optimal Sketching for Kronecker Product Regression and Low Rank Approximation](https://mlsanity.com/paper/1909.13384/) (2019)
- [A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path](https://mlsanity.com/paper/2011.05365/) (2020)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)

## Abstract (arXiv)

In this paper, we consider a heavy inner product identification problem, which generalizes the Light Bulb problem~(citeprr89): Given two sets A subset -1,+1d and B subset -1,+1d with |A|=|B| = n, if there are exact k pairs whose inner product passes a certain threshold, i.e., (a1, b1), cdots, (ak, bk) subset A × B such that forall i ∈ [k], langle ai,bi rangle ≥ ρ · d, for a threshold ρ ∈ (0,1), the goal is to identify those k heavy inner products. We provide an algorithm that runs in O(n2 ω / 3+ o(1)) time to find the k inner product pairs that surpass ρ · 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.