mlsanityData to 7 Oct 2026

Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations

arXiv 2212.11408 ↗First posted 21 Dec 2022cs.DS cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resolution hashing data-structure for fast pairwise summation estimation. Given a data-set X subset ℝd, a binary function f:ℝd× ℝd→ ℝ, and a point y ∈ ℝd, the Pairwise Summation Estimate PSEX(y) := frac1|X| sumx ∈ X f(x,y). For any given data-set X, we need to design a data-structure such that given any query point y ∈ ℝd, the data-structure approximately estimates PSEX(y) in time that is sub-linear in |X|. Prior works on this problem have focused exclusively on the case where the data-set is static, and the queries are independent. In this paper, we design a hashing-based PSE data-structure which works for the more practical textitdynamic setting in which insertions, deletions, and replacements of points are allowed. Moreover, our proposed Adam-Hash is also robust to adaptive PSE queries, where an adversary can choose query qj ∈ ℝd depending on the output from previous queries q1, q2, dots, qj-1.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 31 of its 60 references that are in the map. First posted on arXiv 21 Dec 2022.

Builds on

31 of 60 references.

References · 31

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2016Delving into Transferable Adversarial Examples and Black-box Attackscited by 530
  3. 2016Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samplescited by 439
  4. 2017Adversarial Examples: Attacks and Defenses for Deep Learningcited by 350
  5. 2020Flows for simultaneous manifold learning and density estimationcited by 117
  6. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  7. 2021Machine Learning for Electronic Design Automation: A Surveycited by 71
  8. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  9. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  10. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  11. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  12. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
19 more
  1. 2020GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networkscited by 42
  2. 2022A Faster Small Treewidth SDP Solvercited by 36
  3. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  4. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  5. 2018Hashing-Based-Estimators for Kernel Density in High Dimensionscited by 31
  6. 2020A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Pathcited by 29
  7. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  8. 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
  9. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  10. 2022A Sublinear Adversarial Training Algorithmcited by 22
  11. 2022Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenancecited by 22
  12. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  13. 2017A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Modelscited by 15
  14. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  15. 2020On Adaptive Distance Estimationcited by 10
  16. 2021DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Searchcited by 8
  17. 2021Terminal Embeddings in Sublinear Timecited by 6
  18. 2022Adore: Differentially Oblivious Relational Database Operatorscited by 6
  19. 2018Multi-Resolution Hashing for Fast Pairwise Summationscited by 2

Built on by

Cited by year

Citing papers per year: 2023: 9; 2024: 3; 2025: 2.

14 papers.

Sort:

By area:

  1. 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
  2. 2024BiSHop: Bi-Directional Cellular Learning for Tabular Data with Generalized Sparse Modern Hopfield Modelcited by 21
  3. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  4. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
  5. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  6. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  7. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  8. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  9. 2023Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?cited by 8
  10. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  11. 2024Differentially Private Kernel Density Estimationcited by 2
  12. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
2 more
  1. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  2. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0