Generalized Pinsker Inequality for Bregman Divergences of Negative Tsallis Entropies

Technische Samenvatting: Gegeneraliseerde Pinsker-ongelijkheid voor Bregman-divergenties van negatieve Tsallis-entropieën

Probleemstelling
Het artikel behandelt de noodzaak om grenzen op excess risico voor probabilistische voorspelling te vertalen naar grenzen op de distributionele nabijheid, speciftig de totale variatie-afstand (of $\ell_1$-norm). Terwijl de klassieke Pinsker-ongelijkheid een scherpe ondergrens biedt voor de Kullback–Leibler (KL) divergentie in termen van de gekwadrateerde $\ell_1$-afstand, maken veel moderne toepassingen in robuuste statistiek, signaalverwerking en online leren gebruik van Tsallis (of power) verliezen in plaats van de standaard log-loss. Het Bayes-risico van Tsallis-verliezen komt overeen met de negatieve $\alpha$-Tsallis entropie, en het bijbehorende excess risico is de Bregman-divergentie gegenereerd door deze entropie (equivalent aan de $\beta$-divergentie met $\beta = \alpha$). De centrale vraag is: Wat is het analogue van de Pinsker-ongelijkheid voor deze Bregman-divergenties, en wat is de optimale constante die de conversie van excess risico naar $\ell_1$-controle bepaalt?

Methodologie
De auteurs stellen een scherpe gegeneraliseerde Pinsker-ongelijkheid vast door een variationele karakterisering af te leiden van de optimale constante $C_{\alpha, K}$. De kern van hun methodologie omvat:

1. Variationele Herformulering: Zij drukken de constante $C_{\alpha, K}$ uit als het infimum van een parametrische kwadratische vorm over het relatieve binnenste van de waarschijnlijkheidssimplex $\Delta_K$. Specifiek is $C_{\alpha, K}$ gerelateerd aan het minimaliseren van een gewogen som van de gekwadrateerde componenten van een tangentiële vector $v$ (waarbij $\|v\|_1=1$ en $\sum v_k = 0$) tegen de Hessiaan van de Tsallis-entropie.
2. Hessiaan-analyse: De Hessiaan van de negatieve Tsallis-entropie bevat termen van de vorm $\gamma_k^{\alpha-2}$, waarbij $\gamma$ een punt op de simplex is. Het gedrag van deze coëfficiënten verandert kwalitatief afhankelijk van het teken van $\alpha - 2$.
3. Optimalisatie over Tangentiële Vectoren: Het probleem reduceert tot het minimaliseren van de $\ell_\beta$-norm van tangentiële vectoren, waarbij $\beta = \frac{2}{3-\alpha}$. De auteurs maken gebruik van Lemma's om dit minimalisatieprobleem op te lossen, waarbij zij onderscheid maken tussen gevallen waarin de norm concave is ($\beta < 1$) en convex is ($\beta > 1$), en analyseren de impact van de dimensie $K$ en de pariteit ervan (even vs. oneven).
4. Faseovergangsanalyse: Het bewijs behandelt expliciet verschillende regimes van $\alpha$ en $K$, waarbij wordt geïdentificeerd waar het infimum wordt bereikt (bijv. bij extreme punten van de simplex, in het centrum, of op specifieke randconfiguraties) en waar het infimum verdwijnt.

Belangrijkste Bijdragen en Resultaten
Het artikel stelt Stelling 8 vast, die een expliciete, scherpe constante $C_{\alpha, K}$ biedt zodat voor elke $p, q$ in het relatieve binnenste van $\Delta_K$:
$$D_\alpha(p\|q) \geq \frac{C_{\alpha, K}}{2} \|p - q\|_1^2$$
De constante $C_{\alpha, K}$ vertoont duidelijke regimes gebaseerd op $\alpha$ en $K$:

• Dimensievrije Regimes ($\alpha \leq 1$): De constante is $C_{\alpha, K} = 2^{1-\alpha}$. Deze is onafhankelijk van de dimensie $K$, wat impliceert dat voor $\alpha \leq 1$, de conversie van Tsallis excess risico naar $\ell_1$-controle niet lijdt onder de vloek van dimensionaliteit. Dit herstelt de klassieke Pinsker-ongelijkheid voor $\alpha=1$ (Shannon entropie/KL-divergentie) met de optimale constante.
• Polyloom Afname Regime ($1 < \alpha \leq 2$): De constante schaalt als $K^{1-\alpha}$.
  • Voor even $K$, $C_{\alpha, K} = K^{1-\alpha}$.
  • Voor oneven $K$, $C_{\alpha, K} = K^{1-\alpha} \cdot \sigma_{\alpha, K}$, waarbij $\sigma_{\alpha, K}$ een correctiefactor is die dicht bij 1 ligt ($1 \leq \sigma_{\alpha, K} \leq 1 + O(K^{-2})$). Dit onthult een subtiel pariteitseffect waarbij het oneven geval een kleine tweede-orde correctie ondervindt.
• Binair Geval ($K=2, \alpha > 2$): Een niet-triviale Pinsker-type ongelijkheid houdt stand met $C_{\alpha, 2} = 2^{1-\max\{\alpha, 3\}}$. Er is een faseovergang bij $\alpha=3$ waar het gedrag van de constante verandert.
• Multiclass Breakdown ($K \geq 3, \alpha > 2$): De auteurs bewijzen dat $C_{\alpha, K} = 0$. Er bestaat geen uniforme positieve constante zodanig dat $D_\alpha(p\|q) \geq C \|p-q\|_1^2$ voor alle $p, q$ in het relatieve binnenste. De divergentie kan in dit regime willekeurig klein zijn ten opzichte van de gekwadrateerde $\ell_1$-afstand. Echter, het artikel merkt op dat als $p$ en $q$ ver verwijderd zijn van de rand (d.w.z. coördinaten $\geq \epsilon$), een zwakkere ongelijkheid met een constante die afhangt van $\epsilon$ kan worden afgeleid.

Significantie en Claims
Het artikel claimt de eerste scherpe Pinsker-type ongelijkheid te bieden voor Bregman-divergenties gegenereerd door negatieve $\alpha$-Tsallis entropieën voor alle $\alpha \neq 1$, inclus_ de Itakura-Saito divergentie ($\alpha=0$) en andere $\beta$-divergenties.

De significantie wordt in drie hoofdområden geplaatst:

1. Leertheoretische Gevolgen: Het resultaat biedt een principieel methode om excess risico-grenzen op Tsallis-verliezen om te zetten naar $\ell_1$ (totale variatie) controle. Dit is cruciaal voor het afleiden van 0–1 loss regret bounds voor plug-in regels in multiclass classificatie, waarbij exact wordt verduidelijkt wanneer deze conversie dimensievrij is en wanneer deze degradeert met $K$.
2. Online Leren en Optimalisatie: De constante $C_{\alpha, K}$ identificeert de optimale $\ell_1$-sterke convexiteitsparameter voor negatieve Tsallis-entropieën. Dit verscherpt de krommingparameters die worden gebruikt in de analyse van Follow-the-Regularized-Leader (FTRL) en Mirror Descent algoritmen, met name in bandit-problemen waar Tsallis-entropieën als regularisatoren worden gebruikt.
3. Geometisch Inzicht: Het werk verheldert de geometrische faseovergangen van de Bregman-divergentie geometrie naarmate $\alpha$ en $K$ variëren. Het benadrukt dat voor $\alpha > 2$ in multiclass settings, de geometrie "pathologisch" is met betrekking tot uniforme $\ell_1$-controle, een feit dat de Tsallis-entropie onderscheidt van Csiszár $f$-divergenties (waar gegeneraliseerde Pinsker-ongelijkheden vaak uniform standhouden).

De auteurs stellen expliciet dat hun resultaten orthogonaal zijn aan bestaande gegeneraliseerde Pinsker-ongelijkheden voor Csiszár $f$-divergenties (die Tsallis relatieve entropieën omvatten), waarbij zij opmerken dat voor $\alpha \neq 1$, de Bregman-divergenties van negatieve Tsallis-entropieën geen $f$-divergenties zijn.