Почему стохастический градиентный спуск не сходится?

👍 Многие привыкли использовать SGD(stochastic gradient descent), но не все знают, что он гарантированно(!) не сходится в случае постоянного шага (learning rate) даже для самой приятной в мире функции - сильно выпуклой квадратичной (даже в среднем).😰

🧠 Почему так? Дело в том, что в SGD на каждой итерации на самом деле решается другая задача, построенная по выбранным данным. И эта задача на батче может радикально отличаться от полной задачи (однако, внимательный читатель может отметить, что это не гарантирует очень плохой шаг😬). То есть на каждой итерации мы на самом деле сходимся, но к минимуму другой задачи, и каждую итерацию мы меняем правила игры для метода, не давая ему ему пройти больше одного шага. 👊

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

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

👨‍💻 Код для построения видосов.