классические методы оптимизации

Данный репозиторий содержит результаты работ, выполненнных в рамках курса "Методы оптимизации" в 4 семестре на КТ ИТМО. Преподаватель курса: Головкина Анна Геннадьевна

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

Структура репозитория

flowchart TD
  repo["root"]
  src["📁 src"]
  datasets["📁 datasets"]
  notebooks["📁 notebooks"]
  resources["📁 resources"]

  optimization["📄 optimization.py"]
  oracles["📄 oracles.py"]
  utils["📁 utils"]
  graphics["📄 graphics.py"]
  report["📄 RESEARCH_REPORT.md"]

  repo --> src
  repo --> datasets
  repo --> notebooks
  repo --> resources
  repo --> report
  src --> optimization
  src --> oracles
  src --> utils
  utils --> graphics

Loading

1. src содержит реализацию оптимизаций в файле optimization.py, реализацию оракулов в файле oracles.py и утилиты вроде общего кода для построения графиков, критериев остановки оптимизаций, проверок корректности оракулов, итп.
2. datasets содержит использованные в экспериментах датасеты, взятые отсюда.
3. notebooks содержит проделанные эксперименты, разделенные на 5 директорий по исследуемым методам.
4. resources содержит графики, используемые в RESEARCH_REPORT.md.

Оптимизации

Наиболее полезным в этом репозитории служит файл optimization.py. Помимо реализаций, он содержит подобранные в ходе экспериментов константы для запуска, разные стратегии выбора шага, хранение множества пунктов истории хода работы метода для анализа.

Оптимизации и краткое описание каждой:

1. Градиентный спуск $-$ классический метод с выбором стратегии для линейного поиска шага: константный шаг, стратегия Армихо, стратегия Армихо-Вульфа.
2. Метод Ньютона $-$ классический метод с аналогичным выбором стратегии линейного поиска.
3. Модифицированный градиентный спуск, в котором вместо градиента используется диагональ гессиана (без вычисления полного гессиана!).
4. Линейный метод сопряженных градиентов $-$ метод для быстрого решения СЛАУ, часто используется внутри других методов.
5. Нелинейный метод сопряженных градиентов с формулой Поляка-Рибьера $-$ модификация градиентного спуска, позволяющая оптимизировать направления спуска с эвристикой рестарта.
6. Усечённый метод Ньютона $-$ метод Ньютона, аппроксимирующий гессиан с помощью линейного метода сопряженных градиентов и с возможностью выбора стратегии для коэффициента шага.
7. L-BFGS $-$ один из лучших квазиньютоновских методов с ограниченным использованием памяти (ограничение является параметром метода).
8. Усеченный метод Ньютона с предобуславливанием аппроксимацией L-BFGS гессиана $-$ использует аппроксимированный гессиан в поиске направления линейным методом сопряженных градиентов, позволяя добиться более точного направления на внешней итерации метода и уменьшая его количество внутренних итераций.
9. Субградиентный метод $-$ классический метод решения задачи выпуклой оптимизации с возможностью выбора стартового шага и стратегией обратного корня, строящей сходящуюся к нулю последовательность коэффициентов для направления спуска.
10. Метод проксимального градиента $-$ классический проксимальный метод с параметром для адаптивного линейного поиска.
11. Быстрый метод проксимального градиента $-$ модификация соответствующего метода, использующая прошлые направления для текущего.
12. Метод Франка-Вульфа $-$ альтернативный метод условной оптимизации, использующий линейное приближение функции в $L^1$ шаре. Поддерживает классическое построение последовательности коэффициентов шагов и стратегию Армихо.
13. Метод барьеров $-$ логарифмический метод барьеров, позволяющий настраивать все параметры для стратегии выбора шага, а также поддерживающий метод Ньютона (рекомендуется) и L-BFGS (НЕ рекомендуется) в качестве внутреннего решателя.
14. Стохастический градиентный спуск $-$ градиентный спуск для больших ML-задач, позволяющий варьировать размер батча, количество эффективных эпох и стратегию выбора шага.
15. Stochastic Variance Reduced Gradient $-$ модификация стохастического градиентного спуска, гарантирующая сходимость к оптимуму за счет стремления стохастического шума к нулю.
16. Adam $-$ наиболее продвинутый и повсеместно используемый алгоритм оптимизации для ML-задач (до 2025 года) с варьированием всех внутренних параметров.
17. Subsampled Newton $-$ метод Ньютона для больших ML-задач, позволяющий за счет незначительного увеличения используемой времени и памяти по сравнению с стохастическим градиентным спуском значительно улучшать результат.

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

Исследовательский эксперимент

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

Результатом этих исследований стали улучшения классических результатов в 10-100 раз как по времени, так и по качеству, поэтому отчёт позволит понять все слабые и сильные стороны этого метода.

Авторы

1. Святослав Белкин $-$ полная реализация оптимизаций, проведение всего исследовательского эксперимента, контроль качества остальных экспериментов.
2. Арсений Мухаметшин $-$ полная реализация оракулов, проведение около $\frac{2}{5}$ экспериментов.
3. Станислав Фролов $-$ проведение около $\frac{3}{5}$ экспериментов.