論文の概要: The Local Landscape of Phase Retrieval Under Limited Samples
- arxiv url: http://arxiv.org/abs/2311.15221v1
- Date: Sun, 26 Nov 2023 07:22:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-28 18:46:53.039834
- Title: The Local Landscape of Phase Retrieval Under Limited Samples
- Title（参考訳）: 限られたサンプルによる位相検索の局所的景観
- Authors: Kaizhao Liu, Zihao Wang, Lei Wu
- Abstract要約: 本研究では,限られたサンプルを用いて,地域景観の位相探索の詳細な解析を行う。
我々の目的は、世界規模のミニマを取り巻く良質な景観を保証するのに必要な最小限のサンプルサイズを確かめることである。
- 参考スコア（独自算出の注目度）: 13.898742971304952
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we provide a fine-grained analysis of the local landscape of
phase retrieval under the regime with limited samples. Our aim is to ascertain
the minimal sample size necessary to guarantee a benign local landscape
surrounding global minima in high dimensions. Let $n$ and $d$ denote the sample
size and input dimension, respectively. We first explore the local convexity
and establish that when $n=o(d\log d)$, for almost every fixed point in the
local ball, the Hessian matrix must have negative eigenvalues as long as $d$ is
sufficiently large. Consequently, the local landscape is highly non-convex. We
next consider the one-point strong convexity and show that as long as
$n=\omega(d)$, with high probability, the landscape is one-point strongly
convex in the local annulus: $\{w\in\mathbb{R}^d: o_d(1)\leqslant
\|w-w^*\|\leqslant c\}$, where $w^*$ is the ground truth and $c$ is an absolute
constant. This implies that gradient descent initialized from any point in this
domain can converge to an $o_d(1)$-loss solution exponentially fast.
Furthermore, we show that when $n=o(d\log d)$, there is a radius of
$\widetilde\Theta\left(\sqrt{1/d}\right)$ such that one-point convexity breaks
in the corresponding smaller local ball. This indicates an impossibility to
establish a convergence to exact $w^*$ for gradient descent under limited
samples by relying solely on one-point convexity.
- Abstract（参考訳）: 本稿では,限られたサンプルを用いて局地的位相探索の局地的景観を詳細に解析する。
本研究の目的は,グローバルミニマを取り巻く良質な局所景観を高次元で保証するために必要なサンプルサイズを最小にすることである。
n$ と $d$ はそれぞれサンプルサイズと入力次元を表す。
まず、局所凸性を探究し、$n=o(d\log d)$ が局所球のほとんどすべての固定点に対して、ヘッセン行列は、d$が十分大きい限り負の固有値を持つ必要があることを確かめる。
そのため、地域景観は非凸である。
次に、一点強凸性を考えると、n=\omega(d)$ である限り、高い確率で、そのランドスケープは局所環状の 1点強凸である: $\{w\in\mathbb{r}^d: o_d(1)\leqslant \|w-w^*\|\leqslant c\}$, ここで $w^*$ は基底真理であり、$c$ は絶対定数である。
これは、この領域の任意の点から初期化された勾配降下が指数関数的に速く$o_d(1)$-loss解に収束することを意味する。
さらに、$n=o(d\log d)$ のとき、半径が $\widetilde\Theta\left(\sqrt{1/d}\right)$ であることを示し、一点凸性は対応する小さな局所球で破れる。
これは、一点凸性のみに依存することで、限られたサンプルの下での勾配降下に対して正確な$w^*$の収束を確立することができないことを示している。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Multiple-policy Evaluation via Density Estimation [30.914344538340412]
本稿では,この問題に対して$mathrmCAESAR$というアルゴリズムを提案する。
低次かつ対数的な$mathrmCAESAR$は、$tildeOleft(fracH4epsilon2sum_h=1Hmax_kin[K]sum_s,afrac(d_hpik(s,a))2mu*_h(s,a)right)$である。
論文 参考訳（メタデータ） (2024-03-29T23:55:25Z) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Learning linear dynamical systems under convex constraints [4.4351901934764975]
線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。
A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
論文 参考訳（メタデータ） (2023-03-27T11:49:40Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。
SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。
我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
論文 参考訳（メタデータ） (2021-10-25T07:20:05Z) - Nonasymptotic one-and two-sample tests in high dimension with unknown
covariance structure [0.0]
テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。
本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
論文 参考訳（メタデータ） (2021-09-01T06:22:53Z) - Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
ノイズの多いサンプルの有限集合から$mathbbRD$の$d$次元部分多様体を推定する問題を検討する。
点推定では$n-frack2k + d$、接空間の推定では$n-frack-12k + d$の収束率を推定する。
論文 参考訳（メタデータ） (2021-05-11T02:29:33Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。