# Associative Memories to Accelerate Approximate Nearest Neighbor Search
## 4 Dense, Unbiased Patterns
If \(d^{4}\ll k^{3}\) (note that we always have \(d\ll k\)), we expand the logarithm to obtain:  
\[\mathbb{P}(s(\mathcal{X}^{2},x^{0})\geq s(\mathcal{X}^{1},x^{0}))\leq e^{-td^ {2}+2 kd^{2}t^{2}+\mathcal{O}(kt^{4}d^{4})}\]  
Choosing \(t=\frac{1}{4k}\), we see that the term \(\mathcal{O}(kt^{4}d^{4})\) is in fact \(o(1)\), and therefore:  
\[\mathbb{P}(s(\mathcal{X}^{2},x^{0})\geq s(\mathcal{X}^{1},x^{0}))\leq e^{- \frac{d^{2}}{8k}}\]  
Thus, if \(k\ll d^{2}\) and \(q\ll e^{\frac{d^{2}}{8k}}\), we obtain:  
\[\mathbb{P}(\exists i\geq 2:s(\mathcal{X}^{i},x^{0})\geq s(\mathcal{X}^{1},x^{0 }))\to 0.\]  
On the other hand, if \(d\ll k\leq\mathcal{O}(\tilde{d}^{4/3})\), we choose \(t=k^{-5/4}\). Then, by the same expansion of the logarithm:  
\[\mathbb{P}(s(\mathcal{X}^{2},x^{0})\geq s(\mathcal{X}^{1},x^{0}))\leq\exp \left(-\frac{d^{2}}{k^{\frac{5}{4}}}+2\frac{d^{2}}{k^{\frac{3}{2}}}+\mathcal{ O}((\frac{d}{k})^{4})\right)\]  
Now, the \(-\frac{d^{2}}{k^{\frac{5}{4}}}\) will always dominate the \(\frac{d^{2}}{k^{\frac{5}{4}}}\)-term, and clearly, the \(\mathcal{O}\)-term is again \(o(1)\). Thus:  
\[\mathbb{P}(s(\mathcal{X}^{2},x^{0})\geq s(\mathcal{X}^{1},x^{0}))\leq\exp \left(-\frac{d^{2}}{k^{\frac{5}{4}}}\right)(1+o(1)).\]  
Since \(k\leq\mathcal{O}(d^{4/3})\), the exponent diverges, and we see that as long as \(\log q\ll\frac{d^{2}}{k^{\frac{5}{4}}}\), again:  
\[\mathbb{P}(\exists i\geq 2:s(\mathcal{X}^{i},x^{0})\geq s(\mathcal{X}^{1},x^{0 }))\to 0.\]  
We can easily check that our first condition \(-\frac{k^{-1/4}\varepsilon_{d}^{2}}{2t\sqrt{d}}+\log(k)\to-\infty\) is fulfilled in both cases: \(t=\frac{1}{4k}\) and \(t=k^{-5/4}\), if \(d\ll k\). Again, in a similar way, one can treat the case of an input pattern that is a corrupted version of one of the vectors in the database. **Corollary 2**. : _Assume that the input pattern \(x^{0}\) has a macroscopic overlap with one of the patterns, say \(x^{1}\), in the database, i.e., \(\sum_{l=1}^{d}x_{l}^{0}x_{l}^{1}=\alpha d\), for \(a\in(0,1)\). The algorithm described above works asymptotically correctly and is efficient if:_  
1. \(d\ll k\ll d^{2}\)_, i.e.,_ \(\frac{k}{d^{2}}\to 0\) _and_ \(\frac{k}{d}\to\infty\)_,_
2. _and either_ \(qe^{-\frac{1}{8}\frac{d^{2}}{k^{\frac{5}{4}}}}\to 0\) _if_ \(d^{4}\ll k^{3}\)_,__._
3. _or_ \(qe^{-\frac{4^{4}\beta^{2}}{k^{\frac{2}{3}}}}\to 0\) _if_ \(k\leq Cd^{\frac{4}{3}}\) _for some_ \(C>0\)_._  
Proof. : The proof follows the lines of the proof of Theorem 2 by using the condition that \(\sum_{l=1}^{d}x_{l}^{0}x_{l}^{1}=\alpha d\). **Remark 2**. : _In the spirit of [29], one might wonder how far taking a higher power than two of \(\sum_{l=1}^{d}x_{l}^{0}x_{l}^{1}\) in the computation of the score function changes the results. Therefore, let us assume we take:_  
\[s(\mathcal{X}^{i},x^{0})=\sum_{\mu:x^{\mu}\in\mathcal{X}^{i}}\sum_{l_{1},-l_{ n}}^{d}x_{l_{1}}^{0}x_{l_{1}}^{0}\cdots x_{l_{n}}^{\mu}x_{l_{n}}^{\mu}. \tag{4}\]  
_Then, of course, in the setting of the proof of Theorem 2, we obtain:_  
\[s(\mathcal{X}^{i},x^{0})=d^{n}+\sum_{ \begin{subarray}{c}\mu:x^{\mu}\in \mathcal{X}^{1}\\ p\
eq 1\end{subarray} }\sum_{l_{1},-l_{n}}^{d}x_{l_{1}}^{0}x_{l_{1}}^{0}\cdots x_{l_ {n}}^{\mu}x_{l_{n}}^{\mu}\]  
_so we gain in the exponent. However, the probability that \(s(\mathcal{X}^{1},x^{0})\) is smaller than \(s(\mathcal{X}^{1},x^{0})\) is then much more difficult to estimate. As a matter of fact, none of the techniques used in Sections 2 and 3 work, because a higher power cannot be linearized by Gaussian integration, on the one hand, and the exponential of powers larger than two Gaussian random variables are not integrable. A possible strategy could include exponential bounds as in Proposition 3.2. in [14]. From here one, also learns that in the Hopfield model with \(N\) neurons and \(n\)-spin interaction (\(n\geq 3\)), the storage capacity grows like \(N^{p-1}\). A similar model was discussed in [29], where it is shown that in principle, the problems sketched above can be overcome.