論文の概要: SDP Achieves Exact Minimax Optimality in Phase Synchronization
- arxiv url: http://arxiv.org/abs/2101.02347v1
- Date: Thu, 7 Jan 2021 03:14:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-10 13:29:30.091370
- Title: SDP Achieves Exact Minimax Optimality in Phase Synchronization
- Title（参考訳）: SDPは位相同期における極小最適性を実現する
- Authors: Chao Gao and Anderson Y. Zhang
- Abstract要約: 我々は、ノイズ測定$Y=z*z*+sigma WinmathbbCntimes ntimes nで位相同期問題を研究する。
SDPが誤差境界$ (1+o)fracnp22np$を2乗の$ell$損失で達成することを証明する。
- 参考スコア（独自算出の注目度）: 19.909352968029584
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the phase synchronization problem with noisy measurements
$Y=z^*z^{*H}+\sigma W\in\mathbb{C}^{n\times n}$, where $z^*$ is an
$n$-dimensional complex unit-modulus vector and $W$ is a complex-valued
Gaussian random matrix. It is assumed that each entry $Y_{jk}$ is observed with
probability $p$. We prove that an SDP relaxation of the MLE achieves the error
bound $(1+o(1))\frac{\sigma^2}{2np}$ under a normalized squared $\ell_2$ loss.
This result matches the minimax lower bound of the problem, and even the
leading constant is sharp. The analysis of the SDP is based on an equivalent
non-convex programming whose solution can be characterized as a fixed point of
the generalized power iteration lifted to a higher dimensional space. This
viewpoint unifies the proofs of the statistical optimality of three different
methods: MLE, SDP, and generalized power method. The technique is also applied
to the analysis of the SDP for $\mathbb{Z}_2$ synchronization, and we achieve
the minimax optimal error $\exp\left(-(1-o(1))\frac{np}{2\sigma^2}\right)$ with
a sharp constant in the exponent.
- Abstract（参考訳）: ノイズ測定による位相同期問題を$Y=z^*z^{*H}+\sigma W\in\mathbb{C}^{n\times n}$, ここで、$z^*$は$n$次元複素単位モジュラーベクトルであり、$W$は複素数値ガウス確率行列である。
各エントリ$Y_{jk}$は確率$p$で観測されると仮定される。
MLE の SDP 緩和が 1+o(1))\frac{\sigma^2}{2np}$ の誤差を正規化された正方形 $\ell_2$ の損失の下で達成することを証明する。
この結果は問題のミニマックス下限に一致し、リード定数さえシャープである。
SDPの解析は、高次元空間に持ち上げられた一般化された電力反復の固定点として特徴づけられるような等価な非凸プログラミングに基づいている。
この観点は、3つの異なる手法(MLE、SDP、一般化パワー法)の統計的最適性の証明を統一する。
この手法は、$\mathbb{Z}_2$同期のSDPの解析にも適用され、指数に鋭い定数を持つミニマックス最適誤差 $\exp\left(-(1-o(1))\frac{np}{2\sigma^2}\right)$ を達成する。
関連論文リスト
- Robust Scatter Matrix Estimation for Elliptical Distributions in Polynomial Time [2.311583680973075]
我々はフロベニウスノルムで次元非依存誤差を実現する時間アルゴリズムを設計する。
散乱行列 $Sigma$, for every $t in mathbbN$, we design an estimator that, given $n = dO(t)$ sample, in time $nO(t)$ finds $hatSigma。
論文 参考訳（メタデータ） (2025-02-10T15:31:57Z) - 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) - Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
MDP を弱通信するためには、$widetildeO(SAfracHvarepsilon2 )$, $H$ は最適ポリシーのバイアス関数のスパンであり、$SA$ は状態作用空間の濃度である。
論文 参考訳（メタデータ） (2024-03-18T04:52:11Z) - Span-Based Optimal Sample Complexity for Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
論文 参考訳（メタデータ） (2023-11-22T15:34:44Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳（メタデータ） (2023-03-30T02:50:49Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。