揭示线性记忆存储能力的精确阈值，区分能成功检索与不能的情况。
Sharp Capacity Thresholds in Linear Associative Memory: From Top-1 Retrieval to Tail-Average Learning
- 提出拓扑平均裕度（TAM）新标准，衡量目标在前k名中的相对位置。
- 发现当样本数与维度比值超过2时，可实现高概率精准检索；低于则不可能。
- 开发耦合留一法，适用于复杂依赖关系下的矩阵学习问题。
一个 $d imes d$ 的线性记忆最多能存储多少键值关联？答案不仅取决于 $d^2$ 个自由度，还取决于检索标准。在各向同性高斯嵌入下，我们证明了顶1检索的尖锐阈值：当 $d^2/(n"log n)$ 超过2时，存在能以高概率检索全部 $n$ 个关联的线性记忆；低于该值，则任何数据相关线性记忆都无法做到。$"log n$ 因子是赢家通吃解码的不可避免代价。若忽略对数因子（即 $n/d^2\to α \in (0,∞)$），同时顶1检索不可能实现。但目标仍可接近排名前列。为此引入尾部平均裕度（TAM），对列表大小 $k$，将信号与最强 $k$ 个竞争者平均比较；正裕度保证目标在前 $k$ 名内。当 $k/n\to r\in(0,1)$，通过平滑TAM目标进行经验风险最小化，并通过双参数标量变分问题精确刻画高维极限行为。结果给出信号、竞争者得分、裕度和百分位排名的极限规律。在高维极限后令正则化参数趋于零，得到闭式临界负载 $α_c(r)$，区分平均损失消失与非零的区域。本研究还发展了一种用于矩阵型经验风险问题的耦合留一法，其中每条样本参与多个相关比较，该工具可能适用于更广泛场景。
原文摘要 · Abstract (English)
How many key-value associations can a $d\times d$ linear memory store? The answer depends not only on the $d^2$ degrees of freedom in the memory matrix, but also on the retrieval criterion. Under isotropic Gaussian embeddings, we prove a sharp threshold for top-1 retrieval, where every signal must beat its largest distractor: the critical value of $d^2/(n\log n)$ is $2$. Above the threshold, we explicitly construct a linear memory that retrieves all $n$ associations with high probability; below it, no data-dependent linear memory can do so. The $\log n$ factor is therefore the unavoidable extreme-value cost of winner-take-all decoding. Without the logarithmic factor---that is, when $n/d^2\toα\in(0,\infty)$---simultaneous top-1 retrieval is impossible. The matched target can nevertheless remain near the top of the ranking. We capture this weaker retrieval goal with the Tail-Average Margin (TAM), which, for list size $k$, compares each signal with the average of its $k$ strongest competitors; a positive TAM margin certifies that the target belongs to the top-$k$ candidate list. When $k/n\to r\in(0,1)$, we learn the memory by empirical risk minimization with a smoothed TAM objective and derive an exact high-dimensional characterization through a two-parameter scalar variational problem. The result gives limiting laws for signal and competitor scores, margins, and percentile ranks. Sending the ridge parameter to zero after the high-dimensional limit yields a closed-form critical load $α_c(r)$ separating vanishing from positive average loss. The analysis in this work also develops a coupled leave-one-out method for matrix-valued empirical risk problems in which each sample enters many dependent comparisons, a tool that may be useful beyond associative memory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。