概要
劣モジュラ関数最小化問題について：
(1) $O(n M^3 \log n EO)$ の偽多項式時間アルゴリズムを提案．ただし，目的関数は整数値で，最大値はMとする．
(2) $O(n^{5/3} EO/\epsilon) $ の $\epsilon$-近似アルゴリズムを提案．
アルゴリズムを一言でいえば，最小化したい関数のLovasz拡張を（確率的）劣勾配降下法で最小化する．
しかし，Lovasz拡張の劣勾配の更新が高速であるため，1ステップが速く回せる．
(1) の場合は，Lovasz拡張の劣勾配の成分の非ゼロ要素が O(M) であることに着目し，スパースベクトルの加算時に勾配を速く更新できるアルゴリズムを考える．
(2) の場合は，スパースな確率的劣勾配で分散が十分小さいものを高速に構成する．
文献情報
- Author: D. Chakrabarty, Y. Lee, A Sidford, and S. Wong
- Conference: STOC
- Year: 2017
- arxiv
コメント
- 離散最適化を確率的凸最適化で殴った論文．近似アルゴリズムの方は構成が真に確率的なところが面白い．
概要
対称劣モジュラ関数最小化の $O(|V|^3)$ アルゴリズムを与えた論文．ただし，対称劣モジュラ関数というのは，劣モジュラ関数 $f: 2^V \to \mathbb{R}$ であって，$f(X) = f(V - X)$ が成り立つものである．
文献情報
- Author: M. Queyranne
- Conference: SODA
- Year: 1995
- URL
コメント
-
対称劣モジュラ関数のわかりやすい例は，無向グラフのカット関数である．また，fが劣モジュラ関数のとき，$g(X) = f(X) + f(V - X)$ によって対称劣モジュラ関数 $g$ を作れる．
-
「対称劣モジュラ関数最小化」とは，正確には，$|V| \geq 2$ として，空集合と全体集合を除いた $V$ の真部分集合の中で $f$ を最小化するものを求める問題である．例えば，非負重みをもつ無向グラフのカット関数の最小値は明らかに $f(\emptyset) = f(V) = 0$ であるが，そうではなくて非自明な部分の最小値を求める．
-
アルゴリズムの概要は次の通りである： まず，任意の対称劣モジュラ関数に対して，pendent pairと呼ばれる頂点のペア $(s,t)$ が存在することが知られている．ここでpendent pairというのは，$s$ を固定したとき，s-tカットの最小値が1点集合 ${ t }$ によって達成されるもののことである．このようなペアは $O(n^2)$ 回の関数呼び出しで発見することができる．Queyranneのアルゴリズムは，pendent pair発見アルゴリズムを再帰的に $n-1$ 回呼び出すことで得られる．定義から，pendent pair $(s, t)$ があるとき，最小化問題の解 $X$ は $f(X) = f(t)$ であるか，$s, t \in X$ であるかのどちらかである．前者であれば終了だが，それは判定できないので，ひとまず $t$ と $f(t)$ の値を記憶しておく．後者であると仮定すると，$(s, t)$ をまとめて1頂点だと思うことで，サイズが $n-1$ の問題に帰着される．よって，「pendent pairを見つけて結合する」という操作を残り2頂点になるまで繰り返せば，記憶した $t$ のうちどれかがminimizerになっている．
-
もともと，Nagamochi and Ibaraki (1992)の最小s-tカットアルゴリズムというものがあり，その拡張として提案されたらしい．Fujishige (2005) のsection 13にも歴史が載っている．
概要
劣モジュラ関数最小化問題で，実用上最速と噂されていたFujishige--Wolfeのアルゴリズム（最小ノルム点アルゴリズム）に擬多項式時間の保証を与えた論文．Fujishige--Wolfeは，基多面体 (base polyhedron) の上で2-ノルムの2乗が最小になる点を探すアルゴリズムである．
文献情報
- Author: D. Chakrabarty, P. Jain and P. Kothari
- Conference: NIPS
- Year: 2014
- URL
コメント
-
Chakrabarty, et al. (2014) はまず，任意の多面体に対して，Wolfeの最小ノルム点アルゴリズムの連続最適化としての収束保証を与えた．次に，最小ノルム点の連続最適化としての近似精度が $\epsilon$ ならば，そこから構成できる解の（離散最適化としての）近似精度は $2n\epsilon$ である．よって，目的関数 $f$ の値のジャンプの最小幅 $F$ よりも $2n\epsilon$ を小さくとれば最適解となる．
-
全体での計算量は $O((n^5 \gamma + n^7)F)$ になる．ただし，$\gamma$ は関数値オラクル呼び出しのコストである．ジャンプの幅 $F$ に依存しているため「擬」多項式時間である．ただし，$f$ が整数値であることが予めわかっていれば，ジャンプ幅は1で下から抑えればよい．
-
この分野の論文としては珍しく（？）計算機実験がある．強多項式時間アルゴリズムとしては2014年当時の理論最速だったIwata and Orlin (2009) のアルゴリズムと比較し，Fujishige--Wolfeの方が実計算時間が速い傾向にあることを示した．
-
2017年現在，理論的に速いアルゴリズムは [Lee+2015] や [Chakrabarty+2017] とのことらしい．後者の筆頭著者はこの論文と同じ人．
参考文献
- [Lee+2015] Lee, Sidford and Wong. Faster cutting plane method and its implications for combinatorial and convex optimization. In FOCS, 2015.
- [Chakrabarty+2017] Chakrabarty, Lee, Sidford and Wong. Subquadratic submodular function minimization. In STOC, 2017.
概要
Lassoのハイパーパラメータをチューニングする手法である $AV_\infty$ を提案．真の回帰係数に対してsupノルムの意味での理論保証があり，計算機実験ではcross-validationより高速かつ高性能である．
文献情報
- Author: M. Chichignoud, J. Lederer and M. Wainwright
- Journal: Journal of Machine Learning Research
- Year: 2016
- URL
概要
高次元統計では，観測の次元 $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$ がハイパーパラメータに依存してしまっている．これでは解釈上問題があると考えている研究者もいて，集中不等式の使い方を改善してこの部分の依存性をなくす証明方法もある．
概要
高次元線形回帰モデル ($n < p$) において，ノイズが分散既知の正規分布に従うとする．真の回帰係数が $\ell_q$-ボール ($0 \leq q \leq 1$) に含まれるとき，計画行列に対する適当な条件のもとで $\ell_p$-誤差および $\ell_2$-予測誤差のミニマックスレートを導出した．特に，$\ell_2$-予測誤差の最適レートは $\Omega(\frac{\log p}{n})^{1 - q/2}$ である．
文献情報
- Author: G. Raskutti, M. Wainwright and B. Yu
- Journal: IEEE Transactions on Information Theory
- Year: 2011
- URL
コメント
-
高次元統計では，真の回帰係数にスパース性が仮定されることが多い．スパース性の仮定のもとで得られた理論は，仮定が正しい範囲では良いものの，「スパースに近いが非ゼロ」というような誤特定の状況については正確な示唆を与えてくれないと考えられる．ベクトルのスパース性とは，言い換えれば $\ell_0$-ノルム制約のことである．この論文で考察されている $\ell_q$-球というのは，平たい $\ell_0$ 球よりも少しだけ膨らんだような形状をしている．よって，$\ell_q$-球でのミニマックスを考えることで，誤特定した状況でのワーストな挙動についての示唆が得られる．
-
計画行列に関する条件： (1) 列正規化条件 (2) kernel diameter (3) 制限曲率条件． kernel diameterというのは $\ell_q$-ボールと計画行列の零空間の共通部分の $\ell_p$ 直径．線形回帰モデルでは，零空間に入っているベクトルはそもそも見分けがつかないので，この直径の分はもともと諦めておく必要がある．$\ell_2$-の場合は特殊で，条件 (3) から直径をバウンドすることができる (Lemma 1)．(3) の条件とRE条件などとの比較は3.3.1節にある．
-
証明はcovering numberを抑えてFano不等式
概要
Lassoのサポートリカバリー性能の最適性について調べた論文．サポートリカバリーというのは，おおよそ回帰係数の非ゼロ成分の添字（と符号）を当てるという意味である．
この論文ではまず，次の3つの意味でlassoのサポートリカバリーの性能を評価する：
1. スパースな回帰係数 $\beta$ がランダムに出るモデル (generic S-sparse model) を考える．このとき，lassoは $X \beta$ の$\ell_2$ ノルムの意味でのよい近似を高確率で与える．(Theorem 1.2)
1. $\beta$ の非ゼロ要素の絶対値の下限がある制約を満たすとき，lassoは高確率で $\beta$ の非ゼロ成分の添字と符号を当てる．(= exact model recovery, Theorem 1.3)
1. Lassoは，スパースなモデルの中で，真の $X \beta$ を $\ell_2$ の意味で最もよく近似するものに対して，ある精度で自動的に追従する．(= model selection oracle inequality, Theorem 1.4)
次に，「lassoにとって難しい具体的な問題」として，三角級数展開の形で定数信号を近似する問題を考える．これによって，上記の3つの定理が本質的には改善不可能であるということを主張している．
文献情報
- Author: E. Candès and Y. Plan
- Journal: The Annals of Statistics
- Year: 2009
- URL
コメント
-
ノイズは分散既知のガウシアンとする．計画行列にはcoherence propertyという，列どうしの内積の上界の仮定をおく．
-
ある問題設定においてLassoが最適であるということを主張しているわけではなく，lassoにとって最適な性能保証はどういう形を調べる目的で反例を作っていると思われる．
概要
i.i.d.ガウス雑音が乗った信号を等間隔に観測して，平均二乗誤差の意味で雑音除去を行う問題を考える．真の信号 $f$ はSobolev空間（またはより一般にBesov空間）の球に含まれているが，微分可能性のパラメータ $m$ および球の半径 $C$ はわからないものとする．このような状況で，仮に滑らかさのパラメータを知っていた場合のミニマックス最適に近くなるような推定量を構成したい．
この論文では，SureShrinkという手法を提案している．SUREとはStein's Unbiased Risk Estimateの略であり，SUREに基づいて縮小 (shrinkage) のパラメータを決めるのでこのような名前である．
文献情報
- Author: D. Donoho and I. Johnstone
- Journal: Journal of The American Statistical Association
- Year: 1995
- URL
コメント
-
L^2-Sobolev球で滑らかさパラメータ（mとC）を知っている場合は，Pinsker推定量という線形推定量でミニマックスが達成される．Pinsker推定量はmとCに依存した構成になっているが，これらを知らなくても，知っていた場合のミニマックスリスクに自動追従したい（＝適応的ミニマックス）．Efromovich and Pinsker (1984) やNussbaum and Golubev (1990) の推定量などは適応的ミニマックスであることが知られている．
-
L^p-Sobolev球 (p < 2)の場合，そもそもmとCを知っている状況でも，線形推定量ではミニマックスが達成できないことが知られている．そこで，より広い意味の滑らかさを含みうる状況（Besov球）で適応的ミニマックスな推定量はどうやって作ればよいか，というのが本論文の理論的な背景である．