В этой заметке я собираюсь поделиться своим пониманием/экспозицией статьи Tight Bounds for Approximate Carathéodory and Beyond [1], написанной Mirrokni et al.

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

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

Этот документ содержит 3 основных вклада:

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

2) Используя предложенный алгоритм в качестве конструктивного доказательства, они обеспечивают точную нижнюю оценку задачи Каратеодори, которая показывает, что любая точка внутри многогранника, содержащегося в шаре lp радиус D может быть аппроксимирован с точностью до ϵ в норме lp выпуклой комбинацией только O(D² p/ϵ²) вершин многогранника для p ≥ 2.

3) Они показывают, что простые расширения предложенного алгоритма могут быть применены к другим приложениям, таким как субмодулярная функция и обучение SVM.

Мотивирующий вопрос

Теорема Каратеодори утверждает, что любая точка u многогранника P ⊆ R^n может быть представлена ​​как выпуклая комбинация n+1 вершин многогранника P. Например, на приведенном выше рисунке многогранник P имеет 6 вершин v1, v2, v3, v4, v5, v6 и P ⊆ R². Возьмем произвольно точку u, ее можно выразить как выпуклую комбинацию вершин 2+1 (например, u = 0,25 ⋅ v1 + 0,5 ⋅ v2 + 0 ⋅ v3 + 0 ⋅ v4 + 0 ⋅ v5 + 0,25 ⋅ v6).

Однако вычисление точного решения проблемы Каратеодори может быть дорогостоящим. Сложность становится еще выше, когда многогранник имеет экспоненциально много вершин (например, совпадающий многогранник или матроидный базовый многогранник). Теперь, если мы готовы допустить ошибку ϵ в норме lp; то есть мы принимаем выпуклое комбинационное решение, если

Тогда можем ли мы использовать меньшее количество вершин (более разреженную выпуклую комбинацию) для аппроксимации u? Как можно получить такую ​​разреженную выпуклую комбинацию?

Приближенный алгоритм Миррокни и др.

Добавляемый контент…

Граница для итерации зеркального спуска и разреженности решения

Добавляемый контент…

Комментарии

В этой статье Tight Bounds for Approximate Carathéodory and Beyond [1], написанной Mirrokni et al., есть две вдохновляющие и заслуживающие внимания идеи.

Во-первых, это формулировка задачи как задачи о седловой точке и использование зеркального спуска, что приводит к красивой двойной функции и гарантирует желаемое свойство разреженности для решения. Авторы упомянули, что эта идея вдохновлена ​​существующим решателем положительного линейного программирования, таким как работа Serge et al. [2] и работа Юнга [3].

Второй интересной идеей является вероятностная стратегия доказательства жесткости границы, позволяющая обойти препятствие и построить твердый пример желаемой ситуации. Вместо этого в этой статье доказывается, что желаемый экземпляр проблемы существует. Для получения этой идеи авторы вдохновляются работой Клейна и Янга [4].

Хотя эта заметка не охватывает вторую идею, мы отсылаем читателей к разделу 4.2 исходной статьи (версия arxiv) для дальнейшего чтения.

Справочник

[1] Миррокни, Вахаб и др. «Жесткие границы для приблизительного Каратеодори и выше». Международная конференция по машинному обучению. ПМЛР, 2017.

[2] Плоткин, Серж А., Дэвид Б. Шмойс и Эва Тардос. «Алгоритмы быстрой аппроксимации для задач дробной упаковки и покрытия». Математика исследования операций 20.2 (1995): 257–301.

[3] Янг, Нил Э. «Последовательные и параллельные алгоритмы для смешанной упаковки и покрытия». Материалы 42-го симпозиума IEEE по основам информатики. ИИЭР, 2001.

[4] Кляйн, Филип и Нил Э. Янг. «О количестве итераций для Данцига — Алгоритмы оптимизации Вульфа и аппроксимации упаковки». SIAM Journal on Computing 44.4 (2015): 1154–1172.