Generalized Pinsker Inequality for Bregman Divergences of Negative Tsallis Entropies

Technical Summary: Generalized Pinsker Inequality for Bregman Divergences of Negative Tsallis Entropies

Problem Statement
The paper addresses the need to translate bounds on excess risk for probabilistic prediction into bounds on distributional closeness, specifically the total variation distance (or $\ell_1$-norm). While the classic Pinsker inequality provides a sharp lower bound for the Kullback–Leibler (KL) divergence in terms of the squared $\ell_1$-distance, many modern applications in robust statistics, signal processing, and online learning utilize Tsallis (or power) losses rather than the standard log loss. The Bayes risk of Tsallis losses corresponds to the negative $\alpha$-Tsallis entropy, and the associated excess risk is the Bregman divergence generated by this entropy (equivalently, the $\beta$-divergence with $\beta = \alpha$). The central question is: What is the analogue of the Pinsker inequality for these Bregman divergences, and what is the optimal constant governing the conversion from excess risk to $\ell_1$-control?

Methodology
The authors establish a sharp generalized Pinsker inequality by deriving a variational characterization of the optimal constant $C_{\alpha, K}$. The core of their methodology involves:

1. Variational Reformulation: They express the constant $C_{\alpha, K}$ as the infimum of a parametric quadratic form over the relative interior of the probability simplex $\Delta_K$. Specifically, $C_{\alpha, K}$ is related to minimizing a weighted sum of squared components of a tangent vector $v$ (where $\|v\|_1=1$ and $\sum v_k = 0$) against the Hessian of the Tsallis entropy.
2. Hessian Analysis: The Hessian of the negative Tsallis entropy involves terms of the form $\gamma_k^{\alpha-2}$, where $\gamma$ is a point on the simplex. The behavior of these coefficients changes qualitatively depending on the sign of $\alpha - 2$.
3. Optimization over Tangent Vectors: The problem reduces to minimizing the $\ell_\beta$-norm of tangent vectors, where $\beta = \frac{2}{3-\alpha}$. The authors utilize Lemmas to solve this minimization problem, distinguishing between cases where the norm is concave ($\beta < 1$) and convex ($\beta > 1$), and analyzing the impact of the dimension $K$ and its parity (even vs. odd).
4. Phase Transition Analysis: The proof explicitly handles different regimes of $\alpha$ and $K$, identifying where the infimum is attained (e.g., at extreme points of the simplex, at the center, or on specific boundary configurations) and where the infimum vanishes.

Key Contributions and Results
The paper establishes Theorem 8, which provides an explicit, sharp constant $C_{\alpha, K}$ such that for any $p, q$ in the relative interior of $\Delta_K$:
$$D_\alpha(p\|q) \geq \frac{C_{\alpha, K}}{2} \|p - q\|_1^2$$
The constant $C_{\alpha, K}$ exhibits distinct regimes based on $\alpha$ and $K$:

• Dimension-Free Regime ($\alpha \leq 1$): The constant is $C_{\alpha, K} = 2^{1-\alpha}$. It is independent of the dimension $K$, implying that for $\alpha \leq 1$, the conversion from Tsallis excess risk to $\ell_1$-control does not suffer from the curse of dimensionality. This recovers the classic Pinsker inequality for $\alpha=1$ (Shannon entropy/KL divergence) with the optimal constant.
• Polynomial Decay Regime ($1 < \alpha \leq 2$): The constant scales as $K^{1-\alpha}$.
  • For even $K$, $C_{\alpha, K} = K^{1-\alpha}$.
  • For odd $K$, $C_{\alpha, K} = K^{1-\alpha} \cdot \sigma_{\alpha, K}$, where $\sigma_{\alpha, K}$ is a correction factor close to 1 ($1 \leq \sigma_{\alpha, K} \leq 1 + O(K^{-2})$). This reveals a subtle parity effect where the odd case incurs a small second-order correction.
• Binary Case ($K=2, \alpha > 2$): A non-trivial Pinsker-type inequality holds with $C_{\alpha, 2} = 2^{1-\max\{\alpha, 3\}}$. There is a phase transition at $\alpha=3$ where the behavior of the constant changes.
• Multiclass Breakdown ($K \geq 3, \alpha > 2$): The authors prove that $C_{\alpha, K} = 0$. No uniform positive constant exists such that $D_\alpha(p\|q) \geq C \|p-q\|_1^2$ for all $p, q$ in the relative interior. The divergence can be arbitrarily small relative to the squared $\ell_1$-distance in this regime. However, the paper notes that if $p$ and $q$ are bounded away from the boundary (i.e., coordinates are $\geq \epsilon$), a weaker inequality with a constant depending on $\epsilon$ can be derived.

Significance and Claims
The paper claims to provide the first sharp Pinsker-type inequality for Bregman divergences generated by negative $\alpha$-Tsallis entropies for all $\alpha \neq 1$, including the Itakura-Saito divergence ($\alpha=0$) and other $\beta$-divergences.

The significance is framed in three main areas:

1. Learning-Theoretic Consequences: The result offers a principled method to convert excess risk bounds on Tsallis losses into $\ell_1$ (total variation) control. This is crucial for deriving 0–1 loss regret bounds for plug-in rules in multiclass classification, clarifying exactly when this conversion is dimension-free and when it degrades with $K$.
2. Online Learning and Optimization: The constant $C_{\alpha, K}$ identifies the optimal $\ell_1$-strong convexity parameter for negative Tsallis entropies. This sharpens the curvature parameters used in the analysis of Follow-the-Regularized-Leader (FTRL) and Mirror Descent algorithms, particularly in bandit problems where Tsallis entropies are used as regularizers.
3. Geometric Insight: The work elucidates the geometric phase transitions of the Bregman divergence geometry as $\alpha$ and $K$ vary. It highlights that for $\alpha > 2$ in multiclass settings, the geometry is "pathological" regarding uniform $\ell_1$-control, a fact that distinguishes it from Csiszár $f$-divergences (where generalized Pinsker inequalities often hold uniformly).

The authors explicitly state that their results are orthogonal to existing generalized Pinsker inequalities for Csiszár $f$-divergences (which include Tsallis relative entropies), noting that for $\alpha \neq 1$, the Bregman divergences of negative Tsallis entropies are not $f$-divergences.