Dense Associative Memory Through the Lens of Random Features

We thank the reviewer for the thorough and insightful evaluation of our work. We are glad you found it interesting and beneficial to the ML community!

We will add a Related Work section in which we will review the results of

• Hu et al., Nonparametric Modern Hopfield Models
• Wu et al., Uniform Memory Retrieval

which are already referenced in our paper, in addition to

• Negri et al., Random Feature Hopfield Networks generalize…
• Hu et al., On Sparse Modern Hopfield Model
• Wu et al., Stanhop
• Iatropoulos et al., Kernel Memory Networks

and other suggested papers. We will also include a Broader Impact statement. Below, we do our best to address your comments within the character constraints of the rebuttal.

…results would be strengthened by including comparisons with established baselines and more ablation studies.

We conducted numerical experiments to validate our theorems (see 1-page pdf). Note that our main goal is to approximate the energy and trajectory of a standard DenseAM (MrDAM) using Random Features. Thus, MrDAM is the “baseline” for our method.

"Memory representation" is a strange term for me…

We use the word representation in a more colloquial sense - the description in terms of something. Similarly to Fourier representation, momentum representation in physics, etc.

You can say the total number of entries in $T$ is fixed, but not the number of parameters, unless you clearly define "parameters" differently…

We define the number of parameters as the number of entries in $T$. We will include additional elaboration on these aspects in the revised paper.

I feel Thm1 may be incorrect

(Re: Comment 1) We apologize for the typo. The bound should be $O(D(YK + L(Y+D)))$; the version in the paper is missing a closing bracket around $O(\cdot)$. Other than that, the bound is as stated, with the $DYK$ term coming from the ProcMems subroutine and the $LD(Y+D)$ term coming from the $L$ GradComp invocations. See the proof of Thm 1 in App E1.

(Re: Comment 2) Thm 1 quantifies the complexity of procedures in Alg 1. We do not claim improvement over standard MrDAM for the precise reason stated by the reviewer regarding the choices of $D, Y, K, L$.

These results highlight that energy descent with DrDAM requires computation and memory that only depends on $D$ and $Y$. Together with Thm 2 and Cor 1, we characterize where the energy descent divergence between MrDAM and DrDAM can be bounded with a choice of $Y$ that only depends on $D$ (and other parameters in the energy) but not $K$.

Is there any guarantee ensuring $\alpha L (1 + 2K \beta e^{\beta/2}) < 1$?

There is no guarantee, as stated in Thm 2. Denoting this term with $\delta = \alpha L(1 + 2K \beta e^{\beta/2})$, the upper bound contains a term of the form $\left(\frac{1 - \delta^L}{1 - \delta}\right)$. If $\delta < 1$, it is clear that the numerator grows with $L$, providing a worse upper bound. However, if $\delta > 1$, $\frac{1 - \delta^L}{1 - \delta}$ can be equivalently written as $\frac{\delta^L - 1}{\delta - 1}$, where the $\delta^L$ term grows with $L$, still having the same effect of larger divergence upper bound with larger $L$.

Re: proof for “fixed point convergence results”

The proof is standard in DenseAM literature (see appendices in paper1 or paper2). Consider our Eq (11) for the energy as an example, whose dynamics is described by the following eqs ($i=1...D$)

$$\tau \frac{dx_i}{dt} = - \frac{\partial E}{\partial x_i}.$$

For this reason, the energy monotonically decreases on the dynamical trajectory

$$\frac{dE}{dt} = \sum\limits_{i=1}^D \frac{\partial E}{\partial x_i} \frac{dx_i}{dt} = -\tau \sum\limits_{i=1}^D \Big( \frac{dx_i}{dt}\Big)^2\leq 0.$$

The energy in Eq (11) is bounded from below, by $-\log(K)/\beta$, since the argument of the logarithm is bounded from above by $K$. Thus the energy descent dynamics has to stop sooner or later when $\frac{dx_i}{dt}=0$, which defines the fixed points. Thus, local minima of the energy correspond to the fixed points of the dynamics.

…include ablation studies on changing $L,K,D,Y$ to verify Thm1.

This is a great suggestion. However, note that Thm 1 is a tight analysis of Alg 1, counting the $D$- and $Y$-dimensional vector initializations, additions, and dot-products. So we did not think such an ablation study would provide additional insight.

Why larger $\beta$ needs larger $Y$?

The reviewer is correct that large $\beta$ (low-temperature) leads to more stable and accurate retrieval by approaching the argmax-retrieval in standard DenseAMs. However, this regime is specifically difficult for random features. Consider the L2 distance based energy in Eq (11):

$$E(\mathbf{x}) = -\frac{1}{\beta} \log \sum_{\mu} \exp\left(-\frac{\beta}{2} \| \boldsymbol{\xi}_\mu - \mathbf{x} \|^2 \right).$$

As $\beta$ increases, the $\exp(\cdot)$ term, which we approximate with random features, gets skewed to the extremes across the $K$ memories, with the $\exp(\cdot) \to 0$ for all but the closest memory. This makes the RF approximation harder, requiring larger $Y$ for better approximation.

which part of this work supports the claim that "making it possible to introduce new memories without increasing the number of weights"?

Prop. 5 shows how to update weights $\mathbf{T}$ with a new memory $\boldsymbol{\xi}$ without increasing the number of weights:

$$\mathbf{T} \gets \mathbf{T} + RF(\tau, \boldsymbol{\xi}),$$

taking $O(DY)$ time and $O(D+Y)$ memory.

Thanks for the clarifications.

1. Maybe the authors should polish the draft regarding Thm1, specifying under which conditions it is efficient, as efficiency is mentioned in the draft. I still feel that it is necessary to have exps showing these efficient conditions are true in the final version. Please correct me if I am wrong. 2 settings (efficient v.s. inefficient) benchmarked against MrDAM should suffice.

2. I'd like to remind the authors that the convergence of fixed point and stable point of the energy landscape (local minima) are different concepts. It seems that your derivation is about the latter, given that it's based on gradient descent on $E$. I understand the intuition you want to convey, but I remind the authors that this physics style of derivation is not really fixed-point convergence in a mathematically rigorous way. For one, you don't provide a convergence rate; you just assume it converges perfectly at $\nabla_x E = \frac{dx}{dt} = 0$, whereas, in reality, you only converge to a region defined by the termination of the gradient descent algorithm. Moreover, can you clarify if $E$ is convex? If it is, such analysis should be easier to include.

3. If your derivation is about stable point of energy landscape (local minima), then how can you ensure fixed point convergence? It is acceptable that you don't have it or don't know how to prove it in this model (leave for future work), but it's important to be precise and accurate.

4. My main concern is that it's impossible to have $\delta <1$ given $\alpha,L,K$ are all positive constants greater than 1. It's strange to have an iterative approximation algorithm with error exponentially scaling with its iteration number. This makes Thm2 vacuous. Please correct me if I am wrong.

I appreciate the authors' efforts making this work clearer to me so far. I learned a lot. For this, I raise my score from 4 to 5.

I am willing to further raise score if above concerns are addressed: exps for efficient criteria, fixed point convergence and Thm2.

Thank you!

Actually, in the DenseAM energies studied in this work, there is a 1:1 correspondence between fixed points and local minima of the energy function...

This is not entirely accurate. Your gradient descent (GD) can't reliably approach the point $\nabla_x E = 0$ given $E$ is nonconvex, at least not without strong assumptions. For example, if your local minima form a connected ring, what would be your fixed point?

There is a line of research dedicated to this subtlety. Please refer to the "Global Convergence Theory of Iterative Algorithms" in [1] for related discussions. In that work, global convergence refers to the convergence of "stable points of $E$" and "fixed points of iterative algorithms." Without proving your fixed-point convergence with similar mathematical rigor, the claim seems overreached.

For the same reason, the following statements are also unconvincing without supporting proofs:

• For intuition, note that the energy landscape of Eq (11) “looks like” a mixture of Gaussians that has been inverted such that local peaks in log-probability are now local minima in energy. Thus, our model is non-convex (i.e., there can be many local minima) and each local minimum is a “fixed point”...

• By the argument above, the fixed-point “regions” where gradient descent terminates are, in fact, points, which are indeed local minima of the energy function...

Still, I might be wrong, but for now, I am not convinced by the math presented in this paper.

[1] Sriperumbudur, Bharath K., and Gert RG Lanckriet. "On the Convergence of the Concave-Convex Procedure." NIPS. Vol. 9. 2009.

---

Regarding $\alpha$, please correct me if I am wrong. In line 181 of the submitted draft, it states "$\alpha \in \{1,...,Y\}$". Aren't they the same $\alpha$? If I mistook two different $\alpha$, it would be better to change the repeated index notation to avoid confusion.

---

I appreciate the authors' efforts and trust they will include efficiency experiments (and also modify the draft as they promised). For this, I raise score from 4->5->6.

Thank you!

(Side comment: Even if it's not the main focus of this work, I still think it's important to show general readers where this method is an efficient approximation.)

Improve embedding of this paper into existing literature

Thank you for your suggestions, we will update the paper with the Related Work section and will include the discussion of all the papers that you have suggested. As a side note, the reference [4] actually is cited in our submission, please see Ref [16]. Connection with diffusion, Ref [5] is a beautiful work, which we will be delighted to highlight. As well as the theoretical work on random features Refs [6], [7].

It would be very useful to derive the formula using variational techniques… It could also be interesting to connect it with similar approximations in Gaussian Processes…

We thank the reviewer for these interesting suggestions and connections.

Our presentation of the approximation was motivated by the simplicity of the derivation that highlights how the energy can be approximated with random features in a cleanly straightforward manner; we were hoping to highlight how easily this distributed representation of memories simplifies the energy function. However, after the derivation, we formally and precisely present how the energy descent can be performed with these random features in Algorithm 1, carefully controlling the peak memory usage and computation. Naively, the peak memory usage would have been $O(YD)$, while our carefully crafted algorithm only requires $O(Y+D)$ peak memory with the same outcome.

However, we do think it is important to derive this approximation via other techniques, potentially highlighting other avenues for improvement.

We thank the reviewer for connecting our work to Gaussian processes. It is true that random features have been used for approximating Gaussian Processes, but the form of usage is targeted to a different application. Gaussian Processes are often used for supervising learning (either directly, or as part of a black-box derivative-free optimization), and the main bottleneck is the need to compute and invert the kernel gram matrix of the training points for any inference. With random features, we can instead perform Bayesian linear learning in the expanded feature space, obviating the kernel gram matrix computation and inversion.

DenseAMs are often utilized for memory retrieval, which is different than supervised learning (the main application of Gaussian Processes). However, this suggested connection by the reviewer can lead to interesting cross-contribution between the fields of Gaussian Processes and DenseAMs. This is very much in line with our goal in this paper to view DenseAMs through a lens of random features and kernel machines, bringing together two fields.

I am not convinced about the usefulness of the bound in Eq.12 in non-trivial regimes due to the exponential dependence on the energy.

It is true that the divergence upper bound depends on the term $\exp(\beta E(\mathbf{x}))$. However, note that, for the energy function defined in Eq (11), assuming that all memories and the initial queries are in a ball of diameter $1$, $E(\mathbf{x}) \leq \frac{1}{2} - \frac{\log K}{\beta}$, implies that $\exp(\beta E(\mathbf{x})) \leq \exp(\beta/2) / K$.

An important aspect of our analysis is that the bound is query specific, and depends on the initial energy $E(\mathbf{x})$. As discussed above, this can be upper bounded uniformly, but our bound is more adaptive to the query $\mathbf{x}$.

For example, if the query is initialized near one of the memories, while being sufficiently far from the remaining $(K-1)$ memories, then $\exp (\beta E(\mathbf{x}))$ term can be relatively small.

More precisely, with all memories and queries lying in a ball of diameter $1$, let the query be at a distance $r < 1$ to its closest memories, and as far as possible from the remaining $(K-1)$ memories. In this case, the initial energy $E(\mathbf{x}) \approx -(1/\beta) \log [\exp(-\beta r / 2) + (K-1) \exp(-\beta/2)]$, implying that

$$\exp(\beta E(\mathbf{x})) \approx \frac{\exp(\beta r / 2)}{\Big[1 + (K-1)\exp(-\beta(1 - r)/2)\Big]} \leq \exp(\beta r / 2)$$

For sufficiently small $r < 1$, the above quantity can be relatively small. If, for example, $r \sim O(\log K)$, then $\exp(\beta E(\mathbf{x})) \sim O(K^{\beta/2})$, while $r \to 0$ gives us $\exp(\beta E(\mathbf{x})) \to O(1)$. This highlights the adaptive query-dependent nature of our analysis.

So it is not directly clear why this is not a “non-trivial regime”. We believe that this form of analysis is novel, and highlights the effect of the different quantities of interest in this formulation (such as the effect of the number of memories, energy descent steps, random features, initial particle energy). We accept that this upper bound might not be the tightest. However, that limitation does not necessarily make the analysis “trivial”.

Given the simplicity of the proposed method and its similarities with known approaches such as [TODO]…

We would be happy to elaborate on this comment if the reviewer kindly specifies the “[TODO]” approaches. We do believe, however, that our approach is novel and that our contribution is relevant to this conference. We will add a Related Work section to better differentiate it from existing prior work.

I find intuitively strange that the bound in Eq.13 depends on the absolute value of the energy instead of on a relative energy. Can you provide some intuition for this result?

This result uses the form of the energy, given by Eq (11), which assumes that the zero-energy state is chosen such that the sum of the exponents under the logarithm is equal to 1. Only the difference of the energies appears in Eqs (12,13), but this difference is implicit, given the (arbitrary) choice of the reference point made in Eq (11).

Why using hamming distance when calculating retrieval error when the theoretical results use L2?

We consider Hamming error since we are storing and retrieving binary memories, e.g. in Fig.3. Our theoretical results operate in the more general continuous $\mathbb{R}^d$ space, and thus bounds the L2 error. However, please note that, with binary vectors, Hamming error and L2 error are related by the square root operation. For this reason, our theoretical bound (proven for L2 error) is equal to the square root of the numerical evaluations with Hamming distance.

To my understanding, the proposed method is an approximation to DAM. Thus the paper should at least compare the proposed method to DAM in the experimental section.

You are correct -- our proposed "distributed representation" for DenseAMs, which we call DrDAM, are approximations to the original DAM (what we refer to as the "memory representation" or MrDAM in our paper). The experiments in our paper are explicitly designed to compare against the original DAM a.k.a. MrDAM. E.g., Figs 2 and 3A plot DrDAM's approximation error when compared to the original DAM. Fig 3B shows how well, qualitatively, DrDAM approximates the original DAM (what we call the "Ground Truth" in that figure).

The field of associative memories, Hopfield networks are getting increased attention recently, I think a related work section would benefit this paper a lot.

Thank you for your suggestion. This sentiment was echoed by other reviewers and we will update the paper with a pertinent related works section.

We are happy to hear that the main message of the paper got across well, and thank the reviewer for their insightful comments and feedback. Below we answer individual questions raised.

… looking at the error bound in eq. (12), it seems that $Y$ has to be taken of the order of $O(K^2 D)$…

It is true that if we ignore all the terms on the right hand side of equation (12) except for the $K \sqrt{D/Y}$ term, it appears that $Y \sim O(K^2 D)$. However, it is important to note that the remainder terms in the upper bound on the right hand side of (12) also include the step-size $\alpha$ and $K$ itself. Ignoring the effect of $\alpha$ and $K$ in the remainder terms can give a wrong impression regarding the bound. For that very reason, we explicitly study a special case in Corollary 1, in which the update rate $\alpha$ is scaled in a $K, L$, and $\beta$ dependent manner. An important aspect of our analysis is that the bound is query specific, and depends on the initial energy $E(\mathbf{x})$. For example, if the query is initialized near one of the memories, while being sufficiently far from the remaining $(K-1)$ memories, then $\exp (\beta E(\mathbf{x}))$ term can be relatively small. More precisely, with all memories and queries lying in a ball of diameter $1$, let the query be at a distance $r < 1$ to its closest memory, and as far as possible from the remaining $(K-1)$ memories. In this case, the initial energy $E(\mathbf{x}) \approx -(1/\beta) \log [\exp(-\beta r / 2) + (K-1) \exp(-\beta/2)]$, implying that

$$\exp(\beta E(\mathbf{x})) \approx \frac{\exp(\beta r / 2)}{\Big[1 + (K-1)\exp(-\beta(1 - r)/2)\Big]} \leq \exp(\beta r / 2)$$

Thus, the exponential factor in our bound is not a problem. Overall, the divergence is bounded by $O(\sqrt{D / Y})$, at constant $\beta$, implying the need for $Y \sim O(D / \epsilon^2)$ for at most $\epsilon$ divergence. Please note, that this estimate is independent of $K$, which is the essence of our proposal.

Numerical Experiments are limited… in Fig. 1 the 4x12288=49152 memory matrix has to be replaced by a several times larger Y-sized vector…

The configuration shown in Fig.1 was chosen to illustrate the main idea of the method. $Y$ does not have to be larger than the number of parameters required to describe the memory vectors. To explicitly demonstrate this point we have repeated the experiments shown in Fig.1 with 20 memories; please see Fig (a) in the 1 page PDF rebuttal. Now we have 20x64x64x3=246k parameters in the memory vectors encoded in the 200k-dimensional vector $T$. The method works well and all the conclusions presented in the paper remain valid.

Can the author show a plot similar to Fig. 2 but now showing the theoretical prediction from eq. 12…?

We thank the reviewer for this great suggestion, which would highlight the tightness of our proposed upper bound. We have done it in Fig (c) of the 1 page PDF rebuttal. It is important to note that the upper bound also involves a quantity (precisely the quantity $C_1$ defined in assumption A2 in Theorem 2) which bounds the approximation introduced by the random feature maps (such as Rahimi and Recht (2007)), and this does not have an easily computable analytical form. For this reason, it is challenging to precisely compute this bound. However, it is possible to check the predicted scaling relationships. Specifically, the theoretically predicted $Y^{-1/2}$ dependence in the upper bound for a fixed $D$ appears in most of the results, please see Fig (c) in the 1 page PDF. This shows that the upper bound in equation (12) from Theorem 2 fairly characterizes the dependence on $Y$. Fig (c) from the PDF will be used to update Fig 2 (right side) in the current submission.

It would be nice to make a plot similar to Fig. 2 but now as a function of K.

Thanks for the suggestion. We have generated this plot per your request and included it in Fig (b) of the 1 page PDF. The results are consistent with the theory developed in our paper.

… $\mathbf{p}$ in Algorithm 1 and at the beginning of Section 3 could denote the same thing.

The reviewer is correct that we overload the variable $\mathbf{p}$ both as $\mathbf{p} = \mathbf{g}(\mathbf{x})$ and $\mathbf{p} = RF(\tau, \mathbf{g}(\mathbf{x}))$. We will fix the notation, and use a different term to denote $\mathbf{g}(\mathbf{x})$.

line 215. Usually, the EDP model also contains an $x^2$ term…

The reviewer is correct, the complete EDP energy is

$$E(\mathbf{x}) = -\frac{1}{\beta} \log \sum_\mu \exp(\beta \langle \boldsymbol{\xi}\mu , \mathbf{x} \rangle) + \frac{1}{2} \| \mathbf{x} \|^2.$$

We were referring to the part of the energy which is relevant for the argument in line 215. We will write the complete energy. Our claim of validity of the proof technique of Theorem 2 still applies, since we just need to approximate the $\exp(\beta\langle \boldsymbol{\xi}_\mu, \mathbf{x} \rangle)$ term with the random features.

Assuming that the random feature version is considered as DAM… could the author comment on its capacity in presence of random memories?

This is an interesting question, which may be investigated in the future. However, it remains beyond the scope of our current project. Our goal here is to answer the following question: how well the random feature description can represent the dynamics of DAM?

General Comment

Once again, we greatly appreciate your insightful comments and suggestions. We would be grateful if you could consider increasing the score for our work towards an accept.