Стохастический градиентный спуск ( англ. Stochastic gradient descent , SGD ) — итерационный метод для оптимизации целевой функции с подходящими свойствами гладкости (например, дифференцируемость или субдифференцируемость ). Его можно расценивать как стохастическую аппроксимацию оптимизации методом градиентного спуска , поскольку он заменяет реальный градиент, вычисленный из полного набора данных, оценкой, вычисленной из случайно выбранного подмножества данных . Это сокращает задействованные вычислительные ресурсы и помогает достичь более высокой скорости итераций в обмен на более низкую скорость сходимости . Особенно большой эффект достигается в приложениях, связанных с обработкой больших данных .

Хотя базовая идея стохастической аппроксимации восходит к алгоритму Роббинса-Монро 1950-х годов , стохастический градиентный спуск стал важным оптимизационным методом в машинном обучении .

Предпосылки

И статистическая , и машинное обучение рассматривают задачу минимизации целевой функции , имеющей форму суммы

${\displaystyle Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w),}$

где параметр ${\displaystyle w}$ , минимизирующий ${\displaystyle Q(w)}$ , следует оценить . Каждый член суммы ${\displaystyle Q_{i}}$ обычно ассоциируется с ${\displaystyle i}$ -ым в наборе данных , использованном для обучения.

В классической статистике задачи минимизации суммы возникают в методе наименьших квадратов и методе максимального правдоподобия (для независимых наблюдений). Общий класс оценок, возникающих в виде минимизации сумм, называется . Однако еще в конце XX века было замечено, что требование даже локальной минимизации слишком ограничительно для некоторых задач метода максимального правдоподобия . Поэтому современные теоретики-статистики часто рассматривают стационарные точки функции правдоподобия (или нули её производной, и другие ).

Задача минимизации суммы возникает также при минимизации эмпирического риска . В этом случае ${\displaystyle Q_{i}(w)}$ является значением функции потерь на ${\displaystyle i}$ -ом примере, а ${\displaystyle Q(w)}$ является эмпирическим риском.

При использовании для минимизации вышеприведённой функции, стандартный (или «пакетный») метод градиентного спуска осуществляет следующие итерации:

${\displaystyle w:=w-\eta \nabla Q(w)=w-{\frac {\eta }{n}}\sum _{i=1}^{n}\nabla Q_{i}(w),}$

где ${\displaystyle \eta }$ является размером шага, называемым в машинном обучении.

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

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

Итеративный метод

В стохастическом («онлайновом») градиентном спуске истинный градиент ${\displaystyle Q(w)}$ аппроксимируется градиентом одного тренировочного примера

${\displaystyle w:=w-\eta \nabla Q_{i}(w).}$

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

В псевдокоде стохастический градиентный спуск можно представить следующим образом:

Компромиссом между вычислением истинного градиента и градиента по одному тренировочному примеру может быть вычисление градиента по более чем одному тренировочному примеру, называемому «минипакетом», на каждом шаге. Это может быть существенно лучше, чем описанный «истинный» стохастический градиентный спуск, поскольку код может использовать библиотеки вместо отдельных вычислений на каждом шаге. Это может также привести к более гладкой сходимости, так как градиент, вычисляемый на каждом шаге, усредняется по большему числу тренировочных примеров.

Сходимость стохастического градиентного спуска анализировалась с помощью теорий выпуклой минимизации и стохастической аппроксимации . В упрощенном виде результат можно представить так: при убывании ${\displaystyle \eta }$ с подходящей скоростью, с учётом относительно слабых предположений, стохастический градиентный спуск сходится почти наверняка к глобальному минимуму, если целевая функция выпукла или псевдовыпукла , в противном случае метод сходится почти наверняка к локальному минимуму . Фактически, это следствие теоремы Роббинса — Сигмунда .

Пример

Предположим, что мы хотим приблизить прямую ${\displaystyle {\hat {y}}=\!w_{1}+w_{2}x}$ тренировочным набором с множеством наблюдений ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ и соответствующих ответов ${\displaystyle ({\hat {y_{1}}},{\hat {y_{2}}},\ldots ,{\hat {y_{n}}})}$ с помощью метода наименьших квадратов . Целевой функцией для минимизации будет

${\displaystyle Q(w)=\sum _{i=1}^{n}Q_{i}(w)=\sum _{i=1}^{n}\left({\hat {y_{i}}}-y_{i}\right)^{2}=\sum _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\right)^{2}.}$

Последняя строка в вышеприведённом псевдокоде для задачи превращается в

${\displaystyle {\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}:={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}{\frac {\partial }{\partial w_{1}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\\{\frac {\partial }{\partial w_{2}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\end{bmatrix}}={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}2(w_{1}+w_{2}x_{i}-y_{i})\\2x_{i}(w_{1}+w_{2}x_{i}-y_{i})\end{bmatrix}}.}$

Заметим, что на каждой итерации (которая называется также пересчётом), вычисляется только градиент в одной точке ${\displaystyle x_{i}}$ вместо вычисления на множестве всех выборок.

Ключевое различие по сравнению со стандартным (пакетным) градиентным спуском в том, что только одна часть данных из всего множества используется на каждом шаге и эта часть выбирается на каждом шаге случайно.

Известные приложения

Стохастический градиентный спуск является популярным алгоритмом для обучения широкого ряда моделей в машинном обучении , в частности в (линейном) методе опорных векторов , в логистической регрессии (см. например, ) и в графовых вероятностных моделях . Когда метод комбинируется с алгоритмом обратного распространения ошибки , он является де факто стандартным алгоритмом для обучения искусственных нейронных сетей . Его применение было также замечено в геофизическом сообществе, особенно для приложений Full Waveform Inversion (FWI) .

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

Другой стохастический алгоритм градиентного спуска является адаптивным ( англ. least mean squares adaptive filter , LMS).

Разновидности и модификации

Существует множество модификаций алгоритма стохастического градиентного спуска. В частности, в машинном обучении проблемой является выбор (размера шага): при большом шаге алгоритм может расходиться, а при маленьком — сходимость слишком медленная. Для решения этой проблемы можно использовать , при котором скорость обучения ${\displaystyle \eta _{t}}$ убывает с увеличением номера итерации ${\displaystyle t}$ . При этом на первых итерациях значения параметров изменяются значительно, а на более поздних итерациях — только лишь уточняются. Такие расписания известны со времён работы Мак-Куина по кластеризации методом k -средних . Некоторые практические рекомендации по выбору шага в некоторых вариантах SGD даны в секциях 4.4, 6.6 и 7.5 статьи Сполла (2003) .

Не выраженные явно изменения (ISGD)

Как упомянуто ранее, классический стохастический градиентный спуск обычно чувствителен к ${\displaystyle \eta }$ . Быстрая сходимость требует быстрой большой скорости обучения, но это может вызвать численную неустойчивость . Задача может быть главным образом решена путём рассмотрения неявного изменения , когда стохастический градиент пересчитывается на следующей итерации, а не на текущей

${\displaystyle w^{new}:=w^{old}-\eta \nabla Q_{i}(w^{new}).}$

Это равенство неявное, поскольку ${\displaystyle w^{new}}$ появляется на обеих сторонах равенства. Это стохастическая форма проксимального градиентного метода , поскольку пересчёт может быть выражен в виде

${\displaystyle w^{new}:=\arg \min _{w}\{Q_{i}(w)+{\frac {1}{2\eta }}||w-w^{old}||^{2}\}.}$

В качестве примера рассмотрим метод наименьших квадратов со свойствами ${\displaystyle x_{1},\ldots ,x_{n}\in \mathbb {R} ^{p}}$ и наблюдениями ${\displaystyle y_{1},\ldots ,y_{n}\in \mathbb {R} }$ . Мы хотим решить:

${\displaystyle \min _{w}\sum _{j=1}^{n}(y_{j}-x_{j}'w)^{2},}$

где ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}}$ означает скалярное произведение .

Заметим, что ${\displaystyle x}$ может иметь «1» в качестве первого элемента. Классический стохастический градиентный спуск работает следующим образом

${\displaystyle w^{new}=w^{old}+\eta (y_{i}-x_{i}'w^{old})x_{i}}$

где ${\displaystyle i}$ равномерно распределено между 1 и ${\displaystyle n}$ . Хотя теоретически эта процедура сходится при относительно мягких предположениях, на практике процедура может оказаться сильно нестабильной. В частности, если ${\displaystyle \eta }$ неверно задана, то ${\displaystyle I-\eta x_{i}x_{i}'}$ имеют большие абсолютные собственные значения с большой вероятностью и процедура может расходиться за несколько итераций. Для контраста, явный стохастический градиентный спуск ( англ. implicit stochastic gradient descent , ISGD) может быть выражен в виде формулы

${\displaystyle w^{new}=w^{old}+{\frac {\eta }{1+\eta ||x_{i}||^{2}}}(y_{i}-x_{i}'w^{old})x_{i}.}$

Процедура будет оставаться численно устойчивой почти для всех ${\displaystyle \eta }$ , поскольку теперь нормализована. Такое сравнение между классическим и явным стохастическим градиентным спуском в методе наименьших квадратов очень похоже на сравнение между ( англ. least mean squares , LMS) и ( англ. normalized least mean squares filter , NLMS).

Хотя решение в аналитическом виде для ISGD возможно только в методе наименьших квадратов, процедуру можно эффективно реализовать в широкий ряд моделей. В частности, предположим, что ${\displaystyle Q_{i}(w)}$ зависит от ${\displaystyle w}$ только как линейная комбинация свойств ${\displaystyle x_{i}}$ , так что мы можем записать ${\displaystyle \nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}}$ , где вещественнозначная функция ${\displaystyle q}$ может зависеть от ${\displaystyle x_{i},y_{i}}$ , но не от ${\displaystyle w}$ непосредственно, лишь через ${\displaystyle x_{i}'w}$ . Метод наименьших квадратов удовлетворяет этому условию, а потому удовлетворяют этому условию логистическая регрессия и большинство обобщённых линейных моделей . Например, в методе наименьших квадратов ${\displaystyle q(x_{i}'w)=y_{i}-x_{i}'w}$ , а в логистической регрессии ${\displaystyle q(x_{i}'w)=y_{i}-S(x_{i}'w)}$ , где ${\displaystyle S(u)=e^{u}/(1+e^{u})}$ является логистической функцией . В ${\displaystyle q(x_{i}'w)=y_{i}-e^{x_{i}'w}}$ , и так далее.

В таких условия ISGD легко реализовать следующим образом. Пусть ${\displaystyle f(\xi )=\eta q(x_{i}'w^{old}+\xi ||x_{i}||^{2})}$ , где ${\displaystyle \xi }$ является числом. Тогда ISGD эквивалентен

${\displaystyle w^{new}=w^{old}+\xi ^{\ast }x_{i},\;\xi ^{\ast }=f(\xi ^{\ast }).}$

Масштабный множитель ${\displaystyle \xi ^{\ast }\in \mathbb {R} }$ можно найти методом деления отрезка пополам , поскольку в большинстве моделей, таких как вышеупомянутые обобщённые линейные модели, функция ${\displaystyle q}$ убывает, а тогда границами поиска для ${\displaystyle \xi ^{\ast }}$ будут ${\displaystyle [\min(0,f(0)),\max(0,f(0))]}$ .

Импульс

Более поздние разработки включают метод импульса , который появился в статье Румельхарта , Хинтона и Уильямса об обучении с обратным распространением ошибки . Стохастический градиентный спуск с импульсом запоминает изменение ${\displaystyle \Delta w}$ на каждой итерации и определяет следующее изменение в виде линейной комбинации градиента и предыдущего изменения :

${\displaystyle \Delta w:=\alpha \Delta w-\eta \nabla Q_{i}(w)}$

${\displaystyle w:=w+\Delta w}$

что приводит к

${\displaystyle w:=w-\eta \nabla Q_{i}(w)+\alpha \Delta w}$

где параметр ${\displaystyle w}$ , который минимизирует ${\displaystyle Q(w)}$ , следует оценить , а ${\displaystyle \eta }$ является размером шага (иногда называется в машинном обучении).

Название «импульс» берёт начало от импульса в физике — вектор весов ${\displaystyle w}$ , понимаемый как трасса частицы по пространству параметров , испытывает ускорение от градиента функции потерь (« силы »). В отличие от классического стохастического градиентного спуска, метод пытается сохранить продвижение в том же направлении, предотвращая колебания. Импульс использовался успешно специалистами по информатике для обучения искусственных нейронных сетей в течение нескольких десятилетий .

Усреднение

Усреднённый стохастический градиентный спуск , разработанный независимо Руппертом и Поляком в конце 1980-х годов, является обычным стохастическим градиентным спуском, который записывает среднее вектора параметров. То есть пересчёт тот же, что и в обычном методе стохастического градиентного спуска, но алгоритм также отслеживает

${\displaystyle {\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}}$ .

Когда оптимизация завершена, вектор средних параметров занимает место w .

AdaGrad

AdaGrad (адаптивный градиентный алгоритм, англ. adaptive gradient algorithm ), опубликованный в 2011 , является модификацией стохастического алгоритма градиентного спуска с отдельной для каждого параметра . Неформально, это увеличивает скорость обучения для параметров с редкими данными и уменьшает скорость обучения для параметров с менее редкими. Эта стратегия увеличивает скорость сходимости по сравнению со стандартным стохастическим методом градиентного спуска в условиях, когда данные редки и соответствующие параметры более информативны. Примерами таких приложений являются обработка естественных языков и распознавание образов . Алгоритм имеет базовую скорость обучения ${\displaystyle \eta }$ , но она умножается на элементы вектора ${\displaystyle \{G_{j,j}\}}$ , который является диагональю матрицы внешнего произведения

${\displaystyle G=\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\mathsf {T}}}$

где ${\displaystyle g_{\tau }=\nabla Q_{i}(w)}$ , градиент на итерации ${\displaystyle \tau }$ . Диагональ задаётся выражением

${\displaystyle G_{j,j}=\sum _{\tau =1}^{t}g_{\tau ,j}^{2}}$ .

Этот вектор обновляется после каждой итерации. Формула пересчёта

${\displaystyle w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\circ g}$

или, записывая как пересчёт по параметрам,

${\displaystyle w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}}}}g_{j}.}$

Каждый элемент ${\displaystyle \{G_{(i,i)}\}}$ даёт множитель для скорости обучения, применяемый к одному параметру ${\displaystyle w_{i}}$ . Поскольку знаменатель в этом множителе, ${\displaystyle {\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}}$ , является нормой ℓ ₂ предыдущей производной, большие изменения параметра ослабляются, в то время как параметры, получающие малые изменения получают более высокие скорости обучения .

Хотя алгоритм разрабатывался для выпуклых задач , AdaGrad успешно применяется для невыпуклой оптимизации .

RMSProp

RMSProp (от англ. Root Mean Square Propagation ) — это метод, в котором настраивается для каждого параметра. Идея заключается в делении скорости обучения для весов на скользящие средние значения недавних градиентов для этого веса . Таким образом, первое скользящее среднее вычисляется в терминах среднеквадратичного

${\displaystyle v(w,t):=\gamma v(w,t-1)+(1-\gamma )(\nabla Q_{i}(w))^{2}}$

где, ${\displaystyle \gamma }$ является коэффициентом забывания.

Параметры обновляются как

${\displaystyle w:=w-{\frac {\eta }{\sqrt {v(w,t)}}}\nabla Q_{i}(w)}$

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

Adam

Adam (сокращение от «метод адаптивной оценки моментов», англ. Adaptive Moment Estimation ) — это обновление оптимизатора RMSProp . В этом оптимизационном алгоритме используются скользящие средние как градиентов, так и вторых моментов градиентов. Если даны параметры ${\displaystyle w^{(t)}}$ , а функция потерь ${\displaystyle L^{(t)}}$ , где ${\displaystyle t}$ отражает индекс текущей итерации (отчёт начинается с ${\displaystyle 0}$ ), пересчёт параметра алгоритмом Adam задаётся формулами

${\displaystyle m_{w}^{(t+1)}\leftarrow \beta _{1}m_{w}^{(t)}+(1-\beta _{1})\nabla _{w}L^{(t)}}$

${\displaystyle v_{w}^{(t+1)}\leftarrow \beta _{2}v_{w}^{(t)}+(1-\beta _{2})(\nabla _{w}L^{(t)})^{2}}$

${\displaystyle {\hat {m}}_{w}={\frac {m_{w}^{(t+1)}}{1-\beta _{1}^{t+1}}}}$

${\displaystyle {\hat {v}}_{w}={\frac {v_{w}^{(t+1)}}{1-\beta _{2}^{t+1}}}}$

${\displaystyle w^{(t+1)}\leftarrow w^{(t)}-\eta {\frac {{\hat {m}}_{w}}{{\sqrt {{\hat {v}}_{w}}}+\epsilon }}}$

где ${\displaystyle \epsilon }$ является малой добавкой, используемой для предотвращения деления на 0, а ${\displaystyle \beta _{1}}$ и ${\displaystyle \beta _{2}}$ являются коэффициентами забывания для градиентов и вторых моментов градиентов соответственно. Возведение в квадрат и квадратный корень вычисляются поэлементно.

Естественный градиентный спуск и kSGD

Основанный на фильтре Кальмана стохастический градиентный спуск ( англ. Kalman-based Stochastic Gradient Descent , kSGD) является онлайновым и офлайновым алгоритмом для параметров обучения для статистических задач для моделей , куда входят линейные модели , нелинейные модели , обобщённые линейные модели , и нейронные сети с как частный случай. Для онлайновых задач обучения kSGD является частным случаем фильтра Кальмана для задач линейной регрессии, частным случаем для задач нелинейной регрессии и может рассматриваться как инкрементальный метод Гаусса — Ньютона . Более того, ввиду связи kSGD с фильтром Кальмана и связи естественного градиентного спуска с фильтром Кальмана , kSGD является серьёзным улучшением популярного естественного метода градиентного спуска.

Преимущества kSGD по сравнению с другими методами:

(1) нечувствителен к числу условий задачи,

(2) имеет робастный выбор гиперпараметров,

(3) имеет условие останова.

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

Для описания алгоритма предположим, что функция ${\displaystyle Q_{i}(w)}$ , где ${\displaystyle w\in \mathbb {R} ^{p}}$ , определена с помощью ${\displaystyle (Y_{i},X_{i})\in \mathbb {R} \times \mathbb {R} ^{d}}$ так, что

${\displaystyle \nabla _{w}Q_{i}(w)={\frac {Y_{i}-\mu (X_{i},w)}{V(\mu (X_{i},w))}}\nabla _{w}\mu (X_{i},w)}$

где ${\displaystyle \mu (X_{i},w)}$ функция усреднения (то есть ожидаемое значение ${\displaystyle Y_{i}}$ от ${\displaystyle X_{i}}$ ), а ${\displaystyle V(\mu (X_{i},w))}$ является функцией дисперсии (то есть дисперсия ${\displaystyle Y_{i}}$ для ${\displaystyle X_{i}}$ ). Тогда пересчёт параметра ${\displaystyle w(t+1)}$ и пересчёт ковариантной матрицы ${\displaystyle M(t+1)}$ задаются следующими выражениями

${\displaystyle p=\nabla _{w}\mu (X_{t+1},w(t))}$

${\displaystyle m=\mu (X_{t+1},w(t))}$

${\displaystyle v=M(t)p}$

${\displaystyle s=\min \lbrace \gamma _{1},\max \lbrace \gamma _{2},V(m)\rbrace \rbrace +v^{\mathsf {T}}p}$

${\displaystyle w(t+1)=w(t)+{\frac {Y_{t+1}-m}{s}}v}$

${\displaystyle M(t+1)=M(t)-{\frac {1}{s}}vv^{\mathsf {T}}}$

где ${\displaystyle \gamma _{1},\gamma _{2}}$ являются гиперпараметрами. Пересчёт ${\displaystyle M(t)}$ может привести к тому, что ковариантная матрица станет неопределённой, что можно избежать за счёт умножения матрицы на матрицу. ${\displaystyle M(0)}$ может быть любой положительно определённой симметричной матрицей, но обычно берётся единичная матрица. Как заметил Патель , для всех задач, не считая линейной регрессии, требуются повторные прогоны для обеспечения сходимости алгоритма, но не приведены теоретические детали или детали реализации. В тесно связанном офлайновом мультипакетном методе для нелинейной регрессии, проанализированным Бертсекасом , для доказательства сходимости использовался коэффициент забывания при пересчёте ковариантной матрицы.

Методы второго порядка

Известно, что стохастический аналог стандартного (детерминированного) алгоритма Ньютона — Рафсона (метод «второго порядка») даёт асимптотически оптимальный или почти оптимальный вид итеративной оптимизации в условиях стохастической аппроксимации. Метод, который использует прямое вычисление матриц Гессе членов суммы в эмпирической функции риска, разрабатывали Бёрд, Хансен, Носедаль и Сингер . Однако, прямое определение требующихся матриц Гессе для оптимизации может оказаться невозможным на практике. Практические и теоретически выглядящие методы для версии второго порядка алгоритма SGD, который не требует прямой информации о гессиане, дали Сполл и другие (Менее эффективный метод, основанный на конечных разностях вместо одновременного пересчёта, дал Рупперт ). Эти методы, не требуя напрямую информацию о гессиане, базируются либо на значениях членов суммы в эмпирической функции риска, приведённой выше, либо значениях градиентов членов суммы (то есть ввода SGD). В частности, оптимальность второго порядка асимптотически достижима без непосредственного вычисления матриц Гессе членов суммы в эмпирической функции риска.

Комментарии

См. также

• Координатный спуск — изменяет одну координату за раз
• Линейный классификатор
• Онлайновое машинное обучение

Примечания

Литература

Литература для дальнейшего чтения

• Dimitri P. Bertsekas. Nonlinear Programming. — 2nd. — Cambridge, MA.: Athena Scientific, 1999. — ISBN 978-1-886529-00-7 . .
• Dimitri P. Bertsekas. Convex Analysis and Optimization. — Athena Scientific, 2003.
• Léon Bottou. Stochastic Learning // . — Springer, 2004. — Т. 3176. — С. 146—168. — (LNAI). — ISBN 978-3-540-23122-6 .
• Davidon W.C. [187–197 New least-square algorithms] // Journal of Optimization Theory and Applications. — 1976. — Т. 18 , № 2 . — doi : .
• Richard O. Duda, Peter E. Hart, David G. Stork. Pattern Classification. — 2nd. — Wiley , 2000. — ISBN 978-0-471-05669-0 .
• Krzysztof C. Kiwiel. Convergence of approximate and incremental subgradient methods for convex optimization // SIAM Journal on Optimization. — 2004. — Т. 14 , № 3 . — С. 807—840 . — doi : .
• Jan A. Snyman, Daniel N. Wilke. . — 2. — Springer , 2018. — С. xxvi+372. — (Springer Optimization and Its Applications Vol. 133). — ISBN 978-3-319-77585-2 .
• James C. Spall. . — Wiley , 2003. — ISBN 978-0-471-33052-3 . .

Ссылки

• (неопр.) . 3Blue1Brown (16 октября 2017).