AITOP

样本复杂度

共 10 条相关 AI 资讯
8月4日
12:00
12:00官方账号arXiv cs.LG@Jiachen Hu, Han Zhong
精选
arXiv:2608.02538 论文研究一比特均值估计问题，其中每个样本只用一个二进制消息表示。作者构造了完全非自适应的随机协议，在分布均值位于[-λ,λ]、绝对k阶中心矩不超过σ^k的条件下，匹配了此前两阶段自适应协议的最优样本复杂度。在目标精度 ε、置信度 1-δ 下，当 k>2 时样本复杂度为 (σ/ε)^2 log(1/δ)，当 k=2 时为 (σ/ε)^2 log(σ/ε) log(1/δ)，当 1<k<2 时为 (σ/ε)^{k/(k-1)} log(1/δ)。该结果给出了 COLT 2026 开放问题“交互是否必要”的否定答案。
论文一比特均值估计非自适应协议样本复杂度
推荐理由：这篇论文说一比特均值估计不用交互也能最优，解决了COLT 2026开放问题，统计方向的可以看看。
原文
7月28日
11:58
11:58官方账号arXiv cs.LG@Jon Kleinberg, Amin Saberi, Xizhi Tan, Grigoris Velegkas
本文研究在有限域[n]上从多个数据提供者学习未知分布p的问题，每个查询返回条件分布p(·|S)的独立样本。可学习性由查询集的共现图决定：当图在目标支撑上连通时可达点态一致性，完全图时可达PAC学习。PAC学习的最优样本复杂度范围从近线性到二次：完全共现图族复杂度为Õ(n²/ε²)，紧界；当[n]本身可查询时复杂度为Θ(n/ε²)，即使所有子集可查询也无法改进。作者识别了层次可比性作为近线性复杂度（Õ(n/ε²)）的充分条件，并展示对于每个α∈(1,2)存在查询族达到最优PAC率Θ(n^α/ε²)。
论文分布学习PAC学习条件采样
推荐理由：你想知道从多个供应商凑数据学分布有多难吗？这篇论文给出了从线性到二次的完整样本复杂度图谱，还找到了层次可比性这个好用的结构条件。
原文
7月21日
09:52
09:52官方账号arXiv cs.LG@Joseph Lazzaro, Alessio Russo, Aldo Pacchiano
本文研究在线表格强化学习中的最佳策略识别问题，提出首个非渐近样本复杂度保证。算法Navigate and Stop (NaS)的样本复杂度依赖于特征时间、MDP的连通性、最优特征时间的曲率等实例相关量。研究填补了NaS算法在非渐近分析上的空白，明确了各因素对样本复杂度的贡献。
论文NaS算法BPI强化学习
推荐理由：这篇论文给NaS算法提供了非渐近保证，解释了样本复杂度受哪些因素影响，做强化学习理论的朋友可以看看。
原文
7月14日
12:00
12:00官方账号arXiv cs.LG@Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau, Michael Hahn
这篇论文聚焦Transformer的理论理解，指出已有研究大多分析其表达性，但很少涉及可学习性。受损失景观分析启发，作者初步提出了学习C-RASP构造的样本复杂度边界。该工作为理解Transformer在有限样本下的学习能力提供了理论基础。
论文TransformerC-RASP样本复杂度
推荐理由：这篇论文讲了Transformer的理论短板——表达性研究够了，但学不学得会还不知道。他们用C-RASP给出了样本复杂度的初步界限，对想深挖模型理论的人很有用。
原文
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
10:23官方账号arXiv cs.LG@Yang Pan, Helmut Bölcskei
本文引入解集上的Hausdorff距离作为比较微分方程的自然度量，该度量捕捉两个方程在所有初始条件下的最坏情况分离，从而编码了识别问题的极小极大结构。作者建立了线性和非线性（Lipschitz/Hölder连续向量场）ODE的可识别性边界，明确了何时能从解数据中区分两个不同方程。利用该度量，推导了相关ODE类的度量熵估计，并量化了可靠恢复控制方程所需解观测的样本复杂度界限。
论文ODE可识别性Hausdorff距离
推荐理由：这篇论文给了你从数据识别ODE的理论底线，告诉你最少需要多少观测才能唯一确定方程，做科学机器学习的必读。
原文
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维和思维链学习的下界都算清楚了，做深度学习理论的团队值得细读。
原文