論文の概要: Better Privacy Guarantees for Larger Groups

• arxiv url: http://arxiv.org/abs/2607.14406v1
• Date: Wed, 15 Jul 2026 22:44:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-17 17:01:32.930568
• Title: Better Privacy Guarantees for Larger Groups
• Title（参考訳）: 大規模グループのためのより良いプライバシ保証
• Abstract要約: プジョールとデフォンテーヌは、私的なヒストグラムがより大きな数の誤りをより多く許容するかどうかを尋ね、より大きなグループのメンバをより強く保護するためにそのスラックを使用する。 本稿では, 付加的あるいは削除的隣接の下での固定的解離群について検討する。 プライバシ予算の$v(n)$は、影響を受けるカウントに依存し、増加せず、あらゆる順序でレニイ分割の方向を拘束しなければならない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Pujol and Desfontaines asked whether a private histogram can allow more error on larger counts and use that slack to protect members of larger groups more strongly. We study this question for fixed disjoint groups under add-or-remove-one adjacency. The privacy budget $v(n)$ depends on the affected count, is nonincreasing, and must bound both Rényi-divergence directions at every order. This is the count-dependent form of zero-concentrated differential privacy (zCDP) studied here. The original strict relative-error condition is impossible at count zero. We therefore make the boundary tolerance explicit by requiring $\mathbb{E}\lvert\widehat{x}_i-x_i\rvert < r\max\{x_i,1\}$, without changing the requirement at any positive count. Our main result determines the best dependence on group size. For the upper bound, we directly specialize an existing shifted-transformation framework. The resulting shifted-log Gaussian mechanism has a certified budget $v(n)=O_r(n^{-2})$. Conversely, for every fixed $0<r<1$, any mechanism satisfying the same positive-count utility requirement and count-dependent zCDP must have $v(n)=Ω_r(n^{-2})$. Thus the inverse-square rate is optimal under the repaired formulation. A many-count information argument further places the leading coefficient in the large-count-then-small-error limit between $π/(4e^2)$ and $1/π$, a factor below three. At $r=1$, a data-independent release meets the repaired criterion with zero privacy loss.
• Abstract（参考訳）: プジョールとデフォンテーヌは、私的なヒストグラムがより大きな数の誤りをより多く許容するかどうかを尋ね、より大きなグループのメンバをより強く保護するためにそのスラックを使用する。 本稿では, 付加的あるいは削除的隣接の下での固定的解離群について検討する。 プライバシ予算の$v(n)$は、影響を受けるカウントに依存し、増加せず、あらゆる順序でレニイ分割の方向を拘束しなければならない。 これはゼロ集中微分プライバシー(zCDP)のカウント依存型である。 元の厳密な相対エラー条件はゼロ数では不可能である。 したがって、任意の正のカウントで要求を変更することなく、$\mathbb{E}\lvert\widehat{x}_i-x_i\rvert < r\max\{x_i,1\}$ で境界寛容を明示する。 我々の主な結果は、グループサイズへの最も依存度を決定する。 上界については、既存のシフトトランスフォーメーションフレームワークを直接専門化します。 結果として生じるシフトログのガウス機構は、認定された予算$v(n)=O_r(n^{-2})$を持つ。 逆に、すべての固定された$0<r<1$ に対して、同じ正の数の効用条件と数依存的な zCDP を満たす任意のメカニズムは、$v(n)=Ω_r(n^{-2})$ でなければならない。 したがって、逆二乗率は修復された定式化の下で最適である。 多数の情報議論により、大きな数列の小さな誤差の上限が$π/(4e^2)$から$/π$(3以下の因子)の間にある。 $r=1$で、データに依存しないリリースは、プライバシ損失ゼロの修正基準を満たす。

関連論文リスト

• A positive resolution of the gap-entropy conjecture [33.232618834192564]
  固定信頼度ベストアーム識別のためのギャップエントロピー予想を証明した。 各部分最適アーム $i$ に対して、$_i=_*-_i$ を最適平均とのギャップとする。 インスタンスに依存しないアルゴリズムがあり、期待されるサンプル数は、この量の定数倍数で制限される。
  論文  参考訳（メタデータ） (2026-09-09T17:57:11Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$を符号、空間性、正方性制限なしで証明する。 純粋な$varepsilon$-DP行列力学クラスでは、最適化された最大誤差と平均二乗誤差の両方が$(varepsilon-2log3(n+1))$である。
  論文  参考訳（メタデータ） (2026-07-30T14:41:34Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• Hidden-State Privacy Has an Empty Middle [51.56484100374058]
  すべてのフルランクガウス解放を$O(1)$ Fisher utility で表すと、マハラノビス信号が隠れた幅で直線的に成長する方向を認める。 スクラッチからトレーニングされたスプリットメモリトランスフォーマーは、[20, 33]$90MでG_mathrmMahに達し、固定言語損失ペナルティにおいて、30Mから1Bまでの同じ予算のGPTベースラインに対して6ドル～24ドルという優位性を維持する。
  論文  参考訳（メタデータ） (2026-05-21T20:12:09Z)
• On Purely Private Covariance Estimation [12.864472925970242]
  我々は、純粋な微分プライバシーの下で、$d$次元共分散行列を$Sigma$でリリースするための単純な摂動機構を示す。 少なくとも$ngeq d2/varepsilon$要素を持つ大規模なデータセットの場合、我々のメカニズムは、シテニコロフ2023の証明可能な最適のフロベニウス標準誤差を復元する。
  論文  参考訳（メタデータ） (2025-10-30T17:18:53Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。 Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
  論文  参考訳（メタデータ） (2024-09-25T01:30:16Z)
• Count on Your Elders: Laplace vs Gaussian Noise [9.546521474972485]
  多くの環境では、ラプラスノイズはガウスノイズよりも好まれるかもしれないと我々は主張する。 ガウス機構によって付加される雑音は、常に同値な分散のラプラスノイズに置き換えることができることを示す。 これはガウスノイズが高次元雑音に使用されるという従来の知恵に挑戦する。
  論文  参考訳（メタデータ） (2024-08-13T16:36:33Z)
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。 我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
  論文  参考訳（メタデータ） (2023-10-23T04:07:26Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma [10.176795938619417]
  統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。 フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
  論文  参考訳（メタデータ） (2022-05-17T17:55:10Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• A bounded-noise mechanism for differential privacy [3.9596068699962323]
  ベクトル $vecx(i) の平均 $frac1nsum_i=1n vecx(i)$ を [0,1]k$ で出力し、任意の $vecx(i)$ に対してプライバシーを保持します。 我々は、ほとんどの値$delta$に対して最適な$ell_infty$エラーを持つ$(epsilon,delta)$-privateメカニズムを示す。
  論文  参考訳（メタデータ） (2020-12-07T16:03:21Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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