Участник:Брыскина Кристина//Зеркальный алгоритм Нестерова

Материал из Алговики
Перейти к навигации Перейти к поиску

Автор: [Кристина]

Свойства и структура алгоритма

Общее описание алгоритма

Алгоритм Нестерова с зеркальным шагом, известный как ускоренный зеркальный спуск, был предложен в рамках развития методов выпуклой оптимизации в конце ХХ века, с ключевыми идеями, заложенными Юрием Нестеровым в его работах по ускоренному градиентному спуску 1983 года.

Идея зеркального спуска появилась раньше, в 1970-1980 годах, благодаря работам Аркадия Немировского и Давида Юдина.

Позже произошло их объединение в общую ускоренную версию, например, в работе Кричена, Байена и Бартлетта.

Изначально данный метод использовался для безусловной минимизации гладких выпуклых функций, давая скорость сходимости [math]\displaystyle{ O(\frac{1}{k^2}) }[/math], что лучше, чем [math]\displaystyle{ O(\frac{1}{k}) }[/math] у обычного градиентного спуска. Но с развитием вычислительных методов его применение расширилось на ограниченные выпуклые множества, такие как симплекс в задачах обучения с поддержкой векторов или положительно определенные матрицы в спектральной кластеризации. В настоящее время ускоренный зеркальный спуск применяется в машинном обучении, включая стохастическую оптимизацию и распределенные системы. Для разреженных данных добавляют проксимальные операторы, а в итерационных методах - неполные версии с фильтрацией градиентов. Алгоритм реализует итерации с инерцией и зеркальной проекцией из дискретизации ОДУ. Он популярен благодаря адаптации и ускорению.

Адаптация к геометрия

Зеркальный спуск позволяет использовать неевклидовы нормы, что экономит вычисления по сравнению с проекциями в евклидовом пространстве.

Ускорение сходимости

Встроенная инерция обеспечивает квадратичную скорость [math]\displaystyle{ O(\frac{1}{k^2}) }[/math]. Это достигается за счет комбинации градиентного и зеркального шагов.

Математическое описание алгоритма

Исходные данные: Пусть дано выпуклое замкнутое множество [math]\displaystyle{ X ⊆ R^n }[/math], гладкая выпуклая функция [math]\displaystyle{ f : X → R }[/math] с L-липшицевым градиентом ∇f относительно нормы ∥·∥, и сильно выпуклая зеркальная функция [math]\displaystyle{ ψ : X → R }[/math] с параметром l > 0;

Расхождение Брегмана для ψ определяется как: [math]\displaystyle{ D_ψ(z, y) = ψ(z) − ψ(y) − ⟨∇ψ(y), z − y⟩. }[/math]

Задача оптимизации формулируется следующим образом: [math]\displaystyle{ min f(x), где f^∗ = min f(x). }[/math]

Дискретная версия ускоренного зеркального спуска с постоянным шагом s ≤ 1/L включает следующие итерации:

  • На k-й итерации вычисляем параметры и основную точку:
αk+1 = (k+2)/2*L
τk = 2/(k+2)
xk+1 = τkzk + (1 − τk)yk
  • Сделать градиентный шаг:
 yk+1 = arg min {L/2* ||y − xk+1||^2 + ⟨∇f(xk+1), y − xk+1⟩}
           y∈X
  • Сделать зеркальный шаг:
Пусть Vxk(z) = Dψ(z, xk).
zk = arg min {Vxk(z) + ⟨αk+1f(xk+1), z − zk⟩}
        z∈X

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма сосредоточено в процедуре адаптивного подбора шага и последующего обновления переменных. Здесь ключевую роль играет внутренний цикл backtracking, который выполняется на каждой итерации для оценки локальной константы Липшица LkКурсивное начертание. Ядро состоит из:

  1. Значение функции и градиента: Многократное вычисление значения функции f(y) и однократное вычисление градиента ∇f(x) на итерацию. Это наиболее ресурсоемкая часть.
  2. Проверка условия Армихо: Проверка неравенства вида:
[math]\displaystyle{ \begin{align} f(y_{k+1}) \lt = f(x_{k+1}) - \frac{1}{2L} * ||f(x_{k+1})||^2, \end{align} }[/math]

гарантирующего достаточное убывание функции.

  1. Зеркальный и градиентный шаги: Вычисление проекций для обновления последовательностей y и z с параметром Lk.

Макроструктура алгоритма

Алгоритм сохраняет общую итерационную структуру, но каждая итерация является двухуровневой:

  1. Внешний уровень: Управляет обновлением параметров инерции ([math]\displaystyle{ \alpha_k, \tau_k }[/math]) и переходом к следующему шагу оптимизации.
  2. Внутренний уровень: Процедура поиска шага. Здесь происходит циклический подбор параметра Lk. Внутри этого цикла выполняются операции:
    • Вычисление кандидата на новую переменную y.
    • Вычисление значения f(y) и проверка условия Армихо.
    • Увеличение Lk в случае неудачи. В случае успешной проверки условия - принимается кандидат на новую переменную y.

Схема реализации последовательного алгоритма

Ниже приведен псевдокод, реализующий ускоренный зеркальный градиентный спуск с адаптивным поиском константы Липшица. 

 xk, yk, zk = x0
 for k in 0...max_iterations {
     αk+1 = (k+2) / 2L
     τk = 2 / (k+2)
     xk+1 = τkzk + (1 - τk)yk
     
     while (True) {
         ycand = xk+1 * ∇f(xk+1)
         if f(ycand) <= f(xk+1) - 1/2L * ||∇f(xk+1)||2:
             break
         L *= η
     }

     yk+1 = ycand
     zk+1 = zk - α * ∇f(xk+1)

     if f(yk+1) <= ε:
         break
  }

Последовательная сложность алгоритма

Сложность одной итерации алгоритма складывается из:

  • Сложность вычисления градиента T∇f(x);
  • Сложность векторных операций, равная O(n);

Пусть Nback - среднее число вызовов f(xk+1) внутри backtracking (Ncall ≈ 2). Тогда общая сложность на одной итерации:

[math]\displaystyle{ \begin{align} T_{iter} = T_{\nabla f(x)} + N_{back} * T_f + O(n). \end{align} }[/math]

Общая сложность для достижения точности внешним циклом будет порядка [math]\displaystyle{ O(\frac{1}{\sqrt{\varepsilon}}) }[/math] .

Тогда общей сложностью всего алгоритма будет:

[math]\displaystyle{ \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

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

Подграф имеет слоисто-ярусную структуру и состоит из следующих уровней:

  1. Уровень входа - входные данные: y и z с предыдущей итерации;
  2. Уровень экстраполяции - вычисление точки xk;
  3. Уровень вычислений - вычисление градиента ∇f(x) и f(x);
  4. Уровень ветвления - вычисление новой точки y вместе с backtracking для L и новой точки z;
  5. Уровень проверки выхода - проверяется, достигли ли мы нужной точности. Если не достигли, то переходим к новой итерации, и выходим, если достигли;
  6. Уровень выхода - завершение алгоритма;

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

Ресурс параллелизма алгоритма

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

  • Внешний уровень: Последовательные зависимости
 На верхнем уровне алгоритм является строго последовательным. Итерации k зависимы по данным, т.к. начальное приближение шага определяется результатом предыдущего шага. Данный ярус не имеет параллельного ресурса.
 Внутри каждого шага последовательный подбор константы L также зависим от предыдущего результата проверки.
  • Внутренний уровень: Конечный и массовый параллелизм
 Внутри одной итерации раскрывается основной ресурс параллелизма:
 *# Конечный параллелизм ветвей: после вычисления градиента обновление последовательностей y и z потенциально информационно независимы.
 *# Массовый координатный параллелизм: все покомпонентные операции (сложение, вычитание, умножение на скаляр) векторов размерности n независимы. Обработка компонент при вычислении градиента ∇f(x) для многих задач также выполняется независимо.

Высота одного шага: [math]\displaystyle{ T_{step} ≈ O(\log{n}) }[/math], где [math]\displaystyle{ \log{n} }[/math] - сложность выполнения редукции.

Среднее число попыток backtracking ≈ O(1).

Для успешного завершения алгоритма с заданной точностью [math]\displaystyle{ ε ≈ O(\frac{1}{\sqrt{ε}}) }[/math].

Тогда общая сложность выполнения параллельной программы определяется как: [math]\displaystyle{ \begin{align} T_{nest} = O(\frac{1}{\sqrt{ε}}*\log{n}). \end{align} }[/math]

Входные и выходные данные алгоритма

Входные данные: начальное точка-вектор [math]\displaystyle{ x\lt sub\gt 0\lt /sub\gt }[/math], начальные параметры [math]\displaystyle{ \alpha_0 }[/math], [math]\displaystyle{ \beta_0 }[/math], точность вычислений ε.

Объём входных данных: n + 3.

Выходные данные: найденная точка-вектор оптиума заданной функции.

Объём выходных данных: n.

Свойства алгоритма

  • Вычислительная мощность

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

  • Детерминированность

Алгоритм является детерминированным. При фиксации начального приближения и параметров результат работы алгоритма однозначно определён.

  • Сбалансированность вычислений

Алгоритм неравномерно сбалансирован. Векторных операции и вычисления градиента сбалансированы. Этапы проверки условий и backtracking являются последовательными и слабо загруженными.

  • Устойчивость

Метод обладает свойством самокоррекции ошибок за счет зеркального спуска и адаптивного подбора шага.

  • Динамичность

Число backtracking итераций зависит от свойств целевой функции и текущей точки, что делает время выполнения одной итерации заранее неизвестным.

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

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

  1. Экстраполяция: вычисление точки [math]\displaystyle{ x_{k+1} }[/math] как линейной комбинации точек y и z;
  2. Backtracking: вычисление градиента, значения функции и проверку условия Армихо;
  3. Обновление переменных: обновляются шаги y и z.

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

Ресурс параллелизма позволяет применять ассоциативность векторных операций (разбивать длинные циклы на независимые блоки).

Возможные способы и особенности параллельной реализации

Анализ информационного графа и иерархической структуры зависимостей показывает, что алгоритм допускает эффективное распараллеливание на основе декомпозиции данных (Data Parallelism). Специфика алгоритма не позволяет эффективно использовать конвейерный параллелизм.

Межпроцессорный параллелизм

Векторы-точки (x, y, z) и градиент разбиваются на непрерывные блоки, которые распределяются между MPI-процессами. Каждый процесс отвечает за обновление своей части вектора.

  • Распределение данных: используется блочное разбиение. Размер блока определяется как [math]\displaystyle{ N / P }[/math] (с учетом остатка).
  • Минимизация обменов: векторные операции, вычисление значения функции и вычисление градиента выполняются локально. Обмен данными осуществляется только для операций редукции (скалярное произведение и норма) через MPI_Allreduce, и, если требуются соседние значения для других операций, то обмен ими (Halo Exchange).

Главным узким местом является глобальная синхронизация в backtracking. Каждая проверка на условие Армихо требует синхронизации всех процессов для вычисления значения f(y).

Результаты прогонов

Прогоны программы производились на СК Ломоносов-2.

Время работы алгоритма на 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]\displaystyle{ 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.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Участник:Брыскина_Кристина//Зеркальный_алгоритм_Нестерова&oldid=30375