論文の概要: Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

• arxiv url: http://arxiv.org/abs/2609.12508v1
• Date: Fri, 11 Sep 2026 07:13:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-15 07:38:31.65073
• Title: Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
• Title（参考訳）: パラメータトラクタビリティを固定する差分プライバシー - アルゴリズムと低境界
• Abstract要約: 我々は、$$-differential privacy($-DP)の制約の下で最適化問題を研究する。 Gupta et al の暗黙表現フレームワークを一般化する。 我々は、$-DPエンコーダとデコーダのペアが、デコーダがサブ指数時間で動作する場合、一定の近似保証を達成できないことを証明した。
• 参考スコア（独自算出の注目度）: 40.593115580783156
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study combinatorial optimization problems under the constraint of $ε$-differential privacy ($ε$-DP). Given the strong lower bounds for explicitly outputting solutions, we work within the implicit representation framework of Gupta et al. (SODA 2010), where a private polynomial-time randomized "encoder" generates a representation of a solution, and a "decoder" uses this representation along with the input to extract a valid final solution. In this work, we generalize this framework by allowing the encoder to run in fixed-parameter tractable time. This circumvents approximation barriers inherent to polynomial-time algorithms and obtains improved guarantees for many fundamental combinatorial optimization problems. Finally, we establish the first representation-independent lower bounds for our framework. Assuming a non-uniform variant of the Gap Exponential Time Hypothesis, for sufficiently small $ε> 0$, we prove that no $ε$-DP encoder-decoder pair can achieve certain approximation guarantees, if the decoder runs in subexponential time. We further provide representation-dependent lower bounds that hold even for larger $ε$.
• Abstract（参考訳）: 本稿では,ε$-differential privacy(ε$-DP)の制約下での組合せ最適化問題について検討する。 解を明示的に出力する強い下界を考えると、Gupta et al (SODA 2010) の暗黙の表現フレームワークの中で、プライベート多項式時間ランダム化された "エンコーダ" が解の表現を生成し、"デコーダ" が入力とともにこの表現を使用し、有効な最終解を抽出する。 本研究では,エンコーダを一定パラメータのトラクタで動作させることにより,このフレームワークを一般化する。 これは多項式時間アルゴリズム固有の近似障壁を回避し、多くの基本組合せ最適化問題に対する保証を改善する。 最後に,フレームワークの表現に依存しない最初の下位境界を確立する。 十分に小さな$ε> 0$の場合、ギャップ指数時間仮説の非一様変項を仮定すると、デコーダがサブ指数時間で実行された場合、ε$-DPエンコーダ-デコーダペアが特定の近似保証を達成できないことが証明される。 さらに、より大きい$ε$に対してさえも保持する表現依存下界を提供する。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization [6.024178662558234]
  本稿では,DC正則化を用いた非制約問題のクラスを示す。 証明可能な複雑性保証を伴う問題に対してMomentum Mo Mo Penalty法を提案する。
  論文  参考訳（メタデータ） (2026-05-28T09:06:26Z)
• Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
  線形不等式制約を用いた非コンパクト最適化問題に対するスムーズな原始双対アルゴリズムを提案する。 我々のアルゴリズムは、各サンプルの1つの勾配に基づいて、シングルループの反復である。 既存の手法とは異なり、我々のアルゴリズムは自由なサブ、大きなサイズ、パラメータの増加であり、実現可能性を保証するためにデュアル変数更新を使用する。
  論文  参考訳（メタデータ） (2025-04-10T09:59:43Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization [4.608510640547952]
  我々は、Dy Searchのほぼ最適最適化誤差を保証する。 誤差境界における大域リプシッツ定数への古典的依存は、予算の粒度のアーティファクトであることを示す。
  論文  参考訳（メタデータ） (2022-08-13T19:57:04Z)
• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism [16.996435043565594]
  純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。 我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
  論文  参考訳（メタデータ） (2021-11-25T09:31:15Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)

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

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