- Кинетическая ланжевеновская выборка MCMC без градиентной липшицевой непрерывности — сильно выпуклый случай (arXiv)
Автор: Тим Джонстон, Иосиф Литрас, Сотириос Сабанис.
Аннотация: В этой статье мы рассматриваем выборку из логарифмически вогнутых распределений в гамильтоновой постановке, не предполагая, что целевой градиент является глобально липшицевым. Мы предлагаем два алгоритма, основанные на монотонных полигональных (прирученных) схемах Эйлера, для выборки из целевой меры и предоставления неасимптотических 2-вассерштейновых границ расстояния между законом процесса каждого алгоритма и целевой мерой. Наконец, мы применяем эти результаты для ограничения ошибки оптимизации избыточного риска соответствующей задачи оптимизации.
2. Непрерывные алгоритмы Липшица для задач с графами (arXiv)
Автор: Со Кумабе, Юити Ёсида.
Аннотация: В сообществе машинного обучения было широко замечено, что небольшое возмущение входных данных может вызвать большое изменение в предсказании обученной модели, и такие явления интенсивно изучались в сообществе машинного обучения под названием состязательных атак. . Поскольку графовые алгоритмы также широко используются для принятия решений и поиска знаний, важно разработать графовые алгоритмы, устойчивые к атакам злоумышленников. В этом исследовании мы рассматриваем липшицевую непрерывность алгоритмов как меру устойчивости и инициируем систематическое изучение липшицевой непрерывности алгоритмов для (взвешенных) задач на графах. В зависимости от того, как мы встраиваем выходное решение в метрическое пространство, мы можем думать о нескольких понятиях липшицевости. В основном мы рассматриваем тот, который инвариантен относительно масштабирования весов, и мы предоставляем липшиц-непрерывные алгоритмы и нижние оценки для задачи минимального остовного дерева, задачи кратчайшего пути и задачи сопоставления максимального веса. В частности, наш алгоритм поиска кратчайшего пути получается путем сначала разработки алгоритма для невзвешенных графов, устойчивых к сжатию ребер, а затем применения его к невзвешенному графу, построенному из исходного взвешенного графа. Затем мы рассмотрим другое понятие липшицевости, индуцированное естественным отображением, которое отображает выходное решение в его характеристический вектор. Оказывается, что для этого понятия Липшица не существует непрерывного липшицевого алгоритма, и вместо этого мы разрабатываем алгоритмы с ограниченными поточечными константами Липшица для задачи минимального остовного дерева и задачи двудольного сопоставления максимального веса. Наш алгоритм для последней задачи основан на релаксации ЛП с энтропийной регуляризацией
