1. 为什么我劝你认真学一下集中不等式做机器学习理论研究或者搞高维统计的人几乎每天都要和“误差上界”“泛化界”“置信区间”这类东西打交道。而这些结论的背后十有八九都站着一个共同的理论基石——集中不等式Concentration Inequality。如果你只是调包跑模型可能一辈子都用不到它但如果你想真正看懂一篇理论论文在证明什么或者想自己推导一个算法的泛化误差那集中不等式就是绕不过去的一关。简单说集中不等式回答了一个非常直观的问题一个随机变量或者一组随机变量的取值有多大可能性会偏离它的期望比如你扔一万次硬币期望正面朝上五千次那么实际正面次数落在四千九百到五千一百之间的概率有多大这就是典型的集中现象。集中不等式给我们提供的是概率上界的定量刻画而且这个上界往往以指数速度衰减——也就是说偏离越大概率越小而且小得飞快。这篇文章我想把我自己重新梳理过的集中不等式体系完整分享一下包括最基础的Markov、Chebyshev到指数族的Chernoff、Hoeffding、Bernstein再到处理依赖情形的Azuma、McDiarmid最后聊一聊更新版里我觉得最有价值的非渐近视角和熵方法。每个不等式我都会给出直觉解释、标准形式、证明思路、使用场景和实际踩坑提醒。适合刚接触这个领域的研究生也适合工作几年想回头把理论基础补扎实的工程师。2. 从最朴素的不等式出发建立直觉框架2.1 Markov不等式一切集中不等式的起点所有集中不等式往上追溯源头都是Markov不等式。它说的是对一个非负随机变量X任意t 0都有P(X ≥ t) ≤ E[X] / t这个式子看起来简单到有点无聊但它其实是一个“用期望控制尾部概率”的通用模板。只要变量非负只要期望存在就能给出一个虽然粗糙但永远成立的上界。我第一遍学的时候觉得这玩意儿太弱了根本没啥用。后来才慢慢意识到Markov不等式真正的价值不在它本身而在它提供了一条思想路径如果你想控制某个随机变量的尾部概率那就想办法把它和一个非负量的期望联系起来然后套这个模板。证明思路也极其简单用指示函数放缩就行E[X] ∫ X dP ≥ ∫_{X ≥ t} X dP ≥ t · P(X ≥ t)这个证明我看着想了很久其实核心就一句话期望是整个空间上的平均而尾部事件那块贡献的期望至少是t乘以那块的概率。这个“局部贡献≥概率×阈值”的思路在后面所有不等式中都会被反复用到。2.2 Chebyshev不等式用方差收紧上界Markov给出的界往往太松原因在于它只用到了期望完全忽视了随机变量的波动程度。那自然的改进方向就是把方差也加进来。做法也很有意思。对任意随机变量X和实数t 0考虑非负量(X - E[X])²对它套Markov不等式P(|X - E[X]| ≥ t) P((X - E[X])² ≥ t²) ≤ Var(X) / t²这就是Chebyshev不等式。它告诉我们偏离期望超过t个单位的概率不超过方差除以t²。如果你让t等于k倍标准差那概率就不超过1/k²。Chebyshev的好处是只要求方差存在几乎不限制分布类型适用范围极广。坏处是上界还是太松。假设X是标准正态分布P(|X| ≥ 5)的真实概率大约是5.7e-7而Chebyshev给出的上界是1/25 0.04松了将近五万倍。这就是为什么在要求高精度误差界的时候我们需要更锋利的工具。我在实际推导算法误差的时候一般把Chebyshev当作“兜底方案”——当其他不等式因为条件不满足而无法使用时Chebyshev总能顶上虽然粗糙但不会出错。2.3 为什么需要一个统一的视角把Markov和Chebyshev放在一起看你会发现它们其实是一个套路的不同变体构造某个非负单调函数φ使得事件“X偏离期望”等价于“φ(X)很大”然后对φ(X)用Markov不等式。这个统一的视角直接引出了指数界不等式。如果你选φ(x) e^{λx}λ 0那么P(X ≥ t) P(e^{λX} ≥ e^{λt}) ≤ E[e^{λX}] / e^{λt} exp(-λt log E[e^{λX}])E[e^{λX}]就是矩母函数。对这个式子关于λ求最小值就得到了Chernoff界。我个人的理解是指数函数之所以好用是因为它能把“加和”变成“乘积”这在处理独立随机变量和的时候特别方便——独立变量的和的矩母函数等于各自矩母函数的乘积。这一下就把问题从“一个复杂随机变量”拆解成了“一堆简单随机变量的乘积”然后各自处理再乘起来。这个统一的思路是我认为理解整个集中不等式体系的关键。你不能把这些不等式当作孤立的公式去背而是要看到它们之间的递进关系Markov是最底层的地基Chebyshev加上方差信息指数界则进一步利用了矩母函数提供的全部矩信息。3. 指数界不等式Chernoff、Hoeffding和Bernstein的来龙去脉3.1 Chernoff界从矩母函数出发的通用工具Chernoff界是通往Hoeffding等更精细不等式的大门。对独立随机变量X_1, ..., X_n记S_n X_1 ... X_nChernoff界说的是P(S_n - E[S_n] ≥ t) ≤ inf_{λ0} exp(-λt) · Π_{i1}^{n} E[e^{λ(X_i - E[X_i])}]实际用的时候一般会针对具体分布把矩母函数算出来再对λ求最小值。比如对独立Bernoulli(p)随机变量S_n ~ Binomial(n, p)你可以得到P(S_n ≥ (1δ)np) ≤ exp(-δ²np/(2δ))对δ 0这个界在实际中非常常用。我记得有次推导一个在线学习算法的遗憾界需要控制“好事件发生次数不达预期”的概率直接套的就是单边Chernoff界。关键是Chernoff允许不同随机变量服从不同分布只要独立这在很多实际场景里比Hoeffding要求的“有界性”更容易满足。但Chernoff也有让人头疼的地方对λ求最小值这一步有时候没有闭式解只能数值求解。所以我在实操中一般先尝试能不能找到矩母函数的简单上界如果能就绕开最优化这一步。3.2 Hoeffding不等式有界随机变量的工作马Hoeffding不等式适用于有界随机变量。假设X_i ∈ [a_i, b_i]且相互独立那么P(S_n - E[S_n] ≥ t) ≤ exp(-2t² / Σ(b_i - a_i)²)这个不等式的优美之处在于它完全不依赖具体的分布形状只要知道每个变量有界就行。证明的核心也就是Hoeffding引理对有界随机变量X ∈ [a, b]有E[e^{λ(X - E[X])}] ≤ exp(λ²(b - a)²/8)这个引理的几何直觉是指数函数是凸函数所以它在区间端点的弦上方的值必然不超过弦的值在凹函数条件下这里其实就是把指数函数用线性函数从上方夹住期望被压到了某个只依赖区间宽度的上界。我在实际使用Hoeffding时踩过最大的坑是变量有界但不一定对称直接套Hoeffding会把界变松。举个具体例子如果你的随机变量取值是[0, 100]实际分布是99%概率取0、1%概率取100那方差其实很小但Hoeffding的界还是按区间宽度100来算给出的界远非最优。这时候用Bernstein不等式会更合理。3.3 Bernstein不等式兼顾方差和范围的改进Bernstein不等式的形式是P(S_n - E[S_n] ≥ t) ≤ exp(-t² / (2ΣVar(X_i) (2/3)ct))其中c是X_i上界的某种度量。这个界最大的好处是分子同时考虑了方差项ΣVar(X_i)和“大偏差”项(2/3)ct。当t比较小的时候方差项主导界比Hoeffding好得多当t非常大的时候线性项主导退化到类似Chebyshev的行为。直观理解是这样的Hoeffding只看“范围”它对一个“99%概率取0、1%概率取100”的变量和“50%概率取0、50%概率取100”的变量给的界一样。Bernstein则能区分这两种情况因为它用到了方差信息方差小的情形给紧得多的界。我在实验里对比过对上述那个99%取0、1%取100的分布n 100t 30Hoeffding给的界大概是exp(-2×900/100²) exp(-0.18) ≈ 0.835完全没意义Bernstein给的是exp(-900/(2×99 (2/3)×1×30)) ≈ exp(-4.43) ≈ 0.012虽然说不上多紧但至少是一个有信息量的界。这个差距在实践中就意味着能不能得到非平凡的结论。3.4 三个不等式怎么选我用一个表格来总结什么时候用哪个条件推荐工具上界衰减速度备注只知道变量非负Markov1/t最粗糙兜底只知道方差有限Chebyshev1/t²大偏差失效独立且矩母函数易算Chernoff指数级需要做λ最优化独立且有界Hoeffdingexp(-t²/n)最常用但忽略方差独立有界知道方差上界Bernsteinexp(-t²/(Var ct))小偏差最优从我自己的经验来看做理论工作的时候至少要把Chernoff和Bernstein两种都算一遍取更紧的那个。因为在很多问题中小偏差区域决定主阶项大偏差区域决定对数因子两个区域的紧界来源不同只靠一个不等式很难同时拿下两个区域。4. 处理依赖情形Azuma和McDiarmid以及诸特例4.1 Azuma不等式鞅差序列的集中界前面所有不等式都要求随机变量相互独立。但现实中很多问题并不满足独立条件——比如随机梯度下降中当前步的梯度依赖于上一步的参数而上一步的参数又依赖于更早的所有样本。这就是典型的依赖情形。处理这类问题的标准工具是Azuma不等式也叫Azuma-Hoeffding不等式。它针对的是鞅差序列如果D_1, ..., D_n满足E[D_i | F_{i-1}] 0且|D_i| ≤ c_i那么P(ΣD_i ≥ t) ≤ exp(-t² / (2Σc_i²))这里F_{i-1}表示第i步之前的所有信息。核心条件有两个一是条件期望为零也就是给定历史信息当前步的期望不会系统性偏离二是有界性限制。证明思路和Hoeffding几乎一模一样区别只在于把独立情形的Hoeffding引理替换成了条件版本的Hoeffding引理再利用鞅差的性质逐项条件化。我一直觉得这个证明非常漂亮因为每一步都在“给定历史信息”的条件下处理当前项这使得依赖关系被巧妙地拆解掉了。4.2 McDiarmid不等式不知道方差时的替代方案McDiarmid不等式是Azuma不等式的一个直接推论但在应用上极其顺手。假设f(x_1, ..., x_n)满足有界差分条件对任意i改变第i个坐标的值函数值的变化不超过c_i那么P(f(X_1, ..., X_n) - E[f] ≥ t) ≤ exp(-2t² / Σc_i²)这个不等式的强大之处在于它根本不需要知道X_i具体服从什么分布甚至不需要它们同分布——只要独立就行。只需要验证函数的“敏感度”是有界的。我在实际应用中最常用McDiarmid的场景是推导经验风险最小化ERM算法的泛化误差界。定义f(S) sup_{h∈H} |R(h) - R_hat(h)|其中S是训练样本。只要损失函数有界且假设空间不太复杂改变一个样本对f的影响通常是有界的然后McDiarmid直接给出泛化误差的集中界。这种“先验证有界差分再套不等式”的流程在理论推导中几乎成了肌肉记忆。我甚至可以说一半以上的泛化界论文里出现的“by McDiarmid inequality”都是这个套路。4.3 有界差分条件的扩展处理“无界”实际场景的坑McDiarmid好用但“有界差分”这个条件在实际中经常不满足。比如线性回归中如果特征向量X的范数没有上界那么改变一个样本X_i损失函数对参数的影响理论上可以无限大。这时候有两条路可以走第一条路是截断法truncation。对样本做预处理把范数过大的样本截断到某个半径R以内然后验证截断后函数的差分上界是O(1/√n)量级。代价是引入截断偏差需要在偏差和方差之间做权衡。第二条路是使用带方差的McDiarmid型不等式也被称为Bernstein型McDiarmid它把差分条件从“绝对有界”放松为“方差不大于某个量级”。典型结果是把上界从exp(-2t²/Σc_i²)改成exp(-t²/(2ΣE[c_i²] (2/3)ct))形式上类似Bernstein。我个人的建议是不要一上来就套McDiarmid。先花十分钟判断一下你的函数是不是真的满足有界差分——很多看似自然的问题其实不满足硬套得到的结果在数学上是站不住脚的。我最初做bandit算法推导的时候就犯过这个错误后来审稿人指出来才意识到。4.4 从凸性到凸对偶集中不等式的另一片天地更新版里我最想重点说的是以Talagrand为代表的凸距离不等式和熵方法。这类不等式在组合优化、随机几何、统计学习理论中有着广泛应用但入门门槛比前面那些高不少。核心思想是如果一个事件的概率用“距离”来度量而这个距离具有一定的凸性那么事件发生的概率可以被一个“复杂度项”所控制。直观来说对于高维随机向量X如果某个集合A在X的支撑集中“面积”不大那么X落在A邻域内的概率就会受到限制。这类不等式的一个典型应用是证明经验过程的集中性。给定函数类F和独立同分布样本X_1, ..., X_n考虑sup_{f∈F} |(1/n)Σf(X_i) - E[f]|。如果直接在F上验证有界差分通常需要F的直径有界而使用Talagrand不等式只需要F的覆盖数covering number可控这在实际问题中容易满足得多。我学习熵方法的时候最大的障碍是其中大量的抽象概念covering number、bracketing number、VC维、Rademacher复杂度。后来我的经验是先把这些复杂度量的定义背熟再去看不等式本身最后回到具体例子中验证。这个过程虽然痛苦但一旦打通你对泛化界证明的理解会进入一个全新的层次。5. 更新版中的新内容非渐近视角和尾概率重排5.1 渐近视角 vs 非渐近视角差别在哪传统概率论教材里大数定律和中心极限定理提供的是“当n趋于无穷”的渐近结论。但在现代统计学和机器学习中我们面对的问题往往要求“有限样本”或“非渐近”的保证。比如说你采集了100个样本训练了一个分类器你希望知道在测试集上的误差以95%的概率不会超过某个上界——这里n100是固定的没法取极限。集中不等式提供的正是这种非渐近保证。它们不依赖于极限运算而是直接给出有限样本情形下“概率衰减”的明确上界。这就是为什么集中不等式在现代统计学习理论中地位如此之高——它补齐了渐近理论无法回答的问题。5.2 尾概率与期望重排从P到E的技巧更新版中我觉得特别实用的一个新技巧是“尾概率积分公式”E[f(X)] ∫₀^∞ P(f(X) t) dt这个公式看似平平无奇但在很多证明中能把“控制期望”转化为“控制尾概率”。然后配合集中不等式如果你对P(f(X) t)有一个指数上界那积分就变成简单的高斯积分直接得到E[f(X)]的上界。我在推导Rademacher复杂度泛化界时就用过这个技巧先对sup_{f∈F} |(1/n)Σσ_i f(X_i)|σ是Rademacher变量套一个集中不等式得到tail bound然后积分得到它的期望上界最后并入泛化界。整个过程干净利落省去了很多繁琐的分割讨论。还有一个相关的重排技巧是“分位数函数”视角如果P(f(X) t) ≤ e^{-t²/2}那么f(X)的期望至多是一个常数大约√(2π)。这实际上是在说一个随机变量的尾部越集中它的期望就越被压在一个小范围内。这种“从尾部到期望”的思维方式对快速估计一个算法的误差界非常管用。5.3 更新版里我加进去的“复杂度惩罚”视角这次更新我把集中不等式和“复杂度惩罚”complexity penalty这个视角结合了起来。核心逻辑是这样的在统计学习里我们希望找到一个模型使得它在训练集上的表现和它在测试集上的表现足够接近。集中不等式就是刻画这种“接近程度”的工具。如果模型的复杂度太高比如假设空间太大那么泛化误差界就会松——因为sup在整个空间上的波动会变大。这个视角的价值在于给你一个“设计指导”在选模型的时候不只是看它在训练集上的损失还要考虑它所在假设空间的复杂度。如果一个模型的复杂度惩罚项太大那即使训练误差很小泛化界也可能不成立。这也是交叉验证为什么有效的理论依据之一——它本质上是在估计不同复杂度之间的权衡。在实际操作中我一般会把训练误差和复杂度惩罚项画在同一个坐标轴上观察总界的最小值出现在哪里那个位置的模型复杂度通常就是比较合理的选择。这种思路在调参和模型选择上比单纯看交叉验证分数更可解释。6. 集中不等式的实战选择指南与常见误区6.1 五步走的选型流程面对一个具体问题我一般按照下面这个流程选不等式第一步判断随机变量是否非负。如果不是考虑平移或取绝对值。第二步判断是否存在独立的加和结构。如果问题本身就是“n个独立随机变量的和”直接进入第三步如果是更复杂的函数考虑能否拆成“局部影响有界”的形式。第三步看变量是否有界。如果有界Hoeffding是最低配置如果还能算方差Bernstein往往更好如果能容忍稍微复杂一点的推导Chernoff最灵活。第四步如果变量之间存在依赖立刻切换到鞅差视角。构造自然的鞅序列验证差分有界条件套Azuma或McDiarmid。第五步如果问题是推导一个算法的高概率界最后一般会需要把多个集中不等式的结果用union bound合在一起这时候要注意union bound虽然直观但有时候会损失指数级的精度。更精细的做法是用“最坏情况分割”或“分层Union Bound”。6.2 常见误区一无限放大“上界”的意义新手最容易犯的错误是拿到一个上界就觉得“真实概率不会比这个大”于是放心大胆地用它来支撑结论。但上界就是上界它可能比真实概率大几十个数量级。在推导算法复杂度时如果一个界是O(1/n)另一个是O(1/√n)后者虽然渐近更差但在n不大时可能反而更紧。所以我在实际中一般会把候选不等式都在具体参数下代入算一遍数值对比之后再做决定。6.3 常见误区二忽略常数项很多人只关注指数部分的形式忽略常数项。但常数在非渐近理论中非常重要。比如Hoeffding不等式里那个2如果换成1界就紧了一倍。在一些小样本场景下这个差异可能决定了结论是否成立。我的习惯是每次推导完了都检查一遍常数看看每一步的放缩是不是可优化。很多时候把Hoeffding引理中的常数从1/8优化到1/8ε²某些条件下更紧或者把Bernstein中2/3这个系数再算一遍就能在最终界里省下一个影响显著的对数因子。6.4 常见误区三忽略“高概率事件”的构造在算法设计里常见的用法是先证明“以至少1-δ的概率某个好事件发生”然后把算法的性能界定在好事件上坏事件上给一个平凡界。这种“好事件坏事件”的分解很实用但有一个隐含的坑坏事件的概率δ要足够小才能保证总的期望界不被坏事件拖垮。举例来说如果算法在坏事件上的性能损失是O(1/ε)而δ O(ε)那乘积就是O(1)在总界中可能是个常量级的项。如果你希望总界是O(√(log(1/δ)/n))这种量级那δ通常得取到O(1/n)甚至更小坏事件项才会被n压制住。我在做bandit算法分析时特别关注这一点。一个高概率界如果只做到δ 1/2基本没有意义做到δ 1/n^{2}会让总界紧得多代价是需要更强的集中不等式比如Bernstein或者带方差的McDiarmid。这里的取舍非常实际调过几次参数就明白了。7. 踩坑记录与调试心得7.1 踩坑一条件期望算错使用Azuma不等式时最重要的一步是验证E[D_i | F_{i-1}] 0。这个条件看着简单但在具体问题里经常被忽略细节。比如在推导Langevin dynamics的收敛性时每一步的更新量依赖于上一步的噪声和当前梯度你构造的“鞅差”必须是真正的鞅差——也就是给定历史信息后条件期望确实是零。我吃过一次亏构造了一个序列看起来像是鞅差但在计算条件期望时漏掉了一个有偏项bias结果整个界算出来偏紧但方向上正确让后面的推导全都建立在一个站不住脚的前提上。事后排查发现只要把条件期望完整展开多出来的一项正好是需要额外处理的偏差项。现在我的做法是构造完鞅差序列后专门花十分钟把条件期望展开一次确认没有遗漏任何随机源。这个习惯帮我避免了很多不必要的返工。7.2 踩坑二union bound过度使用Union bound并集界虽然简单但它的代价是随事件数量线性增长的。如果你有n个事件每个事件用Hoeffding给了一个exp(-2t²/n)的界那union bound之后是n·exp(-2t²/n)导致t必须放大到O(√(n log n))级别才能压住。这个额外的√(log n)因子在很多问题中是可以避免的。我用过一个技巧叫“剥离”peeling把事件的“阈值”分层不是所有事件都用同一个t而是让第i层事件的阈值随i递增。这样union bound求和之后往往得到一个几何级数整体界比直接用同一个阈值紧很多。这个方法在高维线性回归的支撑集恢复证明中特别有用你对每个系数分别验证显著性但如果用相同的阈值union bound会带来一个log pp是维度的惩罚因子用分层处理之后可以把这个惩罚因子消除或者压到更低量级。7.3 踩坑三常数被“优化”得反而出错有些文献里会看到“with high probability”这种说法但常数是多少并没有明确写出来。如果你自己推导时需要精确常数务必一步步检查。我记得有次对比两个不等式的数值表现时发现其中一个的常数似乎优化过了头推导过程中出现了“E[X²] ≤ (E[X])²”这种荒谬的放缩。这种错误隐蔽性很强因为最终界在形式上是合理的只是在某个中间步骤“少乘”或者“多除”了一个因子。我现在给自己定的规矩是每一个用到的常数都必须能够追溯到原始引理不能在中间过程中凭空“改进”。如果确实需要更紧的常数必须重新证明或者引用可信的原始文献。8. 集中不等式在具体领域中的实战位置8.1 在线学习与Bandit算法中的应用在多臂老虎机问题中我们需要估计每个臂的期望奖励然后根据估计选择动作。UCBUpper Confidence Bound算法的核心就是对每个臂构造一个“高概率上界”即真实期望以一个很高的概率不超过\hat{μ} c√(log t / n_t)其中n_t是该臂被选的次数。这个上界就用的是Hoeffding不等式。在更复杂的线性bandit中每次选择都依赖于整个协方差矩阵的逆需要对高维随机向量的范数建立集中性。这时候就需要矩阵版本的Chernoff不等式或者矩阵Bernstein不等式。我的经验是先搞清楚你的随机对象是标量还是向量还是矩阵再去选对应版本的工具不要拿标量不等式硬套。8.2 统计学习理论中的应用泛化误差界的三种主流证明路线——基于VC维的、基于Rademacher复杂度的、基于稳定性stability的——全都依赖集中不等式。VC维那条路线用的是对称化技巧加McDiarmid不等式Rademacher路线用的是条件Rademacher平均的集中性稳定性路线用的是“改变一个样本对算法输出的影响”来构造鞅差。三条思路殊途同归本质上都是在回答同一个问题训练集上的表现能否代表总体的表现我个人最推荐新手从稳定性路线入门因为它最直观如果一个算法对单个样本的变化不敏感那么它的泛化能力就应该好。集中不等式在这里的作用是把“不敏感”量化为“概率高概率成立”。8.3 随机矩阵与高维统计中的应用在高维协方差矩阵估计中我们经常需要控制样本协方差矩阵和总体协方差矩阵之间的谱范数误差。对高斯数据来说这可以用矩阵Bernstein不等式处理得到 ||Σ_hat - Σ||_op ≤ C√(p/n) 的高概率界其中p是维度n是样本量。当p远大于n时这个界仍然有界只是退化成常数级这正好说明了高维问题的本质困难。我对矩阵集中不等式最大的体会是复现他人的常数非常困难。矩阵版本的常数高度依赖于定义和范数的选法谱范数、Frobenius范数、∞-范数都不同甚至同一个定理在不同论文里的常数能有几十倍的差异。所以如果你要拿矩阵集中不等式的结论去和实验对比最好先明确你用的是哪个版本。8.4 随机梯度下降中的非渐近收敛性SGD的收敛性分析是另一个典型的应用场景。考虑更新公式θ_{t1} θ_t - η_t g_t其中g_t是梯度的随机估计。为了证明收敛需要同时处理两个随机源样本抽取的随机性和优化路径本身的随机性。这时候Azuma不等式几乎是标准武器因为g_t和θ_t构成了一个天然的鞅差序列。在处理强凸目标函数时我还发现了一个小技巧与其直接对损失函数套集中不等式不如先对“随机梯度和真实梯度之间的差距”套一个集中不等式再把结果代入递推式。这样可以把“噪声项”和“递推收敛项”分开处理推导会清晰很多。9. 我整理出来的快速参考速查表为了便于日常查阅我这几年整理了一张集中不等式的速查表核心信息如下名称条件上界形式典型应用MarkovX ≥ 0E[X]/t兜底几乎无条件ChebyshevVar(X) ∞Var(X)/t²大偏差粗略界Chernoff独立矩母函数存在exp(inf_λ(Σ log M_i(λ) - λt))Binomial及Poisson尾部Hoeffding独立且有界exp(-2t²/Σ(b-a)²)ERM泛化界Bernstein独立方差有界exp(-t²/(2V 2ct/3))小偏差情形高维banditAzuma鞅差且有界exp(-t²/(2Σc_i²))依赖序列、SGD收敛McDiarmid有界差分exp(-2t²/Σc_i²)经验过程、泛化界Bennett独立方差几乎必然有界exp(-σ²h(ct/σ²))大偏差更精细Talagrand凸距离依赖覆盖数经验过程、组合优化这个表我打印了一份贴在工位上平时推导证明的时候随手一翻就能找到候选工具。你要根据自己的领域调整第三列和第四列但第一列和第二列基本是固定的。另外我每次用不等式之前都会问自己三个问题随机变量之间是否独立是否知道方差是否有界这三个问题的答案能帮你快速锁定选择范围。如果三个问题都不满足就要考虑是不是问题本身的建模方式出了偏差需要换一种随机分解方式。10. 一些个人心得和后续可以继续深挖的方向集中不等式是一个看着简单、学起来易懂、用起来却处处是坑的领域。我最大的体会是不要停留在“会证明”的层面要练到“会选、会用、会在常数之间权衡”的程度。每一个不等式背后都是一套“用已知信息换概率保证”的交易区别只在于你愿意用多少信息、换多少精度。如果这篇文章能帮你少走一些弯路那就很有价值了。建议你先拿一个自己手头正在做的推导练手把里面所有用到集中不等式的地方都标出来然后逐个检查用的是哪个不等式条件都验证了吗常数算对了吗有没有更紧的替代对集中不等式的掌握深度会直接决定你做理论研究的天花板。很多高水平的论文在读的时候感觉“不过就是用了一下Hoeffding”但真正想复现时才意识到作者对不等式的选择、常数处理和条件验证背后其实藏着大量经验。希望这篇更新版的梳理能帮你把这些经验也内化成自己的基本功。
