Chinese content符号矩阵列表可复现性的对数乘积界被证明
这篇纯理论论文把可复现性学习里的一个悬置猜想做完了：805·ln(2m)·ln(2n) 的上界配上 Hanner 矩阵的同阶下界，等于给出紧刻画。做学习理论、可复现性或组合拓扑的读者值得细读，证明工具本身（立方载体定理、熵倾斜）也可复用。
#learning theory
10 stories · 1 in 7 days · 3 in 30 days
Stories, products and papers tagged "learning theory", newest first.
Nov 10
Nov 4
Chinese content从掩码信道出发统一刻画学习难度的新理论框架
一页理论论文，把 1995 年的 hardcore lemma 推广到任意凸损失和多类分类，还和 omnipredictors 对上了，做学习理论的朋友可以看看。
Papers13:09
Chinese content高斯划分算法改进多指标模型可靠学习理论一篇理论算法论文，核心是把高斯划分用作学习原语，把 k 个 halfspace 学习的维度依赖从指数降到多项式，还配上了匹配的 SQ 下界，做学习理论的可以看看。
Oct 7
Papers10:24
Chinese content论文提出鲁棒老虎机首个多项式时间学习器搞 bandit 或理论机器学习的可以看看：这论文给 robust bandits 找到了第一个多项式时间算法，遗憾 Õ(√T)，还划清了 NP-hard 边界。
Sep 14
Benign Loss Landscapes in Tree Tensor Networks
This paper provides a theoretical framework for understanding why deep neural networks can learn well despite containing hard-to-learn targets, a key question in machine learning research.
Aug 7
Papers12:40
Chinese content单调对抗者学习最优速率：VC维1以上额外对数因子不可避免这篇论文把单调对抗者模型的误差速率定性了：d=1是Θ(1/n)，d≥2多一个log因子，证明很直接。
Jun 26
Papers10:37
Chinese content学习半空间截断高斯分布的最优样本复杂度快速算法这篇论文给出了学习半空间截断高斯分布的最优算法，样本和时间复杂度都达到理论下界，而且避开了繁琐的随机梯度下降，值得了解。
Jun 17
Papers11:41
Chinese content信号秩、索引与列表可复制性：关联与分离这篇论文厘清了信号秩、Z2-索引和列表可复制数三个复杂概念的关系，解决了前人遗留的分离问题，还给出了组合上界，适合对学习理论下界感兴趣的人。
May 29
Papers11:06
Chinese content有界记忆下的语言生成：理论极限与可行性这篇论文为有界记忆下的语言生成建立了理论基础，对设计内存受限的AI生成系统（如边缘设备上的语言模型）有直接指导意义。做理论或系统优化的开发者值得关注其中的密度与识别界限。
May 14
Chinese contentValiant 原始学习模型：可学习类与成员查询的严格夹逼
这篇论文澄清了机器学习理论中一个长期被误解的基础问题——Valiant 原始模型与 PAC 学习的区别，做学习理论或计算复杂度研究的学者值得一读，尤其是对成员查询能力感兴趣的人。