Fugu-MT 論文翻訳(概要): Complexity of Differentially Private Selection via Federated APIs

論文の概要: Complexity of Differentially Private Selection via Federated APIs

arxiv url: http://arxiv.org/abs/2610.38789v1
Date: Wed, 28 Oct 2026 19:56:53 GMT
ステータス: 翻訳完了
システム内更新日: 2026-11-03 08:37:20.739333
Title: Complexity of Differentially Private Selection via Federated APIs
Title（参考訳）: フェデレーションAPIによる個人別選択の複雑さ
Abstract要約: Sparse Vector Technique (SVT) のバージョンを実装した新しいプリミティブを導入する。我々は、SVTクエリのほぼ最適数$O(dlog*d)$でこれを行うことができることを示す。本稿では,F_p$損失,重み付き同定,スパース平均推定などの多様なタスクに対するモデルの適用性を示す。
参考スコア（独自算出の注目度）: 56.34461735425814
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Differential privacy (DP) has become the standard for privacy-preserving data analysis, yet its practical implementation in federated or distributed settings often faces a significant utility gap compared to the central model. While existing frameworks, including local, shuffle, and secure aggregation models, offer vetted primitives, they can incur high error for important tasks such as selection. Our first contribution is to show that this is inherent in the aggregation model: any private selection algorithm relying on the standard noisy aggregation primitive requires $Ω(\sqrt{d}/\varepsilon)$ samples. To address this limitation, we propose adding a new primitive that implements a version of the Sparse Vector Technique (SVT) and argue that it has simple implementations under various trust models. We demonstrate its power by developing an $\varepsilon$-differentially private algorithm for the selection problem. For selection in dimension $d$, our algorithm achieves an additive error of $O\left(\frac{\log(dn)}{\varepsilon}\right)$, matching that of the central model when $n$ is polynomially bounded in $d$. Furthermore, we show that this can be done using a near-optimal expected number $O(d\log^*d)$ of SVT queries. Together with existing lower bounds for the shuffle model, this result establishes an exponential separation between the SVT model and shuffle or aggregation-based models. We demonstrate the model's broad applicability to diverse tasks such as $F_p$ loss minimization, heavy-hitter identification, and sparse mean estimation.
Abstract（参考訳）: 差別化プライバシ(DP)は、プライバシを保存するデータ分析の標準となっているが、フェデレーションや分散設定における実践的な実装は、中央モデルと比較して大きなユーティリティギャップに直面していることが多い。ローカル、シャッフル、セキュアアグリゲーションモデルを含む既存のフレームワークは、精査されたプリミティブを提供するが、選択のような重要なタスクに対して高いエラーを発生させることができる。標準ノイズアグリゲーションプリミティブに依存する任意のプライベート選択アルゴリズムは、$Ω(\sqrt{d}/\varepsilon)$サンプルを必要とする。この制限に対処するため,Sparse Vector Technique (SVT) のバージョンを実装した新しいプリミティブを提案する。我々は、選択問題に対する$\varepsilon$-differentially privateアルゴリズムを開発することで、その能力を実証する。次元$d$の選択に対して、我々のアルゴリズムは$O\left(\frac{\log(dn)}{\varepsilon}\right)$という加算誤差を達成し、$n$が$d$で多項式的に有界であるときの中心モデルの値と一致する。さらに、これはSVTクエリのほぼ最適数$O(d\log^*d)$で実現できることを示す。シャッフルモデルに対する既存の下界と共に、この結果はSVTモデルとシャッフルモデルまたはアグリゲーションベースモデルとの指数的分離を確立する。 F_p$損失最小化,重ヒッタ同定,スパース平均推定など,多種多様なタスクに対するモデルの適用性を示す。

関連論文リスト

Storage capacity of perceptron with variable selection [10.64866985260943]
機械学習における中心的な課題は、高次元データにおける真の構造と確率相関を区別することである。単純なパーセプトロンは$N$変数から$M = N$変数を最適に選択することで、$P = N$ランダムパターンを完全に分類できることを示す。これは、データの真の構造と急激な正規性とを区別するための定量的な基準を提供するだけでなく、連想記憶モデルの記憶能力ももたらします。
論文参考訳（メタデータ） (2025-12-01T16:44:57Z)
DISCO: Diversifying Sample Condensation for Efficient Model Evaluation [59.01400190971061]
コスト評価は傾向を低下させ、イノベーションのサイクルを遅くし、環境への影響を悪化させる。モデル応答の多様性を最大化するサンプルを選択することが重要となる。我々のメソッドである$textbfDiversifying Sample Condensation (DISCO)$は、最も大きなモデル不一致を持つトップkサンプルを選択します。
論文参考訳（メタデータ） (2025-10-09T08:53:59Z)
FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [68.44043212834204]
Low-Rank Adaptation (LoRA) は、学習における言語モデルの効率的な微調整に広く用いられている。 Low-Rank Adaptation (LoRA) は、学習における言語モデルの効率的な微調整に広く用いられている。
論文参考訳（メタデータ） (2025-05-19T07:32:56Z)
Lightweight Protocols for Distributed Private Quantile Estimation [12.586899971090277]
我々は、各ユーザが1つのデータポイントを1つのドメインに[B]$で保持するときに、1つの量子を推定する2つの強調適応アルゴリズムを考察する。適応的な設定では、$varepsilon$-LDPアルゴリズムを用い、$O(fraclog Bvarepsilon2alpha2)$ユーザしか必要としないエラー$alpha$内の量子化を推定できる。
論文参考訳（メタデータ） (2025-02-05T08:39:02Z)
Triangle Counting with Local Edge Differential Privacy [3.071866762675526]
エッジ差分プライバシーを持つ局所モデルにおける三角形計数について検討する。本研究では,非対話的モデルと対話的モデルの両方について検討する。我々の研究は局所モデルにおける微分プライベートグラフ解析における技術の現状を著しく改善する。
論文参考訳（メタデータ） (2023-05-03T16:50:29Z)
ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits [9.333087475006003]
ProtoBanditは、ソースデータセットから情報的データインスタンスのコンパクトなセットを特定するための、マルチアームのBanditベースのフレームワークである。提案アルゴリズムは,数桁の類似性計算コール数(100～1000倍)を削減し,最先端手法と同等の解を求める。
論文参考訳（メタデータ） (2022-10-04T19:03:47Z)
Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文参考訳（メタデータ） (2022-08-11T04:12:50Z)
Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
論文参考訳（メタデータ） (2021-11-08T18:05:35Z)
Improving Robustness and Generality of NLP Models Using Disentangled Representations [62.08794500431367]
スーパービジョンニューラルネットワークはまず入力$x$を単一の表現$z$にマップし、次に出力ラベル$y$にマッピングする。本研究では,非交叉表現学習の観点から,NLPモデルの堅牢性と汎用性を改善する手法を提案する。提案した基準でトレーニングしたモデルは、広範囲の教師付き学習タスクにおいて、より堅牢性とドメイン適応性を向上することを示す。
論文参考訳（メタデータ） (2020-09-21T02:48:46Z)
The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation [3.2942333712377083]
種々の高次元学習および推定問題に対して,シャッフルモデルとパンプライベートモデルでは,中央モデルと比較してサンプルの複雑さが指数関数的に高くなることを示す。我々の研究は、パンプライベートモデルと一般的なマルチメッセージシャッフルモデルの両方に対して、これらの問題に対する最初の非自明な下界を与える。
論文参考訳（メタデータ） (2020-09-17T01:15:55Z)

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

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