論文の概要: Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via
Early-Stopped Mirror Descent
- arxiv url: http://arxiv.org/abs/2105.03678v1
- Date: Sat, 8 May 2021 11:22:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-11 15:09:21.908923
- Title: Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via
Early-Stopped Mirror Descent
- Title（参考訳）: 初期停止ミラー降下によるノイズスパース位相検索における準最小最適速度
- Authors: Fan Wu, Patrick Rebeschini
- Abstract要約: 本稿では,雑音の位相探索に応用した早期停止ミラー降下法について検討する。
単純なアルゴリズムは、スパーシティを促進するために明示的な正規化やしきい値ステップに依存しない。
- 参考スコア（独自算出の注目度）: 29.206451882562867
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies early-stopped mirror descent applied to noisy sparse phase
retrieval, which is the problem of recovering a $k$-sparse signal
$\mathbf{x}^\star\in\mathbb{R}^n$ from a set of quadratic Gaussian measurements
corrupted by sub-exponential noise. We consider the (non-convex) unregularized
empirical risk minimization problem and show that early-stopped mirror descent,
when equipped with the hyperbolic entropy mirror map and proper initialization,
achieves a nearly minimax-optimal rate of convergence, provided the sample size
is at least of order $k^2$ (modulo logarithmic term) and the minimum (in
modulus) non-zero entry of the signal is on the order of
$\|\mathbf{x}^\star\|_2/\sqrt{k}$. Our theory leads to a simple algorithm that
does not rely on explicit regularization or thresholding steps to promote
sparsity. More generally, our results establish a connection between mirror
descent and sparsity in the non-convex problem of noisy sparse phase retrieval,
adding to the literature on early stopping that has mostly focused on
non-sparse, Euclidean, and convex settings via gradient descent. Our proof
combines a potential-based analysis of mirror descent with a quantitative
control on a variational coherence property that we establish along the path of
mirror descent, up to a prescribed stopping time.
- Abstract（参考訳）: 本稿では,雑音による2次ガウス測度から$k$sparse信号 $\mathbf{x}^\star\in\mathbb{R}^n$ を復元する問題である雑音のスパース位相探索に適用した初期停止ミラー降下について検討する。
非凸)非正規化経験的リスク最小化問題を考えると、双曲的エントロピーミラーマップと適切な初期化を備えると、サンプルサイズが少なくとも$k^2$ (modulo logarithmic term) であり、信号の最小(モジュラー内)非零入力が$\|\mathbf{x}^\star\|_2/\sqrt{k}$ の順であることから、初期停止ミラー降下は、ほぼ最小の最適収束率を達成する。
我々の理論は、空間性を促進するために明示的な正規化やしきい値化のステップに依存しない単純なアルゴリズムにつながる。
より一般に, 雑音下スパース位相検索の非凸問題におけるミラー降下とスパース性の関係が確立され, 勾配降下による非スパース, ユークリッド, 凸設定に主に焦点をあてた早期停止に関する文献が追加されている。
この証明は、ミラー降下のポテンシャルに基づく解析と、ミラー降下の経路に沿って確立される変動コヒーレンス特性を、所定の停止時間まで定量的に制御することを組み合わせたものである。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Stable Phase Retrieval with Mirror Descent [0.5312303275762104]
ミラー降下は位相探索問題の臨界点に収束することを示す。
我々は、高い確率でミラー降下が真のベクトルに近い大域最小化器に収束することを保証する大域収束保証を提供する。
論文 参考訳（メタデータ） (2024-05-17T13:07:14Z) - A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。
i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。
その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
論文 参考訳（メタデータ） (2024-04-18T16:46:08Z) - Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm [12.405427902037971]
本稿では,コンパクトかつ凸集合を持つ分布からの近似サンプリング法を提案する。
このアルゴリズムは、ミラーランゲヴィンの単一ステップによって誘導されるマルコフ連鎖にアセプション-リジェクションフィルタを追加する。
近似的制約サンプリングの誤差耐性に対する指数関数的に優れた依存性が得られる。
論文 参考訳（メタデータ） (2023-12-14T11:11:58Z) - Provable Phase Retrieval with Mirror Descent [1.1662472705038338]
我々は,その挙動の程度から$n$-mの実ベクトルを復元する位相探索の問題を考察する。
2つの測定値について、n$の値が十分であれば、ほとんどすべての初期化子に対して高い確率で元のベクトルが符号まで回復することを示す。
論文 参考訳（メタデータ） (2022-10-17T16:40:02Z) - A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback [93.57603470949266]
2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。
我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-05-27T11:23:57Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval [24.17778927729799]
スパース位相探索に適用した連続時間ミラーを解析する。
これは、測定のみの集合からスパース信号を復元する問題である。
この問題に対して収束解析アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-20T10:03: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) - The Statistical Complexity of Early-Stopped Mirror Descent [27.393821783237186]
早期停止ミラー降下アルゴリズムにより達成される過剰リスクの統計的保証について検討する。
正方形損失の凸性を特徴づける不等式を完遂することにより、オフセットラデマッハ複素数とミラー降下法のポテンシャルベース収束解析との内在的リンクを同定する。
論文 参考訳（メタデータ） (2020-02-01T11:05:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。