Производные и распределение остатков регуляризованных M-оценок с приложением к адаптивной настройке

Основная информация

• ID статьи: 2107.05143
• Название: Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning
• Авторы: Pierre C. Bellec (Rutgers University), Yiwei Shen (Rutgers University)
• Классификация: math.ST stat.ML stat.TH
• Конференция публикации: Proceedings of Machine Learning Research vol 178:1–36, 2022
• Ссылка на статью: https://arxiv.org/abs/2107.05143

Аннотация

В данной работе исследуются M-оценки с функциями потерь, имеющими липшицевы градиенты, и выпуклыми штрафными членами в линейных моделях с гауссовой матрицей плана и произвольным распределением шума. Основные вклады включают: (1) предоставление общих формул для производных регуляризованной M-оценки $\hat{\beta}(y,X)$ по $y$ и $X$, раскрывающих простую дифференцируемую структуру, общую для всех выпуклых регуляризованных M-оценок; (2) использование этих производных для характеризации распределения остатков $r_i = y_i-x_i^\top\hat{\beta}$ в среднемерном режиме, когда размерность и объем выборки имеют одинаковый порядок; (3) предложение нового адаптивного критерия, основанного на распределении остатков, для выбора параметра регуляризации M-оценки, который приближает ошибку вне выборки и не требует знания распределения шума или ковариационной матрицы плана.

Исследовательский контекст и мотивация

Постановка проблемы

В высокомерной статистике M-оценки являются важным инструментом для работы с выбросами и шумом с тяжелыми хвостами. Типичная форма M-оценки: $\hat{\beta}(y,X) = \arg\min_{b\in\mathbb{R}^p} \frac{1}{n}\sum_{i=1}^n \rho(y_i - x_i^\top b) + g(b)$

где $\rho$ — выпуклая функция потерь (например, потери Хьюбера), $g$ — выпуклый штрафной член (например, Elastic-Net).

Мотивация исследования

1. Сложность настройки параметров: существующие методы настройки обычно требуют знания распределения шума или матрицы ковариации плана, которые часто недоступны в практических приложениях.
2. Недостаточное теоретическое понимание: теоретическое понимание дифференцируемой структуры и распределения остатков для общих M-оценок остается неполным.
3. Практические требования: необходим полностью адаптивный критерий настройки, который не зависит от неизвестных параметров и эффективно выбирает оптимальную пару потерь-штрафа.

Ограничения существующих методов

• Большинство существующих работ ограничиваются квадратичными потерями
• Требуется знание матрицы ковариации плана $\Sigma$
• Отсутствуют теоретические гарантии для негладких штрафных функций

Основные вклады

1. Единая схема формул производных: предоставление общих формул для производных по $(y,X)$ произвольной выпуклой регуляризованной M-оценки, раскрывающих единую дифференцируемую структуру.
2. Стохастическое представление распределения остатков: получение точного стохастического представления и результатов асимптотической нормальности для отдельных остатков в среднемерном режиме.
3. Адаптивный критерий настройки: предложение полностью адаптивного критерия выбора параметров, не требующего знания распределения шума или ковариационной матрицы плана.
4. Новые связи эффективных степеней свободы: установление новых связей между производными M-оценок и эффективными степенями свободы.

Описание методов

Постановка задачи

Рассмотрим линейную модель $y = X\beta^* + \varepsilon$, где:

• строки $X \in \mathbb{R}^{n \times p}$ независимо и одинаково распределены как $N(0,\Sigma)$
• $\varepsilon$ независим от $X$ и имеет непрерывное распределение
• размерность $p$ и объем выборки $n$ имеют одинаковый порядок

Основная техническая схема

1. Формулы производных (теорема 1)

Для почти всех $(y,X)$ существует матрица $\hat{A} \in \mathbb{R}^{p \times p}$ такая, что:

$\frac{\partial}{\partial y_i}\hat{\beta}(y,X) = \hat{A}X^\top e_i \psi'(r_i)$

$\frac{\partial}{\partial x_{ij}}\hat{\beta}(y,X) = \hat{A}e_j\psi(r_i) - \hat{A}X^\top e_i \psi'(r_i)\hat{\beta}_j$

где $r_i = y_i - x_i^\top\hat{\beta}$, $\psi = \rho'$, $\|\Sigma^{1/2}\hat{A}\Sigma^{1/2}\|_{op} \leq (n\mu)^{-1}$.

2. Распределение остатков (теорема 4)

Для каждого $i = 1,\ldots,n$ существует $Z_i \sim N(0,1)$ независимый от $\varepsilon_i$ такой, что:

$\left|r_i + \text{tr}[\Sigma\hat{A}]\psi(r_i) - (\varepsilon_i + \|\Sigma^{1/2}(\hat{\beta}-\beta^*)\|Z_i)\right| \leq O_P(n^{-1/4})(\text{члены ошибки})$

Это дает стохастическое представление остатков: $r_i + \text{tr}[\Sigma\hat{A}]\psi(r_i) \approx \varepsilon_i + \|\Sigma^{1/2}(\hat{\beta}-\beta^*)\|Z_i$

3. Адаптивный критерий настройки

На основе распределения остатков предлагается критерий настройки:

$\text{Crit}(\rho, g) = \left\|r + \frac{\hat{df}}{\text{tr}[V]}\psi(r)\right\|^2$

где:

• $r = y - X\hat{\beta}_{\rho,g}$
• $\hat{df} = \text{tr}[X(\partial/\partial y)\hat{\beta}_{\rho,g}]$
• $V = \text{diag}\{\psi'(r)\}(I_n - X(\partial/\partial y)\hat{\beta}_{\rho,g})$

Технические инновации

1. Единая дифференцируемая структура: впервые установлены единые формулы производных для общих выпуклых M-оценок, включая негладкие штрафы.
2. Оценка эффективных степеней свободы: предложение $\hat{df}/\text{tr}[V]$ как оценки $\text{tr}[\Sigma\hat{A}]$, избегающей зависимости от $\Sigma$.
3. Инновационное использование вероятностных инструментов: умелое применение формулы Стейна и техник гауссовского интегрирования для работы с высокомерными M-оценками.

Экспериментальная установка

Процесс генерации данных

• Объем выборки: $n = 1001$, размерность: $p = 1000$
• Матрица плана: строки $X$ независимо и одинаково распределены как $N(0,\Sigma)$, где $\Sigma = R^\top R/(2p)$, $R$ — матрица Радемахера
• Истинный параметр: первые 100 компонент $\beta^*$ равны $\sqrt{10}/10$, остальные равны 0
• Шум: $\varepsilon_i$ независимо и одинаково распределены как t-распределение со степенями свободы 2 (тяжелые хвосты)

Установка модели

Использование оценки Хьюбера-Elastic-Net:

• Функция потерь: $\rho(u;\Lambda) = \Lambda^2 H(\Lambda^{-1}u)$, где $H$ — потери Хьюбера
• Штрафной член: $g(b;\lambda,\tau) = \lambda\|b\|_1 + (\tau/2)\|b\|_2^2$

Метрики оценки

• Ошибка вне выборки: $\|\Sigma^{1/2}(\hat{\beta}-\beta^*)\|^2$
• Ошибка приближения критерия настройки
• Тест нормальности остатков

Результаты экспериментов

Основные результаты

1. Эффективность критерия настройки

На рисунке 1 показано на сетке $(\lambda,\tau)$:

• истинная ошибка вне выборки $\|\Sigma^{1/2}(\hat{\beta}-\beta^*)\|^2$
• приближение критерия настройки $\|r + (\hat{df}/\text{tr}[V])\psi(r)\|^2/n - \|\varepsilon\|^2/n$
• ошибка приближения

Результаты показывают, что критерий настройки точно приближает относительную величину ошибки вне выборки.

2. Проверка нормальности остатков

На рисунке 2 показаны гистограмма и диаграмма Q-Q стандартизованных остатков $\zeta_1$, которые хорошо соответствуют стандартному нормальному распределению при различных комбинациях параметров, подтверждая теоретические предсказания.

3. Оценка эффективных степеней свободы

Таблица 1 показывает, что значения $|\text{tr}[\Sigma\hat{A}] - \hat{df}/\text{tr}[V]|$ малы (около 0.002), подтверждая, что $\hat{df}/\text{tr}[V]$ является хорошей оценкой $\text{tr}[\Sigma\hat{A}]$.

Теоретические гарантии

• Теоремы 7-8: доказано, что оценка, выбранная на основе критерия настройки, с высокой вероятностью достигает оптимальной ошибки вне выборки
• Теорема 9: $E[|\text{tr}[\Sigma\hat{A}]\text{tr}[V]/n - \hat{df}/n|] \leq C(γ,μ)n^{-1/2}$
• Теорема 6: $\|\Sigma^{1/2}(\hat{\beta}-\beta^*)\|^2 + \|\varepsilon\|^2/n = (1+O_P(n^{-1/2}))\|r + \text{tr}[\Sigma\hat{A}]\psi(r)\|^2/n$

Связанные работы

Теория высокомерных M-оценок

Данная работа основана на следующих исследованиях:

• Bayati & Montanari (2012): анализ риска LASSO
• El Karoui et al. (2013): исследование M-оценок без штрафа
• Thrampoulidis et al. (2018): точный анализ ошибок для общих пар потерь-штрафа

Методы настройки параметров

Сравнение с существующими методами:

• Критерий ALO (Rad et al., 2020): требует предположения дважды непрерывной дифференцируемости
• Критерии на основе $\Sigma$ (Bellec, 2020): требуют знания ковариационной матрицы плана
• Метод данной работы: полностью адаптивен, применим к негладким функциям

Уникальность технического вклада

Впервые используются наблюдаемые величины (зависящие только от данных) для описания поведения M-оценок, а не зависящие от неизвестного априорного распределения или ковариационной матрицы.

Заключение и обсуждение

Основные выводы

1. Единая теоретическая схема: установлена единая теория дифференцируемости для выпуклых регуляризованных M-оценок.
2. Практический инструмент настройки: предоставлен адаптивный метод выбора параметров, не требующий предварительных знаний.
3. Теоретические гарантии: доказана эффективность метода при разумных предположениях.

Ограничения

1. Предположение о гауссовом плане: основные теоретические результаты требуют гауссовой матрицы плана, хотя моделирование показывает эффективность и для плана Радемахера.
2. Требование сильной выпуклости: некоторые результаты требуют сильной выпуклости штрафного члена, хотя раздел 7 предоставляет методы ослабления.
3. Вычислительная сложность: для некоторых негладких штрафов матрица $\hat{A}$ не имеет замкнутого выражения.

Направления будущих исследований

1. Расширение на негауссовы планы
2. Рассмотрение более общих классов функций потерь
3. Разработка вычислительно эффективных алгоритмов реализации

Глубокая оценка

Преимущества

1. Значительный теоретический вклад: впервые предоставлена единая теория производных для общих M-оценок, заполняющая важный теоретический пробел.
2. Высокая практическая ценность: предложенный критерий настройки полностью адаптивен и имеет важное значение для практических приложений.
3. Сильная техническая инновативность: умелое сочетание выпуклого анализа, теории случайных матриц и метода Стейна.
4. Достаточная экспериментальная верификация: теоретические предсказания проверены в различных установках.

Недостатки

1. Ограничивающие предположения: предположение о гауссовом плане ограничивает универсальность метода.
2. Недостаточное рассмотрение вычислительных аспектов: мало обсуждается численная стабильность и эффективность при практических вычислениях.
3. Ограниченное эмпирическое сравнение: сравнение с другими адаптивными методами ограничено.

Влияние

1. Теоретическое влияние: предоставляет новые инструменты анализа для теории высокомерных M-оценок.
2. Практическая ценность: предоставляет практический метод выбора параметров в робастной регрессии.
3. Методологический вклад: демонстрирует, как объединить высокомерную теорию вероятностей со статистическим выводом.

Области применения

• Задачи высокомерной робастной регрессии
• Анализ данных с выбросами или шумом с тяжелыми хвостами
• Приложения машинного обучения, требующие адаптивного выбора параметров
• Области с высокими требованиями к робастности: финансы, биоинформатика и др.

Библиография

Основные цитируемые работы включают:

• Bayati, M. and Montanari, A. (2012). The lasso risk for gaussian matrices.
• El Karoui, N. et al. (2013). On robust regression with high-dimensional predictors.
• Thrampoulidis, C. et al. (2018). Precise error analysis of regularized m-estimators in high dimensions.
• Bellec, P.C. (2020). Out-of-sample error estimate for robust m-estimators with convex penalty.