Generalized Pinsker Inequality for Bregman Divergences of Negative Tsallis Entropies

技术摘要：负 Tsallis 熵之 Bregman 散度的广义 Pinsker 不等式

问题陈述
本文旨在解决将概率预测中的超额风险（excess risk）界限转化为分布接近度（即全变差距离或 $\ell_1$ 范数）界限的需求。虽然经典的 Pinsker 不等式为 KL 散度相对于平方 $\ell_1$ 距离提供了一个紧致的下界，但现代鲁棒统计、信号处理和在线学习中的许多应用使用的是 Tsallis（或幂）损失，而非标准的对数损失。Tsallis 损失的贝叶斯风险对应于负 $\alpha$-Tsallis 熵，而相关的超额风险则是该熵生成的 Bregman 散度（等价于 $\beta$-散度，其中 $\beta = \alpha$）。核心问题在于：对于这些 Bregman 散度，其 Pinsker 不等式的类比形式是什么？以及控制从超额风险到 $\ell_1$ 控制的转换所遵循的最优常数是多少？

方法论
作者通过推导最优常数 $C_{\alpha, K}$ 的变分特征，建立了一个紧致的广义 Pinsker 不等式。其核心方法论包括：

1. 变分重构： 他们将常数 $C_{\alpha, K}$ 表示为概率单纯形 $\Delta_K$ 相对内部上一个参数化二次型的下确界。具体而言，$C_{\alpha, K}$ 与最小化一个切向量 $v$（满足 $\|v\|_1=1$ 且 $\sum v_k = 0$）的加权平方分量之和相关，该和式针对 Tsallis 熵的 Hessian 矩阵进行。
2. Hessian 分析： 负 Tsallis 熵的 Hessian 涉及形式为 $\gamma_k^{\alpha-2}$ 的项，其中 $\gamma$ 是单纯形上的一个点。这些系数的行为取决于 $\alpha - 2$ 的符号，会发生性质上的变化。
3. 切向量优化： 该问题简化为最小化 $\ell_\beta$-范数的切向量，其中 $\beta = \frac{2}{3-\alpha}$。作者利用引理来解决这一最小化问题，区分了范数是凹的（$\beta < 1$）还是凸的（$\beta > 1$）情形，并分析了维度 $K$ 及其奇偶性的影响。
4. 相变分析： 证明过程显式地处理了不同的 $\alpha$ 和 $K$ 机制，识别了下确界在何处取得（例如，在极点处、中心处或特定的边界配置处）以及下确界何时消失。

主要贡献与结果
论文建立了 定理 8，它提供了一个显式的、紧致的常数 $C_{\alpha, K}$，使得对于 $\Delta_K$ 相对内部的任何 $p, q$，均有：
$$D_\alpha(p\|q) \geq \frac{C_{\alpha, K}}{2} \|p - q\|_1^2$$
常数 $C_{\alpha, K}$ 根据 $\alpha$ 和 $K$ 展示出截然不同的机制：

• 维度无关机制 ($\alpha \leq 1$)： 常数为 $C_{\alpha, K} = 2^{1-\alpha}$。该常数与维度 $K$ 无关，这意味着对于 $\alpha \leq 1$，从 Tsallis 超额风险到 $\ell_1$ 控制的转换不会遭受维度诅咒。这在 $\alpha=1$（Shannon 熵/KL 散度）时恢复了具有最优常数的经典 Pinsker 不等式。
• 多项式衰减机制 ($1 < \alpha \leq 2$)： 常数按 $K^{1-\alpha}$ 缩放。
  • 对于偶数 $K$，$C_{\alpha, K} = K^{1-\alpha}$。
  • 对于奇数 $K$，$C_{\alpha, K} = K^{1-\alpha} \cdot \sigma_{\alpha, K}$，其中 $\sigma_{\alpha, K}$ 是一个接近 1 的修正因子（$1 \leq \sigma_{\alpha, K} \leq 1 + O(K^{-2})$）。这揭示了一种微妙的奇偶效应，即奇数情况会产生微小的二阶修正。
• 二分类情形 ($K=2, \alpha > 2$)： 存在一个非平凡的 Pinsker 型不等式，其中 $C_{\alpha, 2} = 2^{1-\max\{\alpha, 3\}}$。在 $\alpha=3$ 处存在一个相变，此处常数行为发生变化。
• 多分类失效 ($K \geq 3, \alpha > 2$)： 作者证明了 $C_{\alpha, K} = 0$。在此机制下，不存在统一的正常数 $C$ 使得对于所有 $p, q \in \Delta_K$ 的相对内部，都有 $D_\alpha(p\|q) \geq C \|p-q\|_1^2$。在这种情况下，散度相对于平方 $\ell_1$ 距离可以任意小。然而，论文指出，如果 $p$ 和 $q$ 远离边界（即坐标 $\geq \epsilon$），则可以推导出依赖于 $\epsilon$ 的较弱的不等式。

意义与主张
论文声称，这是针对所有 $\alpha \neq 1$ 的负 $\alpha$-Tsallis 熵生成的 Bregman 散度（包括 Itakura-Saito 散度 $\alpha=0$ 及其他 $\beta$-散度）所提供的第一个紧致的 Pinsker 型不等式。

其意义主要体现在三个领域：

1. 学习理论后果： 该结果提供了一种原则性的方法，将 Tsallis 损失的超额风险界限转化为 $\ell_1$（全变差）控制。这对于将多分类问题中插值规则（plug-in rules）的 0–1 损失遗憾界限转化为 $\ell_1$ 遗憾界限至关重要，并明确了这种转换何时是维度无关的，以及何时会随维度 $K$ 而退化。
2. 在线学习与优化： 常数 $C_{\alpha, K}$ 确定了负 Tsallis 熵的最优 $\ell_1$-强凸参数。这精细化了用于分析 Follow-the-Regularized-Leader (FTRL) 和镜像下降（Mirror Descent）算法的曲率参数，特别是在使用 Tsallis 熵作为正则化项的 Bandit 问题中。
3. 几何洞察： 本工作阐明了 Bregman 散度几何随 $\alpha$ 和 $K$ 变化的几何相变。它强调了对于 $\alpha > 2$ 的多分类设置，其几何结构在统一 $\ell_1$ 控制方面是“病态”的，这一事实将其与 Csiszár $f$-散度（在这些散度中通常存在广义 Pinsker 不等式）区分开来。

作者明确指出，其结果与现有的 Csiszár $f$-散度（包括 Tsallis 相对熵）的广义 Pinsker 不等式是正交的，并指出对于 $\alpha \neq 1$，负 Tsallis 熵的 Bregman 散度并非 $f$-散度。