論文の概要: The Price of Privacy For Approximating Max-CSP

• arxiv url: http://arxiv.org/abs/2602.09273v1
• Date: Mon, 09 Feb 2026 23:16:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-11 20:17:43.281421
• Title: The Price of Privacy For Approximating Max-CSP
• Title（参考訳）: Max-CSPを近似するためのプライバシの価格
• Authors: Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi, Akbar Rafiey, Phanu Vajanopath, Zongrui Zou,
• Abstract要約: 情報理論的には、所定のプライバシー予算に対して可能な最高の近似比率を分類することを目的としている。 我々は,任意の$varepsilon$-DPアルゴリズムが,近似比で$O(varepsilon)$以上のランダムな代入を達成できないことを示す。
• 参考スコア（独自算出の注目度）: 26.35241025899951
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Information-theoretically, we aim to classify the best approximation ratios possible for a given privacy budget $\varepsilon$. In the high-privacy regime ($\varepsilon \ll 1$), we show that any $\varepsilon$-DP algorithm cannot beat a random assignment by more than $O(\varepsilon)$ in the approximation ratio. We devise a polynomial-time algorithm which matches this barrier under the assumptions that the instances are bounded-degree and triangle-free. Finally, we show that one or both of these assumptions can be removed for specific CSPs--such as Max-Cut or Max $k$-XOR--albeit at the cost of computational efficiency.
• Abstract（参考訳）: 差分プライバシー(DP)に基づく最大制約満足度問題(Max-CSP)の近似アルゴリズムについて検討した。 情報理論上は、プライバシー予算が$\varepsilon$でできる最高の近似比率を分類することを目指している。 高民権政権(\varepsilon \ll 1$)では、任意の$\varepsilon$-DPアルゴリズムが近似比で$O(\varepsilon)$以上のランダムな割り当てに勝てないことを示す。 我々は、この障壁に一致する多項式時間アルゴリズムを、実例が有界で三角形のないという仮定の下で考案する。 最後に、計算効率を犠牲にして、Max-Cut や Max $k$-XOR のような特定の CSP に対して、これらの仮定の1つまたは2つを除去できることを示す。

関連論文リスト

• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• DP-Dueling: Learning from Preference Feedback without Compromising User Privacy [32.58099924135157]
  ユーザ好みでアクティブな学習を行うための,最初の微分プライベートなダリング帯域幅アルゴリズムを提案する。 我々のアルゴリズムは、ほぼ最適性能で計算効率が良い。 我々は結果を任意の一般的な決定空間に拡張し、潜在的に無限の腕を持つ$d$次元を持つ。
  論文  参考訳（メタデータ） (2024-03-22T09:02:12Z)
• Fine-Grained Privacy Guarantees for Coverage Problems [3.2135945554116905]
  差分プライバシの下で、Max CoverやSet Coverなどのカバレッジ問題に対して、近隣データベースの新たな概念を導入する。 グラフのノードプライバシに類似した、これらの問題の標準的なプライバシー概念とは対照的に、私たちの新しい定義はよりきめ細かいプライバシー保証を提供します。
  論文  参考訳（メタデータ） (2024-03-05T21:40:10Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。 誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
  論文  参考訳（メタデータ） (2024-01-17T09:23:25Z)
• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
  パーソナライズされたプライバシパラメータで$(epsilon_i,delta_i)$-PLDP設定をシャッフルする方法を示す。 shuffled $(epsilon_i,delta_i)$-PLDP process approximately saves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
  論文  参考訳（メタデータ） (2023-12-22T02:31:46Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach [37.80609997145897]
  強化学習は、環境と対話しながらシーケンシャルな決定を行う必要があるアプリケーションで広く使われている。 決定要件がいくつかの安全制約を満たすことを含むと、問題はより難しくなります。 CMDP問題をモデルのない方法で解き、$epsilon$-optimal cumulative rewardを$epsilon$-factible Policyで達成することができる。 ここでの重要な疑問は、制約違反ゼロで$epsilon$-optimal cumulative rewardを達成できるかどうかである。
  論文  参考訳（メタデータ） (2021-09-13T21:27:03Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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