Сложность Oracle (оптимизация)

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

Формальное описание

Рассмотрим задачу минимизации некоторой целевой функции $f:{\mathcal {X}}\rightarrow \mathbb {R}$ (по некоторому домену ${\mathcal {X}}$ ), где $f$ известно, что он принадлежит некоторому семейству функций ${\mathcal {F}}$ . Вместо прямого доступа к ${\mathcal {f}}$ , предполагается, что алгоритм может получить информацию о $f$ через оракула ${\mathcal {O}}$ , что дает точку $\mathbf {x}$ в ${\mathcal {X}}$ , возвращает некоторую локальную информацию о $f$ в окрестностях $\mathbf {x}$ . Алгоритм начинается в некоторой точке инициализации $\mathbf {x} _{1}$ , использует информацию, предоставленную оракулом, для выбора следующей точки $\mathbf {x} _{2}$ , использует дополнительную информацию для выбора следующей точки $\mathbf {x} _{3}$ , и так далее.

В качестве конкретного примера предположим, что ${\mathcal {X}}=\mathbb {R} ^{d}$ ( $d$ -мерное евклидово пространство ) и рассмотрим алгоритм градиентного спуска , который инициализируется в некоторой точке $\mathbf {x} _{1}$ и происходит через рекурсивное уравнение

\mathbf {x} _{t+1}=\mathbf {x} _{t}-\eta \nabla f(\mathbf {x} _{t})

,

где $\eta$ это некоторый параметр размера шага. Этот алгоритм можно смоделировать в рамках вышеприведенной схемы, где заданы любые $\mathbf {x_{t}}$ оракул возвращает градиент $\nabla f(\mathbf {x_{t}} )$ , который затем используется для выбора следующей точки $\mathbf {x_{t+1}}$ .

В этой структуре для каждого выбора семейства функций ${\mathcal {F}}$ и оракул ${\mathcal {O}}$ , можно изучить, сколько вызовов/итераций оракула требуется, чтобы гарантировать некоторый критерий оптимизации (например, гарантировать, что алгоритм выдает точку $\mathbf {x} _{T}$ такой, что $f(\mathbf {x} _{T})-\inf _{\mathbf {x} \in {\mathcal {X}}}f(\mathbf {x} )\leq \epsilon$ для некоторых $\epsilon >0$ ). Это известно как сложность оракула этого класса задач оптимизации: а именно, такое количество итераций, при котором, с одной стороны, существует алгоритм, который, как доказуемо, требует для успеха только этого количества итераций (для любой функции из ${\mathcal {F}}$ ), а с другой стороны, есть доказательство того, что ни один алгоритм не может добиться успеха с меньшим количеством итераций равномерно для всех функций в ${\mathcal {F}}$ .

Подход сложности оракула по своей сути отличается от теории сложности вычислений , которая опирается на машину Тьюринга для моделирования алгоритмов и требует входных данных алгоритма (в данном случае функция $f$ ), чтобы быть представленным в виде небольшого количества строк в памяти. Вместо этого алгоритм не ограничен вычислительно, но его доступ к функции $f$ предполагается ограниченным. Это означает, что, с одной стороны, результаты оракула по сложности применимы только к конкретным семействам алгоритмов, которые обращаются к функции определенным образом, а не к любому алгоритму, как в теории сложности вычислений. С другой стороны, результаты применимы к большинству, если не ко всем итеративным алгоритмам, используемым на практике, не полагаются на какие-либо недоказанные предположения и приводят к тонкому пониманию того, как геометрия функции и тип информации, используемой алгоритмом, влияют на практическую производительность.

Общие настройки

Сложность Oracle применялась к довольно большому количеству различных настроек, в зависимости от критерия оптимизации, класса функции. ${\mathcal {F}}$ и тип оракула ${\mathcal {O}}$ .

С точки зрения критерия оптимизации, наиболее распространенным из них является поиск точки, близкой к оптимальной, а именно создание $f(\mathbf {x} _{T})-\inf _{\mathbf {x} \in {\mathcal {X}}}f(\mathbf {x} )\leq \epsilon$ для некоторых маленьких $\epsilon >0$ . Некоторые другие критерии включают в себя поиск приблизительно стационарной точки ( $\|\nabla f(\mathbf {x} _{T})\|\leq \epsilon$ ), или нахождение приближенного локального минимума.

Существует множество классов функций ${\mathcal {F}}$ которые были изучены. Некоторые распространенные варианты включают выпуклые , сильно выпуклые и невыпуклые функции, гладкие и негладкие функции (скажем, с точки зрения липшицевых свойств градиентов или производных более высокого порядка), области с ограниченной размерностью. $d$ , против областей с неограниченной размерностью и сумм двух или более функций с разными свойствами.

С точки зрения оракула ${\mathcal {O}}$ , принято считать, что для данной точки $\mathbf {x}$ , он возвращает значение функции в $\mathbf {x}$ , а также производные до некоторого порядка (скажем, только значение, значение и градиент, значение и градиент и гессиан и т. д.). Иногда изучают более сложные оракулы. Например, стохастический оракул возвращает значения и производные, искаженные случайным шумом, и полезен для изучения стохастической оптимизации . методов ^[1] Другой пример — проксимальный оракул , который по заданной точке $\mathbf {x}$ и параметр $\gamma$ , возвращает точку $\mathbf {y}$ минимизация $f(\mathbf {y} )+\gamma \|\mathbf {y} -\mathbf {x} \|^{2}$ .

Примеры результатов сложности оракула

Ниже приведены несколько известных результатов сложности оракула (вплоть до числовых констант) для получения ошибки оптимизации. $\epsilon$ для некоторых достаточно маленьких $\epsilon$ и по домену $\mathbb {R} ^{d}$ где $d$ не фиксировано и может быть сколь угодно большим (если не указано иное). Мы также предполагаем, что точка инициализации $\mathbf {x} _{1}$ удовлетворяет $\|\mathbf {x} _{1}-\mathbf {x} ^{*}\|\leq B$ по какому-то параметру $B$ , где $\mathbf {x} ^{*}$ — некоторый глобальный минимизатор целевой функции.

Класс функции	Оракул	Сложность Oracle
Выпуклый, $L$ -Липшицевый, фиксированный размер $d$	Значение + градиент	$d\log(LB/\epsilon )$ ^[2]
Выпуклый, $L$ -Липшиц	Значение + градиент	$(LB/\epsilon )^{2}$ ^[2]
Выпуклый, $\mu$ -Липшицев градиент	Значение + градиент	${\sqrt {\mu B^{2}/\epsilon }}$ ^[2]
$\lambda$ - Сильно выпуклый, $\mu$ -Липшицев градиент	Значение + градиент	${\sqrt {\mu /\lambda }}\cdot \log(B^{2}/\epsilon )$ ^[2]
Выпуклый, $\mu$ -Липшиц Гессен	Значение + градиент + гессиан	$(\mu B^{3}/\epsilon )^{2/7}$ ^[3]
$\lambda$ - Сильно выпуклый, $\mu$ -Липшиц Гессен	Значение + градиент + гессиан	$(\mu B/\lambda )^{2/7}+\log \log(\lambda ^{3}/\mu ^{2}\epsilon )$ ^[3]

Ссылки

^ Агарвал, Алех; Бартлетт, Питер; Равикумар, Прадип; Уэйнрайт, Мартин (май 2012 г.). «Теоретико-информационные нижние границы сложности оракула стохастической выпуклой оптимизации». Транзакции IEEE по теории информации . 58 (5): 3235–3249. arXiv : 1009.0571 . дои : 10.1109/TIT.2011.2182178 . S2CID 728066 .
^ Перейти обратно: ^а ^б ^с ^д Nesterov, Yurii (2018). Lectures on Convex Optimization . Springer. ISBN 978-3-319-91578-4 .
^ Перейти обратно: ^а ^б Арджевани, Йоси; Шамир, Охад; Шифф, Рон (28 мая 2018 г.). «Сложность Oracle методов второго порядка для гладкой выпуклой оптимизации». Математическое программирование . 178 (1–2): 327–360. arXiv : 1705.07260 . дои : 10.1007/s10107-018-1293-1 . S2CID 28260226 .

Дальнейшее чтение

Немировский, Аркадий; Юдин, Дэвид (1983). Сложность задач и эффективность методов оптимизации . Джон Уайли и сыновья.

Немировский, Аркадий (1994). «Информационная сложность выпуклого программирования (конспекты лекций)» (PDF) . Проверено 14 июня 2020 г.

Бубек, Себастьян (2015). «Выпуклая оптимизация: алгоритмы и сложность». Основы и тенденции в машинном обучении . 8 (3–4): 231–357. arXiv : 1405.4980 . дои : 10.1561/2200000050 .

[1] Агарвал, Алех; Бартлетт, Питер; Равикумар, Прадип; Уэйнрайт, Мартин (май 2012 г.). «Теоретико-информационные нижние границы сложности оракула стохастической выпуклой оптимизации». Транзакции IEEE по теории информации . 58 (5): 3235–3249. arXiv : 1009.0571 . дои : 10.1109/TIT.2011.2182178 . S2CID 728066 .

[nesterov-2] Перейти обратно: ^а ^б ^с ^д Nesterov, Yurii (2018). Lectures on Convex Optimization . Springer. ISBN 978-3-319-91578-4 .

[shiff-3] Перейти обратно: ^а ^б Арджевани, Йоси; Шамир, Охад; Шифф, Рон (28 мая 2018 г.). «Сложность Oracle методов второго порядка для гладкой выпуклой оптимизации». Математическое программирование . 178 (1–2): 327–360. arXiv : 1705.07260 . дои : 10.1007/s10107-018-1293-1 . S2CID 28260226 .

[1]

[2]

[3]