# Online Adaptive Mahalanobis Distance Estimation

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

## Key facts

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

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Delving into Transferable Adversarial Examples and Black-box Attacks](https://mlsanity.com/paper/1611.02770/) (2016)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [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)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (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)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [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)
- [GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks](https://mlsanity.com/paper/2007.03179/) (2020)
- [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)
- [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 Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)

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