Исследователи подтвердили гипотезу о фундаментальном ограничении сложности для алгоритмов разреженной выпуклой оптимизации. Работа доказывает, что линейная зависимость от ограниченного числа обусловленности в задачах наименьших квадратов является неустранимым барьером для любых полиномиальных алгоритмов. Результат опирается на гипотезу о расширении малых множеств (Small-Set Expansion Hypothesis), что закрывает давний теоретический вопрос в области вычислительной сложности.
Разреженные методы наименьших квадратов играют критическую роль в задачах машинного обучения, где требуется отбор признаков или работа с высокоразмерными данными при ограниченных вычислительных ресурсах. Доказательство того, что точность решения напрямую ограничена числом обусловленности матрицы, объясняет, почему классические итерационные методы часто сталкиваются с «плато» при попытке оптимизации сложных разреженных структур.
Данное исследование переводит предположение Аксиотиса и Свириденко из разряда гипотез в доказанный теоретический факт. Это накладывает строгие рамки на разработку новых оптимизаторов: попытки преодолеть этот барьер с помощью стандартных полиномиальных подходов заведомо обречены на неудачу, что заставляет исследователей искать альтернативные методы аппроксимации или использовать специфические допущения о структуре данных.
Ключевые факты
- Доказана гипотеза Аксиотиса и Свириденко (AS21) о невозможности улучшения зависимости от числа обусловленности.
- Установлен теоретический нижний предел сложности для задач разреженных наименьших квадратов.
- Доказательство базируется на гипотезе Small-Set Expansion в формулировке Рагхавендры для взвешенных регулярных графов.
- Результат ограничивает эффективность любых алгоритмов, работающих за полиномиальное время в задачах разреженной выпуклой оптимизации.