On Sparse Modern Hopfield Model
Authors: Jerry Yao-Chieh Hu
Donglin Yang
Dennis Wu
Chenwei Xu
Bo-Yu Chen
Han Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: Hopfield Models; Modern Hopfield Networks; Sparse Attention; Memory Networks
TL;DR: We introduce a sparse modern Hopfield model with memory-retrieval dynamics corresponding to the sparse-structured attention mechanism, enabling robust representation learning, fast convergence, and exponential memory capacity

Abstract: We introduce the sparse modern Hopfield model as a sparse extension of the modern Hopfield model.
Like its dense counterpart, the sparse modern Hopfield model equips a memory-retrieval dynamics whose one-step approximation corresponds to the sparse attention mechanism. 
Theoretically, our key contribution is a principled derivation of a closed-form sparse Hopfield energy using the convex conjugate of the sparse entropic regularizer.
Building upon this, we derive the sparse memory retrieval dynamics from the sparse energy function and show its one-step approximation is equivalent to the sparse-structured attention.
Importantly, we provide a sparsity-dependent memory retrieval error bound which is provably tighter than its dense analog.
The conditions for the benefits of sparsity to arise are therefore identified and discussed.
In addition, we show that the sparse modern Hopfield model maintains the robust theoretical properties of its dense counterpart, including rapid fixed point convergence and exponential memory capacity.
Empirically, we use both synthetic and real-world datasets to demonstrate that the sparse Hopfield model outperforms its dense counterpart in many situations.

On Sparse Modern Hopfield Model
Jerry Yao-Chieh Hu
Donglin Yang! Dennis Wu
Chenwei Xu
Bo-Yu Chen Han Liu
DDpparment of Computer Science, Northwestemn University, Evanston, II. 60208 USA
'Department of Physics, National Taiwan University, Taipei 10617, Taiwan
Department of Statistics and Data Science, Northwestern University, Evanston, IL. 60208 USA
ijuu, dlyang, hibb, exu wtt.northweetern..dd b122020238ntt.edd... hanliufhorttwesteen.com
Abstract
We introduce the sparse modern Hopfield model as a sparse extension of the mod- emn Hopfield model. Like its dense counterpart, the sparse modern Hopfield model equips a memory-retrieval dynamics whose one-step approximation corresponds to the sparse attention mechanism. Theoretically, our key contribution is principled derivation of a closed-form sparse Hopfield energy using the convex conjugate the sparse entropic regularizer. Building upon this, derive the sparse memory retrieval dynamics from the sparse energy function and show its one-step approxi- mation is equivalent the sparse-structured attention. Importantly, we provide -parsity-dependent memory retrieval error bound which is provably tighter than its dense analog. The conditions for the benefits of sparsity arise therefore identified and discussed. In addition, we show that the sparse modern Hopfield model maintains the robust theoretical properties of its dense counterpart, including rapid fixed point convergence and exponential memory capacity. Empirically, we use both synthetic and real-world datasets demonstrate that the sparse Hopfield model outperforms its dense counterpart in many situations.
Introduction
We address the computational challenges of modern Hopfield models by introducing sparse Hopfield model. Our sparse continuous Hopfield model equips memory-retrieval dynamics that aligns with the sparse-structured attention mechanism. By establishing a connection to sparse attention, the proposed model not only offers eecoretically-gouunee enables robust representation learning and seamless integration with deep learning architectures. This approach serves an initial attempt of pushing the correspondence! between Hopfield models and attention mechanism [Ramsauer et al., 2021] ] toward sparse region, both theoretically and empirically, resulting data- detendent sparsity for meaningful and robust pattern representations, and focus on the most relevant information for each specific instance.
energy- model for associative memory but also
Hopfield models are classic associative memory models for both biological and artificial neural networks [Hopfield, 1982, 1984]. These models are designed to store and retrieve memory patterns. They achieve these by embedding the memories in the energy landscape of physical system (e.g.. the Ising model [Hopfield, 1982, Peretto and Niez, 1986]; see Figure 3 for a visualization), where each memory corresponds to a local minimum. When query is presented, the model initiates energy- beergy-minimizing retrieval dynamics at the query, which then navigate the energy landscape to find the nearest local minimum, effectively retrieving the memory most similar to the query.
Code available at GitHub; future updates are on arXiv. |Version: Novermber, 28, 2023]
While this equivalence only holds when the retrieval dynamics is applied exactly once, as originally shown [Ramsauer et al., 2021] and later emphasized in Krotov and Hopfield, 2021], allows to view modern Hopfield models as generalized attentions with additional functionalitics and hence opens new avenues for Hopfield-basee architecture designs. See Appendix C for more discussions.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In the same vein, Ramsauer et al. [2021] propose the modern Hopfield model and integrate it into deep learning urchitectures via a strong connection with transformer attention, offering enhanced per- formance, theoretically guaranteed exponential memory capacity, and the ability to handle continuous patterns. addition, the modern Hopfield models have found success in various applications, such as immunology [Widrich et al., 2020] and large language model [Fürst et al., 2022]. Apart from the ele- gant connection to attention, theoretical advantages and empirically successes, the modern Hopfield models have been shown to be computationally heavy and vulnerable against noisy queries [Millidge et al., 2022]. In particular, the dense output alignments of the retrieval dynamics in modern Hopfield models [Ramsauer et al., 2021] can be computationally inefficient, making models less interpretable and seiisssen by assigning probability mass to many implausible outputs (patterns/keys).
To combat above, incorporating sparsity is an essential and common strategy. While there is a vast body of work on sparsifying attention mechanisms [Tay et al., 2022, Beltagy et al., 2020, Qiu et al., 2019, Child et al., 2019, Peters et al., 2019, Martins and Astudillo, 2016], similar developments for the Hopfield models remain less explored. To bridge this gap, we present sparse Hopfield model that corresponds to the sparsemax attention mechanism [Martins and Astudillo, 2016]. In this paper, we study the sparsification of the modern Hopfield model. The challenges are three-fold:
(CI) Non-Trivial Sparsification - Sparse Hopfield Sparse Attention: To enable the of sparse Hopfield models as computational devices (DNN learning models) akin to [Ramsauer et al., 2021], it is essential to achieve non-trivial sparsifications that exhibit equivalence to specific sparse attention models. In other words, any meaningful sparsification should extend the established equivalence [Ramsauer et al., 2021] between modern Hopfield models and attention to encompass the sparse domain. While generalizing such equivalence is potentially impactful as may lay the groundwork for future Hopfield- based methodologies, architecture designs and bio- bio-computing systems (as in [Kozachkov et al., 2023]), the heuristic design of the modern Hopfield model poses great difficulty to developing desired sparse models.
(C2) Introducing Sparsity into Hopfield Models: Unlike attention mechanisms where sparsification is typically achieved either the attention matrix (e.g., structured-sparsity [Tay al., 2020, Child et al., 2019]) or on the element- wise normalization map (e.g.. sparsity-inducing maps [Correia et al., 2019, Peters al., 2019, Martins and Astudillo, 2016)), the sparsification of Hopfield models is applied to both the energy function and the memory-retrieval dynamics, where the latter monotonically decreases the Hopfield energy over time. Since attention mechanisms (transformers) are typically not equipped with such a dynamical description, introducing sparsity into Hopfield models while retaining the connection to attention is a less straightforward process.
(C3) Properties of the Sparse Hopfield Model:
Further, it is unclear how the introduced sparsity may affect different aspects of the model, such memory capacity, fixed point convergence, retrieval accuracy, and so on. Ideally. we are looking for sparsities that offer provable computational benefits, such enhanced robustness and increased memory capacity, among others.
Challenges (C1) and (C2) are inherent in Hopfield model, and certain requirements on the design of energy function and retrieval dynamics are inevitable obtain non-trivial sparse models. Hence, we suppose the sparsified models should satisfy some conditions and verify them accordingly. Concretely, a formulation for deriving desired sparse Hopfield energy via convex conjugation of entropic regularizers is proposed. Furthermore, by applying Danskin's 's theorem and convex-concave procedure (Yuille and Rangarajan, 2003, 2001] on the sparse Hopfield energy function, we obtain sparse retrieval dynamics linked to sparse attention. For (C3), the convergence of energy stationary points and retrieval dynamics fixed points are connected via Zangwill's method [Zangwill, 1969]. The sparse retrieval error bound is derived and used to determined the well-separation condition for successful memory storage and retrieval. Lastly, the fundamental limit of memory capacity is derived using the expected separation of random points spheres [Cai and Jiang, 2012, Brauchart et al., 2018, Ramsauer et al., 2021].
In summary, this work handles sparsification of modern Hopfield models while linking them to sparse attention by addressing the following question:
Is it possible to develop theoretically grouunddd (non-trivial) sparse Hopfield model capable of storing information or learned prototypes throughout various layers of DNN models?
Contributions. We propose the Sparse Modern Hopfield Model. Our contributions follows:

---

We propose novel sparse Hopfield model whose retrieval dynamics corresponds to sparsemax attention mechanism. It leads to sparse patterns by design, inheriting both noise robustness and potential computational efficiency" from [Martins and Astudillo, 2016), compared to its dense counterparts. This work extends the theoretical understanding of the correspondence between artificial and biological neural networks to sparse region. In addition, the sparse Hopfield layer, a new deep learning component, is introduced with data-dependent sparsity.
Theoretically, we establish provably advantages from sparsity and identify the conditions under which these benefits arise. We begin by deriving the closed-form sparse Hopfield energy from the convex conjugation of sparse entropic regularizer. Next, we demonstrate the correspondence between sparse Hopfield retrieval dynamics and sparsemax attention. In addition, we prove the fast convergence of the fixed points (also known as memory patterns, attractor states in literature) for the retrieval dynamics and establish the exponential (in pattern size) memory capacity lower bound with tighter retrieval error bound, compared with modern Hopfield models.
Empirically, we conduct synthetic and realistic experiments to verify our theoretical results and proposed methodology. Specifically, the sparse Hopfield model outperforms the dense Hopfield model and machine learning baselines in sparse Multiple Instance I Learning (MIL), time series prediction and neural machine translation problems. This is observed with both sparse synthetic and real-world datasets, where the baselines tend to fall short. Moreover, even in cases without data sparsity, our proposed model delivers performance on par with its dense counterpart.
To the best of our knowledge, we are the first to propose a sparse Hopfield model whose retrieval dynamics is equivalent to sparse attention mechanism with provably computational advantages. Methodologically, the proposed model complements existing Hopfield-based DNN architectures [Hoover et al., 2023, Paischer et al., 2022, Seidl et al., 2022, Fürst et al., 2022, Ramsauer et al., 2021] by introducing a sparse Hopfield layer into deep learning models.
Organization. In Section 2, the sparse Hopfield model is introduced. In Section 3, the memory capacity is discussed. In Section 4. experimental studies are conducted. In Section 5, concluding discussions are provided. Additionally, related works and limitations are discussed in Appendix C.
Notations. We write (a. b) a the inner product for vectors a, b Rd The index set {1..... .T} is denoted by [/], where I E N4. The spectral norm is denoted by |1. which is equivalent to the 12-norm when applied to vector. Throughout this paper, we denote the memory patterns (keys) by & E Rd and the tttte/cooniguraaiinnuurrr pattern by x E IRd and E = (Li, .LM) E RdxM as shorthand for stored memory (key) patterns {Sm)ae[ar) Moreover, we set norm == ||x| be the norm of the query pattern, and [MM] ||,,.]| be the largest norm of memory patterns. We also provide a nomenclature table (Table 3) in the appendix.
2 Sparse Hopfield Model
In this section, we introduce the sparse Hopfield energy from convex conjugate of entropic regularizer, and then the sparse retrieval dynamics. In this paper we only consider the Gini entropic regularizer corresponding to the sparsemax distribution [Martins and Astudillo, 2016).
Let E E2d represent the query pattern, and let E == (E...... .E) RR denote the memory patterns. The objective of the Hopfield models is to store the memory patterns E and then retrieve a specific memory pattern ε,, based on given query x. Consequently, any Hopfield model consist of two main components: an energy function H(xx), encoding memories into its local minima, and a retrieval dynamics T(x), which retrieves a memory by iteratively minimizing H(x) when initialized with query. We provide visualization of this procedure in Figure 3. The construction of the energy function H(() is straightforward. As emphasized in [Krotov and Hopfield, 2016), the memories can be easily encoded into H(x) through the overlap-conee construction: H(x) F(=Tx), x). where F : R.M + IR is a smooth function. This ensures that the memories (Ew are located at the stationary points of H(x), since V< (TT=)))l,, = 0 for all μ [M]. Different choices of F lead to different Hopfield models, as demonstrated in [Krotov and Hopfield, 2016, Demircigil et al., 2017, Ramsauer et al., 2021, Krotov and Hopfield, 2021]. However, finding corresponding
NNote that, the proposed model's sparsity falls under the category of sparsity-idducing normalization maps. Consequently, the forward pass still requires O(n²) space complexity. Here, "potential computational efficiency" refers that the computational efficiency can be enhanced if one employs efficient implementations that leverage sparsity, such as sort operations or median finding algorithms. to circumvent unnecessary computations, see Appendix C and [Martins and Astudillo, 2016, Section 2] for more discussions.
3

---

retrieval dynamics, T, for a given energy H(x), is generally more challenging. This is because needs satisfy conditions to ensure successful memory retrieval: (i) To ensure consistent retrieval, an appropriate T should monotonically minimize H(x) when iteratively applied. (ii) To ensure accurate retrieval, an appropriate T should align fixed points (the points where iterative application terminates) with the stationary points of H(x).
To this end, we introduce the sparse Hopfield model, providing principled construction for and T. This model not only fulfills the aforementioned desirable properties, but also enables more robust and faster memory retrieval compared the modern Hopfield model [Ramsauer et al., 2021].
2.1 Sparse Hopfield Energy
Let x E gd be the query pattern, and = = (E1, EM) E Rdx. be the memory patterns. We introduce the sparse Hopfield energy as
H(x) = V (BETx x) + (x, x),
(2.1)
with 1 (z) = 2|12/1 /1[Sparsemax(() (z) z|2 2 2.2 where Sparsemax(-) is defined as follows.
Let z, P. E RAM, and A M = (p E R4 En Py = 1} be the (M 1)-dimensional unit simplex.
Definition 2.1 (Sparsemax in Variational Form [Martins and Astudillo, 2016], also see Remark F.1). Sparsemax(z) == ArgMin ||p z|| = ArgMax [p V [p)]]
(2.2)
PEA
P
where (p) - M pL (p-) is the negative Gini entropy or Gini entropic regularizer.
Remark 2.1. Recall that, the variational form (2.2) is in fact general, that applies to various entropic regularizers, as discussed in [Peters et al., 2019, Wainwright et al., 2008]. The choice of / determines the resulting sparse probability distribution. For instance, if we choose the Gibbs' entropic regularizer L Ginss = - ΣE Pv In Pv. (2.2) reduces to the standard softmax distribution.
Overview of Theoretical Results. At first glance, the energy function (2.1) may seem peculiar. However, it indeed represents a non-trivial sparse Hopfield model with appealing properties, including:
(i) In response challenge (C1) & (C2), as we shall see in Section 2.2, the energy (2.1) leads to sparse retrieval dynamics that not only retrieves memory by monotonically decreasing (Lemma 2.1) its stationary points (Lemma 2.2), but also associates with sparsemax attention through its single-step approximation (Remark 2.2);
(ii) In response to challenge (C3), we shall see in Section 3, it indulges fast convergence of retrieval (Corollary 3. 3.1.2), exponential-in-d memory capacity akin to modern Hopfield models (Lemma 3.1). Notably, it accomplishes these with tighter retrieval error bound (Theorem 1).
We reveal each of these properties in the following sections.
2.2 Sparse Retrieval Dynamics and Connection to Sparse Attention
The optimization problem ArgMaxpe [p_ (p)) does not necessarily have a closed-form solution for arbitrary V. However, a family y has been investigated in literature [Correia et al., 2019, Martins and Astudillo, 2016] with closed-form solutions derived, including the Sparsemax(-).
Sparsemax in Closed-Forme (Proposition of [Martins and Astudillo, 2016)). Let R Denote [a]+ = Max(O, a). Z(x) the 1/th element a sorted descending z-sequence Zsorted == 2(1) 2 2(2) 2
2 =(M)), and x(z) = Max {K E [M] 1 + k=(k) > Evse =cr) }. The optimization problem(s)
(2.2) has closed-form solution
Sparsemax(z) (z -(2)1 where T RRM - RR. the threshold function r(2) = [[ [(Eusnte) Fwo) - /s((z), satis-
(2.3)
fying Em 1=,, 7 (2)]
1 for all z. Notably, <(z) = [8(z) where S(z) {u
[M] Sparsemax, (z) > 0} is the support set of Sparsemax(z).
In this case, present the following theorem to derive the convex conjugate of v in closed-form:

---

Theorem 2.1 (Convex Conjugate of Negative Gini Entropy). Let F F(p) = (p. ((p)) with v
being the negative Gini entropy, V (p)
2
||||
1. The convex conjugate of (p(p is
v (z) = Max, F F(p z) 2 _ 2 Ip' =1 -
(2.4)
PEA MM
where p' Sparscmax(z) is given by (2.3).
Corollary 2.1.1. By Danskin's Theorem, V (z) ArgMaxpeaM F(p, 2) Sparsemax(z).
Proof. A detailed proof is shown in Appendix E.
Theorem 2.1 and Corollary 2.1.1 not only provide the intuition behind the sparse Hopfield energy (2.1) the memory patterns are stored in local minima aligned with the overlap- function constructions (i.e.
E |=|x|| = - 2016] but also prepare us for the following corresponding sparse retrieval dynamics.
M (E.. x) ?) in [Ramsauer al., 2021, Demircigil et al., 2017, Krotov and Hopfield,
Lemma 2.1 (Sparse Retrieval Dynamics), Let t be the iteration number. The energy (2.1) can be monotonically decreased by the following sparse retrieval dynamics over t:
T (x:)
V (3=1x)
Sparsemax (8="x,) X
(2.5)
Proof Sketch. To show monotonic decreasing property, we first derive the sparse retrieval dynamics by utilizing Theorem 2.1, Corollary 2.1.1, along with the convex-concave procedure [Yuille and Rangarajan, 2003, 2001]. Then, we show the monotonicity of H. by constructing a iterative upper bound of H which is convex x and thus, can be lowered iteratively by the convex-concave procedure. A detailed proof is shown in the Appendix E.2.
Remark 2.2. Similar to [Ramsauer et al., 2021], (2.5) is equivalent to sparsemax attention [Martins and Astudillo, 2016] when the T is applied only once, see Appendix for more details. Importantly, 3 acts as scaling factor for the energy function, often referred to as the "inverse temperature". It influences the sharpness of energy landscape Equation (2.1), thereby controlling the dynamics. High B values, corresponding to low temperatures, encourage that the basins of attraction for individual memory patterns remain distinct, leading to easier retrieval.
=== (L,,, x)² (2.5) implies that the local optimum of H. are located near the patterns ,,. Different from previous studies on binary Hopfield models [Demircigil et al., 2017, Krotov and Hopfield, 2016), for continuous patterns, we adopt the relaxed definition from [Ramsauer al., 2021] to rigorously analyze the memory retrieval, and the subsequent lemma.
Notably, since E 2 =- EM=
Definition 2.2 (Stored and Retrieved). Assuming that every pattern &, surrounded by a sphere Sp with finite radius Rt 1 Minpgireeeee ||E, Ev we say &, is stored if there exists generalized fixed point of T, x E Sp.. which all limit points E Sp converge to, and Sp n.S, = 0 for μ # We say E, is e-retrieved by T with x for an error" if [xx) E, S e.
"The retrieval error has naive bound Max {||x E, ||,,. - =1 by interpolating from x to E..-
Definition 2.2 sets the threshold for a memory pattern e,, to be considered stored at a fixed point of T, x". However, this definition does not imply that the fixed points of TT are also stationary points of the energy function H. In fact, monotonicity of (2.5) does not assure the existence of stationary points of energy H [Sriperumbudur and Lanckriet, 2009]. To establish well-defined Hopfield model, we need two types of convergence guarantees. The first is the convergence between x and E,, which ensures that the retrieved memory is close the stored memory. The second is the convergence of H to its stationary points through the dynamics of T, which ensures that the system reaches a state of minimal energy. The following lemma provides the convergence results for both.
Lemma 2.2 (Convergence of Retrieval Dynamics T). Suppose H given by (2.1) and T(x) is given by (2.5). For any sequence [x,) defined by x = (xx,), all limit points of this sequence are stationary points if they are obtained by iteratively applying 7 to H.
'Recall that a fixed point of T with respect to H. is point where x = T(x), and generalized fixed point is point where x T(x). For more details, refer to (Sriperumbudur and Lanckriet, 2009].
5

---

Proof Sketch. We verify and utilize Zangwill's global convergence theory [Zangwill. 1969] for iterative algorithms T, to first show that all the limit points of {x] are generalized fixed points and lim H (x,) = H (x*), where x* are some generalized fixed points of T. Subsequently, by [Sriperumbudur and Lanckriet, 2009, Lemma 5], we show that {x*) } are also stationary points of Minx [Ht]. and hence H. converges to local optimum. A detailed proof is shown in Appendix E.4. Li
Intuitively, Lemma 2.2 indicates that the energy function converges to local optimum, i.c. lim; H. (xx) + H (x*), where x" are stationary points of H. Consequently, it offers formal justifications for the retrieval dynamics (2.5) to retrieve stored memory patterns { je for any query (initial point) x. T monotonically and iteratively approaches stationary points of H. where the memory patterns (E [E(M) are stored. As for the retrieval error, we provide the following theorem stating that T achieves a lower retrieval error compared to its dense counterpart.
Theorem 2.2 (Retrieval Error). Let Theme be the retrieval dynamics of the dense modern Hopfield || [ (x) E/1 for all S,,. Moreover,
model [Ramsauer et al., 2021]. It holds [xT(x) E,0ll
+ 1
[x Eا m + m3
Max (Ev, - | x (r)) ME[M]
(2.6)
where E x
the kth-largest element of = RM following the sparsemax definition (2.3).
(x)
Proof. A detailed proof is shown in Appendix F.3.
Interestingly, (2.6) is sparsity dependent bound'. By denoting n == ||x]], the second term on the RHS
of (2.6) is dominated by the sparsity dimension as it can be expressed as - | [="x] ((mm)) xx with constant 0 S 2. When =
x is sparse (i.e. is small), the bound is tighter, vice versa. Remark 2.3 (Faster Convergence). Computationally, Theorem 2.2 implies that T requires fewer iterations to reach fixed points with the same amount of error tolerance compared to Töense. Namely, retrieves stored memory patterns faster and therefore more efficiently, as evidenced in Figure Moreover, in cases of contaminated patterns with noise n, i.e. X = x + 77 (noise in query) or É., = Eμ + 17 (noise in memory), the impact of noise 1 on the sparse retrieval error (2.6) linear, while its effect on the dense retrieval error (2.7) is exponential. This suggests the robustness advantage of the sparse Hopfield model, as evidenced in Figure 1.
Remark 2.4 NNose-Robusttnsst
2.3 Sparse Hopfield Layers for Deep Learning
The sparse Hopfield model can serve as versatile component for deep learning frameworks, given its continuity and differentiability with respect to parameters. Corresponding to three types of Hopfield Layers proposed in [Ramsauer et al., 2021], we introduce their sparse analogs: (1) (3) apparselopffeldLayee
Layer SparseHopffeld has memory (stored key) patterns E and query (state) pattern x in- puts, and associates these two sets patterns via the sparse retrieval dynamics (2.5). This layer regards the transformer attention layer as its one-step approximation, while utilizing the sparse- max [Martins and Astudillo, 2016] on attention matrix. Layer SparseHoppfee wowpeeooopeeeoooooeooooooooooooo ing and Layer SparseHopf f cLayer terns are memory patterns and query patterns from previous layers or external plugin, respectively. Spa roe f e dPol ing, whose query patterns are learnable parameters, can be interpreted as performing a pooling operation over input memory patterns. SparseHopf fiel dlayer, by contrast, has learnable memory patterns that maps query patterns to hidden states with sparsemax activation. Thus it can substitute a fully connected layer within deep learning architectures. See (D.12) and the implementation Algorithm in Appendix D, and [Ramsauer al., 2021, Section 3] for more details of these associations. In Section 4, we apply these layers and compare them with their dense counterparts in [Ramsauer et al., 2021] and other baseline machine learning methods.
SparseHopfield, (2) SparseHopffeeldPoll1
two variants of SparseHopffe 1d, whose input pat-
3 Fundamental Limits of Memory Capacity of Sparse Hopfield Models
How many patterns can be stored and reliably retrievable in the proposed model? We address this by decomposing into to two sub-questions and answering them separately:
(A) What is the condition for pattern E,, considered well stored in H. and correctly retrieved?
'Notably, [x] - Em|ll is also upper-bounder by a -innsity-iddeeedeentt but M, 3-depeddent bound
[x] - -l < |ieeee (x) E. s 2m(M - 1) exp -B (E...x) - Max
DE(M) (E.. (E.. } (2.7)

---

(B) What is the number, in expectation, of the the patterns satisfying such condition? For (A), we first introduce the notion of separation of patterns following [Ramsauer et al., 2021].
Definition 3.1 (Separation of Patterns). The separation of memory pattern En from all other memory patterns is defined as its minimal inner product difference to any other patterns:
Ap Min [[Ep Ey.) (E,s [.)] (E,: Em) Max [(S Ev)
(3.1)
Similarly, the separation of Eμ at a given x from all memory patterns E is given by
A
Min [(x, En) (x, E.)] 24
(3.2)
and then the well-separation condition for a pattern being well-stored and retrieved.
Theorem 3.1 (Well-Separation Condition). Given the definition of stored and retrieved memories in Definition 2.2, suppose the memory patterns { are located within the sphere Sμ = {x ||x -l S R). where the radius R is finite and defined in Definition 2.2 for all μs. Then, the retrieval dynamics T maps the sphere S₁, onto itself under the following conditions:
1. The initial query x is located within the sphere Sp, i.e., x E Sy-
2. The well-separation condition is satisfied, which is given by:
R m md
D mn + 2mR
= (N)
K
m13d/²
Corollary 3.1.1. Let 6 == Denss f-11-11T
Eu The well-separation condition can be expressed
A
1/ In
2(M-1)) 11m + 2mR, which reduces to that of the dense Hopfield model when 8 0.
11+6
Proof Sketch. The proofs proceed by connecting 4, with [[T(x) - Evll. To do so, we utilize Theorem 2.2 to incorporate the -,.dependent bound on the retrieval error of both sparse and dense Hopfield models [Ramsauer et al., 2021]. A detailed proof shown in Appendix E.5.
Together with Lemma 2.2, the well-separated condition serves as the necessary condition for pattern E, to be well-stored at the stationary points of H. and can be retrieved with at most = R by T. as per Definition 2.2. We make the following three observations about the blessings from sparsity.
1. In general, appreciate the blessings of sparsity, rearrange the well-separation condition R md
1
D, 2mR R+
mn E
(3.3)
K m/,d0/2
ommm with 05a552
and observe the two competing terms, onm and (R- (R-m-ma' tageous when the latter term surpasses the former, i.e. the sparse well-separation condition is consistently lower than its dense counterpart. The condition under which sparsity benefits are more likely to emerge (i.e., when the well-separation condition is more readily satisfied) thereby:
Sparsity proves advan-
I
Min ||E,, - E- 2 /2 [M.E
/2 (1 + axBrrmk) + m, with S a S 2.
(3.4)
2
Intuitively, the sparser ET x is, the easier is for the above condition to be fulfilled.
Large M limit: For large M, the dense well rell-separation condition (Corollary 3.1.1) explodes while the sparse one (Theorem 3.1) saturates to the first three M -iindependent terms. This suggests that the hardness of distinguishing patterns can be tamed by the sparsity, preventing an increase of A, with M as observed in the dense Hopfield model. We numerically confirm this in Figure 1.
3. + oo Limit: In the region of low temperature, where 3 + oc and hence all patterns can be error-free retrieved per (2.7), we have A, 2 2mR + anm with 0 S a S 2. Here, the second term the RHS represents the sparsity level of = x, i.e. smaller indicates higher degree of sparsity in =Tx x. Hence, the higher the sparsity, the easier is to separate patterns.
For (B), equipped with Theorem 3.1 and Corollary 3.1.1, we provide lower bound for the number of patterns being well-stored and can be at least R-retrieved in the next lemma":
FFollowing the convention in memory capacity literature [Ramsauer et al., 2021, Demircigil et al.. 2017, Krotov and Hopfield, 2016), we assume that all memory patterns {E.) } are sampled from d-sphere of radius
7

---

Lemma 3.1 (Memory Capacity Lower Bound). Let 1 p be the probability of successfully storing and retrieving a pattern. The number of patterns randomly sampled from sphere of radius that the sparse Hopfield model can store and retrieve is lower-bounder by
(3.5) where C/ is the solution to C' = W/Wo b with Wo(-) being the principal branch of Lambert W function, == (4/-1) (In [3m(yp-1)/(++)] + 1) and b == 4m 8/5(/11- For sufficiently large 3, the sparse Hopfield model exhibits a larger lower bound on the exponential memory capacity compared to its dense counterpart [Ramsauer et al., 2021]: M 2 MDeme
M 2 VDC
Proof Sketch. Our proof is built on [Ramsauer et al., 2021]. The high-level idea is to utilize the separation of random patterns sampled from spheres [Cai and Jiang, 2012, Brauchart et al., 2018] and the asymptotic expansion of the Lambert W function [Corless et al., 1996]. Firstly, we link the well-separation condition to cosine similarity distance, creating inequality for the probability of pattern being well-stored and retrieved. Next, we identify and prove conditions for the exponential memory capacity M- = VFC 11/4 to hold. Finally, we analyze the scaling behaviors of using its asymptotic expansion and show that M MDense A detailed proof is shown in Appendix E. O
Intuitively, the benefits of sparsity arises from the increased energy landscape separation provided by the sparse Hopfield energy function, which enables the separation of closely correlated patterns, resulting in a tighter well-separation condition for distinguishing such patterns and hence a larger lower bound on the memory capacity. Moreover, the sparse Hopfield model also enjoys the properties of fast convergence and exponentially suppressed retrieval error provided by the following corollary.
Corollary 3.1.2 (Fast Convergence and Exponentially Suppressed Retrieval Error). For any query x, T approximately retrieves a memory pattern E,, with retrieval error e exponentially suppressed by Ay: [IT(x) - Eull < 2m ( - 1) exp(- -3 (A,, 2m Max [[|x - Eull, | x I[))
Proof. This results from Theorem 2.2, Lemma 2.2, and [Ramsauer et al., 2021, Theorem 4].
Corollary 3.1.2 suggests that, with a sufficient A,.. T can approximately retrieve patterns after a single activation, allowing the integration of sparse Hopfield models into deep learning architectures similarly to [Hoover et al., 2023, Scidl et al., 2022, Fürst et al., 2022, Ramsauer et al., 2021].
4 Proof of Concept Experimental Studies
We demonstrate the validity of our theoretical results and method by testing them on various experi- mental settings with both synthetic and real-world datasets.
4.1
Experimental Validation of Theoretical Results
We conduct experiments to verify our thcoretical findings, and report the results in Figure 1. For the memory capacity (the top row of Figure 1), test the proposed sparse model on retrieving half-masked patterns comparing with the Dense (Softmax) and 10th order polynomial Hopfield models [Millidge et al., 2022, Krotov and Hopfield, 2016] on MNIST (high sparsity), Cifar10 (low sparsity) and ImageNet (low sparsity) datasets. For all Hopfield models, we set 3 = 1.5 A query is regarded as correctly retrieved if its cosine similarity error is below a threshold. In addition, for the robustness against noisy queries (the bottom row of Figure 1), we inject Gaussian noises with varying variances (a) into the images. Plotted are the means and standard deviations of 10 runs. The results show that the proposed sparse Hopfield model excels when memory patterns exhibit a high degree of sparsity and the signal-to-noiss ratio in patterns is low, aligning with our theoretical results.
4.2 Multiple Instance Learning Tasks
Ramsauer et al. [2021] point out that the memory-enhanced Hopfield layers present a promising approach for Multiple Instance Learning (MIL) tasks. Multiple Instance Learning (MIL)) [Ilse et al., 2018, Carbonneau et al., 2018] is variation of supervised learning where the training set consists of labeled bags, each containing multiple instances. The goal of MII. is to predict the bag labels based on the instances they contain, which makes particularly useful in scenarios where labeling individual instances is difficult impractical, but bag-level labels are available. Examples of such scenarios include medical imaging (where a bag could be an image, instances could be patches of the
Hooweerr, as pointed out in [Millidge et al., 2022], this is in fact not fair to compare modern Hopfield with 3 1 with higher order polynomial Hoptield models.
8

---

Memery Cepactt (WM4E1)
10
Memory Cupacity (CIFAR
Marrory Capacity (mageeel)
Spars Hopherd (Smenaree)) 10h Order Pay Hepfeed
Souns Hepted Spunermeo 'ce Cndy Hopled
Soens Hepted Spesereo toe Crder Paly Hepled
Momoyy Robustess (1R)51)
Memory Rabusten (CFFAR10)
Memory Rabusthez (hrageNeil
Deme leshied (Sflman
Demes Inshai doffred
Dene tofee (oftmec
Spars Huphed (Saevmmu
Souns Heghed Spanennry
Sann Highed Spesimsc)
Orts may Hophed
Crter Helhed
'ce Code iis Hiphed
C6 12 14
Varienca
Nobe vertene
Figure 1: Top: Memory Capacity measured by successful half-masked retrieval rates. Bottom: Memory Robustness measured by retrieving patterns with varying levels of Gaussian noise. For all Hopfield models, we set 3 _01 / (for
for better visualization. A query pattern is deemed correctly retrieved if its squared Euclidean distance is below set threshold. For MNIST/CIFAR 10/ImageNet datasets, we set the error thresholds to be 10/20/20 to cope with different sparse levels in data. Plotted are the means and standard deviations of 10 runs. The results suggest that the sparse Hopfield model excels when memory patterns exhibit a high degree of sparsity and the signal-to- signal-to-noise ratio in patterns is low.
AAST/CIFARRO//maaeNN
image, and the label could indicate the presence or absence of disease) and document classification (where a bag could be a document, instances could be the words or sentences in the document, and the label could indicate the topic or sentiment of the document). In this subsection, we implement our sparse Hopfield layers and applied them to MIL tasks on one synthetic and four real-world settings. 4.2.1 Synthetic Experiments
We use a synthetic MIL. dataset, the bit pattern dataset, to demonstrate the effectiveness of the sparse Hopfield model. Each bag in this synthetic dataset contains a set of binary bit strings. The positive bag includes at least one of the positive bit patterns. We compare the performance of the SparseHop e lele d and Spars Ssparseoopff f fi eeeieeolllliii lini to their dense counterparts and vanilla attention [Vaswani al., 2017]. We report the mean test accuracy of 10 runs. To demonstrate the effectiveness of sparse Hopfield model, we vary two hyperparameters of the bit pattern dataset corresponding to two perspectives: bag sparsity (sparsity in data) and bag size (number of memory patterns, M). For bag sparsity, we fix the bag size as 200, and inject from 2 to 80 positive patterns in a positive bag, results in to 40 percent of positive patterns in each positive bag. For bag size, fix the number of positive pattern in a bag to be 1, and vary bag size from 20 to 300. We report results of Spar weareeeoffii dooolioooooooooooooooooooo ing in Table and implementation details in Appendix H.I.1. A more complete version of Table 1, including the results of Hop ff fifeeeed eld and attention, is in Appendix G. The sparse Hopfield model demonstrates better performance across all sparsity and all bag sizes.
Table 1: Top (Bag Size): Accuracy comparison on bit pattern dataset for sparse and dense Hopfield model. We report the average accuracy over 10 runs. The results suggest that the sparse Hopfield model demonstrates a better performance when facing a bag size increase. Bottom (Bag Sparsity): : Performance comparison on bit pattern dataset for sparse and dense Hopfield model with varying bag sparsity. We report the average accuracy over 10 runs. The results suggest that the sparse Hopfield model demonstrates a better performance across all sparsity.
Bag Size
20
50
100
150
200
300
Dense Hopfield Pooling
100.0 + 0.00
100.0 1 0.00
100.0
0.00
76.44 0.23
49.13 : 0.01
52.88 + 0.01
Sparse Hopfield Pooling
100.0 + 0.00
100.0 + 0.00
100.0
0.00
99.76
0.00
99.76
0.00
99.76 + 0.00
Bag Sparsity
1%
5%
10%
20%
40%
Dense Hopfield Pooling
49.20 + 0.00
85.58 = 0.10
100.0 + 0.00
100.0 + 0.00
99.68 + 0.00
Sparse Hopfield Pooling
73.40 + 0.06
99.68
0.00
100.0 + 0.00
100.0 + 0.00
100.0 + 0.00
Convergence Analysis. In Figure 2, we numerically examine the convergence of the sparse and dense Hopfield models, plotting their loss and accuracy for the bag size tasks in above on the bit pattern
9

---

dataset. We include multiple bag sizes to assess the effect of increasing memory patterns (i.e. M) on the loss curve. The plotted are the loss and accuracy curves of SparsetlopiieldPollisi
We refer results of Hopf ield d and more details to Appendix G.3. The results (Figure 2) show that, sparse Hopfield model surpasses its dense counterpart all bag sizes. Moreover, for the same bag size, the sparse Hopfield model always reaches the minimum validation loss faster than dense Hopfield model, validating our Theorem 2.2.
Sparsity Generalization. We also evaluate the models' generalization performance with shifting information sparsity, by training dense and sparse Hopfield models with a specific bag sparsity and testing them on the other. We report the results in Table 5 and refer more details to Appendix G.3.
dames M 100
spame
demce 103
darsa
Sparse 120
Sporse
250
datac 200
1 200
spars: 320
dance H 700
90
spone 11-
100
120
149
100
3.0
2.6
dence
Senve
200
denne N 150
244
dence M
darse 51 220
sparos 152
sourse 250
Jens
22
sparse 202
0.8
darse 330
200
102
Epoch
Figure 2: Top: The training loss and accuracy curve of dense and sparse Hopfield models with different bag sizes. Bottom: The validation loss and accuracy curve of dense and sparse Hopfield models with different bag sizes. The plotted are the mean of 10 runs. The results indicate that the sparse Hopfield model converges faster than the dense model and also yields superior accuracy. 4.2.2 WorldWorld MIL. Tasks
Next, we demonstrate that the proposed method achieves near-optimal performance on four real- istic (non-sparse) MIL benchmark datasets: Elephant, Fox and Tiger for image annotation [[lse et al., 2018], UCSB breast cancer classification [Kandemir et al., 2014]. We use Hopfiel d and Spa oopr e eld d to construct a similar model architecture proposed in [Ramsauer et al., 2021] and a detailed description of this experiment well as its training and evaluating process can be found in Appendix 1.1. As shown in Table 2, both Sparse and Dense Hopfield achieve near- best results on Tiger, Elephant and UCSB datasets, despite the low sparsity in data. The sparse Hopfield model outperforms the dense Hopfield model by a small margin on three out of four datasets.
5 Conclusion
Table 2: Results for MII. benchmark datasets in terms of AUC score. The baselines are Path encoding [Küçükaşer and Baydogan, 2018], MInD [Cheplygina et al., 2015], MILES [Chen et al., 2006), APR [Dietterich et al., 1997], Citation- KNN [Wang and Zucker, 2000] and DD [Maron and Lozano- Pérez, 1997]. Results for baselines are taken from [Ramsauer et al., 2021]. The results suggest the proposed model achieves near-optimal performance even when the data is not sparse.
We present a sparse Hopfield model with memory-retrieval dynam- ics that corresponds to the sparse- structured attention mechanism. This model is capable of merging into deep learning architectures with data- dependent sparsity. Theoretically, we introduce a principled construction for modern Hopfield models, based on the convex conjugate of different en- tropy regularizers. It allows us to eas-
Method
Tiger
Fox
Elephane
UCSB
Dense Hopfield
0.878 i 0.028
0.600 0.011
0.907 0.022
0,880 0.013
Sparse Hopfilld
0.882 0.021
0.611 0.010
0.912
0.016
0.877
0.000
ily recover the dense modern Hopfield model [Ramsauer et al., 2021] using Gibbs entropy. Moreover, we intro- duce the sparse Hopfield model using the Gini entropic regularizer, and ex-
Pash encoding
0.910 + 0.010
0.712 + 0.014
0.944
0.007
0,880
0.022
MInD
0.704 0.016
0.936
0.027
MILES APR
0.872 4: 0.017
0.738 1: 0.016
0.927
0.007
0.833 0.026
0.778 # 0.007
0.541 4: 0.009
0.550
:: 0.010
Citation-NNN
0.856
0.635 0.015
0.896 0.009
0.706 0.032
DD
0.841
0.631
0.907
plore its theoretical advantages, delineating conditions that favor its use. Empirically, we demonstrate our theoretical results and methodology to be effective on various synthetic and realistic settings. This work extends the correspondence between artificial and biological neural networks to sparse domain, potentially paving the way for future Hopfield-barn based methodologies and bio- bio-inspired computing systems.
10

---

Post-Acceptance Note [November 28, 2023]. After the completion of this work, the authors learn of two upcoming works [Anonymous, 2023] at ICLR'24 and [Martins et al., 2023] in the Associative Memory & Hopfield Networks Workshop at NeurlPS'2. 23 both addressing similar topics. Both of these works explore theoretical generalizations of this work. addition, [Anonymous, 2023] further presents (sparse) Hopfield-based deep learning model for multivariate time series prediction. We thank the authors of [Martins et al., 2023] for enlightening discussions and for sharing their preliminary manuscript.
Acknowledgments
JH would like thank Tim Tiz-Kit Lau, Robin Luo and Andrew Chen for enlightening discussions on related topics, and Jiayi Wang for invaluable support in facilitating experimental deployments. The authors would like to thank the anonymous reviewers and program chairs for constructive comments.
JH is partially supported by the Walter P. Murphy Fellowship. HL partially supported by NIH R01LM1372201, NSF AAREERI841500 DOE DE-AC02-07CHIE 1359, DOE LAB 20-2261 and NSF TRIPODS 740735. This research was supported in part through the computational resources and staff contributions provided for the Quest high performance computing facility at Northwestern University which is jointly supported by the Office of the Provost, the Office for Research, and Northwestern University Information Technology. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.
References
Anonymous. STanhop:
Sparse tandem hopfield model for memory-enhanced time series prediction. In Submitted The Twelfth International Conference on Learning Representations, 2023. URL https: ppwpreviewwwwweee////p////ooeeem .et/ /eretfforumm forum? id- 6iwg437CZs, 37C2s. under review.
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems, 32, 2019. URL https: https:////axxiii http://awxxx.x..a///.//o/ w1tp:////./////...... 01377.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint wwXiv:2004.05/555 2020. URL https://arxxis wwepxiivvrrg/.ooo wwt//oogg////oooooo/oooeee
Ondřej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Shujian Huang, Matthias Huck, Philipp Koehn, Qun Liu, Varvara Logacheva, et al. Findings of the 2017 conference on machine translation (wmtl7). Association for Computational Linguistics, 2017.
Johannes Brandstetter. Blog post: Hopfield networks is all you need, 2021. URL https:// m1 j...kkk.tiii. 1o/ hto/hopfieldd Laaerdlayrrs... Accessed: April 2023.
Johann S Brauchart, Alexander B Reznikov, Edward B Saff, Ian H Sloan, Yu Guang Wang, and Robert Womersley. Random point sets on the sphere-hole radii, covering, and separation. Experimental Mathematies, 27(1):62-8)) 2018. URL pestps://arxxe httppp////aaxi..og/aa/////////// wwtp:/sgg//aaaeeeeoooo..ooooee 15522 07470.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33: 2020. URL https:/ //arri/a/iivv//// org/ abs///////////// 1512..1111 07470.
T Tony Cai and Tiefeng Jiang. Phase transition in limiting distributions of coherence of high- dimensional random matrices. Journal of Multivariate Analysis, 107:24-39, 2012. URL https: //a w/aaxiivoogg/ae httpg//ab////.....//// 111...922222
Marc-André Carbonneau, Veronika Cheplygina, Eric Granger, and Ghyslain Gagnon. Multiple instance learning: A survey of problem characteristies and applications. Pattern Recognition, 77: 329-353, 2018. URI. hnttps://arxtt htttpp://arxxii.orr/abbesse
03365.
Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling. Autoformer: Searching transformers for visual recognition. In Proceedings of the IEFF/CVE international conference on computer vision, pages 12270-12280 12280, 2021. URL ht https: / wwtp:/wwwwwww///////.///////
00651..
11

---

Yixin Chen, Jinbo Bi, and James Ze Wang. Miles: Multiple-insannce instance learning via embedded instance selection. IEEE transactions on pattern analysis and machine intelligence, 28(12):1931-1947 2006.
Veronika Cheplygina, David MJ Tax, and Marco Loog. Dissimilarity-bare based ensembles for multiple instance learning. IEEE transactions on neural networks and learning systems, (100:::3199999999 2015. URL https: arxiv. org/ abs / 1402. 139..
Rewon Child, Scott Gray, Alec Radford, and llya Sutskever. Generating long sequences with sparse transformers. arXiv preprint a9Xiv:1904. 1050,, 2019. URL https : http/aaxivv.oo/./ abs/
1.04.10505
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022. URL https:
laaxxiioog/ab........ /204. 02311.
Robert M Corless, Gaston H Gonnet, David EG Hare, David Jeffrey, and Donald E Kouth. On the lambert w function. Advances in Computational mathematics, 5:329-359, 1996.
Gonçalo M Correia, Vlad Niculae, and André FT Martins. Adaptively sparse transformers. arXiv preprint arXiv:I909.000
2019. URL httpss://aatte org/ /ttgabs/////eooooooee/..../..aer 1909. 00015.
Herbert A David and Haikady N Nagaraja. Order statistics. John Wiley & Sons, 2004.
Mete Demircigil, Judith Heusel, Matthias Löwe, Sven Upgang, and Franck Vermet. On model of
associative memory with huge storage capacity. Journal of Statistical Physics, 168:288-299, 2017. URL wttph:tt///// /awpavaaiiii//ia///ii//aaaaaaaaa org/ abs 7000110000000 01929.
Thomas G Dietterich, Richard H Lathrop. and Tomás Pérez. Solving the multiple instance problem with axis-parallel rectangles. Artificial intelligence, 89(1-2)331-71, 1997.
Michael Elad. Sparse and redundant representations: from theory to applications in signal and image processing, volume 2. Springer, 2010.
Peter Földiak. Forming sparse representations by local anti-hebbian learning. Biological cybernetics, 64(2):165-170, 1990.
Andreas Fürst, Elisabeth Rumetshofer, Johannes Lehner, Viet Tran, Fei Tang, Hubert Ramsauer, David Kreil, Michael Kopp, Günter Klambauer, Angela Bitto, et al. Cloob: Modern hopfield networks with infoloob outperform clip. Advances in neural information processing systems, 35: 20450-20468, 2022. URL https:://// / aaarivvv... wwxxvvoor///voooooooo abs/ 22120111... 11316.
Bolin Gao and Lacra Pavel. On the properties the softmax function with application in game theory and reinforcement learning. arXiv preprint 154:1774000800 2017. URL https:
//t.xxiv.rrg///////..//////otttt aatpr////////// 704.4 00805.
Asela Gunawardana, William Byrne, and Michael Jordan. Convergence theorems for gen- eralized alternating minimization procedures. Journal of machine learning research, 6 (12), 2005. URL https:/ jmwr..wwwr....................em pttg/papers/vo. ume gur.aaardaraOa..pdt
Benjamin Hoover, Yuchen Liang, Bao Pham, Rameswar Panda, Hendrik Strobelt, Duen Horgg Chau, Mohammed J 7aki, and Dmitry Krotov. Energy transformer. arXiv preprint arXiv:2302.07253, 2023. URL https:ttpt.........tt. www.i. abs 22322.20752522
John J Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(8):2554-25 2558, 1982.
John Hopfield. Neurons with graded response have collective computational properties like those of two-state neurons. Proceedings of the national academy of sciences, (110):3088-002) 1984.
Maximilian llse, Jakub Tomczak, and Max Welling. Attention-based deep multiple instance learning. In International conference on machine learning, pages 2127-2136. PMLR, 2018. URL https:
/ /arxiv..
04712.
12

---

Yanrong Ji, Zhihan Zhou, Han Liu, and Ramana V Davuluri. Dnabert:
pre-trained bidirectional encoder representations from transformers model for dna dna-language in genome. Bioinformatics, 37 (15):2112-2120, 2021. URL https: : //www biorxi http///ttttttnnnn/n//e/ 09. 09.17.301879v.
Melih Kandemir, Chong Zhang, and Fred A Hamprecht. Empowering multiple instance histopathol- ogy cancer diagnosis by cell graphs. In Medical Image Computing and Computer-Assisted Intervention-MICCA 20 17th International Conference, Boston, MA, USA, September 14-18, 48, 2014, Proceedings, Part 17, pages 228-235. Springer, 2014.
Leo Kozachkov, Ksenia V Kastanenka, and Dmitry Krotov. Building transformers from neurons and astrocytes. Proceedings of the National Academy of Sciences, 120G3))e2211150012) 2023. URL https:/ wwww http::www.ioor... wio.biiiiiiiii.......ii.iiiiiiii heagg//ooneet/ttte
10 12.111100v..
Dmitry Krotov and John Hopfield. Dense associative memory for pattern recognition. Advances in neural information processing systems, 29, 2016. URL 01164.
Dmitry Krotov and John J. Hopfield. Large associative memory problem in neurobiology and machine learning. In International Conference on Learning Representations, 2021. URL https: //arxiv. wwg.//////aooo. aba/ / 2008. 06996
Emel Şeyma Küçükaςeı and Mustafa Gökçe Baydogan. Bag encoding strategies in multiple instance learning problems. Information Sciences, 467:559-578, 2018.
YC Lee, Gary Doolen, HH Chen, GZ Sun, Tom Maxwell, and HY Lee. Machine learning using higher order correlation network. Technical report, Los Alamos National Lab,LLNN), Los Alamos, NM (United States); Univ. of Maryland, College Park, MD (United States), 1986.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference computer vision, pages 10012-10022, 2021. URL https:/ /ttp://///vvvv//eeeeeeeeeeeeeeea www.ooggooo.ooooooooo 2103. 14030..
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 01177111.1000
1rXiv:1711.05101, 2017, URL https::tp//ooo httttss://axivv.rrg.../
Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research, 11(1), 2010. URL
https:/ //s::///aaa /aaxxvv....///////////a/////aav/ org/ als// 00008 0908.0050.
Alireza Makhzani and Brendan J Frey. Wimner-take-all autoencoders. Advances neural information processing systems, 28, 2015. URL https: /awxiv..vvvvaa///aa http:///aiii.rr//a////00000
Oded Maron and Tomás Lozano-Pérez, framework for multiple-instance learning. Advances in neural information processing systems, 10, 1997.
Andre Martins and Ramon Astudillo. From softmax to sparsemax: sparse model of attention and multi-label classification. In International conference machine learning, pages 1614-1623. PMLR, 2016. URL https:
/ectts://arxee http://awww///////////././ootttt abs/ 602. 02068.
Andre F. T. Martins, Vlad Niculae, and Daniel McNamee. Sparse modern hopfield networks. Associative Memory & Hopfield Networks in 2023. NeurIPS 2023 workshop. 2023. URL https: / //oopnreeveew.neg net /pdfffff/ d=wwdl VooT..
Beren Millidge, Tommaso Salvatori, Yuhang Song, Thomas Lukasiewiez, and Rafal Bogacz. Uni- versal hopfield networks: A general framework for single-shot associative memory models. In International Conference on Machine Learning, pages 15561-15583. PMLR, 2022. URL
https: //arxivvvvv///////////aaa///avil owg/abs/////ooooooooooooo/sssocs 2202. 04557.
Charles Newman, Memory capacity neural network models: Rigorous lower bounds. Neural Networks, 1(3):223-238, 1988.
13

---

Bruno A Olshausen and David Field. Sparse coding with an overcomplete basis set: A strategy employed by v1? Vision research, 37(23):311-3322, 1997.
Frank WJ Olver, Daniel W Lozier, Ronald F Boisvert, and Charles W Clark. NIST handbook of mathematical functions juncttin hardback and CD-ROM. Cambridge university press, 2010.
Fabian Paischer, Thomas Adler, Vihang Patil, Angela Bitto- NettonNemling, Markus Holzleitner, Sebastian Lehner, Hamid Eghbal-Zadeh, and Sepp Hochreiter. History compression via language models in reinforcement learning. In International Conference on Machine Learning, pages 17156-17185. PMIR, 2022. URL https: : / wwx.v.orrrroooooo.. abs 2205 12258.
Günther Palm. Neural associative memories and sparse coding. Neural Networks, 37:165- 2013.
Pierre Peretto and Jean-Jacques Niez. Long term memory storage capacity of multiconnected neural networks. Biological Cybernetics, 54(1):53-55) 1986.
Ben Peters, Vlad Niculae, and André FT Martins. Sparse sequence-to--sequenee models. arXiv preprint arXiv:1905.05702, 2019. URL https: htttt://///xxii http:://axxxvvvvv... http://www.r///////....00. 09002
Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang. and Jie Tang. Blockwise self-attention for long document understanding, arXiv preprint arXiv:1911.02972 2019. URL
aattps://ariii http://wwwwviraaaaaaaa//oo org/ abaa 1911. 02972.
Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Lukas Gruber, Markus Holzleitner, Thomas Adler, David Kreil, Michael K Kopp. Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. Hopfield networks is all you need. In International Conference on Learning Representations, 2021. URL https:: /tt:://axxxiee arxiv. org/ abc///08....///////// 2008 02217.
Ron Rubinstein, Alfred M Bruckstein, and Michael Elad. Dictionaries for sparse representation modeling. Proceedings of the IEEE, 9845510555551 2010.
Philipp Seidl, Philipp Renz, Natalia Dyubankova, Paulo Neves, Jonas Verhoeven, Jorg K Wegner, Marwin Segler, Sepp Hochreiter, and Gunter Klambauer. Improving few-and zero-shot reac- tion template prediction using modern hopfield networks. Journal of chemical information and modeling, 62(9):2111-212) 2022.
Bharath K Sriperumbudur and Gert RG Lanckriet. On the convergence of the concave-convex procedure. In Advances in neural information processing systems, volume 9, pages 1759- 1767, 2009. URL https:/ htpppppppsss../ nips oc wecp/aapr_ffllee wtt.fflll/aaeee/00/////// 8b5040a8 Sba. feebbaafe06638883e (eeeeee66636222229b300 Part0--pppppppppp pdf.
Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. In International Conference on Machine Learning, pages 9438-9447. PMLR, 2020.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: survey, ACM Computing Surveys, 55(6):1-28, 2022. URL hattp:://ariiv obtp:////rr/bb////////// 06732.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. URL https: //tp/aaxvvv///////////////////aa org/ abs
Martin Wainwright, Michael I Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning. 1(1-2):1-300 2008.
Jun Wang and Jean-Daniel Zucker. Solving multiple-instance problem: A lazy learning approach. 2000.
Michael Widrich, Bernhard Schäfl, Milena Pavlović, Hubert Ramsauer, Lukas Gruber, Markus Holzleitner, Johannes Brandstetter, Geir Kjetil Sandve, Victor Greiff, Sepp Hochreiter, et al. Modern hopfield networks and attention for immune repertoire classification. Advances in Neural Information Processing Systems, 33:18832-18845 2020. URL https: // arxiv. orgo abs/ 2007. 13505.
14

---

Yongyi Yang, Zengfeng Huang, and David Wipf. Transformers from an optimization perspective. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. https: http:////pp/eviieeee ew. net/ forum?
id=vTOY4PIV2mm.
Alan L Yuille and Anand Rangarajan. The concave-convex procedure (ceep). Ad-
vances in neural information processing systems, 14, 2001.
URL https:
//ppocedings..eurippp...... cc wwtpppp.ccpppppppppppppeeppe.eep hra.eedddg...aaaoo...../paaaaaed http://eeeseeapeeeeeeeeeeaeaae/e 4022883110444550055ccoo0000001
Alan Yuille and Anand Rangarajan. The concave-convex procedure. Neural computation, 15(4):
915-936, 2003.
Willard Zangwill. Nonlinear programmigg: unified approach, volume 52. Prentice-Has Engle- wood Cliffs, NJ, 1969.
Yunhao Zhang and Junchi Yan. Crossformer: Transformer utilizing cross-dimension dependency for multivariate time series forecasting, In The Eleventh International Conference on Learning Representations, 2022. URL
net/ forum 2id=vSVLM2 9eie.
Haoyi Zhou, Shanghang Zhang. Jieqi Peng. Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 106-11115, 2021. URL https: aarxivvvvvv/../////i//aaa//vavvv org/ alss 201200122222 2. 07436.
Tian Zhou, Ziqing Ma. Qingsong Wen, Liang Sun, Tao Yao, Wotao Yin, Rong Jin, al. Film: Frequency improved legendre memory model for long-term time series forecasting, Advances in Neural Information Processing Systems, 35:12677-12690 2022. URL https: // //tpx/axvvvo//////////// abs/2203 08897.
15


Reviews:
[{"review_id": "ueijI3ISQL", "reviewer": "Reviewer_haSG", "summary": "The paper proposes a new model from the Dense Associative Memory family that uses Sparsemax function for its energy. This model is studied and compared to the model with the softmax-based energy from both theoretical and empirical perspectives. The work proposes that the sparse model outperforms the model with the softmax (dense model) in terms of the memory retrieval bound.  ", "questions": "1. Could the authors please explain the computational benefits of their model compared to previously studied dense associative memories? \n\n2. I am not too familiar with Gini entropy and its conjugate, but formulas for the relationship between $F(\\mathbf{p})$ and $\\Psi(\\mathbf{p})$ (e.g. above equation 2.4) look very similar to Legendre transformation to me. Krotov & Hopfield 2020 also use Legendge transformation to compute the energy function using Lagrangians. Is there a precise relationship between the Lagrangian language of Krotov and Hopfield and the formalism developed in this submission?\n\n3. The authors present quantitative metrics to empirically evaluate the performance of their model. This is great, but in order to get more intuition about the new model it would be helpful to show a few images for experiments presented in section 4.1 that the authors used in their experiments. For example pairs of initial states and final retrieved images. It would be interesting to see visually what kinds of mistakes the new network makes compared to previously studied models. \n", "limitations": "This is a theoretical work. The authors address societal impacts in the last section “Broader Impact” and appendix A. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work derives a novel model from the modern HN family and analyses its energy and dynamics using convex conjugate of the sparse entropic regularizer. As far as I can tell this is a sophisticated result, which meaningfully extends the family of models that has been previously studied. \n\nThe work studies theoretically several properties of the convergence dynamics in this new model. In general, results pertaining to continues models from this family are scarce, which makes this submission even more valuable. \n\nThe authors also discuss possible ways of integrating their model into existing Hopfield-like frameworks, and propose Sparse Hopfield, SparseHopfieldPooling, SparseHopfieldLayer layers based on their energy function. \n\nEmpirical results look promising. \n\nThe proofs in the appendices look convincing, although I have not checked them carefully. ", "weaknesses": "It would be nice if the authors could summarize in a concise and crisp way what is the theoretical advantage of their model with the Sparsemax compared to previously studied modern HN models. I can see that the new model uses a very different language for its formulation (which is great), but I am struggling to understand its computational benefits compared to previously studied models. The improvements in empirical performance, which the authors present are great, but they are not too significant to claim superiority just based on them. I would appreciate a clear theoretical proposition here. \n\nThe statement in lines 578-579 is somewhat confusing. The model studied in Ramsauer 2020 uses softmax activation function, the model studied in Demircigil uses exponential activation function. Several papers (incorrectly) state that these two models are identical. This is wrong, since they have mathematically distinct energy functions and update equations. \n\nSome wording in Appendix C might be somewhat confusing. The appendix makes it sound that everyone before Ramsauer 2020 studied binary Hopfield networks, but Ramsauer 2020 introduced the continuous networks. This is not quite correct. For instance https://www.pnas.org/doi/10.1073/pnas.81.10.3088 introduced continues sparse (as opposed to dense) Hopfield networks in 1984. Krotov & Hopfield 2016 introduced continuous dense Hopfield networks (see equation 10 in their paper and most of the empirical results on MNIST), etc. Ramsauer 2020 focused on studying a specific model from that family (with softmax activation) and calculated the capacity of that specific model. But the continuous networks (both sparse and dense) were introduced in prior work. \n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### The revised draft is in the same Dropbox folder (in Supplementary Material PDF).\n---\n> Q1 & It would be nice if the authors could summarize in a concise and crisp way...\n\n**Response**: Thank you for your comment. Please see below summary of the advantages of our sparse model over its dense counterpart.\n\n1. **Principled Derivation of Energy Function and Retrieval Dynamics (Sec. 2.1 & 2.2)**: Unlike the heuristic design of the energy function in the dense modern Hopfield model, we provide a principled derivation for the energy function and the corresponding retrieval dynamics. This is based on the insight that the convex conjugate of various entropic regularizers can result in distributions exhibiting different levels of sparsity.\n\n2. **Faster Convergence of Memory Retrieval (Remark 2.3 in the latest version)**: Our model demonstrates faster convergence of memory retrieval from the tighter retrieval error bound. The sparser the pattern is, the faster the convergence.\n>**Remark 2.3 (Faster Convergence)**: Computationally, Theorem 2.2 implies that $\\mathcal{T}$ requires fewer updates to reach fixed points with the same amount of error tolerance compared to $\\mathcal{T}_{\\text{dense}}$. In other words, $\\mathcal{T}$ retrieves stored memory patterns faster and therefore more efficiently, as evidenced in Figure 2.\n\n\n3. **Noise-Robustness (Remark 2.4 in the latest version)**: Our model exhibits significant advantages in scenarios with higher noise levels, as shown in Fig. 1 of the experimental section.\n>**Remark 2.4 (Noise-Robustness)**: Moreover, in cases of contaminated patterns with noise $\\boldsymbol{\\eta}$, i.e., $\\tilde{\\mathbf{x}}=\\mathbf{x}+\\boldsymbol{\\eta}$ (noise in query) or $\\tilde{\\boldsymbol{\\xi}}_\\mu=\\boldsymbol{\\xi}_\\mu+\\boldsymbol{\\eta}$ (noise in memory), the impact of noise $\\boldsymbol{\\eta}$ on the sparse retrieval error (equation 2.6) is linear, while its effect on the dense retrieval error (equation 2,6) is exponential. This suggests the robustness advantage of the sparse Hopfield model, as evidenced in Figure 1.\n\n\n4. **Tighter, Sparsity-Dependent Well-Separation Condition (Thm. 3.1)**: Intuitively, the sparser the pattern is, the easier it is for the well-separation condition to be fulfilled. This means it is easier to separate and retrieve stored memories. The hardness of distinguishing patterns can be tamed by the sparsity, preventing an increase of separation $\\Delta_\\mu$ with $M$ as observed in the dense Hopfield model.\n\nThe benefits of sparsity arise from the increased energy landscape separation provided by the sparse Hopfield energy function. This enables the separation of closely correlated patterns, resulting in a tighter well-separation condition for distinguishing such patterns.\n\nWe hope these points clarify the theoretical advantages of our model. \n\n\n>**Reviewer's Comment:** The improvements in empirical performance, which the authors present are great, but they are not too significant to claim superiority just based on them\n\n**Response:** In response to this, we have added two additional real-world experiments showing that our proposed Sparse Hopfield model not only enhances the performance of transformer-based deep learning models consistently, but also achieves STOA results.\n\n\n>**Reviewer's Comment:**\nThe statement in lines 578-579 is somewhat confusing....\n\n**Response:**\nWe appreciate your attention to this detail, and we fully agree with your observation. The models referenced are indeed distinct, and  many existing works state their resemblance incorrectly.\n\nYet, our statement that “[Ramsauer 2020] generalizes the energy function of [Demircigil 2017]” was intended to highlight the relationship between the **energy functions**, not the activation functions. We did recognize that [Demircigil 2017] does not explicitly define activation functions, and its retrieval dynamics are not related to attention at all.\n\nWe acknowledge that the wording in lines 578-579 may have led to confusion. To ensure clarity and accuracy, we have revised the paragraph in question. Thank you for bringing this to our attention.  \n\n>**Reviewer's Comment:**\nSome wording in Appendix C might be somewhat confusing...\n\n**Response:**\nWe appreciate your clarification. Our intention was not to portray the Modern Hopfield model as the first continuous Hopfield model. We understand how our wording in Appendix C could have led to confusion, and we have revised it accordingly. We have also expanded our citations to include more of the relevant prior work. Please refer to footnote 9 in the updated version of our paper for these changes. Thank you!\n\n>Q2 & I am not too familiar with Gini entropy and its conjugate...\n\n**Response:**\nYour observation is astute. Indeed, the relationship between Gini entropy and its conjugate, as well as the formulas we've presented (such as equation 2.4), do bear a resemblance to the Legendre transformation. \n\nSpecifically, if we let `h_μ = x, Ξ` as per eqn 5 of [Krotov & Hopfield 2020], and set `L_h = Ψ*` such that `∇Ψ* = sparsemax = f_μ` and `L_v = 1/2 x^2` such that `∇L_v = v_i`, we can rewrite our proposed energy function in their formulation, up to an additive constant. Furthermore, the finite difference version of their update rule aligns with our retrieval dynamics. \n\nIt's clear that `L_h` corresponds to the convex conjugate of entropic regularizers. While the formulation in Krotov & Hopfield 2020 necessitates a degree of hindsight to derive different Hopfield variants, our methodology provides a systematic and principled approach for deriving `L_h` for models exhibiting varying degrees of sparsity.\n\n>Q3: The authors present quantitative metrics to empirically evaluate the performance of their mode...\n\nPlease see the Sec. H.1 (Visualization of Experimental Validation of Theoretical Results) of revised draft.\n\nWe're open to any further questions or clarifications you might have about our work."}, {"review_id": "qtevOAmfr7", "reviewer": "Reviewer_XuPM", "summary": "This paper proposes the sparse modern Hopfield network. It studies the new proposed model from both perspectives, theoretical and empirical, validating the approach.", "questions": "Q1) Can you please add a nomenclature in the Appendix with all the mathematical notations and symbols? The paper is not an easy read, and a nomenclature would help the reader seriously.\n\nQ2) Can you please discuss and quantify (using various metrics and techniques) the sparsity patterns obtained, besides the relation with sparse attention? How the various sparsity patterns are before, during, or after training? Some (numerical, or visual) examples would help.", "limitations": "Fairly well discussed.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "* The proposed model and the introduction of sparsity in the modern Hopfield network seem novel\n* The theoretical analyse is well received\n* The empirical validation shows that the sparse model is competitive (if not better) than its dense equivalent\n* The code is provided for easy reproducibility", "weaknesses": "* The paper is very hard to read. It looks to me that it has a mathematical exposition which is much more complex than necessary, while it fails to develop for the reader basic intuitions about the proposed approach\n* The paper structure could have been improved by reserving a fair amount of space to give more details (besides math) about the proposed model and by using any other possible tools (algorithms, illustrations, etc.) to actually show/present how it actually works. Some of the current paper material can be moved into the appendix. This would really ease the reader job.\n* I mention that I didn’t follow the math completely, but even so it can be observed that some mathematical notations are not defined, e.g., what is n on line 111?\n* The literature survey on related works about sparsity in deep learning is quite weak. I believe that this is relatively important as long as the proposed model aims to be used in deep learning models. Also, the related works discussion shall be in the main paper and not in the appendix.\n* The paper needs a careful proofread as it contains typos (for instance, “memoery” on line 112) and English usage can be enhanced for clarity.\n* The paper may be potentially impactful in the research community, but given its current state it is arguable (in my opinion) if it can actually become influential", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### The revised draft is in the same Dropbox folder (in Supplementary Material PDF).\n---\n>**Reviewer's Comment:** The paper is very hard to read, with a mathematical exposition that seems more complex than necessary. It lacks basic intuitions about the proposed approach.\n\n**Response:** We acknowledge the reviewer's concern and have made revisions to enhance readability. These include:\n- Updating sections, tables, and figures for clarity.\n- Adding a high-level overview of the Hopfield model in the introduction to help readers build intuition.\n- Adding an opening paragraph in Section 2 that explains the construction of a well-defined Hopfield model in layman's terms.\n- Adding an overview of theoretical results in Section 2.1 to help readers build intuition.\n- Adding explanations and visual demonstrations to help readers understand the Sparse Hopfield Model.\n- Including a nomenclature table in the appendix.\n- Rephrasing computational benefits into multiple remarks for readability.\n- Moving broader impacts and future direction into the appendix to save space.\n\nWe hope that these modifications have enhanced the overall comprehensibility of the draft.\n\n>**Reviewer's Comment:** The paper structure could be improved by giving more details about the proposed model and using tools like algorithms and illustrations. Some material can be moved to the appendix.\n\n**Response:** We appreciate this suggestion and have made structural changes to include more details and tools to present the model. We have summarized the implementation of the Sparse Hopfield Layer into Algorithm1 (Sec.D.3) in the latest draft. We have also moved some material to the appendix to ease the reader's job.\n\n>**Reviewer's Comment:** Some mathematical notations are not defined, e.g., what is n on line 111?\n\n**Response:** Thank you for pointing this out. We have included a table of notation in the appendix and clarified the definition of n in the latest revision, $n:=||\\mathbf{x}||$ is the norm of query $\\mathbf{x}$. \n\n>**Reviewer's Comment:** The literature survey on sparsity in deep learning is weak, and the related works discussion should be in the main paper.\n\n**Response:** We appreciate the reviewer's concern. However, we believe a broader survey on \"sparsity in DL\" is beyond the scope of our work. This work is primarily related to attention and transformers. The current survey, based on the efficient transformer review [Tay 2022]  and many other efficient transformer papers published in the past three years, should suffice. Nonetheless, we are open to specific suggestions on what additional literature should be incorporated.\n\n[Tay 2022] Tay, Yi et al. “Efficient Transformers: A Survey.” ACM Computing Surveys 55 (2020): 1 - 28. (arXiv:2009.06732)\n\n>**Reviewer's Comment:** The paper contains typos and needs proofreading.\n\n**Response:** Thank you for your careful proofreading. We have fixed all identified typos and grammatical errors.\n\n>**Reviewer's Comment:** The paper's potential impact is arguable in its current state.\n\n**Response:** We appreciate the reviewer's concern on the potential impact of our paper. \n\nIn response to this, we have taken steps to demonstrate the **practical implications** of our work by implementing the proposed model in **two additional real-world experiments** in the latest revision (Sec. G.5). These experiments utilize sparse Hopfield model for transformer-based models for distinct tasks, including multivariate time series prediction and neural machine translation. The results from these experiments show that our proposed Sparse Hopfield model not only enhances the performance of transformer-based deep learning models consistently, but also achieves state-of-the-art results.\n\nOn the **theoretical front**, our work introduces a principled construction of the energy function, achieved through the convex conjugation of the entropy regularizer. This unique approach sets our work apart from the Modern Hopfield Model, marking it as a core contribution of our research. In contrast to the heuristic approach to the learning rule found in MHN, our method provides a more rigorous construction. By utilizing the Gini entropic regularizer, we have been able to analytically derive both the energy function and the retrieval dynamics.\n\nWe believe these advancements represent a significant step beyond mere incremental improvement, thereby making a fair contribution to the field.\n\n>**Reviewer's Comment:** Can you please add a nomenclature in the Appendix with all the mathematical notations and symbols?\n\n**Response:** Yes, we have added a nomenclature table in the appendix (Table 3 in the latest revision) to help readers. Thank you for this suggestion!\n\n>**Reviewer's Question:** Q2) Can you please discuss and quantify (using various metrics and techniques) the sparsity patterns obtained, besides the relation with sparse attention? How the various sparsity patterns are before, during, or after training? Some (numerical, or visual) examples would help.\n\n\n\n**Response:** Please see **Figure 2: Quantifying Sparsity in Bit Experiments** in the **attachment of the global rebuttal response** (or the last page of the latest revision). \n\nHere, we quantify and visualize the patterns' sparsity over 5 runs with sparsity metrics (Sparsity Ratio \\& Hoyer's Sparsity Measure).\n    We plot the real (target) pattern, initial pattern initialized in dense and sparse $\\mathtt{HopfieldPooling}$, and their learned patterns. \n    From above plots, it is easy to see the sparse model obtains sparser patterns than the dense one.\n\n---\nWe sincerely appreciate the time and effort that Reviewer XuPM has invested in reviewing our paper. \nWe have taken all comments into careful consideration and have made corresponding revisions to address the concerns raised. \n\nWe hope that the revisions and clarifications provided in this response address the reviewer's concerns and make the value of our work clear. We look forward to further feedback and discussion.\n"}, {"review_id": "Ye5CQbOSpW", "reviewer": "Reviewer_yZUu", "summary": "The authors introduce sparse Hopfield model, which are memory-associative models used to store and retrieve patterns. Theoretically, the authors connect sparse Hopfield with sparse attention mechanism and empiricially the authors show how their method can outperform the state-of-the art.", "questions": "Please see the weakness section.", "limitations": "Yes, limitations are discussed.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors present the key research questions, limitations of the current state of the art and their contribution in well-organized sections, detailed theoretic analysis is provided. The figure captions are detailed, and the contributions are clearly stated.", "weaknesses": "The paper in terms of language is very hard to follow for layman readers. As Hopfield network may not be familiar to all interested readers, perhaps the authors can give a very basic understanding of what Hopfield network is, why it is interesting and important. \nThe authors talk about computational efficiency and noise-robustness in the introduction, however experiments comparing efficiency of their method with baseline is missing in current manuscript. How and why sparsity increase noise-robustness is not clearly explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### The revised draft is in the same Dropbox folder (in Supplementary Material PDF).\n---\n>**Reviewer's Comment:** The paper in terms of language is very hard to follow for layman readers\n\n**Response:** Thank you for your feedback. We understand the need for making the paper more accessible to readers who may not be familiar with Hopfield networks. To address this, we have included a brief introduction to Hopfield networks in the introductory section of the paper:\n\n>>\"Hopfield models are classical associative memory models based on the Ising model, used in both biological and artificial neural networks (Hopfield, 1982; Hopfield, 1984). These models utilize statistical-mechanical retrieval dynamics to store a collection of memory patterns and retrieve the one that is most similar to a given query. For example, if the stored memories are images of all the dogs you've seen in the past, and the query is the image of a dog you see today, the Hopfield model retrieves the memory of the dog that most closely resembles the one you saw today. This is achieved by embedding the memories in the energy landscape of a physical system, where each memory corresponds to a local minimum. When a query is presented, the model initiates energy-minimizing retrieval dynamics at the query, which then navigate the energy landscape to find the nearest local minimum, effectively retrieving the memory most similar to the query.\"\n\nMoreover, we have made several modifications:\n\n1. Section 2 now begins with an opening paragraph that simplifies the construction of a well-defined Hopfield model, making it more accessible to non-specialists.\n2. We have provided an overview of the theoretical results in Section 2.1 to aid readers in developing a deeper understanding of the concepts.\n3. The discussions on computational benefits have been reformatted into several remarks (Remark 2.3 and 2.4) to improve readability.\n4. We have added Remark 2.1, which succinctly summarizes the relationship between entropic regularizers and sparse probability mappings, supplemented with relevant references and examples.\n5. Additional explanations have been included for Definition 2.2 and Lemma 2.2 to enhance clarity.\n6. Section 4.2 now includes an introductory paragraph about Multiple Instance Learning (MIL).\n7. For the convenience of the readers, a nomenclature table of notations has been added to the appendix.\n\nWe believe these changes will significantly improve the general readability of the draft.\n\n>**Reviewer's Comment:** The authors talk about computational efficiency and noise-robustness in the introduction, however experiments comparing efficiency of their method with baseline are missing in the current manuscript. \n\n**Response:** Thank you for comments. We believe there might have been a slight oversight. The efficiency comparison between our sparse model and the dense baseline can be found in \"Convergence Analysis\" of Sec. 4.2.2 (summarized as Figure 2). The results indicate that the sparse Hopfield model converges faster than the dense model and also yields superior accuracy.\n\nWe acknowledge that our initial submission may not have adequately emphasized the efficiency and noise-robustness. In our revised version, we have made a concerted effort to enhance clarity by breaking down the information into more digestible remarks (remark 2.3 & 2.4).\n\nIn the original submission, we mentioned \"efficiency\" in line 83 of the introduction, referring to the \"potential computational efficiency\" that our model might inherit from [Martins and Astudillo, 2016]. We also acknowledged in footnote 2 (and Limitations Sec.), that our proposed sparse Hopfield model still faces the issue of quadratic complexity and explained that the term \"potential computational efficiency\" was meant to highlight the possible efficient implementations of sparsemax that takes advantage of sparsity, as mentioned in Sec. 2 of  [Martins and Astudillo, 2016].\n\nIn the revised version, we have clarified our meaning and provided additional context to avoid confusion. Thank you for bringing this to our attention.\n\nOn the other hand, there is indeed another kind of \"efficiency\" advantage provided by our model.\nTo clarify, by this \"efficiency,\" we are referring to the efficiency of memory retrieval compared, with dense model. Essentially, a retrieval dynamic with a smaller error converges faster to the fixed points (or stored memories), thereby enhancing efficiency. This concept is elaborated upon in Remark 2.3 of our latest revision.\n\n>>**Remark 2.3 (Faster Convergence)**: Computationally, Theorem 2.2 implies that $\\mathcal{T}$ requires fewer updates to reach fixed points with the same amount of error tolerance compared to $\\mathcal{T}_{\\text{dense}}$. In other words, $\\mathcal{T}$ retrieves stored memory patterns faster and therefore more efficiently, as evidenced in Figure 2.\nWe have conducted a empirical comparison between the sparse Hopfield model and its dense counterpart in Section 4.1, which is summarized in Figure 2. \n\n>**Reviewer's Comment:** How and why sparsity increase noise-robustness is not clearly explained.\n\nIn response to your comment on noise-robustness, Please see line 176-179 of the original submitted version or newly added remark 2.4.\n>>**Remark 2.4 (Noise-Robustness)**: Moreover, in cases of contaminated patterns with noise $\\boldsymbol{\\eta}$, i.e., $\\tilde{\\mathbf{x}}=\\mathbf{x}+\\boldsymbol{\\eta}$ (noise in query) or $\\tilde{\\boldsymbol{\\xi}}_\\mu=\\boldsymbol{\\xi}_\\mu+\\boldsymbol{\\eta}$ (noise in memory), the impact of noise $\\boldsymbol{\\eta}$ on the sparse retrieval error (equation 2.6) is linear, while its effect on the dense retrieval error (equation 2,6) is exponential. This suggests the robustness advantage of the sparse Hopfield model, as evidenced in Figure 1.\n\nThank you for your time and valuable feedback. Please do not hesitate to let us know if there are any other aspects of our work that you would like us to clarify.\n\n\n\n\n"}, {"review_id": "CfCwiEN9a3", "reviewer": "Reviewer_usKi", "summary": "The authors introduce sparse Hopfield networks that feature sparse retrieval dynamics corresponding to sparsemax attention mechanisms and resulting in sparse patterns that are more robust to noise. They prove fast convergence analogous to modern Hopfield networks and show how the sparse Hopfield model has a tighter lower bound for memory capacity compared to the dense version. Altered sparse variations of Hopfield layers to be used in Deep Learning models are introduced and their viability is shown on established Image Classification and one synthetic and four real-world Multiple Instance Learning tasks. The novel approach shows increased memory robustness in relation to Gaussian noise applied to the input images.", "questions": "- What is the goal for the MIL tasks?\n- Line 192: two-layer fully connected networks -> MLPs?\n\n# Minor mistakes\n- Figure and Table 3 are mentioned in the text but are not found in the paper nor in the appendix.\n- Line 14: \"exploit datasets\" is worded strangely\n- Same goes for Line 87 \"provably blessings\"\n- Line 112: \"memoery\"\n- Theorem 3.1: Grammatically incorrect \n- Line 229: \"to utilizes\"\n- Corollary 3.1.2: \"retrieves a memory patterns\"\n- Line 320: \"Boarder impact\"\n\nShould the authors decide to fix the given mistakes I am willing to increase my overall rating!", "limitations": "The authors do not mention any limitations of their work. However, given the theoretical nature of the work, I do not deem it necessary to discuss them at length. Societal impact of this paper does not surpass the already significant implications of research in the field as a whole.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "# Significance\nThe paper's main strength lies in the theoretical results and the Theorems and Lemmas whose proofs can be found in the vast appendix. It's not unlikely that these results will be utilized in future work on associative and biologically plausible Deep Learning. The authors shared their source code facilitating reproducibility.\n\n# Clarity and Quality\nThe goals of this line of research are presented clearly and summarized into one concise research question. The formatting of math such as definitions and theorems is clear and pleasant to read. Proof sketches are more or less easy to follow. The use of language is of high quality minus a number of typos and grammatically wrong sentences.", "weaknesses": "# Originality\nThe papers originality is fair since sparse computation is a well-known topic in Deep Learning and the presented work is merely an incremental improvement on modern Hopfield networks. The connection between Hopfield networks and attention was made in previous work making the correspondence to a form of sparse attention mechanism an obvious venue of investigation.\n\n# Clarity\nThe MIL tasks are not introduced very well: The explanation of the bit pattern experiment is insufficient for readers unfamiliar with the task and the Real-world tasks are not explained at all.\n\n# Significance\nPotential computation advantages gained from sparse patterns is shortly mentioned in the introduction but not touched upon in the remainder of the manuscript. Additionally, a footnote weakens the claim and puts it into perspective.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### The revised draft is in the same Dropbox folder (in Supplementary Material PDF).\n---\n >**Reviewer's comment:** The papers originality is fair since sparse computation is a well-known topic in Deep Learning and the presented work is merely an incremental improvement on modern Hopfield networks. The connection between Hopfield networks and attention was made in previous work making the correspondence to a form of sparse attention mechanism an obvious venue of investigation.\n\n**Response:** We acknowledge that the link between Hopfield networks and attention mechanisms has been well-established in prior work. However, In this work, we introduce a principled construction of the energy function through the convex conjugation of entropy regularizer, which sets our work apart from the Modern Hopfield Network (MHN). We consider this our core construction. \n\nUnlike the heuristic approach to the learning rule found in MHN, which is motivated by previous work from 2017, our method provides a more rigorous construction. By using the Gini entropic regularizer, we can analytically derive both the energy function and the retrieval dynamics. The connection to attention is indeed a part of our work, but it is not the main focus. Therefore, in the submitted version, we treated this connection as a remark and included detailed information in the appendix. Our primary emphasis is on the theoretical advancements in the understanding and construction of Hopfield models, which we believe represents a significant step beyond mere incremental improvement.\n\n>**Reviewer's comment:** The MIL tasks are not introduced very well: The explanation of the bit pattern experiment is insufficient for readers unfamiliar with the task and the Real-world tasks are not explained at all.\n\n**Response:**  Multiple Instance Learning (MIL) is a variation of supervised learning where the training set consists of labeled bags, each containing multiple instances.\nThe goal of MIL is to predict the bag labels based on the instances they contain, which makes it particularly useful in scenarios where labeling individual instances is difficult or impractical, but bag-level labels are available.\nExamples of such scenarios include medical imaging (where a bag could be an image, instances could be patches of the image, and the label could indicate the presence or absence of disease) and document classification (where a bag could be a document, instances could be the words or sentences in the document, and the label could indicate the topic or sentiment of the document).\n\nThus, intuitively, attention-based models are suitable for this task. In practice, MIL was widely used in anomaly detection and other tasks that require high cost for fine-level labeling. \n\n>**Reviewer's comment:**  Line 192: two-layer fully connected networks -> MLPs? \n\n**Response:**  We acknowledge that the original wording was unclear.  We have modified it in the latest revision as follows:\n>>SparseHopfieldLayer, by contrast, has learnable memory patterns that maps query patterns to hidden states with sparsemax activation. Thus it can substitute a fully connected layer within deep learning architectures. \n\nThank you for bringing this to our attention.\n\n\n>**Reviewer's comment:** Figure and Table 3 are mentioned in the text but are not found in the paper nor in the appendix. \n\n**Response:** We appreciate your attention to detail. However, it appears there may have been a slight oversight. Both Figure 3 and Table 3 can be found on page 27 of the appendix in the version of the paper that was submitted.\n\n\n>**Reviewer's comment:** Minor mistakes:  Line 14: \"exploit datasets\" is worded strangely. Same goes for Line 87 \"provably blessings\". Line 112: \"memoery\".  Theorem 3.1: Grammatically incorrect. Line 229: \"to utilizes\". Corollary 3.1.2: \"retrieves a memory patterns\" . Line 320: \"Boarder impact\" .\n\n**Response:**  Thanks for doing such careful proofreading! We have fixed all typos and grammatical errors pointed out. \n\n\nWe hope that our responses adequately address the reviewer's concerns, and we look forward to any further feedback. Thank you for your time and consideration."}]

Author rebuttal:
Dear Reviewers,

We thank the reviewers for the insightful questions and reviews. We have answered all the questions and addressed all the problems in detail in rebuttal and revision. 

The latest revision is readily available in the reproducibility code folder. Any changes or modifications made from the submitted version are highlighted in blue in this updated draft.

In response to the reviewers' suggestions, we have made revisions to improve the overall readability of the paper. 
We have conducted another round of proofreading and have fixed all typos.
Several sections, tables, and figures have been updated for clarity and completeness. These revisions include additional explanations, paragraphs and sections to help readers build intuition, and visual demonstrations of the retrieval task to highlight the advantages of the sparse model over its dense counterpart. Most importantly, a new section, Section G.2 in the appendix, has been added to present **two practical scenarios of integrating the Sparse Hopfield Model into transformer-based deep learning models**.

---
## Revision Details (The revised draft is in the same Dropbox folder in Supplementary Material PDF)

**Major revisions include:**

-  **Two Real-World Additional Experiments**: 
   - We have implemented the proposed model in two additional experiments that utilize transformer-based models for distinct tasks. 
   - These tasks include multivariate time series prediction and neural machine translation. 
   - Our results demonstrate that our proposed Sparse Hopfield model consistently enhances transformer-based deep learning models and achieves state-of-the-art performance.
    - In **60+% of 58 settings, the Sparse Hopfield model ranks first or second**, with 28 top and 7 runner-up performances in the time series prediction task.
    - [Table 1 and Table 2 of the **attachment** or Sec. G.2 of the revised draft]
- **Visual demonstration of retrieval:** We provide a visual demonstration of the advantages of the sparse Hopfield model over its dense counterpart. 
    - [Figure 1 (**Visualizing Noise-Robustness of Sparsemax and Softmax Hopfield Models**) of **attachment** or Figure 4 in  Sec.G.1 of the revised draft] 
- Additional evaluation and visualization of sparse patterns. 
    - [Figure 2 (**Quantifying Sparsity in Bit Experiments**) of **attachment**] 
- An opening paragraph in Section 2 that explains the construction of a well-defined Hopfield model in a manner that is easily understandable to non-specialists.
- An overview of theoretical results in sec2.1 to help readers build intuition.
-  A **nomenclature table** of notations in the appendix. 
    - [Table 3 in Sec.A of the revised draft]
- An algorithm summarizing the implementation of the sparse Hopfield layer with multiple updates. 
    - [Algorithm 1 in Sec.D.3 of the revised draft] 

**Minor revisions include:**

- Proofreading the manuscript and fixing all identified typos and grammatical errors by reviewers and authors.
- Moving the broader impacts and future direction paragraph into the appendix to save space.
- Rephrasing paragraphs regarding computational benefits into multiple remarks for enhanced readability. [remarks 2.3, 2.4 (line 224-231) of the revised draft] 
- Adding a remark summarizing the relationship between entropic regularizers and sparse probability mappings, with citations and examples. [remark 2.1 (line 154-157) of the revised draft] 
- Rephrasing the remark below Lemma 2.1 to include intuition about $\beta$. [Remark 2.2  (line 188-193) of the revised draft] 

We hope these revisions address the reviewers' concerns and improve the overall quality of our paper.

---
**What are included in the attachment:**
1. Figure 1: **Visualizing Noise-Robustness of Sparsemax and Softmax Hopfield Models** (Section 4.1 & Figure 4).
2. Table 1: **Additional Real-World Experiment: Multivariate Time Series Prediction** (Appendix G.5.1).
3. Figure 2: **Quantifying Sparsity in Bit Experiments** (Section 4.2.1).
4. Table 2: **Additional Real-World Experiment: Machine Translation on the WMT17 Dataset with Language Pairs of DE-EN, EN-DE, RU-EN,
EN-RU** (Appendix G.5.2)

---
**The Nomenclature Table:** [Sec. A of the revised draft]

| Symbol | Description |
|---|---|
| $\langle\mathbf{a},\mathbf{b}\rangle$ | Inner product for vectors $\mathbf{a},\mathbf{b}\in \mathbb{R}^d$ |
| $[I]$ | Index set $\{1,\cdots,I\}$, where $I\in\mathbb{N}^+$ |
| $\|\cdot\|_2$ | Spectral norm, equivalent to the $l_2$-norm when applied to a vector |
| $d$ | Dimension of patterns |
| $M$ | Number of stored memory patterns |
| $\beta$ | A scaling factor of the energy function that controls the learning dynamics |
| $\mathbf{x}$ | State/configuration/query pattern in $\mathbb{R}^d$ |
| $\mathbf{\xi}$ | Memory patterns (keys) in $\mathbb{R}^d$ |
| $\mathbf{\Xi}$ | Shorthand for $M$ stored memory (key) patterns in $\mathbb{R}^{d\times M}$ |
| $\mathbf{\Xi}^T \mathbf{x}$ | $M$-dimensional overlap vector |
| $[\mathbf{\Xi}^T \mathbf{x}]_\kappa$ | The $\kappa$-th element of  $\mathbf{\Xi}^T \mathbf{x}$ |
| $n$ | Norm of $\mathbf{x}$, denoted as $n\coloneqq\|\mathbf{x}\|$ |
| $m$ | Largest norm of memory patterns, denoted as $m\coloneqq \max_{\mu\in[M]}\|\mathbf{\xi}_\mu\|$ |
| $\kappa$ | The number of non-zero element of Sparsemax |
| $R$ | The minimal Euclidean distance across all possible pairs of memory patterns |
| $S_\mu$ | The sphere centered at the memory pattern $\mathbf{\xi}_\mu$ with finite radius $R$ |
| $\mathbf{x}^\star_\mu$ | The fixed point of $\mathcal{T}$ covered by $S_\mu$ |
| $\Delta_\mu$ | The separation of a memory pattern $\mathbf{\xi}_\mu$ from all other memory patterns $\mathbf{\Xi}$ |
| $\tilde{\Delta}_\mu$| The separation of $\mathbf{\xi}_\mu$ at a given $\mathbf{x}$ from all memory patterns $\mathbf{\Xi}$ |


Meta-review: The paper makes some very nice contributions regarding Hopfield networks, by proposing a sparse version preserving the desirable properties of its dense counterpart w.r.t. convergence and capacity, as well as connection with attention mechanisms.

The authors provided substantial feedback to the reviews, which satisfactorily addressed key concerns. 

We strongly urge the authors to incorporate their feedback materials into the manuscript. In particular the additional experiments and visualizations add greatly to the significance of the submission.
Decision: Accept (poster)