論文の概要: Proportional Representation in Metric Spaces and Low-Distortion Committee Selection

• arxiv url: http://arxiv.org/abs/2312.10369v1
• Date: Sat, 16 Dec 2023 08:05:32 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-19 17:06:51.999681
• Title: Proportional Representation in Metric Spaces and Low-Distortion Committee Selection
• Title（参考訳）: 計量空間における比例表現と低歪み委員会選定
• Authors: Yusuf Hakan Kalayci and David Kempe and Vikram Kher
• Abstract要約: ここでは、k 個の点の小さな集合 R が計量空間のより大きな集合の「表現的」であるような新しい定義を導入する。 選挙への適用によって動機づけられた我々は、アルゴリズムが実際の距離を学ばない「通常」モデルに主に焦点をあてる。 結果より, 測定値の歪みが44。
• 参考スコア（独自算出の注目度）: 7.4508125914631105
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We introduce a novel definition for a small set R of k points being "representative" of a larger set in a metric space. Given a set V (e.g., documents or voters) to represent, and a set C of possible representatives, our criterion requires that for any subset S comprising a theta fraction of V, the average distance of S to their best theta*k points in R should not be more than a factor gamma compared to their average distance to the best theta*k points among all of C. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size. Since there are instances for which - unless gamma is polynomially large - no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set R of size k as though its size were only k/alpha, for alpha > 1. Furthermore, motivated by the application to elections, we mostly focus on the "ordinal" model, where the algorithm does not learn the actual distances; instead, it learns only for each point v in V and each candidate pairs c, c' which of c, c' is closer to v. Our main result is that the Expanding Approvals Rule (EAR) of Aziz and Lee is (alpha, gamma) representative with gamma <= 1 + 6.71 * (alpha)/(alpha-1). Our results lead to three notable byproducts. First, we show that the EAR achieves constant proportional fairness in the ordinal model, giving the first positive result on metric proportional fairness with ordinal information. Second, we show that for the core fairness objective, the EAR achieves the same asymptotic tradeoff between resource augmentation and approximation as the recent results of Li et al., which used full knowledge of the metric. Finally, our results imply a very simple single-winner voting rule with metric distortion at most 44.
• Abstract（参考訳）: 我々は、計量空間内のより大きな集合の「表現可能」である k 点の小さな集合 r に対する新しい定義を導入する。 Given a set V (e.g., documents or voters) to represent, and a set C of possible representatives, our criterion requires that for any subset S comprising a theta fraction of V, the average distance of S to their best theta*k points in R should not be more than a factor gamma compared to their average distance to the best theta*k points among all of C. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size. ガンマが多項式的に大きければ、解は存在しないので、この概念を資源増強フレームワークで研究し、k の集合 R に対する制約を、α > 1 の場合、そのサイズが k/alpha であるかのように暗黙的に記述する。 アルゴリズムは V の各点 v に対してのみ学習し、c, c' の各候補対 c, c' は v に近づき、Aziz と Lee の expanding Approvals Rule (EAR) は gamma <= 1 + 6.71 * (alpha)/(alpha-1) で表される。 私たちの結果は3つの顕著な副産物をもたらす。 まず、 EAR は順序性モデルにおいて一定の比例フェアネスを達成し、順序性情報を用いた計量比例フェアネスの最初の正の値を与える。 第二に, コアフェアネスの目標として, 資源増強と近似の漸近的トレードオフを, li 等が測定値の知識を十分に活用した最近の結果と同等に達成していることを示す。 最後に, 測定値の歪みが最大44。

関連論文リスト

• Effective resistance in metric spaces [65.94598202303497]
  有効抵抗(ER)はグラフの構造を問う魅力的な方法である。 サンプルのサイズが無限大になるにつれて、任意の2点間のERが自明な量に収束することを示す。 領域を固定し続けることにより、点数が無限大になるにつれて、領域ベースのERが非自明な極限に収束することを示す。
  論文  参考訳（メタデータ） (2023-06-27T17:43:18Z)
• A Hypervolume Based Approach to Rank Intuitionistic Fuzzy Sets and Its Extension to Multi-criteria Decision Making Under Uncertainty [0.0]
  距離に基づくランク付け手法による直観的ファジィ集合のランク付けには、直観的ファジィ集合と基準点の間の距離を計算する必要がある。 本稿では、この仮定が非線形距離関数のいずれかに有効でない理由を数学的に証明する。 距離に基づくランキングの代替として、ハイパーボリュームベースのランキングアプローチを提案する。
  論文  参考訳（メタデータ） (2022-12-25T11:57:04Z)
• Convergence of Random Reshuffling Under The Kurdyka-{\L}ojasiewicz Inequality [3.960041987749073]
  我々はクルディカ・ロジャシエヴィチ(KL)の不等式に基づくステップサイズを小さくした非輝化RRの収束解析を行う。 我々は、KL指数と好適に選択された減少ステップサイズに応じて、対応する収束率を導出する。 また、近位点法に対して同様の強い極限点収束結果を確立する。
  論文  参考訳（メタデータ） (2021-10-10T23:20:04Z)
• A PAC-Bayesian Analysis of Distance-Based Classifiers: Why Nearest-Neighbour works! [12.317405551932195]
  K-nearest-neighbour分類器(K-NN)の一般化誤差に対するPAC-Bayesian境界 我々は、カーネル展開における係数に関する事前測度と、カーネル空間における重みベクトルに関する誘導測度との関係を確立する。
  論文  参考訳（メタデータ） (2021-09-28T17:35:57Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。 アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
  論文  参考訳（メタデータ） (2021-06-04T16:37:19Z)
• Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples [12.77426855794452]
  本稿では,より一般的な設定下でのGOT距離を推定するための収束保証を提供する。 我々の分析における重要なステップは、GOT距離がカーネルの最大誤差距離の族に支配されていることを示すことである。
  論文  参考訳（メタデータ） (2021-02-28T04:30:23Z)
• Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM [15.251738476719918]
  パラメータを既知の重みのK成分を用いたガウス混合モデルとして推定する問題を考察する。 本稿では, EM と勾配 EM の局所収束について, 従来の研究と比較し, より鮮明な解析を行った。 第2のコントリビューションは,EMと勾配EMによる精度評価のための試料サイズ要件の改善である。
  論文  参考訳（メタデータ） (2021-01-03T08:10:01Z)
• Rethink Maximum Mean Discrepancy for Domain Adaptation [77.2560592127872]
  本論文は,(1)最大平均距離の最小化は,それぞれソースとクラス内距離の最大化に等しいが,その差を暗黙の重みと共同で最小化し,特徴判別性は低下する,という2つの本質的な事実を理論的に証明する。 いくつかのベンチマークデータセットの実験は、理論的な結果の有効性を証明しただけでなく、我々のアプローチが比較した最先端手法よりも大幅に向上できることを実証した。
  論文  参考訳（メタデータ） (2020-07-01T18:25:10Z)
• Fractional norms and quasinorms do not help to overcome the curse of dimensionality [62.997667081978825]
  マンハッタンの距離や分数的な準位数 lp は、分類問題における次元性の呪いを克服するのに役立ちます。 系統的な比較では、p=2, 1, 0.5 の lp に基づく kNN の性能の違いは統計的に重要でないことが示されている。
  論文  参考訳（メタデータ） (2020-04-29T14:30:12Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。 我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。 RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
  論文  参考訳（メタデータ） (2020-02-21T00:43:06Z)

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

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