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

Une hiérarchie de relaxations convexes pour la distance de variation totale

Informations de base

  • ID de l'article: 2401.01086
  • Titre: A hierarchy of convex relaxations for the total variation distance
  • Auteur: Jean B. Lasserre
  • Classification: math.OC (Optimisation et Contrôle)
  • Date de publication: Janvier 2024 (arXiv v3: 16 octobre 2025)
  • Lien de l'article: https://arxiv.org/abs/2401.01086

Résumé

Cet article propose un schéma numérique pour approximer arbitrairement précisément la distance de variation totale entre deux mesures μ et ν satisfaisant la condition de Carleman. Le schéma résout une séquence (hiérarchisée) de problèmes de relaxation convexe dont les valeurs optimales convergent vers la distance de variation totale, démontrant ainsi la polyvalence de la hiérarchie Moment-SOS. Chaque relaxation dans la hiérarchie est un problème de programmation semi-définie dont la taille augmente avec le nombre de moments impliqués, possédant une solution optimale — une paire de pseudo-mesures de degré 2n qui convergent vers les moments de la décomposition de Hahn-Jordan de μ-ν lorsque n croît.

Contexte et motivation de la recherche

Importance du problème

Le calcul numérique de la distance de variation totale (TV) est un problème important et difficile avec des applications étendues dans les domaines suivants :

  1. Tests statistiques : utilisés pour les tests d'homogénéité et d'indépendance
  2. Optimisation robuste en distribution : définition d'ensembles d'incertitude
  3. Science des données et apprentissage automatique : mesure de distance entre distributions

Limitations des méthodes existantes

  1. Problèmes des estimateurs empiriques : les estimateurs empiriques basés sur des échantillons aléatoires sont souvent inconsistants, particulièrement pour la distance TV
  2. Défis computationnels : la distance TV est équivalente à la distance de Wasserstein avec une fonction de coût « mauvaise » c(x,y) = 1_{x≠y}, difficile à calculer efficacement
  3. Espace fonctionnel trop grand : l'espace des fonctions mesurables bornées dans la formulation duale standard est trop grand pour une évaluation efficace
  4. Restrictions de support : les méthodes existantes exigent généralement un support compact

Motivation de la recherche

Les contributions existantes se concentrent principalement sur la fourniture de bornes analytiques pour des classes de distributions spécifiques, manquant d'une méthode numérique universelle. Cet article vise à fournir un schéma de calcul pratique sous des hypothèses relativement faibles.

Contributions principales

  1. Schéma de calcul numérique : propose une séquence de relaxations de programmation semi-définie basée sur la hiérarchie Moment-SOS pouvant approximer arbitrairement précisément la distance TV
  2. Garanties théoriques : prouve la monotonie et la convergence de la séquence de relaxation, avec les valeurs optimales convergeant par le bas vers la véritable distance TV
  3. Traitement du support non-compact : la méthode s'applique aux mesures à support non-compact, nécessitant seulement la condition de Carleman
  4. Résolution exacte de cas particuliers : pour les mesures atomiques sur l'axe réel, une solution exacte peut être obtenue lorsque le degré de relaxation n ≥ maxm₁,m₂
  5. Théorie duale : fournit une programmation semi-définie duale, révélant comment renforcer la formulation duale classique de la distance TV en restreignant aux polynômes et en ajoutant des termes de pénalité

Détails de la méthode

Définition de la tâche

Étant donné deux mesures de Borel finies μ, ν ∈ M(ℝᵈ)₊, calculer leur distance de variation 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\}

Hypothèses principales

Hypothèse 2.5 :

  1. Tous les moments de μ et ν sont finis
  2. μ et ν satisfont la condition : ∫exp⁡(c∣xi∣)dμ<∞\int \exp(c|x_i|) d\mu < \infty, pour un certain c > 0 et tous i = 1,...,d

Architecture de la méthode

1. Reformulation en programmation linéaire infini-dimensionnelle

Reformuler la distance TV comme un LP infini-dimensionnel : τ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν}\tau = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu\}

2. Renforcement des contraintes clés

Ajouter des contraintes de domination pour obtenir un problème équivalent : ρ=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. Conversion des conditions de moments

Utiliser le Lemme 2.2, les contraintes de domination sont équivalentes aux conditions de matrices de moments : ϕ≤μ⇔Mn(ϕ)⪯Mn(μ),∀n∈N\phi \leq \mu \Leftrightarrow M_n(\phi) \preceq M_n(\mu), \forall n \in \mathbb{N}

4. Relaxation de programmation semi-définie

Problème de relaxation au niveau 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)\}

Points d'innovation technique

  1. Rôle clé des contraintes de domination : bien que redondantes dans la formulation infini-dimensionnelle, elles sont extrêmement utiles comme outil de compactification dans le schéma de relaxation
  2. Utilisation astucieuse de la condition de Carleman : garantit l'unicité de la mesure, rendant les contraintes de moments équivalentes aux contraintes de domination
  3. Émergence naturelle de la décomposition de Hahn-Jordan : la solution optimale converge vers la décomposition de Hahn-Jordan de μ-ν
  4. Restriction polynomiale du problème dual : traiter la violation de la contrainte ‖f‖∞ ≤ 1 en restreignant à l'espace polynomial et en ajoutant des termes de pénalité

Configuration expérimentale

Outils d'implémentation

  • Logiciel : GloptiPoly 3 pour l'optimisation polynomiale
  • Solveur : SeDuMi 1.03 solveur de programmation semi-définie
  • Plateforme : Ordinateur portable HP Elitebook Ubuntu 24

Cas de test

1. Mesures discrètes

  • Supports disjoints : X = {-1.0, 0.0, 1.0, 2.0}, Y = {-0.7, 0.3, 1.3, 2.3}
  • Un point commun : X ∩ Y = {-1.0}
  • Atomes proches : test de stabilité numérique

2. Mesures gaussiennes

  • Distributions gaussiennes avec moyennes et variances différentes N(m₁,σ₁) et N(m₂,σ₂)
  • Nombre de moments de 2n = 4 à 2n = 8

Indicateurs d'évaluation

  • Proximité de la valeur optimale de relaxation ρₙ à la véritable distance TV
  • Vitesse de convergence et stabilité numérique
  • Temps de calcul (tous les résultats complétés en 0,35 secondes)

Résultats expérimentaux

Résultats principaux

1. Vérification théorique (Théorème 3.4)

Pour les mesures atomiques sur l'axe réel, une solution exacte est obtenue lorsque n ≥ maxm₁,m₂ :

  • Exemple 1 : μ = δ₀, ν = δₑ, ρ₁ = 2 (exact)
  • Exemple 2 : quatre atomes, un point commun, ρ₄ = 1.499 ≈ 1.5
  • Exemple 3 : atomes disjoints, ρ₄ = 1.9999 ≈ 2

2. Résultats pour les mesures gaussiennes

(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. Découvertes importantes

  • ρ₁ correspond exactement aux bornes analytiques inférieures de la littérature 1
  • Amélioration significative à partir de n=2, meilleure performance à n=3,4
  • Comportement proche des mesures mutuellement singulières avec petite variance (distance TV proche de 2)

Analyse de convergence

Le Théorème 3.1 garantit :

  1. Chaque relaxation possède une solution optimale
  2. ρₙ ↑ ‖μ-ν‖_ converge monotonement
  3. Les solutions optimales convergent vers les moments de la décomposition de Hahn-Jordan

Travaux connexes

Directions de recherche principales

  1. Estimateurs empiriques : estimation de distance basée sur des échantillons, mais les estimateurs de distance TV sont souvent inconsistants
  2. Bornes analytiques : fourniture de bornes supérieures et inférieures pour des classes de distributions spécifiques (comme les gaussiennes de haute dimension, les mélanges gaussiens)
  3. Méthodes d'inégalités : inégalité de Pinsker, bornes de distance de Hellinger
  4. Transport optimal : algorithmes spécialisés pour la métrique de Kantorovich (comme l'algorithme de Sinkhorn)

Avantages de cet article

  1. Généralité : applicable aux mesures générales satisfaisant la condition de Carleman
  2. Support non-compact : ne nécessite pas un support compact
  3. Convergence garantie : convergence monotone garantie théoriquement
  4. Praticité : peut traiter à la fois les moments de forme fermée et les moments empiriques

Conclusions et discussion

Conclusions principales

  1. Fournit un schéma numérique universel pour le calcul de la distance TV
  2. Réalise une approximation arbitrairement précise sous des hypothèses relativement faibles
  3. Chaque relaxation fournit une borne inférieure garantie
  4. Une solution exacte peut être obtenue pour les mesures discrètes

Limitations

  1. Sensibilité à la dimension : la méthode est sensible à la dimension, actuellement limitée aux problèmes de petite dimension
  2. Limitations du solveur de programmation semi-définie : impossible de résoudre des problèmes de relaxation hautement dégénérés
  3. Précision numérique : peut rencontrer des problèmes numériques lorsque les atomes sont trop proches
  4. Exigences de taille d'échantillon : nécessite un échantillon suffisamment grand lors de l'utilisation de moments empiriques

Directions futures

  1. Fournir des bornes inférieures alternatives moins coûteuses en calcul
  2. Extension au traitement des problèmes de haute dimension
  3. Amélioration de la stabilité numérique
  4. Études comparatives avec d'autres mesures de distance

Évaluation approfondie

Points forts

  1. Rigueur théorique : preuves complètes de convergence et théorie duale
  2. Nouveauté de la méthode : première application de la hiérarchie Moment-SOS au calcul de la distance TV
  3. Valeur pratique : peut traiter à la fois les données de forme fermée et les données d'échantillon
  4. Garanties d'exactitude : solution exacte possible pour les cas particuliers (mesures atomiques)

Insuffisances

  1. Complexité computationnelle : la complexité computationnelle de la programmation semi-définie limite l'échelle des applications
  2. Expériences limitées : principalement testées sur des problèmes de basse dimension et des distributions simples
  3. Comparaison insuffisante avec les méthodes existantes : manque de comparaison systématique avec d'autres méthodes de calcul de distance TV

Impact

  1. Contribution théorique : fournit un nouveau cadre théorique pour le calcul de la distance TV
  2. Valeur méthodologique : démontre le potentiel de la hiérarchie Moment-SOS dans le calcul de mesures de probabilité
  3. Applications pratiques : fournit de nouveaux outils pour des domaines comme l'optimisation robuste en distribution

Scénarios d'application

  1. Besoins de calcul exact : nécessité de bornes inférieures de distance TV théoriquement garanties
  2. Problèmes de petite dimension : applications pratiques avec dimension relativement faible
  3. Distributions spéciales : distributions gaussiennes, exponentielles et leurs mélanges
  4. Distributions discrètes : mesures atomiques à support fini

Références

L'article cite 28 références connexes, couvrant plusieurs domaines importants incluant le transport optimal, la théorie des moments, la programmation semi-définie et les mesures de probabilité, en particulier les travaux en série de l'auteur sur la hiérarchie Moment-SOS 21,24,26 qui constituent la base théorique de cet article.