mlsanityData to 14 Oct 2026

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

arXiv 2311.11429 ↗First posted 19 Nov 2023cs.LGcited by 0

Not on the map. Why?

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.

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

56 of 94 references.

References · 56

  1. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 203
  2. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 179
  3. 2014Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)cited by 109
  4. 2023Fast Attention Requires Bounded Entriescited by 102
  5. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  6. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  7. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  8. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  9. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  10. 2020A Refined Laser Method and Faster Matrix Multiplicationcited by 56
  11. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  12. 2023Attention Scheme Inspired Softmax Regressioncited by 49
38 more
  1. 2018Approximate Nearest Neighbor Search in High Dimensionscited by 47
  2. 2017Relative Error Tensor Low Rank Approximationcited by 45
  3. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 44
  4. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 44
  5. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  6. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  7. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  8. 2022A Faster Small Treewidth SDP Solvercited by 36
  9. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  10. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  11. 2021Scaling Neural Tangent Kernels via Sketching and Random Featurescited by 32
  12. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  13. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  14. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  15. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  16. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  17. 2020A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Pathcited by 29
  18. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  19. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  20. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  21. 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
  22. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
  23. 2018BourGAN: Generative Networks with Metric Embeddingscited by 22
  24. 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
  25. 2022A Sublinear Adversarial Training Algorithmcited by 22
  26. 2022Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenancecited by 22
  27. 2018Subspace Embedding and Linear Regression with Orlicz Normcited by 19
  28. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  29. 2014Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)cited by 15
  30. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  31. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  32. 2020Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matchingcited by 14
  33. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  34. 2016Distributed Low Rank Approximation of Implicit Functions of a Matrixcited by 12
  35. 2018Towards a Zero-One Law for Column Subset Selectioncited by 12
  36. 2020Average Case Column Subset Selection for Entrywise ℓ1-Norm Losscited by 12
  37. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 12
  38. 2017Near Optimal Sketching of Low-Rank Tensor Regressioncited by 11

50 most cited of 56 All 56 (JSON)

Built on by

Not cited yet.