证明了经验风险最小化在高维随机凸优化中可能过拟合，即使学习可行。
All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension
- 构造反例表明：维度线性增长时，经验风险最小化仍会过拟合
- 提出新泛化下界 Ω(√(ηT/m¹·⁵))，显著缩小与上界差距
- 适用于研究优化算法泛化能力的理论工作者
我们研究了随机凸优化中最佳情况下的经验风险最小化（ERM）的样本复杂度。证明存在一个实例：样本量与维度呈线性关系，学习是可行的，但经验风险最小化器很可能唯一且发生过拟合，解决了Feldman提出的一个开放问题。我们还将结论扩展到近似ERM。基于该构造，进一步证明当迭代次数和学习率随样本量增长时，（约束）梯度下降也可能过拟合。具体地，给出了梯度下降的新泛化下界 Ω(√(ηT/m¹·⁵))，其中 η 为学习率，T 为迭代步数，m 为样本量。该结果将已有上界 O(ηT/m) 与下界之间的差距缩小了指数级。
原文摘要 · Abstract (English)
We study the sample complexity of the best-case Empirical Risk Minimizer in the setting of stochastic convex optimization. We show that there exists an instance in which the sample size is linear in the dimension, learning is possible, but the Empirical Risk Minimizer is likely to be unique and to overfit. This resolves an open question by Feldman. We also extend this to approximate ERMs. Building on our construction we also show that (constrained) Gradient Descent potentially overfits when horizon and learning rate grow w.r.t sample size. Specifically we provide a novel generalization lower bound of $Ω\left(\sqrt{ηT/m^{1.5}}\right)$ for Gradient Descent, where $η$ is the learning rate, $T$ is the horizon and $m$ is the sample size. This narrows down, exponentially, the gap between the best known upper bound of $O(ηT/m)$ and existing lower bounds from previous constructions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。