mlsanityData to 7 Oct 2026

Online Adaptive Mahalanobis Distance Estimation

arXiv 2309.01030 ↗First posted 2 Sep 2023cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Mahalanobis metrics are widely used in machine learning in conjunction with methods like k-nearest neighbors, k-means clustering, and k-medians clustering. Despite their importance, there has not been any prior work on applying sketching techniques to speed up algorithms for Mahalanobis metrics. In this paper, we initiate the study of dimension reduction for Mahalanobis metrics. In particular, we provide efficient data structures for solving the Approximate Distance Estimation (ADE) problem for Mahalanobis distances. We first provide a randomized Monte Carlo data structure. Then, we show how we can adapt it to provide our main data structure which can handle sequences of textitadaptive queries and also online updates to both the Mahalanobis metric matrix and the data points, making it amenable to be used in conjunction with prior algorithms for online learning of Mahalanobis metrics.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 56 of its 104 references that are in the map. First posted on arXiv 2 Sep 2023.

Builds on

56 of 104 references.

References · 56

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2016Practical Black-Box Attacks against Machine Learningcited by 893
  3. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  4. 2016Delving into Transferable Adversarial Examples and Black-box Attackscited by 530
  5. 2016Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samplescited by 439
  6. 2015Strategic Classificationcited by 256
  7. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 200
  8. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 178
  9. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  10. 2023Fast Attention Requires Bounded Entriescited by 102
  11. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  12. 2015Generalization in Adaptive Data Analysis and Holdout Reusecited by 76
38 more
  1. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  2. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  3. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  4. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  5. 2017Relative Error Tensor Low Rank Approximationcited by 45
  6. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  7. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  8. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 43
  9. 2020GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networkscited by 42
  10. 2022A Faster Small Treewidth SDP Solvercited by 36
  11. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  12. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  13. 2021Scaling Neural Tangent Kernels via Sketching and Random Featurescited by 32
  14. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  15. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  16. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  17. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  18. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  19. 2021Understanding GNN Computational Graph: A Coordinated Computation, IO, and Memory Perspectivecited by 28
  20. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  21. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  22. 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
  23. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
  24. 2018BourGAN: Generative Networks with Metric Embeddingscited 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. 2022Dynamic Tensor Product Regressioncited by 17
  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. 2020Improved Guarantees for k-means++ and k-means++ Parallelcited by 12
  37. 2017Near Optimal Sketching of Low-Rank Tensor Regressioncited by 11
  38. 2021Optimal Sketching for Trace Estimationcited by 11

50 most cited of 56 All 56 (JSON)

Built on by

Not cited yet.