論文の概要: Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms

• arxiv url: http://arxiv.org/abs/2510.15076v1
• Date: Thu, 16 Oct 2025 18:42:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-20 20:17:34.359096
• Title: Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
• Title（参考訳）: オンライン相関クラスタリング:$\ell_p$-normsを同時に最適化
• Authors: Sami Davies, Benjamin Moseley, Heather Newman,
• Abstract要約: オフライン設定では、すべての $ell_p$-norms と単一のクラスタリングを同時に近似することができる。 オンラインサンプル(AOS)モデルに対して,高い確率で全ての$ell_p$-normsに対して同時に$O(log4 n)$-competitiveの1つのアルゴリズムを提案する。 この作業は、オフラインの"All-norms"保証をオンラインの世界に翻訳することに成功した。
• 参考スコア（独自算出の注目度）: 14.749236760550332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The $\ell_p$-norm objectives for correlation clustering present a fundamental trade-off between minimizing total disagreements (the $\ell_1$-norm) and ensuring fairness to individual nodes (the $\ell_\infty$-norm). Surprisingly, in the offline setting it is possible to simultaneously approximate all $\ell_p$-norms with a single clustering. Can this powerful guarantee be achieved in an online setting? This paper provides the first affirmative answer. We present a single algorithm for the online-with-a-sample (AOS) model that, given a small constant fraction of the input as a sample, produces one clustering that is simultaneously $O(\log^4 n)$-competitive for all $\ell_p$-norms with high probability, $O(\log n)$-competitive for the $\ell_\infty$-norm with high probability, and $O(1)$-competitive for the $\ell_1$-norm in expectation. This work successfully translates the offline "all-norms" guarantee to the online world. Our setting is motivated by a new hardness result that demonstrates a fundamental separation between these objectives in the standard random-order (RO) online model. Namely, while the $\ell_1$-norm is trivially $O(1)$-approximable in the RO model, we prove that any algorithm in the RO model for the fairness-promoting $\ell_\infty$-norm must have a competitive ratio of at least $\Omega(n^{1/3})$. This highlights the necessity of a different beyond-worst-case model. We complement our algorithm with lower bounds, showing our competitive ratios for the $\ell_1$- and $\ell_\infty$- norms are nearly tight in the AOS model.
• Abstract（参考訳）: 相関クラスタリングの$\ell_p$-normの目的は、全体の不一致を最小化すること($\ell_1$-norm)と、個々のノードに対する公平性を確保すること($\ell_\infty$-norm)の間に、根本的なトレードオフをもたらす。 驚くべきことに、オフライン設定では、すべての$\ell_p$-normsを同時に1つのクラスタリングに近似することができる。 この強力な保証は、オンライン環境で達成できるだろうか? 本稿は、最初の肯定的な回答を提供する。 オンライン・ウィズ・ア・サンプレット(AOS)モデルに対して、入力の小さな定数をサンプルとして与え、高い確率のすべての$\ell_p$-normsに対して同時に$O(\log^4 n)$-competitive、高い確率の$O(\log n)$-competitive、高い確率の$\ell_\infty$-normに対して$O(1)$-competitive、期待の$\ell_1$-normに対して$O(1)$-competitiveを生成する。 この作業は、オフラインの"All-norms"保証をオンラインの世界に翻訳することに成功した。 我々の設定は、標準ランダムオーダー(RO)オンラインモデルにおけるこれらの目的の根本的な分離を示す新しい硬度結果によって動機付けられている。 つまり、$\ell_1$-norm は RO モデルにおいて自明に$O(1)$-approximable であるが、フェアネスを動機とする $\ell_\infty$-norm に対する RO モデルの任意のアルゴリズムは、少なくとも$\Omega(n^{1/3})$ の競合比を持つ必要があることを証明している。 これは、異なるエクストラウォーストケースモデルの必要性を強調します。 我々はアルゴリズムを低い境界で補完し、AOSモデルでは$\ell_1$-と$\ell_\infty$-の競合比がほぼ密であることを示す。

関連論文リスト

• Closed-form $\ell_r$ norm scaling with data for overparameterized linear regression and diagonal linear networks under $\ell_p$ bias [0.0]
  パラメータノルムの族をスケールするために、統一的で高確率な特徴を与える。 次に、降下によって訓練された線形ネットワークについて研究する。
  論文  参考訳（メタデータ） (2025-09-25T13:59:22Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
  私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。 つまり、少なくとも$theta$のリスクが他のグループのリスクよりも少なくとも$lambda$であるような、少なくとも$beta$グループのセットがあります。 計算効率のよい手法により,次元自由な半適応サンプルの複雑性を得る方法を示す。
  論文  参考訳（メタデータ） (2024-10-01T13:45:55Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Online Lewis Weight Sampling [62.38157566916501]
  コーエンとペンはルイスの重量サンプリングを理論計算機科学コミュニティに導入した。 この重要なプリミティブを、オンラインコアセット、スライディングウィンドウ、対向ストリーミングモデルなど、他の設定に拡張した作品もいくつかある。 オンラインコアセット,スライディングウィンドウ,および逆ストリーミングモデルにおいて,すべての$pin(0,infty)$に対して,ほぼ最適に近い$ell_p$サブスペース埋め込みを設計する。
  論文  参考訳（メタデータ） (2022-07-17T19:40:51Z)
• Near-optimal Algorithms for Explainable k-Medians and k-Means [12.68470213641421]
  Dasgupta, Frost, Moshkovitz, Rashtchian (ICML 2020) が導入した$k$-medians と $k$-means の問題を考える。 私たちのゴールは、データを$kクラスタに分割し、$k-mediansや$k-meansの目的を最小化する、最適な決定ツリーを見つけることです。
  論文  参考訳（メタデータ） (2021-07-02T02:07:12Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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