Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codes

• URL: http://arxiv.org/abs/2410.23126v2
• Date: Thu, 31 Oct 2024 16:02:34 GMT
• Title: Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codes
• Authors: Jerry Yao-Chieh Hu, Dennis Wu, Han Liu,
• Abstract summary: We study the optimal capacity memorization of modern Hopfield models and Kernelized Hopfield Models (KHMs) We show that the optimal capacity of KHMs occurs when the feature space allows memories to form an optimal spherical code.
• Score: 6.477597248683852
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the optimal memorization capacity of modern Hopfield models and Kernelized Hopfield Models (KHMs), a transformer-compatible class of Dense Associative Memories. We present a tight analysis by establishing a connection between the memory configuration of KHMs and spherical codes from information theory. Specifically, we treat the stored memory set as a specialized spherical code. This enables us to cast the memorization problem in KHMs into a point arrangement problem on a hypersphere. We show that the optimal capacity of KHMs occurs when the feature space allows memories to form an optimal spherical code. This unique perspective leads to: (i) An analysis of how KHMs achieve optimal memory capacity, and identify corresponding necessary conditions. Importantly, we establish an upper capacity bound that matches the well-known exponential lower bound in the literature. This provides the first tight and optimal asymptotic memory capacity for modern Hopfield models. (ii) A sub-linear time algorithm $\mathtt{U}\text{-}\mathtt{Hop}$+ to reach KHMs' optimal capacity. (iii) An analysis of the scaling behavior of the required feature dimension relative to the number of stored memories. These efforts improve both the retrieval capability of KHMs and the representation learning of corresponding transformers. Experimentally, we provide thorough numerical results to back up theoretical findings.

Related papers

• Predictable Scale: Part I -- Optimal Hyperparameter Scaling Law in Large Language Model Pretraining [56.58170370127227]
  We show that optimal learning rate follows a power-law relationship with both model parameters and data sizes, while optimal batch size scales primarily with data sizes. This work is the first work that unifies different model shapes and structures, such as Mixture-of-Experts models and dense transformers.
  arXiv  Detail & Related papers  (2025-03-06T18:58:29Z)
• Tensor-GaLore: Memory-Efficient Training via Gradient Tensor Decomposition [93.98343072306619]
  We present Navier-GaLore, a novel method for efficient training of neural networks with higher-order tensor weights. Across various PDE tasks, Navier-GaLore achieves substantial memory savings, reducing memory usage by up to 75%.
  arXiv  Detail & Related papers  (2025-01-04T20:51:51Z)
• Memory-Efficient 4-bit Preconditioned Stochastic Optimization [53.422307389223626]
  We introduce 4-bit quantization for Shampoo's preconditioners. To our knowledge, this is the first quantization approach applied to Cholesky factors of preconditioners. We demonstrate that combining Cholesky quantization with error feedback enhances memory efficiency and algorithm performance.
  arXiv  Detail & Related papers  (2024-12-14T03:32:54Z)
• Memory Layers at Scale [67.00854080570979]
  This work takes memory layers beyond proof-of-concept, proving their utility at contemporary scale. On downstream tasks, language models augmented with our improved memory layer outperform dense models with more than twice the budget, as well as mixture-of-expert models when matched for both compute and parameters. We provide a fully parallelizable memory layer implementation, demonstrating scaling laws with up to 128B memory parameters, pretrained to 1 trillion tokens, comparing to base models with up to 8B parameters.
  arXiv  Detail & Related papers  (2024-12-12T23:56:57Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Beyond Scaling Laws: Understanding Transformer Performance with Associative Memory [11.3128832831327]
  Increasing the size of a Transformer does not always lead to enhanced performance. We present a theoretical framework that sheds light on the memorization during pre-training of transformer-based language models.
  arXiv  Detail & Related papers  (2024-05-14T15:48:36Z)
• Nonparametric Modern Hopfield Models [12.160725212848137]
  We present a nonparametric construction for deep learning compatible modern Hopfield models. Key contribution stems from interpreting the memory storage and retrieval processes in modern Hopfield models. We introduce textitsparse-structured modern Hopfield models with sub-quadratic complexity.
  arXiv  Detail & Related papers  (2024-04-05T05:46:20Z)
• Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models [5.929540708452128]
  We propose a two-stage memory retrieval dynamics for modern Hopfield models. Key contribution is a learnable feature map $Phi$ which transforms the Hopfield energy function into kernel space. It utilizes the stored memory patterns as learning data to enhance memory capacity across all modern Hopfield models.
  arXiv  Detail & Related papers  (2024-04-04T23:05:30Z)
• On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis [12.72277128564391]
  We investigate the computational limits of the memory retrieval dynamics of modern Hopfield models. We establish an upper bound criterion for the norm of input query patterns and memory patterns. We prove its memory retrieval error bound and exponential memory capacity.
  arXiv  Detail & Related papers  (2024-02-07T01:58:21Z)
• AdaLomo: Low-memory Optimization with Adaptive Learning Rate [59.64965955386855]
  We introduce low-memory optimization with adaptive learning rate (AdaLomo) for large language models. AdaLomo results on par with AdamW, while significantly reducing memory requirements, thereby lowering the hardware barrier to training large language models.
  arXiv  Detail & Related papers  (2023-10-16T09:04:28Z)
• On Sparse Modern Hopfield Model [12.288884253562845]
  We introduce the sparse modern Hopfield model as a sparse extension of the modern Hopfield model. We show that the sparse modern Hopfield model maintains the robust theoretical properties of its dense counterpart.
  arXiv  Detail & Related papers  (2023-09-22T07:32:45Z)
• Thermodynamics of bidirectional associative memories [0.0]
  We investigate the equilibrium properties of bidirectional associative memories (BAMs) introduced by Kosko in 1988 as a generalization of the Hopfield model to a bipartite structure. We characterize the computational capabilities of a extension of this model in the thermodynamic limit.
  arXiv  Detail & Related papers  (2022-11-17T17:35:37Z)
• Bosonic field digitization for quantum computers [62.997667081978825]
  We address the representation of lattice bosonic fields in a discretized field amplitude basis. We develop methods to predict error scaling and present efficient qubit implementation strategies.
  arXiv  Detail & Related papers  (2021-08-24T15:30:04Z)
• Physics-informed CoKriging model of a redox flow battery [68.8204255655161]
  Redox flow batteries (RFBs) offer the capability to store large amounts of energy cheaply and efficiently. There is a need for fast and accurate models of the charge-discharge curve of a RFB to potentially improve the battery capacity and performance. We develop a multifidelity model for predicting the charge-discharge curve of a RFB.
  arXiv  Detail & Related papers  (2021-06-17T00:49:55Z)
• Learning Optical Flow from a Few Matches [67.83633948984954]
  We show that the dense correlation volume representation is redundant and accurate flow estimation can be achieved with only a fraction of elements in it. Experiments show that our method can reduce computational cost and memory use significantly, while maintaining high accuracy.
  arXiv  Detail & Related papers  (2021-04-05T21:44:00Z)
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory [110.99247009159726]
  Temporal-difference and Q-learning play a key role in deep reinforcement learning, where they are empowered by expressive nonlinear function approximators such as neural networks. In particular, temporal-difference learning converges when the function approximator is linear in a feature representation, which is fixed throughout learning, and possibly diverges otherwise.
  arXiv  Detail & Related papers  (2020-06-08T17:25:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.