Александр Владимирович Гасников

Еще во времена Эйлера и Лагранжа стал популярным тезис о том, что «природа говорит на языке оптимизации». И, действительно, вариационные принципы в механике, теоретической физике и даже в экономике являются ярким тому подтверждением. Однако в последние десятилетия в научной среде резко выросла роль анализа данных и глубокого обучения, в частности. Подобно приведенному выше тезису, мотивированному механическими аналогиями, сейчас мы также можем сказать, что современный анализ данных если не говорит на языке оптимизации, то уж точно (в конечном счете) сводится к задачам оптимизации. Таким образом, задачи оптимизации и эффективные алгоритмы их решения являются важной составляющей совершенно разных исследований. В части таких постановок задач имеется доступ только к значению функции (возможно, зашумленному). Например, если для вычисления функции, в свою очередь, требуется запуск некоторой программы, которая может находить значение функции лишь приближенно (чем точнее, тем дороже это будет стоить).

Как решать такие задачи? Естественная идея — сводить решение таких задач к задачам, в которых доступен градиент целевой функции, с помощью аппроксимации градиента конечными разностями. Ведь градиентные методы хорошо и давно разработаны. Но что делать, если целевая функция негладкая? Например, |x|. В данном случае невозможно гарантировать аппроксимацию производной в решении задачи минимизации — точке 0. Более того, если функция задана неточно, то при стремлении шага конечной разности к нулю возникает неустойчивость и конечная разность (за счет ошибки вычисления целевой функции в числители и стремящегося к нулю знаменателя) может стремиться к бесконечности.

Замечательно, что в данной науке получаются достаточно изящные и простые решения. Чтобы описать основной результат, сначала заметим, что имеется сразу несколько критериев качества работы алгоритма (выдающего решение задачи оптимизации с заданной точностью по функции):

1. Число вычислений значения функции (хотим чтобы оно было минимальным среди всех методов);
2. Число последовательных итераций (хотим чтобы оно также было минимальным среди всех методов с минимальным числом вычислений функции);
3. Максимально допустимый уровень (вообще говоря, враждебного) шума в значении функции, при котором еще можно достичь заданную точность решения (хотим чтобы это число было максимально большим среди всех методов).

Оказывается, что существует алгоритм, который при весьма общих условиях оптимален (с точностью до логарифмических множителей) по всем трем критериям! Это довольно неожиданно, потому что кажется, что чем быстрее алгоритм, тем он должен быть чувствительнее к шуму. Как правило, это так и есть. Но вот тут мы столкнулись с такой простой ситуацией.

В 2–3 лекциях мы постараемся с помощью вполне элементарной математики объяснить, как такое могло получиться. На лекциях потребуется погрузиться немного в современные численные методы оптимизации и попутно освоить несколько общезначимых теорем анализа (формулу дифференцирования под знаком интеграла, формулу Стокса), а также соприкоснуться с очень красивым явлением — концентрацией равномерной меры на многомерной евклидовой сфере.

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

Литература

• Gasnikov A.V. et al. The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems // ICML 2022 https://arxiv.org/pdf/2201.12289.pdf
• Dvinskikh D. et al. Gradient-Free Optimization for Non-Smooth Minimax Problems with Maximum Value of Adversarial Noise // arXiv preprint, 2022. https://arxiv.org/pdf/2202.06114.pdf
• Novitskii V., Gasnikov A. Improved exploitation of higher order smoothness in derivative-free optimization // Optimization Letters. – 2022. – P. 1-13.