論文の概要: On the simplicity and conditioning of low rank semidefinite programs

• arxiv url: http://arxiv.org/abs/2002.10673v2
• Date: Fri, 23 Jul 2021 03:56:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 21:11:50.368977
• Title: On the simplicity and conditioning of low rank semidefinite programs
• Title（参考訳）: 低階半定プログラムの単純性と条件付けについて
• Authors: Lijun Ding, Madeleine Udell
• Abstract要約: 完全データによるSDPの正確な解は、元の低階行列回復問題に対する解を復元することがよく知られている。 ノイズの多い問題データで定式化されたSDPの近似解が元の問題を許容的に解くことを示すことはより困難である。 本稿では,ノイズ問題データや不完全収束による誤差を制限する簡易性と呼ばれる条件の集合を同定する。
• 参考スコア（独自算出の注目度）: 28.71984085513293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Low rank matrix recovery problems appear widely in statistics, combinatorics, and imaging. One celebrated method for solving these problems is to formulate and solve a semidefinite program (SDP). It is often known that the exact solution to the SDP with perfect data recovers the solution to the original low rank matrix recovery problem. It is more challenging to show that an approximate solution to the SDP formulated with noisy problem data acceptably solves the original problem; arguments are usually ad hoc for each problem setting, and can be complex. In this note, we identify a set of conditions that we call simplicity that limit the error due to noisy problem data or incomplete convergence. In this sense, simple SDPs are robust: simple SDPs can be (approximately) solved efficiently at scale; and the resulting approximate solutions, even with noisy data, can be trusted. Moreover, we show that simplicity holds generically, and also for many structured low rank matrix recovery problems, including the stochastic block model, $\mathbb{Z}_2$ synchronization, and matrix completion. Formally, we call an SDP simple if it has a surjective constraint map, admits a unique primal and dual solution pair, and satisfies strong duality and strict complementarity. However, simplicity is not a panacea: we show the Burer-Monteiro formulation of the SDP may have spurious second-order critical points, even for a simple SDP with a rank 1 solution.
• Abstract（参考訳）: 低位行列回復問題は統計学、コンビネータ学、画像学に広く見られる。 これらの問題の解法として、半確定プログラム(SDP)を定式化して解く方法がある。 完全データによるSDPの正確な解は、元の低階行列回復問題に対する解を復元することがよく知られている。 ノイズのある問題データで定式化されたsdpに対する近似解が元の問題を許容的に解くことを示すことはより困難であり、議論は通常各問題の設定に対してアドホックであり、複雑である。 本稿では,ノイズのある問題データや不完全な収束による誤差を制限する,単純さと呼ばれる条件のセットを特定する。 この意味では、単純なsdpsは堅牢であり、単純なsdpsは(ほぼ)スケールで効率的に解くことができ、結果として得られる近似解は、ノイズデータであっても信頼できる。 さらに,確率ブロックモデルや$\mathbb{z}_2$同期,行列補完など,多くの構造的低ランク行列回復問題に対して,単純性が汎用的に保持されることを示した。 形式的には、全射制約写像を持ち、一意の原始および双対解対を認め、強い双対性と厳密な相補性を満たすならば、SDP を単純と呼ぶ。 しかし、単純性はパナセアではない: SDP のブラー・モンティロ定式化は、ランク 1 の解を持つ単純な SDP であっても、二階臨界点を突発的に持つ可能性があることを示す。

関連論文リスト

• Reweighted Solutions for Weighted Low Rank Approximation [47.790126028106734]
  重み付き低階近似(WLRA)は、統計解析から信号処理に至るまで、重要かつ困難なプリミティブである。 そこで本研究では,WLRAに対して,必ずしも低ランクではないが極めて少ないパラメータで保存可能な行列を出力する緩和解を提案する。 我々の中心となる考え方は、重み行列自体を低階解の重み付けに利用することであり、これは非常に単純なアルゴリズムであり、顕著な経験的性能を与える。
  論文  参考訳（メタデータ） (2024-06-04T15:50:35Z)
• Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
  線形支援ベクトルマシン(SVM)における組込み特徴選択問題について検討する。 濃度制約が適用され、完全に説明可能な選択モデルが導かれる。 問題は、濃度制約が存在するためNPハードである。
  論文  参考訳（メタデータ） (2024-04-15T19:15:32Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations [27.353023427198806]
  我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。 POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。 我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-05-28T18:07:16Z)
• Probabilistic Simplex Component Analysis [66.30587591100566]
  PRISMは、データ循環記述のシンプルさの頂点をデータから識別する確率論的シンプルコンポーネント分析手法である。 この問題には多様な応用があり、最も注目すべきはリモートセンシングにおけるハイパースペクトルアンミックスと機械学習における非負行列分解である。
  論文  参考訳（メタデータ） (2021-03-18T05:39:00Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。