Как на практике сходится оптимальный метод решения седловых задач. (сложный - можно делать небольшой группой).

В этом году на конференции НИПС 2022 была вот такая статья . В ней предложен оптимальный метод решения седловых задач с разными константами сильной выпуклости и вогнутости. На примере какой-нибудь небилинейной выпукло-вогнутой задачи исследуйте как сходится предложенный метод. Насколько теоретические оценки скорости сходимости соответствуют практическим наблюдениям? P.S. Пример небилинейной седловой задачи:

Как на практике сходится оптимальный метод решения седловых билинейных задач. (сложный - можно делать небольшой группой).

В этом году на конференции НИПС 2022 была вот такая статья. В ней предложен оптимальный метод решения седловых билинейных задач с разными константами сильной выпуклости и вогнутости. На примере какой-нибудь билинейной выпукло-вогнутой задачи исследуйте как сходится предложенный метод. Насколько теоретические оценки скорости сходимости соответствуют практическим наблюдениям? P.S. Пример билинейной седловой задачи:

Нащупывание равновесия по Вальрасу. (простой).

Посмотрите вот это видео. Решите (оформите) упражнение 4.7 из пособия. Реализуйте алгоритм и проверьте его работу на практике.

Поиск вектора Page Rank. (сложный).

Посмотрите видео (на предмет постановки задачи Google problem и задачи поиска вектора PageRank). Изучите статью 1, статью 2, статью 3. Попробуйте реализовать метод MCMC и еще парочку приглянувшихся методов для задачи поиска вектора PageRank. Опредедите, какой метод и в каком смысле лучше работает.

Чувствительность безградиентных методов оптимизации к шуму не случайной природы. (сложный).

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

Градиентный клиппинг. (сложный).

Посмотрите вот это видео. В различных моделях обучения возникают задачи стохастической оптимизации, в которых у градиентов имеются тяжелые хвосты. Для лучшей практической работы стандартных методов типа SGD используется клиппирование (пробатченного) стохастического градиента. Такой проект мы делали летом со школьниками в Сируисе. В результате было сделано вот это

• Лендинг
• GitHub
• PyPi
• Флайер

Оказывается, для выпуклых задач есть довольно симпатчиная математика, стоящая за всем этим (ссылка) Проект заключается в том, чтобы подобрать новые примеры (классы) задач обучения, на которых клиппированные методы работают лучше неклипированных.

Вокруг методов Монте-Карло. (простой).

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

SVM.

Проект на у мение находить литературу и выбирать наилучшие подходы. В классической задаче обучения машины опорных векторов (support-vector machine) предложите эффективные способы решения такой задачи, в зависимости от размерности и числа слагаемых (длины обучаемой выборки), а также о того, какой параметр регуляризации. SVM - представляет собой яркий пример класса выпуклых негладких задач вида суммы.

Тензорные методы.

На примере минимизации логистической регрессии попробуйте объяснить эффективность тензорных методов, например, методов типа Ньютона (подсказка: вычисление гессиана суммы до определенного момента «незаметно» на фоне обращения гессиана) для случая умеренных размерностей пространства переменных. Для мотивации см. статью. В частности, попопробуйте реализовать метод из статьи.

Visual Permutation Learning.

Статья

На вход вашей сетке должны подаваться изображения в которых с разной силой выражен один признак (например улыбка) (для начала можете использовать MNIST). Причем картинки НЕ ДОЛЖНЫ БЫТЬ отсортированы относительно этого признака. Ваша задача отсортировать эти картинки и вернуть permutation matrix (матрицу, отвечающую за правильный порядок изображений). Предлагается использовать пакет CVXPY и самим сформулировать задачу оптимизации так, чтобы она решалась ( CVXPY не работает с дискретными задачами)

A Convergent Variant of the Nelder–Mead Algorithm.

Статья

Реализовать алгоритм из данной статьи, сравнить его с scipy.minimize(method="Nelder-Mead") на стандартных функциях (см. Таблицу в статье)

Distributed convex optimization with limited communications.

Статья

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

Speeding up Convolutional Neural Networks with Low Rank Expansions

Статья

В статье предложен двухэтапный подход для ускорения свёрточных нейронных сетей, основанный на тензорном разложении. На первом шаге решается нелинейная задача наименьших квадратов, чтобы посчитать низкоранговое CP разложение для свёрточного слоя, на втором шаге cверточный слой заменяется его низкоранговым приближением. Реализовать метод предложенный в данной статье. Проверить его работу на CPU для AlexNet. Реализовать подобный подход, используя разложение Такера и сравнить оба подхода.

Методы второго порядка для Physics-informed Neural Networks В работе [1] было предложено решать граничные и начальные задачи для уравнений в частных производных и обыкновенных дифференциальных уравнений с использованием нейронных сетей. Решение приближается в виде нейронной сети, а веса выбираются так, чтобы норма невязки была минимальна в некотором наборе точек. Спустя 20 лет метод получил второе рождение в работе [2] (нейронные сети получили название Physics informed Neural Networks = PiNN) и с тех пор активно исследуется для различных прямых и обратных задач [3]. Цель данного проекта состоит в том, чтобы проверить, можно ли использовать методы второго порядка, чтобы ускорить обучение (оптимизацию) PiNN. С вычислительной точки зрения возможность использовать Гессиан нейронной сети появляется из-за того, что автоматическое дифференцирование позволяет получить произведение гессиана (матрицы вторых производных) на произвольный вектор почти с такой же вычислительной сложностью как и градиент. Такое произведение может быть позже использовано, например, в методе сопряженных градиентов для того, чтобы получить оценку произведения обратного гессиана на градиент. Более подробно эта процедура описана в [4] и [5].

Литература:

• [1] — Lagaris IE, Likas A, Fotiadis DI. Artificial neural networks for solving ordinary and partial differential equations. IEEE transactions on neural networks. 1998 Sep;9(5):987-1000.
• [2] — Raissi M, Perdikaris P, Karniadakis GE. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational physics. 2019 Feb 1;378:686-707.
• [3] — Karniadakis GE, Kevrekidis IG, Lu L, Perdikaris P, Wang S, Yang L. Physics-informed machine learning. Nature Reviews Physics. 2021 Jun;3(6):422-40.
• [4] — Byrd RH, Chin GM, Neveitt W, Nocedal J. On the use of stochastic hessian information in optimization methods for machine learning. SIAM Journal on Optimization. 2011 Jul 1;21(3):977-95.
• [5], Section 6 — Bottou L, Curtis FE, Nocedal J. Optimization methods for large-scale machine learning. Siam Review. 2018;60(2):223-311.

Поиграться с диффузионными моделями.

Ссылка.

Диффузионные модели сегодня часто используются на практике для задач генерации из распределения данных (чаще всего, изображений). В рамках проекта предлагается рассмотреть какую-нибудь простую диффузионную модель, разобраться в спейифике обучения таких моделей с точки зрения оптимизации и проделать несколько своих численных экспериментов.

Построение оптимального криптовалютного портфеля.

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

Изучение методов оптимизации в непрерывном времени.

Статья

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