L-BFGS法
Orthant-wise limited-memory quasi-Newton (OWL-QN) 法は、l1正則化モデルのフィッティング向けの亜種L-BFGS法であり、l1正則化モデル固有のスパース性を利用する手法である。このアルゴリズムは以下の形式で表わされる関数を最小化する。
f ( x → ) = g ( x → ) + C ‖ x → ‖ 1 {\displaystyle f({\vec {x}})=g({\vec {x}})+C\|{\vec {x}}\|_{1}}
ここで、gは微分可能かつ上に凸な損失関数である。このアルゴリズムは有効制約法の一種であり、各反復において変数の各成分の符号を推定し、次のステップでも同一の符号が保たれるような制約を課す。微分不可能な ‖ x → ‖ 1 {\displaystyle \|{\vec {x}}\|_{1}} 項が符号を固定することにより、L-BFGS 法で扱える滑らかな線形項に置き換わる。L-BFGSステップの実行後、いくつかの変数の符号を変更した上で、反復を続行する。