Аннотация:
В докладе рассматривается задача минимизации суммы большого (но конечного) числа гладких функций. Подобная задача регулярно возникает в машинном обучении при настройке алгоритма по данным путем минимизации эмпирического риска. Поскольку рассматриваемая задача принадлежит классу задач стохастической оптимизации, то ее можно решать с помощью стохастических градиентных методов. Однако скорость сходимости таких методов является сублинейной, поэтому этот подход не позволит получить решение задачи с большой точностью. Причиной сублинейной сходимости является наличие случайного шума при подсчете градиента, причем дисперсия этого шума в любой момент времени равномерно отделена от нуля. Если дополнительно учесть специфику рассматриваемой задачи (конечная сумма, а не произвольное мат. ожидание), то удается модифицировать стохастические градиентные методы таким образом, что дисперсия случайного шума начинает убывать к нулю с ростом числа итераций, при этом стоимость итерации самого метода практически не увеличивается. В результате, специальные методы типа стохастического градиента на каждой итерации вычисляют (в среднем) лишь одно слагаемое вместо всей суммы и при этом обладают линейной сходимостью.
Основной вопрос, служащий мотивацией данного доклада, следующий: возможно ли получить метод, который на каждой итерации будет вычислять лишь одно слагаемое вместо всей суммы, но при этом иметь не линейную, а суперлинейную сходимость? Оказывается, что да, это возможно, и такой метод получается с помощью специальной модификации классического метода Ньютона. В докладе будет подробно рассмотрен этот метод (инкрементальный метод Ньютона) вместе с доказательством его суперлинейной сходимости.
Доклад основан на статье http://www.jmlr.org/proceedings/papers/v48/rodomanov16.html.
