- Локальная линейная сходимость градиентных методов для оптимизации подпространства посредством строгой дополнительности (arXiv)
Автор : Дэн Гарбер, Рон Фишер
Аннотация: Рассматриваются задачи оптимизации, целью которых является найти k-мерное подпространство Rn, k‹‹n, которое минимизирует выпуклые и гладкие потери. Такие проблемы обобщают фундаментальную задачу анализа главных компонентов (PCA), включая, среди прочего, надежные и разреженные аналоги, а также логистический PCA для двоичных данных. К этой проблеме можно подойти либо с помощью невыпуклых градиентных методов с высокоэффективными итерациями, но для которых спор о быстрой сходимости к глобальному минимизатору затруднителен, либо с помощью выпуклой релаксации, для которой спор о сходимости к глобальному минимизатору прост, но соответствующий методы часто неэффективны в больших размерностях. В этой работе мы соединяем эти два подхода в строгом предположении дополнительности, которое, в частности, означает, что оптимальное решение выпуклой релаксации уникально и также является оптимальным решением исходной невыпуклой задачи. Наш основной результат — доказательство того, что метод естественного невыпуклого градиента, \textit{свободный от SVD} и требующий только одной QR-факторизации матрицы n×k на итерацию, сходится локально с линейной скоростью. Мы также установили результаты линейной сходимости для метода невыпуклого проецируемого градиента и метода Франка-Вульфа применительно к выпуклой релаксации.
2. Локальная линейная сходимость знакопеременных проекций в метрических пространствах ограниченной кривизны (arXiv)
Автор: Адриан С. Льюис, Хенаро Лопес-Аседо, Адриана Николае.
Аннотация: Рассматривается популярный и классический метод попеременных проекций для поиска точки пересечения двух замкнутых множеств. Поместив алгоритм в метрическое пространство, снабженное только правильными геодезическими и углами (в смысле Александрова), мы можем выделить два ключевых геометрических компонента в стандартном интуитивном анализе локальной линейной сходимости. Первое — это условие трансверсальности на пересечении; второе — это условие типа выпуклости на одном множестве: «равномерное приближение геодезическими.
