論文の概要: Improved Differentially Private Algorithms for Rank Aggregation

• arxiv url: http://arxiv.org/abs/2511.11319v1
• Date: Fri, 14 Nov 2025 13:58:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-17 22:42:18.641395
• Title: Improved Differentially Private Algorithms for Rank Aggregation
• Title（参考訳）: ランクアグリゲーションのための微分プライベートアルゴリズムの改良
• Authors: Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn, Phanu Vajanopath,
• Abstract要約: ケメニー階数集計問題に対して,改良されたPTASと5$-approximationアルゴリズムを提案する。 我々はまず,足位集計問題について検討する。
• 参考スコア（独自算出の注目度）: 20.175634288058166
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Rank aggregation is a task of combining the rankings of items from multiple users into a single ranking that best represents the users' rankings. Alabi et al. (AAAI'22) presents differentially-private (DP) polynomial-time approximation schemes (PTASes) and $5$-approximation algorithms with certain additive errors for the Kemeny rank aggregation problem in both central and local models. In this paper, we present improved DP PTASes with smaller additive error in the central model. Furthermore, we are first to study the footrule rank aggregation problem under DP. We give a near-optimal algorithm for this problem; as a corollary, this leads to 2-approximation algorithms with the same additive error as the $5$-approximation algorithms of Alabi et al. for the Kemeny rank aggregation problem in both central and local models.
• Abstract（参考訳）: ランキングアグリゲーション(英語: Rank aggregate)とは、複数のユーザーからのアイテムのランキングを、ユーザのランキングを最もよく表す1つのランキングにまとめるタスクである。 Alabi et al (AAAI'22) は、中央モデルと局所モデルの両方においてケメニー階数集計問題に対して、ある加算誤差を持つ微分プライベート (DP) 多項式時間近似スキーム (PTAS) と 5$-近似アルゴリズムを提示する。 本稿では,中心モデルにおける加算誤差を小さくした改良DP PTASを提案する。 さらに,本研究ではまず,DP下でのフットルルランキングの集計問題について検討する。 この問題に対する近似アルゴリズムは概ね最適であり、このアルゴリズムは中心モデルと局所モデルの両方におけるケメニー階数集計問題に対してアラビらの5ドル近似アルゴリズムと同じ加算誤差の2-近似アルゴリズムをもたらす。

関連論文リスト

• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• Improved theoretical guarantee for rank aggregation via spectral method [1.0152838128195467]
  複数の項目間のペアワイズ比較を与えられた場合、ランキングが観測値と一致するようにランク付けする方法? ランクアグリゲーションとして知られるこの問題は、スポーツ、レコメンデーションシステム、その他のウェブアプリケーションに多くの応用を見出している。 ここで、各ペア比較は真のスコア差の破損したコピーである。
  論文  参考訳（メタデータ） (2023-09-07T16:01:47Z)
• Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
  本稿では,二部類ランキングにおける公平性を実現するためのモデルに依存しない後処理フレームワークxOrderを提案する。 xOrderは、教師なしおよび教師なしの公正度メトリックを含む、さまざまな分類モデルとランキングフェアネスメトリクスと互換性がある。 提案アルゴリズムを,4つのベンチマークデータセットと2つの実世界の患者電子健康記録リポジトリ上で評価した。
  論文  参考訳（メタデータ） (2023-07-27T07:42:44Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits [16.038995442397972]
  この問題はN$エージェントによって同時に解決され、M$の共通の武器のセットに直面し、同じ武器の報酬分布を共有すると仮定される。 非方向性グラフに対して2つの完全分散上信頼境界(UCB)アルゴリズムを提案する。 提案されたUCB1およびKL-UCBアルゴリズムにより、ネットワーク内の各エージェントは、シングルエージェントよりも対数的後悔をより良く達成できる。
  論文  参考訳（メタデータ） (2021-11-22T01:05:52Z)
• Optimal Full Ranking from Pairwise Comparisons [16.852801934478475]
  ランキングの最小最大レートは、問題の信号対雑音比の大きさに応じて指数レートと率の間の遷移を示す。 ミニマックスレートを達成するために,まず,n$ プレーヤーを類似したスキルのグループに分割し,次に各グループ内のローカル mle を計算する分割・コンクエストランキングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-21T03:34:44Z)
• Concentric mixtures of Mallows models for top-$k$ rankings: sampling and identifiability [0.0]
  上位ランクの2つのMallowsモデルの混合について検討する。 我々はMallows Top-k$ランキングの効率的なサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-27T13:00:37Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)

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

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