Современные задачи оптимизации в машинном обучении часто оказываются плохо обусловленными — грубо говоря, их ландшафт имеет долины с резко различающейся кривизной. В таких случаях методы на основе градиентного спуска сходятся медленно: шаг, выбранный для устойчивости на одном участке, оказывается слишком малым на другом. Для ускорения сходимости широко применяются методы с механизмом импульса (momentum): классический метод Поляка — Heavy Ball (HB) — и метод Нестерова (ускоренный градиент). Оба эти метода используют идею накапливать «инерцию» градиента, благодаря чему могут двигаться по направлению оптимума быстрее обычного градиентного спуска. Однако, хотя импульс позволяет ускорить алгоритм, сам по себе он не решает проблему плохой обусловленности функции. В таких ситуациях на помощь приходит предобусловливание — масштабирование шагов оптимизации по разным координатам на основе дополнительной информации о функции, чтобы выровнять скорость сходимости по различным направлениям задачи. Всем привет! Меня зовут Степан Трифонов, я аналитик‑разработчик в Яндекс Пэй. Недавно мы с коллегами, Леонидом Левиным и Савелием Чежеговым, опубликовали научную статью Incorporating Preconditioning into Accelerated Approaches: Theoretical Guarantees and Practical Improvement, где ввели предобусловленные версии классических ускоренных методов — Preconditioned Heavy Ball (PHB) и Preconditioned Nesterov (PN) — и доказали для них оценки сходимости при весьма общих допущениях на предобусловливающую матрицу. Также мы провели численные эксперименты, которые продемонстрировали практический выигрыш новых алгоритмов по сравнению с обычными (непредобусловленными) методами HB и Нестерова. Читать далее