arXiv · 26.06.2026 ·Машинное обучение

Новые теоретические гарантии для алгоритма Bregman ADMM в невыпуклой оптимизации

Исследователи представили анализ алгоритма Bregman ADMM для решения задач невыпуклой оптимизации с линейными ограничениями. Авторы заменили стандартное предположение о липшицевости градиента на условие относительной гладкости, основанное на сравнении гессианов относительно ядра Брегмана. Это позволяет эффективно оптимизировать сложные полиномиальные целевые функции в матричных и тензорных моделях, где глобальная константа Липшица зачастую отсутствует.

Метод Bregman ADMM широко используется в задачах машинного обучения, где необходимо учитывать специфическую структуру данных. Переход к условию относительной гладкости расширяет применимость алгоритма на классы задач, которые ранее считались трудноразрешимыми из-за отсутствия гладкости в классическом понимании. Работа доказывает сходимость метода к точкам, удовлетворяющим условиям Каруша-Куна-Таккера (KKT) второго порядка, что гарантирует более высокое качество найденных локальных минимумов.

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

Ключевые факты

Предложен новый подход к анализу Bregman ADMM для невыпуклых и нелипшицевых задач.
Условие относительной гладкости заменяет стандартное требование глобальной липшицевости градиента.
Алгоритм обеспечивает гарантии сходимости к точкам KKT второго порядка.
Метод оптимизирован для работы с полиномиальными объектами в матричных и тензорных моделях.

Источник: arXiv

Обсудить с ИИ

Похожие материалы

arXiv · Машинное обучение Новый метод оценки обобщающей способности моделей через PAC-Bayes Исследователи представили новый подход к дерандомизации PAC-Bayes оценок для функций потерь с высокой степенью гладкости. Традиционные методы оценки обобщающей способности моделей часто опираются на вероятностные предсказатели, что затрудняет их прямое применение к детерминированным алгоритмам. Авторы работы предлагают математический аппарат, позволяющий переносить теоретические гарантии с ансамблей типа Gibbs на конкретные детерминированные модели, используя свойства гладкости функции потерь и класса предсказателей. arXiv · Машинное обучение Новые теоретические границы для стохастического субградиентного метода Исследователи представили уточненные теоретические оценки для последнего итерата стохастического субградиентного метода применительно к одномерным выпуклым липшицевым функциям. Авторы доказали, что при фиксированном горизонте итераций $n$ и стандартном шаге $\eta = \Theta(1/\sqrt{n})$ ошибка оптимизации достигает порядка $1/\sqrt{n}$. Это фундаментальное уточнение устраняет необходимость в усреднении итераций для достижения оптимальной сходимости в заданных условиях. arXiv · Машинное обучение Новый метод оптимизации градиента для ускорения обучения нейросетей Исследователи представили метод Stochastic Gradient Optimization with Model-Assisted Sampling, направленный на снижение дисперсии при оценке стохастического градиента. Новый подход позволяет эффективнее балансировать между скоростью сходимости и качеством обобщения моделей, минимизируя шум, неизбежно возникающий при использовании стандартных мини-пакетных методов обучения в глубоком обучении. arXiv · Машинное обучение Новый метод обучения классификаторов в условиях стратегического поведения пользователей Исследователи представили метод обучения нелинейных классификаторов, устойчивых к стратегическим манипуляциям со стороны пользователей. Ранее подобные задачи ограничивались линейными моделями из-за высокой вычислительной сложности. Новый подход позволяет эффективно оптимизировать классификаторы, когда пользователи пытаются изменить свои данные, чтобы повлиять на решение системы, сохраняя при этом точность и предсказуемость модели в динамической среде. arXiv · Исследования и наука Новый подход к байесовскому выводу через анализ локальной плотности распределения Исследователи представили новый математический метод анализа байесовского вывода, фокусирующийся на поведении локальной плотности вероятности вместо традиционных глобальных метрик. Авторы вводят инструменты «индекса массы» и регуляризованной расширенной дивергенции Кульбака-Лейблера, которые позволяют точнее оценивать распределения в задачах, где стандартные методы, такие как ELBO, недостаточно чувствительны к локальным особенностям данных. arXiv · Машинное обучение Математические риски нелинейной агрегации градиентов в обучении моделей Исследователи проанализировали влияние нелинейной агрегации градиентов на сходимость и обобщающую способность моделей. В современных пайплайнах, включающих адаптивность, приватность и робастность, стандартные гарантии выпуклого обучения часто нарушаются из-за потери монотонности оператора обновления. Работа доказывает, что нелинейные методы агрегации могут приводить к нестабильности обучения, что требует пересмотра подходов к оптимизации сложных систем. arXiv · Машинное обучение Ускорение обучения с подкреплением через метод Heavy-Ball Q-Learning Исследователи представили модифицированный алгоритм Heavy-Ball Q-learning, направленный на повышение эффективности обучения с подкреплением. Метод использует коррекцию остаточных весов для стабилизации процесса и достижения более высокой скорости сходимости по сравнению со стандартным Q-learning. Авторы математически доказали теоретические преимущества нового подхода как для табличных методов, так и для сценариев с линейной аппроксимацией функций. arXiv · Исследования и наука Математическая эквивалентность подходов Blackwell Approachability и Gradient Equilibrium Исследователи доказали математическую эквивалентность между Blackwell Approachability и концепцией Gradient Equilibrium (GEQ). Это открытие объединяет теорию игр с онлайн-оптимизацией, позволяя использовать методы минимизации сожаления для решения задач, где ранее требовались специализированные подходы. Результат упрощает анализ алгоритмов в динамических средах, включая задачи онлайн-конформного прогнозирования и поиска стационарных точек в сложных системах. arXiv · Машинное обучение Новый подход к устранению предвзятости в моделях машинного обучения Исследователи представили методологию борьбы с предвзятостью в алгоритмах, которая учитывает пересечение нескольких защищаемых атрибутов, таких как раса и гендер. Традиционные методы часто не справляются с ситуациями, когда дискриминация проявляется только при сочетании нескольких факторов, что приводит к снижению точности моделей для определенных групп населения. Основная проблема заключается в нехватке репрезентативных данных для таких подгрупп и отсутствии четких математических метрик для оценки справедливости. arXiv · Исследования и наука Поиск стационарных точек невыпуклых функций через сравнение значений Исследователи представили алгоритм для поиска стационарных точек невыпуклых функций, работающий исключительно через оракул сравнения. В отличие от классических методов, требующих вычисления градиентов, этот подход определяет, в какой из двух точек значение функции больше. Метод эффективен для дважды дифференцируемых функций с липшицевыми градиентами и гессианами, обеспечивая сходимость к ε-стационарной точке при ограниченном числе запросов.

← Все материалы