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

全変分距離に対する凸緩和の階層

基本情報

  • 論文ID: 2401.01086
  • タイトル: A hierarchy of convex relaxations for the total variation distance
  • 著者: Jean B. Lasserre
  • 分類: math.OC（最適化と制御）
  • 発表時期: 2024年1月（arXiv v3: 2025年10月16日）
  • 論文リンク: https://arxiv.org/abs/2401.01086

要約

本論文は、Carleman条件を満たす2つの測度μとνに対して、それらの間の全変分距離を任意の精度で近似するための数値スキームを提案している。本スキームは、一連の（階層化された）凸緩和問題を解くことによって実現され、その最適値の列は全変分距離に収束する。これにより、Moment-SOS階層の多機能性がさらに実証される。階層内の各緩和は半定値計画問題であり、その規模は関与するモーメント数の増加に伴って増大し、最適解は次数2nの疑似モーメントのペアであり、nの増加に伴いμ-νのHahn-Jordan分解のモーメントに収束する。

研究背景と動機

問題の重要性

全変分（Total Variation, TV）距離の数値計算は重要かつ困難な問題であり、以下の分野で広く応用されている：

  1. 統計的検定：同質性検定と独立性検定に用いられる
  2. 分布ロバスト最適化：不確実性集合の定義
  3. データサイエンスと機械学習：測度間の距離度量

既存手法の限界

  1. 経験推定量の問題：ランダムサンプルに基づく経験推定量は一般に一貫性がなく、特にTV距離に対して問題がある
  2. 計算上の課題：TV距離は「悪い」コスト関数c(x,y) = 1_{x≠y}を用いたWasserstein距離と等価であり、効率的な計算が困難である
  3. 関数空間が過大：標準的な双対公式における有界可測関数の空間が大きすぎて、効率的な評価が困難である
  4. コンパクト支持の制限：既存手法は通常、コンパクト支持を要求する

研究動機

既存の貢献は主に特定の分布クラスに対する解析的な上下界の提供に集中しており、汎用的な数値計算手法が不足している。本論文は、比較的弱い仮定の下で実用的な計算スキームを提供することを目指している。

核心的貢献

  1. 数値計算スキーム：Moment-SOS階層に基づく半定値計画緩和の列を提案し、TV距離を任意の精度で近似できる
  2. 理論的保証：緩和列の単調性と収束性を証明し、最適値が下方からTV距離に収束することを示す
  3. 非コンパクト支持への対応：非コンパクト支持を持つ測度に適用可能であり、Carleman条件のみを必要とする
  4. 特殊ケースの精確解：実軸上の原子測度に対して、緩和の次数n ≥ maxm₁,m₂のとき精確解を得られる
  5. 双対理論：双対半定値計画を提供し、古典的なTV距離双対公式を多項式への制限とペナルティ項の追加により強化する方法を明らかにする

方法の詳細

問題の定義

2つの有限Borel測度μ, ν ∈ M(ℝᵈ)₊が与えられたとき、それらの全変分距離を計算する： ∥μ−ν∥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\}

核心的仮定

仮定2.5：

  1. μとνのすべてのモーメントが有限である
  2. μとνが条件を満たす：∫exp⁡(c∣xi∣)dμ<∞\int \exp(c|x_i|) d\mu < \infty、ある c > 0 とすべての i = 1,...,d に対して

方法の構造

1. 無限次元線形計画への再構成

TV距離を無限次元LPとして再構成する： τ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν}\tau = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu\}

2. 重要な制約の強化

支配制約を追加して等価問題を得る： ρ=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. モーメント条件への変換

補題2.2を利用して、支配制約をモーメント行列条件と等価にする： ϕ≤μ⇔Mn(ϕ)⪯Mn(μ),∀n∈N\phi \leq \mu \Leftrightarrow M_n(\phi) \preceq M_n(\mu), \forall n \in \mathbb{N}

4. 半定値計画緩和

第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)\}

技術的な革新点

  1. 支配制約の重要な役割：無限次元公式では冗長であるが、緩和スキームではコンパクト化ツールとして極めて有用である
  2. Carleman条件の巧妙な利用：測度の一意性を保証し、モーメント制約が支配制約と等価になることを可能にする
  3. Hahn-Jordan分解の自然な出現：最適解がμ-νのHahn-Jordan分解に収束する
  4. 双対問題の多項式制限：多項式空間への制限とペナルティ項の追加により、‖f‖∞ ≤ 1制約の違反を処理する

実験設定

実装ツール

  • ソフトウェア：多項式最適化用GloptiPoly 3
  • ソルバー：半定値計画ソルバーSeDuMi 1.03
  • プラットフォーム：HP Elitebook Ubuntu 24ノートブック

テストケース

1. 離散測度

  • 互いに素な支持：X = {-1.0, 0.0, 1.0, 2.0}, Y = {-0.7, 0.3, 1.3, 2.3}
  • 1つの共通点：X ∩ Y = {-1.0}
  • 近接原子：数値安定性のテスト

2. ガウス測度

  • 異なる平均と分散を持つガウス分布N(m₁,σ₁)とN(m₂,σ₂)
  • モーメント数は2n = 4から2n = 8

評価指標

  • 緩和最適値ρₙと真のTV距離の接近度
  • 収束速度と数値安定性
  • 計算時間（すべての結果は0.35秒以内に完了）

実験結果

主要な結果

1. 理論的検証（定理3.4）

実軸上の原子測度に対して、n ≥ maxm₁,m₂のとき精確解を得る：

  • 例1：μ = δ₀, ν = δₑ、ρ₁ = 2（精確）
  • 例2：4つの原子、1つの共通点、ρ₄ = 1.499 ≈ 1.5
  • 例3：互いに素な原子、ρ₄ = 1.9999 ≈ 2

2. ガウス測度の結果

(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. 重要な発見

  • ρ₁は文献1の解析的下界と完全に一致する
  • n=2から始まり大幅に改善され、n=3,4でさらに良好である
  • 小さな分散の場合、相互特異測度の挙動に近い（TV距離は2に近い）

収束性分析

定理3.1が保証する：

  1. 各緩和は最適解を持つ
  2. ρₙ ↑ ‖μ-ν‖_に単調収束する
  3. 最適解はHahn-Jordan分解のモーメントに収束する

関連研究

主要な研究方向

  1. 経験推定量：サンプルに基づく距離推定であるが、TV距離の推定量は一般に一貫性がない
  2. 解析的界：特定の分布クラス（高次元ガウス、ガウス混合など）に対する上下界
  3. 不等式手法：Pinsker不等式、Hellinger距離の界
  4. 最適輸送：Kantorovich度量の専用アルゴリズム（Sinkhorn法など）

本論文の利点

  1. 汎用性：Carleman条件を満たす一般的な測度に適用可能
  2. 非コンパクト支持：コンパクト支持を要求しない
  3. 保証された収束：理論的に保証された単調収束性
  4. 実用性：閉形式モーメントと経験的モーメントの両方に対応可能

結論と考察

主要な結論

  1. TV距離計算のための汎用的な数値スキームを提供する
  2. 比較的弱い仮定の下で任意の精度近似を実現する
  3. 各緩和は保証された下界を提供する
  4. 離散測度に対して精確解を得られる

限界

  1. 次元への敏感性：手法は次元に敏感であり、現在は低次元問題に限定される
  2. 半定値計画ソルバーの制限：高度な緩和問題の解法は期待できない
  3. 数値精度：原子が非常に接近している場合、数値的問題が生じる可能性がある
  4. サンプルサイズの要件：経験的モーメント使用時には十分なサンプルが必要である

今後の方向

  1. より計算効率的な代替下界の提供
  2. 高次元問題への拡張
  3. 数値安定性の改善
  4. 他の距離度量との比較研究

深い評価

利点

  1. 理論的厳密性：完全な収束性証明と双対理論
  2. 手法の新規性：TV距離計算へのMoment-SOS階層の初めての応用
  3. 実用的価値：閉形式とサンプルの両方のデータ形式に対応可能
  4. 精確性の保証：特定の場合（原子測度）に精確解を得られる

不足点

  1. 計算複雑性：半定値計画の計算複雑性が応用規模を制限する
  2. 実験の限定性：主に低次元と単純な分布でテストされている
  3. 既存手法との比較不足：他のTV距離計算手法との体系的な比較が不足している

影響力

  1. 理論的貢献：TV距離計算に新しい理論的枠組みを提供する
  2. 方法論的価値：確率度量計算におけるMoment-SOS階層の可能性を示す
  3. 実際の応用：分布ロバスト最適化などの分野に新しいツールを提供する

適用シーン

  1. 精確計算の必要性：理論的に保証されたTV距離下界が必要な場合
  2. 低次元問題：次元が比較的低い実際の応用
  3. 特殊な分布：ガウス分布、指数分布およびそれらの混合
  4. 離散分布：有限支持を持つ原子測度

参考文献

本論文は28篇の関連文献を引用しており、最適輸送、モーメント問題、半定値計画、確率度量など複数の分野の重要な研究をカバーしている。特に著者自身のMoment-SOS階層に関する一連の研究21,24,26が本論文の理論的基礎を構成している。