Учёные из лаборатории продвинутой комбинаторики и сетевых приложений МФТИ в сотрудничестве с исследователями из Сколтеха, Научного института Вайцмана и MBZUAI, разработали ускоренный безградиентный метод для задач негладкой выпуклой оптимизации в условиях шума с бесконечной дисперсией. Статья была отобрана и опубликована в сборнике конференции NeurIPS 2023.
Оптимизация – раздел математики, в которой исследователи ищут способы найти минимальные и максимальные значения функций. Если у выпуклой функции можно взять производную, то найти минимум достаточно просто – нужно найти точку, где производная равняется нулю. Однако существуют негладкие функции, у которых не во всех точках можно взять производную и решить задачу простым методом не получается. Для таких ситуаций математики разрабатывают иные безградиентные подходы. Алгоритм, предложенный в статье, работает в постановке, в которой минимизируется негладкая выпуклая стохастическая функция с бесконечной дисперсией. Выпуклость функции говорит нам о том, сколько у неё есть минимумов — если функция выпуклая, то минимум у неё всего один.
У стохастической функции значение в точке зависит от некоторой вероятности и не определено каким-то одним ответом. Например, к истинному значению функции может каждый раз прибавляться случайный шум. Вероятность ответа определяется распределением, у которого есть определённые свойства — среднее (обычно равное истинному значению функции), дисперсия и т.д.. Авторов исследования интересовала ситуация, в которой у распределения, влияющего на значение функции бесконечная дисперсия. Это означает, что значения в распределении могут находится бесконечно далеко от среднего с ненулевой вероятностью и нет никаких ограничений на то, каким этот разброс может быть. Такие данные часто появляются в реальном мире — например, в биологии и физике. Новый алгоритм позволяет справиться с этой проблемой и находит минимум с высокой вероятностью за минимально возможное число шагов.
«Эта статья — результат огромной работы команды специалистов из нашей лаборатории продвинутой комбинаторики и сетевых приложений МФТИ. В ней исследуются безградиентные методы оптимизации в условиях сильнозашумленных данных. Из важного, в статье можно найти новейшие и нетривиальные теоретические результаты и новые оптимальные алгоритмы, которые являются основой работы. Самым сложным было объединить все новые и старые результаты воедино, преподнести их интересно и понятно для стороннего читателя, а также сохранить высокое качество во всех аспектах работы, от теории до экспериментов», — рассказывает Никита Корнилов, первый автор работы, магистрант МФТИ.
Алгоритм работает следующим образом. Сначала задаются начальные параметры алгоритма, после чего метод итеративно обращается к оракулу — метафорической сущности, которая может дать информацию о функции — чтобы узнать значения функции в двух близких точках. Между этими двумя значениями считается разность и с её помощью строится приближенный градиент — многомерный аналог производной, отражающий меру изменения функции. Используя приближенный градиент, алгоритм понимает, в какую сторону функция растёт, и делает шаг в обратную сторону — где, предположительно находится минимум. Все эти шаги повторяются до того момента, пока минимум не будет найден. Теорема сходимости, представленная в статье, гарантирует нахождение минимума за оптимальное число шагов с высокой вероятностью.
Кроме того, в алгоритме используется техника батчирования — прежде чем алгоритм принимает решение о дальнейшем движении, производится несколько независимых измерений и из всей этой информации собирается итоговый ответ с меньшей вероятностью ошибки. В работе были представлены интересные теоретические обоснования техники батчирования в случае сильно зашумленных данных, которые встречаются повсеместно. Это может стать неплохим подспорьем для будущих исследований и практических эвристик.
Безградиентные методы для работы в условиях сильного шума необходимы для решения задач многоруких бандитов, подбора гиперпараметров моделей искусственного интеллекта, в частности, в сфере Reinforcement Learning. Ученым удалось проверить эффективность предложенных алгоритмов в экспериментах.
Статья была принята на конференцию NeurIPS 2023. Эта ежегодная междисциплинарная конференция является главным мировым событием для исследователей в области машинного обучения, нейробиологии, статистики, оптимизации, компьютерного зрения, обработки естественного языка и других смежных областей. Такое признание на мировом уровне подытоживают огромную работу по исследованию безградиентых методов, которой занимается лаборатория продвинутой комбинаторики и сетевых приложений МФТИ.
«Наша работа ещё не окончена. Насколько эффективно наши алгоритмы работают в зависимости от размерности пространства — открытый вопрос, на который только предстоит найти ответ», — прокомментировал Никита Корнилов.
