Минимаксная оптимизация с малоразмерным блоком без точного решения внутренних задач

В докладе рассматривается задача minₓ∈ℝⁿ maxᵧ∈ℝᵐ f(x,y) при m ≪ n, причём число обращений к оракулу учитывается для каждого блока отдельно.

Стандартный подход использует вложенную схему: метод секущих плоскостей по y, внутри которого ускоренный метод решает каждую подзадачу с точностью ε. Сложность такой схемы составляет O(m√κ log²(1/ε)) вычислений градиента. Мы покажем, что точное решение внутренних задач не требуется.

Предлагаемый метод, перенос сертификата, поддерживает сильно выпуклую нижнюю модель одного среза f и использует её для тёплого старта короткого ускоренного процесса на следующем срезе. Каждый запрос к малому блоку либо сокращает локализующее множество, либо, в силу вогнутости по y, переносит нижнюю модель на выпуклую комбинацию двух срезов с гарантированным приростом. Ни одна внутренняя задача не решается с точностью ε.

При m = 1 метод находит ε-седловую точку с сертификатом за O(√κ log(1/ε)) вычислений градиента и O(log(1/ε)) запросов к малому блоку; эта оценка оптимальна и сохраняется, даже если f(x,) лишь вогнута и липшицева.

Для произвольного m общее число запросов составляет O((m + √(mκ)) log(1/ε)) при оптимальном числе запросов к малому блоку.