- Ускоренный распределенный проекционный градиентный спуск для выпуклой оптимизации с кликовыми связанными ограничениями(arXiv)
Автор:Юто Ватанабэ, Казунори Сакурама
Аннотация: в этой статье рассматривается задача распределенной выпуклой оптимизации с классом связанных ограничений, которые возникают в многоагентной системе, состоящей из нескольких сообществ, моделируемых кликами. Во-первых, мы предлагаем полностью распределенный алгоритм на основе градиента с новым оператором, вдохновленным выпуклой проекцией, называемой проекцией на основе клики. Затем мы тщательно изучаем свойства сходимости как для уменьшающегося, так и для фиксированного размера шага. Для убывающих показана сходимость к оптимальному решению в предположениях о гладкости целевой функции и компактности множества ограничений. Кроме того, когда целевая функция сильно монотонна, строгая сходимость к единственному решению доказывается без предположения о компактности. Для фиксированных размеров шага мы доказываем неэргодическую скорость сходимости O(1/k) относительно целевой невязки в предположении гладкости целевой функции. Кроме того, мы применяем метод ускорения Нестерова к предложенному алгоритму и устанавливаем скорость сходимости O(1/k²). Численные эксперименты иллюстрируют эффективность предлагаемого метода.
2. Алгоритмы прогнозируемого градиентного спуска для решения нелинейных обратных задач с генеративными априорами(arXiv)
Автор:Чжаоцян Лю, Цзюнь Хань
Аннотация: В этой статье мы предлагаем алгоритмы прогнозируемого градиентного спуска (PGD) для оценки сигнала на основе зашумленных нелинейных измерений. Мы предполагаем, что неизвестный p-мерный сигнал находится вблизи диапазона L-липшицевой непрерывной генеративной модели с ограниченными k-мерными входными данными. В частности, мы рассматриваем два случая, когда нелинейная функция зацепления либо неизвестна, либо известна. Для неизвестной нелинейности, аналогично \cite{liu2020generalized}, мы делаем предположение о субгауссовых наблюдениях и предлагаем линейную оценку методом наименьших квадратов. Мы показываем, что при отсутствии ошибки представления и гауссовых векторах считывания примерно O(klogL) отсчетов достаточно для обеспечения линейной сходимости алгоритма PGD к точке, достигающей оптимальной статистической скорости при произвольной инициализации. Для известной нелинейности мы предполагаем монотонность, как в \cite{yang2016sparse}, и делаем гораздо более слабые предположения о векторах зондирования и допускаем ошибку представления. Мы предлагаем нелинейный метод наименьших квадратов, который гарантированно имеет оптимальную статистическую скорость. Предоставляется соответствующий алгоритм PGD, который также линейно сходится к оценке с использованием произвольной инициализации. Кроме того, мы представляем экспериментальные результаты на наборах данных изображений, чтобы продемонстрировать производительность нашего алгоритма PGD.
