論文の概要: Fixed-Parameter Tractability of Private Synthetic Data Generation
- arxiv url: http://arxiv.org/abs/2606.11283v1
- Date: Tue, 09 Jun 2026 15:14:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-11 16:42:38.108103
- Title: Fixed-Parameter Tractability of Private Synthetic Data Generation
- Title（参考訳）: プライベートシンセティックデータ生成における固定パラメータのトラクタビリティ
- Authors: Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi,
- Abstract要約: 差分プライバシーの下で合成データを生成する問題について検討する。
我々のアルゴリズムは、全てのレシスタンスで最適なエラー率を獲得し、2つの異なるアプローチで実現されている。
- 参考スコア（独自算出の注目度）: 84.99100741615423
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth of the query family's incidence graph. Our algorithms attain optimal error rates across all regimes and are realized by two different approaches: the first is based on linear programming (LP) and the FPT of the separation problem for the LP dual; the second is based on a subsampled private multiplicative weights method, where we obtain FPT for sampling from Gibbs distributions. Both approaches are unified by a dynamic programming framework over a tree decomposition.
- Abstract（参考訳）: 差分プライバシーの下で合成データを生成する問題について検討する。
パラメータがクエリーファミリーの頻度グラフのツリー幅であるこの問題に対して、固定パラメータトラクタビリティ(FPT)を確立する。
アルゴリズムは,全てのレシスタンスに対して最適誤差率を達成し,まず線形プログラミング(LP)とLP双対分離問題のFPTを基準とし,次に,Gibs分布から抽出するFPTをサブサンプリングしたプライベート乗算重み法に基づく。
どちらのアプローチも、ツリー分解に関する動的プログラミングフレームワークによって統一されています。
関連論文リスト
- SEED: Targeted Data Selection by Weighted Independent Set [76.68391670109433]
我々はSEEDと呼ばれる堅牢でスケーラブルなデータ選択パイプラインを開発した。
SEEDは、命令チューニング、視覚的命令チューニング、セマンティックセグメンテーションにおける最先端の手法を一貫して上回っている。
論文 参考訳（メタデータ） (2026-05-15T07:26:54Z) - Enhancing Scalability of Metric Differential Privacy via Secret Dataset Partitioning and Benders Decomposition [1.283608820493284]
メトリック微分プライバシー(mDP)は、新しいデータパラダイムとして機能するために、差分プライバシー(DP)の概念を拡張します。
道路網やグリッドマップ上の単語埋め込みや位置情報として符号化されたテキストデータなど、一般的なメートル法空間で表される秘密データを保護するように設計されている。
論文 参考訳（メタデータ） (2024-05-07T14:19:09Z) - Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-04-16T20:01:10Z) - Joint Bayesian Inference of Graphical Structure and Parameters with a
Single Generative Flow Network [59.79008107609297]
本稿では,ベイジアンネットワークの構造上の結合後部を近似する手法を提案する。
サンプリングポリシが2フェーズプロセスに従う単一のGFlowNetを使用します。
パラメータは後部分布に含まれるため、これは局所確率モデルに対してより柔軟である。
論文 参考訳（メタデータ） (2023-05-30T19:16:44Z) - Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。
従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
論文 参考訳（メタデータ） (2021-11-24T13:38:34Z) - A Method for Handling Multi-class Imbalanced Data by Geometry based
Information Sampling and Class Prioritized Synthetic Data Generation (GICaPS) [15.433936272310952]
本稿では,多ラベル分類問題における不均衡データ処理の問題について考察する。
特徴ベクトル間の幾何学的関係を利用する2つの新しい手法が提案されている。
提案手法の有効性は,汎用的なマルチクラス認識問題を解くことによって解析する。
論文 参考訳（メタデータ） (2020-10-11T04:04:26Z) - Sparse learning with CART [18.351254916713305]
二分木を持つ決定木は、分類木と回帰木(CART)の手法を用いて一般的に構築されている。
本稿では,CART法を用いて構築した回帰木の統計的特性について検討する。
論文 参考訳（メタデータ） (2020-06-07T20:55:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。