論文の概要: Minimax optimal differentially private synthetic data for smooth queries

• arxiv url: http://arxiv.org/abs/2602.01607v2
• Date: Thu, 05 Feb 2026 16:22:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 14:11:23.848991
• Title: Minimax optimal differentially private synthetic data for smooth queries
• Title（参考訳）: 滑らかな問合せのための最小最大微分プライベート合成データ
• Authors: Rundong Ding, Yiyun He, Yizhe Zhu,
• Abstract要約: ハイパーキューブでサポートされたサイズ$n$のデータセットから、$(varepsilon,)$-differentially privateな合成データを生成する問題について検討する。 我々は、$n-min 1, frackd$のミニマックス誤差率を$log(n)$ factorまで提案する。
• 参考スコア（独自算出の注目度）: 6.093338631816647
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differentially private synthetic data enables the sharing and analysis of sensitive datasets while providing rigorous privacy guarantees for individual contributors. A central challenge is to achieve strong utility guarantees for meaningful downstream analysis. Many existing methods ensure uniform accuracy over broad query classes, such as all Lipschitz functions, but this level of generality often leads to suboptimal rates for statistics of practical interest. Since many common data analysis queries exhibit smoothness beyond what worst-case Lipschitz bounds capture, we ask whether exploiting this additional structure can yield improved utility. We study the problem of generating $(\varepsilon,δ)$-differentially private synthetic data from a dataset of size $n$ supported on the hypercube $[-1,1]^d$, with utility guarantees uniformly for all smooth queries having bounded derivatives up to order $k$. We propose a polynomial-time algorithm that achieves a minimax error rate of $n^{-\min \{1, \frac{k}{d}\}}$, up to a $\log(n)$ factor. This characterization uncovers a phase transition at $k=d$. Our results generalize the Chebyshev moment matching framework of (Musco et al., 2025; Wang et al., 2016) and strictly improve the error rates for $k$-smooth queries established in (Wang et al., 2016). Moreover, we establish the first minimax lower bound for the utility of $(\varepsilon,δ)$-differentially private synthetic data with respect to $k$-smooth queries, extending the Wasserstein lower bound for $\varepsilon$-differential privacy in (Boedihardjo et al., 2024).
• Abstract（参考訳）: 異なるプライベートな合成データは、個々のコントリビュータに対して厳格なプライバシ保証を提供しながら、センシティブなデータセットの共有と分析を可能にする。 中心的な課題は、意味のある下流分析のための強力なユーティリティ保証を達成することである。 既存の多くの手法は、すべてのリプシッツ関数のような広義のクエリクラスに対して均一な精度を保証するが、このレベルの一般化は、実際的な関心を持つ統計学の最適値に繋がることが多い。 多くの一般的なデータ解析クエリは、最悪のケースであるLipschitz境界のキャプチャ以上の滑らかさを示すので、この追加構造を利用することで、利便性が向上するかどうかを問う。 ハイパーキューブ$[-1,1]^d$でサポートされたデータセットから$(\varepsilon,δ)$-differentially private synthesis dataを生成する問題について検討する。 我々は,最小最大誤差率を$n^{-\min \{1, \frac{k}{d}\}}$, $\log(n)$ factor とする多項式時間アルゴリズムを提案する。 この特徴づけは、相転移を$k=d$で発見する。 We results generalize the Chebyshev moment matching framework of (Musco et al , 2025; Wang et al , 2016) and improve the error rate for $k$-smooth query established in (Wang et al , 2016)。 さらに、$(\varepsilon,δ)$-differentially private synthesis dataを$k$-smoothクエリに対して使用するための最初のminimaxlowboundを確立し、Wasserstein lower boundを$\varepsilon$-differential privacy in (Boedihardjo et al , 2024)に拡張する。

関連論文リスト

• Nearly Optimal Differentially Private ReLU Regression [18.599299269974498]
  微分プライバシ(DP)モデルにおいて、最も基本的な非学習問題の1つ、ReLU回帰について検討する。 我々は,1パスのミニバッチ一般化モデルパーセプトロンアルゴリズムを提案し,解析することで,$epsilon$と公開データの要求を緩和する。
  論文  参考訳（メタデータ） (2025-03-08T02:09:47Z)
• Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
  重み付き勾配を持つ差分プライベート凸最適化(DP-SCO)の問題を考察し、一様境界ではなく、サンプル関数のリプシッツ定数上の$ktextth$-momentを仮定する。 Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon) 1 の誤差を達成し、重み付け設定における第1次最適率(対数係数まで)を得るための新しい還元ベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2024-06-04T21:26:29Z)
• Online Differentially Private Synthetic Data Generation [10.177542186664503]
  差分プライベートな合成データセットを毎回$t$で生成するオンラインアルゴリズムを開発した。 このアルゴリズムは、$O(log(t)t-1/d)$ for $dgeq 2$と$O(log4.5(t)t-1)$ for $d=1$の近似精度を1-ワッサーシュタイン距離で達成する。
  論文  参考訳（メタデータ） (2024-02-12T19:21:14Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)

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

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