論文の概要: Error Bound of Empirical $\ell_2$ Risk Minimization for Noisy Standard
and Generalized Phase Retrieval Problems
- arxiv url: http://arxiv.org/abs/2205.13827v1
- Date: Fri, 27 May 2022 08:38:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-30 13:36:18.011570
- Title: Error Bound of Empirical $\ell_2$ Risk Minimization for Noisy Standard
and Generalized Phase Retrieval Problems
- Title（参考訳）: 雑音標準と一般化位相検索問題に対する経験的$\ell_2$リスク最小化の誤差境界
- Authors: Junren Chen, Michael K. Ng
- Abstract要約: 雑音位相探索(NGPR)問題とは、雑音2次サンプルによるmathbbCd$の$x_0を推定する問題である。
異なる種類のノイズパターンの下では、再構成を近似できる誤差境界を確立する。
境界は、一般雑音に対して$Obig(frac|etasqrtnbig)$と$Obig(sqrtfracdnbig)$であることを示す。
- 参考スコア（独自算出の注目度）: 18.81683506516341
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A noisy generalized phase retrieval (NGPR) problem refers to a problem of
estimating $x_0 \in \mathbb{C}^d$ by noisy quadratic samples
$\big\{x_0^*A_kx_0+\eta_k\big\}_{k=1}^n$ where $A_k$ is a Hermitian matrix and
$\eta_k$ is a noise scalar. When $A_k=\alpha_k\alpha_k^*$ for some
$\alpha_k\in\mathbb{C}^d$, it reduces to a standard noisy phase retrieval (NPR)
problem. The main aim of this paper is to study the estimation performance of
empirical $\ell_2$ risk minimization in both problems when $A_k$ in NGPR, or
$\alpha_k$ in NPR, is drawn from sub-Gaussian distribution. Under different
kinds of noise patterns, we establish error bounds that can imply approximate
reconstruction and these results are new in the literature. In NGPR, we show
the bounds are of $O\big(\frac{||\eta||}{\sqrt{n}}\big)$ and
$O\big(||\eta||_\infty \sqrt{\frac{d}{n}}\big)$ for general noise, and of
$O\big(\sqrt{\frac{d\log n}{n}}\big)$ and $O\big(\sqrt{\frac{d(\log
n)^2}{n}}\big)$ for random noise with sub-Gaussian and sub-exponential tail
respectively, where $\| \eta \|$ and $\| \eta \|_{\infty}$ are the 2-norm and
sup-norm of the noise vector of $\eta_k$. Under heavy-tailed noise, by
truncating response outliers we propose a robust estimator that possesses an
error bound with slower convergence rate. On the other hand, we obtain in NPR
the bound is of $O\big(\sqrt{\frac{d\log n}{n}}\big)$ and
$O\big(\sqrt{\frac{d(\log n)^2}{n}}\big)$) for sub-Gaussian and sub-exponential
noise respectively, which is essentially tighter than the existing bound
$O\big(\frac{||\eta||_2}{\sqrt{n}}\big)$. Although NGPR involving measurement
matrix $A_k$ is more computationally demanding than NPR involving measurement
vector $\alpha_k$, our results reveal that NGPR exhibits stronger robustness
than NPR under biased and deterministic noise. Experimental results are
presented to confirm and demonstrate our theoretical findings.
- Abstract（参考訳）: 雑音一般化位相探索(NGPR)問題(英: noisy generalized phase search)とは、雑音2次検体$\big\{x_0^*A_kx_0+\eta_k\big\}_{k=1}^n$により$x_0 \in \mathbb{C}^d$を推定する問題である。
A_k=\alpha_k\alpha_k^*$ for some $\alpha_k\in\mathbb{C}^d$ とすると、標準的なノイズ位相検索(NPR)問題に還元される。
本研究の目的は,NGPRで$A_k$,NPRで$\alpha_k$,あるいはサブガウス分布から$A_k$,または$\alpha_k$の両問題におけるリスク最小化を推定することである。
様々なノイズパターンにおいて, 再構成を近似できる誤差境界を定式化し, これらの結果は文献で新しいものである。
ngprにおいて、境界は、一般ノイズに対して、$o\big(\frac{||\eta|}{\sqrt{n}}\big)$と$o\big(||\eta|_\infty \sqrt{\frac{d}{n}}\big)$と$o\big(\sqrt{\frac{d\log n}{n}}\big)$と$o\big(\sqrt{\frac{d(\log n)^2}{n}}\big)$である。
重み付き雑音下では、応答外れ値の切り換えにより、収束率の遅い誤差を持つロバスト推定器を提案する。
一方、NPR では、それぞれサブガウスおよびサブ指数雑音に対して $O\big(\sqrt {\frac{d\log n}{n}}\big)$ と $O\big(\sqrt {\frac{d(\log n)^2}{n}}\big)$) の有界が得られ、これは既存の有界 $O\big(\frac{||\eta|||_2}{\sqrt{n}}\big)$ よりも本質的に厳密である。
測定行列 $a_k$ を含むngprは測定ベクトル $\alpha_k$ を含む npr よりも計算的に要求されるが、偏りのある決定論的雑音下では npr よりも強い頑健性を示す。
実験結果を示し, 実験結果を確認し, 実証した。
関連論文リスト
- Spectral Statistics of the Sample Covariance Matrix for High Dimensional
Linear Gaussians [12.524855369455421]
高次元安定状態遷移行列の予言のための通常最小二乗法(OLS)の性能
OLS推定器は、遠相遷移を発生させ、遠相遷移となり、推定誤差を悪化させるだけである。
論文 参考訳（メタデータ） (2023-12-10T06:55:37Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Faster Rates of Convergence to Stationary Points in Differentially
Private Optimization [31.46358820048179]
リプシッツの定常点と滑らかな関数を$(varepsilon,delta)$-differential privacy(DP)で近似する問題について検討する。
点 $widehatw$ は関数 $mathbbRdrightarrowmathbbR$ if $|nabla F(widehatw)|leq alpha$ の $alpha$-stationary point と呼ばれる。
我々は$tildeObig(big[)を見つける新しい効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-06-02T02:43:44Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - On the Power of Localized Perceptron for Label-Optimal Learning of
Halfspaces with Adversarial Noise [4.8728183994912415]
対比雑音を伴う$mathbbRd$の同質半空間のオンラインアクティブ学習について研究する。
私たちの主な貢献は、時間内で動作するパーセプトロンライクなアクティブラーニングアルゴリズムです。
アルゴリズムは、ほぼ最適ラベルの複雑さで基礎となるハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-12-19T22:04:10Z) - On the robustness of the minimum $\ell_2$ interpolator [2.918940961856197]
一般高次元線形回帰フレームワークにおいて最小$ell$-norm$hatbeta$で補間を解析する。
高い確率で、この推定器の予測損失は、上から$(|beta*|2r_cn(Sigma)vee |xi|2)/n$で有界であることを証明する。
論文 参考訳（メタデータ） (2020-03-12T15:12:28Z) - Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。
Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
論文 参考訳（メタデータ） (2020-01-25T14:44:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。