#sample complexity

14 stories · 0 in 7 days · 2 in 30 days

reinforcement learning 2 bandit 1 GAIL 1 MDP 1 Thompson sampling 1 convolutional neural networks 1 multi-armed bandits 1 imitation learning 1

Stories, products and papers tagged "sample complexity", newest first.

Oct 26

Papers11:56

Chinese content强化学习理论新进展：多步转移预测的 Bellman 方程分析

理论上讲清了多步预测为啥能帮强化学习省样本，还给出 BF-BOLA 算法和匹配的复杂度界，做 RL 理论的可以看看。

#reinforcement learning #sample complexity #MDP

arXiv cs.LG@Chenbei Lu et al. (5)Source

Oct 22

Papers10:48

Chinese content局部性与权重共享如何影响卷积神经网络学习

这篇论文用理论推导拆解了卷积网络两大核心假设：c=0 时权重共享只带来 P 倍加速，c>0 时局部连接反而可能更好，结论挺反直觉。

#convolutional neural networks #theoretical analysis #sample complexity

arXiv cs.LG@Francesco Mori, Melanie WeberSource

Oct 8

Papers Builders10:20

Chinese content多臂老虎机问题中引入期望样本复杂度 ACE 新框架

一篇多臂老虎机理论论文，提出 ACE 框架把样本复杂度从高概率保证换成期望保证，还证明了 Thompson 采样在 ε 未知时的紧界。

#multi-armed bandits #Thompson sampling #sample complexity #bandit

arXiv cs.LG@Nadav Sukenik, Nadav MerlisSource

Sep 29

Papers13:24

Chinese content正则化为何有效：对抗模仿学习的快速率理论证明

GAIL 这些老方法里加正则化为什么效果好，这篇终于给出了数学证明，还配套了新算法，做强化学习理论的朋友可以看看。

#GAIL #imitation learning #reinforcement learning #sample complexity

arXiv cs.LG@Hanbin Zhou et al. (4)Source

Aug 4

PapersSelected12:00

Chinese content研究证明：一比特均值估计无需交互即可达到最优

这篇论文说一比特均值估计不用交互也能最优，解决了COLT 2026开放问题，统计方向的可以看看。

#sample complexity #COLT 2026

arXiv cs.LG@Jiachen Hu, Han ZhongSource

Jul 28

Papers11:58

Chinese content从多个数据提供者学习分布：条件采样下的PAC学习边界

你想知道从多个供应商凑数据学分布有多难吗？这篇论文给出了从线性到二次的完整样本复杂度图谱，还找到了层次可比性这个好用的结构条件。

#PAC learning #sample complexity

arXiv cs.LG@Jon Kleinberg et al. (4)Source

Jul 21

Papers09:52

Chinese content在线强化学习最佳策略识别的非渐近样本复杂度保证

这篇论文给NaS算法提供了非渐近保证，解释了样本复杂度受哪些因素影响，做强化学习理论的朋友可以看看。

#BPI #reinforcement learning #sample complexity

arXiv cs.LG@Joseph Lazzaro et al. (3)Source

Jul 14

Papers12:00

Chinese content从表达性到样本复杂度：C-RASP为Transformer设计窄教师网络

这篇论文讲了Transformer的理论短板——表达性研究够了，但学不学得会还不知道。他们用C-RASP给出了样本复杂度的初步界限，对想深挖模型理论的人很有用。

#Transformer #C-RASP #sample complexity #theoretical analysis

arXiv cs.LG@Michael Rizvi-Martel et al. (4)Source

Jul 8

Papers10:16

Chinese content组合学习的函数空间二分法：神经正切核的指数次优性

这篇论文数学证明了在组合结构任务上，神经正切核比真实神经网络差指数级样本数，实验显示两层网络在稀疏奇偶问题上测试误差低4-6个数量级。

#Neural Tangent Kernel #ReLU networks #sample complexity

arXiv cs.LG@Arkaprabha Ganguli, Emil ConstantinescuSource

Jul 3

Papers12:05

Chinese content有限量子记忆下稳定子状态测试与学习的最优复杂度

这篇论文揭示了相干量子记忆是实现稳定子状态测试与学习分离的关键资源，给出了精确的样本复杂度上下界，对量子计算理论研究者有启发。

#quantum computing #Stabilizer states #sample complexity

arXiv cs.LG@Srinivasan Arunachalam, Louis SchatzkiSource

Jun 26

Papers10:37

Chinese content学习半空间截断高斯分布的最优样本复杂度快速算法

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

#Gaussian #halfspace truncation #sample complexity #learning theory

arXiv cs.LG@Haitong Liu et al. (4)Source

Papers10:23

Chinese content从解数据恢复控制方程：线性和非线性ODE可识别性边界

这篇论文给了你从数据识别ODE的理论底线，告诉你最少需要多少观测才能唯一确定方程，做科学机器学习的必读。

#ODE #identifiability #sample complexity #scientific machine learning

arXiv cs.LG@Yang Pan, Helmut BölcskeiSource

Jun 19

Papers11:46

Chinese content确定性多校准与全预测：最优样本复杂度的新算法

这篇论文解决了机器学习里一个悬而未决的问题：确定性多校准算法终于能像随机算法一样高效了。如果你关心公平性、可信预测的样本效率，可以看看他们怎么做到的。

#sample complexity

arXiv cs.LG@Georgy Noarov, Aaron RothSource

Jun 9

PapersSelected12:12

Chinese contentTransformer样本复杂度紧界：VC维与思维链学习

理论研究者终于有了Transformer样本复杂度的紧界——VC维和思维链学习的下界都算清楚了，做深度学习理论的团队值得细读。

#Transformer #VC dimension #sample complexity #chain-of-thought

arXiv cs.LG@Chenxiao Yang et al. (3)Source