颠覆传统认知：凸学习的样本复杂度由高斯过程决定，而非鲁棒性复杂的计算。
Do we really need the Rademacher complexities?
- 提出新学习算法，结合最优均值估计与泛化链技术
- 证明所有具有相同L2结构的学习问题样本复杂度一致
- 适用于重尾分布等极端情况，适合理论学习研究者
我们研究了在凸类中基于平方损失的学习问题。当前最优的样本复杂度估计依赖于难以控制的Rademacher复杂度。本文证明，在最简假设下，样本复杂度并非由Rademacher复杂度决定，而是由极限高斯过程的行为决定。特别地，所有具有相同L2结构的学习问题——即使面对重尾分布——也具有相同的样本复杂度。这是首个关于一般凸学习问题的普适性结果。证明基于一种新颖的学习过程，其性能通过将实值随机变量的最优均值估计技术与Talagrand的泛化链方法相结合进行分析。
原文摘要 · Abstract (English)
We study the fundamental problem of learning with respect to the squared loss in a convex class. The state-of-the-art sample complexity estimates in this setting rely on Rademacher complexities, which are generally difficult to control. We prove that, contrary to prevailing belief and under minimal assumptions, the sample complexity is not governed by the Rademacher complexities but rather by the behaviour of the limiting gaussian process. In particular, all such learning problems that have the same $L_2$-structure -- even those with heavy-tailed distributions -- share the same sample complexity. This constitutes the first universality result for general convex learning problems. The proof is based on a novel learning procedure, and its performance is studied by combining optimal mean estimation techniques for real-valued random variables with Talagrand's generic chaining method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。