ISTA、FISTA
L1正則化問題を解くための解法の一つにISTA、またその高速化バージョンであるFISTAと呼ばれるものがあります。この方法はL1正則化に特化されており、構造正則化問題に適用するにはさらにもう一段手順が必要になります。まずこの記事では、ISTAの考え方を、メジャライザを利用した最適化法という観点から説明したいと思います。
以下のL1正則化問題を考えます。
ここで は損失関数で、今は凸関数であるとします。
この問題の解を求めるにあたり、ISTAでは損失関数 をメジャライザという単純な2次関数に置き換える事を行います。
以下でこのメジャライザの導出を説明します。
メジャライザ
関数 の点
周辺でのテイラー展開を考えます。
式（１）
となります。ここで がβの2次以下で書けるなら右辺と左辺は一致します。
また は、点
における関数
の曲率となります。
この曲率が
を持たす場合式(1)は
式（２）
と書けます。
この右辺
のβに関する2次関数をメジャライザと呼びます。
式(2)から分かるメジャライザの性質として
i ) メジャライザは の 上をおさえる関数（等号から明らか）
ii) 、即ちメジャライザは点
で
に接する
（f と g は交わるが g が f の上にあるのだから接する）
が分かります。
例えばβが1次元で
式（３）
と書けるとすると、メジャライザは
式（４）
となります。ここで なので
です（ f が式（３）のような2次関数の場合、K=2なら f と g は一致します）。
逆に K < 2 なら式（２）の不等号は成立しない、つまり上をおさえる関数にはなりません。
式(3)の f と、β0=-5における K=1(オレンジ)、K=4(緑)の場合のメジャライザ
K=1の場合は f > g となる所が現れる（というか上の場合下をおさえる関数となる）
このようにISTAでは、損失関数の上をおさえる2次関数を求め、その最適化を繰り返すことでを最小にするβを求めます。
例えば式（３）の損失関数について、式（４）の K を 4 としたメジャライザを使用する場合を下の図に示します。
損失関数である式（３）は青線で描かれ、大域的最適解(β = -2)は黄色の丸で書かれています。
今 K = 4 としβ0 = -5 とした場合を考えます。この時のメジャライザはオレンジの放物線で、これはβ = -3.5 で最小になります（青〇）。
今度は f (β = -3.5) をβ0 として（紫の〇）メジャライザを作り直します（緑の放物線）。そしてこれはβ = -2.75 で最小になります（緑〇）…
この操作を繰り返してゆけば、メジャライザ最小の点は黄色の丸にどんどん近づいてゆくでしょう。
メジャライザの平方完成
さて、このメジャライザの最小解ですが、以下の算術計算でその解析解が求められます。
式（４）の2次関数は、平方完成で以下のようにさらに簡単に書き直せます。
（右辺の2乗ノルムを展開すれば左辺に一致することがすぐわかります。）
ところで、上の式を最小にするβを求めたいわけですが、この際、上の右辺第2項、第3項は だけによる項なのでβについての最小化には関わらず、よって定数と見なせます。つまり
となります。