論文の概要: Phase transition of \emph{descending} phase retrieval algorithms

• arxiv url: http://arxiv.org/abs/2506.18275v1
• Date: Mon, 23 Jun 2025 04:10:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-24 19:06:36.846524
• Title: Phase transition of \emph{descending} phase retrieval algorithms
• Title（参考訳）: emph{descending}相検索アルゴリズムの相転移
• Authors: Mihailo Stojnic,
• Abstract要約: 本研究では,位相探索アルゴリズムの理論的限界について検討する。 我々は、エンファラメトリー多様体の概念とそのエンファネリング点を重要な数学的対象として識別する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study theoretical limits of \emph{descending} phase retrieval algorithms. Utilizing \emph{Random duality theory} (RDT) we develop a generic program that allows statistical characterization of various algorithmic performance metrics. Through these we identify the concepts of \emph{parametric manifold} and its \emph{funneling points} as key mathematical objects that govern the underlying algorithms' behavior. An isomorphism between single funneling point manifolds and global convergence of descending algorithms is established. The structure and shape of the parametric manifold as well as its dependence on the sample complexity are studied through both plain and lifted RDT. Emergence of a phase transition is observed. Namely, as sample complexity increases, parametric manifold transitions from a multi to a single funneling point structure. This in return corresponds to a transition from the scenarios where descending algorithms generically fail to the scenarios where they succeed in solving phase retrieval. We also develop and implement a practical algorithmic variant that in a hybrid alternating fashion combines a barrier and a plain gradient descent. Even though the theoretical results are obtained for infinite dimensional scenarios (and consequently non-jittery parametric manifolds), we observe a strong agrement between theoretical and simulated phase transitions predictions for fairly small dimensions on the order of a few hundreds.
• Abstract（参考訳）: 位相探索アルゴリズムの理論的限界について検討する。 アルゴリズムの性能指標を統計的に評価できる汎用プログラムを, RDT(emph{Random duality theory)を用いて開発する。 これらを通して、基礎となるアルゴリズムの振舞いを管理する重要な数学的対象として、 \emph{parametric manifold} の概念とその \emph{funneling points} を識別する。 単関手点多様体と下降アルゴリズムの大域収束の間の同型性を確立する。 パラメトリック多様体の構造と形状および試料の複雑さへの依存性について, 平面および昇降RDTの両方を用いて検討した。 相転移の発生が観察される。 すなわち、サンプルの複雑性が増加するにつれて、パラメトリック多様体は多元体から単一のファンネル点構造へ遷移する。 これは、下降アルゴリズムが一般的に失敗するシナリオから、フェーズ検索を成功させるシナリオへの遷移に対応する。 我々はまた,バリアと平面勾配勾配を交互に組み合わせた,実用的なアルゴリズム的変種を開発し,実装する。 理論結果は無限次元のシナリオ(したがって非ジッタリーパラメトリック多様体)に対して得られるが、理論とシミュレートされた位相遷移の予測の間には数百の順序でかなり小さな次元の強い蓄積が観察される。

関連論文リスト

• Phase retrieval with rank $d$ measurements -- \emph{descending} algorithms phase transitions [0.0]
  118] は強力な EmphRandom duality theory (RDT) に基づく解析プログラムを開発した。 本手法は, 正定位相探索 (PR) のランクを$d$ で処理できることを示す。
  論文  参考訳（メタデータ） (2025-06-23T04:28:46Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms [19.99781875916751]
  textttZo-RASAは$epsilon$-approximation 1次定常解を生成するのに最適なサンプル複雑性を実現する。 指数写像や並列輸送の代わりに幾何とベクトル輸送を用いることで,アルゴリズムの実用性を向上させる。
  論文  参考訳（メタデータ） (2023-09-25T20:13:36Z)
• Multi-Frequency Joint Community Detection and Phase Synchronization [22.683901672480353]
  本稿では, 相対位相をもつテクスト確率ブロックモデルにおける共同コミュニティ検出と位相同期問題について検討する。 本稿では,その最大推定値(MLE)の定式化を精査し,テキストマルチ周波数構造を示す。 MLEの定式化を利用して、複数の周波数にまたがる情報から得られる2つの単純かつ効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-16T23:08:27Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。 ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。 ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
  論文  参考訳（メタデータ） (2022-06-14T12:30:11Z)
• Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic [4.94128206910124]
  本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。 このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。 また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
  論文  参考訳（メタデータ） (2022-06-12T13:14:14Z)
• Orbital MCMC [82.54438698903775]
  任意の微分同相写像から周期軌道を構築するための2つの実用的なアルゴリズムを提案する。 また,両カーネルの実用的メリットを実証した実証的研究を行った。
  論文  参考訳（メタデータ） (2020-10-15T22:25:52Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。 本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
  論文  参考訳（メタデータ） (2020-06-16T19:57:48Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  ランダム量子回路は古典的にシミュレートするのは難しいと見なされる。 典型例の近似シミュレーションは, 正確なシミュレーションとほぼ同程度に困難であることを示す。 また、十分に浅いランダム回路はより一般的に効率的にシミュレーション可能であると推測する。
  論文  参考訳（メタデータ） (2019-12-31T19:00:00Z)

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

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