2025-11-14T20:13:11.521057

Minimax Optimal Kernel Two-Sample Tests with Random Features

Mukherjee, Sriperumbudur
Reproducing Kernel Hilbert Space (RKHS) embedding of probability distributions has proved to be an effective approach, via MMD (maximum mean discrepancy), for nonparametric hypothesis testing problems involving distributions defined over general (non-Euclidean) domains. While a substantial amount of work has been done on this topic, only recently have minimax optimal two-sample tests been constructed that incorporate, unlike MMD, both the mean element and a regularized version of the covariance operator. However, as with most kernel algorithms, the optimal test scales cubically in the sample size, limiting its applicability. In this paper, we propose a spectral-regularized two-sample test based on random Fourier feature (RFF) approximation and investigate the trade-offs between statistical optimality and computational efficiency. We show the proposed test to be minimax optimal if the approximation order of RFF (which depends on the smoothness of the likelihood ratio and the decay rate of the eigenvalues of the integral operator) is sufficiently large. We develop a practically implementable permutation-based version of the proposed test with a data-adaptive strategy for selecting the regularization parameter. Finally, through numerical experiments on simulated and benchmark datasets, we demonstrate that the proposed RFF-based test is computationally efficient and performs almost similarly (with a small drop in power) to the exact test.
academic

Минимаксные оптимальные ядерные двухвыборочные тесты со случайными признаками

Основная информация

  • ID статьи: 2502.20755
  • Название: Minimax Optimal Kernel Two-Sample Tests with Random Features
  • Авторы: Soumya Mukherjee, Bharath K. Sriperumbudur (Pennsylvania State University)
  • Классификация: math.ST cs.LG stat.ML stat.TH
  • Дата публикации: 17 октября 2025 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2502.20755

Аннотация

В данной статье предлагается метод спектральной регуляризации для двухвыборочного тестирования на основе аппроксимации случайными признаками Фурье (RFF) для задач, основанных на вложениях в воспроизводящее ядерное гильбертово пространство (RKHS). Предложенный метод сохраняет статистическую оптимальность, одновременно значительно снижая вычислительную сложность с кубической до почти линейной, и предоставляет полностью управляемую данными практическую реализацию.

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

Основная проблема

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

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

  1. Субоптимальность MMD-тестов: Хотя тесты максимальной средней разности (MMD) широко применяются, им не хватает минимаксной оптимальности, так как они учитывают только вложение среднего значения, игнорируя информацию оператора ковариации
  2. Вычислительные узкие места спектральной регуляризации: Недавно предложенные спектрально регуляризованные MMD-тесты достигают минимаксной оптимальности, но имеют вычислительную сложность O(n³), что ограничивает их применение к крупномасштабным данным
  3. Сложность выбора параметров: Выбор параметра регуляризации зависит от неизвестных характеристик распределения и не имеет адаптивной стратегии, управляемой данными

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

Целью данной работы является значительное повышение вычислительной эффективности спектрально регуляризованного двухвыборочного теста путем применения техники аппроксимации случайными признаками Фурье при сохранении статистической оптимальности, а также разработка практически применимой адаптивной версии.

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

  1. Вычислительно эффективный и статистически оптимальный тест: Предложен спектрально регуляризованный двухвыборочный тест на основе RFF, который снижает вычислительную сложность с O(n³) до O(nl²+nld), сохраняя при этом минимаксную оптимальность при достаточных условиях
  2. Теоретические гарантии: Установлена теоретическая связь между порядком аппроксимации RFF и статистической оптимальностью, доказана минимаксная оптимальность теста при выполнении определённых условий на количество признаков l
  3. Практическая адаптивная версия: Разработана полностью управляемая данными версия на основе перестановочного теста, включающая адаптивные стратегии выбора параметра регуляризации и ядерной функции
  4. Комплексная экспериментальная верификация: Эффективность метода проверена на синтетических и эталонных наборах данных, продемонстрирован хороший компромисс между вычислительной эффективностью и статистической производительностью

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

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

Даны независимые выборки X₁:N и Y₁:M из распределений P и Q соответственно. Требуется проверить гипотезу H₀: P = Q против H₁: P ≠ Q.

Архитектура основного метода

1. Структура спектральной регуляризации

Для ядерной функции K определяется спектрально регуляризованное расхождение:

ηλ(P,Q) = 4⟨Tgλ(T)u, u⟩_{L²(R)}

где T — интегральный оператор, u = dP/dR - 1 — отклонение отношения правдоподобия, gλ — функция регуляризации.

2. Аппроксимация случайными признаками Фурье

Для ядерных функций вида K(x,y) = ∫φ(x,θ)φ(y,θ)dΞ(θ) строится приближённое ядро:

Kₗ(x,y) = (1/l)∑ᵢ₌₁ˡ φ(x,θᵢ)φ(y,θᵢ)

3. Приближённая тестовая статистика

На основе приближённого ядра Kₗ строится тестовая статистика:

η̂λ,l = (1/[n(n-1)m(m-1)]) ∑ᵢ≠ⱼ ∑ᵢ'≠ⱼ' t(Xᵢ,Xⱼ,Yᵢ',Yⱼ')

где функция t включает квадратный корень регуляризованного оператора ковариации.

Технические инновации

1. Теоретические инновации

  • Условия минимаксной оптимальности: Установлена точная связь между количеством RFF-признаков l и статистической оптимальностью
  • Случаи полиномиального и экспоненциального затухания: Отдельный анализ различных режимов затухания собственных значений интегрального оператора
  • Неасимптотический анализ: Предоставлены гарантии производительности для конечных выборок

2. Алгоритмические инновации

  • Адаптивная регуляризация: Реализация выбора параметра регуляризации, управляемого данными, через объединённое тестирование
  • Адаптация ядерной функции: Расширение на адаптивный выбор нескольких ядерных функций
  • Реализация перестановочного теста: Обеспечение полностью управляемого данными расчёта критических значений

3. Вычислительные инновации

  • Эффективные алгоритмы: Детальный анализ вычислительной сложности и оптимизированная реализация
  • Параллелизация: Естественная параллелизуемость перестановочного теста

Экспериментальная установка

Наборы данных

  1. Синтетические данные:
    • Сдвиг среднего гауссовского распределения: P = N(0,I), Q = N(μ,I)
    • Масштабный сдвиг гауссовского распределения: P = N(0,I), Q = N(0,σ²I)
    • Сдвиг медианы распределения Коши: распределения Коши с различными медианами
  2. Реальные данные:
    • Набор данных MNIST: изображения рукописных цифр 7×7 пикселей, размерность d=49
    • Обнаружение различий в распределениях различных подмножеств цифр

Метрики оценки

  • Статистическая мощность (Power): Вероятность правильного отклонения нулевой гипотезы при альтернативной гипотезе
  • Время вычисления: Сравнение времени выполнения алгоритма
  • Ошибка первого рода: Контроль на уровне α=0.05

Методы сравнения

  • Точный адаптивный тест: Спектрально регуляризованный тест на основе полной матрицы ядра
  • Различное количество RFF-признаков: Сравнение производительности при l ∈ {1,3,5,7,9,15,20}

Детали реализации

  • Функция регуляризации: Showalter regularizer gλ(x) = (1-e^(-x/λ))/x
  • Ядерные функции: гауссово и лапласово ядра с адаптивным выбором полосы пропускания
  • Количество перестановок: B=550-800 для RFF-версии, B'=250-450 для точной версии

Результаты экспериментов

Основные результаты

1. Статистическая производительность

  • Сдвиг среднего гауссовского распределения: При l≥7 мощность близка к точному методу
  • Масштабный сдвиг гауссовского распределения: Хорошая производительность при l≥5
  • Распределение Коши: Требуется больше признаков (l≥10-15) для обработки распределений с тяжёлыми хвостами
  • Данные MNIST: Хорошая производительность на сложных реальных данных при l≥15

2. Вычислительная эффективность

Значительная экономия времени вычисления:

  • Гауссовские эксперименты: RFF-метод требует только 33-44% времени вычисления
  • Масштабный сдвиг: 30-40% затрат времени
  • Эксперименты с распределением Коши: только 5-6% затрат времени
  • MNIST: 5-15% затрат времени

3. Теоретическая верификация

Результаты экспериментов подтверждают теоретические предсказания:

  • Требования к количеству признаков связаны с размерностью данных и сложностью распределения
  • Компромисс между вычислениями и статистикой соответствует теоретическому анализу

Абляционные эксперименты

Путём сравнения различного количества RFF-признаков проверены:

  1. Существование порога количества признаков
  2. Потеря мощности при недостаточном количестве признаков
  3. Достижение оптимального компромисса при надлежащем количестве признаков

Экспериментальные находки

  1. Эффект размерности: Высокомерные данные требуют больше RFF-признаков
  2. Влияние типа распределения: Распределения с тяжёлыми хвостами требуют больше признаков для гарантии производительности
  3. Практические пороги: Теоретически требуемое количество признаков может быть в практике несколько снижено

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

Ядерные методы двухвыборочного тестирования

  • MMD-тесты: Основополагающие работы Gretton et al. (2006, 2012)
  • Минимаксная оптимальность: Недавние достижения Li & Yuan (2024), Schrab et al. (2023)
  • Спектральная регуляризация: Теоретический прорыв Hagrass et al. (2024)

Аппроксимация случайными признаками

  • Теория RFF: Базовая структура Rahimi & Recht (2007)
  • Ускорение MMD: Приложения Zhao & Meng (2015), Choi & Kim (2024)
  • Компромисс вычисления-статистики: Теоретический анализ Sriperumbudur & Sterge (2022)

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

Основные преимущества по сравнению с существующими работами:

  1. Более общие ядерные функции: Не ограничиваются трансляционно-инвариантными ядрами
  2. Более широкая применимость: Поддержка распределений на неевклидовых областях
  3. Более сильные теоретические гарантии: Неасимптотическая минимаксная оптимальность
  4. Более практичные алгоритмы: Полностью управляемая данными реализация

Заключение и обсуждение

Основные выводы

  1. Теоретический вклад: Впервые установлена теория минимаксной оптимальности спектрально регуляризованного двухвыборочного теста при аппроксимации RFF
  2. Алгоритмический вклад: Предоставлен вычислительно эффективный и статистически оптимальный практический алгоритм
  3. Эмпирическая верификация: Эффективность метода проверена на различных типах данных

Ограничения

  1. Выбор количества признаков: Хотя предоставлено теоретическое руководство, практический выбор всё ещё требует эмпирической настройки
  2. Зависимость от ядерной функции: Производительность по-прежнему зависит от выбора ядерной функции
  3. Распределения с тяжёлыми хвостами: Для экстремально тяжёлых хвостов может потребоваться большое количество признаков

Будущие направления

  1. Альтернативные методы аппроксимации: Исследование техник Nyström и других альтернативных аппроксимаций
  2. Дешёвые перестановочные тесты: Интеграция с cheap permutation testing для дальнейшего снижения вычислительных затрат
  3. Автоматическая настройка параметров: Разработка более интеллектуальных стратегий выбора гиперпараметров

Глубокая оценка

Достоинства

  1. Теоретическая строгость: Предоставлен полный неасимптотический теоретический анализ, включая достаточные условия и доказательства минимаксной оптимальности
  2. Практическая применимость: Алгоритм полностью управляется данными и не требует априорного знания
  3. Достаточные эксперименты: Охватывают синтетические и реальные данные, различные типы распределений
  4. Ясное изложение: Технические детали подробны, доказательства полны

Недостатки

  1. Анализ сложности: Хотя асимптотическая сложность снижена, постоянные множители могут быть значительными
  2. Чувствительность к параметрам: Выбор параметра регуляризации и количества признаков остаётся относительно чувствительным
  3. Обработка тяжёлых хвостов: Эффективность обработки распределений с тяжёлыми хвостами требует улучшения

Влияние

  1. Теоретическая ценность: Предоставляет новую теоретическую структуру для компромисса вычисления-статистики в ядерных методах
  2. Практическая ценность: Имеет важное применение в двухвыборочном тестировании крупномасштабных данных
  3. Методологический вклад: Применение RFF-аппроксимации в статистическом тестировании предоставляет новые идеи для связанных исследований

Сценарии применения

  1. Крупномасштабные данные: Вычислительные преимущества явны при больших объёмах выборок
  2. Высокомерные данные: Значительные преимущества по сравнению с традиционными методами в высокомерных условиях
  3. Приложения в реальном времени: Повышение вычислительной эффективности делает возможным тестирование в реальном времени
  4. Непараметрические условия: Применимо в общих случаях, когда форма распределения неизвестна

Библиография

  1. Gretton, A., et al. (2012). A kernel two-sample test. JMLR.
  2. Hagrass, O., et al. (2024). Spectral regularized kernel two-sample tests. Annals of Statistics.
  3. Rahimi, A., & Recht, B. (2007). Random features for large-scale kernel machines. NIPS.
  4. Choi, I., & Kim, I. (2024). Computational-statistical trade-off in kernel two-sample testing with random Fourier features.
  5. Sriperumbudur, B. K., & Sterge, N. (2022). Approximate kernel PCA: Computational versus statistical trade-off. Annals of Statistics.

Общая оценка: Это высокачественная статья по теоретической статистике, которая успешно применяет технику аппроксимации случайными признаками к спектрально регуляризованному двухвыборочному тестированию, значительно повышая вычислительную эффективность при сохранении статистической оптимальности. Теоретический анализ статьи глубок и детален, экспериментальная верификация полна, работа имеет важное значение как для теории статистического обучения, так и для практических приложений.