1. Об асимптотической линейной сходимости прогнозируемого градиентного спуска для метода наименьших квадратов с ограничениями (arXiv)
Автор:Трунг Ву, Равив Райх
Аннотация: многие недавние проблемы в обработке сигналов и машинном обучении, такие как сжатое восприятие, восстановление изображения, восстановление матрицы/тензора и неотрицательная матричная факторизация, могут быть представлены как оптимизация с ограничениями. Прогнозируемый градиентный спуск — это простой, но эффективный метод решения таких задач оптимизации с ограничениями. Анализ локальной сходимости способствует нашему пониманию его асимптотического поведения вблизи решения, предлагая более точные границы скорости сходимости по сравнению с анализом глобальной сходимости. Однако локальные гарантии часто оказываются разбросанными по проблемным областям машинного обучения и обработки сигналов. В этой рукописи представлена единая основа для анализа локальной сходимости прогнозируемого градиентного спуска в контексте метода наименьших квадратов с ограничениями. Предлагаемый анализ дает представление об основных свойствах локальной сходимости, таких как условия линейной сходимости, область сходимости, точная асимптотическая скорость сходимости и ограничение количества итераций, необходимых для достижения определенного уровня точности. Чтобы продемонстрировать применимость предложенного подхода, мы представляем рецепт анализа сходимости проецируемого градиентного спуска и демонстрируем его с помощью сквозного применения рецепта к четырем фундаментальным задачам, а именно: линейный метод наименьших квадратов с ограничениями равенства, разреженные восстановление, метод наименьших квадратов с ограничением единичной нормы и завершение матрицы
2. Слепое сверхразрешение точечных источников с помощью проецируемого градиентного спуска (arXiv)
Автор:Сихан Мао, Джинчи Чен
Аннотация:Слепое сверхразрешение можно рассматривать как проблему восстановления матрицы низкого ранга, используя присущую простоте сигнала и низкоразмерную структуру точечных функций рассеяния. В этой статье мы разрабатываем простой, но эффективный метод невыпуклого прогнозируемого градиентного спуска для этой задачи, основанный на низкоранговой структуре векторизованной матрицы Ганкеля, связанной с целевой матрицей. Теоретический анализ показывает, что предложенный метод точно сходится к целевой матрице с линейной скоростью сходимости при тех же условиях, что и выпуклые подходы. Численные результаты показывают, что наш подход конкурентоспособен с существующими выпуклыми подходами с точки зрения способности извлечения и эффективности.
3. Онлайн прогнозируемый градиентный спуск для стохастической оптимизации с зависимыми от решений распределениями (arXiv)
Автор: Киллиан Вуд, Джанлука Бьянчин, Эмилиано Далл’Анезе.
Аннотация: в этой статье исследуется проблема отслеживания решений задач стохастической оптимизации с изменяющимися во времени затратами, которые зависят от случайных величин с распределениями, зависящими от решений. В этом контексте мы предлагаем использовать онлайн-метод стохастического градиентного спуска для решения задачи оптимизации и предоставляем явные границы ожидания и высокой вероятности для расстояния между оптимизаторами и точками, сгенерированными алгоритмом. В частности, мы показываем, что когда ошибка градиента из-за выборки моделируется как случайная величина суб-Вейбулла, то ошибка отслеживания в конечном итоге ограничена в ожидании и с высокой вероятностью. Теоретические выводы подтверждаются с помощью численного моделирования в контексте оптимизации зарядки парка электромобилей.
