加速されたランダム化された座標降下

1
u49K3df2 2020-06-22 23:23.

この論文は有名な教授によるものです。数百の引用があります。この論文を理解している人がいるに違いない。誰かが最適化の経験があるなら、これを見てください。

降下アルゴリズムを座標

https://link.springer.com/article/10.1007%2Fs10107-015-0892-3

Stephen J. Wrightによる仮定(14ページ)は次のように与えられます。

仮定1 関数$f$$\text{ min } f(x) $ 凸で均一なリプシッツ連続微分可能であり、最小値に達します $f^{*}$ セットで $S$。有限があります$R_{0}$ fに設定されたレベルがによって定義されるように $x_0$ 有界、つまり、 $$ \max _{x^{*} \in \mathcal{S}} \max _{x}\left\{\left\|x-x^{*}\right\|: f(x) \leq f\left(x^{0}\right)\right\} \leq R_{0} $$

次に、加速されたランダム化された座標降下(19ページ)を扱う部分で、次のように述べられています。

定理2: *仮定1が成り立つと仮定し、次のように定義します。 $$ S_{0}:=\sup _{x^{*} \in \mathcal{S}} L_{\max }\left\|x^{0}-x^{*}\right\|^{2}+\left(f\left(x^{0}\right)-f^{*}\right) / n^{2} $$ その後、すべてのために $k\ge0$ 我々は持っています

\ begin {aligned} E&(f(x ^ k))-f ^ * \ nonumber \\&\ le S_0 \ frac {\ sigma} {L_ \ mathrm {max}} \ left [\ left(1+ \ frac {\ sqrt {\ sigma / L_ \ mathrm {max}}} {2n} \ right)^ {k + 1}-\ left(1- \ frac {\ sqrt {\ sigma / L_ \ mathrm {max}}} {2n} \ right)^ {k + 1} \ right] ^ {-2} \\&\ le S_0 \ left(\ frac {n} {k + 1} \ right)^ 2。\ end {aligned}

どこ $\sigma$ は強い凸面の係数であり、 $L_{\text{max}}$ 座標リプシッツ定数です。

それから彼は次のように結論します: 用語 $$ \left(1+\frac{\sqrt{\sigma / L_{\max }}}{2 n}\right)^{k+1} $$ 最終的に第2期を支配する $$ \left(1-\frac{\sqrt{\sigma / L_{\max }}}{2 n}\right)^{k+1} $$ そのため、この式で提案される線形収束速度は、対応する速度よりも大幅に速くなります。 $$ E\left[f\left(x^{k}\right)\right]-f^{*} \leq\left(1-\frac{\sigma}{n L_{\max }}\right)^{k}\left(f\left(x^{0}\right)-f^{*}\right) \quad \forall k \geq 1 $$ アルゴリズム3(加速なしのランダム化された座標降下)の場合。

最後に私の問題:私は彼の論理に従うことができず、なぜこの式が他の式よりも大幅に速いのかわかりません。

ヒントをいただければ幸いです。

1 answers

1
Trung Vu 2020-07-05 16:46.

収束率が速い理由を確認するには、次の2つの量を比較します。 $1-\frac{\sigma}{n L_{\max}}$ そして $\Bigl[ \bigl(1+\frac{\sqrt{\sigma/L_{\max}}}{2n}\bigr)^{k+1} - \bigl(1-\frac{\sqrt{\sigma/L_{\max}}}{2n}\bigr)^{k+1}\Bigr]^{-2}$。いつ$k$ 大きくなると、後者は次のように表すことができます

$$ \frac{1}{\biggl( \bigl(1+\frac{\sqrt{\sigma/L_{\max}}}{2n}\bigr)^{k+1} - \bigl(1-\frac{\sqrt{\sigma/L_{\max}}}{2n}\bigr)^{k+1} \biggr)^2} \approx \frac{1}{\biggl( \bigl(1+\frac{\sqrt{\sigma/L_{\max}}}{2n}\bigr)^{k+1} \biggr)^2} = \Biggl( \frac{1}{\bigl(1+\frac{\sqrt{\sigma/L_{\max}}}{2n}\bigr)^2} \Biggr)^{k+1}. $$

現在、1次のテイラー展開を使用しています。 $\frac{1}{(1+x)^2} \approx 1-2x$。したがって、レートはさらに概算できます。

$$ \frac{1}{\bigl(1+\frac{\sqrt{\sigma/L_{\max}}}{2n}\bigr)^2} \approx 1 - \frac{\sqrt{\sigma/L_{\max}}}{n} < 1 - \frac{\sigma/L_{max}}{n}. $$

係数による改善 $\sqrt{L_{\max}/\sigma}$ 反復回数は、次の式で確認できます。

$$ (1-\rho)^k < \epsilon \Rightarrow k > \frac{\log (1/\epsilon)}{\log(1/(1-\rho))} \approx \frac{1}{\rho} \log (1/\epsilon) , $$

代用する場所 $\rho = \frac{\sigma/L_{max}}{n}$ そして $\rho = \frac{\sqrt{\sigma/L_{\max}}}{n}$ それぞれ。

Related questions

MORE COOL STUFF

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ウィリアム王子が 8 歳のときに寄宿学校に通わせたことについて、ダイアナ妃がどのように感じたかを学びましょう。

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

Shaquille O'Neal は最近、Big Chicken レストラン帝国を拡大するため、ダラス郊外に住居を購入しました。

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90日の婚約者」シーズン9のスター、イヴ・アレラーノが逮捕され、モハメド・アブデルハメドへの暴行容疑で家庭内暴力の罪に問われている.

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマン自身、ポール・ルーベンスと親密です。彼らの友情について彼女が言ったことを発見してください。

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

米国政府は自動運転車に関する国家政策を必要としています

米国政府は自動運転車に関する国家政策を必要としています

ほんの一握りのアメリカの都市だけが自動運転車の準備を真剣に行っているのと同じように、連邦政府も先を考えていないようです。運輸長官のアンソニー・フォックスは昨日、彼の部門には自動運転車に関する国内規制の計画がないことを明らかにしました。

ゲイの男性が献血できるようになりました

ゲイの男性が献血できるようになりました

米国食品医薬品局はついに献血の禁止を解除しましたが、多くのゲイ男性はまだ献血できません。新しい規則の下では、男性は、最後に別の男性とセックスしたときから1年以上経過している場合にのみ、血液を与えることを許可されます。

ダートトラックマネージャーは、ダムメジャーリーグの野球のリクエストに応えてエピックバーンを提供します

ダートトラックマネージャーは、ダムメジャーリーグの野球のリクエストに応えてエピックバーンを提供します

メジャーリーグベースボールは、彼らのファンベースが読むことも綴ることもできないと想定することを決定し、エルドラスピード​​ウェイの「マッドサマークラシック」という名前の使用に問題を抱えました。MLBは、イベントが彼らの「真夏のクラシック」に近すぎるように聞こえたと主張し、Eldoraはそれを変更することに同意しましたが、最初にMLBを掘り下げることなくではありませんでした。

グーグルデータは、銃規制について話す準備ができていると言っていますが、おそらく話しません

グーグルデータは、銃規制について話す準備ができていると言っていますが、おそらく話しません

ウォールストリートジャーナルは、サンバーナーディーノでの銃撃の前後から銃に関連する検索習慣が急速に変化したことを示す、希望に満ちたデータセットをGoogleから取得しました。「ガンショップ」検索(赤)に関連する「ガンコントロール」検索(上の画像の青)の急増が見られました。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

水門の修理

水門の修理

天王星と海王星の間の領域に向かって宇宙を 3/4 g の低温で航行しながら、私たちは数週間燃え続けていました。Dawson Trawler の科学者が Yggdrasil ポータルと呼んだもの。

美しいもの

美しいもの

女性として、私は通常、関係を築くことをためらっています。私はいつも彼らに負けないように苦労しました。私は誰かと共有したいという衝動と戦わなければなりません。

逃走中の女性からの発信

最も家が必要なときに家のように感じる場所はありません。

逃走中の女性からの発信

私は誰よりも移動しました。父が住んでいた土地には、父が 1 歳馬を折るミニチュアの競馬場がありました。

死にゆく男から学んだ最大の人生の教訓

彼は、私たちが持っているのはこの現在の瞬間だけであることを知るのが遅すぎました。

死にゆく男から学んだ最大の人生の教訓

ブラッドは、カーキ色のショート パンツとポロ シャツを着たまま、白いゴルフ グローブを両手で高く引っ張ったまま、ベッドルームに入ってきました。彼は満面の笑みを浮かべながら、「今年は私の人生で最高の年だったと思います!」と言いました。通常は保守的な消費者である私たちは、通常とは異なることをしました。

Language