For the most popular distance metrics—the Euclidean distance (\(\ell _2\) -norm) and Manhattan distance (\(\ell _1\) -norm)—classic dimension-reduction (sketching) provide very efficient distance oracles [1]}, [2]}, [3]}.
However, in many real-world problems, these metrics do not adequately capture similarities between data points, and a long line of work has demonstrated that more complex (possibly learnable) metrics
can lead to substantially better prediction and data compression [4]}. In particular, many works over the last decade have been dedicated to extending various optimization problems beyond Euclidean/Manhattan distances, for example in (kernel) linear regression [5]}, approximate nearest neighbor [6]}, [7]}, sampling [8]}, matrix column subset selection [9]}, and statistical queries [10]}.
