論文の概要: Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries

• arxiv url: http://arxiv.org/abs/2512.21499v1
• Date: Thu, 25 Dec 2025 04:14:59 GMT
• ステータス: 情報取得中
• システム内更新日: 2025-12-29 11:53:03.757466
• Title: Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries
• Title（参考訳）: 重み付けされたフーリエ因子:異なるプライベートなマージナルおよび製品クエリのための最適ガウスノイズ
• Authors: Christian Janos Lebeda, Aleksandar Nikolov, Haohua Tang,
• Abstract要約: 差分プライバシー下での余分なクエリを付加(相関)ガウス雑音で解放する作業を再考する。 因子化機構である我々のアルゴリズムは、すべての因子化機構の中で正確に最適であることを示す。 提案手法は,数値属性のしきい値を用いた拡張限界クエリを製品クエリに組み込む方法を示す。
• 参考スコア（独自算出の注目度）: 43.692381991745755
• License:
• Abstract: We revisit the task of releasing marginal queries under differential privacy with additive (correlated) Gaussian noise. We first give a construction for answering arbitrary workloads of weighted marginal queries, over arbitrary domains. Our technique is based on releasing queries in the Fourier basis with independent noise with carefully calibrated variances, and reconstructing the marginal query answers using the inverse Fourier transform. We show that our algorithm, which is a factorization mechanism, is exactly optimal among all factorization mechanisms, both for minimizing the sum of weighted noise variances, and for minimizing the maximum noise variance. Unlike algorithms based on optimizing over all factorization mechanisms via semidefinite programming, our mechanism runs in time polynomial in the dataset and the output size. This construction recovers results of Xiao et al. [Neurips 2023] with a simpler algorithm and optimality proof, and a better running time. We then extend our approach to a generalization of marginals which we refer to as product queries. We show that our algorithm is still exactly optimal for this more general class of queries. Finally, we show how to embed extended marginal queries, which allow using a threshold predicate on numerical attributes, into product queries. We show that our mechanism is almost optimal among all factorization mechanisms for extended marginals, in the sense that it achieves the optimal (maximum or average) noise variance up to lower order terms.
• Abstract（参考訳）: 差分プライバシー下での余分なクエリを付加(相関)ガウス雑音で解放する作業を再考する。 まず、任意のドメインに対して、重み付けされた余分なクエリの任意のワークロードに答える構成を与える。 提案手法は, 独立雑音を用いたFourierベースでクエリを分離し, 分散を慎重に調整し, 逆フーリエ変換を用いて問合せ応答を復元する手法である。 重み付き雑音分散の和を最小化し,最大雑音分散を最小化するために,因子分解機構である本アルゴリズムは,すべての因子分解機構の中で正確に最適であることを示す。 半定値プログラミングによるすべての因子化機構の最適化に基づくアルゴリズムとは異なり、我々のメカニズムはデータセットの時間多項式と出力サイズで実行される。 この構成では,Xiao et al [Neurips 2023] の結果を,より単純なアルゴリズムと最適性証明,より優れた実行時間で回収する。 次に、我々のアプローチを製品クエリと呼ばれる限界の一般化に拡張する。 我々のアルゴリズムは、このより一般的なクエリーのクラスに対して、いまだに最適であることを示す。 最後に,拡張限界クエリを製品クエリに組み込む方法を示し,数値属性のしきい値の述語を製品クエリに組み込む。 このメカニズムは, 最適(最大または平均)ノイズ分散を低次項まで達成するという意味で, 拡張限界に対するすべての因子分解機構の中で, ほぼ最適であることを示す。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approach [18.009376840944284]
  本稿では,ヘッセン損失行列を効果的に正規化できるアルゴリズムを提案する。 提案手法は,CLIPとチェーン・オブ・ファインチューニングデータセットの事前学習における一般化の改善に有効である。
  論文  参考訳（メタデータ） (2023-06-14T14:58:36Z)
• Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage [24.40306100502023]
  我々は,雑音学習アルゴリズムのクラスにおける一般化挙動を解析するために,情報理論の枠組みを採用する。 更新関数の仮定が雑音の最適選択にどのように影響するかを示す。
  論文  参考訳（メタデータ） (2023-02-28T12:13:57Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  SGLDにおけるノイズ構造を操作することにより,情報理論の一般化を最適化する。 低経験的リスクを保証するために制約を課すことで、最適なノイズ共分散が期待される勾配共分散の平方根であることを証明する。
  論文  参考訳（メタデータ） (2021-10-26T15:02:27Z)
• Learning Numeric Optimal Differentially Private Truncated Additive Mechanisms [5.079561894598125]
  実効性境界が強い付加的なメカニズムに対して,トランクテッドノイズを学習するためのツールを提案する。 平均単調な単調な音から, 対称性やその新しい音を考慮すれば十分であることを示す。 感度境界機構については, 平均単調な単調なノイズから, 対称性とその新しさを考えるのに十分であることを示す。
  論文  参考訳（メタデータ） (2021-07-27T17:22:57Z)
• Proximal and Federated Random Reshuffling [11.83842808044211]
  ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。 ProxRR と FedRR は複合凸有限和最小化問題を解く。 ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
  論文  参考訳（メタデータ） (2021-02-12T18:59:24Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  少数のデータポイントで学習したガウス過程を訓練した空間定式化を提案する。 このアプローチはまた、より小さく、計算的にもより安価なサブソルバを低いバウンディングに導く。 提案手法の順序の順序による時間収束を,総じて低減する。
  論文  参考訳（メタデータ） (2020-05-21T20:59:11Z)

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

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