#学习理论

这篇纯理论论文把可复现性学习里的一个悬置猜想做完了：805·ln(2m)·ln(2n) 的上界配上 Hanner 矩阵的同阶下界，等于给出紧刻画。做学习理论、可复现性或组合拓扑的读者值得细读，证明工具本身（立方载体定理、熵倾斜）也可复用。

一页理论论文，把 1995 年的 hardcore lemma 推广到任意凸损失和多类分类，还和 omnipredictors 对上了，做学习理论的朋友可以看看。

一篇理论算法论文，核心是把高斯划分用作学习原语，把 k 个 halfspace 学习的维度依赖从指数降到多项式，还配上了匹配的 SQ 下界，做学习理论的可以看看。

搞 bandit 或理论机器学习的可以看看：这论文给 robust bandits 找到了第一个多项式时间算法，遗憾 Õ(√T)，还划清了 NP-hard 边界。

这篇论文把单调对抗者模型的误差速率定性了：d=1是Θ(1/n)，d≥2多一个log因子，证明很直接。

这篇论文给出了学习半空间截断高斯分布的最优算法，样本和时间复杂度都达到理论下界，而且避开了繁琐的随机梯度下降，值得了解。

这篇论文厘清了信号秩、Z2-索引和列表可复制数三个复杂概念的关系，解决了前人遗留的分离问题，还给出了组合上界，适合对学习理论下界感兴趣的人。

这篇论文为有界记忆下的语言生成建立了理论基础，对设计内存受限的AI生成系统（如边缘设备上的语言模型）有直接指导意义。做理论或系统优化的开发者值得关注其中的密度与识别界限。