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

A hierarchy of convex relaxations for the total variation distance

基本信息

  • 论文ID: 2401.01086
  • 标题: A hierarchy of convex relaxations for the total variation distance
  • 作者: Jean B. Lasserre
  • 分类: math.OC (Optimization and Control)
  • 发表时间: 2024年1月 (arXiv v3: 2025年10月16日)
  • 论文链接: https://arxiv.org/abs/2401.01086

摘要

本文针对满足Carleman条件的两个测度μ和ν，提出了一个数值方案来任意精确地逼近它们之间的全变分距离。该方案通过求解一系列（层次化的）凸松弛问题，其最优值序列收敛到全变分距离，进一步展示了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距离对偶公式

方法详解

任务定义

给定两个有限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}
  • 一个公共点：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：四个原子，一个公共点，ρ₄ = 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. 方法新颖性：首次将Moment-SOS层次应用于TV距离计算
  3. 实用价值：可处理闭式和样本两种数据形式
  4. 精确性保证：对特定情况（原子测度）可获得精确解

不足

  1. 计算复杂性：半定规划的计算复杂度限制了应用规模
  2. 实验有限性：主要在低维和简单分布上测试
  3. 与现有方法比较不足：缺乏与其他TV距离计算方法的系统比较

影响力

  1. 理论贡献：为TV距离计算提供了新的理论框架
  2. 方法论价值：展示了Moment-SOS层次在概率度量计算中的潜力
  3. 实际应用：为分布鲁棒优化等领域提供了新工具

适用场景

  1. 精确计算需求：需要理论保证的TV距离下界
  2. 小维度问题：维度较低的实际应用
  3. 特殊分布：高斯、指数分布及其混合
  4. 离散分布：有限支撑的原子测度

参考文献

论文引用了28篇相关文献，涵盖了最优传输、矩问题、半定规划和概率度量等多个领域的重要工作，特别是作者自己在Moment-SOS层次方面的系列工作21,24,26构成了本文的理论基础。