Contraction of Rényi Divergences for Discrete Channels: Properties and Applications

Technische Samenvatting: Contractie van Rényi-divergenties voor discrete kanalen

Probleemstelling
De Data-Processing Inequality (DPI) is een hoeksteen van de informatietheorie, die stelt dat post-verwerking de informatie niet kan vergroten. De Strong Data-Processing Inequality (SDPI) verfijnt dit door de contractie van informatie door een kanaal te kwantificeren, gekenmerkt door een contractieconstante $\eta$. Terwijl de eigenschappen van SDPI-constanten voor $\phi$-divergenties (een brede familie die onder meer de KL-divergentie en de totale variatie omvat) goed gevestigd zijn, blijft het gedrag van SDPI-constanten voor Rényi-divergenties van orde $\alpha \ge 0$ minder goed begrepen. Dit werk onderzoekt de contractie-eigenschappen van Rényi-divergenties onder discrete Markov-kanalen, waarbij specifiek wordt onderzocht of de contractiegedragingen waargenomen bij $\phi$-divergenties standhouden voor Rényi-divergenties over verschillende orden $\alpha$.

Methodologie
De auteurs analyseren de SDPI-constante $\eta_\alpha(K)$ voor een Markov-kernel $K$ en orde $\alpha$, gedefinieerd als het supremum van de ratio van de output- tot de input-Rényi-divergentie. De methodologie omvat:

1. Vergelijkende Analyse: Het vaststellen van grenzen en identiteiten die de relatie tussen Rényi-SDPI-constanten en die van Hellinger- en $\chi^2$-divergenties relateren.
2. Regime-differentiatie: Het onderzoeken van het gedrag van deze constanten in twee verschillende regimes: $\alpha \in [0, 1]$ en $\alpha > 1$.
3. Structurele Karakterisering: Het bepalen van de voorwaarden waaronder de contractieconstante gelijk is aan 1 (wat duidt op geen contractie) op basis van de ondersteuningseigenschappen van de overgangskansen van het kanaal.
4. Limietanalyse: Het afleiden van specifieke karakteriseringen voor de $\infty$-Rényi-divergentie ($\alpha \to \infty$) en het relateren hiervan aan Local Differential Privacy (LDP).
5. Toepassing op Convergentie: Het toepassen van deze resultaten om de convergentiesnelheid van Markov-ketens naar hun stationaire verdeling te begrenzen, waarbij Rényi-gebaseerde grenzen worden afgezet tegen traditionele $L_\alpha$-norm-grenzen.

Belangrijkste Bijdragen en Resultaten

• Divergentie van gedrag op basis van $\alpha$:
  Het artikel toont aan dat de orde $\alpha$ bepaalt of de contractie-eigenschappen van Rényi-divergenties de $\phi$-divergenties weerspiegelen.

  • Voor $\alpha \in [0, 1]$: De contractie-eigenschappen komen grotendeels overeen met $\phi$-divergenties. Specifiek is de SDPI-constante begrensd door de totale variatie (TV) constante ($\eta_\alpha(K) \le \eta_{TV}(K)$), en de identiteit $\eta_\alpha(K) = \eta_{\chi^2}(K)$ houdt stand.
  • Voor $\alpha > 1$: Het gedrag wijkt significant af. Het artikel bewijst dat $\eta_\alpha(K)$ groter kan zijn dan $\eta_{TV}(K)$, en de identiteit $\eta_\alpha(K) = \eta_{\chi^2}(K)$ faalt. Bovendien zijn er nieuwe ondergrenzen vastgesteld die $\eta_\alpha$ relateren aan de Hellinger SDPI-constante.

• Structurele Voorwaarden voor Niet-Contractie:
  De auteurs bieden noodzakelijke en voldoende voorwaarden voor $\eta_\alpha(K) = 1$ (d.w.z. het kanaal contracteert de divergentie niet):

  • Voor $\alpha \in [0, 1]$ geldt $\eta_\alpha(K) = 1$ dan en slechts dan als er twee inputtoestanden bestaan met disjuncte output-ondersteuningen (orthogonale rijen).
  • Voor $\alpha > 1$ geldt $\eta_\alpha(K) = 1$ dan en slechts dan als er twee inputtoestanden bestaan met verschillende output-ondersteuningen. Dit is een strikt zwakkere voorwaarde, wat impliceert dat kanalen contractief kunnen zijn onder $\phi$-divergenties maar niet-contractief onder Rényi-divergenties voor $\alpha > 1$.

• Karakterisering van de $\infty$-Rényi-divergentie:
  Voor de limiet $\alpha \to \infty$ stelt het artikel vast dat de verdeling die het supremum in de SDPI-definitie bereikt, een restrictie is van de input-verdeling $\mu$ op een deelverzameling $A \subset X$. Een gesloten vorm van de distributie-onafhankelijke constante $\eta_\infty(K)$ wordt afgeleid, waarbij de minimale ratio van overgangskansen tussen rijen betrokken is.

• Connectie met Local Differential Privacy (LDP):
  Een directe equivalentie wordt vastgesteld tussen de $\infty$-Rényi SDPI-constante en $\epsilon$-Local Differential Privacy. Specifiek is een kanaal $\epsilon$-LDP dan en slechts dan als $\eta_\infty(K) \le 1 - e^{-\epsilon}$. Dit koppelt het concept van "ultra-mixing" in Markov-ketenanalyse aan privacygaranties.

• Convergentie van Markov-ketens:
  De resultaten worden toegepast op de convergentie van Markov-ketens. Het artikel laat zien dat Rényi-SDPI's een grens bieden aan de convergentie van de $L_\alpha$-norm van de dichtheidsratio naar 1. Dit wordt geframed als een "niet-lineaire" contractie, verschillend van de lineaire contractie van $L_\alpha$-normen die gewoonlijk wordt bestudeerd. Numerieke voorbeelden suggereren dat voor een klein aantal iteraties de Rényi-gebaseerde grens nauwer kan zijn dan klassieke $L_\alpha$-norm-grenzen.

Significantie
Het artikel betoogt dat de contractie van Rényi-divergenties een nieuw perspectief biedt op informatieverwerking, met name voor $\alpha > 1$. Door te benadrukken dat standaard eigenschappen van $\phi$-divergenties (zoals bovengrenzen door de totale variatie) niet universeel uitbreiden naar Rényi-divergenties, verheldert dit werk de beperkingen van het toepassen van $\phi$-divergentie-intuïtie op Rényi-instellingen. De expliciete connectie tussen $\infty$-Rényi-contractie en $\epsilon$-LDP biedt een verenigd kader voor het analyseren van privacy en mengeigenschappen. Bovendien suggereert de toepassing op Markov-ketens dat Rényi-gebaseerde grenzen preciezere schattingen kunnen bieden van convergentiesnelheden in specifieke regimes, met name tijdens de vroege iteraties van de keten.