去掉学习算法泛化误差界中的对数因子，提升理论紧致性。
Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms
- 通过双副本随机化方法，将结论从坐标立方体推广到任意独立分布。
- 证明了p阶矩上界为16pnβ + M√(2pn)，消除了旧界中的log n因子。
- 适用于分析稳定学习算法的泛化性能，理论研究者必读。
均匀稳定性是控制学习算法泛化误差的经典工具。Bousquet、Klochkov 和 Zhivotovskiy（2020）表明该问题可归约为独立随机变量的弱相互作用函数之和的矩不等式。其原有界包含额外的 log n 因子，并询问该因子能否被去除。本文正面回答此问题。具体地，设随机向量 Z=(Z₁,…,Zₙ) 的各分量独立，函数 gᵢ(Z) 满足：对任意 i，有 E[gᵢ(Z)|Z₋ᵢ]=0，|E[gᵢ(Z)|Zᵢ]|≤M，且改变任意非i坐标 Zⱼ（j≠i）时，gᵢ 的变化不超过 β。我们证明：对任意 p≥2，有 ‖∑gᵢ(Z)‖_p ≤ 16pnβ + M√(2pn)。该结果去除了此前界的 log n 因子，并在覆盖范围上与 Bousquet 等人的下界相差常数因子。证明首先建立在 Rademacher 立方体上的估计，再通过双副本随机化技巧推广至一般乘积分布。
原文摘要 · Abstract (English)
Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor $\log n$, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let $Z=(Z_1,\ldots,Z_n)$ have independent coordinates and let $g_i(Z)$ satisfy $\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n, $ where $Z_{-i}$ denotes all coordinates except $Z_i$. Assume additionally that changing any coordinate $Z_j$, $j\neq i$, changes $g_i$ by at most $β$, we prove that, for every $p\ge2$, for every $p\ge2$, $$ \left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}. $$ This removes the $\log n$ factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。