論文の概要: On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling

• arxiv url: http://arxiv.org/abs/2602.13684v1
• Date: Sat, 14 Feb 2026 09:12:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 14:17:28.337458
• Title: On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling
• Title（参考訳）: 相関クラスタリングのスパーシフィビリティについて:エッジサンプリングによる近似保証
• Authors: Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma,
• Abstract要約: 相関クラスタリング(CC)は基本的な教師なし学習プリミティブである。 LPベースの保証を維持するためには,どの程度のエッジ情報が必要であるかを検討する。 ヤオのミニマックス原理を通して、擬距離構造がなければ、任意のアルゴリズムが$o(n)$一様ランダムエッジを観測すると近似比が生じることを示す。
• 参考スコア（独自算出の注目度）: 6.908972852063454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Correlation Clustering (CC) is a fundamental unsupervised learning primitive whose strongest LP-based approximation guarantees require $Θ(n^3)$ triangle inequality constraints and are prohibitive at scale. We initiate the study of \emph{sparsification--approximation trade-offs} for CC, asking how much edge information is needed to retain LP-based guarantees. We establish a structural dichotomy between pseudometric and general weighted instances. On the positive side, we prove that the VC dimension of the clustering disagreement class is exactly $n{-}1$, yielding additive $\varepsilon$-coresets of optimal size $\tilde{O}(n/\varepsilon^2)$; that at most $\binom{n}{2}$ triangle inequalities are active at any LP vertex, enabling an exact cutting-plane solver; and that a sparsified variant of LP-PIVOT, which imputes missing LP marginals via triangle inequalities, achieves a robust $\frac{10}{3}$-approximation (up to an additive term controlled by an empirically computable imputation-quality statistic $\overlineΓ_w$) once $\tildeΘ(n^{3/2})$ edges are observed, a threshold we prove is sharp. On the negative side, we show via Yao's minimax principle that without pseudometric structure, any algorithm observing $o(n)$ uniformly random edges incurs an unbounded approximation ratio, demonstrating that the pseudometric condition governs not only tractability but also the robustness of CC to incomplete information.
• Abstract（参考訳）: 相関クラスタリング (CC) は基本的な教師なし学習プリミティブであり、LPに基づく最強近似を保証するには、(n^3)$三角形の不等式制約が必要である。 我々は,LPベースの保証を維持するためにどの程度のエッジ情報が必要なのかを問う,CCのためのemph{sparsification--approximation trade-offs}の研究を開始する。 擬似計量と一般重み付きインスタンスの構造的二分法を確立する。 正の面では、クラスタリング不一致クラスのVC次元がちょうど$n{-}1$であり、最適サイズ$\tilde{O}(n/\varepsilon^2)$ の加法 $\varepsilon$-coresets が得られることを証明し、少なくとも$\binom{n}{2}$ 三角形の不等式は任意のLP頂点で有効であり、正確な切断平面ソルバが可能であることを証明し、かつ、LP-PIVOT のスパース化された変種は、三角形の不等式によってLPの辺縁を含まないことを暗示する、堅牢な$\frac{10}{3}$-approximation (経験的に計算可能な不等式によって制御される加法項$\tilde{O}(n/\varepsilon^2)$ を満たす。 負の面から、Yaoのミニマックス原理により、$o(n)$一様ランダムエッジを観測するアルゴリズムは、非有界近似比を生じさせ、擬似距離条件がトラクタビリティだけでなく、CCの不完全情報に対するロバスト性も支配することを示した。

関連論文リスト

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 ノイズモーメントを仮定することなく、幅広い種類の非線形性を保証する。
  論文  参考訳（メタデータ） (2024-10-17T18:25:28Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)

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

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