- Улучшенные детерминированные алгоритмы для немонотонной субмодульной максимизации (arXiv)
Автор: Сяомин Сунь, Цзялин Чжан, Шо Чжан, Чжицзе Чжан.
Аннотация: Субмодулярная максимизация является одной из центральных тем комбинаторной оптимизации. Он нашел множество применений в реальном мире. В последние десятилетия для решения этой задачи был предложен ряд алгоритмов. Однако большинство современных алгоритмов рандомизированы. Остаются существенные пробелы в отношении коэффициентов аппроксимации между детерминированными и рандомизированными алгоритмами в субмодульной максимизации. В этой статье мы предлагаем детерминированные алгоритмы с улучшенными коэффициентами аппроксимации для немонотонной субмодулярной максимизации. В частности, для матроидного ограничения мы предоставляем детерминистический алгоритм аппроксимации 0,283−o(1), в то время как предыдущий наилучший детерминистический алгоритм достигает коэффициента аппроксимации только 1/4. Для ограничения рюкзака мы предоставляем детерминистический алгоритм аппроксимации 1/4, в то время как предыдущий лучший детерминистический алгоритм достигает коэффициента аппроксимации только 1/6. Для ограничений линейной упаковки с большой шириной мы предлагаем детерминированный алгоритм аппроксимации 1/6−ε. Насколько нам известно, в настоящее время не существует алгоритма детерминированной аппроксимации для ограничений
2. Эффективная коммуникационная децентрализованная онлайн-непрерывная субмодульная максимизация аварийного восстановления (arXiv)
Автор: Цисинь Чжан, Цзэндэ Дэн, Сянжу Цзянь, Зайи Чен, Хаоюань Ху, Ю Ян.
Аннотация: Максимизация монотонной субмодулярной функции является фундаментальной задачей машинного обучения, экономики и статистики. В этой статье мы представляем два децентрализованных онлайн-алгоритма с эффективной коммуникацией для монотонной непрерывной DR-субмодульной задачи максимизации, оба из которых уменьшают количество оценок градиента для каждой функции и сложность связи для каждого раунда с T3/2 до 1. Первый один, One-shot Decentralized Meta-Frank-Wolfe (Mono-DMFW), достигает границы (1−1/e)-сожаления O(T4/5). Насколько нам известно, это первый одноразовый децентрализованный онлайн-алгоритм без проекций для монотонной непрерывной DR-субмодулярной максимизации. Затем, вдохновленные не забывающей функцией повышения \citep{zhang2022boosting}, мы предлагаем алгоритм децентрализованного онлайн-ускорения градиентного восхождения (DOBGA), который достигает (1−1/e)-сожаления O(T−−√). Насколько нам известно, это первый результат, позволяющий получить оптимальное O(T−−√) по сравнению с (1−1/e)-аппроксимацией только с одним запросом градиента для каждой локальной целевой функции за шаг. Наконец, различные экспериментальные результаты подтверждают эффективность предложенного метода.
