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

Una gerarchia di rilassamenti convessi per la distanza della variazione totale

Informazioni Fondamentali

  • ID Articolo: 2401.01086
  • Titolo: A hierarchy of convex relaxations for the total variation distance
  • Autore: Jean B. Lasserre
  • Classificazione: math.OC (Ottimizzazione e Controllo)
  • Data di Pubblicazione: Gennaio 2024 (arXiv v3: 16 ottobre 2025)
  • Link Articolo: https://arxiv.org/abs/2401.01086

Riassunto

Il presente articolo propone uno schema numerico per approssimare arbitrariamente con precisione la distanza della variazione totale tra due misure μ e ν che soddisfano la condizione di Carleman. Lo schema procede risolvendo una sequenza (gerarchica) di problemi di rilassamento convesso, i cui valori ottimali convergono alla distanza della variazione totale, dimostrando ulteriormente la versatilità della gerarchia Moment-SOS. Ogni rilassamento nella gerarchia è un problema di programmazione semidefinita, la cui dimensione aumenta con il numero di momenti coinvolti, con soluzione ottimale—una coppia di pseudomisure di grado 2n, che convergono ai momenti della decomposizione di Hahn-Jordan di μ-ν al crescere di n.

Contesto di Ricerca e Motivazione

Importanza del Problema

Il calcolo numerico della distanza della variazione totale (Total Variation, TV) è un problema importante e impegnativo, con applicazioni diffuse nei seguenti ambiti:

  1. Test Statistici: utilizzati per test di omogeneità e test di indipendenza
  2. Ottimizzazione Robusta Distributiva: definizione di insiemi di incertezza
  3. Data Science e Machine Learning: misure di distanza tra distribuzioni

Limitazioni dei Metodi Esistenti

  1. Problemi degli Stimatori Empirici: gli stimatori empirici basati su campioni casuali sono spesso incoerenti, in particolare per la distanza TV
  2. Sfide Computazionali: la distanza TV è equivalente alla distanza di Wasserstein con funzione di costo "cattiva" c(x,y) = 1_{x≠y}, difficile da calcolare efficientemente
  3. Spazio Funzionale Eccessivamente Grande: lo spazio delle funzioni misurabili limitate nella formulazione duale standard è troppo grande per una valutazione efficace
  4. Restrizioni sul Supporto: i metodi esistenti generalmente richiedono supporto compatto

Motivazione della Ricerca

I contributi esistenti si concentrano principalmente nel fornire limiti analitici superiori e inferiori per classi specifiche di distribuzioni, mancando di un metodo numerico di calcolo universale. Il presente articolo mira a fornire uno schema di calcolo pratico sotto ipotesi relativamente deboli.

Contributi Principali

  1. Schema di Calcolo Numerico: propone una sequenza di rilassamenti di programmazione semidefinita basata sulla gerarchia Moment-SOS, in grado di approssimare arbitrariamente con precisione la distanza TV
  2. Garanzie Teoriche: dimostra la monotonicità e la convergenza della sequenza di rilassamenti, con i valori ottimali che convergono dal basso alla vera distanza TV
  3. Gestione del Supporto Non Compatto: il metodo è applicabile a misure con supporto non compatto, richiedendo solo la soddisfazione della condizione di Carleman
  4. Risoluzione Esatta di Casi Particolari: per misure atomiche sulla retta reale, si ottiene la soluzione esatta quando il grado di rilassamento n ≥ maxm₁,m₂
  5. Teoria Duale: fornisce la programmazione semidefinita duale, rivelando come rafforzare la formulazione duale classica della distanza TV limitandosi a polinomi e aggiungendo termini di penalità

Dettagli del Metodo

Definizione del Compito

Date due misure di Borel finite μ, ν ∈ M(ℝᵈ)₊, calcolare la loro distanza della variazione totale: ∥μ−ν∥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\}

Ipotesi Fondamentali

Ipotesi 2.5:

  1. Tutti i momenti di μ e ν sono finiti
  2. μ e ν soddisfano la condizione: ∫exp⁡(c∣xi∣)dμ<∞\int \exp(c|x_i|) d\mu < \infty, per qualche c > 0 e tutti i = 1,...,d

Architettura del Metodo

1. Riformulazione come Programmazione Lineare Infinito-Dimensionale

Ricostituire la distanza TV come LP infinito-dimensionale: τ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν}\tau = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu\}

2. Potenziamento dei Vincoli Chiave

Aggiungere vincoli di dominanza per ottenere il problema equivalente: ρ=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. Conversione delle Condizioni di Momento

Utilizzando il Lemma 2.2, i vincoli di dominanza sono equivalenti alle condizioni di matrice di momento: ϕ≤μ⇔Mn(ϕ)⪯Mn(μ),∀n∈N\phi \leq \mu \Leftrightarrow M_n(\phi) \preceq M_n(\mu), \forall n \in \mathbb{N}

4. Rilassamento di Programmazione Semidefinita

Problema di rilassamento di livello n: ρ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)\}

Punti di Innovazione Tecnica

  1. Ruolo Cruciale dei Vincoli di Dominanza: sebbene ridondanti nella formulazione infinito-dimensionale, sono estremamente utili come strumento di compattificazione nello schema di rilassamento
  2. Utilizzo Abile della Condizione di Carleman: garantisce l'unicità della misura, rendendo i vincoli di momento equivalenti ai vincoli di dominanza
  3. Emergenza Naturale della Decomposizione di Hahn-Jordan: la soluzione ottimale converge ai momenti della decomposizione di Hahn-Jordan di μ-ν
  4. Restrizione Polinomiale del Problema Duale: affrontare la violazione del vincolo ‖f‖∞ ≤ 1 limitandosi allo spazio polinomiale e aggiungendo termini di penalità

Configurazione Sperimentale

Strumenti di Implementazione

  • Software: GloptiPoly 3 per l'ottimizzazione polinomiale
  • Risolutore: SeDuMi 1.03 risolutore di programmazione semidefinita
  • Piattaforma: Notebook HP Elitebook Ubuntu 24

Casi di Test

1. Misure Discrete

  • Supporti mutuamente disgiunti: X = {-1.0, 0.0, 1.0, 2.0}, Y = {-0.7, 0.3, 1.3, 2.3}
  • Un punto comune: X ∩ Y = {-1.0}
  • Atomi vicini: test della stabilità numerica

2. Misure Gaussiane

  • Distribuzioni gaussiane con medie e varianze diverse N(m₁,σ₁) e N(m₂,σ₂)
  • Numero di momenti da 2n = 4 a 2n = 8

Indicatori di Valutazione

  • Vicinanza del valore ottimale di rilassamento ρₙ alla vera distanza TV
  • Velocità di convergenza e stabilità numerica
  • Tempo di calcolo (tutti i risultati completati in 0.35 secondi)

Risultati Sperimentali

Risultati Principali

1. Verifica Teorica (Teorema 3.4)

Per misure atomiche sulla retta reale, si ottiene la soluzione esatta quando n ≥ maxm₁,m₂:

  • Esempio 1: μ = δ₀, ν = δₑ, ρ₁ = 2 (esatto)
  • Esempio 2: quattro atomi, un punto comune, ρ₄ = 1.499 ≈ 1.5
  • Esempio 3: atomi mutuamente disgiunti, ρ₄ = 1.9999 ≈ 2

2. Risultati per Misure Gaussiane

(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. Scoperte Importanti

  • ρ₁ coincide perfettamente con i limiti inferiori analitici della letteratura 1
  • Miglioramento significativo a partire da n=2, ancora migliore per n=3,4
  • Con varianza piccola, comportamento prossimo a misure mutuamente singolari (distanza TV prossima a 2)

Analisi della Convergenza

Il Teorema 3.1 garantisce:

  1. Ogni rilassamento ha una soluzione ottimale
  2. ρₙ ↑ ‖μ-ν‖_ converge monotonicamente
  3. Le soluzioni ottimali convergono ai momenti della decomposizione di Hahn-Jordan

Lavori Correlati

Principali Direzioni di Ricerca

  1. Stimatori Empirici: stima della distanza basata su campioni, ma gli stimatori della distanza TV sono spesso incoerenti
  2. Limiti Analitici: fornire limiti superiori e inferiori per classi specifiche di distribuzioni (come gaussiane ad alta dimensione, miscele gaussiane)
  3. Metodi di Disuguaglianza: disuguaglianza di Pinsker, limiti di distanza di Hellinger
  4. Trasporto Ottimale: algoritmi specializzati per la metrica di Kantorovich (come algoritmo di Sinkhorn)

Vantaggi del Presente Lavoro

  1. Universalità: applicabile a misure generali che soddisfano la condizione di Carleman
  2. Supporto Non Compatto: non richiede insiemi di supporto compatto
  3. Convergenza Garantita: convergenza monotonica garantita teoricamente
  4. Praticità: può gestire sia momenti in forma chiusa che momenti empirici

Conclusioni e Discussione

Conclusioni Principali

  1. Fornisce uno schema numerico universale per il calcolo della distanza TV
  2. Realizza approssimazione arbitraria con precisione sotto ipotesi relativamente deboli
  3. Ogni rilassamento fornisce un limite inferiore garantito
  4. Per misure discrete si può ottenere la soluzione esatta

Limitazioni

  1. Sensibilità alla Dimensione: il metodo è sensibile alla dimensione, attualmente limitato a problemi a bassa dimensione
  2. Limitazioni del Risolutore di Programmazione Semidefinita: non è possibile aspettarsi di risolvere problemi di rilassamento di alto grado
  3. Precisione Numerica: possibili problemi numerici quando gli atomi sono troppo vicini
  4. Requisiti sulla Dimensione del Campione: quando si utilizzano momenti empirici, è necessaria una dimensione del campione sufficientemente grande

Direzioni Future

  1. Fornire limiti inferiori alternativi computazionalmente più efficienti
  2. Estendere il trattamento a problemi ad alta dimensione
  3. Migliorare la stabilità numerica
  4. Studi comparativi con altre misure di distanza

Valutazione Approfondita

Punti di Forza

  1. Rigore Teorico: dimostrazioni complete della convergenza e teoria duale
  2. Novità del Metodo: prima applicazione della gerarchia Moment-SOS al calcolo della distanza TV
  3. Valore Pratico: può gestire sia dati in forma chiusa che campionari
  4. Garanzie di Precisione: soluzione esatta ottenibile per casi particolari (misure atomiche)

Insufficienze

  1. Complessità Computazionale: la complessità computazionale della programmazione semidefinita limita la scala di applicazione
  2. Limitatezza degli Esperimenti: principalmente testato su problemi a bassa dimensione e distribuzioni semplici
  3. Confronto Insufficiente con Metodi Esistenti: manca un confronto sistematico con altri metodi di calcolo della distanza TV

Impatto

  1. Contributo Teorico: fornisce un nuovo quadro teorico per il calcolo della distanza TV
  2. Valore Metodologico: dimostra il potenziale della gerarchia Moment-SOS nel calcolo di metriche probabilistiche
  3. Applicazioni Pratiche: fornisce nuovi strumenti per campi come l'ottimizzazione robusta distributiva

Scenari di Applicazione

  1. Requisiti di Calcolo Esatto: quando sono necessari limiti inferiori della distanza TV con garanzie teoriche
  2. Problemi a Bassa Dimensione: applicazioni pratiche con dimensionalità relativamente bassa
  3. Distribuzioni Speciali: distribuzioni gaussiane, esponenziali e loro miscele
  4. Distribuzioni Discrete: misure atomiche con supporto finito

Bibliografia

L'articolo cita 28 riferimenti correlati, coprendo molteplici campi come trasporto ottimale, problemi di momenti, programmazione semidefinita e metriche probabilistiche, con particolare enfasi sui lavori dell'autore stesso sulla gerarchia Moment-SOS 21,24,26 che costituiscono la base teorica del presente articolo.