論文の概要: Optimally Selecting Representative Agents from a Metric Space
- arxiv url: http://arxiv.org/abs/2608.29097v1
- Date: Sat, 29 Aug 2026 07:05:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:30.836312
- Title: Optimally Selecting Representative Agents from a Metric Space
- Title（参考訳）: メトリック空間から代表エージェントを最適選択する
- Abstract要約: 本稿では, 対等なクラスタリングの問題について検討する。
目標は、計量空間にも属するエージェントの集合を正確に表す計量空間から「$k$center'」を選択することである。
- 参考スコア（独自算出の注目度）: 2.2940141855172036
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the problem of proportionally fair clustering, where the goal is to select $k$ ``centers'' from a metric space that fairly represent a set of agents who also lie in the metric space. Specifically, we focus on finding a clustering satisfying a fairness property known as the Droop core. In the practical special case in which the set of feasible center locations contains every agent location, the previous best-known result guaranteed a $(1 + \sqrt{2})$-approximation of the Droop core, while the best-known lower bound was $2$. In this paper, we show that this lower bound is tight and that a clustering in the $2$-Droop core always exists. Further, we show that such a clustering can be achieved by only selecting centers from locations in the metric space where an agent resides. We establish this using Scarf's theorem guaranteeing a nonempty core for balanced non-transferable utility games. This result has several interesting corollaries. Most notably, it resolves the $β$-plurality problem of Aronov et al. [2021] for general metric spaces. The main result of this paper was generated by $\mathtt{ChatGPT}$-$\mathtt{5.6}$-$\mathtt{Sol}$ through a series of interactions with the authors. The authors of this paper verified the generated proof and rewrote it for clarity.
- Abstract（参考訳）: 本稿では、比例的に公平なクラスタリングの問題を研究し、そこでは、計量空間にまたがるエージェントの集合を正確に表す計量空間から$k$ ``centers' を選択することが目的である。
具体的には、Droopコアとして知られる公正性を満たすクラスタリングを見つけることに焦点を当てる。
実現可能な中心位置の集合がすべてのエージェント位置を含む現実的な特別な場合、前の最もよく知られた結果は、Droopコアの$(1 + \sqrt{2})$-approximationを保証し、最もよく知られた下限は2$である。
本稿では、この下限は厳密であり、2ドルのDroopコアのクラスタリングは常に存在することを示す。
さらに,エージェントが居住する距離空間内の位置からのみ中心を選択することで,そのようなクラスタリングを実現することができることを示す。
我々は、バランスの取れないユーティリティゲームに対して空でないコアを保証するスカーフの定理を用いてこれを確立する。
この結果にはいくつかの興味深い結論がある。
中でも注目すべきは、一般距離空間に対する Aronov et al [2021] の$β$-pleurality 問題を解くことである。
この論文の主な結果は、著者との一連の相互作用を通じて、$\matht{ChatGPT}$-$\matht{5.6}$-$\matht{Sol}$によって生成される。
本論文の著者らは、生成した証明を検証し、明確性のために書き直した。
関連論文リスト
- High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking [69.90407799170687]
分散最適化における高確率収束保証について検討する。
その結果, 地平線上の条件は, 比較時間と同一であることがわかった。
論文 参考訳（メタデータ） (2026-04-30T22:45:21Z) - The Core in Max-Loss Non-Centroid Clustering Can Be Empty [17.80792387357159]
我々は,各エージェントの損失がクラスタの他のメンバとの最大距離である最大余剰目標の下で,非セントロイドクラスタリングのコア安定性について検討した。
これは、我々の知る限りでは、コアが最大ロスの目的の下で非セントロイドクラスタリングにおいて空であることを示す最初の不可能な結果である。
論文 参考訳（メタデータ） (2025-11-24T13:42:43Z) - 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) - A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
我々は、ユーザのネットワーク上で動作する分散センターベースのクラスタリングアルゴリズムのファミリーを開発する。
私たちのフレームワークは、$K$-meansやHuber Losといった一般的なクラスタリング損失を含む、スムーズな凸損失関数の幅広いクラスを可能にします。
ブレグマン損失の特別の場合、固定点がロイド点の集合に収束することを示す。
論文 参考訳（メタデータ） (2024-02-02T10:44:42Z) - Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。
グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
論文 参考訳（メタデータ） (2024-01-16T03:14:24Z) - On Generalization Bounds for Projective Clustering [3.4490841399255823]
ポイントのセットが与えられた場合、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントのパーティションを見つけることで構成される。
中心に基づく目的に対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
j$-次元部分空間を持つ部分空間クラスタリングに対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
論文 参考訳（メタデータ） (2023-10-13T14:15:54Z) - Approximating Fair $k$-Min-Sum-Radii in Euclidean Space [1.6369404745833038]
定数$k$の場合の任意の次元のユークリッド空間における$k$-min-sum-radii問題を研究する。
定数$k$の場合の任意の次元のユークリッド空間における公平な$k$-min-sum-radii問題に対するPTASを提案する。
論文 参考訳（メタデータ） (2023-09-02T06:01:59Z) - Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。
本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
論文 参考訳（メタデータ） (2023-01-17T17:49:04Z) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳（メタデータ） (2022-07-07T06:16:19Z) - FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。
$cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。
$mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文 参考訳（メタデータ） (2021-10-19T17:43:50Z) - Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries [22.672233769934845]
オラクルクエリを用いたクラスタ依存の正確な問題について検討する。
任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意
論文 参考訳（メタデータ） (2021-01-31T18:00:29Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。