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 г. (arXiv v3: 16 октября 2025 г.)
  • Ссылка на статью: https://arxiv.org/abs/2401.01086

Аннотация

В данной работе предложена численная схема для произвольно точного приближения расстояния полной вариации между двумя мерами μ и ν, удовлетворяющими условию Карлемана. Схема основана на решении последовательности (иерархических) задач выпуклой релаксации, последовательность оптимальных значений которых сходится к расстоянию полной вариации, что демонстрирует универсальность иерархии Moment-SOS. Каждая релаксация в иерархии представляет собой задачу полуопределённого программирования (ПОП), размер которой растёт с количеством задействованных моментов. Оптимальные решения — это пара псевдомер степени 2n, которые при возрастании n сходятся к моментам разложения Хана-Жордана для μ-ν.

Исследовательский контекст и мотивация

Важность проблемы

Численное вычисление расстояния полной вариации (Total Variation, TV) является важной и сложной задачей с широким применением в следующих областях:

  1. Статистическое тестирование: используется для тестов однородности и независимости
  2. Распределительно-робастная оптимизация: определение множеств неопределённости
  3. Наука о данных и машинное обучение: метрики расстояния между мерами

Ограничения существующих методов

  1. Проблемы эмпирических оценок: эмпирические оценки на основе случайных выборок часто несостоятельны, особенно для расстояния TV
  2. Вычислительные трудности: расстояние TV эквивалентно расстоянию Вассерштейна с "плохой" функцией стоимости c(x,y) = 1_{x≠y}, что затрудняет эффективное вычисление
  3. Чрезмерно большое функциональное пространство: пространство ограниченных измеримых функций в стандартной двойственной формулировке слишком велико для эффективной оценки
  4. Ограничения на носитель: существующие методы обычно требуют компактного носителя

Исследовательская мотивация

Существующие работы в основном сосредоточены на получении аналитических верхних и нижних границ для конкретных классов распределений, но отсутствует универсальный численный метод. Данная работа направлена на предоставление практической вычислительной схемы при относительно слабых предположениях.

Основные вклады

  1. Численная вычислительная схема: предложена последовательность релаксаций полуопределённого программирования на основе иерархии Moment-SOS, позволяющая произвольно точно приближать расстояние TV
  2. Теоретические гарантии: доказана монотонность и сходимость последовательности релаксаций, оптимальные значения сходятся к истинному расстоянию TV снизу
  3. Обработка некомпактных носителей: метод применим к мерам с некомпактным носителем, требуя только выполнения условия Карлемана
  4. Точное решение частных случаев: для атомарных мер на вещественной оси при степени релаксации n ≥ maxm₁,m₂ получается точное решение
  5. Двойственная теория: предоставлена двойственная задача ПОП, раскрывающая, как усилить классическую двойственную формулировку расстояния TV путём ограничения на полиномиальное пространство и добавления штрафных членов

Подробное описание метода

Определение задачи

Даны две конечные борелевские меры μ, ν ∈ 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 как бесконечномерной ЛП: τ=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. Искусное использование условия Карлемана: гарантирует единственность меры, делая условия на моменты эквивалентными доминирующим ограничениям
  3. Естественное появление разложения Хана-Жордана: оптимальные решения сходятся к моментам разложения Хана-Жордана для μ-ν
  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. Оптимальные решения сходятся к моментам разложения Хана-Жордана

Связанные работы

Основные направления исследований

  1. Эмпирические оценки: оценки расстояния на основе выборок, но оценки расстояния TV часто несостоятельны
  2. Аналитические границы: верхние и нижние границы для конкретных классов распределений (например, многомерные гауссовы, гауссовы смеси)
  3. Методы неравенств: неравенство Пинскера, границы через расстояние Хеллингера
  4. Оптимальный транспорт: специализированные алгоритмы для метрики Канторовича (например, алгоритм Синхорна)

Преимущества данной работы

  1. Универсальность: применима к общим мерам, удовлетворяющим условию Карлемана
  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 составляет теоретическую основу данной работы.