論文の概要: On the Sample Complexity and Optimization Landscape for Quadratic
Feasibility Problems
- arxiv url: http://arxiv.org/abs/2002.01066v2
- Date: Mon, 14 Dec 2020 19:10:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-04 02:59:07.092530
- Title: On the Sample Complexity and Optimization Landscape for Quadratic
Feasibility Problems
- Title（参考訳）: 二次可能性問題に対するサンプル複雑度と最適化景観について
- Authors: Parth Thaker, Gautam Dasarathy, and Angelia Nedi\'c
- Abstract要約: 複素ベクトル $mathbfxin mathbbCn$ を $mangle A-imathbfx, mathbfxr_i=1m から復元する問題を考える。
一般に、NP-ハードが解ける二次問題であるだけでなく、実際には特定できないかもしれない。
- 参考スコア（独自算出の注目度）: 7.722592882475735
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of recovering a complex vector $\mathbf{x}\in
\mathbb{C}^n$ from $m$ quadratic measurements $\{\langle A_i\mathbf{x},
\mathbf{x}\rangle\}_{i=1}^m$. This problem, known as quadratic feasibility,
encompasses the well known phase retrieval problem and has applications in a
wide range of important areas including power system state estimation and x-ray
crystallography. In general, not only is the the quadratic feasibility problem
NP-hard to solve, but it may in fact be unidentifiable. In this paper, we
establish conditions under which this problem becomes {identifiable}, and
further prove isometry properties in the case when the matrices
$\{A_i\}_{i=1}^m$ are Hermitian matrices sampled from a complex Gaussian
distribution. Moreover, we explore a nonconvex {optimization} formulation of
this problem, and establish salient features of the associated optimization
landscape that enables gradient algorithms with an arbitrary initialization to
converge to a \emph{globally optimal} point with a high probability. Our
results also reveal sample complexity requirements for successfully identifying
a feasible solution in these contexts.
- Abstract（参考訳）: 複素ベクトル $\mathbf{x}\in \mathbb{C}^n$ を $m$ 二次測度 $\{\langle A_i\mathbf{x}, \mathbf{x}\rangle\}_{i=1}^m$ から回収する問題を考える。
この問題は二次実現可能性と呼ばれ、よく知られた位相検索問題を含み、電力系統状態推定やx線結晶構造解析など、幅広い分野に適用できる。
一般に、NP-ハードが解決すべき二次実現可能性問題であるだけでなく、実際には特定できないかもしれない。
本稿では,この問題が {identizable} となる条件を定式化し,複素ガウス分布からサンプリングされたエルミート行列の行列 $\{a_i\}_{i=1}^m$ の場合の等長性をさらに証明する。
さらに、この問題の非凸最適化を定式化し、任意の初期化を持つ勾配アルゴリズムを高い確率で \emph{globally optimal} 点に収束させることを可能にする、関連する最適化ランドスケープの有意義な特徴を確立する。
また,これらの文脈で実現可能な解の同定に成功するためのサンプル複雑性要件も明らかにした。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。
我々のアルゴリズムは距離を使って複雑さを見積もることができる。
MathO (log d) / EuM4。
DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
論文 参考訳（メタデータ） (2024-06-27T18:38:42Z) - Checking the Sufficiently Scattered Condition using a Global Non-Convex
Optimization Software [16.556378176193032]
十分分散状態 (SSC) は、行列分解問題の同定可能性において重要な条件である。
現実的なシナリオで適切な時間内にチェックできることが示されます。
論文 参考訳（メタデータ） (2024-02-08T19:41:38Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Efficient Algorithms for High-Dimensional Convex Subspace Optimization
via Strict Complementarity [19.24470467199451]
目的が$realsn$, $k$の部分空間を見つけることにある最適化問題を考慮し、凸の滑らかな損失を最小限に抑える。
この問題は高次元のレジームでは高いが、大域的最適解を見つけることは困難である。
本稿では自然について述べる。
収束する最適な次元緩和を 決定するのです
グローバルは単純です
論文 参考訳（メタデータ） (2022-02-08T17:36:43Z) - Learning Linear Models Using Distributed Iterative Hessian Sketching [4.567810220723372]
観測データから線形システムのマルコフパラメータを学習する問題を考察する。
Hessian-Sketchingに基づくランダムに分散されたニュートンアルゴリズムは、$epsilon$-optimal Solutionを生成可能であることを示す。
論文 参考訳（メタデータ） (2021-12-08T04:07:23Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - The limits of min-max optimization algorithms: convergence to spurious
non-critical sets [82.74514886461257]
min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。
問題のどの点も引き付けないアルゴリズムが存在することを示す。
ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
論文 参考訳（メタデータ） (2020-06-16T10:49:27Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。