多分类中梯度下降的泛化能力取决于损失函数的几何形状。
Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification
- 通过分析损失模板的p-范数光滑性，揭示泛化性能的关键机制。
- 指数衰减损失下，p=∞时风险对类别数k为对数依赖，p=2时为线性依赖。
- 首次证明p=2时k的多项式依赖不可避免，适合理论研究者阅读。
我们研究无正则化梯度方法在可分线性分类中的泛化性能。与以往主要关注二分类不同，本文聚焦于具有k个类别的多分类场景，针对趋于零的损失函数建立了新的总体风险上界。结果表明，收敛速率由损失模板的几何结构（Wang和Scott, 2024定义）决定，而非损失函数本身。特别地，我们给出了适用于任意衰减速率、其模板关于p-范数光滑的损失函数的风险上界。对于指数衰减损失，结果揭示：当p=∞时，风险对类别数k呈对数依赖；而当p=2时，风险随k线性增长。为正式建立此差异，我们还证明了后一情形下的下界，表明k的多项式依赖无法避免。分析核心是首次建立关于低噪声向量值线性预测器、损失模板关于一般p-范数光滑的Rademacher复杂度新界。
原文摘要 · Abstract (English)
We study the generalization performance of unregularized gradient methods for separable linear classification. While previous work mostly deal with the binary case, we focus on the multiclass setting with $k$ classes and establish novel population risk bounds for Gradient Descent for loss functions that decay to zero. In this setting, we show risk bounds that reveal that convergence rates are crucially influenced by the geometry of the loss template, as formalized by Wang and Scott (2024), rather than of the loss function itself. Particularly, we establish risk upper bounds that holds for any decay rate of the loss whose template is smooth with respect to the $p$-norm. In the case of exponentially decaying losses, our results indicates a contrast between the $p=\infty$ case, where the risk exhibits a logarithmic dependence on $k$, and $p=2$ where the risk scales linearly with $k$. To establish this separation formally, we also prove a lower bound in the latter scenario, demonstrating that the polynomial dependence on $k$ is unavoidable. Central to our analysis is a novel bound on the Rademacher complexity of low-noise vector-valued linear predictors with a loss template smooth w.r.t.~general $p$-norms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。