論文の概要: On the Robustness of the Successive Projection Algorithm

• arxiv url: http://arxiv.org/abs/2411.16195v1
• Date: Mon, 25 Nov 2024 08:49:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-26 14:22:21.165516
• Title: On the Robustness of the Successive Projection Algorithm
• Title（参考訳）: 連続射影アルゴリズムのロバスト性について
• Authors: Giovanni Barbarino, Nicolas Gillis,
• Abstract要約: 我々は,SPAの雑音に対する頑健さとその変種について再考する。 特に,SPAにおける既存の誤差境界の厳密性を証明する。 我々は、まずデータポイントをシフトして持ち上げる、より堅牢なSPAの亜種を提案する。
• 参考スコア（独自算出の注目度）: 13.554186778126095
• License:
• Abstract: The successive projection algorithm (SPA) is a workhorse algorithm to learn the $r$ vertices of the convex hull of a set of $(r-1)$-dimensional data points, a.k.a. a latent simplex, which has numerous applications in data science. In this paper, we revisit the robustness to noise of SPA and several of its variants. In particular, when $r \geq 3$, we prove the tightness of the existing error bounds for SPA and for two more robust preconditioned variants of SPA. We also provide significantly improved error bounds for SPA, by a factor proportional to the conditioning of the $r$ vertices, in two special cases: for the first extracted vertex, and when $r \leq 2$. We then provide further improvements for the error bounds of a translated version of SPA proposed by Arora et al. (''A practical algorithm for topic modeling with provable guarantees'', ICML, 2013) in two special cases: for the first two extracted vertices, and when $r \leq 3$. Finally, we propose a new more robust variant of SPA that first shifts and lifts the data points in order to minimize the conditioning of the problem. We illustrate our results on synthetic data.
• Abstract（参考訳）: 逐次プロジェクションアルゴリズム(SPA)は、データサイエンスに多くの応用がある、$(r-1)$-dimensional データポイントの集合の凸殻の$r$頂点を学習するためのワークホースアルゴリズムである。 本稿では,SPAの雑音に対するロバスト性とその変種について再検討する。 特に、$r \geq 3$ の場合、SPA と SPA のより堅牢な2つの事前条件付き変種に対して、既存の誤差境界の厳密性を証明する。 また,SPAに対して,最初の抽出頂点の場合と$r \leq 2$の場合の2つの特別な場合において,$r$Verticesの条件に比例する係数で誤差境界を著しく改善する。 次に、Aroraらによって提案されたSPAの翻訳版('証明可能な保証付きトピックモデリングのための実践的アルゴリズム', ICML, 2013)のエラー境界について、最初の2つの抽出頂点と$r \leq 3$の2つの特別なケースでさらに改善する。 最後に、問題の条件付けを最小化するために、まずデータポイントをシフトし、持ち上げるSPAのより堅牢な新しい変種を提案する。 合成データについてその結果を解説する。

関連論文リスト

• Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
  非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。 本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
  論文  参考訳（メタデータ） (2024-05-28T20:52:46Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Improved Algorithm and Bounds for Successive Projection [10.308064661121552]
  頂点探索は、単純体の$K$頂点を推定する問題である。 一般的なアルゴリズムは逐次投影アルゴリズム(SPA)である 擬似点SPA(pp-SPA)を提案する。 p-SPAの誤差境界を導出し、(おそらく)高次元ランダムベクトルの極値理論を利用する。
  論文  参考訳（メタデータ） (2024-03-16T20:42:27Z)
• Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
  政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。 本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
  論文  参考訳（メタデータ） (2023-11-15T12:36:45Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
  複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
  論文  参考訳（メタデータ） (2020-10-21T15:05:53Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates [16.54912614895861]
  我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。 我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。 その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
  論文  参考訳（メタデータ） (2020-03-03T03:59:26Z)

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

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