Скорость, вычислительные затраты PCA, LASSO, эластичная сеть

Я пытаюсь сравнить сложность вычислений / скорость оценки трех групп методов для линейной регрессии, как это различается в Hastie et al. «Элементы статистического обучения» (2-е изд.), Глава 3:

1. Выбор подмножества
2. Методы усадки
3. Методы с использованием производных направлений ввода (PCR, PLS)

Сравнение может быть очень грубым, просто чтобы дать некоторое представление. Я понимаю, что ответы могут зависеть от масштаба проблемы и от того, как она соответствует архитектуре компьютера, поэтому в качестве конкретного примера можно рассмотреть размер выборки 500 и 50 кандидатов в регрессоры. В основном меня интересует мотивация вычислительной сложности / скорости оценки, а не то, сколько времени потребуется для определенного процессора в данном примере.

Группа 1 :
Сложность / скорость группы 1. кажется, не слишком сложно выяснить, используются ли алгоритмы грубой силы (хотя могут быть более эффективные альтернативы, такие как алгоритм «скачков и границ»). Например, полный выбор подмножества потребует регрессий, чтобы соответствовать, учитывая пул K возможностей кандидата. Подход OLS одной линейной регрессии имеет сложность O ( K 2 n ) (согласно этому посту ), где n - размер выборки. Следовательно, общая сложность выбора полного подмножества методом грубой силы должна быть O ( 2 K K $2^K$$K$$\mathcal{O}(K^2 n)$$n$ .$\mathcal{O}(2^K K^2 n)$

Группа 2 :
Сложность / скорость группы 2. обсуждается в разделах 3.8 и 3.9 книги. Например, регрессия гребня с заданным штрафом имеет ту же вычислительную сложность, что и регулярная регрессия. Поскольку λ необходимо найти с помощью перекрестной проверки, вычислительная нагрузка линейно увеличивается в количестве разделений данных, используемых при перекрестной проверке (скажем, S ). Если сетка λ имеет L точек, общая сложность регрессии гребня с настройкой параметра λ будет O ( L S K 2 n ) .$\lambda$$\lambda$$S$$\lambda$$L$$\lambda$$\mathcal{O}(LSK^2 n)$
В книге довольно много разговоров о LASSO , но я не смог найти то, что мне нужно. Однако я нашел на с. 443 Efron et al. «Регрессия наименьшего угла» (2004), что сложность LASSO для данного такая же, как сложность подгонки OLS линейной регрессии, если используется метод LARS. Тогда общая сложность LASSO с настройкой параметра λ будет O ( L S K 2 n ) . (Я не читал эту статью внимательно, поэтому, пожалуйста, поправьте меня, если я ошибся.) Эластичная сетка сочетает в себе гребень и LASSO; оба имеют одинаковую вычислительную сложность; следовательно, сложность эластичной сетки должна быть$\lambda$$\lambda$$\mathcal{O}(LSK^2 n)$
где A - размер сетки параметра настройки α, который балансирует вес гребня по сравнению с LASSO.$\mathcal{O}(ALSK^2 n)$$A$$\alpha$

Группа 3 :
Мне все еще не хватает заметки о сложности / скорости для группы 3. Она состоит из регрессии главных компонентов (PCR) и частичных наименьших квадратов (PLS).

Это только для одной части вопроса 2 в группе 3 выше (а именно, PLS), но, тем не менее, может быть информативным: Srinivasan et al (2010, технический отчет; см. Https://www.umiacs.umd.edu/~balajiv/Papers/ UMD_CS_TR_Pls_Gpu.pdf ) провел некоторые измерения на PLS с использованием алгоритма NIPALS, заявив, что сложность этого алгоритма во времени (и пространстве) равна O (dN) - для извлечения и включив их в различные модели для: а) обнаружения людей на изображениях, и b. ) распознавание лица. Измерения проводились с использованием их собственной реализации на основе графического процессора.