論文の概要: Private Frequency Estimation Via Residue Number Systems

• arxiv url: http://arxiv.org/abs/2511.11569v2
• Date: Mon, 17 Nov 2025 10:42:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:22.689026
• Title: Private Frequency Estimation Via Residue Number Systems
• Title（参考訳）: 残数システムによるプライベート周波数推定
• Authors: Héber H. Arcolezi,
• Abstract要約: 本報告では,ローカル・ディファレンシャル・プライベート(LDP)周波数推定のための新しいアルゴリズムであるtextsfModularSubsetSelection (MSS) を提案する。 私たちの$varepsilon$-LDPメカニズムは、サイズが$k$と$n$のユーザに与えられたら、それぞれの入力をResidue Number System (RNS)経由で$ell$ペアワイズ・コプライム・モジュリでエンコードします。 MSS は評価された全ての LDP プロトコルの中で最小の再構成攻撃成功率を達成する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present \textsf{ModularSubsetSelection} (MSS), a new algorithm for locally differentially private (LDP) frequency estimation. Given a universe of size $k$ and $n$ users, our $\varepsilon$-LDP mechanism encodes each input via a Residue Number System (RNS) over $\ell$ pairwise-coprime moduli $m_0, \ldots, m_{\ell-1}$, and reports a randomly chosen index $j \in [\ell]$ along with the perturbed residue using the statistically optimal \textsf{SubsetSelection} (SS) (Wang et al. 2016). This design reduces the user communication cost from $Θ\bigl(ω\log_2(k/ω)\bigr)$ bits required by standard SS (with $ω\approx k/(e^\varepsilon+1)$) down to $\lceil \log_2 \ell \rceil + \lceil \log_2 m_j \rceil$ bits, where $m_j < k$. Server-side decoding runs in $Θ(n + r k \ell)$ time, where $r$ is the number of LSMR (Fong and Saunders 2011) iterations. In practice, with well-conditioned moduli (\textit{i.e.}, constant $r$ and $\ell = Θ(\log k)$), this becomes $Θ(n + k \log k)$. We prove that MSS achieves worst-case MSE within a constant factor of state-of-the-art protocols such as SS and \textsf{ProjectiveGeometryResponse} (PGR) (Feldman et al. 2022) while avoiding the algebraic prerequisites and dynamic-programming decoder required by PGR. Empirically, MSS matches the estimation accuracy of SS, PGR, and \textsf{RAPPOR} (Erlingsson, Pihur, and Korolova 2014) across realistic $(k, \varepsilon)$ settings, while offering faster decoding than PGR and shorter user messages than SS. Lastly, by sampling from multiple moduli and reporting only a single perturbed residue, MSS achieves the lowest reconstruction-attack success rate among all evaluated LDP protocols.
• Abstract（参考訳）: そこで本研究では,局所微分プライベート(LDP)周波数推定のための新しいアルゴリズムである<textsf{ModularSubsetSelection} (MSS)を提案する。 私たちの$\varepsilon$-LDPメカニズムは、サイズが$k$と$n$の宇宙が与えられた場合、それぞれの入力をResidue Number System (RNS) over $\ell$ pairwise-coprime moduli $m_0, \ldots, m_{\ell-1}$でエンコードし、統計的に最適である \textsf{SubsetSelection} (SS) (Wang et al 2016) を用いて、ランダムに選択されたインデックス $j \in [\ell]$と摂動残余を報告します。 この設計により、ユーザ通信コストは、標準SSで要求される$$\bigl(ω\log_2(k/ω)\bigr)$ bits($ω\approx k/(e^\varepsilon+1)$)から$\lceil \log_2 \ell \rceil + \lceil \log_2 m_j \rceil$ bits($m_j < k$)に削減される。 サーバサイドのデコーディングは、$(n + r k \ell)$ timeで実行され、$r$はLSMR(Fong and Saunders 2011)のイテレーションの数である。 実際には、よく条件付きモジュライ (\textit{i.e.}) で、定数 $r$ と $\ell = >(\log k)$ とすると、これは$(n + k \log k)$ となる。 SS や \textsf{ProjectiveGeometryResponse} (PGR) (Feldman et al 2022) のような最先端のプロトコルでは,PGR が必要とする代数的前提条件や動的プログラミングデコーダを回避しつつ,最悪の MSE を実現していることを示す。 経験的に、MSSはSS, PGR, \textsf{RAPPOR} (Erlingsson, Pihur, Korolova 2014)の推定精度を現実的な$(k, \varepsilon)$設定と一致させ、PGRよりも高速なデコーディングとSSよりも短いユーザーメッセージを提供する。 最後に、複数のモジュールからサンプリングし、単一の摂動残差のみを報告することにより、評価された全てのLDPプロトコルの中で、MSSは最小の再構成攻撃成功率を達成する。

関連論文リスト

• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$ [0.0]
  我々は、$ell_p$ norm(mathsfSVP_p$)およびUnique-SVP(mathsfuSVP_p$)における最短ベクトル問題に対する近似結果の決定的困難性を確立する。 すべての$p > 2$に対して、定数比硬さを証明します: no-time algorithm almosts $mathsfSVP_p$ or $mathsfuSVP_p$ in a ratio of $sqrt2 - o(1)$。
  論文  参考訳（メタデータ） (2025-10-19T20:17:26Z)
• Sandwich test for Quantum Phase Estimation [0.0]
  量子位相推定(QPE)は多くの実用的な応用を通じて科学的革命の可能性を秘めている。 多くのQPEアルゴリズムは、大きな整数$k$に対して$langle psi|Uk|psirangle$を推定するためにHadamardテストを使用する。 本稿では,このボトルネックに対処する新しいアルゴリズムであるSANDWICHを提案する。
  論文  参考訳（メタデータ） (2025-07-31T16:45:07Z)
• Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning [2.2984209387877628]
  無限水平平均逆強化学習(RL)におけるリプシッツ MDP について検討した。 for $d_texteff. = dPhi_z+2$ for model-free algorithmtextitPZRL-MF and $d_texteff. = 2d_mathcalS + dPhi_z + 3$ for
  論文  参考訳（メタデータ） (2024-05-29T06:18:09Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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