論文の概要: Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

• arxiv url: http://arxiv.org/abs/2607.20418v1
• Date: Wed, 22 Jul 2026 17:54:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-23 18:51:38.173305
• Title: Pure-DP Statistical Query Release at the Conjectured Square-Root Rate
• Title（参考訳）: 導出方形ルートレートにおけるPure-DP統計クエリのリリース
• Abstract要約: Nikolov と Ullman は、T の宇宙上の k 個の統計クエリは、既知の下界によって示唆される平方根率で最悪の座標誤差を期待して、純粋な微分プライバシーの下で解放できるかどうかを尋ねた。 我々はそれらの予想上界を証明した。 コンパニオンのLean 4開発マシンは、有限構造、決定論的デコーディング後の純粋なプライバシ、表示されたすべての登録値の上限をチェックする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nikolov and Ullman asked whether k statistical queries on a universe of size T can be released under pure differential privacy with expected worst-coordinate error at the square-root rate suggested by known lower bounds. We prove their conjectured upper bound. For every database size n and privacy parameter $\varepsilon>0$, there is an $\varepsilon$-differentially private mechanism with expected error $O(\min\{1,\sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$. This matches the lower-bound dependence in the standard high-dimensional regimes where those bounds apply; the shifted logarithms and outer minimum make the upper bound valid without additional parameter assumptions. The construction starts from a selection-only private multiplicative weights transcript, then replaces its probability mass function by a distance-penalized likelihood envelope. To prove that the modification preserves accuracy, a likelihood-level Maurey argument upper-bounds each Hamming-ball maximum by a small family of auxiliary PMW laws. Renyi moment bounds control nearby balls, a direct mixture bound controls distant balls, and grouping radii at the privacy scale prevents an additional $1/\varepsilon$ factor in the error. The mechanism is information-theoretic. A companion Lean 4 development machine-checks the finite construction, pure privacy after deterministic decoding, and the displayed all-regimes upper bound.
• Abstract（参考訳）: Nikolov と Ullman は、T の宇宙上の k 個の統計クエリは、既知の下界によって示唆される平方根率で最悪の座標誤差を期待して、純粋な微分プライバシーの下で解放できるかどうかを尋ねた。 我々はそれらの予想上界を証明した。 すべてのデータベースサイズ n とプライバシパラメータ $\varepsilon>0$ に対して、期待されるエラー $O(\min\{1,\sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$ を持つ $\varepsilon$-differentially private メカニズムが存在する。 これは、これらの境界が適用される標準の高次元レギュレーションにおける下界依存と一致し、シフト対数と外限は、追加のパラメータ仮定なしで上界が有効となる。 この構成は、選択のみのプライベート乗法重みの転写から始まり、その確率質量関数を距離に制限された確率エンベロープで置き換える。 この修正が正確性を保つことを証明するために、確率レベルMaurey引数は、補助的なPMW法則の小さな族によって各ハミングボール最大値を上界する。 Renyiのモーメントは近くの球を制御し、直接の混合は遠くの球を制御し、プライバシーの尺度でラジイをグループ化すると、エラーの1/\varepsilon$要素がさらに増える。 そのメカニズムは情報理論である。 コンパニオンのLean 4開発マシンは、有限構造、決定論的デコーディング後の純粋なプライバシ、表示されたすべての登録値の上限をチェックする。

関連論文リスト

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy [38.10483249859454]
  最小限のリスクと後悔は期待に基づく基準であり、稀だが連続的な失敗を捉えない。 対話型統計的意思決定のための$$$-explicit minimax-quantile理論を開発した。
  論文  参考訳（メタデータ） (2026-06-22T09:41:48Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。 予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
  論文  参考訳（メタデータ） (2025-11-17T23:58:11Z)
• Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
  プライバシー制約の下では、プライベート線形回帰の複雑さは通常の共分散行列によって捉えられる。 最適率を達成するための情報重み付け回帰手法を提案する。 特に、我々の結果は、共同プライバシーは追加費用がほとんどないことを示している。
  論文  参考訳（メタデータ） (2025-02-18T18:35:24Z)
• On Differentially Private U Statistics [25.683071759227293]
  局所的なH'ajekプロジェクションを用いて、データの異なる部分集合を再重み付けする新しいしきい値に基づくアプローチを提案する。 これは、非退化U統計に対してほぼ最適なプライベート誤差をもたらし、退化U統計に対してほぼ最適であることを示す強い指標となる。
  論文  参考訳（メタデータ） (2024-07-06T03:27:14Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。 誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
  論文  参考訳（メタデータ） (2024-01-17T09:23:25Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Contraction of Locally Differentially Private Mechanisms [8.547801169402923]
  我々は、$PK$と$QK$の出力分布が$epsilon$-LDPメカニズムの$K$のばらつきに基づいて、厳密な境界を導出する。 次に、これらの境界を利用して、バンツリーの不等式、ル・カム、アスード、および相互情報手法の局所的プライベートバージョンを確立する。
  論文  参考訳（メタデータ） (2022-10-24T16:38:12Z)
• 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)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Robust Estimation of Discrete Distributions under Local Differential Privacy [1.52292571922932]
  局所的な差分プライバシー制約の下で,n$の汚染データバッチから離散分布を推定する問題を考察する。 2つの制約を組み合わせることで、$epsilonsqrtd/alpha2 k+sqrtd2/alpha2 kn$を$sqrtlog (1/epsilon)$ factorに設定できる。
  論文  参考訳（メタデータ） (2022-02-14T15:59:02Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)

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

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