AITOP
全部 AI 动态
AI 相关资讯全量信息流
全部博客资讯推文论文
全部模型产品行业论文技巧
标签：学习理论×
6月26日
10:37
10:37arXiv cs.LG@Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer
Lee、Mehrotra和Zampetakis（FOCS'24）首次提出多项式时间算法学习高维截断高斯，但样本与时间非最优。本研究针对非平凡截断，给出高效算法，使用n = Õ(d²/ε²)个样本在总变差距离上达到ε误差。算法时间复杂度主要由计算经验协方差矩阵主导。该样本与时间复杂度在d和ε上均为最优，即使无截断时亦如此。关键创新在于用相对截断参数重新解释截断高斯低阶矩，从而直接恢复参数，避开耗时投影随机梯度下降。
论文Gaussianhalfspace truncation样本复杂度学习理论算法
推荐理由：这篇论文给出了学习半空间截断高斯分布的最优算法，样本和时间复杂度都达到理论下界，而且避开了繁琐的随机梯度下降，值得了解。
原文
6月17日
11:41
11:41arXiv cs.LG@Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
这篇论文研究了二元概念类的信号秩（sign rank）的下界方法。作者证明了Z2-索引（Z2-index）被列表可复制数（list replicability number）的线性函数所上界，从而解决了Frick、Hosseini和Vasileuski提出的信号秩与Z2-索引之间是否存在强分离的问题。论文进一步分析了列表可复制数的上界，将其关联到两个组合度量：高度（height）和最小星数（minimum star number）。最后，作者证明了两个概念类的乘积的列表可复制数不超过各自列表可复制数之和。
论文sign rankZ2-indexlist replicability number学习理论组合度量
推荐理由：这篇论文厘清了信号秩、Z2-索引和列表可复制数三个复杂概念的关系，解决了前人遗留的分离问题，还给出了组合上界，适合对学习理论下界感兴趣的人。
原文
6月16日
20:46
6月12日
12:57
6月11日
15:28
15:23
15:07
5月29日
11:06
11:06arXiv cs.AI@Jon Kleinberg, Anay Mehrotra, Amin Saberi, Grigoris Velegkas
这篇论文研究了在有限记忆条件下语言生成的理论极限。传统研究假设学习者能访问全部历史数据，但现实算法只能保留有限信息。作者首先证明了在温和的枚举限制下，即使没有记忆，任何可数无限语言集合仍可生成；否则，他们精确刻画了无记忆生成可行的条件。对于有限集合，他们利用Sperner定理和对称链分解给出了无记忆生成器能达到的最优极小极大密度。进一步发现，滑动窗口（最近W个样本）不改善最坏情况密度，而自适应存储b个历史样本则能提升密度。最后，他们重新审视了极限识别问题，证明在仅记忆上一次猜测的增量变体中，精确识别对三个语言集合即失败，但放宽到“近似”版本后，对任何有限集合都可行。
论文语言生成有界记忆学习理论极限识别Sperner定理
推荐理由：这篇论文为有界记忆下的语言生成建立了理论基础，对设计内存受限的AI生成系统（如边缘设备上的语言模型）有直接指导意义。做理论或系统优化的开发者值得关注其中的密度与识别界限。
原文
5月14日
13:26
13:26arXiv cs.LG@Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis
精选
这篇论文重新审视了 Valiant 1984 年提出的原始学习模型（不同于 PAC 学习），该模型中学习器只能接收正例、可发起成员查询、且必须输出无假正例的假设。作者对有限域（包括布尔超立方体）给出了可学习性的充要条件：每个可实现的样本必须能被一个多项式大小的自适应查询压缩方案认证。这一刻画表明，Valiant 模型的可学习类严格介于 PAC 模型和无查询的 Valiant 模型之间，是少数成员查询能改变可学习类集合而非仅复杂度的情况。对于任意域，同样的严格夹逼关系仍然成立。此外，论文首次给出了 d 维半空间在 Valiant 模型中的学习算法（多项式样本和查询），并证明了 Ω(d) 的样本或查询下界。
论文学习理论PAC学习成员查询半空间学习样本压缩
推荐理由：这篇论文澄清了机器学习理论中一个长期被误解的基础问题——Valiant 原始模型与 PAC 学习的区别，做学习理论或计算复杂度研究的学者值得一读，尤其是对成员查询能力感兴趣的人。
原文