論文の概要: Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness
- arxiv url: http://arxiv.org/abs/2604.12811v1
- Date: Tue, 14 Apr 2026 14:38:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-15 19:11:32.505102
- Title: Algorithmic Analysis of Dense Associative Memory: Finite-Size Guarantees and Adversarial Robustness
- Title（参考訳）: ディエンス連想記憶のアルゴリズム解析:有限サイズ保証と対向ロバスト性
- Authors: Madhava Gaikwad,
- Abstract要約: Dense Associative Memory (DAM) は高次相互作用によりホップフィールドネットワークを一般化する。
キャパシティは、最悪の場合、$(Nn-1)$からpolylogarithmic factorまでのスケールを保証します。
DAM検索のダイナミクスは、純粋なナッシュ平衡に収束することを保証する潜在的なゲーム解釈を持つことを示す。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: Dense Associative Memory (DAM) はホップフィールドネットワークを高次相互作用により一般化し、適切なパターン分離条件下では$O(N^{n-1})$のストレージ容量を実現する。
既存の力学解析は、主にランダムにサンプリングされたパターンで熱力学極限$N\to\infty$を研究するため、有限サイズ保証や明示的な収束率を提供しない。
我々は, 明示的, 検証可能なパターン条件下で有限$N$保証が得られるDAM検索力学のアルゴリズム解析を開発する。
分離仮定と高負荷時の有界干渉条件の下では、軌道がアトラクションの台に入ると、$O(\log N)$収束時間を意味するような、非同期検索力学の幾何収束を証明できる。
さらに、スイープ毎に許容できる崩壊したビットの数を定量化する明示的マージン条件で表現された対数ロバスト性境界を定め、最悪の場合において、そのスケールを$(N^{n-1})$ の多元性因子まで保証すると同時に、ランダムパターンアンサンブルに対する古典的な $(N^{n-1})$ のスケーリングを回復する。
最後に、DAM検索のダイナミクスは、非同期更新の下で純粋なNash平衡に収束することを保証する潜在的なゲーム解釈を持つことを示す。
完全な証明は、予測収束性、堅牢性、キャパシティスケーリングの振る舞いを示す予備実験とともに付属物に提供される。
関連論文リスト
- Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics [13.202844408027412]
我々は3つの一般的な離散拡散モデルに対する新しい鋭い収束保証を開発する。
各手法の計算複雑性は, 対数的因子まで, 次元で線形にスケールすることを示した。
この研究は、これらのノイズ発生過程に対する最初の非漸近収束保証を提供する。
論文 参考訳（メタデータ） (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) は機械学習の研究で広く使われている。
本稿では,より緩やかなステップサイズ条件下でのSGDの収束解析法を提案する。
論文 参考訳（メタデータ） (2025-04-17T02:56:20Z) - A Unified Analysis for Finite Weight Averaging [50.75116992029417]
Gradient Descent(SGD)の平均イテレーションは、SWA(Weight Averaging)、EMA(Exponential moving Average)、LAWA(Latest Weight Averaging)といったディープラーニングモデルのトレーニングにおいて、経験的な成功を収めている。
本稿では、LAWAを有限重み平均化(FWA)として一般化し、最適化と一般化の観点からSGDと比較して、それらの利点を説明する。
論文 参考訳（メタデータ） (2024-11-20T10:08:22Z) - Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。
分析として,勾配の非収束に関連する神話や伝説について考察した。
論文 参考訳（メタデータ） (2023-10-19T17:58:59Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
平均場ランゲヴィン力学の収束速度解析について述べる。
ダイナミックスに付随する$p_q$により、凸最適化において古典的な結果と平行な収束理論を開発できる。
論文 参考訳（メタデータ） (2022-01-25T17:13:56Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳（メタデータ） (2021-06-30T18:32:46Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳（メタデータ） (2021-02-20T13:45:11Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and
Interpolation [17.199023009789308]
予想されるSGD(SGD)の仮定は、非アーティザン関数に対して日常的に使われている。
本稿では,スムーズな非線形設定への収束のパラダイムを示す。
また,異なるステップサイズ条件の理論的保証も提供する。
論文 参考訳（メタデータ） (2020-06-18T07:05:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。