非最小位置で収束するL1-正規化システムの最小化？

Question

これは私の最初のポストstackoverflowです、これは正しい領域ではない場合は謝罪します。私はL1正規化システムの最小化に取り組んでいます。

私は基本的な線形システムY = X * B、Xはn行p列の行列、Bはモデル係数のp行1列のベクトル、Yは次のようになります。 n行1列の出力ベクトル。

私はモデル係数を見つけようとしていますが、私はL1正規化システムを最小化するために勾配降下アルゴリズムと座標降下アルゴリズムの両方を実装しました。私のステップサイズを見つけるには、私はバックトラッキングアルゴリズムを使用しています。グラジエントのノルム-2を見てアルゴリズムを終了させ、ゼロに近い場合は終了します（現在は0.001を使用しています）。

私が最小限にしようとしている関数は以下の（0.5）*（norm（（Y-X * B）、2）^ 2）+λ* norm（B、1）です。 （注：ノルム（Y、2）はベクトルYのノルム-2の値を意味します）。私のX行列は150 x 5で、スパースではありません。

正則化パラメータλを0に設定すると、最小自乗解に収束するはずです。私のアルゴリズムがこれをかなりうまく迅速に実行することを確認できます。規範-2勾配のは常に正の数であるので、私は私のモデル係数がすべてゼロに向かう傾向ラムダを高めるために起動した場合、これは私が期待するものである

、私のアルゴリズムは、しかし決して終了しません。例えば、1000のラムダは私に10 ^（ - 19）の範囲の係数を与えますが、私の勾配のnorm2は〜1.5です。これは数千回の反復の後です。私の勾配値はすべて0から1の何かに収束します私のステップサイズは非常に小さくなります（10 ^（ - 37）レンジ）。状況を改善しないアルゴリズムを長く実行させると、何とかしてしまったように見えます。

私の勾配アルゴリズムと座標降下アルゴリズムは、同じポイントに収束し、終了条件に同じnorm2（勾配）数を与えます。彼らはまた、ラムダ0で非常にうまく動作します。もし私が非常に小さなラムダ（例えば0.001）を使うと、コンバージェンスが得られます.1、2、1ラムダ、それ以上のラムダ、収束率はそれほど小さくないので無駄です。

問題に関連すると思われる質問がいくつかありましたか？ 10 ^（の時間と/（2H）） - Iは、有限差分法（F（X-H）は、f（x + h）を） - 使用してい勾配の計算において

5）。 hのこの価値に関する考えは？

これらの非常に小さなステップでは、最小にほぼ直交する方向に前後に移動しているため、収束速度が遅くなりすぎて役に立たないという考えもありました。

私の最後の考えは、コンバージェンスレートが極端に遅くなって終了した場合、おそらくコンバージェンスのレートを見て、別のターミネーション方法を使用しているはずです。これは共通の終了方法ですか？

Answer 1

1ノルムは微分できません。これは多くのことに根本的な問題を引き起こします。特に、あなたが選んだターミネーションテストです。勾配はあなたの最小値付近で大幅に変化し、測定値0のセットには存在しません。あなたが本当にしたい

終了テストは、の線に沿ってになります「subgradientで非常に短いベクトルがあります。」

^2 +ラムダ|| X || || _1 AX-B || _2の劣勾配における最短ベクトルを見つけるのはかなり簡単です。、賢く、許容範囲を選択してepsし、次の手順を実行します。

1. 計算をv = grad(||Ax-b||_2^2).

2. x[i] < -eps場合、v[i]からラムダを引きます。 x[i] > epsの場合は、v[i]にラムダを追加します。 -eps <= x[i] <= epsの場合は、v[i]を最小にする[-lambda, lambda]〜v[i]の数値を追加します。

グラジエントとしてvを処理して、ここで終了テストを行うことができます。また、次の繰り返しがどこにあるかを選択するときに、グラデーションにvを使用することをお勧めします。