2025-11-22T06:46:16.153487

A hierarchy of convex relaxations for the total variation distance

Lasserre
Given two measures $μ$, $ν$ on Rd that satisfy Carleman's condition, we provide a numerical scheme to approximate as closely as desired the total variation distance between $μ$ and $ν$. It consists of solving a sequence (hierarchy) of convex relaxations whose associated sequence of optimal values converges to the total variation distance, an additional illustration of the versatility of the Moment-SOS hierarchy. Indeed each relaxation in the hierarchy is a semidefinite program whose size increases with the number of involved moments. It has an optimal solution which is a couple of degree-2n pseudo-moments which converge, as n grows, to moments of the Hahn-Jordan decomposition of $μ$-$ν$.
academic

Eine Hierarchie konvexer Relaxationen für die Totalvariationsdistanz

Grundinformationen

  • Paper-ID: 2401.01086
  • Titel: A hierarchy of convex relaxations for the total variation distance
  • Autor: Jean B. Lasserre
  • Klassifizierung: math.OC (Optimierung und Kontrolle)
  • Veröffentlichungsdatum: Januar 2024 (arXiv v3: 16. Oktober 2025)
  • Paper-Link: https://arxiv.org/abs/2401.01086

Zusammenfassung

In diesem Artikel wird ein numerisches Schema für zwei Maße μ und ν, die die Carleman-Bedingung erfüllen, vorgeschlagen, um die Totalvariationsdistanz zwischen ihnen mit beliebiger Genauigkeit anzunähern. Das Schema löst eine Reihe von (hierarchischen) konvexen Relaxationsproblemen, deren optimale Wertefolge gegen die Totalvariationsdistanz konvergiert, und demonstriert die Vielseitigkeit der Moment-SOS-Hierarchie. Jede Relaxation in der Hierarchie ist ein semidefinites Programm, dessen Größe mit der Anzahl der beteiligten Momente wächst, mit optimalen Lösungen – einem Paar von Pseudomomenten vom Grad 2n, die gegen die Momente der Hahn-Jordan-Zerlegung von μ-ν konvergieren, wenn n wächst.

Forschungshintergrund und Motivation

Bedeutung des Problems

Die numerische Berechnung der Totalvariations-(TV-)Distanz ist ein wichtiges und herausforderndes Problem mit breiter Anwendung in folgenden Bereichen:

  1. Statistische Tests: Verwendung in Homogenitäts- und Unabhängigkeitstests
  2. Distributionsrobuste Optimierung: Definition von Unsicherheitsmengen
  3. Datenwissenschaft und maschinelles Lernen: Distanzmaße zwischen Maßen

Einschränkungen bestehender Methoden

  1. Probleme mit empirischen Schätzern: Empirische Schätzer basierend auf Zufallsstichproben sind oft inkonsistent, besonders für die TV-Distanz
  2. Rechnerische Herausforderungen: Die TV-Distanz entspricht der Wasserstein-Distanz mit einer „schlechten" Kostenfunktion c(x,y) = 1_{x≠y}, die schwer effizient zu berechnen ist
  3. Zu großer Funktionsraum: Der Raum beschränkter messbarer Funktionen in der standardmäßigen Dualformel ist zu groß für effektive Auswertung
  4. Einschränkungen des Trägers: Bestehende Methoden erfordern typischerweise kompakte Träger

Forschungsmotivation

Bestehende Beiträge konzentrieren sich hauptsächlich auf analytische Ober- und Untergrenzen für spezifische Verteilungsklassen, es fehlt jedoch eine universelle numerische Berechnungsmethode. Dieser Artikel zielt darauf ab, ein praktisches Berechnungsschema unter relativ schwachen Annahmen bereitzustellen.

Kernbeiträge

  1. Numerisches Berechnungsschema: Vorschlag einer Folge von semidefiniten Programmierungsrelaxationen basierend auf der Moment-SOS-Hierarchie, die die TV-Distanz mit beliebiger Genauigkeit annähern kann
  2. Theoretische Garantien: Beweis der Monotonie und Konvergenz der Relaxationsfolge, wobei die optimalen Werte von unten gegen die wahre TV-Distanz konvergieren
  3. Behandlung nicht-kompakter Träger: Die Methode ist auf Maße mit nicht-kompaktem Träger anwendbar und erfordert nur die Erfüllung der Carleman-Bedingung
  4. Exakte Lösung für Spezialfälle: Für Atommasse auf der reellen Achse können exakte Lösungen erhalten werden, wenn der Relaxationsgrad n ≥ maxm₁,m₂
  5. Dualtheorie: Bereitstellung eines dualen semidefiniten Programms, das offenbart, wie die klassische TV-Distanz-Dualformel durch Einschränkung auf Polynome und Hinzufügen von Strafbegriffen verstärkt wird

Methodische Details

Aufgabendefinition

Gegeben zwei endliche Borel-Maße μ, ν ∈ M(ℝᵈ)₊, berechne ihre Totalvariationsdistanz: ∥μ−ν∥TV=sup⁡f{∫fdμ−∫fdν:∥f∥∞≤1}\|\mu - \nu\|_{TV} = \sup_f \left\{\int f d\mu - \int f d\nu : \|f\|_\infty \leq 1\right\}

Kernvoraussetzungen

Annahme 2.5:

  1. Alle Momente von μ und ν sind endlich
  2. μ und ν erfüllen die Bedingung: ∫exp⁡(c∣xi∣)dμ<∞\int \exp(c|x_i|) d\mu < \infty, für ein c > 0 und alle i = 1,...,d

Methodische Architektur

1. Unendlich-dimensionale lineare Programmierungsumformulierung

Umformulierung der TV-Distanz als unendlich-dimensionales LP: τ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν}\tau = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu\}

2. Verstärkung der Schlüsselbeschränkung

Hinzufügen von Dominanzbeschränkungen für ein äquivalentes Problem: ρ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν;ϕ+≤μ;ϕ−≤ν}\rho = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu; \phi_+ \leq \mu; \phi_- \leq \nu\}

3. Umwandlung in Momentenbedingungen

Verwendung von Lemma 2.2, wobei Dominanzbeschränkungen äquivalent zu Momentenmatrixbedingungen sind: ϕ≤μ⇔Mn(ϕ)⪯Mn(μ),∀n∈N\phi \leq \mu \Leftrightarrow M_n(\phi) \preceq M_n(\mu), \forall n \in \mathbb{N}

4. Semidefinite Programmierungsrelaxation

Das n-te Relaxationsproblem: ρn=min⁡ϕ,ψ{ϕ(1)+ψ(1):ϕα−ψα=μα−να,∀α∈N2nd;\rho_n = \min_{\phi,\psi} \{\phi(1) + \psi(1) : \phi_\alpha - \psi_\alpha = \mu_\alpha - \nu_\alpha, \forall \alpha \in \mathbb{N}^d_{2n};0⪯Mn(ϕ)⪯Mn(μ);0⪯Mn(ψ)⪯Mn(ν)}0 \preceq M_n(\phi) \preceq M_n(\mu); 0 \preceq M_n(\psi) \preceq M_n(\nu)\}

Technische Innovationen

  1. Schlüsselrolle der Dominanzbeschränkung: Obwohl in der unendlich-dimensionalen Formulierung redundant, ist sie im Relaxationsschema als Kompaktifizierungswerkzeug äußerst nützlich
  2. Geschickte Nutzung der Carleman-Bedingung: Gewährleistet die Eindeutigkeit des Maßes, wodurch Momentenbeschränkungen äquivalent zu Dominanzbeschränkungen werden
  3. Natürliches Auftreten der Hahn-Jordan-Zerlegung: Die optimale Lösung konvergiert gegen die Hahn-Jordan-Zerlegung von μ-ν
  4. Polynombeschränkung des Dualproblems: Behandlung der Beschränkung ‖f‖∞ ≤ 1 durch Einschränkung auf den Polynomraum und Hinzufügen von Strafbegriffen

Experimentelle Einrichtung

Implementierungswerkzeuge

  • Software: GloptiPoly 3 für Polynomoptimierung
  • Solver: SeDuMi 1.03 semidefiniter Programmiersolver
  • Plattform: HP Elitebook Ubuntu 24 Notebook

Testfälle

1. Diskrete Maße

  • Disjunkte Träger: X = {-1.0, 0.0, 1.0, 2.0}, Y = {-0.7, 0.3, 1.3, 2.3}
  • Ein gemeinsamer Punkt: X ∩ Y = {-1.0}
  • Nahe beieinander liegende Atome: Test der numerischen Stabilität

2. Gauß-Maße

  • Normalverteilungen N(m₁,σ₁) und N(m₂,σ₂) mit unterschiedlichen Mittelwerten und Varianzen
  • Momentenanzahl von 2n = 4 bis 2n = 8

Bewertungsmetriken

  • Nähe der Relaxationsoptimalwerte ρₙ zur wahren TV-Distanz
  • Konvergenzgeschwindigkeit und numerische Stabilität
  • Rechenzeit (alle Ergebnisse in weniger als 0,35 Sekunden abgeschlossen)

Experimentelle Ergebnisse

Hauptergebnisse

1. Theoretische Verifikation (Satz 3.4)

Für Atommasse auf der reellen Achse werden exakte Lösungen erhalten, wenn n ≥ maxm₁,m₂:

  • Beispiel 1: μ = δ₀, ν = δₑ, ρ₁ = 2 (exakt)
  • Beispiel 2: Vier Atome, ein gemeinsamer Punkt, ρ₄ = 1.499 ≈ 1.5
  • Beispiel 3: Disjunkte Atome, ρ₄ = 1.9999 ≈ 2

2. Ergebnisse für Gauß-Maße

(m₁,σ₁)(m₂,σ₂)ρ₁ρ₂ρ₃ρ₄
(0,0.1)(1,0.1)1.92311.99361.99911.9997
(0,0.2)(1,0.2)1.72411.90491.93761.939
(0,0.5)(1,0.5)1.00001.00001.16531.1897

3. Wichtige Erkenntnisse

  • ρ₁ stimmt vollständig mit analytischen Untergrenzen in der Literatur 1 überein
  • Signifikante Verbesserung ab n=2, noch besser bei n=3,4
  • Bei kleiner Varianz Verhalten nahe singulär-singulärer Maße (TV-Distanz nahe 2)

Konvergenzanalyse

Satz 3.1 garantiert:

  1. Jede Relaxation hat eine optimale Lösung
  2. ρₙ ↑ ‖μ-ν‖_ konvergiert monoton
  3. Optimale Lösungen konvergieren gegen Momente der Hahn-Jordan-Zerlegung

Verwandte Arbeiten

Hauptforschungsrichtungen

  1. Empirische Schätzer: Distanzschätzung basierend auf Stichproben, aber TV-Distanz-Schätzer sind oft inkonsistent
  2. Analytische Grenzen: Ober- und Untergrenzen für spezifische Verteilungsklassen (z.B. hochdimensionale Gauß-Verteilungen, Gauß-Mischungen)
  3. Ungleichungsmethoden: Pinsker-Ungleichung, Hellinger-Distanz-Grenzen
  4. Optimaler Transport: Spezialisierte Algorithmen für Kantorovich-Metrik (z.B. Sinkhorn-Algorithmus)

Vorteile dieses Artikels

  1. Allgemeingültigkeit: Anwendbar auf allgemeine Maße, die die Carleman-Bedingung erfüllen
  2. Nicht-kompakte Träger: Erfordert keinen kompakten Träger
  3. Garantierte Konvergenz: Theoretisch garantierte monotone Konvergenz
  4. Praktikabilität: Kann sowohl geschlossene als auch empirische Momente verarbeiten

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Bereitstellung eines universellen numerischen Schemas zur Berechnung der TV-Distanz
  2. Erreichung beliebiger Genauigkeit unter relativ schwachen Annahmen
  3. Jede Relaxation liefert eine garantierte Untergrenze
  4. Exakte Lösungen für diskrete Maße erreichbar

Einschränkungen

  1. Dimensionsempfindlichkeit: Die Methode ist dimensionsabhängig, derzeit auf kleine Dimensionsprobleme beschränkt
  2. Einschränkungen des Solvers: Hochgradige Relaxationsprobleme können nicht erwartet werden
  3. Numerische Genauigkeit: Mögliche numerische Probleme bei sehr nahe beieinander liegenden Atomen
  4. Stichprobengröße: Ausreichend große Stichproben erforderlich bei Verwendung empirischer Momente

Zukünftige Richtungen

  1. Bereitstellung kostengünstigerer alternativer Untergrenzen
  2. Erweiterung auf hochdimensionale Probleme
  3. Verbesserung der numerischen Stabilität
  4. Vergleichende Studien mit anderen Distanzmaßen

Tiefgreifende Bewertung

Stärken

  1. Theoretische Strenge: Vollständige Konvergenzbeweise und Dualtheorie
  2. Methodische Neuheit: Erste Anwendung der Moment-SOS-Hierarchie auf TV-Distanzberechnung
  3. Praktischer Wert: Kann sowohl geschlossene als auch Stichprobendaten verarbeiten
  4. Genauigkeitsgarantie: Exakte Lösungen für spezielle Fälle (Atommasse) erreichbar

Mängel

  1. Rechenkomplexität: Die Rechenkomplexität des semidefiniten Programms begrenzt die Anwendungsgröße
  2. Begrenzte Experimente: Hauptsächlich Tests bei niedriger Dimension und einfachen Verteilungen
  3. Unzureichender Vergleich mit bestehenden Methoden: Fehlende systematische Vergleiche mit anderen TV-Distanz-Berechnungsmethoden

Auswirkungen

  1. Theoretischer Beitrag: Neuer theoretischer Rahmen für TV-Distanzberechnung
  2. Methodologischer Wert: Demonstriert das Potenzial der Moment-SOS-Hierarchie bei der Berechnung von Wahrscheinlichkeitsmaßen
  3. Praktische Anwendung: Neues Werkzeug für Felder wie distributionsrobuste Optimierung

Anwendungsszenarien

  1. Anforderungen an exakte Berechnung: Theoretisch garantierte Untergrenzen der TV-Distanz erforderlich
  2. Probleme niedriger Dimension: Praktische Anwendungen mit niedriger Dimension
  3. Spezielle Verteilungen: Gauß-, Exponential- und Mischverteilungen
  4. Diskrete Verteilungen: Atommasse mit endlichem Träger

Literaturverzeichnis

Der Artikel zitiert 28 relevante Referenzen, die wichtige Arbeiten in mehreren Bereichen abdecken – optimaler Transport, Momentenprobleme, semidefinite Programmierung und Wahrscheinlichkeitsmaße – insbesondere die Arbeiten des Autors zur Moment-SOS-Hierarchie 21,24,26, die die theoretische Grundlage dieses Artikels bilden.