Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness

• URL: http://arxiv.org/abs/2604.12811v1
• Date: Tue, 14 Apr 2026 14:38:46 GMT
• Title: Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness
• Abstract summary: We study Dense Associative Memory (DAM) generalizes Hopfield networks through higher-order interactions.<n>We derive capacity guarantees that scale as $(Nn-1)$ up to polylogarithmic factors in the worst case.<n>We show that DAM retrieval dynamics admit a potential-game interpretation that ensures convergence to pure Nash equilibria.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dense Associative Memory (DAM) generalizes Hopfield networks through higher-order interactions and achieves storage capacity that scales as $O(N^{n-1})$ under suitable pattern separation conditions. Existing dynamical analyses primarily study the thermodynamic limit $N\to\infty$ with randomly sampled patterns and therefore do not provide finite-size guarantees or explicit convergence rates. We develop an algorithmic analysis of DAM retrieval dynamics that yields finite-$N$ guarantees under explicit, verifiable pattern conditions. Under a separation assumption and a bounded-interference condition at high loading, we prove geometric convergence of asynchronous retrieval dynamics, which implies $O(\log N)$ convergence time once the trajectory enters the basin of attraction. We further establish adversarial robustness bounds expressed through an explicit margin condition that quantifies the number of corrupted bits tolerable per sweep, and derive capacity guarantees that scale as $Θ(N^{n-1})$ up to polylogarithmic factors in the worst case, while recovering the classical $Θ(N^{n-1})$ scaling for random pattern ensembles. Finally, we show that DAM retrieval dynamics admit a potential-game interpretation that ensures convergence to pure Nash equilibria under asynchronous updates. Complete proofs are provided in the appendices, together with preliminary experiments that illustrate the predicted convergence, robustness, and capacity scaling behavior.

Related papers

• Geometric and dynamical analysis of attractor boundaries and storage limits in kernel Hopfield networks [0.0]
  This paper investigates the global geometry of attractor basins and the mechanisms governing the storage limit in KLR-trained Hopfield networks.<n>Experiments show that the network achieves a storage capacity for random sequences up to $P/N approx 16$, while maintaining stable retrieval for structured data at effective loads near $P/N approx 20$.
  arXiv  Detail & Related papers  (2026-05-01T03:04:44Z)
• Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics [13.202844408027412]
  We develop new and sharp convergence guarantees for three popular discrete diffusion models.<n>We show that the computational complexity of each method scales linearly in the dimension, up to logarithmic factors.<n>This study provides the first non-asymptotic convergence guarantees for these noising processes.
  arXiv  Detail & Related papers  (2025-11-29T18:24:43Z)
• Stochastic Gradient Descent in Non-Convex Problems: Asymptotic Convergence with Relaxed Step-Size via Stopping Time Methods [13.677904140815386]
  Gradient Descent (SGD) is widely used in machine learning research.<n>This paper introduces a novel analytical method for convergence analysis of SGD under more relaxed step-size conditions.
  arXiv  Detail & Related papers  (2025-04-17T02:56:20Z)
• A Unified Analysis for Finite Weight Averaging [50.75116992029417]
  Averaging iterations of Gradient Descent (SGD) have achieved empirical success in training deep learning models, such as Weight Averaging (SWA), Exponential Moving Average (EMA), and LAtest Weight Averaging (LAWA) In this paper, we generalize LAWA as Finite Weight Averaging (FWA) and explain their advantages compared to SGD from the perspective of optimization and generalization.
  arXiv  Detail & Related papers  (2024-11-20T10:08:22Z)
• Non-asymptotic estimates for accelerated high order Langevin Monte Carlo algorithms [8.058385158111207]
  We propose new algorithms, namely, aHOLA aHOLLA, to sample from high-dimensional target distributions.<n>We establish non-asymotic convergence for aHOLA in Wassersteinstein.
  arXiv  Detail & Related papers  (2024-05-09T11:12:03Z)
• Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
  gradient descent (SGD) and its variants are the main workhorses for solving large-scale optimization problems. As our analyses, we addressed certain myths and legends related to the non convergence of the gradient.
  arXiv  Detail & Related papers  (2023-10-19T17:58:59Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  convergence rate analysis of the mean field Langevin dynamics is presented. $p_q$ associated with the dynamics allows us to develop a convergence theory parallel to classical results in convex optimization.
  arXiv  Detail & Related papers  (2022-01-25T17:13:56Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  Heavy tails emerge in gradient descent (SGD) in various scenarios. We provide convergence guarantees for SGD under a state-dependent and heavy-tailed noise with a potentially infinite variance. Our results indicate that even under heavy-tailed noise with infinite variance, SGD can converge to the global optimum.
  arXiv  Detail & Related papers  (2021-02-20T13:45:11Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
  arXiv  Detail & Related papers  (2020-10-19T15:23:18Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation [17.199023009789308]
  The Expected assumption of SGD (SGD) is being used routinely for non-artisan functions. In this paper, we show a paradigms for convergence to a smooth non-linear setting. We also provide theoretical guarantees for different step-size conditions.
  arXiv  Detail & Related papers  (2020-06-18T07:05:56Z)

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.