分析哪些算法有紧泛化界，发现稳定性是关键
Which Algorithms Have Tight Generalization Bounds?
- 不稳定的算法因归纳偏置导致无法有紧泛化界
- 足够稳定的算法能获得紧泛化界
- 用损失的条件方差统一刻画泛化界存在性
我们研究哪些机器学习算法具有紧泛化界。首先，给出预示紧泛化界不存在的条件：具有特定归纳偏置导致不稳定的算法，无法拥有紧泛化界。其次，证明充分稳定的算法确实具备紧泛化界。最后，提出一个简单判据，将紧泛化界的存在性与算法损失的条件方差相联系。
原文摘要 · Abstract (English)
We study which machine learning algorithms have tight generalization bounds. First, we present conditions that preclude the existence of tight generalization bounds. Specifically, we show that algorithms that have certain inductive biases that cause them to be unstable do not admit tight generalization bounds. Next, we show that algorithms that are sufficiently stable do have tight generalization bounds. We conclude with a simple characterization that relates the existence of tight generalization bounds to the conditional variance of the algorithm's loss.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。