Dense Associative Memory Through the Lens of Random Features

Authors: benjamin  hoover
horng  duen
georgia  chau
  tech
hendrik  strobelt
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:39:26

Abstract: Dense Associative Memories are high storage capacity variants of the Hopfield networks that are capable of storing a large number of memory patterns in the weights of the network of a given size. Their common formulations typically require storing each pattern in a separate set of synaptic weights, which leads to the increase of the number of synaptic weights when new patterns are introduced. In this work we propose an alternative formulation of this class of models using random features, commonly used in kernel methods. In this formulation the number of network's parameters remains fixed. At the same time, new memories can be added to the network by modifying existing weights. We show that this novel network closely approximates the energy function and dynamics of conventional Dense Associative Memories and shares their desirable computational properties.

Main paper: 
 introduction: 
 Hopfield network of associative memory is an elegant mathematical model that makes it possible to store a set of memory patterns in the synaptic weights of the neural network [1] . For a given prompt σ i (t = 0), which serves as the initial state of that network, the neural update equations drive the dynamical flow towards one of the stored memories. For a system of K memory patterns in the Ddimensional binary space the network's dynamics can be described by the temporal trajectory σ i (t), which descends the energy functionEQUATIONHere ξ µ i (index µ = 1...K, and index i = 1...D) represent memory vectors. The neural dynamical equations describe the energy descent on this landscape. In this formulation, which we call the memory representation, the geometry of the energy landscape is encoded in the weights of the network ξ µ i , which coincide with the memorised patterns. Thus, in situations when the set of the memories needs to be expanded by introducing new patterns one must introduce additional weights.Alternatively, one could rewrite the above energy in a different form, which is more commonly used in the literature. Specifically, the sum over the memories can be computed upfront and the energy can be written asE = - D i,j=1T ij σ i σ j , whereT ij = K µ=1 ξ µ i ξ µ j (2)Figure 1 : The Distributed Representation for Dense Associative Memory (DrDAM) approximates both the energy and fixed-point dynamics of the traditional Memory Representation for Dense Associative Memory (MrDAM) while having a parameter space of constant size. A) Diagram of DrDAM using a basis function parameterized by random features (e.g., see eq. ( 8)). In the distributed representation, adding new memories does not change the size of the memory tensor. B) Comparing energy descent dynamics between DrDAM and MrDAM on 3x64x64 images from Tiny Imagenet [11] . Both models are initialized on queries where the bottom two-thirds of pixels are occluded with zeros; dynamics are run while clamping the visible pixels and their collective energy traces shown. DrDAM achieves the same fixed points as MrDAM, and these final fixed points have the same energy. The energy decreases with time for both MrDAM and DrDAM, although the dependence of the energy relaxation towards the fixed point is sometimes different between the two representations. Experimental setup is described in appendix D.In this form one can think about weights of the network being the symmetric tensor T ij instead of ξ µ i . One advantage of formulating the model this way is that the tensor T ij does not require adding additional parameters when new memories are introduced. Additional memories are stored in the already existing set of weights by redistributing the information about new memories across the already existing network parameters. We refer to this formulation as distributed representation.A known problem of the network (eqs. ( 1) and ( 2)) is that it has a small memory storage capacity, which scales at best linearly as the size of the network D is increased [1] . This limitation has been resolved with the introduction of Dense Associative Memories (DenseAMs), also known as Modern Hopfield Networks [2] . This is achieved by strengthening the non-linearities (interpreted as neural activation functions) in eq. (1) , which can lead to the super-linear and even exponentially large memory storage capacity [2, 3] . Using continuous variables x ∈ R D , the energy is defined as1 EQUATIONwhere the function g : R D → R D is a vector function (e.g., a sigmoid, a linear function, or a layernorm), the function F (•) is a rapidly growing separation function (e.g., power F (•) = (•) n or exponent), S[x, x ′ ] is a similarity function (e.g., a dot product or a Euclidean distance), and Q is a scalar monotone function (e.g., linear or logarithm). For instance, in order to describe the classical Hopfield network with binary variables (eq. ( 1)) one could take: linear Q, quadratic F (•) = (•) 2 , dot product S, and a sign function for g i = sign(x i ) = σ i . There are many possible combinations of various functions g, F (•), S(•, •) that lead to different models from the DenseAM family [2] [3] [4] [5] [6] [7] ; many of the resulting models have proven useful for various problems in AI and neuroscience [8] . Diffusion models have been linked to even more sophisticated forms of the energy landscape [9, 10] .From the perspective of the information storage capacity DenseAMs are significantly superior compared to the classical Hopfield networks. At the same time, most 2 of the models from the DenseAM family are typically formulated using the memory representation, and for this reason Figure 2 : DrDAM achieves parameter compression over MrDAM, successfully storing 20 different 64x64x3 images from TinyImagenet [11] and retrieving them when occluding the lower 40% of each query. The memory matrix of MrDAM is of shape (20, 12288) while the memory tensor of DrDAM is of shape Y = 2 • 10 5 , a ∼20% reduction in the number of parameters compared to MrDAM; all other configurations for this experiment match those in appendix D. Further compression can be achieved with a higher tolerance for DrDAM's retrieval error, smaller β, and fewer occluded pixels, see § 4.Top: Occluded query images. Middle: Fixed-point retrievals from DrDAM. Bottom: (ground truth) Fixed-point retrievals of MrDAM.require introduction of new weights when additional memory patterns are added to the network. The main question that we ask in our paper is: how can we combine superior memory storage properties of DenseAMs with the distributed (across synaptic weights) formulation of these models in the spirit of classical Hopfield networks (eq. ( 2))? If such a formulation is found, it would allow us to add memories to the existing network by simply recomputing already existing synaptic weights, without adding new parameters.A possible answer to this question is offered by the theory of random features and kernel machines.Given an input domain X , kernel machines leverage a positive definite Mercer kernel function k : X × X → R + that measures the similarity between pairs of inputs. The renowned "kernel trick" allows one to compute the inner-productEQUATIONbetween two inputs x, x ′ ∈ X in a rich feature space defined by the feature map φ(x) without ever explicitly realizing the feature map φ(x). Various machine learning models (such as support vector machines [12] , logistic regression, and various others [13, 14] ) can be learned with just access to pairwise inner-products, and thus, the kernel trick allows one to learn such models in an extremely expressive feature space. Kernel functions have been developed for various input domains beyond the Euclidean space such as images, documents, strings (such as protein sequences [15] ), graphs (molecules [16] , brain neuron activation paths) and time series (music, financial data) [17] . Common kernels for Euclidean data are the radial basis function or RBF kernel k(x, x ′ ) = exp(-γ∥x -x ′ ∥ 2 2 ) and the polynomial kernel k(x, x ′ ) = (⟨x, x ′ ⟩ + b) p . To appreciate the expressivity of these kernel machines, note that, for input domain R D , the RBF kernel corresponds to an infinite dimensional feature space (Y = ∞) and the polynomial kernel to a O(D p ) dimensional feature space.Interpreting the composition of the separation and similarity functions in eq. ( 3) as the left hand side of the kernel trick eq. ( 4) we can map the energy into the feature space, using appropriately chosen feature maps. Subsequently, the order of the summations over memories and features can be swapped, and the sum over memories can be computed explicitly. This makes it possible to encode all the memories in a tensor T α , which we introduce in section § 3, that contains all the necessary information about the memories. The energy function then becomes defined in terms of this tensor only, as opposed to individual memories. This functionality is summarized in fig. 1 . Additionally, we show examples of retrieved Tiny ImageNet images that have been memorised using the original DenseAM model, which we call MrDAM, and the "featurized" version of the same model, which we call DrDAM (please see the explanations of these names in the caption to fig. 1 ). These examples visually illustrate that mapping the problem into the feature space preserves most of the desirable computational properties of DenseAMs, which normally are defined in the "kernel space".▶ We propose a novel approximation of a DenseAM network utilizing random features commonly used in kernel machines. This novel architecture does not require the storage of the original memories, and can incorporate new memories without increasing the size of the network.▶ We precisely characterize the approximation introduced in the energy descent dynamics by this architecture, highlighting the different critical factors that drive the difference between the exact energy descent and the proposed approximate one. ▶ We validate our theoretical guarantee with empirical evaluations.In the past, kernel trick has been used for optimizing complexity of the attention mechanism in Transformers [18] , and those results have been recently applied to associative memory [19] , given the various connections between Transformers and DenseAMs [4, 20] . Existing studies [18, 19] focus on settings when attention operation or associative memory retrieval is done in a single step update. This is different from our goals here, which is to study the recurrent dynamics of the associative memory updates and convergence of that dynamics to the attractor fixed points. Iatropoulos et al. [21] propose kernel memory networks which are a recurrent form of a kernel support vector machine, and highlight that DenseAM networks are special cases of these kernel memory networks. Making a connection between nonparametric kernel regression and associative memory, Hu et al. [22] propose a family of provably efficient sparse Hopfield networks [23, 24] , where the dynamics of any given input are explicitly driven by a subset of the memories due to various entropic regularizations on the energy. DenseAMs have been also used for sequences [25, 26, 24] . To reduce the complexity of computing all the pairs of F (S[ξ, x]) for a given set of memories and queries, Hu et al. [27] leverage a low-rank approximation of this separation-similarity matrix using polynomial expansions. The kernel trick has also recently been used to increase separation between memories (with an additional learning stage to learn the kernel), thereby improving memory capacity [28] . There are also very recent theoretical analysis of the random feature Hopfield networks [29, 30] , where their focus in on the construction of memories using random features. Kernels are also related to density estimation [31] , and recent works have leveraged a connection between mixtures of Gaussians and DenseAMs for clustering [32, 33] . Lastly, random features have been used for biological implementations of both Transformers and DenseAMs [34, 35] .To the best of our knowledge there is no rigorous theoretical and empirical comparison of DenseAMs and their distributed (featurized) variants in recurrent memory storage and retrieval settings, as well as results pertaining to the recovery of the fixed points of the energy descent dynamics. This is the main focus of our work.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: We lay out clearly our contribution of a novel approximation of the dynamical process for Dense Associative Memory that uses random features. 
technical background: 
 Given the energy function in eq. (3), a variable x is updated in the forward pass through the "layers" of this recurrent model such that its energy decreases with each update. If the energy is bounded from below, this ensures that the input will (approximately) converge to a local minimum. This can be achieved by performing a "gradient descent" in the energy landscape. Considering the continuous dynamics, updating the input x over time with dx/dt, we need to ensure that dE/dt < 0. This can be achieved by setting dx/dt ∝ -∇ x E.Discretizing the above dynamics, the update of an input x at the t-th recurrent layer is given by:EQUATIONwhere η (t) is a (step dependent) step-size for the energy gradient descent, E (t) is the energy of the input after the t-th layer, and the input to the first layer x (0) ← x. The final output of the associative memory network after L layers is x (L) .DenseAMs significantly improve the memory capacity of the associative memory network by utilizing rapidly growing nonlinearity-based separation-similarity compositions such asF (S[x, ξ µ ]) = exp(β ⟨x, ξ µ ⟩) or F (S[x, ξ µ ]) = exp(-β /2∥x -ξ µ ∥ 2 ) or F (S[x, ξ µ ]) = (⟨x, ξ µ ⟩) p , p > 2,among other choices, with β > 0 corresponding to the inverse temperature that controls how rapidly the separation-similarity function grows. However, these separation-similarity compositions do not allow for the straightforward simplifications as in eq. ( 2), except for the power composition. For a general similarity function, the update based on gradient descent over the energy in eq. ( 3) is given by:EQUATIONFor example, withQ(•) = (1/β) log(•), F (•) = exp(β•), S[ξ µ , x] = ⟨ξ µ , x⟩ and g(x) = x/∥x∥ 2 ,the energy function and the corresponding update3 are:EQUATIONThis form does not directly admit itself to a distributed storage of memories as in eq. ( 2), and thus, in order to perform the gradient descent on the energy, it is necessary to keep all the memories in their original form. We will try to address this issue by taking inspiration from the area of kernel machines [36] .The expressivity of kernel learning usually comes with increased computational complexity both during training and inference, taking time quadratic and linear in the size of the training set respectively. The groundbreaking work of Rahimi and Recht [37] introduced random features to generate explicit feature maps φ : R D → R Y for the RBF and other shift-invariant kernels4 that approximate the true kernel function -that is ⟨φ(x), φ(x ′ )⟩ ≈ k(x, x ′ ). Various such random maps have been developed for shift-invariant kernels [18, 19, 38] and polynomials kernels [39] [40] [41] .For the RBF kernel and the exponentiated dot-product or EDP kernel k(x, x ′ ) = exp(⟨x, x ′ ⟩), there are usually two classes of random features -trigonometric features and exponential features. For the RBF kernel k(x, x ′ ) = exp(-∥x -x ′ ∥ 2 2 /2), the trigonometric features [37] are given on the left and the exponential features [18] are on the right:EQUATIONwhere ω α ∼ N (0, I D )∀α ∈ {1, . . . , Y } are the random projection vectors. 5 A random feature map φ for the RBF kernel can be used for the EDP kernel by scaling φ(x) with exp(∥x∥ 2 2 /2). While the trigonometric features ensure that k(x, x) = ⟨φ(x), φ(x)⟩ = 1, the exponential features ensure that φ(x) ∈ R 2Y + , which is essential in certain applications as in transformers [18, 19] . Furthermore, while the random samples ω α ∼ N (0, I D ) are supposed to be independent, Choromanski et al. [42] show that the {ω 1 , . . . , ω Y } can be entangled to be exactly orthogonal to further reduce the variance of the approximation while maintaining unbiasedness. In general, the approximation of the random feature map is O( D/Y ), implying that a feature space with Y ∼ O(D/ϵ 2 ) random features will ensure, with high probability, for any x, x ′ ∈ R D , |k(x, x ′ ) -⟨φ(x), φ(x ′ )⟩ | ≤ ϵ. Scaling in the kernel functions such as exp(-β∥x -x ′ ∥ 2 2 /2) or exp(β ⟨x, x ′ ⟩) can be handled with the aforementioned random feature maps φ by applying them to√ βx with φ( √ βx), φ( √ βx ′ ) ≈ exp(-β∥x -x ′ ∥ 2 2 /2).3 DrDAM with Random FeaturesRevisting the general energy function in eq. ( 3), if we have available an explicit mapping φ :R D → R Y such that ⟨φ(ξ µ ), φ(x)⟩ ≈ F (S[ξ µ , x]), then we can simplify the general energy function in eq. ( 3) toEQUATIONDenoting T = µ φ(ξ µ ), we can write a simplified general update step for any input x as:EQUATIONwhere dφ(x)/dx ∈ R Y ×D is the gradient of the feature map with respect to its input. In the presence of such an explicit map φ, we can distribute the memory in a MrDAM into the single Y -dimensional vector T, and be able to apply the update in eq. (10) . We can then use the random feature based energy gradient ∇ x Ê(x) instead of the true energy gradient ∇ x E(x) in the energy gradient descent step in eq. ( 5). 6 We name this scheme "Distributed representation for Dense Associative Memory" or DrDAM, and we compare the computational costs of DrDAM with the "Memory representation of Dense Associative Memory" or MrDAM in the following:Proposition 1. With access to the K memories {ξ µ ∈ R D , µ ∈ K }, MrDAM takes O(LKD) timeand O(KD) peak memory for L energy gradient descent steps (or layers) as defined in eq. ( 5) with the true energy gradient ∇ x E(x).Algorithm 1: Procedures for DrDAM with random features.RF(Seed τ , Memory ξ) Initialize p ← 0 Y Set RNG R seed to τ for α = 1, . . . , Y do Sample random feature φα from R pα ← φα(ξ) return p ProcMems(Seed τ , Mems {ξ µ , µ ∈ {1, . . . , K}) Initialize T ← 0 Y for µ = 1, . . . , K do T ← T+RF(τ , ξ µ ) return T GradComp(Seed τ , Distributed mems T, Input x) p ← RF(τ, g(x)) Initialize z ← 0 D // Compute ∇yφ(y) ⊤ T in O(Y ) mem for i = 1, . . . , D do Compute u ← dφ(y)/dyi| y=g(x) zi ← ⟨u, T⟩ Initialize z ′ ← 0 D // Compute z∇xg(x) in O(D) mem for i = 1, . . . , D do Compute y ← dg(x)/dxi z ′ i ← ⟨y, z⟩ Compute q ← -dQ(s)/ds| s=⟨T,p⟩ return qz ′Naively, the random feature based DrDAM would require O(DY ) memory to store the random vectors and the ∇ x φ(x) matrix. However, we can show that we can generate the random vectors on demand to reduce the overall peak memory to just O(Y ). The various procedures in DrDAM are detailed in Algorithm 1. The RF subroutine generates the random feature for any memory or input. The ProcMems subroutine consolidates all the memories into a single T ∈ R Y vector. The GradComp subroutine compute the gradient ∇ x Ê. The following are the computational complexities of these procedures: 5) with the random feature based approximation gradient ∇ x Ê(x) defined in eq. (10) .However, note that the memory encoding only needs to be done once, while the same T can be utilized for L steps of energy gradient steps for multiple input, and the cost of ProcMems is amortized over these multiple inputs. We also show that the computational costs of the inclusion of a new memories ξ:Proposition 5. The inclusion of a new memory ξ ∈ R D to a DrDAM with K memories distributed in T ∈ R Y takes O(DY ) time and O(D + Y ) peak memory.The above result shows that inclusion of new memories correspond to constant time and memory irrespective of the number of memories in the current DenseAM. Next, we study the divergence between the output of a L-layered MrDAM using the energy descent in eq. ( 5) with the true gradient in eq. ( 6) and that of DrDAM using the random feature based gradient in eq. ( 10).Theorem 2. Consider the following energy function with K memories {ξ µ ∈ R D , µ ∈ {1, . . . , K}} and inverse temperature β > 0:EQUATIONWe further make the following assumptions: (A1) All memories ξ µ and inputs ) be the output of the MrDAM defined by the energy function in eq. ( 11) using the true energy gradient in eq. ( 6) and x(L) be the output of DrDAM with approximate gradient in eq. ( 10) using the random feature map φ using a constant step-size of η > 0 in (5) . Thenx lie in X = [0, 1 / √ D] D . (A2) Using a random feature map φ : R D → R Y using Y random feature maps, for any x, x ′ ∈ R d there is a constant C 1 > 0 such that exp(∥x -x ′ ∥ 2 2 /2) -⟨φ(x), φ(x ′ )⟩ ≤ C 1 D /Y . Given an input x ∈ X , let x (LEQUATIONAssumption (A1) just ensures that all the memories and inputs have bounded norm, and can be achieved via translating and scaling the memories and inputs. Assumption (A2) pertains to the approximation introduced in the kernel function evaluation with the random feature map, and is satisfied (with high probability) based on results such as Rahimi and Recht [37, Claim 1] and Choromanski et al. [18, Theorem 4] . The above result precisely characterizes the effect on the divergence ∥x (L) -x(L) ∥ of the (i) initial energy of the input E(x) -lower is better, (ii) the inverse temperature β -lower is better, (iii) the number of memories K -lower is better, (iv) the ambient data dimensionality D -lower is better, (v) the number of random features Y -higher is better, and (vi) the number of layers L -lower is better. The proof and further discussion are provided in appendix F.2. Note that theorem 2 analyzes the discretized system, but as the step-size η → 0, we approach the fully contracting continuous model. An appropriate choice for the energy descent stepsize η simplifies the above result, bounding the divergence to O( D/Y ): Corollary 1. Under the conditions and definitions of theorem 2, if we set the step size η = C2 L(1+2Kβe β/2 ) with C 2 < 1, the divergence is bounded as:EQUATION)These above results can be extended to the EDP based energy function E(x) = -1 /β log µ exp(β ⟨ξ µ , x⟩) + 1 /2∥x∥ 2 2 using the same proof technique.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Limitations are characterized theoretically in § 3, empirically in § 4, and summarized in appendix A. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: Assumptions, propositions, and theorems are given in § 3, with additional proofs in appendix F. 
empirical evaluation: 
 To be an accurate approximation of the traditional MrDAM, DrDAM must empirically satisfy the following desiderata for all possible queries and at all configurations for inverse temperature β and pattern dimension D:(D1) for the same query, DrDAM must predict similar energies and energy gradients as MrDAM; and (D2) for the same initial query, DrDAM must retrieve similar fixed points as MrDAM.However, in our experiments we observed that the approximation quality of DrDAM is strongly affected by the choice of β and that the approximation quality decreases the further the query patterns are from the stored memory patterns, as predicted by theorem 2. We characterize this behavior in the following experiments using the trigonometric "SinCos" basis function, which performed best in our ablation experiments (see appendix C), but note that the choice of the random features do play a significant role in the interpretations of these results.4.1 (D1) How accurate are the energies and gradients of DrDAM? 14)) is taken over 500 queries initialized: at stored patterns (i.e., queries equal the stored patterns), near stored patterns (i.e., queries equal the stored patterns where 10% of the bits have been flipped), and randomly (i.e., queries are random and far from stored patterns). Error bars represent the standard error of the mean but are visible only at poor approximations. Red horizontal lines represent the expected error of random energies and gradients. The theoretical error upper bounds of eq. ( 13) (dark curves on the gradient errors in the right plot only) show a tight fit to empirical results at low β and D and are only shown if predictions are "better than random". The shaded area shows the difference between the theoretical bound and the empirical results.We generated 2K = 1000 unique, binary patterns (where each value is normalized to be {0, 1 √ D }) and stored K = 500 of them into the memory matrix Ξ of MrDAM. We denote these stored patterns as ξ µ ∈ {0, 1 √ D } D , µ ∈ K , where D is a hyperparameter controlled by the experiment. For a given β, the memory matrix is converted into the featurized memory vector T α := µ φ α (ξ µ ) from eq. ( 9), where α ∈ 2Y . The remaining patterns are treated as the "random queries" x b far , b ∈ K (i.e., queries that are far from the stored patterns). Finally, in addition to evaluating the energy at these random queries and at the stored patterns, we also want to evaluate the energy at queries x b near that are "near" the stored patterns; thus, we take each stored pattern ξ µ and perform bit-flips on 0.1D of its entries. EQUATIONWe found it useful to visualize the results using log-scale and to compare the errors against the expected error of a "random guess" of the energy/gradients (horizontal red dashed line in each plot of fig. 3 ). The "random guess error" was empirically computed by sampling a new set of random queries x b guess , b ∈ K (independent of the reference queries) and computing the MAE between the standard energy on the reference queries vs. the approximate energies on the random queries. This error was averaged across Y for each β; the highest average error across all βs is plotted. Observation 1: DrDAM approximations are best for queries near stored patterns DrDAM approximations for both the energy and energy gradients are better the closer the query patterns are to the stored patterns. In this regime, approximation accuracy predictably improves when increasing Observation 3: DrDAM approximations break at sufficiently high values of D and β In general, DrDAM's approximation errors remain the same across choices for D, especially when the queries are near the stored patterns. However, when both β and D are sufficiently large (e.g., β ≥ 40 and D ≥ 100 in fig. 3 ), increasing the value of Y does not improve the approximation quality: DrDAM continues to return almost random gradients and energies. We explore this phenomenon more in § 4.2 in the context of the retrievability of stored patterns.Memory retrieval is the process by which an initial query x (0) descends the energy function and is transformed into a fixed point of the energy dynamics. This process can be described by the discrete update rule in eq. (5) , where E can represent either MrDAM's energy or the approximate energy of DrDAM. A memory is said to be "retrieved" when |E(x (L) ) -E(x (L-1) )| < ε for some small ε > 0, at which point x (L-1) ≈ x (L) =: x ⋆ is declared to be the retrieved memory after L iterations because x ⋆ lives at a local minimum of the energy function E.Quantifying retrieval error Given the same initial queries x (0) ∈ {0, 1 √ D } D , we want to quantify the difference between the fixed points x⋆ retrieved by descending DrDAM's approximate energy and the fixed points x ⋆ retrieved by descending the energy of MrDAM. We follow the experimental setup of § 4.1, only this time we run full memory retrieval dynamics until convergence.Note that since energy uses an L2-similarity kernel, memory retrieval is not guaranteed to return binary values. Thus, we binarize x ⋆ by assigning each entry to its nearest binary value before computing the normalized Hamming approximation error ∆ H , i.e.,⌈x⌋ :=    1 √ D , x ≥ 1 2 √ D 0, otherwise, andEQUATION)The choice of normalized Hamming approximation error ∆ H on our binary data is equivalent to the squared L2 error on the left side of our bound in eq. ( 13) (up to a linear scaling of 1 √ D ). Figure 4A shows the results of this experiment. Many observations from § 4.1 translate to these experiments: we notice that retrieval is random at high β and D, and that retrievals are of generally higher accuracy nearer the stored patterns. However, we notice that high β values can retrieve better approximations than lower values of β when the queries are at or near stored patterns. Additionally, for sufficiently high β (e.g., see D = 1000, β = 50 near stored patterns), this accompanies an interesting "thresholding" behavior for Y where retrieval error starts to improve rapidly once Y reaches a minimal threshold. This behavior is corroborated in the high D regime in fig. 4B .Visualizing retrieval error Figure 4B shows what retrieval errors look like qualitatively. We stored K = 10 random images from CIFAR10 [43] into the memory matrix of MrDAM, resulting in patterns of size D = 3 × 32 × 32 = 3072, and compared retrievals using βs that produced meaningful image results with MrDAM. To keep β values consistent with our previous experiments, each pixel was normalized to the continuous range between 0 and 1√ D s.t. ξ µ i ∈ [0, 1 √ D ], with µ ∈ K and i ∈ D . From § 4.1 and fig. 4A , we know that approximate retrievals are inaccurate at high β and high D if the query is far from the stored patterns. However, this is exactly the regime we test when retrieving images in fig. 4B . The visible pixels (top half of the image) are clamped while running the dynamics until convergence. Retrieved memories at different configurations for DrDAM are plotted against their corresponding MrDAM retrievals in fig. 4B .As β increases, insufficiently large values of Y fail to retrieve meaningful approximations to the dynamics of MrDAM. We observe that image completions generally become less noisy as Y increases, but with diminishing improvement in perceptible quality after some threshold where DrDAM goes from predicting noise to predicting meaningful image completions.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: Extensive descriptions of the main experimental results are provided in § 4; experimental details that were not appropriate for the main paper are explained in appendix D and appendix E. Our proposed method itself is explained in detail in Algorithm 1. 
conclusion: 
 Our study is explicitly designed to characterize where DrDAM is a good approximation to the energies and dynamics of MrDAM. In pushing the limits of the distributed representation, we discovered that DrDAM is most accurate when: (1) query patterns are nearer to the stored patterns; (2) β is lower; and (3) Y is large. Error bounds for these situations are explicitly derived in theorem 2 and empirically tested in § 4.We have explored the use of distributed representations via random feature maps in DenseAMs. We have demonstrated how this can be done efficiently, and we precisely characterized how it performs the neural dynamics relative to the memory representation DenseAMs. Our theoretical results highlight the factors playing a role in the approximation introduced by the distributed representations, and our experiments validate these theoretical insights. As future work, we intend to explore how such distributed representations can be leveraged in hierarchical associative memory networks [44, 45] , which can have useful inductive biases (e.g., convolutions, attention), and allow extensions with multiple hidden layers. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: All details are provided alongside the results reported in § 4. Computational environment for the experiments is described in appendix E. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: Error bars representing the "standard error of the mean" (SEM) are shown on all quantitative plots (i.e., figs. 3, 4 and 6) . We evaluated on large sample sizes s.t. the SEM is small, but still visible when the predictions have high variability.Guidelines: ▶ The answer NA means that the paper does not include experiments. ▶ The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. ▶ The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).▶ The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) ▶ The assumptions made should be given (e.g., Normally distributed errors). ▶ It should be clear whether the error bar is the standard deviation or the standard error of the mean. ▶ It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. ▶ For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). ▶ If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We use the same computational environment for all experiments, which is described in appendix E. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Our work does not require human subjects. Datasets used are public and the nature of the evaluation is not dependent on any inherent biases. The work does not have unexpected anticipated societal harms or other harmful consequences requiring mitigation. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: We do not anticipate any additional societal harms or other harmful consequences requiring mitigation beyond the well-known risks.Guidelines: ▶ The answer NA means that there is no societal impact of the work performed. ▶ If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.▶ Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. ▶ The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. ▶ The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. ▶ If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: No proprietary datasets were used. The models developed are not anticipated to have a high risk potential for misuse.Guidelines: ▶ The answer NA means that the paper poses no such risks. ▶ Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. ▶ Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. ▶ We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: All owners of assets used in this paper are properly cited. No licensed work was used.Guidelines: ▶ The answer NA means that the paper does not use existing assets. ▶ The authors should cite the original paper that produced the code package or dataset. ▶ The authors should state which version of the asset is used and, if possible, include a URL. ▶ The name of the license (e.g., CC-BY 4.0) should be included for each asset. ▶ For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. ▶ If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: In this paper, we have explored the use of distributed representations via random feature maps in DenseAMs. However, we are only scratching the surface of opportunities that such distributed representations bring to DenseAMs. There are various aspects we do not cover: (i) We do not cover the ability of these distributed representations to provide (probably lossy) compression. (ii) We do not study the properties of DrDAM relative to MrDAM when DrDAM is allowed to have different step sizes and number of layers than MrDAM. A further limitation of our work is the limited number of datasets on which we have characterized the performance of DrDAM.B Approximation error when increasing the number of stored patterns in DrDAM § 4.1 validated eq. ( 13), confirming that approximation error decreases as the number of random features Y increases under constant number of stored patterns K. We can also consider a related but different question: under constant number of random features Y , how does approximation error behave when increasing the number of stored patterns K? Intuitively, DrDAM's approximation should be good when a small number of patterns are stored in the network, and this approximation should worsen as we increase the number of stored patterns.Figure 5 validates this intuition empirically, with the caveat that random queries generally improve in accuracy because the probability of being near a stored patterns (a regime that generally leads to higher accuracy of retrievals, see § 4) increases as we store more patterns into the network. For this experiment, Y = 2e5 was held constant across all experiments and each plotted approximation error is averaged over a number of queries equal to the number of stored patterns K. The experimental design otherwise exactly replicates that of fig. 3 . 14)) increases as the number of stored patterns K increases (except at random starting positions, where more stored patterns increases the probability that a random query is closer to a memory, a regime that leads to higher accuracy of the retrievals, see fig. 3 ), keeping Y = 2e5 constant across all experiments.Different basis functions can be used to approximate the RBF kernel used in the energy of the memory representation of the DAM in eq. ( 7). We considered the following kernels ("Cos", "SinCos", "Exp", "ExpExp"), rewritten here asφ Cos (x) = 2 Y     cos( ω 1 , x + b 1 ) cos( ω 2 , x + b 2 ) . . . , cos( ω Y , x + b Y )     , φ SinCos (x) = 1 √ Y          cos( ω 1 , x ) sin( ω 1 , x ) cos( ω 2 , x ) sin( ω 2 , x ) . . . , cos( ω Y , x ) sin( ω Y , x )          , φ Exp (x) = exp(-∥x∥ 2 2 ) √ Y     exp( ω 1 , x + b 1 ) exp( ω 2 , x + b 2 ) . . . , exp( ω Y , x + b Y )     , φ ExpExp (x) = exp(-∥x∥ 2 2 ) √ 2Y          exp(+ ω 1 , x ) exp(-ω 1 , x ) exp(+ ω 2 , x ) exp(-ω 2 , x ) . . . , exp(+ ω Y , x ) exp(-ω Y , x )         , where ω α ∼ N (0, I D ), α ∈ Y are the random projection vectors and b α ∼ U(0, 2π) are random "biases" or shifts in the basis function.Figure 6 shows how well the above basis functions approximated the true energy and energy gradient at different values for β and size of feature dimension Y . Specifically, given the Letter dataset [46] which consists of 16-dimensional continuous vectors whose values were normalized to be between [0, 1 √ D ], we randomly selected 900 unique data points, storing 500 patterns into the memory and choosing the remaining 400 to serve as new patterns. We then compared how well the energy and energy gradients of the chosen basis function approximates the predictions of the original DAM.We observe that the trigonometric basis functions (i.e., either Cos or SinCos) provide the most accurate approximations for the energy and gradients of the standard MrDAM, especially in the regime of high β which is required for the high memory storage capacity of DenseAMs. Surprisingly, the Positive Random Features (PRFs) of [18] do not perform well in the dense (high β) regime; in general, trigonometric features always provide better approximations than the PRFs.We conclude that the SinCos basis function is the best approximation for use in the experiments reported in the main paper, as this choice consistently produces the best approximations for the energy gradients across all values of β.In performing the qualitative reconstructions shown in fig. 1 , we used a standard MrDAM energy (eq. ( 7)) configured with inverse temperature β = 60. We approximated this energy in a DrDAM using the trigonometric "SinCos" basis function shown in eq. ( 8) configured with feature dimension Y = 1.8e5. The four images shown were selected from the Tiny Imagenet [11] dataset, rasterized into a vector, and stored in the memory matrix a MrDAM, resulting in a memory of shape (4, 12288) . Energy descent for both MrDAM and DrDAM used standard gradient descent at a step size of 0.1 until the dynamics of all images converged (for fig. 1 after 300 steps, see energy traces). Visible pixels are "clamped" throughout the duration of the dynamics by zeroing out the energy gradients on the visible top one-third of the image. Experiments performed on the 16-dimensional Letters dataset [46] .In MrDAM, the memory matrix necessarily grows linearly when storing new patterns ξ µ . However, the distributed memory tensor T of DrDAM does not grow when new patterns are stored. This means it is possible to compress the memories into a smaller tensor T where Y < NumPixels, provided that we operate in a regime that allows larger approximation errors in the retrieval and smaller initial occlusions. Figure 2 shows a variation of the setting of fig. 1 where stored patterns are actually compressed into DrDAM's memory tensor, successfully storing 20 * 12288 pixels from a distributed tensor of size Y = 2e5 and retrieving the memories with 40% initial occlusion of the queries, a ∼20% reduction in the number of parameters compared to MrDAM. All other hyperparameters are the same as was used to generate fig. 1 , and convergence on all images occurs after 1000 steps.All experiments are performed on a single L40s GPU equipped with 46GB VRAM. Experiments were written and performed using the JAX [47] library for tensor manipulations. Unless otherwise noted, gradient computation was performed using JAX's powerful autograd mechanism. Experimental code with instructions to replicate the results in this paper are made available at this GitHub repository (https://github.com/bhoov/distributed_DAM), complete with instructions to setup the coding environment and run all experiments. Putting the runtimes together, and using the maximum of the peak memories gives us the statement of the theorem.Note that, comparing the computational complexities of MrDAM in proposition 1 to that of DrDAM in theorem 1 does not directly provide any computational improvements as it would depend on the choices of D, K, L, Y . The main point of these results is to highlight, that once the memories are processed via ProcMems, the energy descent with DrDAM requires computation and memory that only depends on D and Y . And together with theorem 2 and corollary 1, we characterize situations 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 function) but not K. Here we will make use of the following result from Li et al. [48] : Lemma 1 (adapted from Li et al. [48] Lemma B.1). For x, z ∈ R K with max i,j∈ K (x i -x j ) ≤ δ and max i,j∈ K (z i -z j ) ≤ δ, we have the following:EQUATION)We now develop the following results:Lemma 2. Under the conditions and notation of theorem 2, for x, z ∈ X , we haveEQUATIONProof. Given the energy function in eq. ( 11), we can write the energy gradient ∇ x E(x) as:EQUATIONwhereEQUATIONEQUATIONEQUATIONEQUATIONwhere we applied lemma 1 to the softmax term in the right hand side of eq. ( 22) with δ = β/2 since all pairwise distances in X are in [0, 1].EQUATIONEQUATIONsince ∥ξ µ ∥ ≤ 1 and ∥x + z∥ ≤ ∥x∥ + ∥z∥ ≤ 2. Putting eq. ( 26) in eq. ( 23), and using the fact that ∥Ξ∥ 2 ≤ K, we haveEQUATIONgiving is eq. ( 16) in the statement of the lemma.Given the structure of the energy gradient in eq. ( 18) of the energy function in eq. ( 11), we consider a specific energy gradient for this specific energy function instead of the generic energy gradient in eq. (10) . We can rewrite the exact energy gradient asEQUATIONUsing random feature maps, we can write the approximate gradient asEQUATIONEQUATIONwhere we again just need to store T and R as defined above and do not need to maintain the original memory matrix Ξ.EQUATIONWriting out the recursion using induction, we can show thatEQUATIONEQUATION)Replacing the values of A and B above gives us the statement of the theorem.F.2.2 Dependence on the initial energy E(x) of the input.The divergence upper bound in eq. ( 12) (in theorem 2) depends on the term exp(βE(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 (which is the assumption A1 in theorem 2), E(x) ≤ 1 2 -log K β , implying that exp(βE(x)) ≤ exp(β/2)/K, and we can replace this in the upper bound and remove the dependence on E(x).However, an important aspect of our analysis is that the bound is input specific, and depends on the initial energy E(x). As discussed above, this can be upper bounded uniformly, but our bound is more adaptive to the input x.For example, if the input is initialized near one of the memories, while being sufficiently far from the remaining (K -1) memories, then exp(βE(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(x) ≈ -(1/β) log(exp(-βr/2) + (K -1) exp(-β/2)), implying thatEQUATIONFor sufficiently small r < 1, the above quantity can be relatively small. If, for example, r ∼ O(log K), then exp(βE(x)) ∼ O(K β ), while r → 0 gives us exp(βE(x)) → O(1). This highlights the adaptive input-dependent nature of our analysis.NeurIPS Paper Checklist▶ The answer NA means that the abstract and introduction do not include the claims made in the paper. ▶ The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. ▶ The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. ▶ It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.▶ The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. ▶ The authors are encouraged to create a separate "Limitations" section in their paper. ▶ The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. ▶ The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. ▶ The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. ▶ The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. ▶ If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. ▶ While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.▶ The answer NA means that the paper does not include theoretical results. ▶ All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. ▶ All assumptions should be clearly stated or referenced in the statement of any theorems. ▶ The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. ▶ Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. ▶ Theorems and Lemmas that the proof relies upon should be properly referenced.▶ The answer NA means that the paper does not include experiments. ▶ If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. ▶ If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. ▶ Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. ▶ While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. . ▶ Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.▶ The answer NA means that the paper does not include experiments. ▶ The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. ▶ The full details can be provided either with the code, in appendix, or as supplemental material.▶ The answer NA means that the paper does not include experiments. ▶ The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. ▶ The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. ▶ The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).▶ The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics. ▶ If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. ▶ The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Throughout the paper we use bold symbols for denoting vectors and tensors, e.g., ξ µ is a D-dimensional vector in the space of neurons for each value of index µ. Individual elements of those vectors and tensors are denoted with the same symbol, but with plain font. In the example above, these individual elements have an explicit vector index, e.g., ξ µ i . Same applies to vectors in the feature space introduced later.This is true for all DenseAMs with the exception of the power model of Krotov and Hopfield[2], which can be written using n-index tensors Ti 1 ,i 2 ,...,in in analogy with the 2-tensor Tij as in eq. (2).We are eliding the dg(x)/dx = (1/∥x∥2)[ID -(1/∥x∥ 3/22 )xx ⊤ ] term for the ease of exposition.Kernel functions that only depend on (x -x ′ ) and not individually on x and x ′ .A technical detail here is that while we are using Y random samples, we are actually developing a 2Ydimensional feature map φ : R D → R 2Y -we can get a Y dimensional feature map by dropping the sin(•) terms in the trigonometric features (and add a random rotation term b α , α ∈ Y to the cos(⟨ω α , x⟩ + b α ) term), and the exp(-•) term in the exponential features. This modification (using 2Y features instead of Y ) reduces the variance of the kernel function approximation[18, Lemma 1,2].If Q(•) = log(•) in eq. (9), note that the inner product between unconstrained choices of φ can be negative but the argument to log must not be; thus, we clip the value to the log to some small ε > 0. 


Decision: The present study proposes a kernel approximation of the dense associative memory. Connecting the random feature approximation and the dense associative memory is novel. After comprehensive author-reviewer discussions, reviewers have carefully checked the mathematical derivations in the paper and the authors' replies have addressed most of the concerns. Therefore I recommend accepting the present paper. Meanwhile, reviewers pointed out the original manuscript hasn't systematically compared with related work and fully discussed its limitations. Please revise the manuscript based on the reviewers' comments.

Reviews: review: paper_summary: paper_summary: The paper proposes to interpret the energy function of Dense Associative Memory as relying on a kernel that can be approximated by kernel-specific random feature maps. 
The approximation allows to condensate the stored patterns into a tensor whose size is independent of the number of patterns stored, similarly to what can be done in classical and polynomial Hopfield networks. 
New patterns can then be incorporated without changing the dimensionality of the parameter space. 
They provide bounds for the approximation error of the iterates in the gradient descent procedure that uses their energy approximation.
strength_weakness: strength_weakness: - The main limitation of the work in my opinion is that one has to go to very  large values of the feature size Y in order to have a good approximation.  In fact, looking at the error bound in eq. (12), it seems that Y has to be taken of the order of O(K^2*D) in order to have a good approximation, which is much larger than the size of the memory matrix (K*D). This not taking into account the exp(beta*E) term in the bound, which could penalize high-energy configurations a lot.

- Numerical Experiments are limited and not fully convincing. For instance, in Fig. 1 the 4x12288=49152 memory matrix has to be replaced by a several times larger Y-sized vector in order to obtain a good approximation.
questions: questions: - Can the author show a plot similar to Fig. 2 but now showing the theoretichal prediction from eq. 12 (say for L=1 and alpha=1) compared to the actual error?
Probably this information could just be plotted in Fig. 2B. 

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

- In order to help the reader and improve consistency, p in Algorithm 1 and at the beginning of Section 3 could denote the same thing.

- Assuming that the random feature version is considered as DAM per se instead of an approximation to another DAM, could the author comment on its capacity in presence of random memories? It is linear in Y?

- line 215. Usually, the EDP model also contains an x^2 term outside the logarithm.
limitations: limitations: The authors could discuss more the limitations of their work. In particular, the fact that the approximation requires a very large feature size Y in order to be accurate. This could limit the practical use of the method.
paper_summary: paper_summary: This paper studies a method to modify associative memory network weights when introducing new memories. The proposed uses random features and is shown to approximate the energy function of the conventional ones.
strength_weakness: strength_weakness: 1. Why using hamming distance when calculating retrieval error when the theoretical results use L2?
2. To my understanding, the proposed method is an approximation to DAM. Thus the paper should at least compare the proposed method to DAM in thr experimental section.
3. The field of associative memories, Hopfield networks are getting increased attention recently, I think a related work section would benefit this paper a lot.
questions: questions: Please refer to weaknesses.
limitations: limitations: This paper addresses its limitations in the appendix.
paper_summary: paper_summary: The paper offers a kernel-based approximation of Dense Associative Memory that allows for Hebbian encoding in a space of randomized basis functions. The main advantage when compared with the exact approach is that information concerning all patterns is shared in a single weight tensor, without requiring additional weights for each new pattern.

The authors provide some complexity results and bounds on the Euclidean deviation from the exact retrieved pattern in the case of exponential Dense Associative Networks (i.e. modern Hopfield networks). In a series of numerical experiments, the author show that the approximation breaks down for low values of the inverse temperature and for large number of patterns when compared with the number of basis functions.
strength_weakness: strength_weakness: 1) The embedding of this paper in the existing literature is limited. Feature expansion methods have been studied for classical Hopfield and generalized models [1,2,3], and there are uncited existing papers connecting Dense Associative Memories and kernel methods [4]. It would also be useful to discuss the recent results connecting exponential Dense Associative Memories (i.e. modern Hopfield networks) with generative diffusion models [5], since as pointed out in the paper the connection provides an alternative way to learn the same energy function in a fixed synaptic structure. It could also be useful to discuss more theoretical results involving random features, for example [6] and [7].
It would be good to have this treatment organized in a proper Related Work section. 

2) While the approximation is based on a sound idea, its derivation is very informal. It would be very useful to derive the formula using variational techniques or other known systematic methods for deriving approximations. It could also be interesting to connect it with similar approximations in Gaussian Processes, since kernel feature expansions are commonly used for GPs.

3) 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. 

4) Given the simplicity of the proposed method and its similarities with known approaches such as [TODO], I am not convicted that the contribution is relevant enough for this conference.

References:
[1] Liwanag, Arnold, and Suzanna Becker. "Improving associative memory capacity: one-shot learning in multilayer Hopfield networks." Proceedings of the 19th Annual Conference of the Cognitive Science Society. Vol. 442. 1997.
[2] Barra, Adriano, Matteo Beccaria, and Alberto Fachechi. "A new mechanical approach to handle generalized Hopfield neural networks." Neural Networks 106 (2018): 205-222.
[3] Yilmaz, Ozgur. "Machine Learning Using Cellular Automata Based Feature Expansion and Reservoir Computing." Journal of Cellular Automata 10 (2015).
[4] Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models
[5] Ambrogioni, Luca. "In search of dispersed memories: Generative diffusion models are associative memory networks." arXiv preprint arXiv:2309.17290 (2023).
[6] Negri, Matteo, et al. "Random Feature Hopfield Networks generalize retrieval to previously unseen examples." Associative Memory {\&} Hopfield Networks in 2023. 2023.
[7] Negri, Matteo, et al. "Storage and learning phase transitions in the random-features hopfield model." Physical Review Letters 131.25 (2023): 257301.
questions: questions: 1) 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?
limitations: limitations: The limitations of the proposed approximate method are adequately discussed.
paper_summary: paper_summary: This paper introduce an iterative random feature Dense Associative Memory Model (DenseAM).
It is a kernel approximation of the standard DenseAMs using random feature decomposition and approximation. 
The authors term this approach to DenseAMs as distributed representation/formulation of memory (DrDAM).

Theoretically, they analyze the time complexity of the proposed method (Thm1) and the approximation error (Thm2), both benchmarked against the standard DenseAM (MrDAM). 
Experimentally, they evaluate the approximation accuracy of DrDAM's energies and gradients, defined as the MAE difference between DrDAM and MrDAM, and the retrieval accuracy of DrDAM. 
Importantly, their analysis of DrDAM considers its iterative nature, distinguishing their contribution from prior works.

In sum, they address important research questions and their approach is natural and intuitive based on recent advances in the random feature kernel trick.
strength_weakness: strength_weakness: ## Summary of Weaknesses

Overall, this paper presents a good idea, but it seems rushed, which affects the contribution of an otherwise very interesting work. Regardless of the final decision, I hope the authors find my comments helpful in further refining their draft.

There are a few areas that could benefit from further improvement and clarity:

* **Experiments:** The current experimental results would be strengthened by including comparisons with established baselines and more ablation studies.
* **Clarity:** Some of the theoretical results are difficult to interpret due to minor typos and a need for increased mathematical clarity.
* **Motivation:** The motivation and problem statement could be articulated more convincingly. Even after multiple readings of the intro, it remains unclear if distributed representation is truly parameter-efficient beyond the nonparametric sense.
* **Related Works:** Additionally, while not critical, the idea of Random Feature DenseAM (and Kernel DenseAM) has been discussed in prior works. The related discussion in this paper could be expanded to better position the contribution within the existing literature. For examples:
  * ```Random Feature DenseAM``` Random Feature Hopfield Networks generalize retrieval to previously unseen examples https://openreview.net/forum?id=bv2szxARh2)
  * ```Random Feature DenseAM``` Nonparametric Modern Hopfield Models https://arxiv.org/abs/2404.03900
  * ```Kernel DenseAM``` Kernel Memory Networks: A Unifying Framework for Memory Modeling  https://arxiv.org/abs/2208.09416
  * ```Kernel DenseAM``` Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models  https://arxiv.org/abs/2404.03827
  * ```Kernel DenseAM``` Bridging Associative Memory and Probabilistic Modeling https://arxiv.org/abs/2402.10202



**Note:** I have tried my best to evaluate this paper. I spent much more time on this review than on my previous ones because I like this paper. Still, I might have missed something. Please correct me if I am wrong with fair justifications. I am open to changing my opinion and raising the score.

---

## Major: My main concern with this paper is its soundness and inadequate experimental evidence

### General


* ```line23:``` "Memory representation" is a strange term for me. If you are referring to the way of encoding memory patterns onto the energy landscape, isn't it "memory encoding"? Representation generally involves learning, and to my understanding, there is no learning here.

  >Thus, in situations when the set of the memories needs to be expanded by introducing new patterns one must introduce additional weights.

  A side comment: this statement implies nonparametric, as suggested in [17].

* ```distributed representation```: I find the description of distributed representation vague. With more memories, $K$ increases, resulting in more degrees of freedom in $\mathbf{T}$. You can say the total number of entries in $\mathbf{T}$ is fixed, but not the number of parameters, unless you clearly define "parameters" differently. The current draft makes it difficult to parse the soundness.  I believe the idea of distributed representation deserves more elaboration. The current draft seems nonparametric to me.

  In my current review, I assume what is stated in lines 29-30 is correct.

* ```Sec3```: Section 3 is hard to follow due to typos and the lack of clarity.

* ```Missing Broader Impacts```: The authors didn't discuss both potential positive and negative societal impacts except in the checklist. My understanding is that this discussion needs to be included in the main text or the appendix, as the checklist is not considered part of the paper.

---

### Theory


* ```line92```: Eqn. (6) is hard to follow without clearly defined $S,s$. 

  I suppose $S:\mathbb{R}^d\times \mathbb{R}^d\to \mathbb{R}$ which makes $s\in\mathbb{R}$ a scalar realization of $S$?


* ```No fixed point convergence results```: Per my understanding, DenseAMs are energy models with memories stored in their local minima. Memory retrieval is conducted through energy minimization. This setting requires convergence between local minima and fixed points of retrieval updates, such as the convergence results of [Ramsauer2020,Hu2023]. Otherwise, there may be unbounded retrieval error due to the mismatch between local minima and fixed points of retrieval updates. Specifically, I believe lines 106-110 are at best ambiguous.

  * [Ramsauer2020] Hopfield Networks is All You Need. Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich, M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M., Sandve, G.K., and Greiff, V., 2020. arXiv preprint arXiv:2008.02217.
  
  * [Hu2023] On Sparse Modern Hopfield Model. Hu, J.Y.C., Yang, D., Wu, D., Xu, C., Chen, B.Y., and Liu, H., 2023. Advances in Neural Information Processing Systems, 36.

* ```Theorem 1```: I feel Thm1 may be incorrect. Could you elaborate more on this?

  * **My understanding:** Let $L$ be the number of updates, $K$ be the number of stored memories, $D$ be the memory dimension, and $Y$ be the feature space dimension. DrDAM improves time complexity from $O(LKD)$ to $O(D(Y K + L(Y + D))$, and improves peak memory from $O(KD)$ to $O(Y+D)$.
  * **Comment1:** $O(D(Y K + L(Y + D))$ is clearly a typo and makes the result hard to parse.
  * **Comment2:** Without specifying the relationships between $L$, $K$, $D$, and $Y$, it's hard to tell if this is truly an improvement. I can easily think of counterexamples.

  Given these, can you kindly elaborate more on the significance of thm1?


* ```Theorem 2```: Eqn. (12) is strange. Is there any guarantee ensuring $\alpha L(1+2K\beta e^{\beta/2}) < 1$? If not, it doesn't make sense that more updates would result in larger error. Perhaps this is related to the missing fixed point convergence?

---

### Experiments

* ```No Comparison to existing works:``` there is no baseline compared. 

* ```No efficiency evaluation1:``` Please include ablation studies on changing $L,K,D,Y$ to verify Thm1. 

* ```No efficiency evaluation2:``` Please also compare the efficiency with other methods, including linear, top-K, random feature, and random masked from [17], as well as dense [Ramsauer2020], sparse [Hu2023], and generalized sparse [Wu2023] MHNs. For example, the current draft needs some figures similar to Fig. 4 of [17] to justify the efficiency. Please do whatever makes sense to you. For instance, you can pick just two out of [Ramsauer2020, Hu2023, Wu2023] since they share similar structures.

  * [Ramsauer2020] Hopfield Networks is All You Need. Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich, M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M., Sandve, G.K., and Greiff, V., 2020. arXiv preprint arXiv:2008.02217.
  
  * [Millidge2022] Universal Hopfield Networks: A General Framework for Single-Shot Associative Memory Models. Millidge, B., Salvatori, T., Song, Y., Lukasiewicz, T., and Bogacz, R., 2022, June. In International Conference on Machine Learning (pp. 15561-15583). PMLR.
  
  * [Wu2023] Stanhop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Prediction. Wu, D., Hu, J.Y.C., Li, W., Chen, B.Y., and Liu, H., 2023. arXiv preprint arXiv:2312.17346.
  
  * [Hu2023] On Sparse Modern Hopfield Model. Hu, J.Y.C., Yang, D., Wu, D., Xu, C., Chen, B.Y., and Liu, H., 2023. Advances in Neural Information Processing Systems, 36.



* ```Compare with existing kernel DenseAMs.``` Also, a direct comparison with existing kernel methods is also necessary. For example,
  * Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models. Wu, D., Hu, J.Y.C., Hsiao, T.Y., and Liu, H., 2024. arXiv preprint arXiv:2404.03827.
  
  * Kernel Memory Networks: A Unifying Framework for Memory Modeling. Iatropoulos, G., Brea, J., & Gerstner, W., 2022. Advances in Neural Information Processing Systems, 35, 35326-35338.
  
  * Bridging Associative Memory and Probabilistic Modeling. Schaeffer, R., Zahedi, N., Khona, M., Pai, D., Truong, S., Du, Y., Ostrow, M., Chandra, S., Carranza, A., Fiete, I.R., and Gromov, A., 2024. arXiv preprint arXiv:2402.10202.

---

## Minor

* ```Inadequate Related Work Discussion```: A paragraph discussing related works is given at the end of the introduction. However, I feel it could be made more comprehensive to provide more background on the evolution of ideas and existing works in this field. At least, I feel the current draft is hard for a non-expert in DenseAMs to follow. Please see the following points.

* ```line38:``` I believe here can be benefited by including more comprehensive references. There are other recent works showing exponentially large memory storage capacity in various settings and dense associative memory (or modern Hopfield) networks/models. For examples: (I am not sure of their exact relevance, so I will leave it to the authors to decide whether they should be included and discussed.)

   * Hopfield Networks is All You Need. Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich, M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M., Sandve, G.K., and Greiff, V., 2020. arXiv preprint arXiv:2008.02217.
  * Kernel Memory Networks: A Unifying Framework for Memory Modeling. Iatropoulos, G., Brea, J., & Gerstner, W., 2022. Advances in Neural Information Processing Systems, 35, 35326-35338.
  * On Sparse Modern Hopfield Model. Hu, J.Y.C., Yang, D., Wu, D., Xu, C., Chen, B.Y., and Liu, H., 2023. Advances in Neural Information Processing Systems, 36.
  * Stanhop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Prediction. Wu, D., Hu, J.Y.C., Li, W., Chen, B.Y., and Liu, H., 2023. arXiv preprint arXiv:2312.17346.
  * Bridging Associative Memory and Probabilistic Modeling. Schaeffer, R., Zahedi, N., Khona, M., Pai, D., Truong, S., Du, Y., Ostrow, M., Chandra, S., Carranza, A., Fiete, I.R., and Gromov, A., 2024. arXiv preprint arXiv:2402.10202.
  * Sparse and Structured Hopfield Networks. Santos, S., Niculae, V., McNamee, D., and Martins, A.F., 2024. arXiv preprint arXiv:2402.13725.
  * On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis. Hu, J.Y.C., Lin, T., Song, Z., and Liu, H., 2024. arXiv preprint arXiv:2402.04520.
  * Outlier-Efficient Hopfield Layers for Large Transformer-Based Models. Hu, J.Y.C., Chang, P.H., Luo, R., Chen, H.Y., Li, W., Wang, W.P., and Liu, H., 2024. arXiv preprint arXiv:2404.03828.


* ```line46:``` Similarly, here can be benefited by including more recent references
  > DenseAM family [...] 

* ```line51```: A similar motivating question is asked and explored in [17] from a kernel regression perspective. I agree this paper contributes something different and even beyond [17]. However, given the similarity of aims between the two, the current draft should:
  1. State the overlaps between the two works (both use a kernel approach to DenseAMs, and...).
  2. State the clear distinctions between the two works (both use a kernel approach to DenseAMs, but...).

  Such discussion will help readers parse the contributions of this work, which is currently lacking.

  [17] Jerry Yao-Chieh Hu, Bo-Yu Chen, Dennis Wu, Feng Ruan, and Han Liu. Nonparametric modern hopfield models. arXiv preprint arXiv:2404.03900, 2024. URL https://arxiv.org/pdf/2404.03900.pdf.
 

* ```line92```: 
  > those results have been recently applied to associative memory [15].

  I might have missed something, but it would be better to make the discussion of prior work more complete if it's presented in its current form (e.g., a paragraph highlighting the novelty and contributions benchmarked against existing works). The application of the kernel trick to associative memory is not new. While [16,17] are discussed right after [15], I feel it's better to cite them together as [15,16,17]. Additionally, there are two papers related to the kernel trick in associative memory, which I have attached below. Again, I am not sure of their exact relevance, so I will leave it to the authors to decide whether they should be included and discussed.

  - Iatropoulos, G., Brea, J., & Gerstner, W. (2022). Kernel memory networks: A unifying framework for memory modeling. Advances in neural information processing systems, 35, 35326-35338.
  
  -  Schaeffer, R., Zahedi, N., Khona, M., Pai, D., Truong, S., Du, Y., Ostrow, M., Chandra, S., Carranza, A., Fiete, I.R. and Gromov, A., 2024. Bridging Associative Memory and Probabilistic Modeling. arXiv preprint arXiv:2402.10202.

* ```line97```: 
  > Another paper [17] uses kernels for studying the sparse modern Hopfield network. 

  This is incorrect. 

  As stated in their abstract, [17] presents a general framework (referred to as nonparametric) to analyze and design modern Hopfield networks. The sparse network is just a special case of their framework. Additionally, [17] has already introduced the construction of random feature HMNs. While this construction lacks detailed analysis, which is a limitation they acknowledged, it would be more accurate to say that the submitted draft serves as a strong companion to [17] with rigorous theoretical and empirical results. I understand that the authors are not obliged to treat arXiv preprints (unpublished papers) too seriously, but it is better to give accurate credit to existing works when possible. To clarify, I am very happy to see this draft improves the results/proposal of [17] with detailed analysis, including multiple retrieval updates.

* I did not check the proofs line by line. However, I had a quick skim through them and found some typos and areas for improvement. Please do another round of proofreading if possible.


---

### Update 2024/08/07: raise score from 4 -> 5 -> 6 -> 7
questions: questions: * ```line109```: why you call the number of updates as *layers*? Are you recurrently passing the output as input to the same network or the network really has many layers? For example, recurrent layer is RNN sense is the later. 


* ```Proposition 1,2,3```: what is peak memory? why we should care about it?

* ```Time Complexity```: I appreciate the analysis of the computational complexity of the proposed method. From my view, this proposal is a special case of [Hu2024] with $L=1$ (where $L$ is the sequence length in their analysis). [Hu2024] provides a characterization of all sub-quadratic (efficient) variants of the modern Hopfield model. Essentially, your proposal is an efficient approximation to the softmax DenseAMs. Hence, the relevance holds. Can you discuss how your proposal fits into the results of [Hu2024]?
  
  * [Hu2024] Hu, J.Y.C., Lin, T., Song, Z. and Liu, H., 2024. On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis. arXiv preprint arXiv:2402.04520.


* ```line255, Exp Observation 2```: This observation is a bit counterintuitive. Normally, large $\beta$ means low-temperature region and leads to more stable/accurate retrieval, e.g., infinity $\beta$ leads to argmax-retrieval. Why random DrDAM shows otherwise?  



* ```Fig3```: Intuitively, why larger $\beta$ needs larger $Y$?

* ```line303```: What's the point of approximating energies and update dynamics? Shouldn't the significance lie in the approximation error of retrieval?

* I am wondering if you have explored the learning aspect of the proposed method. It is known that many DenseAMs are connected to transformer attention and can be used as a learning model or layer. Can you explore this part a bit as in [17]? If not, please explain why.

* Can you kindly remind me which part of this work supports the claim "making it possible to introduce new memories without increasing the number of weights"?
limitations: limitations: There is a limitation section but no broader impact or impact statement expect in the checklist.


Appendix A of the draft acknowledges that the experimental explorations are limited. However, it would benefit from discussing comparisons with baselines and including some vital ablations. This would help clarify the contribution and soundness of the proposed method. See above for other limitations.

Comments: title: raising my score
comment: Dear Reviewers, Dear Area Chair,

Once again, thanks a lot for taking the time to read our work and to communicate to us your feedback. On reading the reviews, we are very happy to see many enthusiastic statements, e.g., "The paper addresses perhaps the greatest limitation of Dense Associative Memories with non-quadratic energy" from reviewer wQ3r. Such statements mean a lot to us, and we are thankful for these encouraging comments.

There is still one borderline reject score (4) from reviewer wQ3r, and we have not heard from them any response to our rebuttal. Since there is less than 24 hours left for us to be able to communicate with reviewers, we kindly ask reviewer wQ3r to consider increasing the numerical score for our submission.

We are thankful to reviewers B4qp and xsUY for raising their scores to 6 and to reviewer 9NBh for raising their score to 7! With the decision-making process soon underway, if B4qp or xsUY believe our paper is worthy of acceptance, we kindly ask considering a further increase of the scores to a "full accept" (7). We remain available to resolve any outstanding issues that would bump our paper from a borderline accept to an accept in the remaining time dedicated for discussion.

Sincerely,
Authors
I'm satisfied with the answers and raising my score.
With the discussion period soon drawing to a close, we wanted to check in to see if our rebuttal has satisfactorily addressed the concerns you raised in your initial review? If you have any further questions or require additional clarifications, we would be more than happy to engage in further discussion.
With the discussion period soon drawing to a close, we wanted to check in to see if our rebuttal has satisfactorily addressed the concerns you raised in your initial review? If you have any further questions or require additional clarifications, we would be more than happy to engage in further discussion.
Thanks for the response.
I think the authors have addressed all my concerns, I will raise my score accordingly.
The connected ring is just a special case that current theory can't justify. This is an example where energy stable points might not coincide with retrieval update/dynamics fixed points. This is exactly my point—fixed-point convergence and energy convergence are not the same thing.

While it’s hard to engineer, it could occur in certain configurations of stored memory patterns. For completeness and rigor in theoretical work, it's important to address this. If a theory doesn't hold under certain scenarios, one should clarify the assumptions or provide further theoretical justifications, as mentioned in [1].

Thank you for the clarification. I have no further issues with Thm2. I suggest the authors to polish the draft according to our discussion and include a remark on the parameter region where it's not vacuous. It will clarify things for general audience.

Thank you! Good luck!
We thank the reviewer for seeing the value in our work and increasing their score! In the spirit of a healthy discussion period, we will continue to respond to your questions:

> 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?
> 

It would require a huge amount of fine-tuning for $\beta$ and the location of memories to engineer a connected ring, or any other type of flat directions in the energy defined by Eq (11). Here we are working in the dense regime of DenseAMs, when $\beta$ is sufficiently large, so that every memory is a point attractor. Flat directions are common in more advanced models of AM, such as [Energy Transformer](https://arxiv.org/abs/2302.07253), but these are not considered in this work.

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

You are absolutely justified in your confusion and we apologize for this clash of notation, where $\alpha$ can represent both the index into the distributed memory and discrete gradient-descent step size. The $\alpha$ in Eq (12) is the “gradient descent step size” first defined in Eq (5), and used in Cor 1 to constrain the divergence. We will refine this notation in the final draft — thank you for spotting this.
**Edited 15mins later:** After further consideration, the fixed-point convergence issue is just food for thought/discussion but not a fatal flaw in this work. The work is still refreshing overall, so I am raising my score to 7. This paper is one of those with real new ideas. I recommend it for acceptance.

However, I hope the authors can refine the related discussions based on my comments. Alternatively, if I am mistaken, please clarify where I went wrong. I'd really appreciate it.
> 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.)
Thank you for your questions. We are happy to provide further clarity.

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

We understand that the reviewer is asking for us to choose configurations of the hyperparams in Thm 1 that cause DrDAM to be more/less efficient (in terms of memory and computational complexity) than the baseline MrDAM. Per your repeated requests, we will add experiments on select configurations to the final draft, though “efficiency” was not an emphasis of our original draft. On re-reading our submission, we find mention to efficiency in only one sentence, in our Conclusion: “We have demonstrated how this can be done efficiently…” We will modify this sentence to prevent future confusion. Thank you for identifying this. Just to reiterate, theoretically, the peak memory complexity of MrDAM is $O(KD)$ vs $O(Y+D)$ for DrDAM. Given that in the interesting regime $Y\sim D/\varepsilon^2$ (Corollary 1), DrDAM is more memory efficient than MrDAM if $K>const/\varepsilon^2$. For running time complexity (ignoring memory encoding), which is $O(LKD)$ for MrDAM vs. $O(LD(Y+D))$ for DrDAM, MrDAM is generally more efficient than DrDAM.  

> …the convergence of fixed point and stable point of the energy landscape (local minima) are different concepts…
> 

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. The argument we presented above is mathematically rigorous and correct. For intuition, note that the energy landscape of Eq (11) “looks like” a mixture of Gaussians that has been inverted s.t. 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” (where $\nabla_{\mathbf{x}} E = \frac{dx}{dt} = 0$) of the dynamics.

Imagine for simplicity that $\beta$ is large and $x_i$ is sufficiently close to one of the memories, say memory 1 (i.e., $\xi^1_i$), then only one of the exponential terms in Eq 11 is appreciably different from 0. Thus, in this limit the energy can be simplified to $E \approx \frac{1}{2} \sum\limits_{i=1}^D (\xi^1_i - x_i)^2$, locally around memory 1. This is just a quadratic function. Optimization is very simple and the solution for the fixed point is $x_i=\xi^1_i$ both from solving the continuous time differential equation and from minimizing the energy. There are no any subtleties or ambiguities here.  

> can you clarify if $E$ is convex?
> 

The energies of DenseAMs are non-convex functions because they have many local minima.

> For one, you don't provide a convergence rate… you only converge to a region defined by the termination of the gradient descent algorithm
> 

A convergence rate is not necessary to prove convergence. 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. Maybe you refer to some numerical precision errors? If so, of course everything that we do is impacted by those errors, but they are small. So, in reality we always stop $10^{-6}$ or so away from the true fixed point, but this does not impact any of our methods. 

> If your derivation is about stable point of energy landscape (local minima), then how can you ensure fixed point convergence?
> 

We believe we have answered this question above.

> it's impossible to have $\delta < 1$ given $\alpha, L, K$ are all positive constants greater than 1.
> 

This statement incorrectly assumes that $\alpha > 1$: $\alpha$ (our discrete gradient-descent step size) is a strictly positive scalar that approaches the continuous setting as $\alpha \rightarrow 0$. In all the results presented in our paper $\alpha<1$.
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!
> Since it's approximation to single step of iterative algorithm, can you comment on the "iterative" error bound? Is it sth that you analyze or the current results are just for single step?
> 

Nothing in our work is about a single step update. We only consider fully recurrent DenseAMs with many iterative updates. Just to reiterate, the network is defined by the differential equation 

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

which can be discretized to obtain Eq (5) in the submission. All the results in the paper pertain to studying this fully iterative system. The number of iterations can be as big as it is necessary in order to reach the fixed point. 

The fixed points of this trajectory are the "memories" of the system. MrDAM will follow this trajectory by descending the gradient of the standard energy $-\frac{\partial E}{\partial x_i}$ in e.g., Eq (11). DrDAM will follow this trajectory by descending the gradient of the approximate energy $-\frac{\partial \hat{E}}{\partial x_i}$.

To be a "good" approximation, DrDAM must produce similar energies and fixed points as that of MrDAM (Fig 2 and 3). We do not specifically consider the case of single steps down the energy landscape for either MrDAM or DrDAM because we want to guarantee that we have reached the "end" (fixed point) of the dynamics. See the trace of energy over time in Fig 1 to see that a single update step is not guaranteed to converge to a fixed point.

This said, if you are interested in how well DrDAM approximates MrDAM in the single step regime, you can substitute $L=1$ Thm 2, taking 1 discrete step down the energy. The approximation error in this regime is dependent only on the error between the gradients $\nabla \hat{E}$ and $\nabla E$, which we empirically test in Fig 2 of our paper.

> I suppose random feature is for efficiency by sacrificing some accuracy.
> 

We use Random Features to decouple the energy and dynamics of MrDAM from the number of stored patterns $K$. Efficiency is not our goal in this paper. Arguments for the "efficiency" of DrDAM over MrDAM depend on specific choices for $L,Y,D,K$. Thm 1 derives the computational complexity as a function of these hyperparams; Thm 2 derives the error bounds as a function of these hyperparams. In addition, Fig 2 and 3 empirically characterize where DrDAM is a good approximation i.e., when queries have low initial energy at or near the stored patterns, at higher values of $Y$, and at lower values of $K$ and $\beta$. Thus, a user can use the relationships described in our work to choose regimes where DrDAM is more or less efficient than MrDAM. This was our intent when we said "We do not claim improvement over standard MrDAM for the precise reason stated by the reviewer regarding the choices of $L,Y,D,K$”.

> What do you mean by tight analysis?... Thm 1 is about # of operations needed, correct?
> 

Correct, Thm 1 is about the number of operations needed to perform memory retrieval using DrDAM. The complexity can be verified by counting the number of operations during retrieval. Thm 1 emphasizes that the gradient computation `GradComp` is independent of the value of $K$.

> The multiple updates of DrDAM lead to looser error bound. This contradicts to the fixed point convergence argument.
> 

DenseAM in continuous time is a fully contracting system, if the energy decreases along the dynamical trajectory and the energy is bounded from below (please see our rebuttal for the derivation of this result). Both these conditions are satisfied for both MrDAM and DrDAM, thus both these networks are contracting. The bound derived in Eq 12 is for discretized system, Eq (5). You are correct that this bound is useless for $\delta>1$, as it grows to infinity as $L$ is increased. However, it is a very useful bound for sufficiently small $\alpha$, which corresponds to $\delta<1$ (please see Corollary 1). There is no contradiction here, it’s just the bound becomes uninformative for $\delta>1$. As a side note, in our empirical experiments $\alpha$ is always sufficiently small to make sure that $\delta<1$ and that the discretized network is sufficiently close to the network described by continuous time.
> 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.

Thanks for the clarification. 

Since it's approximation to single step of iterative algorithm, can you comment on the "iterative" error bound? Is it sth that you analyze or the current results are just for single step?

Thanks!

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

This is ok. Yet I suggest the authors to refine the wording to ensure preciseness. The examples you mentioned, Fourier & momentum, are mathematically meaningful, e.g., one of the domains connected by some transformation.

> (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 $L,Y,D,K$

Thanks for clarification. Yet this confuses me. I suppose random feature is for efficiency by sacrificing some accuracy, but you don't really ensure DrDAM is more efficient here. Isn't this make the contribution vacuous?

> There is no guarantee, as stated in Thm 2...

This is concerning. The multiple updates of DrDAM lead to looser error bound. This contradicts to the fixed point convergence argument. It is not contraction map toward fixed point.

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

I am confused. What do you mean by tight analysis? Do you mean "everything is exact by counting"? Thm 1 is about # of operations needed, correct?

===

Thanks for your response. Please address above if possible. Thank you!
Thanks for clarifications. Haven't finished going through them. Yet, I understand the rebuttal space is limited. I am ok if the authors use comments to clarify more. I will read them.