Теория аппроксимации для 1-липшицевых ResNets

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

• ID статьи: 2505.12003
• Название: Approximation theory for 1-Lipschitz ResNets
• Авторы: Davide Murari (University of Cambridge), Takashi Furuya (Doshisha University, RIKEN AIP), Carola-Bibiane Schönlieb (University of Cambridge)
• Классификация: cs.LG cs.NA math.NA
• Конференция: 39th Conference on Neural Information Processing Systems (NeurIPS 2025)
• Ссылка на статью: https://arxiv.org/abs/2505.12003v2

Аннотация

В данной работе исследуется аппроксимационная способность 1-липшицевых остаточных сетей (ResNets), основанных на явных шагах Эйлера отрицательного градиентного потока. Используя ограниченную теорему Стоуна-Вейерштрасса, авторы доказывают, что при возрастании ширины и глубины эти 1-липшицевы ResNets плотны в множестве скалярных 1-липшицевых функций на любом компактном множестве. Кроме того, доказано, что эти сети могут точно представлять скалярные кусочно-аффинные 1-липшицевы функции. Получен более сильный результат: путём вставки линейных отображений с ограничением нормы между остаточными блоками сохраняется та же плотность при фиксированной ширине скрытого слоя. Поскольку каждый слой следует простому ограничению нормы, полученная модель может быть обучена с использованием стандартных оптимизаторов.

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

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

1-липшицевы нейронные сети играют фундаментальную роль в нескольких важных областях:

• Генеративное моделирование: Дискриминатор в Wasserstein GAN должен быть 1-липшицевым для обеспечения эффективной оценки 1-расстояния Вассерштейна через двойственность Канторовича-Рубинштейна
• Обратные задачи: В алгоритмах Plug-and-Play 1-липшицево ограничение гарантирует сходимость итерационной схемы
• Робастные классификаторы: Контроль константы Липшица сети повышает устойчивость к противодействующим атакам

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

1. Снижение выразительной способности: Ограничение константы Липшица сети обычно снижает её выразительную способность, приводя к значительному падению производительности
2. Недостаток теории: Недостаточное понимание аппроксимационных свойств ограниченных сетей; различные стратегии ограничения могут привести к существенно различной выразительной способности
3. Трудности реализации: Существующие 1-липшицевы ResNets не имеют строгих теоретических гарантий

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

Данная работа направлена на заполнение пробела в теоретическом анализе 1-липшицевых ResNets, обеспечение строгого математического основания для понимания аппроксимационной способности этого класса сетей и предоставление теоретической поддержки для практических приложений.

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

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

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

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

Исследование пространства 1-липшицевых функций на компактном множестве $X \subset \mathbb{R}^d$: $C_1(X,\mathbb{R}) = \{g : X \to \mathbb{R} \mid \|g(y) - g(x)\|_2 \leq \|y - x\|_2, \forall x,y \in X\}$

Цель состоит в построении семейства нейронных сетей, которые плотны в $C_1(X,\mathbb{R})$.

Основные строительные блоки

1-липшицев остаточный слой

На основе явного шага Эйлера отрицательного градиентного потока: $\Phi_{\theta_\ell}(x) = x - \tau_\ell W_\ell^T \sigma(W_\ell x + b_\ell)$

где $\sigma = \text{ReLU}$, с ограничениями: $0 \leq \tau_\ell \leq 2/\|W_\ell\|_2^2$, $\|W_\ell\|_2 \leq 1$

Определение архитектуры сети

Семейство сетей с неограниченной шириной и глубиной: $\mathcal{G}_{d,\sigma}(X,\mathbb{R}) = C_1(X,\mathbb{R}) \cap \{v^T \circ \Phi_{\theta_L} \circ \cdots \circ \Phi_{\theta_1} \circ Q : X \to \mathbb{R}\}$

Семейство сетей с фиксированной шириной: $\tilde{\mathcal{G}}_{d,\sigma,h}(X,\mathbb{R}) = \{v^T \circ \Phi_{\theta_L} \circ A_{L-1} \circ \cdots \circ A_1 \circ \Phi_{\theta_1} \circ Q : X \to \mathbb{R}\}$

где $A_i$ — аффинные отображения с ограничением нормы.

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

1. Двойная стратегия доказательства

• Метод Стоуна-Вейерштрасса: Проверка того, что семейство сетей является решёткой, разделяющей точки, и удовлетворяет условиям ограниченной теоремы Стоуна-Вейерштрасса
• Конструктивный метод: Доказательство того, что сети могут точно представлять все кусочно-аффинные 1-липшицевы функции

2. Инновационное проектирование при фиксированной ширине

Путём введения специальной структуры остаточного слоя: $\tilde{\mathcal{E}}_{h,\sigma} = \left\{\Phi_\theta : \mathbb{R}^{h+3} \to \mathbb{R}^{h+3} \mid \Phi_\theta(x) = \begin{bmatrix} \max\{x_1, x_2\} \\ \min\{x_1, x_2\} \\ x_3 \\ \tilde{\Phi}_\theta(x_{4:}) \end{bmatrix}\right\}$

3. Использование ключевых свойств ReLU

Использование положительной однородности ReLU и следующих тождеств:

• $x = \sigma(x) - \sigma(-x)$
• $\max\{x,y\} = x + \sigma(y-x)$
• $\min\{x,y\} = x - \sigma(x-y)$

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

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

1. Набор данных Two-moon: 4000 точек с добавленным гауссовским шумом со стандартным отклонением 0,1, 20% используется для обучения
2. Набор данных MNIST: Стандартное разбиение на обучение/тестирование, нормализованный ввод

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

• Точность классификации
• Время выполнения ограничений (среднее время на эпоху)

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

• Оптимизатор: Оптимизатор Adam с расписанием обучения косинусного отжига
• Размер пакета: 256
• Ограничение весов: Выполняется методом проективного градиентного спуска с использованием степенного метода для оценки спектральной нормы
• Инициализация: Используется стратегия инициализации динамической изометрии

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

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

Результаты на наборе данных Two-moon

Результаты на наборе данных MNIST (архитектура теоремы 4.1)

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

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

Теоретический анализ

Основные теоремы

Теорема 3.1 (неограниченная ширина и глубина)

Пусть $d \in \mathbb{N}$, $\sigma = \text{ReLU}$, $X \subset \mathbb{R}^d$ компактно, тогда $\mathcal{G}_{d,\sigma}(X,\mathbb{R})$ удовлетворяет универсальному аппроксимационному свойству для $C_1(X,\mathbb{R})$.

Теорема 4.1 (фиксированная ширина)

Пусть $d \in \mathbb{N}$, $\sigma = \text{ReLU}$, $X \subset \mathbb{R}^d$ компактно, тогда $\tilde{\mathcal{G}}_{d,\sigma,d+3}(X,\mathbb{R})$ удовлетворяет универсальному аппроксимационному свойству для $C_1(X,\mathbb{R})$.

Ключевые этапы доказательства

Метод Стоуна-Вейерштрасса

1. Разделение точек: Доказательство того, что семейство сетей может разделить любые две различные точки
2. Свойство решётки: Доказательство того, что семейство сетей замкнуто относительно операций максимума и минимума
3. Плотность: Плотность следует из ограниченной теоремы Стоуна-Вейерштрасса

Конструктивный метод

1. Базовые операции: Доказательство возможности реализации поэлементного максимума и минимума
2. Представление кусочно-аффинных функций: Использование теоремы представления max-min
3. Универсальная аппроксимация: Кусочно-аффинные функции плотны в 1-липшицевых функциях

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

Методы ограничения 1-липшицевых сетей

1. Спектральная нормализация: Контроль спектральной нормы матриц весов
2. Ортогональные матрицы весов: Использование ортогональных преобразований для сохранения липшицева свойства
3. Методы градиентного потока: Стратегии ограничения на основе динамических систем и численного анализа

Теория аппроксимации ограниченных сетей

• Теория сетей с активацией GroupSort от Anil и соавторов
• Исследования сплайн-активаций от Neumayer и соавторов
• Данная работа впервые предоставляет полную теорию для 1-липшицевых ResNets

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

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

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

Ограничения

1. Зависимость от функции активации: Теория сильно зависит от специальных свойств ReLU
2. Сложность реализации: Архитектура с фиксированной шириной требует дополнительных аффинных слоёв, что усложняет реализацию
3. Ограничение на скалярные функции: Основные результаты сосредоточены на скалярных функциях; расширение на векторные функции требует дальнейших исследований

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

1. Другие функции активации: Расширение теоретического анализа на другие функции активации
2. Современные архитектуры: Применение теории к современным архитектурам, таким как Transformers и GNNs
3. Скорости аппроксимации: Исследование конкретных скоростей аппроксимации и анализ сложности
4. Векторные функции: Совершенствование теоретической базы для функций с несколькими выходами

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

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

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

Недостатки

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

Влияние

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

Применимые сценарии

1. Wasserstein GANs: Предоставляет теоретическую поддержку для проектирования дискриминатора
2. Алгоритмы Plug-and-Play: Проектирование денойзера, гарантирующего сходимость
3. Противодействующая робастность: Повышение устойчивости классификатора к противодействующим атакам
4. Решение обратных задач: Приложения в медицинской визуализации, обработке сигналов и других областях

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

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