Given matrix $A \in \Bbb R^{m \times m}$, let function $f : \Bbb R^m \to \Bbb R$ defined by
$$f(x) := x^T A x$$
Suppose there are $n \gg m$ points $a_i \in \Bbb R^m$. I seek to find
$$\min_{i \in [n]} f(a_i)$$
or, at least an approximation of this this quantity with bounded error (likely depending on the geometric distribution of $\{a_i\}$) with sub-linear computational complexity in $n$. We can assume that any pre-processing of $\{a_i\}$ is free.
I have seen some results in computational geometry for Nearest Neighbour Search (NNS) which makes me think that this might be possible, with an error bound depending on something like the mutual coherence of the evaluation points, but I think to compute this exactly requires the linear complexity in $n$.