論文の概要: Understanding the Generalization Performance of Spectral Clustering Algorithms

• arxiv url: http://arxiv.org/abs/2205.00281v1
• Date: Sat, 30 Apr 2022 14:21:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-03 14:00:04.764883
• Title: Understanding the Generalization Performance of Spectral Clustering Algorithms
• Title（参考訳）: スペクトルクラスタリングアルゴリズムの一般化性能の理解
• Authors: Shaojie Li, Sheng Ouyang and Yong Liu
• Abstract要約: 本稿では,一般的なスペクトルクラスタリングアルゴリズムであるEmphrelaxed RatioCutとEmphrelaxed NCutの過剰なリスク境界について検討する。 本稿では,この量をペナルライズするだけでなく,サンプル全体を再固有分解することなくサンプル外のデータをクラスタリングする2つの新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 11.025579607812167
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The theoretical analysis of spectral clustering mainly focuses on consistency, while there is relatively little research on its generalization performance. In this paper, we study the excess risk bounds of the popular spectral clustering algorithms: \emph{relaxed} RatioCut and \emph{relaxed} NCut. Firstly, we show that their excess risk bounds between the empirical continuous optimal solution and the population-level continuous optimal solution have a $\mathcal{O}(1/\sqrt{n})$ convergence rate, where $n$ is the sample size. Secondly, we show the fundamental quantity in influencing the excess risk between the empirical discrete optimal solution and the population-level discrete optimal solution. At the empirical level, algorithms can be designed to reduce this quantity. Based on our theoretical analysis, we propose two novel algorithms that can not only penalize this quantity, but also cluster the out-of-sample data without re-eigendecomposition on the overall sample. Experiments verify the effectiveness of the proposed algorithms.
• Abstract（参考訳）: スペクトルクラスタリングの理論解析は主に一貫性に焦点を当てているが、その一般化性能に関する研究は少ない。 本稿では,一般的なスペクトルクラスタリングアルゴリズム, \emph{relaxed} RatioCut と \emph{relaxed} NCut の過剰なリスク境界について検討する。 まず、経験的連続最適解と人口レベルの連続最適解の間の過剰なリスク境界が$\mathcal{o}(1/\sqrt{n})$収束率を持つことを示す。 第2に,実証的離散最適解と集団レベルでの離散最適解との間の余剰リスクに影響を与える基本量を示す。 経験的なレベルでは、この量を減らすためにアルゴリズムを設計することができる。 理論的解析に基づき,この量をペナルライズするだけでなく,サンプル全体を再固有分解することなくサンプル外のデータをクラスタリングする2つの新しいアルゴリズムを提案する。 提案アルゴリズムの有効性を検証する実験を行った。

関連論文リスト

• SOREL: A Stochastic Algorithm for Spectral Risks Minimization [1.6574413179773761]
  スペクトルリスクは機械学習、特に現実世界の意思決定において幅広い応用がある。 異なるサンプルポイントの損失に異なる重みを割り当てることで、平均的なパフォーマンスと最悪のパフォーマンスの間にモデルのパフォーマンスを配置することができる。 SORELはスペクトルリスク最小化のための収束保証をもつ最初の勾配に基づくアルゴリズムである。
  論文  参考訳（メタデータ） (2024-07-19T18:20:53Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。 非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
  論文  参考訳（メタデータ） (2023-10-19T13:57:38Z)
• Best Subset Selection in Reduced Rank Regression [1.4699455652461724]
  提案アルゴリズムは,有意な確率でランク推定を行うことができることを示す。 がん研究における数値的研究と応用は、有効性と拡張性を示している。
  論文  参考訳（メタデータ） (2022-11-29T02:51:15Z)
• Quantization-Based Optimization: Alternative Stochastic Approximation of Global Optimization [0.0]
  NP-hard問題における目的関数のエネルギーレベルを定量化するための大域的最適化アルゴリズムを提案する。 数値実験により,提案アルゴリズムはNP-ハード最適化問題の解法において従来の学習法よりも優れていた。
  論文  参考訳（メタデータ） (2022-11-08T03:01:45Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。 決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。 我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
  論文  参考訳（メタデータ） (2021-09-20T21:48:19Z)
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory [11.840747467007963]
  我々は,「ベスト勾配仮説」で評価された分散,有効損失誤差,ノルムとほぼ最適にスケールする問題依存率について検討する。 一様局所収束(uniform localized convergence)と呼ばれる原理的枠組みを導入する。 我々は,既存の一様収束と局所化解析のアプローチの基本的制約を,我々のフレームワークが解決していることを示す。
  論文  参考訳（メタデータ） (2020-11-12T04:07:29Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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