論文の概要: Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
- arxiv url: http://arxiv.org/abs/2603.18254v1
- Date: Wed, 18 Mar 2026 20:20:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-20 17:19:05.836223
- Title: Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
- Title（参考訳）: ベイズ推定における計算と実用のトレードオフ
- Authors: Sitan Chen, Jingqiu Ding, Mahbod Majid, Walter McKelvie,
- Abstract要約: 平均二乗誤差を実現する2つの問題に対して,最初の効率的なアルゴリズムを提案する。
我々は、プライベートベイズ最適推定を実現するために、arXiv:2212.05のプライバシーとロバスト性に関するフレームワークを取り上げている。
また、ショートフラット分解に基づく新しい種類の制約を平方和ツールキットに追加する。
- 参考スコア（独自算出の注目度）: 14.293470686822305
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Bayesian methods lie at the heart of modern data science and provide a powerful scaffolding for estimation in data-constrained settings and principled quantification and propagation of uncertainty. Yet in many real-world use cases where these methods are deployed, there is a natural need to preserve the privacy of the individuals whose data is being scrutinized. While a number of works have attempted to approach the problem of differentially private Bayesian estimation through either reasoning about the inherent privacy of the posterior distribution or privatizing off-the-shelf Bayesian methods, these works generally do not come with rigorous utility guarantees beyond low-dimensional settings. In fact, even for the prototypical tasks of Gaussian mean estimation and linear regression, it was unknown how close one could get to the Bayes-optimal error with a private algorithm, even in the simplest case where the unknown parameter comes from a Gaussian prior. In this work, we give the first efficient algorithms for both of these problems that achieve mean-squared error $(1+o(1))\mathrm{OPT}$ and additionally show that both tasks exhibit an intriguing computational-statistical gap. For Bayesian mean estimation, we prove that the excess risk achieved by our method is optimal among all efficient algorithms within the low-degree framework, yet is provably worse than what is achievable by an exponential-time algorithm. For linear regression, we prove a qualitatively similar lower bound. Our algorithms draw upon the privacy-to-robustness framework of arXiv:2212.05015, but with the curious twist that to achieve private Bayes-optimal estimation, we need to design sum-of-squares-based robust estimators for inherently non-robust objects like the empirical mean and OLS estimator. Along the way we also add to the sum-of-squares toolkit a new kind of constraint based on short-flat decompositions.
- Abstract（参考訳）: ベイズ的手法は現代のデータ科学の中心にあり、データ制約された設定と原則付き定量化と不確実性の伝播における推定のための強力な足場を提供する。
しかし、これらの方法がデプロイされている現実世界の多くのユースケースでは、データを精査している個人のプライバシーを維持する必要がある。
多くの研究が、後部分布の固有のプライバシーについて推論したり、市販のベイズ的手法を民営化したりすることで、微分プライベートなベイズ的推定の問題にアプローチしようとしているが、これらの研究は一般に低次元設定以上の厳密な実用性保証を伴わない。
実際、ガウス平均推定と線形回帰の原型的タスクでさえ、未知のパラメータがガウス以前のパラメータから来る最も単純な場合であっても、プライベートアルゴリズムでベイズ最適誤差にどの程度近づいたかは分かっていなかった。
本研究では, 平均二乗誤差(1+o(1))\mathrm{OPT}$) を達成し, 両タスクが興味深い計算統計的ギャップを示すことを示す。
ベイズ平均推定では、我々の手法によって達成される余剰リスクは、低次フレームワーク内の全ての効率的なアルゴリズムの中で最適であるが、指数時間アルゴリズムで達成できるものよりも確実に劣っていることを示す。
線形回帰について、定性的に類似した下界を証明する。
私たちのアルゴリズムは、arXiv:2212.05015のプライバシとロバスト性のフレームワークをベースとしていますが、プライベートベイズ最適推定を実現するには、経験的平均やOLS推定のような本質的に非ロバストなオブジェクトに対する2乗ベースのロバストな推定器を設計する必要があります。
その過程で、ショートフラット分解に基づいた新しい種類の制約を追加します。
関連論文リスト
- RPWithPrior: Label Differential Privacy in Regression [0.0]
本稿では,$$-label差分プライバシー保証の下での回帰タスクに着目した。
元の応答とランダムな応答を連続確率変数としてモデル化し、離散化を完全に回避する。
我々のアルゴリズムであるRPWithPriorは、$$-label差分プライバシーを保証する。
論文 参考訳（メタデータ） (2026-01-30T06:27:13Z) - Approximate Algorithms for Verifying Differential Privacy with Gaussian Distributions [2.9748898344267776]
離散分布と連続分布の両方からサンプリングしたループフリープログラムの確率分布を近似する新しい手法を提案する。
我々の検証アルゴリズムは、積分近似とテール確率境界を組み合わせることにより、任意の所望の精度で確率を計算することに基づいている。
論文 参考訳（メタデータ） (2025-09-10T17:37:56Z) - Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Sample-Optimal Private Regression in Polynomial Time [3.3748750222488657]
アルゴリズムのサンプル複雑性の改善は,統計的クエリや情報理論的下位境界に反することを示した。
アルゴリズムは任意の外れ値の小さな部分に対して頑健であり、外れ値の小さな部分の関数として最適誤差率を達成する。
論文 参考訳（メタデータ） (2025-03-31T17:08:12Z) - Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。
微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。
これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
論文 参考訳（メタデータ） (2025-02-13T02:05:45Z) - Differentially Private Domain Adaptation with Theoretical Guarantees [46.37771025567305]
多くのアプリケーションでは、ラベル付きデータの処分におけるラベル付きデータはプライバシー上の制約を受けており、比較的制限されている。
これは、パブリックソースからプライベートターゲットドメインへのドメイン適応を監督する現代の問題である。
我々は、理論的な学習保証の恩恵を受けるために、一般の学習者を利用する。
論文 参考訳（メタデータ） (2023-06-15T04:03:06Z) - Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean
Estimation [8.9598796481325]
本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。
プライベートスパース平均推定のための情報計算ギャップを確立する。
また、プライバシーによって引き起こされる情報計算のギャップを、いくつかの統計や学習問題に対して証明する。
論文 参考訳（メタデータ） (2022-11-01T20:03:41Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳（メタデータ） (2022-05-05T06:43:46Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Robust and Differentially Private Mean Estimation [40.323756738056616]
異なるプライバシーは、米国国勢調査から商用デバイスで収集されたデータまで、さまざまなアプリケーションで標準要件として浮上しています。
このようなデータベースの数は、複数のソースからのデータからなり、それらすべてが信頼できるわけではない。
これにより、既存のプライベート分析は、腐敗したデータを注入する敵による攻撃に弱い。
論文 参考訳（メタデータ） (2021-02-18T05:02:49Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。