論文の概要: From graph cuts to isoperimetric inequalities: Convergence rates of
Cheeger cuts on data clouds
- arxiv url: http://arxiv.org/abs/2004.09304v2
- Date: Fri, 11 Mar 2022 16:51:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-11 18:29:31.852767
- Title: From graph cuts to isoperimetric inequalities: Convergence rates of
Cheeger cuts on data clouds
- Title（参考訳）: グラフカットから等度不等式へ:データクラウド上のチーガーカットの収束率
- Authors: Nicolas Garcia Trillos, Ryan Murray, Matthew Thorpe
- Abstract要約: バランスの取れたグラフカットの最適化に依存するグラフベースのクラスタリングアルゴリズムについて検討する。
チェーガー定数とそれに関連するチェーガーカットの両方に対して、それらの連続体に対する高い確率収束率を得る。
- 参考スコア（独自算出の注目度）: 3.222802562733786
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we study statistical properties of graph-based clustering
algorithms that rely on the optimization of balanced graph cuts, the main
example being the optimization of Cheeger cuts. We consider proximity graphs
built from data sampled from an underlying distribution supported on a generic
smooth compact manifold $M$. In this setting, we obtain high probability
convergence rates for both the Cheeger constant and the associated Cheeger cuts
towards their continuum counterparts. The key technical tools are careful
estimates of interpolation operators which lift empirical Cheeger cuts to the
continuum, as well as continuum stability estimates for isoperimetric problems.
To our knowledge the quantitative estimates obtained here are the first of
their kind.
- Abstract（参考訳）: 本研究では,均衡グラフ切断の最適化に依存するグラフクラスタリングアルゴリズムの統計的性質について検討し,その一例としてチーガーカットの最適化について述べる。
我々は、汎用的な滑らかなコンパクト多様体上でサポートされている基底分布からサンプリングされたデータから構築された近接グラフを考える。
この設定では、シーガー定数とそれに伴うシーガーカットの両方が連続体に対して高い確率収束率を得る。
主要な技術ツールは、実験的なチーガーカットを連続体に引き上げる補間作用素の慎重な推定と、等尺問題に対する連続的な安定性の推定である。
我々の知る限り、ここで得られた量的推定は彼らの最初のものである。
関連論文リスト
- Variance-Reducing Couplings for Random Features [57.73648780299374]
ランダム機能(RF)は、機械学習においてカーネルメソッドをスケールアップする一般的なテクニックである。
ユークリッド空間と離散入力空間の両方で定義されるRFを改善するための結合を求める。
パラダイムとしての分散還元の利点と限界について、驚くほどの結論に達した。
論文 参考訳（メタデータ） (2024-05-26T12:25:09Z) - On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
我々は,強い対数対数データの下での拡散に基づく生成モデルの収束挙動を理論的に保証する。
スコア推定に使用される関数のクラスは、スコア関数上のリプシッツネスの仮定を避けるために、リプシッツ連続関数からなる。
この手法はサンプリングアルゴリズムにおいて最もよく知られた収束率をもたらす。
論文 参考訳（メタデータ） (2023-11-22T18:40:45Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
グラフの混合重みとノード間のデータ不均一性の関係に収束の依存性を特徴付ける。
グラフが現在の勾配を混合する能力を定量化する計量法を提案する。
そこで本研究では,パラメータを周期的かつ効率的に最適化する手法を提案する。
論文 参考訳（メタデータ） (2022-04-13T15:54:35Z) - COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic
Convex Optimization [4.970364068620608]
我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。
問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。
また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
論文 参考訳（メタデータ） (2021-09-07T17:21:09Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - Continuous Regularized Wasserstein Barycenters [51.620781112674024]
正規化ワッサーシュタイン・バリセンタ問題に対する新しい双対定式化を導入する。
我々は、強い双対性を確立し、対応する主対関係を用いて、正規化された輸送問題の双対ポテンシャルを用いて暗黙的にバリセンターをパラメトリゼーションする。
論文 参考訳（メタデータ） (2020-08-28T08:28:06Z) - Weighted Cheeger and Buser Inequalities, with Applications to Clustering
and Cutting Probability Densities [0.30586855806896046]
確率密度関数のスパースあるいは等尺カットが、その主固有関数のチーガーカットとどのように関係しているかを示す。
Alon-Milman の正規化グラフ Laplacian に類似した Cheeger と Buser の型不等式を証明する。
論文 参考訳（メタデータ） (2020-04-20T19:31:25Z) - Residual Correlation in Graph Neural Network Regression [39.54530450932135]
我々は条件付き独立仮定が予測力を著しく制限していることを示します。
この問題を解釈可能かつ効率的なフレームワークで解決する。
我々のフレームワークは、競合するベースラインよりもかなり高い精度を実現している。
論文 参考訳（メタデータ） (2020-02-19T16:32:54Z) - Cram\'er-Rao Lower Bounds Arising from Generalized Csisz\'ar Divergences [17.746238062801293]
我々は Csisz'ar $f$-divergences の一般化された族に対する確率分布の幾何学について研究する。
これらの定式化が, 護衛モデルの偏りのない, 効率的な推定手法の発見に繋がることを示す。
論文 参考訳（メタデータ） (2020-01-14T13:41:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。