Какова временная сложность регрессии Лассо?

Какова асимптотическая временная сложность регрессии Лассо по мере роста числа строк или столбцов?

Напомним, что Лассо является линейной моделью с регуляризацией.$l_1$

Нахождение параметров можно сформулировать как задачу оптимизации без ограничений, где параметры задаются как

.$\arg \min_\beta ||y - X\beta||^2 + \alpha||\beta||_1$

В ограниченной формулировке параметры задаются как

$\arg \min_\beta ||y - X\beta||^2 s.t.||\beta||_1 < \alpha$

Это проблема квадратичного программирования и, следовательно, полином.

Почти все выпуклые процедуры оптимизации, даже для гибких нелинейных вещей, таких как нейронные сети, полагаются на вычисление производной ваших целевых параметров по параметрам. Вы не можете взять производную от хотя. Таким образом, вы полагаетесь на различные методы. Существует много методов поиска параметров. Вот обзорный документ на тему « Оптимизация наименьших квадратов с регуляризацией L1-нормы» . Сложность по времени итеративной выпуклой оптимизации довольно сложно проанализировать, поскольку она зависит от критерия сходимости. Как правило, итерационные проблемы сходятся в меньшее количество эпох по мере увеличения наблюдений.$\alpha||w||_1$

Хотя @JacobMick предоставляет более широкий обзор и ссылку на обзорный документ, позвольте мне дать «краткий ответ» (который можно считать частным случаем его ответа).

Пусть число переменных-кандидатов (объектов, столбцов) равно а размер выборки (количество наблюдений, строк) - n . Рассмотрим LASSO, реализованный с использованием алгоритма LARS ( Efron et al., 2004 ). Вычислительная сложность LASSO составляет O ( K 3 + K 2 n ) ( там же )$K$$n$$\mathcal{O}(K^3 + K^2 n)$

• Для , К 3 < К 2 л и вычислительной сложности Лассо О ( К 2 н $K<n$$K^3 < K^2 n$$\mathcal{O}(K^2 n)$ , который является таким же , как и регрессии с переменных ( Эфрон и др., 2004 , стр. 443-444 также цитируется в Schmidt, 2005 , раздел 2.4; вычислительная сложность регрессии приведена в этом посте ).$K$
• $K \geqslant n$$K^3 \geqslant K^2 n$$\mathcal{O}(K^3)$

Ссылки:

• Эфрон, Брэдли и др. «Наименьший угол регрессии». Летопись статистики 32.2 (2004): 407-499.
• Шмидт, Марк. «Оптимизация наименьших квадратов с регуляризацией l1-нормы». Отчет о проекте CS542B (2005).