論文の概要: Phase retrieval: Global convergence of gradient descent with optimal sample complexity

• arxiv url: http://arxiv.org/abs/2410.09990v1
• Date: Thu, 17 Oct 2024 03:31:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 03:43:37.211916
• Title: Phase retrieval: Global convergence of gradient descent with optimal sample complexity
• Title（参考訳）: 位相探索: 最適なサンプル複雑性を持つ勾配勾配勾配の大域収束
• Authors: Théodore Fougereux, Cédric Josz, Xiaopeng Li,
• Abstract要約: 本稿では,$m(O)$の測定値から信号ベクトルを復元することを目的とした位相探索問題に対処する。 我々は、m(O)$測定が、高い確率で、目的関数が良質なグローバルな風景を持つことを保証するのに十分であることを証明した。
• 参考スコア（独自算出の注目度）: 3.7873341907492923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses the phase retrieval problem, which aims to recover a signal vector $x$ from $m$ measurements $y_i=|\langle a_i,x^{\natural}\rangle|^2$, $i=1,\ldots,m$. A standard approach is to solve a nonconvex least squares problem using gradient descent with random initialization, which is known to work efficiently given a sufficient number of measurements. However, whether $O(n)$ measurements suffice for gradient descent to recover the ground truth efficiently has remained an open question. Prior work has established that $O(n\,{\rm poly}(\log n))$ measurements are sufficient. In this paper, we resolve this open problem by proving that $m=O(n)$ Gaussian random measurements are sufficient to guarantee, with high probability, that the objective function has a benign global landscape. This sample complexity is optimal because at least $\Omega(n)$ measurements are required for exact recovery. The landscape result allows us to further show that gradient descent with a constant step size converges to the ground truth from almost any initial point.
• Abstract（参考訳）: 本稿では,信号ベクトル$x$を$m$から$y_i=|\langle a_i,x^{\natural}\rangle|^2$,$i=1,\ldots,m$から回収することを目的とした位相探索問題に対処する。 標準的なアプローチは、無作為な初期化を伴う勾配降下を用いた非凸最小二乗問題の解法である。 しかし、基底真理を効率的に回復するために勾配降下を測るのに$O(n)$の値が十分であるかどうかは未解決のままである。 以前の研究により、$O(n\,{\rm poly}(\log n))$測定が十分であることが証明された。 本稿では,このオープンな問題を$m=O(n)$ Gaussian random Measurement が十分であり,高い確率で目的関数が良質なグローバルな景観を持つことを保証して解決する。 このサンプルの複雑さは、正確な回復には少なくとも$\Omega(n)$の測定が必要であるため、最適である。 ランドスケープの結果は、任意の初期点から一定のステップサイズで勾配降下が基底真理に収束することをさらに示せる。

関連論文リスト

• Weighted Low-rank Approximation via Stochastic Gradient Descent on Manifolds [1.9648630752093679]
  多様体上の閉包を許容する勾配降下に対する収束に基づくリトラクション定理を確立する。 このアルゴリズムはユークリッド空間上の既存の勾配勾配よりも優れる。 また、この多様体上の加速線探索とユークリッド空間上の既存の加速線探索を比較する。
  論文  参考訳（メタデータ） (2025-02-20T00:59:50Z)
• Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates [61.091122503406304]
  勾配帯域幅アルゴリズムは, 経験的定値学習率を用いて, ほぼ確実にグローバルな最適ポリシーに収束することを示す。 この結果は、標準の滑らかさと騒音制御の仮定が崩壊するシナリオにおいても、勾配アルゴリズムが適切な探索と利用のバランスを保ち続けていることを証明している。
  論文  参考訳（メタデータ） (2025-02-11T00:12:04Z)
• Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
  重み付き雑音下でのグラディエントDescence(SGD)の収束を確実にする上での勾配正規化とクリッピングの役割について検討する。 我々の研究は、重尾雑音下でのSGDの勾配正規化の利点を示す最初の理論的証拠を提供する。 我々は、勾配正規化とクリッピングを取り入れた加速SGD変種を導入し、さらに重み付き雑音下での収束率を高めた。
  論文  参考訳（メタデータ） (2024-10-21T22:40:42Z)
• On the Convergence of Gradient Descent for Large Learning Rates [55.33626480243135]
  固定ステップサイズを使用すると収束が不可能であることを示す。 正方形損失を持つ線形ニューラルネットワークの場合,これを証明した。 また、勾配に対するリプシッツ連続性のような強い仮定を必要とせず、より一般的な損失に対する収束の不可能性も証明する。
  論文  参考訳（メタデータ） (2024-02-20T16:01:42Z)
• One-step corrected projected stochastic gradient descent for statistical estimation [49.1574468325115]
  これは、Fisherスコアリングアルゴリズムの1ステップで修正されたログ様関数の予測勾配勾配に基づいている。 理論およびシミュレーションにより、平均勾配勾配や適応勾配勾配の通常の勾配勾配の代替として興味深いものであることを示す。
  論文  参考訳（メタデータ） (2023-06-09T13:43:07Z)
• Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data [63.34506218832164]
  本研究では,ReLUを活性化した2層完全連結ニューラルネットワークにおける勾配流と勾配降下の暗黙的バイアスについて検討する。 勾配流には、均一なニューラルネットワークに対する暗黙のバイアスに関する最近の研究を活用し、リーク的に勾配流が2つ以上のランクを持つニューラルネットワークを生成することを示す。 勾配降下は, ランダムな分散が十分小さい場合, 勾配降下の1ステップでネットワークのランクが劇的に低下し, トレーニング中もランクが小さくなることを示す。
  論文  参考訳（メタデータ） (2022-10-13T15:09:54Z)
• Convergence of gradient descent for deep neural networks [7.360807642941713]
  勾配降下は「深層学習革命」の主要な要因の1つである 本稿では、勾配降下の収束の新たな基準を、大域的最小値に提示する。
  論文  参考訳（メタデータ） (2022-03-30T17:01:14Z)
• Improved Overparametrization Bounds for Global Convergence of Stochastic Gradient Descent for Shallow Neural Networks [1.14219428942199]
  本研究では,1つの隠れ層フィードフォワードニューラルネットワークのクラスに対して,勾配降下アルゴリズムのグローバル収束に必要な過パラメトリゼーション境界について検討する。
  論文  参考訳（メタデータ） (2022-01-28T11:30:06Z)
• Convergence of gradient descent for learning linear neural networks [2.209921757303168]
  勾配勾配勾配は損失関数の臨界点,すなわち本論文の平方損失に収束することを示す。 3層以上の層の場合、勾配勾配は、ある固定階数の多様体行列上の大域最小値に収束することを示す。
  論文  参考訳（メタデータ） (2021-08-04T13:10:30Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem [8.164433158925593]
  本研究では,動的降下,永続勾配,ランジュバン景観降下などの解析ベースアルゴリズムについて検討する。 統計的軌道からの統計場理論をアルゴリズムにフルタイムで適用し、開始時と大規模なシステムサイズで適用します。
  論文  参考訳（メタデータ） (2021-03-08T17:06:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。