Алговики - Вклад [ru]

Участница:OvsyannikovaSA/Программная реализация стохастического градиентного спуска

2025-12-09T12:22:10Z

OvsyannikovaSA: /* Масштабируемость реализации */

==Ссылки==
==Локальность данных и вычислений==
==Масштабируемость алгоритма и его реализации==
===Теоретическая масштабируемость алгоритма===
Масштабируемость алгоритма SGD определяется его структурой и необходимостью синхронизации на каждом шаге.

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

На каждом шаге SGD происходят следующие критические операции, которые ограничивают масштабируемость:

1. Вычисление частных градиентов: массово параллельный этап. Потоки работают независимо на своих частях мини-батча.

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

3. Обновление весов: последовательный по времени этап, но параллельный по координатам вектора весов.

Максимальное ускорение <math>S_{max}</math> на одном шаге SGD ограничено законом Амдала, где последовательная часть — это время, затраченное на глобальную редукцию и, в меньшей степени, на векторное обновление. На практике масштабируемость ограничивается эффективностью редукции при росте числа процессоров.

===Масштабируемость реализации===

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

Главная цель состояла в ускорении вычислительно наиболее затратной фазы одного шага SGD: вычисление градиента по мини-батчу.

Сильная масштабируемость SGD хорошая до определенного предела. При увеличении <math>P</math> рабочая нагрузка на один процессор <math>B/P</math> уменьшается, что приводит к сокращению времени вычисления градиента.

Когда <math>P</math> становится близким к <math>B</math>, уменьшение времени вычисления градиента замедляется. При дальнейшем росте <math>P</math> время, затрачиваемое на синхронизацию, начинает доминировать над временем полезных вычислений. Это приводит к падению эффективности и остановке роста ускорения.

<math>S_{max}</math> достигается, когда <math>P \approx B</math> или <math>P \approx d</math> (зависит от того, что больше; <math>d</math> - размерность вектора весов).

Слабая масштабируемость SGD очень хорошая. При одновременном увеличении общего размера данных <math>N</math> и числа процессоров <math>P</math> время вычисления градиента (самая затратная часть) остается примерно постоянным, поскольку нагрузка на один процессор неизменна.

Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.

Реализация выполнена с помощью OpenMP на суперкомпьютере "Ломоносов-2". Число объектов в выборке <math>N=200000</math>, размерность признаков <math>m=20</math>, число эпох <math>E=30</math>, learning rate <math>\alpha=0.005</math>.
[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]

==Динамические характеристики и эффективность реализации алгоритма==
==Результаты прогонов==

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-12-09T12:01:26Z

OvsyannikovaSA: /* Информационный граф */

==Свойства и структура алгоритмов==
===Общее описание алгоритма===
'''Стохастический градиентный спуск''' (Stochastic Gradient Descent, SGD) представляет собой один из базовых и наиболее распространённых алгоритмов оптимизации, применяемых для обучения моделей машинного обучения и нейронных сетей. Он относится к классу итерационных методов минимизации функций.

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

Пусть даны <math>\{x_i, y_i\}_{i=1}^N, x_i \in \mathbb{R}^m</math> - вектор признаков <math>i</math>-го объекта, <math>y_i \in \mathbb{R}</math> - значение целевой переменной; класс моделей <math>a_\omega: \mathbb{R}^m \rightarrow \mathbb{R}</math>; функция потерь <math>f: \mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R}</math>. Задача: найти вектор параметров модели (весов) <math>\omega \in \mathbb{R}^d</math>, т.ч. <math>\omega = argmin_{\omega\in \mathbb{R}^d}\;L(\omega),\;L(\omega)=\sum_{i=1}^N f(a_{\omega}(x_i), y_i)</math>.

Алгоритм '''классического градиентного спуска (batch gradient descent)''' можно сформулировать следующим образом:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
вычислить градиент g <- grad L(ω);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Здесь и далее шаг обучения (learning rate) <math>\alpha</math> является гиперпараметром, т.е. параметром, который не оптимизируется в ходе работы алгоритма и который необходимо выбрать заранее. Начальное приближение <math>\omega_0</math> также необходимо выбрать заранее исходя из некоторых соображений.
Условие достижения сходимости на практике обычно заменяется повторением процедуры некоторое количество раз, после чего можно считать, что алгоритм сошелся в требуемом приближении.
В данном подходе для того, чтобы совершить одно обновление весов, необходимо вычислить функцию потерь для всех элементов выборки. Этот метод может оказаться неподходящим в некоторых случаях, например, при использовании больших датасетов, не помещающихся в памяти, или в случае, когда новые данные поступают в реальном времени.

Модернизацией этого алгоритма является '''стохастический градиентный спуск (stochastic gradient descent)''':
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xi, yi)
вычислить градиент g <- grad f(ω; xi, yi);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Алгоритм отличается от предыдущего тем, что обновление весов происходит после обработки одного объекта выборки. Компромиссом между двумя этими подходами служит '''стохастический градиентный спуск на мини-батчах (mini-batch gradient descent)'''. Для него требуется выбрать размер батча (batch_size, <math>B</math>). Обозначим <math>L(\omega)=\sum_{i=1}^{B} f(a_{\omega}(x_i), y_i)</math>
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск с мини-батчами'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α, размер батча B
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xik, yik), 1<=k<=B
вычислить градиент g <- grad L(ω; (xik, yik), 1<=k<=B);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления.
В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.

Необходимо некоторым способом определить условия, при которых будет считаться, что алгоритм сошелся. Будем считать, что сходимость достигается за <math>E</math> итераций обработки всей выборки (будем называть одну итерацию '''эпохой''').

В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по <math>B</math> объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Таким образом, процедура случайного выбора мини-батча заменяется на линейный проход по всем данным.

===Вычислительное ядро алгоритма===
Основное время работы алгоритма приходится на вычисление градиента, которые повторяются, пока сходимость не будет достигнута.

=== Макроструктура алгоритма ===
Алгоритм стохастического градиентного спуска с мини-батчами представляется повторением следующих макроопераций:

1. Инициализация параметров: задание начального приближения вектора параметров модели <math>w_0</math>. Может быть случайной инициализацией, загрузкой предварительно обученной модели и т.п.

w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)

2. Перемешивание обучающей выборки: получение случайной перестановки обучающей выборки в начале эпохи. Можно выполнять, например, алгоритмом Фишера-Йетса.

Входные данные: <math>D=\{(x_i, y_i)\}_{i=1}^N</math> - обучающая выборка.

Выходные данные: <math>D_{perm}</math> - перемешанная выборка.

D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)

3. Формирование мини-батчей: разбиение переставленной выборки на последовательность мини-батчей.

Входные данные: <math>D_{perm}</math>

Выходные данные: последовательность подмножеств <math>B_k\subset D, \; k=1,..., K, \; \cup_k B_k=D, B_k \cap B_j = \emptyset, k\neq j</math>.

СписокБатчей ← ФормированиеМиниБатчей((X,y)_perm, размер_батча)

4. Вычисление градиента на батче. Может включать вычисление значений модели на батче, матрично-векторные умножения, суммирование по объектам батча.

Входные данные: текущие параметры <math>w</math>, мини-батч <math>B=\{(x_i, y_i)\}_{i\in I_B}</math>

Выходные данные: <math>g_B</math> - градиент по параметрам на этом батче.

g_B ← ВычислениеГрадиентаНаБатче(w, B)

5. Обновление параметров: осуществление одного шага метода по вычисленному градиенту на батче.

Входные данные: текущие параметры <math>w</math>, градиент на батче <math>g_B</math>.

Выходные данные: новые параметры <math>w_{new}=w-\alpha g_B</math>.

w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)

6. Проверка критерия останова: проверка условий завершения итерационного процесса. Может быть проверкой номера эпохи, проверкой изменения функции потерь и т.п.

флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, номер_шага, значение_критерия, история)

На макроуровне алгоритм можно описать так:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:100%;"
|+ '''Макроструктура алгоритма'''
|-
| <syntaxhighlight lang="pseudo">
w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)
номер_эпохи ← 0
повторять
номер_эпохи ← номер_эпохи + 1
D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)
СписокБатчей ← ФормированиеМиниБатчей(D_perm, размер_батча)
Для каждого B из СписокБатчей:
g_B ← ВычислениеГрадиентаНаБатче(w, B)
w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)
флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, значение_критерия, история)
Пока флаг_стоп = ЛОЖЬ
</syntaxhighlight>
|}

=== Схема реализации последовательного алгоритма ===
[[Файл:Sequential SGD with mini-batches scheme.png|Схема последовательной реализации стохастического градиентного спуска с мини-батчами]]

=== Последовательная сложность алгоритма ===
<math>N</math> - размер выборки,

<math>B</math> - размер батча (<math>batch\_size</math>),

<math>C</math> - сложность вычисления производной функции потерь на одном примере,

<math>E</math> - число эпох.

Как уже упоминалось, будем перемешивать выборку случайным образом в начале каждой эпохи. Сложность случайного перемешивания выборки объема <math>N</math> алгоритмом Фишера-Йетса - <math>O(N)</math>. Если отказаться от этого предположения, можно считать, что сложность выбора <math>B</math> случайных элементов - <math>O(B)</math>. Такая оценка будет верна, если в системе реализован произвольный доступ к памяти. Однако для больших выборок, не помещающихся целиком в памяти, произвольный доступ к элементам выборки не будет возможен.

Сложность обработки одного батча - <math>O(B \cdot C)</math>.

Будем считать, что количество батчей <math>N/B</math> - целое число; тогда сложность вычисления градиентов в течение одной эпохи - <math>O(N/B \cdot B \cdot C) = O(N\cdot C)</math>.

Сложность одной эпохи с учетом перемешивания выборки - <math>O(N)+O(N\cdot C)=O(N\cdot C)</math>.

Сложность всего алгоритма с <math>E</math> эпохами - <math>O(E\cdot N\cdot C)</math>.

=== Информационный граф ===
На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.

[[file:Informational_graph_minibatch_SGD.png|center|Информационный граф стохастического градиентного спуска с мини-батчами]]
Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.

===Ресурс параллелизма алгоритма===
Ресурс параллелизма алгоритма стохастического градиентного спуска (SGD) определяется зависимостями данных между его основными шагами: вычислением градиента и обновлением весов.

====Иерархическая Структура Параллелизма====

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

1. Внешний уровень: '''конечный параллелизм'''

Внешний уровень параллелизма определяется последовательностью итераций по эпохам и по батчам:
* цикл по эпохам: итерации по эпохам зависимы, поскольку веса, полученные на одной эпохе, используются на следующей. Этот цикл не имеет параллельного ресурса.
* цикл по батчам (мини-батчам): обновления весов на основе последовательных мини-батчей информационно зависимы. Обновление <math>w_{k+1}</math> зависит от <math>w_k</math> и градиента <math>g_k</math>. Это создает ресурс конечного параллелизма.

2. Внутренний уровень: '''массовый параллелизм'''

Внутренний уровень связан с обработкой данных внутри одного шага SGD (одного мини-батча).

Это ресурс массового параллелизма, который может быть реализован двумя способами:

* Вычисление градиента: вычисление частных градиентов для каждого примера (<math>x_i</math>) в мини-батче полностью независимо: <math>\frac{1}{|B|} \sum_{x_i \in B} \nabla L_i(w)</math>.

Этот этап демонстрирует '''координатный параллелизм''' (независимость итераций цикла по примерам в батче).
* Обновление весов: операция <math>w_{k+1} = w_k - \alpha g_k</math> представляет собой векторные операции (вычитание и скалярное умножение), которые также могут быть распараллелены по координатам вектора весов (<math>w</math>).

====Параллельная сложность и высота ярусно-параллельной формы====

Оценка параллельной сложности алгоритма (высота канонической ярусно-параллельной формы) дается в терминах числа операций умножения/деления и сложения (которые доминируют).

Пусть <math>d</math> — размерность вектора весов, <math>B</math> — размер мини-батча.

Основной вычислительный шаг SGD состоит из трех этапов:

{| class="wikitable sortable"
|+ Параллельная сложность одного шага Стохастического Градиентного Спуска (SGD)
|-
! Этап
! Параллельная сложность (Высота ЯПФ, ''H'')
! Ширина ЯПФ (''W'' - Сбалансированность)
! Описание Ресурса Параллелизма
|-
| '''Вычисление градиентов'''
| <math>O(\log_2 B + 1)</math>
| <math>O(d \times B)</math>
| '''Массовый параллелизм''' (Координатный параллелизм) по примерам в мини-батче. Требуется редукция/суммирование.
|-
| '''Усреднение и масштабирование'''
| <math>O(1)</math>
| <math>O(d)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|-
| '''Обновление весов'''
| <math>O(1)</math>
| <math>O(d)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|}

Таким образом, параллельная сложность (высота) одного шага SGD составляет <math>H = O(\log_2 B)</math>.

====Сбалансированность параллельных шагов (ширина ярусов)====

Ширина ярусов отражает сбалансированность параллельных шагов по числу операций:

* Ширина этапа градиентов: на этапе вычисления градиентов ширина ярусов максимальна, достигает <math>W = O(d \times B)</math>. Этот этап сбалансирован при <math>P</math> процессорах, где <math>P \le B</math>, поскольку каждому процессу можно поручить обработку <math>\lceil B/P \rceil</math> примеров.
* Ширина этапов обновления: на этапах усреднения и обновления весов ширина ярусов составляет <math>W = O(d)</math>. Этот этап также сбалансирован, если <math>P \le d</math>, поскольку операции могут быть распределены по <math>P</math> процессорам.

Алгоритм SGD обладает хорошей сбалансированностью на каждом шаге, что позволяет эффективно использовать большое число процессоров (ядер), особенно когда произведение <math>d \times B</math> велико.

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

Обучающая выборка (<math>D</math>) обычно представляется в виде двух плотных структур данных:

1. Матрица Признаков (<math>X\in\mathbb{R}^{N \times m}</math>), <math>N</math> — общее число обучающих примеров, а <math>m</math> — число признаков.

В задачах машинного обучения <math>N</math> часто значительно больше, чем <math>m</math> (много примеров, но относительно небольшое число признаков), или же <math>m</math> может быть очень большим (например, при использовании One-Hot-Encoding).

В зависимости от задачи, матрица <math>X</math> может быть:
* плотной (dense): каждая ячейка содержит значащее числовое значение.
* разреженной (sparse): если большая часть элементов равна нулю.

2. Вектор целевых значений (<math>y</math>) - вектор размера <math>N \times 1</math> или <math>N \times C</math> (для многоклассовой классификации, где <math>C</math> — число классов).

Обычно плотный, содержит действительные числа (для регрессии) или целочисленные метки/векторы (для классификации).

3. Параметры обучения

* Скорость обучения (<math>\alpha\in\mathbb{R}</math>, learning rate): его значение обычно мало (например, <math>10^{-2}</math> или <math>10^{-3}</math>) и оказывает критическое влияние на сходимость.
* Размер мини-батча (<math>B\in\mathbb{R}</math>, batch size): определяет число примеров, используемых для одного шага. Обычно является степенью двойки (<math>32, 64, 128, \dots</math>).
* Число эпох (<math>E\in\mathbb{N}</math>, epochs): число полных проходов по всему набору данных.

====Выходные Данные====

* Вектор весов модели (<math>w</math>): вектор размера <math>d \times 1</math> (или матрица <math>d \times C</math>, если модель содержит скрытые слои или многоклассовый вывод).

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

* История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен <math>(E \times N) / B</math>. Используется для анализа сходимости и отладки алгоритма.

===Свойства алгоритма===
====Соотношение последовательной и параллельной сложности====

Алгоритм SGD является последовательным по отношению к шагам обновления весов. Однако в рамках одного шага обновления (одного мини-батча) он обладает высоким ресурсом параллелизма.

* Последовательная сложность одного шага SGD: <math>T_{seq} = O(B \cdot d)</math>, где <math>B</math> - размер батча, <math>d</math> - размерность весов.
* Параллельная сложность одного шага SGD (высота ЯПФ): <math>H = O(\log_2 B + 1)</math>.

Теоретический выигрыш от параллельной реализации (ускорение) составляет:

<math>S = \frac{T_{seq}}{H} = \frac{O(B \cdot d)}{O(\log_2 B + 1)}</math>

Теоретически, параллельная реализация обеспечивает значительное ускорение <math>O(B \cdot d)</math>, которое растет линейно с размером батча и размерностью задачи, если есть достаточное количество процессоров <math>P</math>.

* Сложности параллелизации: главная сложность заключается в информационной зависимости между последовательными шагами обновления. Параллельная реализация дает выигрыш только внутри одного шага (градиент и обновление), но не может ускорить последовательность шагов, что является фундаментальным ограничением SGD.
====Вычислительная Мощность====
* Общее число операций (за одну эпоху): <math>O(N \cdot d)</math>, где <math>N</math> — общее число объектов.
* Объем входных данных (матрица <math>X</math>): <math>O(N \cdot d)</math>.
* Объем выходных данных (вектор весов <math>w</math>): <math>O(d)</math>.

<math>W_{comp} = \frac{\text{Число операций}}{\text{Объем входных данных}} = \frac{O(N \cdot d)}{O(N \cdot d + d)}</math>

При больших <math>N</math> <math>N \cdot d</math> доминирует в знаменателе. Таким образом, вычислительная мощность SGD составляет:

<math>W_{comp} \approx O(1)</math>

Вычислительная мощность SGD близка к константе (<math>O(1)</math>). Это означает, что число операций примерно равно объему исходных данных. Это значение относительно невысокое. Это свойство требует, чтобы алгоритм выполнялся "близко" к памяти с данными (например, на том же узле кластера), чтобы минимизировать накладные расходы на перемещение данных.
====Устойчивость Алгоритма====

Алгоритм SGD является '''стохастическим и неустойчивым''' в смысле получения одного и того же результата при каждом запуске.

* Неустойчивость к входным данным: поскольку SGD использует только часть данных (мини-батч) для каждого шага, дисперсия в оценке градиента высокая. Это приводит к флуктуациям в траектории сходимости.
* Ошибка округления: при использовании массового параллелизма (например, при суммировании градиентов от <math>B</math> примеров) на системах с массовым параллелизмом порядок выполнения ассоциативных операций (сложение) может меняться от запуска к запуску. Это приводит к неповторяемости результатов работы параллельных программ, что является серьезной проблемой на практике.

====Сбалансированность вычислительного процесса====

Алгоритм обладает хорошей сбалансированностью с точки зрения распределения нагрузки.

На каждой итерации преобладают арифметические операции при вычислении градиента. Соотношение между арифметическими операциями и обращениями к памяти (чтение/запись) определяется параметром <math>B \cdot d</math>, который обычно достаточно велик, что обеспечивает эффективную работу процессоров.

Распределение нагрузки по <math>P</math> процессам на этапе вычисления градиента достигается просто: каждый процессор обрабатывает <math>\lceil B/P \rceil</math> примеров. Это обеспечивает высокую балансировку нагрузки.

====Детерминированность====
Алгоритм SGD является '''недетерминированным''' по следующим причинам:

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

====Дополнительные свойства====

* Степень исхода вершины: высока для вектора весов <math>w</math>. На каждом шаге <math>w</math> используется для вычисления градиента для всех <math>B</math> примеров. На этапе реализации это требует эффективной рассылки вектора <math>w</math> всем параллельным процессам/потокам, работающим над батчем, и эффективного доступа к нему.
* "Длинные" дуги: возникают в информационном графе SGD при рассылке величин (таких как learning rate <math>\alpha</math> или текущие веса <math>w</math>) по всем итерациям цикла мини-батчей. В случае вектора весов (<math>w</math>), это рассылка всего вектора. Поскольку эта процедура хорошо изучена и оптимизирована на практике, она обычно не вызывает серьезных проблем с размещением данных в иерархии памяти, но требует эффективной коммуникации.

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

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

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

===Выводы для классов архитектур===

==Литература==
Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800

Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-12-09T11:59:45Z

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

==Свойства и структура алгоритмов==
===Общее описание алгоритма===
'''Стохастический градиентный спуск''' (Stochastic Gradient Descent, SGD) представляет собой один из базовых и наиболее распространённых алгоритмов оптимизации, применяемых для обучения моделей машинного обучения и нейронных сетей. Он относится к классу итерационных методов минимизации функций.

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

Пусть даны <math>\{x_i, y_i\}_{i=1}^N, x_i \in \mathbb{R}^m</math> - вектор признаков <math>i</math>-го объекта, <math>y_i \in \mathbb{R}</math> - значение целевой переменной; класс моделей <math>a_\omega: \mathbb{R}^m \rightarrow \mathbb{R}</math>; функция потерь <math>f: \mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R}</math>. Задача: найти вектор параметров модели (весов) <math>\omega \in \mathbb{R}^d</math>, т.ч. <math>\omega = argmin_{\omega\in \mathbb{R}^d}\;L(\omega),\;L(\omega)=\sum_{i=1}^N f(a_{\omega}(x_i), y_i)</math>.

Алгоритм '''классического градиентного спуска (batch gradient descent)''' можно сформулировать следующим образом:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
вычислить градиент g <- grad L(ω);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Здесь и далее шаг обучения (learning rate) <math>\alpha</math> является гиперпараметром, т.е. параметром, который не оптимизируется в ходе работы алгоритма и который необходимо выбрать заранее. Начальное приближение <math>\omega_0</math> также необходимо выбрать заранее исходя из некоторых соображений.
Условие достижения сходимости на практике обычно заменяется повторением процедуры некоторое количество раз, после чего можно считать, что алгоритм сошелся в требуемом приближении.
В данном подходе для того, чтобы совершить одно обновление весов, необходимо вычислить функцию потерь для всех элементов выборки. Этот метод может оказаться неподходящим в некоторых случаях, например, при использовании больших датасетов, не помещающихся в памяти, или в случае, когда новые данные поступают в реальном времени.

Модернизацией этого алгоритма является '''стохастический градиентный спуск (stochastic gradient descent)''':
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xi, yi)
вычислить градиент g <- grad f(ω; xi, yi);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Алгоритм отличается от предыдущего тем, что обновление весов происходит после обработки одного объекта выборки. Компромиссом между двумя этими подходами служит '''стохастический градиентный спуск на мини-батчах (mini-batch gradient descent)'''. Для него требуется выбрать размер батча (batch_size, <math>B</math>). Обозначим <math>L(\omega)=\sum_{i=1}^{B} f(a_{\omega}(x_i), y_i)</math>
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск с мини-батчами'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α, размер батча B
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xik, yik), 1<=k<=B
вычислить градиент g <- grad L(ω; (xik, yik), 1<=k<=B);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления.
В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.

Необходимо некоторым способом определить условия, при которых будет считаться, что алгоритм сошелся. Будем считать, что сходимость достигается за <math>E</math> итераций обработки всей выборки (будем называть одну итерацию '''эпохой''').

В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по <math>B</math> объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Таким образом, процедура случайного выбора мини-батча заменяется на линейный проход по всем данным.

===Вычислительное ядро алгоритма===
Основное время работы алгоритма приходится на вычисление градиента, которые повторяются, пока сходимость не будет достигнута.

=== Макроструктура алгоритма ===
Алгоритм стохастического градиентного спуска с мини-батчами представляется повторением следующих макроопераций:

1. Инициализация параметров: задание начального приближения вектора параметров модели <math>w_0</math>. Может быть случайной инициализацией, загрузкой предварительно обученной модели и т.п.

w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)

2. Перемешивание обучающей выборки: получение случайной перестановки обучающей выборки в начале эпохи. Можно выполнять, например, алгоритмом Фишера-Йетса.

Входные данные: <math>D=\{(x_i, y_i)\}_{i=1}^N</math> - обучающая выборка.

Выходные данные: <math>D_{perm}</math> - перемешанная выборка.

D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)

3. Формирование мини-батчей: разбиение переставленной выборки на последовательность мини-батчей.

Входные данные: <math>D_{perm}</math>

Выходные данные: последовательность подмножеств <math>B_k\subset D, \; k=1,..., K, \; \cup_k B_k=D, B_k \cap B_j = \emptyset, k\neq j</math>.

СписокБатчей ← ФормированиеМиниБатчей((X,y)_perm, размер_батча)

4. Вычисление градиента на батче. Может включать вычисление значений модели на батче, матрично-векторные умножения, суммирование по объектам батча.

Входные данные: текущие параметры <math>w</math>, мини-батч <math>B=\{(x_i, y_i)\}_{i\in I_B}</math>

Выходные данные: <math>g_B</math> - градиент по параметрам на этом батче.

g_B ← ВычислениеГрадиентаНаБатче(w, B)

5. Обновление параметров: осуществление одного шага метода по вычисленному градиенту на батче.

Входные данные: текущие параметры <math>w</math>, градиент на батче <math>g_B</math>.

Выходные данные: новые параметры <math>w_{new}=w-\alpha g_B</math>.

w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)

6. Проверка критерия останова: проверка условий завершения итерационного процесса. Может быть проверкой номера эпохи, проверкой изменения функции потерь и т.п.

флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, номер_шага, значение_критерия, история)

На макроуровне алгоритм можно описать так:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:100%;"
|+ '''Макроструктура алгоритма'''
|-
| <syntaxhighlight lang="pseudo">
w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)
номер_эпохи ← 0
повторять
номер_эпохи ← номер_эпохи + 1
D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)
СписокБатчей ← ФормированиеМиниБатчей(D_perm, размер_батча)
Для каждого B из СписокБатчей:
g_B ← ВычислениеГрадиентаНаБатче(w, B)
w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)
флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, значение_критерия, история)
Пока флаг_стоп = ЛОЖЬ
</syntaxhighlight>
|}

=== Схема реализации последовательного алгоритма ===
[[Файл:Sequential SGD with mini-batches scheme.png|Схема последовательной реализации стохастического градиентного спуска с мини-батчами]]

=== Последовательная сложность алгоритма ===
<math>N</math> - размер выборки,

<math>B</math> - размер батча (<math>batch\_size</math>),

<math>C</math> - сложность вычисления производной функции потерь на одном примере,

<math>E</math> - число эпох.

Как уже упоминалось, будем перемешивать выборку случайным образом в начале каждой эпохи. Сложность случайного перемешивания выборки объема <math>N</math> алгоритмом Фишера-Йетса - <math>O(N)</math>. Если отказаться от этого предположения, можно считать, что сложность выбора <math>B</math> случайных элементов - <math>O(B)</math>. Такая оценка будет верна, если в системе реализован произвольный доступ к памяти. Однако для больших выборок, не помещающихся целиком в памяти, произвольный доступ к элементам выборки не будет возможен.

Сложность обработки одного батча - <math>O(B \cdot C)</math>.

Будем считать, что количество батчей <math>N/B</math> - целое число; тогда сложность вычисления градиентов в течение одной эпохи - <math>O(N/B \cdot B \cdot C) = O(N\cdot C)</math>.

Сложность одной эпохи с учетом перемешивания выборки - <math>O(N)+O(N\cdot C)=O(N\cdot C)</math>.

Сложность всего алгоритма с <math>E</math> эпохами - <math>O(E\cdot N\cdot C)</math>.

=== Информационный граф ===
На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.

[[file:Informational_graph_minibatch_SGD.png|thumb|center|Информационный граф стохастического градиентного спуска с мини-батчами]]
Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.

===Ресурс параллелизма алгоритма===
Ресурс параллелизма алгоритма стохастического градиентного спуска (SGD) определяется зависимостями данных между его основными шагами: вычислением градиента и обновлением весов.

====Иерархическая Структура Параллелизма====

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

1. Внешний уровень: '''конечный параллелизм'''

Внешний уровень параллелизма определяется последовательностью итераций по эпохам и по батчам:
* цикл по эпохам: итерации по эпохам зависимы, поскольку веса, полученные на одной эпохе, используются на следующей. Этот цикл не имеет параллельного ресурса.
* цикл по батчам (мини-батчам): обновления весов на основе последовательных мини-батчей информационно зависимы. Обновление <math>w_{k+1}</math> зависит от <math>w_k</math> и градиента <math>g_k</math>. Это создает ресурс конечного параллелизма.

2. Внутренний уровень: '''массовый параллелизм'''

Внутренний уровень связан с обработкой данных внутри одного шага SGD (одного мини-батча).

Это ресурс массового параллелизма, который может быть реализован двумя способами:

* Вычисление градиента: вычисление частных градиентов для каждого примера (<math>x_i</math>) в мини-батче полностью независимо: <math>\frac{1}{|B|} \sum_{x_i \in B} \nabla L_i(w)</math>.

Этот этап демонстрирует '''координатный параллелизм''' (независимость итераций цикла по примерам в батче).
* Обновление весов: операция <math>w_{k+1} = w_k - \alpha g_k</math> представляет собой векторные операции (вычитание и скалярное умножение), которые также могут быть распараллелены по координатам вектора весов (<math>w</math>).

====Параллельная сложность и высота ярусно-параллельной формы====

Оценка параллельной сложности алгоритма (высота канонической ярусно-параллельной формы) дается в терминах числа операций умножения/деления и сложения (которые доминируют).

Пусть <math>d</math> — размерность вектора весов, <math>B</math> — размер мини-батча.

Основной вычислительный шаг SGD состоит из трех этапов:

{| class="wikitable sortable"
|+ Параллельная сложность одного шага Стохастического Градиентного Спуска (SGD)
|-
! Этап
! Параллельная сложность (Высота ЯПФ, ''H'')
! Ширина ЯПФ (''W'' - Сбалансированность)
! Описание Ресурса Параллелизма
|-
| '''Вычисление градиентов'''
| <math>O(\log_2 B + 1)</math>
| <math>O(d \times B)</math>
| '''Массовый параллелизм''' (Координатный параллелизм) по примерам в мини-батче. Требуется редукция/суммирование.
|-
| '''Усреднение и масштабирование'''
| <math>O(1)</math>
| <math>O(d)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|-
| '''Обновление весов'''
| <math>O(1)</math>
| <math>O(d)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|}

Таким образом, параллельная сложность (высота) одного шага SGD составляет <math>H = O(\log_2 B)</math>.

====Сбалансированность параллельных шагов (ширина ярусов)====

Ширина ярусов отражает сбалансированность параллельных шагов по числу операций:

* Ширина этапа градиентов: на этапе вычисления градиентов ширина ярусов максимальна, достигает <math>W = O(d \times B)</math>. Этот этап сбалансирован при <math>P</math> процессорах, где <math>P \le B</math>, поскольку каждому процессу можно поручить обработку <math>\lceil B/P \rceil</math> примеров.
* Ширина этапов обновления: на этапах усреднения и обновления весов ширина ярусов составляет <math>W = O(d)</math>. Этот этап также сбалансирован, если <math>P \le d</math>, поскольку операции могут быть распределены по <math>P</math> процессорам.

Алгоритм SGD обладает хорошей сбалансированностью на каждом шаге, что позволяет эффективно использовать большое число процессоров (ядер), особенно когда произведение <math>d \times B</math> велико.

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

Обучающая выборка (<math>D</math>) обычно представляется в виде двух плотных структур данных:

1. Матрица Признаков (<math>X\in\mathbb{R}^{N \times m}</math>), <math>N</math> — общее число обучающих примеров, а <math>m</math> — число признаков.

В задачах машинного обучения <math>N</math> часто значительно больше, чем <math>m</math> (много примеров, но относительно небольшое число признаков), или же <math>m</math> может быть очень большим (например, при использовании One-Hot-Encoding).

В зависимости от задачи, матрица <math>X</math> может быть:
* плотной (dense): каждая ячейка содержит значащее числовое значение.
* разреженной (sparse): если большая часть элементов равна нулю.

2. Вектор целевых значений (<math>y</math>) - вектор размера <math>N \times 1</math> или <math>N \times C</math> (для многоклассовой классификации, где <math>C</math> — число классов).

Обычно плотный, содержит действительные числа (для регрессии) или целочисленные метки/векторы (для классификации).

3. Параметры обучения

* Скорость обучения (<math>\alpha\in\mathbb{R}</math>, learning rate): его значение обычно мало (например, <math>10^{-2}</math> или <math>10^{-3}</math>) и оказывает критическое влияние на сходимость.
* Размер мини-батча (<math>B\in\mathbb{R}</math>, batch size): определяет число примеров, используемых для одного шага. Обычно является степенью двойки (<math>32, 64, 128, \dots</math>).
* Число эпох (<math>E\in\mathbb{N}</math>, epochs): число полных проходов по всему набору данных.

====Выходные Данные====

* Вектор весов модели (<math>w</math>): вектор размера <math>d \times 1</math> (или матрица <math>d \times C</math>, если модель содержит скрытые слои или многоклассовый вывод).

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

* История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен <math>(E \times N) / B</math>. Используется для анализа сходимости и отладки алгоритма.

===Свойства алгоритма===
====Соотношение последовательной и параллельной сложности====

Алгоритм SGD является последовательным по отношению к шагам обновления весов. Однако в рамках одного шага обновления (одного мини-батча) он обладает высоким ресурсом параллелизма.

* Последовательная сложность одного шага SGD: <math>T_{seq} = O(B \cdot d)</math>, где <math>B</math> - размер батча, <math>d</math> - размерность весов.
* Параллельная сложность одного шага SGD (высота ЯПФ): <math>H = O(\log_2 B + 1)</math>.

Теоретический выигрыш от параллельной реализации (ускорение) составляет:

<math>S = \frac{T_{seq}}{H} = \frac{O(B \cdot d)}{O(\log_2 B + 1)}</math>

Теоретически, параллельная реализация обеспечивает значительное ускорение <math>O(B \cdot d)</math>, которое растет линейно с размером батча и размерностью задачи, если есть достаточное количество процессоров <math>P</math>.

* Сложности параллелизации: главная сложность заключается в информационной зависимости между последовательными шагами обновления. Параллельная реализация дает выигрыш только внутри одного шага (градиент и обновление), но не может ускорить последовательность шагов, что является фундаментальным ограничением SGD.
====Вычислительная Мощность====
* Общее число операций (за одну эпоху): <math>O(N \cdot d)</math>, где <math>N</math> — общее число объектов.
* Объем входных данных (матрица <math>X</math>): <math>O(N \cdot d)</math>.
* Объем выходных данных (вектор весов <math>w</math>): <math>O(d)</math>.

<math>W_{comp} = \frac{\text{Число операций}}{\text{Объем входных данных}} = \frac{O(N \cdot d)}{O(N \cdot d + d)}</math>

При больших <math>N</math> <math>N \cdot d</math> доминирует в знаменателе. Таким образом, вычислительная мощность SGD составляет:

<math>W_{comp} \approx O(1)</math>

Вычислительная мощность SGD близка к константе (<math>O(1)</math>). Это означает, что число операций примерно равно объему исходных данных. Это значение относительно невысокое. Это свойство требует, чтобы алгоритм выполнялся "близко" к памяти с данными (например, на том же узле кластера), чтобы минимизировать накладные расходы на перемещение данных.
====Устойчивость Алгоритма====

Алгоритм SGD является '''стохастическим и неустойчивым''' в смысле получения одного и того же результата при каждом запуске.

* Неустойчивость к входным данным: поскольку SGD использует только часть данных (мини-батч) для каждого шага, дисперсия в оценке градиента высокая. Это приводит к флуктуациям в траектории сходимости.
* Ошибка округления: при использовании массового параллелизма (например, при суммировании градиентов от <math>B</math> примеров) на системах с массовым параллелизмом порядок выполнения ассоциативных операций (сложение) может меняться от запуска к запуску. Это приводит к неповторяемости результатов работы параллельных программ, что является серьезной проблемой на практике.

====Сбалансированность вычислительного процесса====

Алгоритм обладает хорошей сбалансированностью с точки зрения распределения нагрузки.

На каждой итерации преобладают арифметические операции при вычислении градиента. Соотношение между арифметическими операциями и обращениями к памяти (чтение/запись) определяется параметром <math>B \cdot d</math>, который обычно достаточно велик, что обеспечивает эффективную работу процессоров.

Распределение нагрузки по <math>P</math> процессам на этапе вычисления градиента достигается просто: каждый процессор обрабатывает <math>\lceil B/P \rceil</math> примеров. Это обеспечивает высокую балансировку нагрузки.

====Детерминированность====
Алгоритм SGD является '''недетерминированным''' по следующим причинам:

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

====Дополнительные свойства====

* Степень исхода вершины: высока для вектора весов <math>w</math>. На каждом шаге <math>w</math> используется для вычисления градиента для всех <math>B</math> примеров. На этапе реализации это требует эффективной рассылки вектора <math>w</math> всем параллельным процессам/потокам, работающим над батчем, и эффективного доступа к нему.
* "Длинные" дуги: возникают в информационном графе SGD при рассылке величин (таких как learning rate <math>\alpha</math> или текущие веса <math>w</math>) по всем итерациям цикла мини-батчей. В случае вектора весов (<math>w</math>), это рассылка всего вектора. Поскольку эта процедура хорошо изучена и оптимизирована на практике, она обычно не вызывает серьезных проблем с размещением данных в иерархии памяти, но требует эффективной коммуникации.

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

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

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

===Выводы для классов архитектур===

==Литература==
Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800

Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747

Участница:OvsyannikovaSA/Программная реализация стохастического градиентного спуска

2025-12-09T11:54:08Z

OvsyannikovaSA: /* Масштабируемость реализации */

==Ссылки==
==Локальность данных и вычислений==
==Масштабируемость алгоритма и его реализации==
===Теоретическая масштабируемость алгоритма===
Масштабируемость алгоритма SGD определяется его структурой и необходимостью синхронизации на каждом шаге.

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

На каждом шаге SGD происходят следующие критические операции, которые ограничивают масштабируемость:

1. Вычисление частных градиентов: массово параллельный этап. Потоки работают независимо на своих частях мини-батча.

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

3. Обновление весов: последовательный по времени этап, но параллельный по координатам вектора весов.

Максимальное ускорение <math>S_{max}</math> на одном шаге SGD ограничено законом Амдала, где последовательная часть — это время, затраченное на глобальную редукцию и, в меньшей степени, на векторное обновление. На практике масштабируемость ограничивается эффективностью редукции при росте числа процессоров.

===Масштабируемость реализации===

Сильная масштабируемость SGD хорошая до определенного предела. При увеличении <math>P</math> рабочая нагрузка на один процессор <math>B/P</math> уменьшается, что приводит к сокращению времени вычисления градиента.

Когда <math>P</math> становится близким к <math>B</math>, уменьшение времени вычисления градиента замедляется. При дальнейшем росте <math>P</math> время, затрачиваемое на синхронизацию, начинает доминировать над временем полезных вычислений. Это приводит к падению эффективности и остановке роста ускорения.

<math>S_{max}</math> достигается, когда <math>P \approx B</math> или <math>P \approx d</math> (зависит от того, что больше; <math>d</math> - размерность вектора весов).

Слабая масштабируемость SGD очень хорошая. При одновременном увеличении общего размера данных <math>N</math> и числа процессоров <math>P</math> время вычисления градиента (самая затратная часть) остается примерно постоянным, поскольку нагрузка на один процессор неизменна.

Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.

Реализация выполнена с помощью OpenMP на суперкомпьютере "Ломоносов-2". Число объектов в выборке <math>N=200000</math>, размерность признаков <math>m=20</math>, число эпох <math>E=30</math>, learning rate <math>\alpha=0.005</math>.
[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]

==Динамические характеристики и эффективность реализации алгоритма==
==Результаты прогонов==

Участница:OvsyannikovaSA/Программная реализация стохастического градиентного спуска

2025-12-09T09:06:09Z

OvsyannikovaSA: /* Масштабируемость реализации */

==Ссылки==
==Локальность данных и вычислений==
==Масштабируемость алгоритма и его реализации==
===Теоретическая масштабируемость алгоритма===
Масштабируемость алгоритма SGD определяется его структурой и необходимостью синхронизации на каждом шаге.

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

На каждом шаге SGD происходят следующие критические операции, которые ограничивают масштабируемость:

1. Вычисление частных градиентов: массово параллельный этап. Потоки работают независимо на своих частях мини-батча.

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

3. Обновление весов: последовательный по времени этап, но параллельный по координатам вектора весов.

Максимальное ускорение <math>S_{max}</math> на одном шаге SGD ограничено законом Амдала, где последовательная часть — это время, затраченное на глобальную редукцию и, в меньшей степени, на векторное обновление. На практике масштабируемость ограничивается эффективностью редукции при росте числа процессоров.

===Масштабируемость реализации===

Сильная масштабируемость SGD хорошая до определенного предела. При увеличении <math>P</math> рабочая нагрузка на один процессор <math>B/P</math> уменьшается, что приводит к сокращению времени вычисления градиента.

Когда <math>P</math> становится близким к <math>B</math>, уменьшение времени вычисления градиента замедляется. При дальнейшем росте <math>P</math> время, затрачиваемое на синхронизацию, начинает доминировать над временем полезных вычислений. Это приводит к падению эффективности и остановке роста ускорения.

<math>S_{max}</math> достигается, когда <math>P \approx B</math> или <math>P \approx d</math> (зависит от того, что больше; <math>d</math> - размерность вектора весов).

Слабая масштабируемость SGD очень хорошая. При одновременном увеличении общего размера данных <math>N</math> и числа процессоров <math>P</math> время вычисления градиента (самая затратная часть) остается примерно постоянным, поскольку нагрузка на один процессор неизменна.

Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.

Реализация выполнена с помощью OpenMP на суперкомпьютере "Ломоносов-2".
[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]

==Динамические характеристики и эффективность реализации алгоритма==
==Результаты прогонов==

Участница:OvsyannikovaSA/Программная реализация стохастического градиентного спуска

2025-12-09T09:04:50Z

OvsyannikovaSA: добавлено: масштабируемость алгоритма и его реализации

==Ссылки==
==Локальность данных и вычислений==
==Масштабируемость алгоритма и его реализации==
===Теоретическая масштабируемость алгоритма===
Масштабируемость алгоритма SGD определяется его структурой и необходимостью синхронизации на каждом шаге.

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

На каждом шаге SGD происходят следующие критические операции, которые ограничивают масштабируемость:

1. Вычисление частных градиентов: массово параллельный этап. Потоки работают независимо на своих частях мини-батча.

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

3. Обновление весов: последовательный по времени этап, но параллельный по координатам вектора весов.

Максимальное ускорение <math>S_{max}</math> на одном шаге SGD ограничено законом Амдала, где последовательная часть — это время, затраченное на глобальную редукцию и, в меньшей степени, на векторное обновление. На практике масштабируемость ограничивается эффективностью редукции при росте числа процессоров.

===Масштабируемость реализации===

Сильная масштабируемость SGD хорошая до определенного предела. При увеличении <math>P</math> рабочая нагрузка на один процессор <math>B/P</math> уменьшается, что приводит к сокращению времени вычисления градиента.

Когда <math>P</math> становится близким к <math>B</math>, уменьшение времени вычисления градиента замедляется. При дальнейшем росте <math>P</math> время, затрачиваемое на синхронизацию, начинает доминировать над временем полезных вычислений. Это приводит к падению эффективности и остановке роста ускорения.

<math>S_{max}</math> достигается, когда <math>P \approx B</math> или <math>P \approx d</math> (зависит от того, что больше; <math>d</math> - размерность вектора весов).

Слабая масштабируемость SGD очень хорошая. При одновременном увеличении общего размера данных <math>N</math> и числа процессоров <math>P</math> время вычисления градиента (самая затратная часть) остается примерно постоянным, поскольку нагрузка на один процессор неизменна.

Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.

[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]

==Динамические характеристики и эффективность реализации алгоритма==
==Результаты прогонов==

Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png

2025-12-09T09:02:20Z

OvsyannikovaSA:

Ускорение параллельного SGD в зависимости от числа потоков и размера батча

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-12-09T08:33:29Z

OvsyannikovaSA: исправления неточностей

==Свойства и структура алгоритмов==
===Общее описание алгоритма===
'''Стохастический градиентный спуск''' (Stochastic Gradient Descent, SGD) представляет собой один из базовых и наиболее распространённых алгоритмов оптимизации, применяемых для обучения моделей машинного обучения и нейронных сетей. Он относится к классу итерационных методов минимизации функций.

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

Пусть даны <math>\{x_i, y_i\}_{i=1}^N, x_i \in \mathbb{R}^m</math> - вектор признаков <math>i</math>-го объекта, <math>y_i \in \mathbb{R}</math> - значение целевой переменной; класс моделей <math>a_\omega: \mathbb{R}^m \rightarrow \mathbb{R}</math>; функция потерь <math>f: \mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R}</math>. Задача: найти вектор параметров модели (весов) <math>\omega \in \mathbb{R}^d</math>, т.ч. <math>\omega = argmin_{\omega\in \mathbb{R}^d}\;L(\omega),\;L(\omega)=\sum_{i=1}^N f(a_{\omega}(x_i), y_i)</math>.

Алгоритм '''классического градиентного спуска (batch gradient descent)''' можно сформулировать следующим образом:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
вычислить градиент g <- grad L(ω);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Здесь и далее шаг обучения (learning rate) <math>\alpha</math> является гиперпараметром, т.е. параметром, который не оптимизируется в ходе работы алгоритма и который необходимо выбрать заранее. Начальное приближение <math>\omega_0</math> также необходимо выбрать заранее исходя из некоторых соображений.
Условие достижения сходимости на практике обычно заменяется повторением процедуры некоторое количество раз, после чего можно считать, что алгоритм сошелся в требуемом приближении.
В данном подходе для того, чтобы совершить одно обновление весов, необходимо вычислить функцию потерь для всех элементов выборки. Этот метод может оказаться неподходящим в некоторых случаях, например, при использовании больших датасетов, не помещающихся в памяти, или в случае, когда новые данные поступают в реальном времени.

Модернизацией этого алгоритма является '''стохастический градиентный спуск (stochastic gradient descent)''':
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xi, yi)
вычислить градиент g <- grad f(ω; xi, yi);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Алгоритм отличается от предыдущего тем, что обновление весов происходит после обработки одного объекта выборки. Компромиссом между двумя этими подходами служит '''стохастический градиентный спуск на мини-батчах (mini-batch gradient descent)'''. Для него требуется выбрать размер батча (batch_size, <math>B</math>). Обозначим <math>L(\omega)=\sum_{i=1}^{B} f(a_{\omega}(x_i), y_i)</math>
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск с мини-батчами'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α, размер батча B
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xik, yik), 1<=k<=B
вычислить градиент g <- grad L(ω; (xik, yik), 1<=k<=B);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления.
В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.

Необходимо некоторым способом определить условия, при которых будет считаться, что алгоритм сошелся. Будем считать, что сходимость достигается за <math>E</math> итераций обработки всей выборки (будем называть одну итерацию '''эпохой''').

В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по <math>B</math> объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Таким образом, процедура случайного выбора мини-батча заменяется на линейный проход по всем данным.

===Вычислительное ядро алгоритма===
Основное время работы алгоритма приходится на вычисление градиента, которые повторяются, пока сходимость не будет достигнута.

=== Макроструктура алгоритма ===
Алгоритм стохастического градиентного спуска с мини-батчами представляется повторением следующих макроопераций:

1. Инициализация параметров: задание начального приближения вектора параметров модели <math>w_0</math>. Может быть случайной инициализацией, загрузкой предварительно обученной модели и т.п.

w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)

2. Перемешивание обучающей выборки: получение случайной перестановки обучающей выборки в начале эпохи. Можно выполнять, например, алгоритмом Фишера-Йетса.

Входные данные: <math>D=\{(x_i, y_i)\}_{i=1}^N</math> - обучающая выборка.

Выходные данные: <math>D_{perm}</math> - перемешанная выборка.

D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)

3. Формирование мини-батчей: разбиение переставленной выборки на последовательность мини-батчей.

Входные данные: <math>D_{perm}</math>

Выходные данные: последовательность подмножеств <math>B_k\subset D, \; k=1,..., K, \; \cup_k B_k=D, B_k \cap B_j = \emptyset, k\neq j</math>.

СписокБатчей ← ФормированиеМиниБатчей((X,y)_perm, размер_батча)

4. Вычисление градиента на батче. Может включать вычисление значений модели на батче, матрично-векторные умножения, суммирование по объектам батча.

Входные данные: текущие параметры <math>w</math>, мини-батч <math>B=\{(x_i, y_i)\}_{i\in I_B}</math>

Выходные данные: <math>g_B</math> - градиент по параметрам на этом батче.

g_B ← ВычислениеГрадиентаНаБатче(w, B)

5. Обновление параметров: осуществление одного шага метода по вычисленному градиенту на батче.

Входные данные: текущие параметры <math>w</math>, градиент на батче <math>g_B</math>.

Выходные данные: новые параметры <math>w_{new}=w-\alpha g_B</math>.

w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)

6. Проверка критерия останова: проверка условий завершения итерационного процесса. Может быть проверкой номера эпохи, проверкой изменения функции потерь и т.п.

флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, номер_шага, значение_критерия, история)

На макроуровне алгоритм можно описать так:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:100%;"
|+ '''Макроструктура алгоритма'''
|-
| <syntaxhighlight lang="pseudo">
w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)
номер_эпохи ← 0
повторять
номер_эпохи ← номер_эпохи + 1
D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)
СписокБатчей ← ФормированиеМиниБатчей(D_perm, размер_батча)
Для каждого B из СписокБатчей:
g_B ← ВычислениеГрадиентаНаБатче(w, B)
w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)
флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, значение_критерия, история)
Пока флаг_стоп = ЛОЖЬ
</syntaxhighlight>
|}

=== Схема реализации последовательного алгоритма ===
[[Файл:Sequential SGD with mini-batches scheme.png|мини|Схема последовательной реализации стохастического градиентного спуска с мини-батчами]]

=== Последовательная сложность алгоритма ===
<math>N</math> - размер выборки,

<math>B</math> - размер батча (<math>batch\_size</math>),

<math>C</math> - сложность вычисления производной функции потерь на одном примере,

<math>E</math> - число эпох.

Как уже упоминалось, будем перемешивать выборку случайным образом в начале каждой эпохи. Сложность случайного перемешивания выборки объема <math>N</math> алгоритмом Фишера-Йетса - <math>O(N)</math>. Если отказаться от этого предположения, можно считать, что сложность выбора <math>B</math> случайных элементов - <math>O(B)</math>. Такая оценка будет верна, если в системе реализован произвольный доступ к памяти. Однако для больших выборок, не помещающихся целиком в памяти, произвольный доступ к элементам выборки не будет возможен.

Сложность обработки одного батча - <math>O(B \cdot C)</math>.

Будем считать, что количество батчей <math>N/B</math> - целое число; тогда сложность вычисления градиентов в течение одной эпохи - <math>O(N/B \cdot B \cdot C) = O(N\cdot C)</math>.

Сложность одной эпохи с учетом перемешивания выборки - <math>O(N)+O(N\cdot C)=O(N\cdot C)</math>.

Сложность всего алгоритма с <math>E</math> эпохами - <math>O(E\cdot N\cdot C)</math>.

=== Информационный граф ===
На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.

[[file:Informational_graph_minibatch_SGD.png|thumb|center|Информационный граф стохастического градиентного спуска с мини-батчами]]
Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.

===Ресурс параллелизма алгоритма===
Ресурс параллелизма алгоритма стохастического градиентного спуска (SGD) определяется зависимостями данных между его основными шагами: вычислением градиента и обновлением весов.

====Иерархическая Структура Параллелизма====

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

1. Внешний уровень: '''конечный параллелизм'''

Внешний уровень параллелизма определяется последовательностью итераций по эпохам и по батчам:
* цикл по эпохам: итерации по эпохам зависимы, поскольку веса, полученные на одной эпохе, используются на следующей. Этот цикл не имеет параллельного ресурса.
* цикл по батчам (мини-батчам): обновления весов на основе последовательных мини-батчей информационно зависимы. Обновление <math>w_{k+1}</math> зависит от <math>w_k</math> и градиента <math>g_k</math>. Это создает ресурс конечного параллелизма.

2. Внутренний уровень: '''массовый параллелизм'''

Внутренний уровень связан с обработкой данных внутри одного шага SGD (одного мини-батча).

Это ресурс массового параллелизма, который может быть реализован двумя способами:

* Вычисление градиента: вычисление частных градиентов для каждого примера (<math>x_i</math>) в мини-батче полностью независимо: <math>\frac{1}{|B|} \sum_{x_i \in B} \nabla L_i(w)</math>.

Этот этап демонстрирует '''координатный параллелизм''' (независимость итераций цикла по примерам в батче).
* Обновление весов: операция <math>w_{k+1} = w_k - \alpha g_k</math> представляет собой векторные операции (вычитание и скалярное умножение), которые также могут быть распараллелены по координатам вектора весов (<math>w</math>).

====Параллельная сложность и высота ярусно-параллельной формы====

Оценка параллельной сложности алгоритма (высота канонической ярусно-параллельной формы) дается в терминах числа операций умножения/деления и сложения (которые доминируют).

Пусть <math>d</math> — размерность вектора весов, <math>B</math> — размер мини-батча.

Основной вычислительный шаг SGD состоит из трех этапов:

{| class="wikitable sortable"
|+ Параллельная сложность одного шага Стохастического Градиентного Спуска (SGD)
|-
! Этап
! Параллельная сложность (Высота ЯПФ, ''H'')
! Ширина ЯПФ (''W'' - Сбалансированность)
! Описание Ресурса Параллелизма
|-
| '''Вычисление градиентов'''
| <math>O(\log_2 B + 1)</math>
| <math>O(d \times B)</math>
| '''Массовый параллелизм''' (Координатный параллелизм) по примерам в мини-батче. Требуется редукция/суммирование.
|-
| '''Усреднение и масштабирование'''
| <math>O(1)</math>
| <math>O(d)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|-
| '''Обновление весов'''
| <math>O(1)</math>
| <math>O(d)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|}

Таким образом, параллельная сложность (высота) одного шага SGD составляет <math>H = O(\log_2 B)</math>.

====Сбалансированность параллельных шагов (ширина ярусов)====

Ширина ярусов отражает сбалансированность параллельных шагов по числу операций:

* Ширина этапа градиентов: на этапе вычисления градиентов ширина ярусов максимальна, достигает <math>W = O(d \times B)</math>. Этот этап сбалансирован при <math>P</math> процессорах, где <math>P \le B</math>, поскольку каждому процессу можно поручить обработку <math>\lceil B/P \rceil</math> примеров.
* Ширина этапов обновления: на этапах усреднения и обновления весов ширина ярусов составляет <math>W = O(d)</math>. Этот этап также сбалансирован, если <math>P \le d</math>, поскольку операции могут быть распределены по <math>P</math> процессорам.

Алгоритм SGD обладает хорошей сбалансированностью на каждом шаге, что позволяет эффективно использовать большое число процессоров (ядер), особенно когда произведение <math>d \times B</math> велико.

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

Обучающая выборка (<math>D</math>) обычно представляется в виде двух плотных структур данных:

1. Матрица Признаков (<math>X\in\mathbb{R}^{N \times m}</math>), <math>N</math> — общее число обучающих примеров, а <math>m</math> — число признаков.

В задачах машинного обучения <math>N</math> часто значительно больше, чем <math>m</math> (много примеров, но относительно небольшое число признаков), или же <math>m</math> может быть очень большим (например, при использовании One-Hot-Encoding).

В зависимости от задачи, матрица <math>X</math> может быть:
* плотной (dense): каждая ячейка содержит значащее числовое значение.
* разреженной (sparse): если большая часть элементов равна нулю.

2. Вектор целевых значений (<math>y</math>) - вектор размера <math>N \times 1</math> или <math>N \times C</math> (для многоклассовой классификации, где <math>C</math> — число классов).

Обычно плотный, содержит действительные числа (для регрессии) или целочисленные метки/векторы (для классификации).

3. Параметры обучения

* Скорость обучения (<math>\alpha\in\mathbb{R}</math>, learning rate): его значение обычно мало (например, <math>10^{-2}</math> или <math>10^{-3}</math>) и оказывает критическое влияние на сходимость.
* Размер мини-батча (<math>B\in\mathbb{R}</math>, batch size): определяет число примеров, используемых для одного шага. Обычно является степенью двойки (<math>32, 64, 128, \dots</math>).
* Число эпох (<math>E\in\mathbb{N}</math>, epochs): число полных проходов по всему набору данных.

====Выходные Данные====

* Вектор весов модели (<math>w</math>): вектор размера <math>d \times 1</math> (или матрица <math>d \times C</math>, если модель содержит скрытые слои или многоклассовый вывод).

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

* История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен <math>(E \times N) / B</math>. Используется для анализа сходимости и отладки алгоритма.

===Свойства алгоритма===
====Соотношение последовательной и параллельной сложности====

Алгоритм SGD является последовательным по отношению к шагам обновления весов. Однако в рамках одного шага обновления (одного мини-батча) он обладает высоким ресурсом параллелизма.

* Последовательная сложность одного шага SGD: <math>T_{seq} = O(B \cdot d)</math>, где <math>B</math> - размер батча, <math>d</math> - размерность весов.
* Параллельная сложность одного шага SGD (высота ЯПФ): <math>H = O(\log_2 B + 1)</math>.

Теоретический выигрыш от параллельной реализации (ускорение) составляет:

<math>S = \frac{T_{seq}}{H} = \frac{O(B \cdot d)}{O(\log_2 B + 1)}</math>

Теоретически, параллельная реализация обеспечивает значительное ускорение <math>O(B \cdot d)</math>, которое растет линейно с размером батча и размерностью задачи, если есть достаточное количество процессоров <math>P</math>.

* Сложности параллелизации: главная сложность заключается в информационной зависимости между последовательными шагами обновления. Параллельная реализация дает выигрыш только внутри одного шага (градиент и обновление), но не может ускорить последовательность шагов, что является фундаментальным ограничением SGD.
====Вычислительная Мощность====
* Общее число операций (за одну эпоху): <math>O(N \cdot d)</math>, где <math>N</math> — общее число объектов.
* Объем входных данных (матрица <math>X</math>): <math>O(N \cdot d)</math>.
* Объем выходных данных (вектор весов <math>w</math>): <math>O(d)</math>.

<math>W_{comp} = \frac{\text{Число операций}}{\text{Объем входных данных}} = \frac{O(N \cdot d)}{O(N \cdot d + d)}</math>

При больших <math>N</math> <math>N \cdot d</math> доминирует в знаменателе. Таким образом, вычислительная мощность SGD составляет:

<math>W_{comp} \approx O(1)</math>

Вычислительная мощность SGD близка к константе (<math>O(1)</math>). Это означает, что число операций примерно равно объему исходных данных. Это значение относительно невысокое. Это свойство требует, чтобы алгоритм выполнялся "близко" к памяти с данными (например, на том же узле кластера), чтобы минимизировать накладные расходы на перемещение данных.
====Устойчивость Алгоритма====

Алгоритм SGD является '''стохастическим и неустойчивым''' в смысле получения одного и того же результата при каждом запуске.

* Неустойчивость к входным данным: поскольку SGD использует только часть данных (мини-батч) для каждого шага, дисперсия в оценке градиента высокая. Это приводит к флуктуациям в траектории сходимости.
* Ошибка округления: при использовании массового параллелизма (например, при суммировании градиентов от <math>B</math> примеров) на системах с массовым параллелизмом порядок выполнения ассоциативных операций (сложение) может меняться от запуска к запуску. Это приводит к неповторяемости результатов работы параллельных программ, что является серьезной проблемой на практике.

====Сбалансированность вычислительного процесса====

Алгоритм обладает хорошей сбалансированностью с точки зрения распределения нагрузки.

На каждой итерации преобладают арифметические операции при вычислении градиента. Соотношение между арифметическими операциями и обращениями к памяти (чтение/запись) определяется параметром <math>B \cdot d</math>, который обычно достаточно велик, что обеспечивает эффективную работу процессоров.

Распределение нагрузки по <math>P</math> процессам на этапе вычисления градиента достигается просто: каждый процессор обрабатывает <math>\lceil B/P \rceil</math> примеров. Это обеспечивает высокую балансировку нагрузки.

====Детерминированность====
Алгоритм SGD является '''недетерминированным''' по следующим причинам:

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

====Дополнительные свойства====

* Степень исхода вершины: высока для вектора весов <math>w</math>. На каждом шаге <math>w</math> используется для вычисления градиента для всех <math>B</math> примеров. На этапе реализации это требует эффективной рассылки вектора <math>w</math> всем параллельным процессам/потокам, работающим над батчем, и эффективного доступа к нему.
* "Длинные" дуги: возникают в информационном графе SGD при рассылке величин (таких как learning rate <math>\alpha</math> или текущие веса <math>w</math>) по всем итерациям цикла мини-батчей. В случае вектора весов (<math>w</math>), это рассылка всего вектора. Поскольку эта процедура хорошо изучена и оптимизирована на практике, она обычно не вызывает серьезных проблем с размещением данных в иерархии памяти, но требует эффективной коммуникации.

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

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

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

===Выводы для классов архитектур===

==Литература==
Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800

Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-12-08T23:06:55Z

OvsyannikovaSA: добавлено: свойства алгоритма

==Свойства и структура алгоритмов==
===Общее описание алгоритма===
'''Стохастический градиентный спуск''' (Stochastic Gradient Descent, SGD) представляет собой один из базовых и наиболее распространённых алгоритмов оптимизации, применяемых для обучения моделей машинного обучения и нейронных сетей. Он относится к классу итерационных методов минимизации функций.

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

Пусть даны <math>\{x_i, y_i\}_{i=1}^N, x_i \in \mathbb{R}^m</math> - вектор признаков <math>i</math>-го объекта, <math>y_i \in \mathbb{R}</math> - значение целевой переменной; класс моделей <math>a_\omega: \mathbb{R}^m \rightarrow \mathbb{R}</math>; функция потерь <math>f: \mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R}</math>. Задача: найти вектор параметров модели (весов) <math>\omega \in \mathbb{R}^d</math>, т.ч. <math>\omega = argmin_{\omega\in \mathbb{R}^d}\;L(\omega),\;L(\omega)=\sum_{i=1}^N f(a_{\omega}(x_i), y_i)</math>.

Алгоритм '''классического градиентного спуска (batch gradient descent)''' можно сформулировать следующим образом:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
вычислить градиент g <- grad L(ω);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Здесь и далее шаг обучения (learning rate) <math>\alpha</math> является гиперпараметром, т.е. параметром, который не оптимизируется в ходе работы алгоритма и который необходимо выбрать заранее. Начальное приближение <math>\omega_0</math> также необходимо выбрать заранее исходя из некоторых соображений.
Условие достижения сходимости на практике обычно заменяется повторением процедуры некоторое количество раз, после чего можно считать, что алгоритм сошелся в требуемом приближении.
В данном подходе для того, чтобы совершить одно обновление весов, необходимо вычислить функцию потерь для всех элементов выборки. Этот метод может оказаться неподходящим в некоторых случаях, например, при использовании больших датасетов, не помещающихся в памяти, или в случае, когда новые данные поступают в реальном времени.

Модернизацией этого алгоритма является '''стохастический градиентный спуск (stochastic gradient descent)''':
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xi, yi)
вычислить градиент g <- grad f(ω; xi, yi);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Алгоритм отличается от предыдущего тем, что обновление весов происходит после обработки одного объекта выборки. Компромиссом между двумя этими подходами служит '''стохастический градиентный спуск на мини-батчах (mini-batch gradient descent)'''. Для него требуется выбрать размер батча (batch_size). Обозначим <math>L(\omega)=\sum_{i=1}^{batch\_size} f(a_{\omega}(x_i), y_i)</math>
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск с мини-батчами'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α, размер батча batch_size
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xik, yik), 1<=k<=batch_size
вычислить градиент g <- grad L(ω; (xik, yik), 1<=k<=batch_size);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления.
В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.

Необходимо некоторым способом определить условия, при которых будет считаться, что алгоритм сошелся. Будем считать, что сходимость достигается за <math>E</math> итераций обработки всей выборки (будем называть одну итерацию '''эпохой''').

В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по <math>n</math> объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Таким образом, процедура случайного выбора мини-батча заменяется на линейный проход по всем данным.

===Вычислительное ядро алгоритма===
Основное время работы алгоритма приходится на вычисление градиента, которые повторяются, пока сходимость не будет достигнута.

=== Макроструктура алгоритма ===
Алгоритм стохастического градиентного спуска с мини-батчами представляется повторением следующих макроопераций:

1. Инициализация параметров: задание начального приближения вектора параметров модели <math>w_0</math>. Может быть случайной инициализацией, загрузкой предварительно обученной модели и т.п.

w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)

2. Перемешивание обучающей выборки: получение случайной перестановки обучающей выборки в начале эпохи. Можно выполнять, например, алгоритмом Фишера-Йетса.

Входные данные: <math>D=\{(x_i, y_i)\}_{i=1}^N</math> - обучающая выборка.

Выходные данные: <math>D_{perm}</math> - перемешанная выборка.

D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)

3. Формирование мини-батчей: разбиение переставленной выборки на последовательность мини-батчей.

Входные данные: <math>D_{perm}</math>

Выходные данные: последовательность подмножеств <math>B_k\subset D, \; k=1,..., K, \; \cup_k B_k=D, B_k \cap B_j = \emptyset, k\neq j</math>.

СписокБатчей ← ФормированиеМиниБатчей((X,y)_perm, размер_батча)

4. Вычисление градиента на батче. Может включать вычисление значений модели на батче, матрично-векторные умножения, суммирование по объектам батча.

Входные данные: текущие параметры <math>w</math>, мини-батч <math>B=\{(x_i, y_i)\}_{i\in I_B}</math>

Выходные данные: <math>g_B</math> - градиент по параметрам на этом батче.

g_B ← ВычислениеГрадиентаНаБатче(w, B)

5. Обновление параметров: осуществление одного шага метода по вычисленному градиенту на батче.

Входные данные: текущие параметры <math>w</math>, градиент на батче <math>g_B</math>.

Выходные данные: новые параметры <math>w_{new}=w-\alpha g_B</math>.

w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)

6. Проверка критерия останова: проверка условий завершения итерационного процесса. Может быть проверкой номера эпохи, проверкой изменения функции потерь и т.п.

флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, номер_шага, значение_критерия, история)

На макроуровне алгоритм можно описать так:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:100%;"
|+ '''Макроструктура алгоритма'''
|-
| <syntaxhighlight lang="pseudo">
w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)
номер_эпохи ← 0
повторять
номер_эпохи ← номер_эпохи + 1
D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)
СписокБатчей ← ФормированиеМиниБатчей(D_perm, размер_батча)
Для каждого B из СписокБатчей:
g_B ← ВычислениеГрадиентаНаБатче(w, B)
w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)
флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, значение_критерия, история)
Пока флаг_стоп = ЛОЖЬ
</syntaxhighlight>
|}

=== Схема реализации последовательного алгоритма ===
[[Файл:Sequential SGD with mini-batches scheme.png|мини|Схема последовательной реализации стохастического градиентного спуска с мини-батчами]]

=== Последовательная сложность алгоритма ===
<math>N</math> - размер выборки,

<math>n</math> - размер батча (<math>batch\_size</math>),

<math>C</math> - сложность вычисления производной функции потерь на одном примере,

<math>E</math> - число эпох.

Как уже упоминалось, будем перемешивать выборку случайным образом в начале каждой эпохи. Сложность случайного перемешивания выборки объема <math>N</math> алгоритмом Фишера-Йетса - <math>O(N)</math>. Если отказаться от этого предположения, можно считать, что сложность выбора <math>n</math> случайных элементов - <math>O(n)</math>. Такая оценка будет верна, если в системе реализован произвольный доступ к памяти. Однако для больших выборок, не помещающихся целиком в памяти, произвольный доступ к элементам выборки не будет возможен.

Сложность обработки одного батча - <math>O(n \cdot C)</math>.

Будем считать, что количество батчей <math>N/n</math> - целое число; тогда сложность вычисления градиентов в течение одной эпохи - <math>O(N/n \cdot n \cdot C) = O(N\cdot C)</math>.

Сложность одной эпохи с учетом перемешивания выборки - <math>O(N)+O(N\cdot C)=O(N\cdot C)</math>.

Сложность всего алгоритма с <math>E</math> эпохами - <math>O(E\cdot N\cdot C)</math>.

=== Информационный граф ===
На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.

[[file:Informational_graph_minibatch_SGD.png|thumb|center|Информационный граф стохастического градиентного спуска с мини-батчами]]
Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.

===Ресурс параллелизма алгоритма===
Ресурс параллелизма алгоритма стохастического градиентного спуска (SGD) определяется зависимостями данных между его основными шагами: вычислением градиента и обновлением весов.

====Иерархическая Структура Параллелизма====

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

1. Внешний уровень: конечный параллелизм

Внешний уровень параллелизма определяется последовательностью итераций по эпохам и по батчам:
* цикл по эпохам: итерации по эпохам зависимы, поскольку веса, полученные на одной эпохе, используются на следующей. Этот цикл не имеет параллельного ресурса.
* цикл по батчам (мини-батчам): обновления весов на основе последовательных мини-батчей информационно зависимы. Обновление <math>w_{k+1}</math> зависит от <math>w_k</math> и градиента <math>g_k</math>. Это создает ресурс конечного параллелизма, то есть высокая параллельность внутри каждого шага, но последовательность между шагами.

2. Внутренний уровень: массовый параллелизм

Внутренний уровень связан с обработкой данных внутри одного шага SGD (одного мини-батча).

Это ресурс массового параллелизма, который может быть реализован двумя способами:

* Вычисление градиента: вычисление частных градиентов для каждого примера (<math>x_i</math>) в мини-батче полностью независимо: <math>\frac{1}{|B|} \sum_{x_i \in B} \nabla Q_i(W)</math>.

Этот этап демонстрирует координатный параллелизм (независимость итераций цикла по примерам в батче).
* Обновление весов: операция <math>w_{k+1} = w_k - \eta g_k</math> представляет собой векторные операции (вычитание и скалярное умножение), которые также могут быть распараллелены по координатам вектора весов ($w$).

====Параллельная Сложность и Высота Ярусно-Параллельной Формы====

Оценка параллельной сложности алгоритма (высота канонической ярусно-параллельной формы) дается в терминах числа операций умножения/деления и сложения (которые доминируют).

Пусть <math>m</math> — размерность вектора весов (число признаков), <math>B</math> — размер мини-батча.

Основной вычислительный шаг SGD состоит из трех этапов:

{| class="wikitable sortable"
|+ Параллельная сложность одного шага Стохастического Градиентного Спуска (SGD)
|-
! Этап
! Параллельная сложность (Высота ЯПФ, ''H'')
! Ширина ЯПФ (''W'' - Сбалансированность)
! Описание Ресурса Параллелизма
|-
| '''Вычисление градиентов'''
| <math>O(\log_2 B + 1)</math>
| <math>O(m \times B)</math>
| '''Массовый параллелизм''' (Координатный параллелизм) по примерам в мини-батче. Требуется редукция/суммирование.
|-
| '''Усреднение и масштабирование'''
| <math>O(1)</math>
| <math>O(m)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|-
| '''Обновление весов'''
| <math>O(1)</math>
| <math>O(m)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|}

Таким образом, параллельная сложность (высота) одного шага SGD составляет <math>H = O(\log_2 B)</math>.

====Сбалансированность параллельных шагов (ширина ярусов)====

Ширина ярусов отражает сбалансированность параллельных шагов по числу операций:

* Ширина этапа градиентов: на этапе вычисления градиентов ширина ярусов максимальна, достигая <math>W = O(m \times B)</math>. Этот этап сбалансирован при <math>P</math> процессорах, где <math>P \le B</math>, поскольку каждому процессу можно поручить обработку <math>\lceil B/P \rceil</math> примеров.
* Ширина этапов обновления: на этапах усреднения и обновления весов ширина ярусов составляет <math>W = O(m)</math>. Этот этап также сбалансирован, если <math>P \le m</math>, поскольку операции могут быть распределены по <math>P</math> процессорам.

Алгоритм SGD обладает хорошей сбалансированностью на каждом шаге, что позволяет эффективно использовать большое число процессоров (ядер), особенно когда произведение <math>m \times B</math> велико.

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

Обучающая выборка (<math>D</math>) обычно представляется в виде двух плотных структур данных:

1. Матрица Признаков (<math>X\in\mathbb{R}^{N \times m}</math>), <math>N</math> — общее число обучающих примеров, а <math>m</math> — число признаков (размерность векторов весов).

В задачах машинного обучения <math>N</math> часто значительно больше, чем <math>m</math> (много примеров, но относительно небольшое число признаков), или же <math>m</math> может быть очень большим (например, при использовании One-Hot-Encoding).

В зависимости от задачи, матрица <math>X</math> может быть:
* плотной (dense): каждая ячейка содержит значащее числовое значение.
* разреженной (sparse): если большая часть элементов равна нулю.

2. Вектор целевых значений (<math>y</math>) - вектор размера <math>N \times 1</math> или <math>N \times C</math> (для многоклассовой классификации, где <math>C</math> — число классов).

Обычно плотный, содержит действительные числа (для регрессии) или целочисленные метки/векторы (для классификации).

3. Параметры обучения

* Скорость обучения (<math>\alpha\in\mathbb{R}</math>, learning rate): его значение обычно мало (например, <math>10^{-2}</math> или <math>10^{-3}</math>) и оказывает критическое влияние на сходимость.
* Размер мини-батча (<math>B\in\mathbb{R}</math>, batch size): определяет число примеров, используемых для одного шага. Обычно является степенью двойки (<math>32, 64, 128, \dots</math>).
* Число эпох (<math>E\in\mathbb{N}</math>, epochs): число полных проходов по всему набору данных.

====Выходные Данные====

* Вектор весов модели (<math>w</math>): вектор размера <math>m \times 1</math> (или матрица <math>m \times C</math>, если модель содержит скрытые слои или многоклассовый вывод).

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

* История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен <math>(E \times N) / B</math>. Используется для анализа сходимости и отладки алгоритма.

===Свойства алгоритма===
====Соотношение последовательной и параллельной сложности====

Алгоритм SGD является последовательным по отношению к шагам обновления весов. Однако в рамках одного шага обновления (одного мини-батча) он обладает высоким ресурсом параллелизма.

* Последовательная сложность одного шага SGD: <math>T_{seq} = O(B \cdot d)</math>, где <math>B</math> - размер батча, <math>d</math> - размерность весов.
* Параллельная сложность одного шага SGD (высота ЯПФ): <math>H = O(\log_2 B + 1)</math>.

Теоретический выигрыш от параллельной реализации (ускорение) составляет:

<math>S = \frac{T_{seq}}{H} = \frac{O(B \cdot d)}{O(\log_2 B + 1)}</math>

Теоретически, параллельная реализация обеспечивает значительное ускорение <math>O(B \cdot d)</math>, которое растет линейно с размером батча и размерностью задачи, если есть достаточное количество процессоров <math>P</math>.

* Сложности параллелизации: главная сложность заключается в информационной зависимости между последовательными шагами обновления. Параллельная реализация дает выигрыш только внутри одного шага (градиент и обновление), но не может ускорить последовательность шагов, что является фундаментальным ограничением SGD.
====Вычислительная Мощность====
* Общее число операций (за одну эпоху): <math>O(N \cdot d)</math>, где <math>N</math> — общее число объектов.
* Объем входных данных (матрица <math>X</math>): <math>O(N \cdot d)</math>.
* Объем выходных данных (вектор весов <math>w</math>): <math>O(d)</math>.

<math>W_{comp} = \frac{\text{Число операций}}{\text{Объем входных данных}} = \frac{O(N \cdot d)}{O(N \cdot d + d)}</math>

При больших <math>N</math> <math>N \cdot d</math> доминирует в знаменателе. Таким образом, вычислительная мощность SGD составляет:

<math>W_{comp} \approx O(1)</math>

Вычислительная мощность SGD близка к константе (<math>O(1)</math>). Это означает, что число операций примерно равно объему исходных данных. Это значение относительно невысокое. Это свойство требует, чтобы алгоритм выполнялся "близко" к памяти с данными (например, на том же узле кластера), чтобы минимизировать накладные расходы на перемещение данных.
====Устойчивость Алгоритма====

Алгоритм SGD является '''стохастическим и неустойчивым''' в смысле получения одного и того же результата при каждом запуске.

* Неустойчивость к входным данным: поскольку SGD использует только часть данных (мини-батч) для каждого шага, дисперсия в оценке градиента высокая. Это приводит к флуктуациям в траектории сходимости.
* Ошибка округления: при использовании массового параллелизма (например, при суммировании градиентов от <math>B</math> примеров) на системах с массовым параллелизмом порядок выполнения ассоциативных операций (сложение) может меняться от запуска к запуску. Это приводит к неповторяемости результатов работы параллельных программ, что является серьезной проблемой на практике.

====Сбалансированность вычислительного процесса====

Алгоритм обладает хорошей сбалансированностью с точки зрения распределения нагрузки.

На каждой итерации преобладают арифметические операции (умножение и сложение) при вычислении градиента. Соотношение между арифметическими операциями и обращениями к памяти (чтение/запись) определяется параметром <math>B \cdot d</math>, который обычно достаточно велик, что обеспечивает эффективную работу процессоров.

Распределение нагрузки по <math>P</math> процессам на этапе вычисления градиента достигается просто: каждый процессор обрабатывает <math>\lceil B/P \rceil</math> примеров. Это обеспечивает высокую балансировку нагрузки.

====Детерминированность====
Алгоритм SGD является недетерминированным по следующим причинам:

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

====Дополнительные свойства====

* Степень исхода вершины: высока для вектора весов <math>w</math>. На каждом шаге <math>w</math> используется для вычисления градиента для всех <math>B</math> примеров. На этапе реализации это требует эффективной рассылки вектора <math>w</math> всем параллельным процессам/потокам, работающим над батчем, и эффективного доступа к нему.
* "Длинные" дуги: типичные "длинные" дуги в информационном графе SGD возникают при рассылке скалярных величин (таких как learning rate <math>\alpha</math> или текущие веса <math>w</math>) по всем итерациям цикла мини-батчей. В случае вектора весов (<math>w</math>), это рассылка всего вектора. Поскольку этот паттерн (рассылка) хорошо изучен и оптимизирован на практике, он обычно не вызывает серьезных проблем с размещением данных в иерархии памяти, но требует эффективной коммуникации.

==Литература==
Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800

Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-12-08T22:05:39Z

OvsyannikovaSA: добавлено: ресурс параллелизма алгоритма, входные и выходные данные алгоритма

==Свойства и структура алгоритмов==
===Общее описание алгоритма===
'''Стохастический градиентный спуск''' (Stochastic Gradient Descent, SGD) представляет собой один из базовых и наиболее распространённых алгоритмов оптимизации, применяемых для обучения моделей машинного обучения и нейронных сетей. Он относится к классу итерационных методов минимизации функций.

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

Пусть даны <math>\{x_i, y_i\}_{i=1}^N, x_i \in \mathbb{R}^m</math> - вектор признаков <math>i</math>-го объекта, <math>y_i \in \mathbb{R}</math> - значение целевой переменной; класс моделей <math>a_\omega: \mathbb{R}^m \rightarrow \mathbb{R}</math>; функция потерь <math>f: \mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R}</math>. Задача: найти вектор параметров модели (весов) <math>\omega \in \mathbb{R}^d</math>, т.ч. <math>\omega = argmin_{\omega\in \mathbb{R}^d}\;L(\omega),\;L(\omega)=\sum_{i=1}^N f(a_{\omega}(x_i), y_i)</math>.

Алгоритм '''классического градиентного спуска (batch gradient descent)''' можно сформулировать следующим образом:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
вычислить градиент g <- grad L(ω);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Здесь и далее шаг обучения (learning rate) <math>\alpha</math> является гиперпараметром, т.е. параметром, который не оптимизируется в ходе работы алгоритма и который необходимо выбрать заранее. Начальное приближение <math>\omega_0</math> также необходимо выбрать заранее исходя из некоторых соображений.
Условие достижения сходимости на практике обычно заменяется повторением процедуры некоторое количество раз, после чего можно считать, что алгоритм сошелся в требуемом приближении.
В данном подходе для того, чтобы совершить одно обновление весов, необходимо вычислить функцию потерь для всех элементов выборки. Этот метод может оказаться неподходящим в некоторых случаях, например, при использовании больших датасетов, не помещающихся в памяти, или в случае, когда новые данные поступают в реальном времени.

Модернизацией этого алгоритма является '''стохастический градиентный спуск (stochastic gradient descent)''':
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xi, yi)
вычислить градиент g <- grad f(ω; xi, yi);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Алгоритм отличается от предыдущего тем, что обновление весов происходит после обработки одного объекта выборки. Компромиссом между двумя этими подходами служит '''стохастический градиентный спуск на мини-батчах (mini-batch gradient descent)'''. Для него требуется выбрать размер батча (batch_size). Обозначим <math>L(\omega)=\sum_{i=1}^{batch\_size} f(a_{\omega}(x_i), y_i)</math>
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:60%;"
|+ '''Стохастический градиентный спуск с мини-батчами'''
|-
| <syntaxhighlight lang="pseudo">
вход: функция потерь L(ω), шаг обучения α, размер батча batch_size
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xik, yik), 1<=k<=batch_size
вычислить градиент g <- grad L(ω; (xik, yik), 1<=k<=batch_size);
обновить веса ω <- ω - αg;
вернуть ω
</syntaxhighlight>
|}
Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления.
В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.

Необходимо некоторым способом определить условия, при которых будет считаться, что алгоритм сошелся. Будем считать, что сходимость достигается за <math>E</math> итераций обработки всей выборки (будем называть одну итерацию '''эпохой''').

В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по <math>n</math> объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Таким образом, процедура случайного выбора мини-батча заменяется на линейный проход по всем данным.

===Вычислительное ядро алгоритма===
Основное время работы алгоритма приходится на вычисление градиента, которые повторяются, пока сходимость не будет достигнута.

=== Макроструктура алгоритма ===
Алгоритм стохастического градиентного спуска с мини-батчами представляется повторением следующих макроопераций:

1. Инициализация параметров: задание начального приближения вектора параметров модели <math>w_0</math>. Может быть случайной инициализацией, загрузкой предварительно обученной модели и т.п.

w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)

2. Перемешивание обучающей выборки: получение случайной перестановки обучающей выборки в начале эпохи. Можно выполнять, например, алгоритмом Фишера-Йетса.

Входные данные: <math>D=\{(x_i, y_i)\}_{i=1}^N</math> - обучающая выборка.

Выходные данные: <math>D_{perm}</math> - перемешанная выборка.

D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)

3. Формирование мини-батчей: разбиение переставленной выборки на последовательность мини-батчей.

Входные данные: <math>D_{perm}</math>

Выходные данные: последовательность подмножеств <math>B_k\subset D, \; k=1,..., K, \; \cup_k B_k=D, B_k \cap B_j = \emptyset, k\neq j</math>.

СписокБатчей ← ФормированиеМиниБатчей((X,y)_perm, размер_батча)

4. Вычисление градиента на батче. Может включать вычисление значений модели на батче, матрично-векторные умножения, суммирование по объектам батча.

Входные данные: текущие параметры <math>w</math>, мини-батч <math>B=\{(x_i, y_i)\}_{i\in I_B}</math>

Выходные данные: <math>g_B</math> - градиент по параметрам на этом батче.

g_B ← ВычислениеГрадиентаНаБатче(w, B)

5. Обновление параметров: осуществление одного шага метода по вычисленному градиенту на батче.

Входные данные: текущие параметры <math>w</math>, градиент на батче <math>g_B</math>.

Выходные данные: новые параметры <math>w_{new}=w-\alpha g_B</math>.

w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)

6. Проверка критерия останова: проверка условий завершения итерационного процесса. Может быть проверкой номера эпохи, проверкой изменения функции потерь и т.п.

флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, номер_шага, значение_критерия, история)

На макроуровне алгоритм можно описать так:
{| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:100%;"
|+ '''Макроструктура алгоритма'''
|-
| <syntaxhighlight lang="pseudo">
w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)
номер_эпохи ← 0
повторять
номер_эпохи ← номер_эпохи + 1
D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)
СписокБатчей ← ФормированиеМиниБатчей(D_perm, размер_батча)
Для каждого B из СписокБатчей:
g_B ← ВычислениеГрадиентаНаБатче(w, B)
w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)
флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, значение_критерия, история)
Пока флаг_стоп = ЛОЖЬ
</syntaxhighlight>
|}

=== Схема реализации последовательного алгоритма ===
[[Файл:Sequential SGD with mini-batches scheme.png|мини|Схема последовательной реализации стохастического градиентного спуска с мини-батчами]]

=== Последовательная сложность алгоритма ===
<math>N</math> - размер выборки,

<math>n</math> - размер батча (<math>batch\_size</math>),

<math>C</math> - сложность вычисления производной функции потерь на одном примере,

<math>E</math> - число эпох.

Как уже упоминалось, будем перемешивать выборку случайным образом в начале каждой эпохи. Сложность случайного перемешивания выборки объема <math>N</math> алгоритмом Фишера-Йетса - <math>O(N)</math>. Если отказаться от этого предположения, можно считать, что сложность выбора <math>n</math> случайных элементов - <math>O(n)</math>. Такая оценка будет верна, если в системе реализован произвольный доступ к памяти. Однако для больших выборок, не помещающихся целиком в памяти, произвольный доступ к элементам выборки не будет возможен.

Сложность обработки одного батча - <math>O(n \cdot C)</math>.

Будем считать, что количество батчей <math>N/n</math> - целое число; тогда сложность вычисления градиентов в течение одной эпохи - <math>O(N/n \cdot n \cdot C) = O(N\cdot C)</math>.

Сложность одной эпохи с учетом перемешивания выборки - <math>O(N)+O(N\cdot C)=O(N\cdot C)</math>.

Сложность всего алгоритма с <math>E</math> эпохами - <math>O(E\cdot N\cdot C)</math>.

=== Информационный граф ===
На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.

[[file:Informational_graph_minibatch_SGD.png|thumb|center|Информационный граф стохастического градиентного спуска с мини-батчами]]
Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.

===Ресурс параллелизма алгоритма===
Ресурс параллелизма алгоритма стохастического градиентного спуска (SGD) определяется зависимостями данных между его основными шагами: вычислением градиента и обновлением весов.

====Иерархическая Структура Параллелизма====

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

1. Внешний уровень: конечный параллелизм

Внешний уровень параллелизма определяется последовательностью итераций по эпохам и по батчам:
* цикл по эпохам: итерации по эпохам зависимы, поскольку веса, полученные на одной эпохе, используются на следующей. Этот цикл не имеет параллельного ресурса.
* цикл по батчам (мини-батчам): обновления весов на основе последовательных мини-батчей информационно зависимы. Обновление <math>w_{k+1}</math> зависит от <math>w_k</math> и градиента <math>g_k</math>. Это создает ресурс конечного параллелизма, то есть высокая параллельность внутри каждого шага, но последовательность между шагами.

2. Внутренний уровень: массовый параллелизм

Внутренний уровень связан с обработкой данных внутри одного шага SGD (одного мини-батча).

Это ресурс массового параллелизма, который может быть реализован двумя способами:

* Вычисление градиента: вычисление частных градиентов для каждого примера (<math>x_i</math>) в мини-батче полностью независимо: <math>\frac{1}{|B|} \sum_{x_i \in B} \nabla Q_i(W)</math>.

Этот этап демонстрирует координатный параллелизм (независимость итераций цикла по примерам в батче).
* Обновление весов: операция <math>w_{k+1} = w_k - \eta g_k</math> представляет собой векторные операции (вычитание и скалярное умножение), которые также могут быть распараллелены по координатам вектора весов ($w$).

====Параллельная Сложность и Высота Ярусно-Параллельной Формы====

Оценка параллельной сложности алгоритма (высота канонической ярусно-параллельной формы) дается в терминах числа операций умножения/деления и сложения (которые доминируют).

Пусть <math>m</math> — размерность вектора весов (число признаков), <math>B</math> — размер мини-батча.

Основной вычислительный шаг SGD состоит из трех этапов:

{| class="wikitable sortable"
|+ Параллельная сложность одного шага Стохастического Градиентного Спуска (SGD)
|-
! Этап
! Параллельная сложность (Высота ЯПФ, ''H'')
! Ширина ЯПФ (''W'' - Сбалансированность)
! Описание Ресурса Параллелизма
|-
| '''Вычисление градиентов'''
| <math>O(\log_2 B + 1)</math>
| <math>O(m \times B)</math>
| '''Массовый параллелизм''' (Координатный параллелизм) по примерам в мини-батче. Требуется редукция/суммирование.
|-
| '''Усреднение и масштабирование'''
| <math>O(1)</math>
| <math>O(m)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|-
| '''Обновление весов'''
| <math>O(1)</math>
| <math>O(m)</math>
| '''Конечный параллелизм''' (Координатный параллелизм) по координатам вектора весов.
|}

Таким образом, параллельная сложность (высота) одного шага SGD составляет <math>H = O(\log_2 B)</math>.

====Сбалансированность параллельных шагов (ширина ярусов)====

Ширина ярусов отражает сбалансированность параллельных шагов по числу операций:

* Ширина этапа градиентов: на этапе вычисления градиентов ширина ярусов максимальна, достигая <math>W = O(m \times B)</math>. Этот этап сбалансирован при <math>P</math> процессорах, где <math>P \le B</math>, поскольку каждому процессу можно поручить обработку <math>\lceil B/P \rceil</math> примеров.
* Ширина этапов обновления: на этапах усреднения и обновления весов ширина ярусов составляет <math>W = O(m)</math>. Этот этап также сбалансирован, если <math>P \le m</math>, поскольку операции могут быть распределены по <math>P</math> процессорам.

Алгоритм SGD обладает хорошей сбалансированностью на каждом шаге, что позволяет эффективно использовать большое число процессоров (ядер), особенно когда произведение <math>m \times B</math> велико.

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

Обучающая выборка (<math>D</math>) обычно представляется в виде двух плотных структур данных:

1. Матрица Признаков (<math>X\in\mathbb{R}^{N \times m}</math>), <math>N</math> — общее число обучающих примеров, а <math>m</math> — число признаков (размерность векторов весов).

В задачах машинного обучения <math>N</math> часто значительно больше, чем <math>m</math> (много примеров, но относительно небольшое число признаков), или же <math>m</math> может быть очень большим (например, при использовании One-Hot-Encoding).

В зависимости от задачи, матрица <math>X</math> может быть:
* плотной (dense): каждая ячейка содержит значащее числовое значение.
* разреженной (sparse): если большая часть элементов равна нулю.

2. Вектор целевых значений (<math>y</math>) - вектор размера <math>N \times 1</math> или <math>N \times C</math> (для многоклассовой классификации, где <math>C</math> — число классов).

Обычно плотный, содержит действительные числа (для регрессии) или целочисленные метки/векторы (для классификации).

3. Параметры обучения

* Скорость обучения (<math>\alpha\in\mathbb{R}</math>, learning rate): его значение обычно мало (например, <math>10^{-2}</math> или <math>10^{-3}</math>) и оказывает критическое влияние на сходимость.
* Размер мини-батча (<math>B\in\mathbb{R}</math>, batch size): определяет число примеров, используемых для одного шага. Обычно является степенью двойки (<math>32, 64, 128, \dots</math>).
* Число эпох (<math>E\in\mathbb{N}</math>, epochs): число полных проходов по всему набору данных.

====Выходные Данные====

* Вектор весов модели (<math>w</math>): вектор размера <math>m \times 1</math> (или матрица <math>m \times C</math>, если модель содержит скрытые слои или многоклассовый вывод).

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

* История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен <math>(E \times N) / B</math>. Используется для анализа сходимости и отладки алгоритма.

==Литература==
Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800

Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-11-27T17:22:11Z

OvsyannikovaSA: /* Информационный граф */

Файл:Informational graph minibatch SGD.png

2025-11-27T17:19:00Z

OvsyannikovaSA: OvsyannikovaSA загрузила новую версию Файл:Informational graph minibatch SGD.png

Информационный граф стохастического градиентного спуска с мини-батчами

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-11-27T17:17:34Z

OvsyannikovaSA: информационный граф

Файл:Informational graph SGD.png

2025-11-27T17:15:27Z

OvsyannikovaSA:

Информационный граф стохастического градиентного спуска с мини-батчами

Файл:Informational graph minibatch SGD.png

2025-11-27T16:45:56Z

OvsyannikovaSA:

Информационный граф стохастического градиентного спуска с мини-батчами

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-11-27T12:44:11Z

OvsyannikovaSA: /* Макроструктура алгоритма */

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-11-27T11:07:48Z

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

Файл:Sequential SGD with mini-batches scheme.png

2025-11-27T11:06:54Z

OvsyannikovaSA:

Схема последовательной реализации стохастического градиентного спуска с мини-батчами

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-11-23T15:24:43Z

OvsyannikovaSA: исправлено мат. описание алгоритма

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-11-23T08:57:40Z

OvsyannikovaSA: добавлено: последовательная сложность алгоритма

Участница:OvsyannikovaSA/Стохастический градиентный спуск

2025-11-03T20:12:16Z

OvsyannikovaSA: добавлено: общее описание алгоритма, математическое описание алгоритма, литература