論文の概要: Improved Algorithm and Bounds for Successive Projection

• arxiv url: http://arxiv.org/abs/2403.11013v1
• Date: Sat, 16 Mar 2024 20:42:27 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 20:36:44.404323
• Title: Improved Algorithm and Bounds for Successive Projection
• Title（参考訳）: 逐次投影のための改良されたアルゴリズムと境界
• Authors: Jiashun Jin, Zheng Tracy Ke, Gabriel Moryoussef, Jiajun Tang, Jingming Wang,
• Abstract要約: 頂点探索は、単純体の$K$頂点を推定する問題である。 一般的なアルゴリズムは逐次投影アルゴリズム(SPA)である 擬似点SPA(pp-SPA)を提案する。 p-SPAの誤差境界を導出し、(おそらく)高次元ランダムベクトルの極値理論を利用する。
• 参考スコア（独自算出の注目度）: 10.308064661121552
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a $K$-vertex simplex in a $d$-dimensional space, suppose we measure $n$ points on the simplex with noise (hence, some of the observed points fall outside the simplex). Vertex hunting is the problem of estimating the $K$ vertices of the simplex. A popular vertex hunting algorithm is successive projection algorithm (SPA). However, SPA is observed to perform unsatisfactorily under strong noise or outliers. We propose pseudo-point SPA (pp-SPA). It uses a projection step and a denoise step to generate pseudo-points and feed them into SPA for vertex hunting. We derive error bounds for pp-SPA, leveraging on extreme value theory of (possibly) high-dimensional random vectors. The results suggest that pp-SPA has faster rates and better numerical performances than SPA. Our analysis includes an improved non-asymptotic bound for the original SPA, which is of independent interest.
• Abstract（参考訳）: $d$-次元空間における$K$-頂点単純点が与えられたとき、ノイズのある単純点上の$n$点を測ると仮定する(従って、観測された点のいくつかは単純点の外にある)。 頂点探索は、単純体の$K$頂点を推定する問題である。 一般的な頂点探索アルゴリズムは逐次投影アルゴリズム(SPA)である。 しかし、SPAは強い雑音や外周下では不満足に動作することが観察される。 擬似点SPA(pp-SPA)を提案する。 プロジェクションステップと denoise ステップを使用して擬似点を生成し、頂点狩りのためにSPAに供給する。 p-SPAの誤差境界を導出し、(おそらく)高次元ランダムベクトルの極値理論を利用する。 その結果, p-SPAはSPAよりも高速で, 数値性能が良好であることが示唆された。 我々の分析には、独立した関心を持つ元のSPAに対する非漸近的境界の改善が含まれている。

関連論文リスト

• On the Robustness of the Successive Projection Algorithm [13.554186778126095]
  我々は,SPAの雑音に対する頑健さとその変種について再考する。 特に,SPAにおける既存の誤差境界の厳密性を証明する。 我々は、まずデータポイントをシフトして持ち上げる、より堅牢なSPAの亜種を提案する。
  論文  参考訳（メタデータ） (2024-11-25T08:49:33Z)
• On the SAGA algorithm with decreasing step [0.0]
  本稿では,Gradient DescentアルゴリズムとSAGAアルゴリズムを補間する新しい$lambda$-SAGAアルゴリズムを提案する。 我々は$lambda$-SAGAアルゴリズムの中央極限定理を確立する。 非漸近的な$mathbbLp$収束率を提供する。
  論文  参考訳（メタデータ） (2024-10-02T12:04:36Z)
• Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
  重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。 その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
  論文  参考訳（メタデータ） (2024-08-19T11:07:05Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
  強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。 1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
  論文  参考訳（メタデータ） (2021-02-19T01:42:50Z)
• Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
  複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
  論文  参考訳（メタデータ） (2020-10-21T15:05:53Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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