Новый алгоритм ускоряет робастную регрессию с блочными весами Льюиса
Исследователи опубликовали в arXiv статью, посвящённую новому алгоритму для группы распределённо-робастной (GDR) регрессии по методу наименьших квадратов. Алгоритм решает задачу, когда данные разбиты на m групп, а матрица признаков имеет размерность d.
Как сообщается в работе, метод достигает (1+?)-мультипликативного оптимального решения, выполняя O?(min{rank(A),m}^{1/3}?^{-2/3}) решений линейных систем вида A?BA, где B — блочно-диагональная матрица. Это существенно быстрее стандартных методов внутренней точки в диапазоне умеренной точности.
В основе алгоритма лежит геометрическая конструкция — блочные веса Льюиса, которые связывают эмпирическую GDR-задачу с тщательно подобранной задачей наименьших квадратов. Затем применяется ускоренный проксимальный метод. Такой подход позволяет плавно интерполировать между минимизацией средней ошибки и робастной потерей.
Авторы отмечают, что их алгоритм достигает такой же гарантии, как и современные методы для частного случая ??-регрессии, но при этом работает для произвольных групп. Это открывает возможности для более эффективной обработки данных с гетерогенной структурой.
Практическое значение работы — ускорение вычислений в задачах, где данные разбиты на группы с разными распределениями, например, в финансах или медицине. Алгоритм может быть интегрирован в существующие библиотеки машинного обучения.
