Стохастический градиентный спуск со случайными перестановками: простой анализ со значительными следствиями

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