A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
Written by Kentaro Minami in Statistics on 金, 24 3 2017. Tags: [Statistical Science], lasso, 高次元, スパース推定,
概要
高次元統計では，観測の次元 $n$ に対してパラメータの次元 $p$ が大きいモデルを扱う．このような状況では，真の分布（真のパラメータ）の構造に関する仮定が何もなければ，適当な意味で一致性や収束性をもった推定を行うことができない．よって，高次元統計では真のパラメータに何らかの「低次元構造」を仮定する．代表的な低次元構造はスパース性，グループスパース性，行列の低ランク性などである．
現在までの高次元統計で最も発展してきた推定手法といえば，$\ell_1$-正則化（i.e. Lasso [Tibshirani 1996]）をはじめとした，スパース性罰則つきのM-推定である．例えば，スパースベクトルの推定にはLasso [Tibshirani 1996]，グループ構造をもったスパースベクトルの推定にはGroup lasso [Yuan and Lin 2006]，低ランク行列の推定には核ノルム正則化などといった正則化手法が用いられる．高次元統計の理論では，こういったM-推定量に対して，予測誤差やリスクの収束レートやそのための条件が研究されてきた．Lassoを例にとるならば，真のベクトルが $s$-スパース（非ゼロ要素数が $s$）であって，計画行列に適当な条件があるならば，パラメータ推定のレートはおよそ $s \log p / n$ になるといった様子である．
この論文では，高次元M-推定の設定を抽象化し，収束レートとそのための条件を非常に一般的な形で与えた．とくに，(1) 正則化項が分解可能ノルム (decomposable norm) であって，(2) 損失関数が制限強凸性 (restricted strong convexity) という性質をもつときに，subspace compatibility constantと呼ばれる量で推定誤差や損失のバウンドを与えることができる．これによって，高次元のさまざまな設定での収束レートを導出することができる．Lassoについては，スパースベクトルの復元についての既知の収束レートを復元したり，弱スパース性（ $\ell_q$-セミノルム（$q \in [0, 1]$) の制約）のもとでの収束レートを導出することができる．
文献情報
- Author: S. Negahban, P. Ravikumar, M. Wainwright and B. Yu
- Journal: Statistical Science
- Year: 2012
- URL
コメント
-
スパース線形回帰の研究では，計画行列 $X$ についての制限固有値条件 (restricted eigenvalue condition) やcompatibility conditionといった条件がよく用いられているが，それらを損失関数の条件として隠蔽して書いたものが制限強凸性といえる．制限強凸性は，今ではよく知られた条件と思われる．
-
Decomposabilityとはおおよそ次のような条件である：ノルム $R(\theta)$ が線形部分空間 $M$ についてdecomposableとは，$\theta \in M$ かつ $\gamma \in M^\perp$ のときに，$R(\theta + \gamma) = R(\theta) + R(\gamma)$ となる．例えば $\ell_1$-ノルムなら，座標の添字の分割について分解可能である．
-
Decomposabilityは，「制限強凸性が成り立つ方向に解を誘導する」という働きをもっている (Lemma 1)
-
ハイパーパラメータの理論値は，既知のノイズ分散に依存している．他の論文でもこのような形の保証は多いが，実用上パラメータチューニングをどうするかは別途考える必要がある．また，リスクバウンドの「確率 $1 - \delta$ で成り立つ」の部分の $\delta$ がハイパーパラメータに依存してしまっている．これでは解釈上問題があると考えている研究者もいて，集中不等式の使い方を改善してこの部分の依存性をなくす証明方法もある．