AITOP

样本复杂度

共 6 条相关 AI 资讯
7月8日
10:16
10:16官方账号arXiv cs.LG@Arkaprabha Ganguli, Emil Constantinescu
论文在单位圆上分析神经网络优于神经正切核（NTK）的条件与幅度，提出傅里叶复杂度和结构复杂度两个度量。刻画深度L、宽度w、权重范数R的ReLU网络类的极小极大率，介于Ω(Lw^2R^2/n)和Õ(L^2w^2R^2/n)之间。当复杂度解耦时，NTK回归在深度-L迭代锯齿波上需要Ω(4^L)样本，而极小极大下界是L的多项式。数值实验表明，在超立方体稀疏奇偶模型上，两层网络比NTK测试误差低4到6个数量级。
论文Neural Tangent KernelReLU网络组合学习样本复杂度极小极大率
推荐理由：这篇论文数学证明了在组合结构任务上，神经正切核比真实神经网络差指数级样本数，实验显示两层网络在稀疏奇偶问题上测试误差低4-6个数量级。
原文
7月3日
12:05
12:05官方账号arXiv cs.LG@Srinivasan Arunachalam, Louis Schatzki
该论文研究在最多k量子比特相干量子记忆限制下，n量子比特稳定子状态的测试与学习。结果表明测试的样本复杂度为Θ(n−k)，而学习的样本复杂度非自适应时为Θ(n^2/k)。与无记忆限制时测试仅需6个副本不同，即使k=0.99n，测试也无法常数副本完成；当k=cn(0<c<1)时，测试与学习同样困难，均需Θ(n)个副本。此外，论文还证明纯化测试在允许连贯记忆时也有指数下界。
论文量子计算量子记忆Stabilizer states样本复杂度
推荐理由：这篇论文揭示了相干量子记忆是实现稳定子状态测试与学习分离的关键资源，给出了精确的样本复杂度上下界，对量子计算理论研究者有启发。
原文
6月26日
10:37
10:37官方账号arXiv cs.LG@Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer
Lee、Mehrotra和Zampetakis（FOCS'24）首次提出多项式时间算法学习高维截断高斯，但样本与时间非最优。本研究针对非平凡截断，给出高效算法，使用n = Õ(d²/ε²)个样本在总变差距离上达到ε误差。算法时间复杂度主要由计算经验协方差矩阵主导。该样本与时间复杂度在d和ε上均为最优，即使无截断时亦如此。关键创新在于用相对截断参数重新解释截断高斯低阶矩，从而直接恢复参数，避开耗时投影随机梯度下降。
论文Gaussianhalfspace truncation样本复杂度学习理论算法
推荐理由：这篇论文给出了学习半空间截断高斯分布的最优算法，样本和时间复杂度都达到理论下界，而且避开了繁琐的随机梯度下降，值得了解。
原文
10:23
6月19日
11:46
11:46官方账号arXiv cs.LG@Georgy Noarov, Aaron Roth
这篇论文提出了一种确定性多校准算法，达到最小最大最优的样本复杂度率 O~(ε⁻³)，解决了此前只有随机算法能达到该复杂度而确定性算法样本复杂度更差的开放问题。算法进一步推广到结果不可区分性（OI）和全预测器，给出了针对有限或有限覆盖测试集合的最优确定性预测器。这解决了CLNR26和OKK25等先前工作中明确提出的开放问题。
论文多校准确定性算法全预测结果不可区分性样本复杂度
推荐理由：这篇论文解决了机器学习里一个悬而未决的问题：确定性多校准算法终于能像随机算法一样高效了。如果你关心公平性、可信预测的样本效率，可以看看他们怎么做到的。
原文
6月9日
12:12
12:12官方账号arXiv cs.LG@Chenxiao Yang, Nathan Srebro, Zhiyuan Li
精选
该论文严格刻画了深度L、总参数W的Transformer的VC维，上界为O(L W log(T W))，下界为Ω(L W log(T W / L))，其中T为输入序列长度。进一步，论文给出了思维链学习（chain-of-thought）的样本复杂度紧界：教师强制（teacher forcing）方法需要O(L W log((T+T')W))个样本，而任何利用思维链数据的学习规则至少需要Ω(L W log((T+T')W / L))个样本，T'为自回归步数。这些结果首次为Transformer的泛化能力提供了理论保证，对理解大模型的数据效率有重要意义。
论文TransformerVC维样本复杂度思维链泛化理论
推荐理由：理论研究者终于有了Transformer样本复杂度的紧界——VC维和思维链学习的下界都算清楚了，做深度学习理论的团队值得细读。
原文