揭示均匀稳定性在高概率下的最优尾部行为,解决长期未解问题。
The Sharp Tail of Uniform Stability
- 构建确定性学习问题,实现对数无依赖的稳定界
- 首次证明损失差在任意置信度下达到理论最优线性依赖
- 适用于分析稳定算法的泛化性能,尤其关注高置信度场景
均匀稳定性衡量单个训练样本对任意测试点损失的影响。新提出的无对数上界表明,一个损失值在[0, L]范围内的γ-均匀稳定算法,在概率1−δ下,泛化误差不超过O(γ log(1/δ) + L√(log(1/δ)/n))。此前是否能实现对数项的线性依赖仍未知:已有构造仅适用于辅助弱相关随机变量,且其取值范围随n增长;已有下界仅在常数概率下成立。本文完全填补该空白:对任意n、γ和L,我们构造了一个确定性的γ-均匀稳定学习问题,使得对1≤p≤cn,有P(R(A_S)−R_S(A_S)≥c′min{L, γp+L√(p/n)})≥e^{-p}。该构造基于常数标签的有界绝对损失回归,核心是多尺度稀疏Rademacher特征。坐标轴上的分段线性函数在sup范数下稳定,而奇对称最大值操作将唯一极端特征转化为约γp的误差,同时不突破损失上界。几何间隔的分段函数使所有置信水平共存于同一问题中。结合无对数上界,本文确定了均匀稳定性在高概率与矩依赖下的最优行为,仅差常数因子。
原文摘要 · Abstract (English)
Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a $γ$-uniformly stable algorithm with loss in $[0,L]$ has generalization gap at most $O \left(γ\log(1/δ) +L\sqrt{\frac{\log(1/δ)}{n}}\right)$ with probability $1-δ$. Whether an actual bounded-loss learning algorithm can realize the linear dependence on $\log(1/δ)$ has remained open. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows with $n$. The known learning lower bound holds only at constant probability. We close this gap. For every $n$, stability level $γ$, and loss bound $L$, we construct one deterministic $γ$-uniformly stable learning problem whose tail satisfies, simultaneously for $1\le p\le c n$, $\mathbb P \left( R(A_S)-R_S(A_S) \ge c'\min \left\{L,γp+L\sqrt{p/n}\right\} \right)\ge e^{-p}.$ The construction is ordinary bounded absolute-loss regression with constant labels. Its key is a multiscale collection of rare Rademacher features. A coordinatewise ramp is stable in sup norm, while an odd symmetrized maximum converts a unique extreme feature into a gap of order $γp$ without violating the loss bound. Geometrically spaced ramps put all confidence levels into the same problem. Together with the logarithmic-free upper bound, this determines the optimal high-probability and moment dependence of uniform stability up to universal constants.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。