Link Search Menu Expand Document

Выбор темы

🗓 25 февраля. 🦄 5 баллов.

К этому моменту необходимо лично согласовать с преподавателем тему проекта и высокоуровневое описание процесса работы над ним.

Главное требование к теме проекта - вам должно быть прикольно его делать, тема должна вас живо интересовать. Второе требование - он должен быть связан с методами оптимизации (хотя бы как-то 🙂). Тему проекта необходимо придумать\найти\выбрать самостоятельно. В качестве вдохновения можно посмотреть на лучшие проекты студентов прошлых лет:

Проекты из слака от лектора Гасникова А.В.

  • Оптимальные алгоритмы VR для седловых задач вида суммы

    Оптимальные (ускоренные) методы для седловых задач.
    В последнее время становится все более и более популярным (в том числе в связи с приложениями к децентрализованной оптимизации) рассматривать ускоренные методы для седловых задач (с билинейной седловой частью и более общие). Постановки задачи могут включать композиты, структуру суммы и т.п.  Тем не менее, до сих пор в общем случае не получены нижние оценки и оптимальные методы (нижняя оценка https://link.springer.com/content/pdf/10.1007/s10107-021-01660-z.pdf совсем не покрывает все интересные случаи). Известны только различные частные случае, где такая оптимальность имеет место. Среди прочего отметим недавнюю работу https://arxiv.org/pdf/2112.15199.pdf  и цитированную там литературу. Из открытых вопросов здесь, прежде всего, отметим работы, посвященные оптимальным алгоритмам для седловых задач вида суммы https://arxiv.org/pdf/2103.08280.pdf и https://arxiv.org/pdf/2102.08352.pdf. Зазор, который тут есть заключается в том, что нижние оценки первой статьи из таблицы 1 до сих пор не понятно как достигать. Во второй статье предложен алгоритм, который достигает нижних границ из таблицы 2 (но не первой таблицы). Тем не менее, недавно появилась статья https://arxiv.org/pdf/2102.13643.pdf, в которой в частном случае показывается как нижняя оценка из таблицы 1 достигается… В общем случае вопрос, насколько мне известно, является открытым. Было бы здорово попробовать с этим разобраться…

    Стоит отметить важный момент, что даже для обычных седловых задач (без структуры суммы) до сих пор нет понимание насколько нижние оценки https://link.springer.com/content/pdf/10.1007/s10107-019-01420-0.pdf https://arxiv.org/pdf/1912.07481.pdf полученные на задачах, в которых седловая часть билинейная, точны в общем случае. Ведь существующие методы не достигают их (точнее достигают но лишь в билинейном случае) https://arxiv.org/pdf/2112.15199.pdf п. 5; https://arxiv.org/pdf/2111.12743.pdf; https://arxiv.org/pdf/2011.06572.pdf Appendix C.\ P.S.* Кстати сказать, похоже есть довольно интересная завязка сюжета из последней статьи на проблему существования зазора  VR для седел, о котором в основном тексте говорилось. Дело в том, что VR (неускоренное) в условиях относительной гладкости (для выпуклой оптимизации) приводит к лишним факторам https://hal.inria.fr/tel-03389344/document раздел 6.5б, причем, похоже не устранимым (там же раздел 3). Собственно, видимо поэтому если пойти по пути https://arxiv.org/pdf/2011.06572.pdf  беря за основу метод VR для седел из https://arxiv.org/pdf/2102.13643.pdf получается, что в самом методе VR для седел сидит как бы лишний \sqrt{m} (ь - число слагаемых). Но он может быть и не лишний, потому что, если бы его не было, то мы бы пришли (используя конструкцию типа https://arxiv.org/pdf/2011.06572.pdf  ) к противоречию с нижними оценками для VR методов для задач выпуклой оптимизации.

  • Стохастическая онлайн оптимизация в условиях типа острого миниума

    Предварительно посмотреть вот это видео Код доступа: ?2rs@QU6, в котором говорит о связи онлайн и офлайн подходов к задачам стох. оптимизации. И упоминается открытая задача, связанная с условием типа острого минимума. Офлайн подход в этом случае проработан (см. ссылки ниже, в частности эту), а онлайн не до конца (а только в случае равномерной выпуклости). Задача - проработать до конца. “На коленке” все посмотрел. Все получается. То есть из этого может получится новый результат. Чтобы сделать то что нужно, предварительно необходимо посмотреть вот эти две статьи https://arxiv.org/pdf/2202.01805.pdf (наиболее важная часть этой статьи связана с окрестностями условия (5.128) http://ie.sharif.ir/~sp/SPbook.pdf) https://pubsonline.informs.org/doi/pdf/10.1287/10-SSY010\ Собственно, если во второй статье подметить, что реально нужна не $\rho$-равномерная выпуклость (\rho >= 2), а именно просто выпуклость и условие роста в решении (условие роста типа (5.128), см. выше, т.е. \rho >= 1), то можно применять рестарты, которые описаны в этой статье. Чтобы по-простому понять идею рестартов, можно посмотреть указание к упражнению 2.3 вот тут при \delta = 0. Более того, если посмотреть на указание к упражнению 5.4 в том же пособии, то можно попробовать обобщить этот результат и на седловые задачи с условием в седле типа (5.128), см. работу https://arxiv.org/pdf/2202.01805.pdf. Но это не сразу, а на потом. А сначала нужно попробовать сделать именно выпуклый случай.

  • Проекты от Константина Мищенко

    Хочу предложить несколько проектов, может кому-то будет интересно:

    1. В приложенном черновике я произвёл попытку получить экстраградиентный аналог метода Ньютона из моей недавней статьи. К сожалению, я пока что не вижу как довести доказательство до конца (и не уверен, возможно ли это). Предлагаю всем желающим посмотреть на эту задачу, если её получится добить, то можно будет смело писать статью.
    2. Во втором черновике (он скоро появится на архиве) предложен новый локальный метод для распределённой оптимизации. В отличии от предыдущих работ, таких как Scaffold, в этом методе удалось показать, что есть большая польза от локальных шагов. Особенно ценно здесь было бы получить улучшенный стох анализ (в прикладываемой статье нет улучшения от числа нод n), но кажется, что это довольно трудно. Если будет интерес двигаться в каком-то направлении, надо будет с Питером Рихтариком это обсудить (он соавтор приложенной работы), чтобы избежать пересечений с ним.
    3. Есть идея поделать стохастические методы второго порядка. Кажется, что задача очень плохо решается в случае регуляризованного/кубического Ньютона (по крайней мере я ничего интересного не придумал), но есть идея попробовать взять за основу кубический экстраградиент и посмотреть как он сочетается с variance reduced extragradient. Поскольку доказательство здесь через расстояния до решения, а не функциональные значения, есть куда больший шанс, что что-то выйдет.

Прочие идеи проектов

  • Приложения ускоренных альтернированных методов.

    В рамках проекта предлагается развить идею приложения техник ускорения Нестерова для методов альтернированной оптимизации. Хорошее введение в альтернированные методы. И приложить это для задач поиска тензора канонического разложения, разложения Таккера и Tensor Train. Данные методы позволяют эффективно решать некоторые невыпуклые задачи и являются практическим стандартом де-факто в ряде областей.

  • Методы оптимизации в прохождении компьютерных игр.
  • Создание питон библиотеки - черного ящика для бенчмаркинга методов оптимизации с разными запусками, единым интерфейсом, построением графиков.
  • Еще идеи проектов
  • Есть парабола. Пробуем аппроксимировать параболу с помощью fully-connected нейросети, не очень маленькой. Пытаемся обучать эту сетку sgd, страдаем. Изучаем почему так. Стоит посмотреть следующее видео с недавними результатами по теме.
  • Оптимальное инвестирование деняк. Есть Tinkoff инвестиции, у них есть python API. Давайте возьмем немного денег, реализуем парочку интересных стратегий поторговать автоматически, сравним.
  • Изучение сходимости стохастических градиентных методов в непрерывном времени. https://fmin.notion.site/SDE-simulation-40dbe2a5baf04f718c9690ea36e76ffb
  • Поиграться с новыми моделями генерации https://lilianweng.github.io/lil-log/2021/07/11/diffusion-models.html Критерий оценивания: бинарный (успели согласовать тему - 5 баллов, не успели - 0 баллов).

Project proposal

🗓 18 марта. 🦄 25 баллов.

На мой взгляд - это важнейший этап проекта. Тут нужно очень четко определить куда и как двигаться, какие тропы уже пройдены другими людьми. Project Proposal должен быть выполнен с помощью \(\LaTeX\) и системы цитирования bibtex. Обратите внимание на следующие аспекты:

  • Название проекта. 🦄 1/25
  • Abstract (краткое описание проекта в один абзац). 🦄 2/25
  • Описание проекта (обратите внимание на конкретность постановки задачи и её реалистичность). 🦄 5/25
  • Outcomes - опишите, что конкретно будет выходом Вашего проекта (код, теорема, численные эксперименты, телеграм бот, веб сайт, приложение, рассказ). 🦄 2/25
  • Литературный обзор (краткий обзор релевантных источников по теме, со ссылками на них - минимальное число источников - 7). 🦄 5/25
  • Детальный план работ. Ясно, что в процессе выполнения проекта он будет меняться, однако наличие плана здесь лучше его отсутствия. 🦄 5/25
  • Метрики качества. По возможности, приведите формальные и измеряемые показатели, по которым можно оценивать Ваше решение\ проект - это могут быть конкретные метрики качества алгоритмов, соц. опрос, логическое доказательство и т.д. 🦄 5/25

Для удобства приведен 📝 \(\LaTeX\) шаблон с 📜 примером.

Draft 1

🗓 1 апреля. 🦄 10 баллов.

Постер в латехе с разделением на разделы, объяснением - что в каком разделе где будет. Для удобства приведен 📝 \(\LaTeX\) шаблон с 📜 примером. На этом моменте дается фидбек и ставятся задачи к следующему этапу.

Draft 2

🗓 8 апреля. 🦄 10 баллов.

На этом моменте дается фидбек и ставятся задачи к защите проекта.

Защита

🗓 15 апреля. 🦄 20 баллов.

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

Publishing plan

🗓 22 апреля. 🦄 10 баллов.

На основании результатов проделанной работы мы совместно решаем каким образом необходимо опубликовать проделанный труд. Это может быть:

  • статья в журнале
  • статья на конференции
  • статья для летней школы
  • доклад на конференции
  • публикация на вашем сайте
  • статья в блоге

В частности, этот план содержит конкретные даты, выбранный журнал\конфу\место, куда это будет подаваться.

Публичная защита

🗓 29 апреля. 🦄 20 баллов.

Подведение итогов. Финальная защита. Здесь в первую очередь оценивается выступление студента. Оно должно быть понятным, структурированным, интересным.