Улучшенная сложность выборки для обучения модели диффузии без доступа к эмпирическому минимизатору риска

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

• ID статьи: 2505.18344
• Название: Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Access
• Авторы: Mudit Gaur, Prashant Trivedi, Sasidhar Kunapuli, Amrit Singh Bedi и Vaneet Aggarwal
• Учреждения: Purdue University, University of Central Florida, UC Berkeley
• Классификация: cs.LG, cs.AI, stat.ML
• Дата публикации: arXiv:2505.18344v6 cs.LG 12 Nov 2025
• Ссылка на статью: https://arxiv.org/abs/2505.18344

Аннотация

Модели диффузии демонстрируют передовые результаты в области компьютерного зрения, обработки естественного языка и научных приложений. Несмотря на эмпирический успех, предыдущие теоретические анализы сложности выборки страдают от двух основных проблем: экспоненциальный рост с размерностью входных данных и зависимость от нереалистичных предположений (таких как доступ к точному эмпирическому минимизатору риска). В данной работе предоставляется принципиальный анализ оценки функции градиента логарифма плотности (score function), устанавливающий границу сложности выборки $\tilde{O}(\epsilon^{-4})$. Метод достигает этого путём структурированного разложения ошибки оценки градиента на статистическую ошибку, ошибку аппроксимации и ошибку оптимизации, устраняя экспоненциальную зависимость от параметров нейронной сети в предыдущих анализах. Это первый результат, достигающий границу сложности выборки без предположения о доступе к эмпирическому минимизатору риска для потерь оценки функции градиента.

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

Определение проблемы

Модели диффузии осуществляют выборку из сложных распределений путём обучения обращению процесса добавления шума, при этом ключевым элементом является оценка функции градиента логарифма плотности (score function) $\nabla \log p_t(x)$. Несмотря на превосходную практическую производительность моделей диффузии, теоретическое понимание остаётся ограниченным, особенно в отношении:

1. Проблема сложности выборки: Сколько образцов требуется для обучения высококачественной модели диффузии?
2. Проклятие размерности: Существующие теоретические результаты демонстрируют экспоненциальную зависимость от размерности данных $d$ (например, $\tilde{O}(\epsilon^{-d})$)
3. Нереалистичные предположения: Все предыдущие работы предполагают доступ к эмпирическому минимизатору риска (ERM) для потерь оценки функции градиента, что невозможно реализовать на практике

Значимость исследования

Понимание сложности выборки важно для:

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

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

Как показано в таблице 1, существующие работы имеют следующие проблемы:

*Примечание: Gupta et al. (2024) утверждают $\tilde{O}(\epsilon^{-3})$, но не корректно накапливают ошибки дискретизации временных шагов

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

Данная работа направлена на ответ на центральный вопрос:

Сколько образцов требуется для того, чтобы достаточно выразительная нейронная сеть оценила функцию градиента логарифма плотности без доступа к эмпирическому минимизатору риска, позволяя алгоритму DDPM генерировать высококачественные образцы?

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

1. Первая конечная граница сложности выборки без предположения ERM: Установлена граница сложности выборки $\tilde{O}(\epsilon^{-4})$, не требующая доступа к эмпирическому минимизатору риска и не зависящая от экспоненциальных членов размерности данных или параметров нейронной сети
2. Принципиальная структура разложения ошибок: Предложено систематическое разложение ошибки оценки функции градиента на три компонента:
   • Ошибка аппроксимации (Approximation Error): Ограничения выразительной способности класса функций нейронной сети
   • Статистическая ошибка (Statistical Error): Ошибка, вызванная конечным размером выборки
   • Ошибка оптимизации (Optimization Error): Ошибка, вызванная конечным числом шагов SGD
3. Новые методы технического анализа:
   • Использование условной нормальности для обработки статистической ошибки функций потерь без верхней границы
   • Ограничение ошибки оптимизации через условие Polyak-Łojasiewicz (PL) и рекурсивный анализ
   • Поддержка гарантий сходимости как для постоянной, так и для убывающей скорости обучения
4. Мост между теорией и практикой: Прямое связывание качества обучения функции градиента с полной вариационной дистанцией между генерируемым и целевым распределениями

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

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

Процесс прямой диффузии: Используется процесс Орнштейна-Уленбека (OU): $dx_t = -x_t dt + \sqrt{2}dB_t, \quad x_0 \sim p_0, \quad x \in \mathbb{R}^d$

Замкнутое решение имеет вид: $x_t \sim e^{-t}x_0 + \sqrt{1-e^{-2t}}\epsilon, \quad \epsilon \sim \mathcal{N}(0, I)$

При $t \to \infty$ процесс сходится к стационарному распределению $\mathcal{N}(0, I)$.

Процесс обратной диффузии: Получается путём обращения времени в теории: $dx_{T-t} = (x_{T-t} + 2\nabla \log p_{T-t}(x_{T-t}))dt + \sqrt{2}dB_t$

Дискретизация: Дискретизация по временным точкам $0 < t_0 < t_1 < \cdots < t_K = T$ с использованием оценённой функции градиента $\hat{s}_{t_k}$ для реализации алгоритма DDPM.

Цель: Количественное определение полной вариационной (TV) дистанции между обученной генеративной моделью $\hat{p}_{t_0}$ и истинным распределением данных $p$: $\text{TV}(p_{t_0}, \hat{p}_{t_0}) \leq O(\epsilon)$

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

Предположение 1 (Ограниченный второй момент распределения данных): Распределение данных $p_0$ абсолютно непрерывно, поддержка находится на компактном множестве $\Gamma \subset \mathbb{R}^d$, и $\mathbb{E}[\|x_0\|^2] \leq C_1$.

Предположение 2 (Условие Polyak-Łojasiewicz): Функция потерь $L_k(\theta)$ удовлетворяет условию PL: $\frac{1}{2}\|\nabla L_k(\theta)\|^2 \geq \mu_t(L_k(\theta) - L_k(\theta^*))$

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

Предположение 3 (Ошибка аппроксимации): Существуют параметры нейронной сети $\theta \in \Theta$ такие, что: $\mathbb{E}_{x \sim p_t}[\|s_\theta(x,t) - \nabla \log p_t(x)\|^2] \leq \epsilon_{\text{approx}}$

Предположение 4 (Гладкость и ограниченная дисперсия градиента):

• Функция потерь $\kappa$-гладкая: $\|\nabla L_k(\theta) - \nabla L_k(\theta')\| \leq \kappa\|\theta - \theta'\|$
• Дисперсия оценки градиента ограничена: $\mathbb{E}\|\nabla \hat{L}_k(\theta) - \nabla L_k(\theta)\|^2 \leq \sigma^2$

Структура разложения ошибок

Для временного шага $k$ ошибка оценки функции градиента разлагается как: $\mathbb{E}_{x \sim p_{t_k}}[\|\hat{s}_{t_k}(x,t_k) - \nabla \log p_{t_k}(x)\|^2] \leq 4E_k^{\text{approx}} + 4E_k^{\text{stat}} + 4E_k^{\text{opt}}$

где:

• $\theta_k^a = \arg\min_{\theta \in \Theta} \mathbb{E}_{x \sim p_{t_k}}[\|s_\theta(x,t_k) - \nabla \log p_t(x,t_k)\|^2]$ (теоретически оптимальный)
• $\theta_k^b = \arg\min_{\theta \in \Theta} \frac{1}{n}\sum_{i=1}^n \|s_\theta(x_i,t_k) - \nabla \log p_t(x_i,t_k)\|^2$ (эмпирически оптимальный)
• $\hat{\theta}_k$ = параметры после $n$ шагов SGD (фактически полученные)

Ограничение ошибок

Лемма 1 (Ошибка аппроксимации): Прямо следует из предположения 3: $E_k^{\text{approx}} \leq \epsilon_{\text{approx}}$

Лемма 2 (Статистическая ошибка): Используя условную нормальность и ограниченный второй момент, с вероятностью не менее $1-\delta$: $E_k^{\text{stat}} \leq O\left(W^D \cdot d \cdot \sqrt{\frac{\log(2/\delta)}{n_k}}\right)$

Ключевые методы:

1. Определение усечённой функции градиента для обработки неограниченности
2. Использование сложности Радемахера для ограничения ошибки обобщения
3. Контроль вероятностной массы вне области усечения

Лемма 3 (Ошибка оптимизации): Используя убывающую скорость обучения $\eta_i = \frac{\alpha}{i+\gamma}$ (где $\alpha \mu > 1$, $\gamma > \alpha \kappa$), с вероятностью не менее $1-\delta$: $E_k^{\text{opt}} \leq O\left(W^D \cdot d \cdot \sqrt{\frac{\log(2/\delta)}{n_k}}\right)$

Ключевые методы:

1. Использование свойства квадратичного роста условия PL
2. Рекурсивный анализ ошибки каждого шага SGD
3. Обработка градиентов с тяжёлыми хвостами при обрезании

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

Теорема 1 (Граница полной вариационной дистанции): При выполнении предположений 1-4, если количество образцов удовлетворяет: $n_k = \Omega\left(W^{2D} \cdot d^2 \cdot \log\left(\frac{4K}{\delta}\right) \cdot \epsilon^{-4} \sigma_k^{-4}\right)$

то с вероятностью не менее $1-\delta$: $\text{TV}(p_{t_0}, \hat{p}_{t_0}) \leq O(e^{-T}) + O\left(\frac{1}{\sqrt{K}}\right) + O(\epsilon) + \epsilon_{\text{approx}}$

Устанавливая $T = \Omega(\log(1/\epsilon))$ и $K = \Omega(\epsilon^{-2})$, получаем: $\text{TV}(p_{t_0}, \hat{p}_{t_0}) \leq O(\epsilon) + \epsilon_{\text{approx}}$

Общая сложность выборки: $n_{\text{total}} = \sum_{k=0}^K n_k = \tilde{O}(\epsilon^{-4})$

Схема доказательства

1. Разложение TV дистанции: $\text{TV}(p_{t_0}, \hat{p}_{t_0}) \leq \text{TV}(p_{t_0}, p_{t_0}^{\text{dis}}) + \text{TV}(p_{t_0}^{\text{dis}}, \tilde{p}_{t_0}) + \text{TV}(\tilde{p}_{t_0}, \hat{p}_{t_0})$
2. Накопление ошибок оценки функции градиента: Использование теоремы Гирсанова: $\text{TV}(p_{t_0}^{\text{dis}}, \tilde{p}_{t_0}) \leq \frac{1}{2}\sqrt{\sum_{k=0}^K \mathbb{E}[\|\hat{s}_{t_k} - \nabla \log p_{t_k}\|^2](t_{k+1}-t_k)}$
3. Суммирование ошибок: Через границы трёх типов ошибок установка соответствующего количества образцов обеспечивает: $\sum_{k=0}^K A(k)(t_{k+1}-t_k) \leq \epsilon^2 T$
4. Выбор параметров: Балансировка ошибки дискретизации, ошибки инициализации и ошибки оценки функции градиента

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

Примечание: Данная работа является чисто теоретической и не включает экспериментальную часть. Основной вклад заключается в теоретическом анализе и установлении границ сложности выборки.

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

Основы моделей диффузии

• DDPM (Ho et al., 2020): Основополагающая работа по моделям вероятностной диффузии с удалением шума
• Score-based SDE (Song et al., 2021): Структура стохастических дифференциальных уравнений на основе функции градиента
• Latent Diffusion (Rombach et al., 2022): Эффективная генерация в скрытом пространстве

Исследования сложности итераций

Работы, предполагающие ограниченную оценку функции градиента:

• Li et al. (2024b), Benton et al. (2024): Гарантии сложности итераций для DDPM
• Li & Yan (2024), Huang et al. (2024): Улучшенные скорости сходимости при предположении низкой размерности данных
• Liang et al. (2025a,b): Ускоренные графики удаления шума

Исследования сложности выборки

• Экспоненциальная зависимость от размерности: Chen et al. (2023), Zhang et al. (2024), Wibisono et al. (2024), Oko et al. (2023) с границами $\tilde{O}(\epsilon^{-O(d)})$
• Улучшенные границы, но требующие ERM: Gupta et al. (2024) фактически $\tilde{O}(\epsilon^{-5})$ (требуется совместная граница)

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

1. Отсутствие предположения ERM: Первый результат установления границы сложности выборки в условиях реальной оптимизации
2. Более оптимальная граница: Улучшение с $\tilde{O}(\epsilon^{-5})$ до $\tilde{O}(\epsilon^{-4})$
3. Более слабые предположения: Требуется только ограниченный второй момент, не требуется ограниченная поддержка или sub-Gaussian
4. Полный анализ: Явная обработка трёх типов ошибок: статистической, аппроксимационной и оптимизационной

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

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

1. Сложность выборки: Для достижения точности $\epsilon$ без доступа к ERM требуется $\tilde{O}(\epsilon^{-4})$ образцов
2. Источники ошибок: Систематическое выявление и ограничение вклада трёх типов ошибок
3. Теоретический прогресс: Первая граница сложности выборки для моделей диффузии при реалистичных предположениях оптимизации

Ограничения

1. Константа ошибки аппроксимации: $\epsilon_{\text{approx}}$ рассматривается как константа без анализа её зависимости от размера сети (на практике может потребоваться экспоненциально большая сеть для достижения малой ошибки аппроксимации)
2. Условие PL: Хотя слабее сильной выпуклости, может не выполняться в общей невыпуклой постановке (хотя часто встречается в переопределённых сетях)
3. Время раннего останова: Граница определена для $\text{TV}(p_{t_0}, \hat{p}_{t_0})$ а не $\text{TV}(p_0, \hat{p}_{t_0})$, последнее требует дополнительного предположения sub-Gaussian (теорема 2)
4. Безусловная генерация: Анализ охватывает только безусловные распределения, расширение на условные параметры является направлением будущих исследований
5. Экспериментальная проверка: Как чисто теоретическая работа, отсутствует экспериментальная проверка теоретических предсказаний

Направления будущих исследований

1. Условная генерация: Расширение гарантий на условные модели диффузии (например, classifier-free guidance)
2. Более слабые предположения: Исследование границ при более общих распределениях данных и условиях оптимизации
3. Анализ плотности: Исследование того, является ли граница $\epsilon^{-4}$ плотной, возможные нижние границы
4. Практические алгоритмы: Разработка практических алгоритмов обучения, использующих теоретические идеи
5. Другие архитектуры: Анализ сложности выборки для современных архитектур, таких как Transformer

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

Преимущества

1. Важный теоретический прорыв:
   • Первое устранение предположения ERM, являющегося ключевым ограничением на практике
   • Улучшение известной оптимальной границы (с $\epsilon^{-5}$ до $\epsilon^{-4}$)
   • Отсутствие экспоненциальной зависимости от размерности, применимо к высокомерным параметрам
2. Технические инновации:
   • Анализ статистической ошибки: Умелое использование условной нормальности и методов усечения для обработки неограниченных потерь
   • Анализ ошибки оптимизации: Первый явный анализ влияния конечного числа итераций SGD с использованием условия PL и рекурсивных методов
   • Структура разложения ошибок: Чёткое трёхчленное разложение делает вклад каждого фактора прозрачным
3. Теоретическая строгость:
   • Полное и подробное доказательство (приложение превышает 30 страниц)
   • Явные и относительно мягкие предположения (по сравнению с предыдущими работами)
   • Ясная зависимость констант (хотя потенциально большие)
4. Качество изложения:
   • Чёткая структура, достаточная мотивация
   • Ясное объяснение технических вкладов
   • Всеобъемлющее сравнение с связанными работами (особенно анализ Gupta et al. в приложении A)

Недостатки

1. Разрыв между теорией и практикой:
   • Граница сложности выборки, хотя полиномиальная, может иметь большие скрытые константы ($W^{2D} \cdot d^2$)
   • На практике размеры нейронных сетей намного меньше теоретически требуемых
   • Отсутствует экспериментальная проверка эффективности теоретических предсказаний
2. Практичность предположений:
   • Условие PL: Хотя часто встречается в переопределённых параметрах, сложно проверяется
   • Константа ошибки аппроксимации: Предположение о константности избегает компромисса между ёмкостью сети и качеством аппроксимации
   • Гладкость и ограниченная дисперсия: Могут не строго выполняться при реальном обучении
3. Технические ограничения:
   • Анализ зависит от процесса OU, другие графики добавления шума (например, VP/VE SDE) не охватываются
   • Влияние выбора времени раннего останова $t_0$ недостаточно обсуждается
   • Граница для $p_{t_0}$ вместо $p_0$ требует дополнительных предположений (теорема 2)
4. Справедливость сравнений:
   • Сравнение с Gupta et al. (2024) зависит от переинтерпретации их результатов (приложение A)
   • Отсутствует сравнение с другими методами без предположения ERM (например, Block et al. 2020)
5. Отсутствующий контент:
   • Отсутствует анализ нижних границ, неизвестно, является ли $\epsilon^{-4}$ оптимальным
   • Отсутствуют детали реализации алгоритма или псевдокод (только высокоуровневое описание)
   • Отсутствуют численные эксперименты для проверки теоретических предсказаний

Влияние

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

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

1. Теоретические исследования: Обеспечение теоретической основы для моделей диффузии, согласованного оценивания, генеративных моделей
2. Разработка алгоритмов: Направление стратегий обучения (размер выборки, скорость обучения, ранний останов)
3. Планирование ресурсов: Оценка вычислительных и данных ресурсов, необходимых для достижения целевого качества
4. Проверка предположений: Применение в конкретных параметрах, удовлетворяющих условию PL и другим предположениям

Неприменимо для:

• Практических приложений, требующих плотных констант
• Общей невыпуклой оптимизации, не удовлетворяющей условию PL
• Задач условной генерации (в настоящее время не охватываются)

Глубокий анализ технических особенностей

Инновационная обработка статистической ошибки

Традиционная теория статистического обучения (например, Shalev-Shwartz & Ben-David, 2014) требует ограниченности функции потерь для применения сложности Радемахера. Однако функция градиента $\nabla \log p_t(x) = \frac{x - e^{-t}x_0}{\sigma_t^2}$ неограничена при неограниченном $x$.

Решение:

1. Определение усечённой функции градиента: