Семинар Книгочтения

Используя оценки скорости сходимости к нулю для рекуррентного неравенства с прошлых докладов, мы, в качестве простых следствий, получим оценку скорости сходимости для Prox-SGD в разных случаях (например, сильно и несильно выпуклом) и метриках. Далее в явном виде получим скорость для случая UBV (uniformly bounded variance). Затем мы перейдём к частным случаям convex smooth stochastic trajectories, где сравним скорости сходимости.

Продолжим рассмотрение общей леммы (3.5) для обработки типичных рекуррентных соотношений, возникающих в анализе сходимости методов, подобных стохастическому градиентному спуску. Рассмотрим вопрос оптимальности полученной в ней оценки сверху, а также обсудим её следствия.

Резюмируем предыдущие разделы, посвященные оценке градиента в гладком случае. Перейдем к рассмотрению второго важного аспекта методов стохастического градиентного спуска - оптимальному выбору шага итерации.

Мы разберём алгоритм Prox-SGD, где к оптимизируемой функции добавляется регуляризатор. Для этого мы кратко разберём некоторые свойства prox-операторов. Затем мы разберём доказательство сходимости алгоритма при довольно общих ограничениях на оракул градиента, которые включают последние три набора условий (uniformly bounded variance, convex smooth stochastic trajectories, finite sum problems).

Продолжим разбор третьей главы рассмотрением оптимизации конечных сумм и применяемых для этого методов уменьшения дисперсии: SAGA, SVRG/LSVRG и SDCA. Докажем теорему о сходимости метода L-SVRG.

Продолжим разбор третьей главы: выпуклая стохастическая оптимизация в гладком случае. При условиях L-гладкости, mu-квази сильной выпуклости, (mu,L)-сильной выпуклости и равномерной ограниченности дисперсии градиента докажем теорему сходимости для стохастического градиентного спуска. Разберем на примерах. И перенесём основной результат на условие выпуклых гладких стохастических траекторий.

Начнем разбор третьей главы: выпуклая стохастическая оптимизация в гладком случае. Разберем такие условия как L-гладкость, mu-квази сильная выпуклость, (mu,L)-сильная выпуклость, равномерная ограниченность дисперсии градиента. Докажем теорему сходимости для стохастического градиентного спуска.

Мы поговорим об онлайн-оптимизации с точки зрения характеристики качества Regret. Разбор будет идти по монографии F.Orabona «A modern introduction to online learning» (2019). На простых примерах мы разберём идею данной характеристики и приведём её оценки в простом случае и случаях разобранных ранее при разборе субградиентного спуска. После этого мы разберём случаи игры с противником в моделях 'обучение с экспертами' и 'многорукий бандит'.

Мы закончим обсуждение метода зеркального спуска с ограничениями рассмотрев сопряжённую задачу. Если останется время, то также поговорим об online постановке этого алгоритма.

Подведем резюме предыдущих трех докладов: рассмотрим алгоритм зеркального спуска, основанный на дивергенции Брэгмана; поговорим о свойствах дивергенции Брэгмана; докажем и сравним оценки скоростей сходимости для градиентного и зеркального спуска.

Мы обсудим нижние оценки для количества шагов и для точности решения для и сравним с полученными ранее результатами. Далее мы разберём стохастическую относительную непрерывность и результаты в данном случае. После этого перейдём к задаче минимизации с ограничениями.

На семинаре мы введем Stochastic Composite Mirror Descent алгоритм и проанализируем скорость его сходимости.

Мы кратко ознакомимся с разделом 1.3, содержащим заключительные замечания. Затем перейдем ко второй главе, где рассмотрим метод стохастического субградиента.

Закончим разбор раздела про близость решений эмпирической оптимизационной задачи и теоретической. Для этого мы сначала резюмируем разобранные результаты раздела, затем рассмотрим понятии функции s-роста и найдём оценку объема выборки, гарантирующую оптимальность решения для функций s-роста. Закончим доклад иллюстрацией полученных оценок на простом примере.

Будет разобрана оценка объёма выборки необходимого для того, чтобы приближённое решение эмпирической оптимизационной задачи было достаточно близко к решению теоретической задачи. Оценка получена при условии, что целевая функция сильно выпуклая.

На семинаре мы разберем доказательство теоремы, дающей оценку выборочной сложности оффлайн алгоритма (Sample Average Approximation) оптимизации стохастической оптимизационной задачи.

Также на этом заседании состоится обсуждение/голосование за название этого семинара.