論文の概要: Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view
- arxiv url: http://arxiv.org/abs/2506.18279v1
- Date: Mon, 23 Jun 2025 04:20:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-24 19:06:36.849017
- Title: Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view
- Title（参考訳）: 最適スペクトル初期化器は位相探索相転移に影響を及ぼす -- RDT ビュー
- Authors: Mihailo Stojnic,
- Abstract要約: 我々はスペクトル初期化器と共振位相探索アルゴリズム(dPR)の理論限界の関係を解析する。
我々は、Emphoverlap optimal spectrum initializers (OptSpins) をdPRの出発点とみなし、それらを統計的に特徴付ける汎用的なEmphRandom duality theory (RDT) ベースのプログラムを開発した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We analyze the relation between spectral initializers and theoretical limits of \emph{descending} phase retrieval algorithms (dPR). In companion paper [104], for any sample complexity ratio, $\alpha$, \emph{parametric manifold}, ${\mathcal {PM}}(\alpha)$, is recognized as a critically important structure that generically determines dPRs abilities to solve phase retrieval (PR). Moreover, overlap between the algorithmic solution and the true signal is positioned as a key ${\mathcal {PM}}$'s component. We here consider the so-called \emph{overlap optimal} spectral initializers (OptSpins) as dPR's starting points and develop a generic \emph{Random duality theory} (RDT) based program to statistically characterize them. In particular, we determine the functional structure of OptSpins and evaluate the starting overlaps that they provide for the dPRs. Since ${\mathcal {PM}}$'s so-called \emph{flat regions} are highly susceptible to \emph{local jitteriness} and as such are key obstacles on dPR's path towards PR's global optimum, a precise characterization of the starting overlap allows to determine if such regions can be successfully circumvented. Through the presented theoretical analysis we observe two key points in that regard: \textbf{\emph{(i)}} dPR's theoretical phase transition (critical $\alpha$ above which they solve PR) might be difficult to practically achieve as the ${\mathcal {PM}}$'s flat regions are large causing the associated OptSpins to fall exactly within them; and \textbf{\emph{(ii)}} Opting for so-called ``\emph{safer compression}'' and slightly increasing $\alpha$ (by say $15\%$) shrinks flat regions and allows OptSpins to fall outside them and dPRs to ultimately solve PR. Numerical simulations are conducted as well and shown to be in an excellent agreement with theoretical predictions.
- Abstract（参考訳）: 本稿では,スペクトル初期化器と位相探索アルゴリズム(dPR)の理論的限界の関係を解析する。
共用紙[104]では、任意のサンプル複雑性比に対して、$\alpha$, \emph{parametric manifold}, ${\mathcal {PM}}(\alpha)$は、位相探索(PR)を解くdPRの能力を一般化的に決定する重要な構造として認識される。
さらに、アルゴリズム解と真の信号との重なりは、キー ${\mathcal {PM}}$'s コンポーネントとして配置される。
ここでは、いわゆる 'emph{overlap optimal} スペクトル初期化器(OptSpins) を dPR の出発点とみなし、それらを統計的に特徴づけるための一般 \emph{Random duality theory} (RDT) ベースのプログラムを開発する。
特に、OptSpinsの機能構造を決定し、それらがdPRに提供する開始重なりについて評価する。
${\mathcal {PM}}$'s いわゆる \emph{flat region} は \emph{local jitteriness} に非常に影響を受けやすいため、dPR の PR の大域的最適への道の鍵となる障害であるため、開始重なりの正確な特徴付けにより、そのような領域を回避できるかどうかを判断できる。
提示された理論解析を通して、その点における2つの重要な点を観察する。
(i)}} dPR の理論的相転移(上述の PR を解くための臨界 $\alpha$ )は、${\mathcal {PM}}$ の平坦な領域が大きければ、関連する OptSpins がちょうどその内部に落ちてしまうこと、そして \textbf{\emph{
(ii)}} いわゆる ‘\emph{safer compression}' のオプトアウトと$\alpha$ ($15\%$) のわずか増加はフラットリージョンを縮小し,OptSpins が外部に落ちて,dPR が最終的にPRを解決することを可能にする。
数値シミュレーションも行われ、理論的な予測とよく一致している。
関連論文リスト
- Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。
逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。
これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。
ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。
Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
論文 参考訳（メタデータ） (2024-10-10T06:33:41Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization [0.552480439325792]
パラメトリックな特徴を持つ不完全な情報を持つ分散最適化問題として$n$のエージェントを考える。
本稿では,各エージェントが未知パラメータの現在の信念を更新する分散近似アルゴリズムを提案する。
アルゴリズムの性能に影響を与える因子を定量的に解析し、決定変数の平均二乗誤差が$mathcalO(frac1nk)+mathcalOleft(frac1sqrtn (1-rho_w)right)frac1k1.5で有界であることを証明する。
論文 参考訳（メタデータ） (2024-04-21T14:18:49Z) - Stochastic Gradient Methods with Compressed Communication for
Decentralized Saddle Point Problems [0.0]
圧縮に基づく勾配アルゴリズムを2つ開発し,非滑らかな凸凸の強い凹凸点問題のクラスを解く。
最初のアルゴリズムは、一般的な設定のための圧縮(C-RDPSG)を用いたRestartベースの分散近似勾配法である。
次に,有限和設定のための圧縮 (C-DPSVRG) を用いた分散近似変数低減勾配アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-28T15:17:19Z) - Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。
線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
論文 参考訳（メタデータ） (2022-04-20T21:15:38Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample
Complexity [25.775517797956237]
本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。
我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2022-02-01T07:27:34Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-23T17:08:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。