Fugu-MT 論文翻訳(概要): Federated Aggregation of Mallows Rankings: A Comparative Analysis of Borda and Lehmer Coding

論文の概要: Federated Aggregation of Mallows Rankings: A Comparative Analysis of Borda and Lehmer Coding

arxiv url: http://arxiv.org/abs/2409.00848v1
Date: Sun, 1 Sep 2024 21:36:09 GMT
ステータス: 処理完了
システム内更新日: 2024-09-06 08:51:29.876346
Title: Federated Aggregation of Mallows Rankings: A Comparative Analysis of Borda and Lehmer Coding
Title（参考訳）: マロランキングのフェデレーションアグリゲーション:ボルダとレーマーの符号化の比較分析
Authors: Jin Sima, Vishal Rana, Olgica Milenkovic,
Abstract要約: ボルダのスコアリングとレーマー符号を用いた最初の連邦ランクアグリゲーション法を提案する。この結果は,Mallowsモデルの下での集中的および分散的設定におけるボルダ法の最初の厳密な解析である。
参考スコア（独自算出の注目度）: 27.138031759281745
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Rank aggregation combines multiple ranked lists into a consensus ranking. In fields like biomedical data sharing, rankings may be distributed and require privacy. This motivates the need for federated rank aggregation protocols, which support distributed, private, and communication-efficient learning across multiple clients with local data. We present the first known federated rank aggregation methods using Borda scoring and Lehmer codes, focusing on the sample complexity for federated algorithms on Mallows distributions with a known scaling factor $\phi$ and an unknown centroid permutation $\sigma_0$. Federated Borda approach involves local client scoring, nontrivial quantization, and privacy-preserving protocols. We show that for $\phi \in [0,1)$, and arbitrary $\sigma_0$ of length $N$, it suffices for each of the $L$ clients to locally aggregate $\max\{C_1(\phi), C_2(\phi)\frac{1}{L}\log \frac{N}{\delta}\}$ rankings, where $C_1(\phi)$ and $C_2(\phi)$ are constants, quantize the result, and send it to the server who can then recover $\sigma_0$ with probability $\geq 1-\delta$. Communication complexity scales as $NL \log N$. Our results represent the first rigorous analysis of Borda's method in centralized and distributed settings under the Mallows model. Federated Lehmer coding approach creates a local Lehmer code for each client, using a coordinate-majority aggregation approach with specialized quantization methods for efficiency and privacy. We show that for $\phi+\phi^2<1+\phi^N$, and arbitrary $\sigma_0$ of length $N$, it suffices for each of the $L$ clients to locally aggregate $\max\{C_3(\phi), C_4(\phi)\frac{1}{L}\log \frac{N}{\delta}\}$ rankings, where $C_3(\phi)$ and $C_4(\phi)$ are constants. Clients send truncated Lehmer coordinate histograms to the server, which can recover $\sigma_0$ with probability $\geq 1-\delta$. Communication complexity is $\sim O(N\log NL\log L)$.
Abstract（参考訳）: ランキングアグリゲーションは、複数のランクリストをコンセンサスランキングにまとめる。バイオメディカルなデータ共有のような分野では、ランキングは分散され、プライバシーが要求される。これにより、複数のクライアントにまたがる分散、プライベート、および通信効率の学習をサポートするフェデレートされたランク集約プロトコルの必要性が高まっている。本稿では,BordaスコアリングとLehmer符号を用いて,既知のスケーリング係数$\phi$と未知のセントロイド置換$\sigma_0$を用いて,Mallows分布上でのフェデレーションアルゴリズムのサンプル複雑性に着目した最初のフェデレーションランクアグリゲーション手法を提案する。フェデレートされたボルダのアプローチには、ローカルクライアントスコアリング、非自明な量子化、プライバシ保護プロトコルが含まれる。例えば$\phi \in [0,1)$と$\sigma_0$ of length $N$の場合、$L$クライアントのそれぞれに対して、ローカルに集約する$\max\{C_1(\phi), C_2(\phi)\frac{1}{L}\log \frac{N}{\delta}\}$ ranks, where $C_1(\phi)$と$C_2(\phi)$は定数であり、結果を量子化し、$\sigma_0$を$\geq 1-\delta$で回収できるサーバに送信する。通信複雑性は$NL \log N$とスケールする。この結果は,Mallowsモデルの下での集中的および分散的設定におけるボルダ法の最初の厳密な解析である。フェデレートされたLehmerコーディングアプローチは、効率とプライバシのための特殊な量子化メソッドを備えた座標長集約アプローチを使用して、各クライアント用のローカルなLehmerコードを生成する。我々は、$\phi+\phi^2<1+\phi^N$ および$\sigma_0$ of length $N$ に対して、$L$クライアントのそれぞれに局所的に $\max\{C_3(\phi), C_4(\phi)\frac{1}{L}\log \frac{N}{\delta}\} を足し、$C_3(\phi)$ と $C_4(\phi)$ を定数とする。クライアントはtruncated Lehmer座標ヒストグラムをサーバに送り、$\sigma_0$を確率$\geq 1-\delta$でリカバリすることができる。通信複雑性は$\sim O(N\log NL\log L)$である。

関連論文リスト

$\mathsf{OPA}$: One-shot Private Aggregation with Single Client Interaction and its Applications to Federated Learning [6.977111770337479]
一発のプライベートアグリゲーション(mathsfOPA$)を導入します。各クライアントはアグリゲーション毎に1回だけ通信するので、ドロップアウトの管理と動的参加が簡単になる。 $mathsfOPA$は実用的で、最先端のソリューションよりも優れています。
論文参考訳（メタデータ） (2024-10-29T17:50:11Z)
A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering [10.697784653113095]
すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイント数は、他のグループ$j in [ell]$のポイントの数のt倍でなければならない。私たちは、$ell=2$が一般的な均一容量$k$-medianに匹敵する難易度である場合にも、その問題を示します。
論文参考訳（メタデータ） (2024-05-16T18:17:44Z)
Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文参考訳（メタデータ） (2023-07-14T16:11:22Z)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。本稿では,この数値をほぼ最適に推定する手法を提案する。
論文参考訳（メタデータ） (2022-02-15T03:49:28Z)
Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
論文参考訳（メタデータ） (2021-11-08T20:18:10Z)
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)
FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning [21.055643409860743]
Averaging(FedAvg、またはLocal-SGD)は、クライアントが複数のローカルSGDステップを実行して、アップデートをオーケストレーションサーバに通信する、古典的なフェデレーション学習である。本稿では,新しいフェデレーション学習アルゴリズムであるFedAvgを提案する。
論文参考訳（メタデータ） (2021-08-10T15:41:27Z)
Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文参考訳（メタデータ） (2021-07-22T14:25:16Z)
Federated Bandit: A Gossiping Approach [22.595542913855624]
我々は、分散化されたマルチアーマッド・バンドイット問題であるemphFederated Banditを、$N$エージェントのセットで研究し、接続グラフ$G$で記述された隣人とのみローカルデータを通信できる。 Gossip_UCBは、ローカルな帯域学習をグローバルなゴシッププロセスに適応させ、接続されたエージェント間で情報を共有し、$O(max textttpoly(N,M) log T, textttpoly(N,M) log_lambda-1の順序で後悔を保証できることを示す。
論文参考訳（メタデータ） (2020-10-24T03:44:25Z)
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)

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

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