Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Стохастический анализ в задачах
29 октября 2016 г. 11:00–15:00, г. Москва, ауд.401 МЦНМО
 


Инкрементальный метод Ньютона для больших сумм функций

А. О. Родоманов

Национальный исследовательский университет "Высшая школа экономики", г. Москва
Дополнительные материалы:
Adobe PDF 2.9 Mb

Количество просмотров:
Эта страница:291
Материалы:39
Youtube:



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

Дополнительные материалы: presentation_1.pdf (2.9 Mb)
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024