L1 регуляризация

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM DeepSeek и проверена участником Aliia Latipova 23:50, 16 июля 2026 (MSD)

Содержание

1 Определение и геометрическая интуиция
2 Выбор коэффициента регуляризации
3 Алгоритмы оптимизации для L1-регуляризации
4 Теоретические свойства
5 Применения в машинном обучении
6 Сравнение L1-регуляризации с L2-регуляризацией
7 Ограничения L1-регуляризации и их преодоление
8 Современные обобщения и направления исследований
9 Практические рекомендации по выбору алгоритма оптимизации
10 Примечания
11 Литература
12 См. также

L1-регуляризация (также известная как LASSO-регуляризация) — метод регуляризации в задачах машинного обучения и статистики, заключающийся в добавлении к функции потерь штрафа, пропорционального $\ell_1$ -норме вектора параметров модели. Основное свойство L1-регуляризации — автоматический отбор признаков за счёт сжатия (shrinkage) коэффициентов к нулю, что приводит к разреженным (sparse) решениям. Наибольшую известность метод получил благодаря работе Роберта Тишбирани^[1], предложившего LASSO (Least Absolute Shrinkage and Selection Operator) как комбинацию сжатия и отбора переменных в линейной регрессии.

В современной статистике и оптимизации L1-регуляризация является фундаментальным инструментом, лежащим в основе теории сжатого зондирования (compressed sensing), а также широко используется в задачах с высокой размерностью ( $p \gg n$ ), где требуется восстановление разреженных сигналов.

Определение и геометрическая интуиция

Формальная постановка задачи

Пусть задана выборка $\{(x_i, y_i)\}_{i=1}^n$ , где $x_i \in \mathbb{R}^p$ — векторы признаков, $y_i \in \mathbb{R}$ — отклики (для регрессии) или метки классов (для классификации). Рассмотрим эмпирический риск $L(w) = \frac{1}{n} \sum_{i=1}^n \ell(y_i, \langle w, x_i \rangle)$ , где $\ell(\cdot, \cdot)$ — функция потерь (например, квадратичная $\ell(y, \hat{y}) = (y - \hat{y})^2$ или логистическая). Задача L1-регуляризации формулируется как минимизация составного функционала:

$\hat{w} = \arg\min_{w \in \mathbb{R}^p} \left\{ L(w) + \lambda \|w\|_1 \right\},$

где $\lambda \ge 0$ — коэффициент регуляризации, а $\|w\|_1 = \sum_{j=1}^p |w_j|$ — $\ell_1$ -норма вектора параметров.

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

$\hat{w} = \arg\min_{w} \left\{ \frac{1}{2n} \|y - X w\|_2^2 + \lambda \|w\|_1 \right\}.$

Эквивалентная ограничительная формулировка (для некоторого $t \ge 0$ ):

$\min_{w: \|w\|_1 \le t} \frac{1}{2n} \|y - X w\|_2^2,$

где между $\lambda$ и $t$ существует взаимно однозначное соответствие (при строгой выпуклости задачи).

Геометрическая интерпретация

Геометрический смысл L1-регуляризации становится ясным при рассмотрении ограничительной формулировки. Множество $\{w : \|w\|_1 \le t\}$ представляет собой $\ell_1$ -шар — выпуклый многогранник, являющийся аналогом октаэдра в размерности $p$ . В отличие от $\ell_2$ -шара, имеющего гладкую границу, $\ell_1$ -шар имеет угловые точки, лежащие на координатных осях. При минимизации квадратичной функции (или другой гладкой функции потерь) на таком многограннике решение с высокой вероятностью достигается в одной из угловых точек, что соответствует обнулению части координат. Это и есть механизм разреживания.

Важно подчеркнуть, что угловые точки $\ell_1$ -шара соответствуют векторам с одним ненулевым элементом. В более высоких размерностях грани многогранника соответствуют разреженным векторам с заданным числом ненулевых координат.

Связь с байесовским подходом

С вероятностной точки зрения L1-регуляризация эквивалентна заданию априорного распределения Лапласа (двустороннего экспоненциального) на параметры модели $w_j \sim \text{Laplace}(0, 1/\lambda)$ . Это распределение имеет более тяжёлые хвосты и пик в нуле по сравнению с гауссовским (соответствующим L2-регуляризации), что способствует разреженности апостериорного распределения.

Выбор коэффициента регуляризации $\lambda$

Коэффициент $\lambda$ управляет балансом между качеством аппроксимации данных и степенью разреженности решения. Выбор $\lambda$ критически влияет на обобщающую способность модели.

Методы кросс-валидации

Наиболее распространённый эмпирический подход — $K$ -блочная кросс-валидация (например, $K = 5$ или $10$ ). Для каждого значения $\lambda$ из сетки вычисляется средняя ошибка на валидационных блоках; выбирается $\lambda$ , минимизирующее эту ошибку. На практике часто используют одно стандартное отклонение правило (one-standard-error rule): выбирают наибольшее $\lambda$ , ошибка которого лежит в пределах одного стандартного отклонения от минимальной, что даёт более разреженную модель без статистически значимой потери качества.

Информационные критерии

Для линейных моделей предложены модификации информационных критериев Акаике (AIC) и Байесовского (BIC), учитывающие эффективное число степеней свободы LASSO. Для квадратичной потери эффективная размерность (degrees of freedom) оценивается как число ненулевых коэффициентов $\| \hat{w} \|_0$ (Zou, Hastie, Tibshirani, 2007). Тогда критерии имеют вид:

$\text{AIC}(\lambda) = n \log(\hat{\sigma}^2) + 2 \| \hat{w} \|_0,$

$\text{BIC}(\lambda) = n \log(\hat{\sigma}^2) + \| \hat{w} \|_0 \log n.$

В случае $p \gg n$ BIC часто приводит к более разреженным решениям, чем кросс-валидация.

Универсальные правила

В теории сжатого зондирования известно универсальное правило выбора $\lambda$ , обеспечивающее восстановление сигнала с высоким уровнем шума. Для задачи $y = X w^* + \varepsilon$ с $\varepsilon \sim \mathcal{N}(0, \sigma^2 I)$ часто используют

$\lambda \asymp \sigma \sqrt{2 \log p}$

(минимаксная оценка). Однако это правило является асимптотическим и на практике часто приводит к излишнему сжатию; для реальных данных его калибруют с помощью кросс-валидации или эмпирического правила Байеса (Efron, 2004).

Масштабирование признаков

L1-регуляризация зависит от масштаба признаков: если признак $j$ умножить на константу $c$ , то его коэффициент при неизменном $\lambda$ должен быть разделён на $c$ , чтобы сохранить штраф. Поэтому перед применением LASSO настоятельно рекомендуется стандартизация всех признаков к нулевому среднему и единичной дисперсии ( $x_{ij} \leftarrow \frac{x_{ij} - \bar{x}_j}{\hat{\sigma}_j}$ ). Это обеспечивает одинаковый масштаб штрафов для всех признаков.

Алгоритмы оптимизации для L1-регуляризации

Задача (1) является негладкой (из-за $\ell_1$ -нормы), но выпуклой. Для её решения разработаны специализированные алгоритмы, использующие структуру субградиента и проксимальные операторы.

Проксимальный градиентный спуск (Proximal Gradient Descent)

Проксимальный градиентный метод является стандартным подходом для минимизации суммы гладкой выпуклой функции $L(w)$ и негладкой $R(w) = \lambda \|w\|_1$ . Итерационная формула:

$w^{k+1} = \operatorname{prox}_{\alpha R} \left( w^k - \alpha \nabla L(w^k) \right),$

где $\alpha > 0$ — шаг (размер шага), а проксимальный оператор для $\ell_1$ -нормы имеет вид оператора мягкого порога (soft-thresholding):

$\big( \operatorname{prox}_{\alpha \lambda \|\cdot\|_1}(z) \big)_j = \operatorname{sign}(z_j) \max\{ |z_j| - \alpha \lambda, 0 \}.$

Псевдокод (неускоренный вариант):

Вход: $X, y, \lambda$ , начальное приближение $w^0$ , максимальное число итераций $K$ , параметр остановки $\varepsilon$ .
Для :
- Вычислить градиент: $g^k = \nabla L(w^k)$ .
- Сделать шаг градиентного спуска: $z^{k} = w^k - \alpha_k g^k$ .
- Применить мягкий порог: $w^{k+1} = S_{\alpha_k \lambda}(z^{k})$ .
- Если $\|w^{k+1} - w^k\|_2 < \varepsilon$ , остановиться.
Вернуть $w^{K}$ .

Оценка сходимости: Если $L$ имеет $\beta$ -липшицев градиент, то при выборе шага $\alpha_k = 1/\beta$ метод сходится со скоростью $O(1/k)$ по значению функции. Ускоренный вариант (FISTA^[1]) имеет скорость $O(1/k^2)$ . Вычислительная сложность одной итерации составляет $O(np)$ для вычисления градиента.

Координатный спуск (Coordinate Descent)

Координатный спуск является наиболее эффективным для LASSO при больших $n$ и $p$ , особенно в реализации GLMNET^[1]. Алгоритм циклически обновляет каждый коэффициент, решая одномерную задачу с мягким порогом. Для линейной регрессии обновление для $j$ -го коэффициента имеет вид:

$w_j^{\text{new}} = \frac{S\left( \sum_{i=1}^n x_{ij} (y_i - \sum_{k \neq j} x_{ik} w_k), \lambda \right)}{\sum_{i=1}^n x_{ij}^2}.$

Этот алгоритм чрезвычайно быстр для разреженных решений и хорошо масштабируется на $p \sim 10^6$ . Сходимость координатного спуска для выпуклых дифференцируемых функций с сепарабельным регуляризатором доказана (Tseng, 2001).

Метод наименьших углов (LARS)

Алгоритм LARS (Efron et al., 2004) позволяет эффективно строить весь регуляризационный путь LASSO при квадратичной потере. Вычислительная сложность LARS сравнима со сложностью вычисления одного МНК-решения ( $O(p^3 + n p^2)$ ), что делает его полезным для умеренных $p$ , но неэффективным при $p \gg n$ .

Альтернативные методы

Алгоритм ADMM (Alternating Direction Method of Multipliers) — эффективен для распределённых вычислений и задач с дополнительными линейными ограничениями.
Субградиентные методы — просты, но имеют медленную сходимость $O(1/\sqrt{k})$ .
Квазиньютоновские методы с проксимальной модификацией (например, L-BFGS-B) — применяются для задач с ограничениями.

Для задач с $n \gg p$ предпочтителен координатный спуск; для $p \gg n$ и очень больших данных (разреженные матрицы) — проксимальные методы с использованием случайных подвыборок градиента (SVRG, SAGA).

Теоретические свойства

Теория L1-регуляризации опирается на условия на матрицу признаков $X$ и уровень шума. Основные результаты формулируются в терминах восстановления (support recovery) и предсказательной точности (prediction consistency).

Условия восстановления носителя

Для асимптотического восстановления истинного носителя $S = \{j: w_j^* \neq 0\}$ требуется условие взаимной некоррелированности признаков. Классическое Neighborhood stability condition (Zhao & Yu, 2006) и Irrepresentable condition требуют, чтобы корреляция между признаками из $S$ и вне $S$ была ограничена:

$\| X_{S^c}^\top X_S (X_S^\top X_S)^{-1} \|_\infty \le 1 - \gamma$

для некоторого $\gamma > 0$ . Это условие является необходимым и достаточным для восстановления носителя в асимптотике при правильном выборе $\lambda \asymp \sqrt{\frac{\log p}{n}}$ .

Неравенства оракула и скорости сходимости

В условиях ограниченного собственного значения (Restricted Eigenvalue condition — RE) или Restricted Isometry Property (RIP)^[1] для LASSO можно получить неравенство оракула:

$\| \hat{w} - w^* \|_2^2 \le C \cdot \frac{s \log p}{n},$

где $s = \| w^* \|_0$ — число ненулевых компонент, а $C$ — константа, зависящая от RE-константы. Это гарантирует, что LASSO адаптируется к неизвестной разреженности: скорость сходимости определяется эффективной размерностью $s$ , а не полной $p$ .

В терминах ошибки предсказания:

$\frac{1}{n} \| X \hat{w} - X w^* \|_2^2 \le C \cdot \frac{s \log p}{n}$

при $\lambda \asymp \sqrt{\frac{\log p}{n}}$ и условии RE (Bickel, Ritov, Tsybakov, 2009; van de Geer, 2008).

Асимптотическое распределение

В классической асимптотике $p$ фиксировано, $n \to \infty$ , LASSO не является асимптотически нормальным для ненулевых коэффициентов из-за сжатия (shrinkage). Однако существуют модификации (например, деспарсифицированный LASSO или LASSO с поправкой, см. Javanmard & Montanari, 2014), позволяющие строить доверительные интервалы.

Применения в машинном обучении

L1-регуляризация используется в широком спектре задач:

Линейная и логистическая регрессия — отбор наиболее значимых признаков в медицине, биоинформатике, социальных науках.
Сжатое зондирование — восстановление сигналов (изображений, аудио) из неполных измерений с помощью $\ell_1$ -минимизации (Candes, Romberg, Tao, 2006).
Обучение словарей (dictionary learning) — разреженное представление данных.
Глубокое обучение — L1-регуляризация применяется к весам слоёв для их разреживания, что позволяет сократить память и ускорить вывод (например, обрезка нейронных сетей). В последние годы появились работы о групповой разреженности и структурной разреженности в свёрточных сетях.
Матричное сжатие — в задаче низкорангового восстановления с использованием ядерной нормы (аналог L1 для сингулярных чисел).
Обработка естественного языка — отбор признаков для моделей мешка слов с размерностью $p \sim 10^5$ и выше.

Сравнение L1-регуляризации с L2-регуляризацией

L2-регуляризация (ридж-регрессия, Tikhonov regularization) использует штраф $\lambda \|w\|_2^2$ . Принципиальные различия:

Разреженность: L1 даёт разреженные решения, L2 — нет (все коэффициенты, как правило, ненулевые).
Устойчивость: L2-регуляризация строго выпукла и имеет единственное решение; L1 при $p > n$ может иметь неединственное решение (если матрица вырождена).
Поведение при коррелированных признаках: L1 склонен выбирать только один признак из сильно коррелированной группы (эффект «выбора одной из группы»), тогда как L2 сглаживает коэффициенты внутри группы, придавая им схожие значения. Это ограничение L1 породило групповые варианты (см. ниже).
Смещение и дисперсия: L1 вносит большее смещение для больших коэффициентов по сравнению с L2, но может давать меньшее среднеквадратичное отклонение в разреженных сценариях.
Вычислительные аспекты: L2 сводится к решению линейной системы (можно аналитически), L1 требует итеративных методов.

Ограничения L1-регуляризации и их преодоление

Насыщение при $p \gg n$

При $p \gg n$ LASSO может выбрать максимум $n$ ненулевых коэффициентов (в силу ограничений геометрии). Если истинный носитель больше $n$ , LASSO не способен его восстановить. В таких случаях используют другие регуляризаторы (например, эластичная сеть, групповой LASSO) или используют двухэтапные процедуры (marginal screening, ISIS).

Неединственность решения

При $p > n$ и недостаточной регуляризации задача может иметь бесконечно много решений. Этого избегают, либо добавляя малую L2-регуляризацию (эластичная сеть), либо используя выбор решения с минимальной $\ell_2$ -нормой среди всех решений LASSO.

Коррелированные признаки

LASSO неустойчив при высокой корреляции: он выбирает одну переменную случайным образом, что снижает интерпретируемость. Решение — эластичная сеть (Zou & Hastie, 2005), объединяющая штрафы $\lambda \|w\|_1 + \gamma \|w\|_2^2$ , что обеспечивает стабильность и отбор групп.

Чувствительность к масштабу

Требуется стандартизация признаков; в противном случае штрафы для различных признаков несопоставимы.

Тщательная настройка $\lambda$

Результаты сильно зависят от выбора $\lambda$ . Рекомендуется использовать кросс-валидацию с тщательной калибровкой сетки.

Невыпуклые альтернативы

Для улучшения восстановления предложены невыпуклые регуляризаторы, аппроксимирующие $\ell_0$ -норму (например, MCP^[1], SCAD^[1]). Они обладают свойством оракула (асимптотически дают несмещённые оценки) и менее смещены для больших коэффициентов. Однако их оптимизация сложнее из-за невыпуклости (требуется многократный запуск, возникают локальные минимумы).

Современные обобщения и направления исследований

Групповой LASSO (Yuan & Lin, 2006) — штрафует группы признаков как $\sum_{g} \|w_g\|_2$ , позволяя включать или исключать целые группы.
Структурированный LASSO — учитывает иерархию (например, тенденции, спайковые и гладкие компоненты).
Адаптивный LASSO (Zou, 2006) — использует веса $w_j^*$ , полученные из начальной оценки, для улучшения теоретических свойств (устранение смещения).
Квадратичный LASSO и обобщения на экспоненциальное семейство (GLM).
L1-регуляризация в нейронных сетях — активно применяется для разреживания весов при обучении с глубокими архитектурами; комбинируется с групповой разреженностью для сжатия сетей (Sparse Group Lasso).
Теория двойного спуска (double descent) — в некоторых работах показано, что LASSO в перепараметризованных моделях демонстрирует пик обобщающей ошибки при $p \approx n$ , но при $p \gg n$ ошибка может снова уменьшаться (интерполяционный режим).

Практические рекомендации по выбору алгоритма оптимизации

Выбор алгоритма зависит от размерности данных $(n, p)$ , структуры матрицы $X$ (плотная/разреженная), требуемой точности и доступных вычислительных ресурсов.

Для малых $p$ ( $p \lesssim 1000$ ) и $n$ умеренного: можно использовать LARS для получения всего пути, либо координатный спуск.
Для $p$ от $10^3$ до $10^5$ , плотные данные: предпочтительнее координатный спуск (GLMNET). Он хорошо использует локальность обновлений и кеширование.
Для $p \gg n$ и разреженных матриц: проксимальные методы с ускорением (FISTA) или стохастические варианты (SAGA, SVRG). Координатный спуск может работать медленно, если данные не удовлетворяют условию «путь разрежен».
Для распределённых вычислений или систем с ограниченной памятью: ADMM, позволяющий разбивать задачу на подзадачи.
Для задач с высокими требованиями к точности: рекомендуется использовать методы второго порядка (например, проксимальный Ньютон) или сочетание координатного спуска и BFGS-подобных аппроксимаций (например, алгоритм QUIC для $\ell_1$ -графических моделей).
При наличии априорной информации о структуре разреженности: использовать адаптированные методы (например, групповой LASSO + блок-координатный спуск).

Важно: на этапе подбора $\lambda$ обычно строят регуляризационный путь — последовательность решений для убывающей сетки $\lambda$ , используя тёплый старт. Это значительно ускоряет вычисления.

Примечания

Литература

Tibshirani R. Regression Shrinkage and Selection via the Lasso // Journal of the Royal Statistical Society. Series B (Methodological). — 1996. — Т. 58. — № 1. — С. 267—288.
Candes E. J., Tao T. Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? // IEEE Transactions on Information Theory. — 2006. — Т. 52. — № 12. — С. 5406—5425.
Friedman J., Hastie T., Tibshirani R. Regularization Paths for Generalized Linear Models via Coordinate Descent // Journal of Statistical Software. — 2010. — Т. 33. — № 1. — С. 1—22.
Beck A., Teboulle M. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems // SIAM Journal on Imaging Sciences. — 2009. — Т. 2. — № 1. — С. 183—202.
Zhao P., Yu B. On Model Selection Consistency of Lasso // Journal of Machine Learning Research. — 2006. — Т. 7. — С. 2541—2563.
Bickel P. J., Ritov Y., Tsybakov A. B. Simultaneous Analysis of Lasso and Dantzig Selector // The Annals of Statistics. — 2009. — Т. 37. — № 4. — С. 1705—1732.
Zou H., Hastie T. Regularization and Variable Selection via the Elastic Net // Journal of the Royal Statistical Society. Series B (Statistical Methodology). — 2005. — Т. 67. — № 2. — С. 301—320.
Zhang C.-H. Nearly Unbiased Variable Selection Under Minimax Concave Penalty // The Annals of Statistics. — 2010. — Т. 38. — № 2. — С. 894—942.
Fan J., Li R. Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties // Journal of the American Statistical Association. — 2001. — Т. 96. — № 456. — С. 1348—1360.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed.. — New York: Springer, 2009. — С. 61—79.
Bühlmann P., van de Geer S. Statistics for High-Dimensional Data: Methods, Theory and Applications. — Heidelberg: Springer, 2011.

См. также

Источник — «http://www.machinelearning.ru/wiki/index.php?title=L1_%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F»

Категории: Регуляризация | Линейные модели | Машинное обучение | Статистическое обучение

@@ Строка 2: / Строка 2: @@
 {{TOCright}}
-'''L1-регуляризация''' (также известная как '''LASSO''' — Least Absolute Shrinkage and Selection Operator) — метод регуляризации в статистическом обучении, заключающийся в добавлении к функционалу эмпирического риска штрафа, пропорционального <tex>\ell_1</tex>-норме вектора параметров. Этот подход одновременно решает две задачи: сокращение (сжатие) коэффициентов и отбор признаков, приводя к разреженным решениям. L1-регуляризация лежит в основе [[LASSO|классического LASSO]], является ключевым инструментом в [[Сжатое зондирование|сжатом зондировании]] и активно применяется в задачах с высокой размерностью, где число признаков <tex>p</tex> может значительно превосходить число наблюдений <tex>n</tex>.
+'''L1-регуляризация''' (также известная как ''LASSO-регуляризация'') — метод [[Регуляризация|регуляризации]] в задачах [[Машинное обучение|машинного обучения]] и [[Статистика|статистики]], заключающийся в добавлении к функции потерь штрафа, пропорционального <tex>\ell_1</tex>-норме вектора параметров модели. Основное свойство L1-регуляризации — автоматический отбор признаков за счёт сжатия (shrinkage) коэффициентов к нулю, что приводит к разреженным (sparse) решениям. Наибольшую известность метод получил благодаря работе [[Роберт Тишбирани|Роберта Тишбирани]]<ref name="tibshirani1996">{{статья |автор= Tibshirani R. |заглавие= Regression Shrinkage and Selection via the Lasso |ссылка= https://www.jstor.org/stable/2346178 |издание= Journal of the Royal Statistical Society. Series B (Methodological) |год= 1996 |том= 58 |номер= 1 |страницы= 267—288}}</ref>, предложившего ''LASSO'' (Least Absolute Shrinkage and Selection Operator) как комбинацию сжатия и отбора переменных в линейной регрессии.
-== Формальная постановка и геометрическая интерпретация ==
+В современной статистике и оптимизации L1-регуляризация является фундаментальным инструментом, лежащим в основе теории [[Сжатое зондирование|сжатого зондирования]] (compressed sensing), а также широко используется в задачах с высокой размерностью (<tex>p \gg n</tex>), где требуется восстановление разреженных сигналов.
-Рассмотрим задачу обучения с учителем: дана выборка <tex> \{(x_i, y_i)\}_{i=1}^n </tex>, где <tex> x_i \in \mathbb{R}^p </tex> — векторы признаков, <tex> y_i \in \mathbb{R} </tex> — отклики (для регрессии). Пусть <tex> \ell(y, \hat{y}) </tex> — функция потерь, а <tex> w \in \mathbb{R}^p </tex> — вектор параметров модели. В случае линейной модели <tex> \hat{y}(x) = w^\top x </tex> (без смещения или с центрированными данными) задача L1-регуляризации ставится как минимизация регуляризованного эмпирического риска:
+== Определение и геометрическая интуиция ==
-:: <tex> \widehat{w}(\lambda) = \arg\min_{w \in \mathbb{R}^p} \left\{ \frac{1}{n} \sum_{i=1}^n \ell(y_i, w^\top x_i) + \lambda \|w\|_1 \right\}, </tex>
+=== Формальная постановка задачи ===
-где <tex> \|w\|_1 = \sum_{j=1}^p |w_j| </tex>, а <tex> \lambda \geqslant 0 </tex> — коэффициент регуляризации, управляющий степенью сжатия. Для задачи квадратичной регрессии (<tex> \ell(y, \hat{y}) = (y - \hat{y})^2 </tex>) получаем классический LASSO<ref>{{статья |автор=Tibshirani, R. |заглавие=Regression Shrinkage and Selection via the Lasso |ссылка=https://www.jstor.org/stable/2346178 |издание=Journal of the Royal Statistical Society. Series B (Methodological) |год=1996 |том=58 |номер=1 |страницы=267—288}}</ref>:
+Пусть задана выборка <tex>\{(x_i, y_i)\}_{i=1}^n</tex>, где <tex>x_i \in \mathbb{R}^p</tex> — векторы признаков, <tex>y_i \in \mathbb{R}</tex> — отклики (для регрессии) или метки классов (для классификации). Рассмотрим эмпирический риск <tex>L(w) = \frac{1}{n} \sum_{i=1}^n \ell(y_i, \langle w, x_i \rangle)</tex>, где <tex>\ell(\cdot, \cdot)</tex> — функция потерь (например, квадратичная <tex>\ell(y, \hat{y}) = (y - \hat{y})^2</tex> или логистическая). Задача L1-регуляризации формулируется как минимизация составного функционала:
-:: <tex> \widehat{w}^{\text{LASSO}} = \arg\min_{w} \left\{ \frac{1}{2n} \|y - X w\|_2^2 + \lambda \|w\|_1 \right\}. </tex>
+:: <tex>\hat{w} = \arg\min_{w \in \mathbb{R}^p} \left\{ L(w) + \lambda \|w\|_1 \right\},</tex>
-Геометрическая интерпретация L1-регуляризации связана с заменой нерегуляризованной задачи (которая может быть недоопределена) на задачу условной оптимизации: минимизировать эмпирический риск при ограничении <tex> \|w\|_1 \leqslant t </tex>. Множество <tex> \{w: \|w\|_1 \leqslant t\} </tex> представляет собой <tex>\ell_1</tex>-шар — в <tex>\mathbb{R}^p</tex> это выпуклый многогранник с вершинами на координатных осях. При минимизации квадратичной функции на таком многограннике решение часто достигается в вершине, что соответствует обнулению части координат. Это и обеспечивает разреженность. В отличие от <tex>\ell_2</tex>-шара (гладкая сфера), <tex>\ell_1</tex>-шар имеет «углы» на осях, что способствует отбору признаков.
+где <tex>\lambda \ge 0</tex> — коэффициент регуляризации, а <tex>\|w\|_1 = \sum_{j=1}^p |w_j|</tex> — <tex>\ell_1</tex>-норма вектора параметров.
+В случае линейной регрессии с квадратичной потерей получаем классическую задачу LASSO:
+:: <tex>\hat{w} = \arg\min_{w} \left\{ \frac{1}{2n} \|y - X w\|_2^2 + \lambda \|w\|_1 \right\}.</tex>
+Эквивалентная ограничительная формулировка (для некоторого <tex>t \ge 0</tex>):
+:: <tex>\min_{w: \|w\|_1 \le t} \frac{1}{2n} \|y - X w\|_2^2,</tex>
+где между <tex>\lambda</tex> и <tex>t</tex> существует взаимно однозначное соответствие (при строгой выпуклости задачи).
+=== Геометрическая интерпретация ===
+Геометрический смысл L1-регуляризации становится ясным при рассмотрении ограничительной формулировки. Множество <tex>\{w : \|w\|_1 \le t\}</tex> представляет собой <tex>\ell_1</tex>-шар — выпуклый многогранник, являющийся аналогом октаэдра в размерности <tex>p</tex>. В отличие от <tex>\ell_2</tex>-шара, имеющего гладкую границу, <tex>\ell_1</tex>-шар имеет угловые точки, лежащие на координатных осях. При минимизации квадратичной функции (или другой гладкой функции потерь) на таком многограннике решение с высокой вероятностью достигается в одной из угловых точек, что соответствует обнулению части координат. Это и есть механизм ''разреживания''.
+Важно подчеркнуть, что угловые точки <tex>\ell_1</tex>-шара соответствуют векторам с одним ненулевым элементом. В более высоких размерностях грани многогранника соответствуют разреженным векторам с заданным числом ненулевых координат.
+=== Связь с байесовским подходом ===
+С вероятностной точки зрения L1-регуляризация эквивалентна заданию априорного распределения Лапласа (двустороннего экспоненциального) на параметры модели <tex>w_j \sim \text{Laplace}(0, 1/\lambda)</tex>. Это распределение имеет более тяжёлые хвосты и пик в нуле по сравнению с гауссовским (соответствующим L2-регуляризации), что способствует разреженности апостериорного распределения.
 == Выбор коэффициента регуляризации <tex>\lambda</tex> ==
-Выбор параметра <tex>\lambda</tex> критичен для качества модели. Основные подходы:
+Коэффициент <tex>\lambda</tex> управляет балансом между качеством аппроксимации данных и степенью разреженности решения. Выбор <tex>\lambda</tex> критически влияет на обобщающую способность модели.
+=== Методы кросс-валидации ===
+Наиболее распространённый эмпирический подход — <tex>K</tex>-блочная кросс-валидация (например, <tex>K = 5</tex> или <tex>10</tex>). Для каждого значения <tex>\lambda</tex> из сетки вычисляется средняя ошибка на валидационных блоках; выбирается <tex>\lambda</tex>, минимизирующее эту ошибку. На практике часто используют ''одно стандартное отклонение'' правило (one-standard-error rule): выбирают наибольшее <tex>\lambda</tex>, ошибка которого лежит в пределах одного стандартного отклонения от минимальной, что даёт более разреженную модель без статистически значимой потери качества.
+=== Информационные критерии ===
+Для линейных моделей предложены модификации информационных критериев Акаике (AIC) и Байесовского (BIC), учитывающие эффективное число степеней свободы LASSO. Для квадратичной потери эффективная размерность (degrees of freedom) оценивается как число ненулевых коэффициентов <tex>\| \hat{w} \|_0</tex> (Zou, Hastie, Tibshirani, 2007). Тогда критерии имеют вид:
+:: <tex>\text{AIC}(\lambda) = n \log(\hat{\sigma}^2) + 2 \| \hat{w} \|_0,</tex>
+:: <tex>\text{BIC}(\lambda) = n \log(\hat{\sigma}^2) + \| \hat{w} \|_0 \log n.</tex>
+В случае <tex>p \gg n</tex> BIC часто приводит к более разреженным решениям, чем кросс-валидация.
+=== Универсальные правила ===
+В теории сжатого зондирования известно универсальное правило выбора <tex>\lambda</tex>, обеспечивающее восстановление сигнала с высоким уровнем шума. Для задачи <tex>y = X w^* + \varepsilon</tex> с <tex>\varepsilon \sim \mathcal{N}(0, \sigma^2 I)</tex> часто используют
+:: <tex>\lambda \asymp \sigma \sqrt{2 \log p}</tex>
+(минимаксная оценка). Однако это правило является асимптотическим и на практике часто приводит к излишнему сжатию; для реальных данных его калибруют с помощью кросс-валидации или эмпирического правила Байеса (Efron, 2004).
-* '''Кросс-валидация''' (K-fold cross-validation): выбирается <tex>\lambda</tex>, минимизирующий ошибку прогноза на валидационных выборках. На практике используется сетка значений <tex>\lambda</tex>, часто в логарифмическом масштабе, и выбирается <tex>\lambda_{\text{min}}</tex> или <tex>\lambda_{1\text{se}}</tex> (наибольшее значение, дающее ошибку не более чем на одно стандартное отклонение от минимума) для улучшения устойчивости.
+=== Масштабирование признаков ===
-* '''Информационные критерии''': для линейной регрессии с гауссовским шумом можно использовать модификации AIC или BIC с эффективным числом степеней свободы. Для LASSO доказано, что число степеней свободы равно числу ненулевых коэффициентов<ref>{{статья |автор=Zou, H., Hastie, T., Tibshirani, R. |заглавие=On the “degrees of freedom” of the lasso |ссылка=https://projecteuclid.org/euclid.aos/1201012957 |издание=The Annals of Statistics |год=2007 |том=35 |номер=5 |страницы=2173—2192}}</ref>.
-* '''Универсальные правила''': в контексте сжатого зондирования предложены правила, связывающие <tex>\lambda</tex> с уровнем шума и размерностью, например <tex>\lambda \asymp \sigma \sqrt{\frac{\log p}{n}}</tex> для гарантий восстановления при определённых условиях.
-* '''Эмпирические эвристики''': часто выбирают <tex>\lambda_{\max} = \max_j |\frac{1}{n} (X_j^\top y)|</tex> (при стандартизованных данных), при котором все коэффициенты равны нулю, и строят сетку от <tex>\lambda_{\max}</tex> до <tex>\lambda_{\max} \cdot \varepsilon</tex>.
-'''Особенности работы с признаками:''' перед применением L1-регуляризации признаки необходимо '''стандартизовать''' (центрировать и масштабировать к единичной дисперсии), так как штраф зависит от масштаба каждого признака. В противном случае признаки с большей дисперсией будут иметь меньшие коэффициенты при одинаковом штрафе, что искажает отбор.
+L1-регуляризация зависит от масштаба признаков: если признак <tex>j</tex> умножить на константу <tex>c</tex>, то его коэффициент при неизменном <tex>\lambda</tex> должен быть разделён на <tex>c</tex>, чтобы сохранить штраф. Поэтому перед применением LASSO настоятельно рекомендуется стандартизация всех признаков к нулевому среднему и единичной дисперсии (<tex>x_{ij} \leftarrow \frac{x_{ij} - \bar{x}_j}{\hat{\sigma}_j}</tex>). Это обеспечивает одинаковый масштаб штрафов для всех признаков.
-== Алгоритмы оптимизации ==
+== Алгоритмы оптимизации для L1-регуляризации ==
-Задача L1-регуляризации является выпуклой, но негладкой (из-за модуля). Это требует специальных методов оптимизации.
+Задача (1) является негладкой (из-за <tex>\ell_1</tex>-нормы), но выпуклой. Для её решения разработаны специализированные алгоритмы, использующие структуру субградиента и проксимальные операторы.
 === Проксимальный градиентный спуск (Proximal Gradient Descent) ===
-Для композиции гладкой функции <tex>f(w) = \frac{1}{2n}\|y - Xw\|_2^2</tex> и негладкой <tex>g(w) = \lambda \|w\|_1</tex> применяется итеративная процедура:
+Проксимальный градиентный метод является стандартным подходом для минимизации суммы гладкой выпуклой функции <tex>L(w)</tex> и негладкой <tex>R(w) = \lambda \|w\|_1</tex>. Итерационная формула:
-:: <tex> w^{k+1} = \operatorname{prox}_{\alpha_k g} \left( w^k - \alpha_k \nabla f(w^k) \right), </tex>
+:: <tex>w^{k+1} = \operatorname{prox}_{\alpha R} \left( w^k - \alpha \nabla L(w^k) \right),</tex>
-где <tex>\alpha_k</tex> — шаг (например, постоянный <tex>\alpha = 1 / L</tex>, где <tex>L</tex> — константа Липшица градиента <tex>\nabla f</tex>), а проксимальный оператор для <tex>\ell_1</tex>-нормы — это оператор мягкого порога (soft-thresholding):
+где <tex>\alpha > 0</tex> — шаг (размер шага), а проксимальный оператор для <tex>\ell_1</tex>-нормы имеет вид оператора мягкого порога (soft-thresholding):
-:: <tex> \bigl[ \operatorname{prox}_{\alpha \lambda \|\cdot\|_1} (v) \bigr]_j = \operatorname{sign}(v_j) \max(|v_j| - \alpha \lambda, 0). </tex>
+:: <tex>\big( \operatorname{prox}_{\alpha \lambda \|\cdot\|_1}(z) \big)_j = \operatorname{sign}(z_j) \max\{ |z_j| - \alpha \lambda, 0 \}.</tex>
-'''Псевдокод:'''
+'''Псевдокод (неускоренный вариант):'''
-* Инициализация: <tex>w^{(0)} = 0</tex>, выбрать <tex>\alpha = 1 / \lambda_{\max}(X^\top X/n)</tex> (или использовать правило Армихо для выбора шага).
-* Для <tex>k = 0, 1, 2, \ldots</tex> до сходимости:
-* # Вычислить градиент: <tex> \nabla f(w^{(k)}) = \frac{1}{n} X^\top (X w^{(k)} - y) </tex>.
-* # Вычислить <tex> v = w^{(k)} - \alpha \nabla f(w^{(k)}) </tex>.
-* # Применить мягкий порог: <tex> w^{(k+1)}_j = \operatorname{sign}(v_j) \max(|v_j| - \alpha \lambda, 0) </tex>.
-'''Оценка сходимости:''' при постоянном шаге <tex>\alpha = 1/L</tex> проксимальный градиентный метод сходится со скоростью <tex>O(1/k)</tex> по значению функции. Для ускоренной версии (FISTA) достигается скорость <tex>O(1/k^2)</tex><ref>{{статья |автор=Beck, A., Teboulle, M. |заглавие=A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems |ссылка=https://epubs.siam.org/doi/10.1137/080716542 |издание=SIAM Journal on Imaging Sciences |год=2009 |том=2 |номер=1 |страницы=183—202}}</ref>. Вычислительная сложность на итерацию — <tex>O(np)</tex>, что делает метод применимым для задач среднего размера.
+* Вход: <tex>X, y, \lambda</tex>, начальное приближение <tex>w^0</tex>, максимальное число итераций <tex>K</tex>, параметр остановки <tex>\varepsilon</tex>.
+* Для <tex>k = 0, 1, \ldots, K-1</tex>:
+** Вычислить градиент: <tex>g^k = \nabla L(w^k)</tex>.
+** Сделать шаг градиентного спуска: <tex>z^{k} = w^k - \alpha_k g^k</tex>.
+** Применить мягкий порог: <tex>w^{k+1} = S_{\alpha_k \lambda}(z^{k})</tex>.
+** Если <tex>\|w^{k+1} - w^k\|_2 < \varepsilon</tex>, остановиться.
+* Вернуть <tex>w^{K}</tex>.
+'''Оценка сходимости:''' Если <tex>L</tex> имеет <tex>\beta</tex>-липшицев градиент, то при выборе шага <tex>\alpha_k = 1/\beta</tex> метод сходится со скоростью <tex>O(1/k)</tex> по значению функции. Ускоренный вариант (FISTA<ref name="beck2009">{{статья |автор= Beck A., Teboulle M. |заглавие= A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems |ссылка= https://epubs.siam.org/doi/10.1137/080716542 |издание= SIAM Journal on Imaging Sciences |год= 2009 |том= 2 |номер= 1 |страницы= 183—202}}</ref>) имеет скорость <tex>O(1/k^2)</tex>. Вычислительная сложность одной итерации составляет <tex>O(np)</tex> для вычисления градиента.
 === Координатный спуск (Coordinate Descent) ===
-Наиболее популярный метод для LASSO в пакетах (например, `glmnet`). На каждой итерации последовательно обновляется одна координата <tex>w_j</tex> при фиксированных остальных. Для квадратичной потери обновление имеет аналитическую формулу:
+Координатный спуск является наиболее эффективным для LASSO при больших <tex>n</tex> и <tex>p</tex>, особенно в реализации [[GLMNET]]<ref name="friedman2010">{{статья |автор= Friedman J., Hastie T., Tibshirani R. |заглавие= Regularization Paths for Generalized Linear Models via Coordinate Descent |ссылка= https://www.jstatsoft.org/article/view/v033i01 |издание= Journal of Statistical Software |год= 2010 |том= 33 |номер= 1 |страницы= 1—22}}</ref>. Алгоритм циклически обновляет каждый коэффициент, решая одномерную задачу с мягким порогом. Для линейной регрессии обновление для <tex>j</tex>-го коэффициента имеет вид:
-:: <tex> w_j^{\text{new}} = \frac{ S\left( \frac{1}{n} \sum_{i=1}^n x_{ij} (y_i - \sum_{k \ne j} x_{ik} w_k), \lambda \right) }{ \frac{1}{n} \sum_{i=1}^n x_{ij}^2 }, </tex>
+:: <tex>w_j^{\text{new}} = \frac{S\left( \sum_{i=1}^n x_{ij} (y_i - \sum_{k \neq j} x_{ik} w_k), \lambda \right)}{\sum_{i=1}^n x_{ij}^2}.</tex>
-где <tex>S(z, \lambda) = \operatorname{sign}(z) \max(|z| - \lambda, 0)</tex> — мягкий порог.
+Этот алгоритм чрезвычайно быстр для разреженных решений и хорошо масштабируется на <tex>p \sim 10^6</tex>. Сходимость координатного спуска для выпуклых дифференцируемых функций с сепарабельным регуляризатором доказана (Tseng, 2001).
-'''Псевдокод (циклический координатный спуск):'''
+=== Метод наименьших углов (LARS) ===
-* Инициализация: <tex>w = 0</tex> (или с предыдущего решения для пути регуляризации).
-* Пока не выполнено условие остановки:
-* # Для <tex>j = 1</tex> до <tex>p</tex>:
-* ## Вычислить частичный остаток <tex> r_j = y - \sum_{k \ne j} X_k w_k </tex> (на практике поддерживается вектор остатков <tex>r = y - Xw</tex>).
-* ## Вычислить <tex> z_j = \frac{1}{n} X_j^\top r_j </tex>.
-* ## Обновить: <tex> w_j^{\text{new}} = S(z_j, \lambda) / \left( \frac{1}{n} \|X_j\|_2^2 \right) </tex>.
-* ## Обновить остаток: <tex> r \leftarrow r - X_j (w_j^{\text{new}} - w_j^{\text{old}}) </tex>.
-'''Оценка сходимости:''' для выпуклых дифференцируемых функций координатный спуск сходится к глобальному минимуму со скоростью как минимум линейной при соблюдении условий (например, строгой выпуклости на активном множестве)<ref>{{книга |автор=Wright, S. J. |заглавие=Coordinate descent algorithms |ссылка=https://link.springer.com/article/10.1007/s10107-015-0892-3 |издание=Mathematical Programming |год=2015 |том=151 |номер=1 |страницы=3—34}}</ref>. Вычислительная сложность одной полной итерации по всем координатам — <tex>O(np)</tex>, но на практике метод часто быстрее проксимального градиента для больших <tex>p</tex> и разреженных решений, так как использует структуру задачи.
+Алгоритм LARS (Efron et al., 2004) позволяет эффективно строить весь регуляризационный путь LASSO при квадратичной потере. Вычислительная сложность LARS сравнима со сложностью вычисления одного МНК-решения (<tex>O(p^3 + n p^2)</tex>), что делает его полезным для умеренных <tex>p</tex>, но неэффективным при <tex>p \gg n</tex>.
 === Альтернативные методы ===
-* '''Метод наименьших углов (LARS)''' — даёт точное решение для всего пути регуляризации LASSO за <tex>O(p^3 + np^2)</tex> (неэффективен для больших <tex>p</tex>).
+* '''Алгоритм ADMM''' (Alternating Direction Method of Multipliers) — эффективен для распределённых вычислений и задач с дополнительными линейными ограничениями.
-* '''Алгоритмы на основе SWAP (например, для обобщённого LASSO)''' — используются в задачах с дополнительными структурными ограничениями.
+* '''Субградиентные методы''' — просты, но имеют медленную сходимость <tex>O(1/\sqrt{k})</tex>.
-* '''Стохастические методы''' (SAG, SVRG) — применимы для больших <tex>n</tex>, но требуют модификаций для работы с <tex>\ell_1</tex>-штрафом (например, проксимальный SVRG).
+* '''Квазиньютоновские методы с проксимальной модификацией''' (например, L-BFGS-B) — применяются для задач с ограничениями.
-'''Выбор алгоритма:'''
+Для задач с <tex>n \gg p</tex> предпочтителен координатный спуск; для <tex>p \gg n</tex> и очень больших данных (разреженные матрицы) — проксимальные методы с использованием случайных подвыборок градиента (SVRG, SAGA).
-* Для <tex>p \lesssim 10^4</tex> и <tex>n \lesssim 10^5</tex> — координатный спуск (реализация `glmnet`).
-* Для задач с очень большим <tex>p</tex> (например, <tex>p > 10^5</tex>) и разреженным истинным вектором — методы, использующие активные множества или ускоренный проксимальный градиент.
-* При ограниченных вычислительных ресурсах и необходимости быстрого приближения — FISTA.
-* Для распределённых вычислений — используют ADMM (Alternating Direction Method of Multipliers), который разбивает задачу на подзадачи.
 == Теоретические свойства ==
-Теория L1-регуляризации активно развивается с конца 1990-х годов. Основные результаты касаются условий восстановления истинного разреженного вектора и оценок обобщающей способности.
+Теория L1-регуляризации опирается на условия на матрицу признаков <tex>X</tex> и уровень шума. Основные результаты формулируются в терминах восстановления (support recovery) и предсказательной точности (prediction consistency).
-=== Условия восстановления ===
+=== Условия восстановления носителя ===
-Пусть истинный вектор <tex>w^*</tex> имеет <tex>s = \|w^*\|_0</tex> ненулевых компонент. Рассмотрим линейную модель <tex>y = X w^* + \varepsilon</tex>, где <tex>\varepsilon \sim \mathcal{N}(0, \sigma^2 I_n)</tex>. Для гарантированного восстановления <tex>w^*</tex> по LASSO (с вероятностью <tex>\geqslant 1 - \delta</tex>) достаточно выполнения одного из следующих условий на матрицу <tex>X</tex>:
+Для асимптотического восстановления истинного носителя <tex>S = \{j: w_j^* \neq 0\}</tex> требуется ''условие взаимной некоррелированности признаков''. Классическое ''Neighborhood stability condition'' (Zhao & Yu, 2006) и ''Irrepresentable condition'' требуют, чтобы корреляция между признаками из <tex>S</tex> и вне <tex>S</tex> была ограничена:
-* '''Условие ограниченной изометрии (Restricted Isometry Property, RIP)''': для всех <tex>s</tex>-разреженных векторов <tex>v</tex> выполняется
+:: <tex>\| X_{S^c}^\top X_S (X_S^\top X_S)^{-1} \|_\infty \le 1 - \gamma</tex>
-  :: <tex> (1 - \delta_s) \|v\|_2^2 \leqslant \frac{1}{n}\|X v\|_2^2 \leqslant (1 + \delta_s) \|v\|_2^2 </tex>
-  при <tex>\delta_{2s} \lesssim 1/\sqrt{s}</tex>. Это условие обеспечивает устойчивое восстановление при <tex>\lambda \asymp \sigma \sqrt{\frac{\log p}{n}}</tex><ref>{{статья |автор=Candès, E. J., Tao, T. |заглавие=Decoding by Linear Programming |ссылка=https://ieeexplore.ieee.org/document/1458136 |издание=IEEE Transactions on Information Theory |год=2005 |том=51 |номер=12 |страницы=4203—4215}}</ref>.
-* '''Условие взаимной некоррелированности (Mutual Coherence)''' — более сильное, но легко проверяемое: максимальное абсолютное значение скалярного произведения между различными столбцами (после нормализации) <tex>\mu</tex> должно удовлетворять <tex>\mu \lesssim 1/(s \log p)</tex>. При этом LASSO восстанавливает носитель точно.
+для некоторого <tex>\gamma > 0</tex>. Это условие является необходимым и достаточным для восстановления носителя в асимптотике при правильном выборе <tex>\lambda \asymp \sqrt{\frac{\log p}{n}}</tex>.
-* '''Условие строгого неравенства собственных значений (Restricted Eigenvalue Condition)''' — более слабое, чем RIP, достаточно для получения оценок предсказания и <tex>\ell_2</tex>-нормы ошибки<ref>{{статья |автор=Bickel, P. J., Ritov, Y., Tsybakov, A. B. |заглавие=Simultaneous analysis of Lasso and Dantzig selector |ссылка=https://projecteuclid.org/euclid.aos/1223908047 |издание=The Annals of Statistics |год=2009 |том=37 |номер=4 |страницы=1705—1732}}</ref>.
+=== Неравенства оракула и скорости сходимости ===
-=== Неравенства оракула ===
+В условиях ограниченного собственного значения (Restricted Eigenvalue condition — RE) или [[Restricted Isometry Property|Restricted Isometry Property (RIP)]]<ref name="candes2006">{{статья |автор= Candes E. J., Tao T. |заглавие= Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? |ссылка= https://ieeexplore.ieee.org/document/1614062 |издание= IEEE Transactions on Information Theory |год= 2006 |том= 52 |номер= 12 |страницы= 5406—5425}}</ref> для LASSO можно получить неравенство оракула:
-Неравенство оракула гарантирует, что оценка LASSO по качеству предсказания (среднеквадратичной ошибке) не хуже оценки, которую дал бы идеальный оракул, знающий истинный носитель (набор ненулевых коэффициентов), с точностью до множителя, зависящего от логарифма числа признаков. В типичных условиях (например, при выполнении условия Restricted Eigenvalue) для квадратичной потери справедливо:
+:: <tex>\| \hat{w} - w^* \|_2^2 \le C \cdot \frac{s \log p}{n},</tex>
-:: <tex> \frac{1}{n} |X(\widehat{w} - w^*)|_2^2 \lesssim \sigma^2 \frac{s \log p}{n}, </tex>
+где <tex>s = \| w^* \|_0</tex> — число ненулевых компонент, а <tex>C</tex> — константа, зависящая от RE-константы. Это гарантирует, что LASSO адаптируется к неизвестной разреженности: скорость сходимости определяется эффективной размерностью <tex>s</tex>, а не полной <tex>p</tex>.
-где <tex>s</tex> — число ненулевых коэффициентов, <tex>\sigma^2</tex> — дисперсия шума. Это означает, что LASSO достигает минимаксной (оптимальной) скорости сходимости для разреженных моделей, платя лишь логарифмическую цену за неизвестность носителя.
+В терминах ошибки предсказания:
-=== Оценки сходимости в терминах числа ненулевых элементов ===
+:: <tex>\frac{1}{n} \| X \hat{w} - X w^* \|_2^2 \le C \cdot \frac{s \log p}{n}</tex>
-При выполнении условий ограниченной изометрии или взаимной некоррелированности, LASSO обеспечивает:
+при <tex>\lambda \asymp \sqrt{\frac{\log p}{n}}</tex> и условии RE (Bickel, Ritov, Tsybakov, 2009; van de Geer, 2008).
-* <tex> \|\widehat{w} - w^*\|_2 \lesssim \sigma \sqrt{\frac{s \log p}{n}} </tex> (это минимаксная скорость для <tex>\ell_2</tex>-нормы при <tex>s</tex>-разреженном векторе).
+=== Асимптотическое распределение ===
-* Точное восстановление носителя (support recovery) при условии «минимального сигнала» (beta-min): <tex>\min_{j \in \operatorname{supp}(w^*)} |w^*_j| \gtrsim \sigma \sqrt{\frac{\log p}{n}}</tex>.
+В классической асимптотике <tex>p</tex> фиксировано, <tex>n \to \infty</tex>, LASSO не является асимптотически нормальным для ненулевых коэффициентов из-за сжатия (shrinkage). Однако существуют модификации (например, деспарсифицированный LASSO или ''LASSO с поправкой'', см. Javanmard & Montanari, 2014), позволяющие строить доверительные интервалы.
 == Применения в машинном обучении ==
@@ Строка 116: / Строка 145: @@
 L1-регуляризация используется в широком спектре задач:
-* '''Линейная и логистическая регрессия''' — для отбора признаков и повышения интерпретируемости модели.
+* '''Линейная и логистическая регрессия''' — отбор наиболее значимых признаков в медицине, биоинформатике, социальных науках.
-* '''Сжатое зондирование''' — восстановление сигналов по недостаточному числу измерений.
+* '''Сжатое зондирование''' — восстановление сигналов (изображений, аудио) из неполных измерений с помощью <tex>\ell_1</tex>-минимизации (Candes, Romberg, Tao, 2006).
-* '''Обработка текстов''' — в задачах классификации документов с большим числом терминов (Bag-of-Words) для выделения значимых слов.
+* '''Обучение словарей''' (dictionary learning) — разреженное представление данных.
-* '''Генетические данные''' — анализ экспрессии генов (<tex>p \gg n</tex>), где важно выделить небольшое число релевантных генов.
+* '''Глубокое обучение''' — L1-регуляризация применяется к весам слоёв для их разреживания, что позволяет сократить память и ускорить вывод (например, ''обрезка'' нейронных сетей). В последние годы появились работы о групповой разреженности и структурной разреженности в свёрточных сетях.
-* '''Рекомендательные системы''' — построение разреженных матриц предпочтений.
+* '''Матричное сжатие''' — в задаче низкорангового восстановления с использованием ядерной нормы (аналог L1 для сингулярных чисел).
-* '''Обучение признаков''' — в нейросетях применяются варианты L1-регуляризации для разреживания весов (например, в задачах сжатия моделей).
+* '''Обработка естественного языка''' — отбор признаков для моделей [[Bag-of-words|мешка слов]] с размерностью <tex>p \sim 10^5</tex> и выше.
-В глубоком обучении L1-регуляризация используется реже из-за проблем с недифференцируемостью и медленной сходимостью при больших размерах сетей, однако она применяется для разреживания полносвязных слоёв и в некоторых архитектурах с использованием групповой разреженности.
+== Сравнение L1-регуляризации с L2-регуляризацией ==
-== Сравнение L1 и L2-регуляризации ==
+L2-регуляризация ([[ридж-регрессия]], [[Tikhonov regularization]]) использует штраф <tex>\lambda \|w\|_2^2</tex>. Принципиальные различия:
-L2-регуляризация (гребневая регрессия, Ridge) добавляет штраф <tex>\lambda \|w\|_2^2</tex>. Основные различия:
+* '''Разреженность''': L1 даёт разреженные решения, L2 — нет (все коэффициенты, как правило, ненулевые).
+* '''Устойчивость''': L2-регуляризация строго выпукла и имеет единственное решение; L1 при <tex>p > n</tex> может иметь неединственное решение (если матрица вырождена).
+* '''Поведение при коррелированных признаках''': L1 склонен выбирать только один признак из сильно коррелированной группы (эффект «выбора одной из группы»), тогда как L2 сглаживает коэффициенты внутри группы, придавая им схожие значения. Это ограничение L1 породило групповые варианты (см. ниже).
+* '''Смещение и дисперсия''': L1 вносит большее смещение для больших коэффициентов по сравнению с L2, но может давать меньшее среднеквадратичное отклонение в разреженных сценариях.
+* '''Вычислительные аспекты''': L2 сводится к решению линейной системы (можно аналитически), L1 требует итеративных методов.
-{| class="wikitable"
+== Ограничения L1-регуляризации и их преодоление ==
-! Свойство !! L1 (LASSO) !! L2 (Ridge)
-|-
-| Разреженность || Да (коэффициенты обнуляются) || Нет (все коэффициенты ненулевые)
-|-
-| Отбор признаков || Встроенный || Отсутствует
-|-
-| Устойчивость решений || Может быть неединственной (при <tex>p > n</tex> или коррелированных признаках) || Единственна (строго выпукла)
-|-
-| Поведение при коррелированных признаках || Выбирает один из группы, остальные обнуляет (нестабильно) || Сглаживает коэффициенты между коррелированными признаками
-|-
-| Вычислительная сложность || Выше (нужна оптимизация негладкой функции) || Ниже (аналитическое решение для линейной регрессии)
-|-
-| Смещение (для ненулевых коэффициентов) || Смещён в сторону нуля (сжатие) || Смещён в сторону нуля (гладкое сжатие)
-|-
-| Дисперсия || Меньше, чем у нерегуляризованного МНК, но может быть выше, чем у Ridge при сильной корреляции || Обычно даёт меньшую дисперсию, чем LASSO, при коррелированных признаках
-|-
-| Геометрия шара || Многогранник с углами || Гладкая сфера
-|}
-Компромиссный вариант — '''Elastic Net'''<ref>{{статья |автор=Zou, H., Hastie, T. |заглавие=Regularization and variable selection via the elastic net |ссылка=https://www.jstor.org/stable/3647480 |издание=Journal of the Royal Statistical Society: Series B |год=2005 |том=67 |номер=2 |страницы=301—320}}</ref>, объединяющий L1 и L2 штрафы: <tex>\lambda_1 \|w\|_1 + \lambda_2 \|w\|_2^2</tex>. Он позволяет отбирать группы коррелированных признаков и сохраняет устойчивость.
+=== Насыщение при <tex>p \gg n</tex> ===
-== Ограничения L1-регуляризации ==
+При <tex>p \gg n</tex> LASSO может выбрать максимум <tex>n</tex> ненулевых коэффициентов (в силу ограничений геометрии). Если истинный носитель больше <tex>n</tex>, LASSO не способен его восстановить. В таких случаях используют другие регуляризаторы (например, эластичная сеть, групповой LASSO) или используют двухэтапные процедуры (marginal screening, ISIS).
-Несмотря на популярность, LASSO имеет ряд серьёзных ограничений:
+=== Неединственность решения ===
-* '''Насыщение при <tex>p \gg n</tex>''': LASSO может выбрать не более <tex>n</tex> признаков (если <tex>p > n</tex>), что является следствием геометрии <tex>\ell_1</tex>-шара в размерности <tex>p</tex> и свойствами опорных гиперплоскостей. Это ограничение можно обойти с помощью Elastic Net или группового LASSO.
+При <tex>p > n</tex> и недостаточной регуляризации задача может иметь бесконечно много решений. Этого избегают, либо добавляя малую L2-регуляризацию (эластичная сеть), либо используя выбор решения с минимальной <tex>\ell_2</tex>-нормой среди всех решений LASSO.
-* '''Неединственность решения''': при <tex>p > n</tex> или при наличии коррелированных признаков решение LASSO не всегда единственно. Это может затруднить интерпретацию и воспроизводимость.
-* '''Проблемы с группами сильно коррелированных признаков''': LASSO склонен выбирать один признак из группы, игнорируя остальные, что может быть нежелательно, если признаки имеют совместную предсказательную силу. Для этого существуют варианты: групповой LASSO (Group LASSO) и разреженный групповой LASSO (Sparse Group LASSO).
-* '''Чувствительность к масштабу данных''': требует обязательной стандартизации, иначе масштаб признака влияет на величину штрафа.
-* '''Необходимость тщательной настройки <tex>\lambda</tex>''': неправильный выбор может привести к переобучению (малое <tex>\lambda</tex>) или к чрезмерному сжатию и смещению (большое <tex>\lambda</tex>).
-* '''Несостоятельность при некоторых типах корреляции''': LASSO не является состоятельным для выбора переменных (variable selection consistency) без выполнения условия «строгой взаимной некоррелированности» или условия «неравенства на корреляции между значимыми и незначимыми признаками». Для обеспечения состоятельности разработаны модификации, такие как адаптивный LASSO (Adaptive LASSO)<ref>{{статья |автор=Zou, H. |заглавие=The Adaptive Lasso and Its Oracle Properties |ссылка=https://projecteuclid.org/euclid.jas/1225396872 |издание=Journal of the American Statistical Association |год=2006 |том=101 |номер=476 |страницы=1418—1429}}</ref>, который использует весовые коэффициенты <tex>\lambda_j = \lambda / |\widehat{w}_j^{\text{initial}}|^\gamma</tex> на основе начальной оценки.
-== Современные обобщения и альтернативы ==
+=== Коррелированные признаки ===
-* '''Невыпуклые альтернативы''' (SCAD, MCP)<ref>{{статья |автор=Fan, J., Li, R. |заглавие=Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties |ссылка=https://projecteuclid.org/euclid.jas/1074872391 |издание=Journal of the American Statistical Association |год=2001 |том=96 |номер=456 |страницы=1348—1360}}</ref> — обеспечивают меньшее смещение для больших коэффициентов и сохраняют разреженность, но задача становится невыпуклой, что требует специальных алгоритмов (например, локальный квадратичный аппроксимация). Они обладают оракульными свойствами (асимптотически ведут себя как МНК на истинном носителе).
+LASSO неустойчив при высокой корреляции: он выбирает одну переменную случайным образом, что снижает интерпретируемость. Решение — [[Elastic Net|эластичная сеть]] (Zou & Hastie, 2005), объединяющая штрафы <tex>\lambda \|w\|_1 + \gamma \|w\|_2^2</tex>, что обеспечивает стабильность и отбор групп.
-* '''Групповой LASSO''' — штраф на группы признаков: <tex>\sum_{g \in G} \|w_g\|_2</tex>, что позволяет включать или исключать целые группы (например, категориальные переменные).
-* '''Разреженный групповой LASSO''' — комбинация <tex>\ell_1</tex> и группового штрафа для разреженности как внутри, так и между группами.
-* '''Обобщения для глубокого обучения''' — например, '''глобальная разреженность''' (Global Sparsity) через групповую регуляризацию весов, а также использование L1-регуляризации в байесовских нейросетях для автоматического определения значимости нейронов (variational dropout с L1-штрафами).
-* '''Структурированное сжатое зондирование''' — учёт дополнительной структуры (например, разреженность в частотной области, ранговые ограничения) через композицию норм.
-* '''Интеграция с методами глубокого обучения''' — например, L1-регуляризация активаций (sparse autoencoders) для получения разреженных представлений.
+=== Чувствительность к масштабу ===
+Требуется стандартизация признаков; в противном случае штрафы для различных признаков несопоставимы.
-== Заключение ==
+=== Тщательная настройка <tex>\lambda</tex> ===
-L1-регуляризация является фундаментальным инструментом современной статистики и машинного обучения, обеспечивающим разреженные и интерпретируемые модели. Её теоретическая база (условия восстановления, оракульные неравенства) хорошо разработана, а вычислительные методы (координатный спуск, проксимальный градиент) позволяют решать задачи с размерностью до сотен тысяч и миллионов признаков. Однако практическое применение требует учёта ограничений: чувствительности к корреляции, неединственности, необходимости стандартизации и аккуратного выбора <tex>\lambda</tex>. Современные исследования направлены на создание адаптивных вариантов, интеграцию с глубокими архитектурами и развитие невыпуклых подходов для улучшения статистических свойств. Для большинства прикладных задач рекомендуется начинать с Elastic Net или адаптивного LASSO, а выбор оптимизатора диктовать размерностью данных и доступными вычислительными ресурсами.
+Результаты сильно зависят от выбора <tex>\lambda</tex>. Рекомендуется использовать кросс-валидацию с тщательной калибровкой сетки.
+=== Невыпуклые альтернативы ===
+Для улучшения восстановления предложены невыпуклые регуляризаторы, аппроксимирующие <tex>\ell_0</tex>-норму (например, MCP<ref name="zhang2010">{{статья |автор= Zhang C.-H. |заглавие= Nearly Unbiased Variable Selection Under Minimax Concave Penalty |ссылка= https://projecteuclid.org/euclid.aos/1266586616 |издание= The Annals of Statistics |год= 2010 |том= 38 |номер= 2 |страницы= 894—942}}</ref>, SCAD<ref name="fan2001">{{статья |автор= Fan J., Li R. |заглавие= Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties |ссылка= https://www.jstor.org/stable/2670143 |издание= Journal of the American Statistical Association |год= 2001 |том= 96 |номер= 456 |страницы= 1348—1360}}</ref>). Они обладают свойством оракула (асимптотически дают несмещённые оценки) и менее смещены для больших коэффициентов. Однако их оптимизация сложнее из-за невыпуклости (требуется многократный запуск, возникают локальные минимумы).
+== Современные обобщения и направления исследований ==
+* '''Групповой LASSO''' (Yuan & Lin, 2006) — штрафует группы признаков как <tex>\sum_{g} \|w_g\|_2</tex>, позволяя включать или исключать целые группы.
+* '''Структурированный LASSO''' — учитывает иерархию (например, тенденции, спайковые и гладкие компоненты).
+* '''Адаптивный LASSO''' (Zou, 2006) — использует веса <tex>w_j^*</tex>, полученные из начальной оценки, для улучшения теоретических свойств (устранение смещения).
+* '''Квадратичный LASSO''' и обобщения на экспоненциальное семейство ([[Обобщённая линейная модель|GLM]]).
+* '''L1-регуляризация в нейронных сетях''' — активно применяется для разреживания весов при обучении с глубокими архитектурами; комбинируется с групповой разреженностью для сжатия сетей (Sparse Group Lasso).
+* '''Теория двойного спуска''' (double descent) — в некоторых работах показано, что LASSO в перепараметризованных моделях демонстрирует пик обобщающей ошибки при <tex>p \approx n</tex>, но при <tex>p \gg n</tex> ошибка может снова уменьшаться (интерполяционный режим).
+== Практические рекомендации по выбору алгоритма оптимизации ==
+Выбор алгоритма зависит от размерности данных <tex>(n, p)</tex>, структуры матрицы <tex>X</tex> (плотная/разреженная), требуемой точности и доступных вычислительных ресурсов.
+* '''Для малых <tex>p</tex> (<tex>p \lesssim 1000</tex>) и <tex>n</tex> умеренного:''' можно использовать LARS для получения всего пути, либо координатный спуск.
+* '''Для <tex>p</tex> от <tex>10^3</tex> до <tex>10^5</tex>, плотные данные:''' предпочтительнее координатный спуск (GLMNET). Он хорошо использует локальность обновлений и кеширование.
+* '''Для <tex>p \gg n</tex> и разреженных матриц:''' проксимальные методы с ускорением (FISTA) или стохастические варианты (SAGA, SVRG). Координатный спуск может работать медленно, если данные не удовлетворяют условию «путь разрежен».
+* '''Для распределённых вычислений или систем с ограниченной памятью:''' ADMM, позволяющий разбивать задачу на подзадачи.
+* '''Для задач с высокими требованиями к точности:''' рекомендуется использовать методы второго порядка (например, проксимальный Ньютон) или сочетание координатного спуска и BFGS-подобных аппроксимаций (например, алгоритм QUIC для <tex>\ell_1</tex>-графических моделей).
+* '''При наличии априорной информации о структуре разреженности:''' использовать адаптированные методы (например, групповой LASSO + блок-координатный спуск).
+Важно: на этапе подбора <tex>\lambda</tex> обычно строят регуляризационный путь — последовательность решений для убывающей сетки <tex>\lambda</tex>, используя тёплый старт. Это значительно ускоряет вычисления.
+== Примечания ==
-== Литература ==
 <references/>
-* {{статья |автор=Tibshirani, R. |заглавие=Regression Shrinkage and Selection via the Lasso |ссылка=https://www.jstor.org/stable/2346178 |издание=Journal of the Royal Statistical Society. Series B (Methodological) |год=1996 |том=58 |номер=1 |страницы=267—288}}
+== Литература ==
-* {{статья |автор=Candès, E. J., Tao, T. |заглавие=Decoding by Linear Programming |ссылка=https://ieeexplore.ieee.org/document/1458136 |издание=IEEE Transactions on Information Theory |год=2005 |том=51 |номер=12 |страницы=4203—4215}}
-* {{книга |автор=Hastie, T., Tibshirani, R., Wainwright, M. |заглавие=Statistical Learning with Sparsity: The Lasso and Generalizations |ссылка=https://www.stat.berkeley.edu/~ryantibs/statlearn-sls/ |место=Boca Raton |издательство=CRC Press |год=2015}}
+* {{статья |автор= Tibshirani R. |заглавие= Regression Shrinkage and Selection via the Lasso |ссылка= https://www.jstor.org/stable/2346178 |издание= Journal of the Royal Statistical Society. Series B (Methodological) |год= 1996 |том= 58 |номер= 1 |страницы= 267—288}}
-* {{книга |автор=Bühlmann, P., van de Geer, S. |заглавие=Statistics for High-Dimensional Data: Methods, Theory and Applications |издательство=Springer |год=2011}}
+* {{статья |автор= Candes E. J., Tao T. |заглавие= Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? |ссылка= https://ieeexplore.ieee.org/document/1614062 |издание= IEEE Transactions on Information Theory |год= 2006 |том= 52 |номер= 12 |страницы= 5406—5425}}
-* {{статья |автор=Beck, A., Teboulle, M. |заглавие=A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems |ссылка=https://epubs.siam.org/doi/10.1137/080716542 |издание=SIAM Journal on Imaging Sciences |год=2009 |том=2 |номер=1 |страницы=183—202}}
+* {{статья |автор= Friedman J., Hastie T., Tibshirani R. |заглавие= Regularization Paths for Generalized Linear Models via Coordinate Descent |ссылка= https://www.jstatsoft.org/article/view/v033i01 |издание= Journal of Statistical Software |год= 2010 |том= 33 |номер= 1 |страницы= 1—22}}
-* {{статья |автор=Friedman, J., Hastie, T., Tibshirani, R. |заглавие=Regularization Paths for Generalized Linear Models via Coordinate Descent |ссылка=https://www.jstatsoft.org/article/view/v033i01 |издание=Journal of Statistical Software |год=2010 |том=33 |номер=1 |страницы=1—22}}
+* {{статья |автор= Beck A., Teboulle M. |заглавие= A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems |ссылка= https://epubs.siam.org/doi/10.1137/080716542 |издание= SIAM Journal on Imaging Sciences |год= 2009 |том= 2 |номер= 1 |страницы= 183—202}}
-* {{статья |автор=Zou, H., Hastie, T. |заглавие=Regularization and variable selection via the elastic net |ссылка=https://www.jstor.org/stable/3647480 |издание=Journal of the Royal Statistical Society: Series B |год=2005 |том=67 |номер=2 |страницы=301—320}}
+* {{статья |автор= Zhao P., Yu B. |заглавие= On Model Selection Consistency of Lasso |ссылка= https://www.jmlr.org/papers/v7/zhao06a.html |издание= Journal of Machine Learning Research |год= 2006 |том= 7 |страницы= 2541—2563}}
-* {{статья |автор=Fan, J., Li, R. |заглавие=Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties |ссылка=https://projecteuclid.org/euclid.jas/1074872391 |издание=Journal of the American Statistical Association |год=2001 |том=96 |номер=456 |страницы=1348—1360}}
+* {{статья |автор= Bickel P. J., Ritov Y., Tsybakov A. B. |заглавие= Simultaneous Analysis of Lasso and Dantzig Selector |ссылка= https://projecteuclid.org/euclid.aos/1233841879 |издание= The Annals of Statistics |год= 2009 |том= 37 |номер= 4 |страницы= 1705—1732}}
-* {{статья |автор=El Ghaoui, L., Viallon, V., Rabbani, T. |заглавие=Safe Feature Elimination for the Lasso and Sparse Supervised Learning |ссылка=https://jmlr.org/papers/v13/elghaoui12a.html |издание=Journal of Machine Learning Research |год=2012 |том=13 |страницы=581—599}}
+* {{статья |автор= Zou H., Hastie T. |заглавие= Regularization and Variable Selection via the Elastic Net |ссылка= https://www.jstor.org/stable/3647580 |издание= Journal of the Royal Statistical Society. Series B (Statistical Methodology) |год= 2005 |том= 67 |номер= 2 |страницы= 301—320}}
-* {{cite web |url=https://web.stanford.edu/~hastie/glmnet/glmnet_alpha.html |title=GLMNET: Lasso and Elastic-Net Regularized Generalized Linear Models |author=Friedman, J., Hastie, T., Tibshirani, R. |access-date=2026-07-16}}
+* {{статья |автор= Zhang C.-H. |заглавие= Nearly Unbiased Variable Selection Under Minimax Concave Penalty |ссылка= https://projecteuclid.org/euclid.aos/1266586616 |издание= The Annals of Statistics |год= 2010 |том= 38 |номер= 2 |страницы= 894—942}}
+* {{статья |автор= Fan J., Li R. |заглавие= Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties |ссылка= https://www.jstor.org/stable/2670143 |издание= Journal of the American Statistical Association |год= 2001 |том= 96 |номер= 456 |страницы= 1348—1360}}
+* {{книга |автор= Hastie T., Tibshirani R., Friedman J. |заглавие= The Elements of Statistical Learning: Data Mining, Inference, and Prediction |издание= 2nd ed. |место= New York |издательство= Springer |год= 2009 |страницы= 61—79}}
+* {{книга |автор= Bühlmann P., van de Geer S. |заглавие= Statistics for High-Dimensional Data: Methods, Theory and Applications |место= Heidelberg |издательство= Springer |год= 2011}}
+== См. также ==
+* [[LASSO]]
+* [[Регуляризация]]
+* [[Сжатое зондирование]]
+* [[Проксимальный градиентный спуск]]
+* [[Координатный спуск]]
+* [[Restricted Isometry Property]]
+* [[Эластичная сеть]]
+* [[Групповой LASSO]]
 [[Категория:Регуляризация]]
 [[Категория:Линейные модели]]
 [[Категория:Машинное обучение]]
-[[Категория:Высокоразмерная статистика]]
+[[Категория:Статистическое обучение]]