|
|
| Строка 1: |
Строка 1: |
| Автор: [[https://algowiki-project.org/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%91%D1%80%D1%8B%D1%81%D0%BA%D0%B8%D0%BD%D0%B0_%D0%9A%D1%80%D0%B8%D1%81%D1%82%D0%B8%D0%BD%D0%B0|Брыскина Кристина]]
| |
|
| |
|
| == Свойства и структура алгоритма ==
| |
| === Общее описание алгоритма ===
| |
| Алгоритм Нестерова с зеркальным шагом, известный как ускоренный зеркальный спуск, был предложен в рамках развития методов выпуклой оптимизации в конце ХХ века, с ключевыми идеями, заложенными Юрием Нестеровым в его работах по ускоренному градиентному спуску 1983 года.
| |
|
| |
| Идея зеркального спуска появилась раньше, в 1970-1980 годах, благодаря работам Аркадия Немировского и Давида Юдина.
| |
|
| |
| Позже произошло их объединение в общую ускоренную версию, например, в работе Кричена, Байена и Бартлетта.
| |
|
| |
| Изначально данный метод использовался для безусловной минимизации гладких выпуклых функций, давая скорость сходимости <math>O(\frac{1}{k^2})</math>, что лучше, чем <math>O(\frac{1}{k})</math> у обычного градиентного спуска. Но с развитием вычислительных методов его применение расширилось на ограниченные выпуклые множества, такие как симплекс в задачах обучения с поддержкой векторов или положительно определенные матрицы в спектральной кластеризации.
| |
| В настоящее время ускоренный зеркальный спуск применяется в машинном обучении, включая стохастическую оптимизацию и распределенные системы. Для разреженных данных добавляют проксимальные операторы, а в итерационных методах - неполные версии с фильтрацией градиентов.
| |
| Алгоритм реализует итерации с инерцией и зеркальной проекцией из дискретизации ОДУ. Он популярен благодаря адаптации и ускорению.
| |
|
| |
| ==== Адаптация к геометрия ====
| |
| Зеркальный спуск позволяет использовать неевклидовы нормы, что экономит вычисления по сравнению с проекциями в евклидовом пространстве.
| |
|
| |
| ==== Ускорение сходимости ====
| |
| Встроенная инерция обеспечивает квадратичную скорость <math>O(\frac{1}{k^2})</math>. Это достигается за счет комбинации градиентного и зеркального шагов.
| |
|
| |
| === Математическое описание алгоритма ===
| |
| Исходные данные: Пусть дано выпуклое замкнутое множество <math>X ⊆ R^n</math>, гладкая выпуклая функция <math>f : X → R</math> с L-липшицевым градиентом ∇f относительно нормы ∥·∥, и сильно выпуклая зеркальная функция <math>ψ : X → R</math> с параметром l > 0;
| |
|
| |
| Расхождение Брегмана для ψ определяется как:
| |
| <math>D_ψ(z, y) = ψ(z) − ψ(y) − ⟨∇ψ(y), z − y⟩.</math>
| |
|
| |
| Задача оптимизации формулируется следующим образом:
| |
| <math>min f(x), где f^∗ = min f(x).</math>
| |
|
| |
| Дискретная версия ускоренного зеркального спуска с постоянным шагом s ≤ 1/L включает следующие итерации:
| |
|
| |
| * На k-й итерации вычисляем параметры и основную точку:
| |
| α<sub>k+1</sub> = (k+2)/2*L
| |
| τ<sub>k</sub> = 2/(k+2)
| |
| x<sub>k+1</sub> = τ<sub>k</sub>z<sub>k</sub> + (1 − τ<sub>k</sub>)y<sub>k</sub>
| |
| * Сделать градиентный шаг:
| |
| y<sub>k+1</sub> = arg min {L/2* ||y − x<sub>k+1</sub>||^2 + ⟨∇f(x<sub>k+1</sub>), y − x<sub>k+1</sub>⟩}
| |
| y∈X
| |
|
| |
| * Сделать зеркальный шаг:
| |
| Пусть V<sub>xk</sub>(z) = D<sub>ψ</sub>(z, x<sub>k</sub>).
| |
| z<sub>k</sub> = arg min {V<sub>xk</sub>(z) + ⟨α<sub>k+1</sub>f(x<sub>k+1</sub>), z − z<sub>k</sub>⟩}
| |
| z∈X
| |
|
| |
| === Вычислительное ядро алгоритма ===
| |
| Вычислительное ядро алгоритма сосредоточено в процедуре адаптивного подбора шага и последующего обновления переменных. Здесь ключевую роль играет внутренний цикл backtracking, который выполняется на каждой итерации для оценки локальной константы Липшица '''L<sub>k</sub>'''''Курсивное начертание''. Ядро состоит из:
| |
|
| |
| # Значение функции и градиента: Многократное вычисление значения функции '''''f(y)''''' и однократное вычисление градиента '''''∇f(x)''''' на итерацию. Это наиболее ресурсоемкая часть.
| |
| # Проверка условия Армихо: Проверка неравенства вида:
| |
| :<math>
| |
| \begin{align}
| |
| f(y_{k+1}) <= f(x_{k+1}) - \frac{1}{2L} * ||f(x_{k+1})||^2,
| |
| \end{align}
| |
| </math>
| |
| гарантирующего достаточное убывание функции.
| |
| # Зеркальный и градиентный шаги: Вычисление проекций для обновления последовательностей '''''y''''' и '''''z''''' с параметром '''''L<sub>k</sup>'''''.
| |
|
| |
| === Макроструктура алгоритма ===
| |
| Алгоритм сохраняет общую итерационную структуру, но каждая итерация является двухуровневой:
| |
|
| |
| # Внешний уровень: Управляет обновлением параметров инерции (<math>\alpha_k, \tau_k</math>) и переходом к следующему шагу оптимизации.
| |
| # Внутренний уровень: Процедура поиска шага. Здесь происходит циклический подбор параметра L<sub>k</sub>. Внутри этого цикла выполняются операции:
| |
| #* Вычисление кандидата на новую переменную y.
| |
| #* Вычисление значения f(y) и проверка условия Армихо.
| |
| #* Увеличение L<sub>k</sub> в случае неудачи. В случае успешной проверки условия - принимается кандидат на новую переменную y.
| |
|
| |
| === Схема реализации последовательного алгоритма ===
| |
| Ниже приведен псевдокод, реализующий ускоренный зеркальный градиентный спуск с адаптивным поиском константы Липшица.
| |
|
| |
| x<sub>k</sub>, y<sub>k</sub>, z<sub>k</sub> = x<sub>0</sub>
| |
| for k in 0...max_iterations {
| |
| α<sub>k+1</sub> = (k+2) / 2L
| |
| τ<sub>k</sub> = 2 / (k+2)
| |
| x<sub>k+1</sub> = τ<sub>k</sub>z<sub>k</sub> + (1 - τ<sub>k</sub>)y<sub>k</sub>
| |
|
| |
| while (True) {
| |
| y<sub>cand</sub> = x<sub>k+1</sub> * ∇f(x<sub>k+1</sub>)
| |
| if f(y<sub>cand</sub>) <= f(x<sub>k+1</sub>) - 1/2L * ||∇f(x<sub>k+1</sub>)||<sup>2</sup>:
| |
| break
| |
| L *= η
| |
| }
| |
|
| |
| y<sub>k+1</sub> = y<sub>cand</sub>
| |
| z<sub>k+1</sub> = z<sub>k</sub> - α * ∇f(x<sub>k+1</sub>)
| |
|
| |
| if f(y<sub>k+1</sub>) <= ε:
| |
| break
| |
| }
| |
|
| |
| === Последовательная сложность алгоритма ===
| |
| Сложность одной итерации алгоритма складывается из:
| |
|
| |
| * Сложность вычисления градиента T<sub>∇f(x)</sub>;
| |
| * Сложность векторных операций, равная O(n);
| |
| Пусть N<sub>back</sub> - среднее число вызовов f(x<sub>k+1</sub>) внутри backtracking (N<sub>call</sub> ≈ 2). Тогда общая сложность на одной итерации:
| |
|
| |
| <math>
| |
| \begin{align}
| |
| T_{iter} = T_{\nabla f(x)} + N_{back} * T_f + O(n).
| |
| \end{align}
| |
| </math>
| |
|
| |
| Общая сложность для достижения точности внешним циклом будет порядка <math>O(\frac{1}{\sqrt{\varepsilon}})</math> .
| |
|
| |
| Тогда общей сложностью всего алгоритма будет:
| |
|
| |
| <math>
| |
| \begin{align}
| |
| N_{call} ≈ O(1)\\
| |
| T_{\nabla f(x)} ≈ O(n^2)\\
| |
| T_f ≈ O(n)\\
| |
| T_{nest} = O(\frac{1}{\sqrt{ε}} * (T_{\nabla f(x)} + N_{call} * T_f + O(n))) ≈ O(\frac{1}{ε} * n^2)
| |
| \end{align}
| |
| </math>
| |
|
| |
| === Информационный граф ===
| |
|
| |
| [[Файл:Информационный граф для зеркального метода Нестерова.png|Информационный граф для зеркального метода Нестерова.png]]
| |
|
| |
| Информационный граф зеркального метода Нестерова описывает структуру зависимостей между операциями внутри одной итерации алгоритма. Данный граф является динамическим, т.е. последовательную конкатенацию базового подграфа, т.к. заранее неизвестно количество итераций алгоритма.
| |
|
| |
| Подграф имеет слоисто-ярусную структуру и состоит из следующих уровней:
| |
| # '''Уровень входа''' - входные данные: y и z с предыдущей итерации;
| |
| # '''Уровень экстраполяции''' - вычисление точки x<sub>k</sub>;
| |
| # '''Уровень вычислений''' - вычисление градиента ∇f(x) и f(x);
| |
| # '''Уровень ветвления''' - вычисление новой точки y вместе с backtracking для L и новой точки z;
| |
| # '''Уровень проверки выхода''' - проверяется, достигли ли мы нужной точности. Если не достигли, то переходим к новой итерации, и выходим, если достигли;
| |
| # '''Уровень выхода''' - завершение алгоритма;
| |
|
| |
| Таким образом, информационный граф алгоритма - это последовательная цепь таких подграфов, длина которой заранее неизвестна и зависит от целевой функции.
| |
|
| |
| === Ресурс параллелизма алгоритма ===
| |
|
| |
| Параллелизм алгоритма имеет двухуровневую структуру, связанную с циклическим профилем последовательной реализации.
| |
| * '''Внешний уровень: Последовательные зависимости'''
| |
| На верхнем уровне алгоритм является строго последовательным. Итерации ''k'' зависимы по данным, т.к. начальное приближение шага определяется результатом предыдущего шага. Данный ярус не имеет параллельного ресурса.
| |
| Внутри каждого шага последовательный подбор константы ''L'' также зависим от предыдущего результата проверки.
| |
| * '''Внутренний уровень: Конечный и массовый параллелизм'''
| |
| Внутри одной итерации раскрывается основной ресурс параллелизма:
| |
| *# '''Конечный параллелизм ветвей''': после вычисления градиента обновление последовательностей ''y'' и ''z'' '''потенциально''' информационно независимы.
| |
| *# '''Массовый координатный параллелизм''': все покомпонентные операции (сложение, вычитание, умножение на скаляр) векторов размерности n независимы. Обработка компонент при вычислении градиента ∇f(x) для многих задач также выполняется независимо.
| |
|
| |
| Высота одного шага: <math>T_{step} ≈ O(\log{n})</math>, где <math>\log{n}</math> - сложность выполнения редукции.
| |
|
| |
| Среднее число попыток backtracking ≈ O(1).
| |
|
| |
| Для успешного завершения алгоритма с заданной точностью <math>ε ≈ O(\frac{1}{\sqrt{ε}})</math>.
| |
|
| |
| Тогда общая сложность выполнения параллельной программы определяется как:
| |
| <math>
| |
| \begin{align}
| |
| T_{nest} = O(\frac{1}{\sqrt{ε}}*\log{n}).
| |
| \end{align}
| |
| </math>
| |
|
| |
| === Входные и выходные данные алгоритма ===
| |
|
| |
| '''Входные данные''': начальное точка-вектор <math>x<sub>0</sub></math>, начальные параметры <math>\alpha_0</math>, <math>\beta_0</math>, точность вычислений ''ε''.
| |
|
| |
| '''Объём входных данных''': ''n + 3''.
| |
|
| |
| '''Выходные данные''': найденная точка-вектор оптиума заданной функции.
| |
|
| |
| '''Объём выходных данных''': ''n''.
| |
|
| |
| === Свойства алгоритма ===
| |
|
| |
| * '''Вычислительная мощность'''
| |
| Алгоритм обладает высокой вычислительной мощностью в том случае, если вычисление значения функции и градиента является трудоемкой. Для простых задач объем пересылаемых данных сопоставим с числом арифметических операций.
| |
|
| |
| * '''Детерминированность'''
| |
| Алгоритм является детерминированным. При фиксации начального приближения и параметров результат работы алгоритма однозначно определён.
| |
|
| |
| * '''Сбалансированность вычислений'''
| |
| Алгоритм неравномерно сбалансирован. Векторных операции и вычисления градиента сбалансированы. Этапы проверки условий и backtracking являются последовательными и слабо загруженными.
| |
|
| |
| * '''Устойчивость'''
| |
| Метод обладает свойством самокоррекции ошибок за счет зеркального спуска и адаптивного подбора шага.
| |
|
| |
| * '''Динамичность'''
| |
| Число backtracking итераций зависит от свойств целевой функции и текущей точки, что делает время выполнения одной итерации заранее неизвестным.
| |
|
| |
| == Программная реализация алгоритма ==
| |
|
| |
| === Особенности реализации последовательного алгоритма ===
| |
|
| |
| Стандартная последовательная реализация метода ускоренного зеркального спуска строится как итерационный процесс, на каждом шаге которого решается задача минимизации линейной модели функции. Основу реализации составляет цикл по итерациям, внутри которого выполняются 3 блока операций:
| |
| # '''Экстраполяция''': вычисление точки <math>x_{k+1}</math> как линейной комбинации точек ''y'' и ''z'';
| |
| # '''Backtracking''': вычисление градиента, значения функции и проверку условия Армихо;
| |
| # '''Обновление переменных''': обновляются шаги ''y'' и ''z''.
| |
|
| |
| Основной выбор реализации касается работы с памятью. Вместо динамического выделения буферов внутри цикла нужно предварительно аллоцировать все рабочие векторы при инициализации. Для задач высокой размерности эффективность повышается за счет слияния циклов.
| |
|
| |
| Ресурс параллелизма позволяет применять ассоциативность векторных операций (разбивать длинные циклы на независимые блоки).
| |
|
| |
| === Возможные способы и особенности параллельной реализации ===
| |
|
| |
| Анализ информационного графа и иерархической структуры зависимостей показывает, что алгоритм допускает эффективное распараллеливание на основе декомпозиции данных (Data Parallelism). Специфика алгоритма не позволяет эффективно использовать конвейерный параллелизм.
| |
|
| |
| '''Межпроцессорный параллелизм'''
| |
|
| |
| Векторы-точки (''x, y, z'') и градиент разбиваются на непрерывные блоки, которые распределяются между MPI-процессами. Каждый процесс отвечает за обновление своей части вектора.
| |
|
| |
| * '''Распределение данных''': используется блочное разбиение. Размер блока определяется как <math>N / P</math> (с учетом остатка).
| |
| * '''Минимизация обменов''': векторные операции, вычисление значения функции и вычисление градиента выполняются локально. Обмен данными осуществляется только для операций редукции (скалярное произведение и норма) через '''MPI_Allreduce''', и, если требуются соседние значения для других операций, то обмен ими (Halo Exchange).
| |
|
| |
| Главным узким местом является глобальная синхронизация в backtracking. Каждая проверка на условие Армихо требует синхронизации всех процессов для вычисления значения ''f(y)''.
| |
|
| |
| === Результаты прогонов ===
| |
|
| |
| Прогоны программы производились на СК Ломоносов-2.
| |
|
| |
| {| class="wikitable"
| |
| |+ Время работы алгоритма на p процессах
| |
| |-
| |
| ! P (кол-во процессов) !! T (время, с)
| |
| |-
| |
| | 1 || 13.914765
| |
| |-
| |
| | 2 || 7.891406
| |
| |-
| |
| | 4 || 4.026877
| |
| |-
| |
| | 6 || 3.038892
| |
| |-
| |
| | 8 || 2.518778
| |
| |-
| |
| | 10 || 2.188900
| |
| |-
| |
| | 12 || 1.991381
| |
| |-
| |
| | 16 || 1.067469
| |
| |}
| |
|
| |
| === Выводы для классов архитектур ===
| |
|
| |
| Для данного алгоритма ключевым фактором производительности является пропускная способность памяти и латентность сети. Для этого больше всего подходят:
| |
| * '''Кластерные системы (MMID)''' - хорошая масштабируется при условии большой локальной памяти.
| |
| * '''Графические ускорители (SIMT/GPU)''' - идеально подходит для массово-параллельных векторных операций.
| |
|
| |
| == Литература ==
| |
| * Нестеров, Ю.Е. (1983). Метод решения задачи выпуклого программирования с темпом сходимости <math>O(\frac{1}{k^2})</math>. Доклады Академии наук СССР, 27(2), 372–376.
| |
| * Немировский А. С., Юдин Д. Б. "Сложность задач и эффективность методов оптимизации."— М.: Наука, 1979
| |
| * Krichene, W., Bayen, A., Bartlett, P. (2015). Accelerated Mirror Descent in Continuous and Discrete Time. NeurIPS.
| |