論文の概要: Adaptive Data Analysis in a Balanced Adversarial Model

• arxiv url: http://arxiv.org/abs/2305.15452v2
• Date: Fri, 3 Nov 2023 18:30:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-07 22:30:09.701973
• Title: Adaptive Data Analysis in a Balanced Adversarial Model
• Title（参考訳）: balanced adversarial modelにおける適応データ解析
• Authors: Kobbi Nissim, Uri Stemmer, Eliad Tsfadia
• Abstract要約: 適応データ解析において、メカニズムは未知の分布から$n$、すなわち$D$のサンプルを取得し、正確な推定を行う必要がある。 我々は、それぞれが2つの分離されたアルゴリズムから構成されるアンフバランスドと呼ばれる、より制限された敵を考える。 これらの強い硬さの仮定は、計算的に有界なアンフバランス逆元が公開鍵暗号の存在を示唆するという意味では避けられないことを示す。
• 参考スコア（独自算出の注目度）: 26.58630744414181
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In adaptive data analysis, a mechanism gets $n$ i.i.d. samples from an unknown distribution $D$, and is required to provide accurate estimations to a sequence of adaptively chosen statistical queries with respect to $D$. Hardt and Ullman (FOCS 2014) and Steinke and Ullman (COLT 2015) showed that in general, it is computationally hard to answer more than $\Theta(n^2)$ adaptive queries, assuming the existence of one-way functions. However, these negative results strongly rely on an adversarial model that significantly advantages the adversarial analyst over the mechanism, as the analyst, who chooses the adaptive queries, also chooses the underlying distribution $D$. This imbalance raises questions with respect to the applicability of the obtained hardness results -- an analyst who has complete knowledge of the underlying distribution $D$ would have little need, if at all, to issue statistical queries to a mechanism which only holds a finite number of samples from $D$. We consider more restricted adversaries, called \emph{balanced}, where each such adversary consists of two separated algorithms: The \emph{sampler} who is the entity that chooses the distribution and provides the samples to the mechanism, and the \emph{analyst} who chooses the adaptive queries, but has no prior knowledge of the underlying distribution (and hence has no a priori advantage with respect to the mechanism). We improve the quality of previous lower bounds by revisiting them using an efficient \emph{balanced} adversary, under standard public-key cryptography assumptions. We show that these stronger hardness assumptions are unavoidable in the sense that any computationally bounded \emph{balanced} adversary that has the structure of all known attacks, implies the existence of public-key cryptography.
• Abstract（参考訳）: 適応データ分析において、メカニズムは未知の分布から$D$から$n$、すなわち$D$のサンプルを取得し、適応的に選択された統計的クエリのシーケンスに対して正確な推定を行う必要がある。 Hardt and Ullman (FOCS 2014) と Steinke and Ullman (COLT 2015) は、一般に、片方向関数の存在を前提として、$\Theta(n^2)$ Adaptive query 以上の答えは計算的に困難であることを示した。 しかし、これらの否定的な結果は、アダプティブクエリを選択したアナリストが基盤となるディストリビューションである$d$を選択するため、そのメカニズムよりも敵アナリストに著しく有利な敵モデルに強く依存している。 この不均衡は、得られた硬度結果の適用性に関する疑問を提起する -- 基礎となる分布について完全な知識を持つアナリストは、$D$から有限個のサンプルしか持たないメカニズムに統計的クエリを発行する必要性はほとんどない。 より制限された敵は \emph{ Balanced} と呼ばれ、それぞれの敵は2つの分離されたアルゴリズムから構成される: 分布を選択し、そのメカニズムにサンプルを提供する存在である \emph{sampler} と、適応的なクエリを選択するが、基礎となる分布について事前の知識を持たない(従って、そのメカニズムに関して事前の優位性を持たない)。 我々は,通常の公開鍵暗号の仮定の下で,効率のよい 'emph{ Balanced} 逆数を用いて再検討することで,以前の下位境界の品質を向上させる。 これらの強硬度仮定は、すべての既知の攻撃の構造を持つ計算的に有界な \emph{balanced} 逆元が公開鍵暗号の存在を暗示するという意味では避けられない。

関連論文リスト

• How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions [0.0]
  本研究では,確率的検証器が解析結果がほぼ正しいことを確認するための証明システムについて検討する。 未知の分布が要求される特性を持っていることを検証する。 我々の主な貢献は、検証者と信頼できない証明者との間の対話的プロトコルであり、任意のプロパティを検証するのに使用できる。
  論文  参考訳（メタデータ） (2024-09-10T15:37:23Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  拒絶による分類は、モデルを予測しないことを許容する学習パラダイムとして現れます。 そこで我々は,事前学習したモデルの性能を最大化する理想的なデータ分布を求める。 私たちのフレームワークは、クリーンでノイズの多いデータセットで実証的にテストされます。
  論文  参考訳（メタデータ） (2024-05-29T01:32:17Z)
• Score-based generative models are provably robust: an uncertainty quantification perspective [4.396860522241307]
  本研究では,スコアベース生成モデル (SGM) が実運用において複数の誤差源に対して確実に堅牢であることを示す。 我々の主要なツールは、ワッサーシュタイン不確実性伝播(WUP)定理である。 a) 有限サンプル近似による誤差, (b) 早期停止, (c) スコアマッチング対象選択, (d) スコア関数パラメトリゼーション, (e) 基準分布選択が生成モデルの品質に与える影響を示す。
  論文  参考訳（メタデータ） (2024-05-24T17:50:17Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。 適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
  論文  参考訳（メタデータ） (2024-05-24T11:22:19Z)
• Revisiting the Dataset Bias Problem from a Statistical Perspective [72.94990819287551]
  統計的観点から「データセットバイアス」問題を考察する。 問題の主な原因は、クラス属性 u と非クラス属性 b の強い相関関係である。 本稿では,各試料nの目的をフラクタル1p(u_n|b_n)で重み付けするか,その試料をフラクタル1p(u_n|b_n)に比例してサンプリングすることにより,データセットバイアスを軽減することを提案する。
  論文  参考訳（メタデータ） (2024-02-05T22:58:06Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• CARD: Classification and Regression Diffusion Models [51.0421331214229]
  本稿では,条件生成モデルと事前学習条件平均推定器を組み合わせた分類と回帰拡散(CARD)モデルを提案する。 おもちゃの例と実世界のデータセットを用いて条件分布予測におけるCARDの卓越した能力を示す。
  論文  参考訳（メタデータ） (2022-06-15T03:30:38Z)
• Robust Linear Regression for General Feature Distribution [21.0709900887309]
  本研究では, 不正な相手によってデータが汚染されるような頑健な線形回帰について検討する。 必ずしもその機能が中心であるとは限らない。 特徴が中心ならば、標準収束率を得ることができる。
  論文  参考訳（メタデータ） (2022-02-04T11:22:13Z)
• Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification [16.0817847880416]
  ヒルベルト空間上の様々な線形予測問題を含む統一的なフレームワークを提供する。 誤特定レベル $epsilon$ に対して、これらの推定器は、文献で最もよく知られたレートと一致する、$O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$ の誤差率を達成する。
  論文  参考訳（メタデータ） (2022-01-06T08:51:08Z)
• Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness [50.96431444396752]
  主な課題は、各ランダム化メカニズムの適切性を評価する方法である。 まず最初に、ガウスのメカニズムが$ell$-normを証明するための適切な選択肢であると結論付ける。 驚いたことに、ガウスのメカニズムは指数機構の代わりに$ell_infty$-normを証明するための適切な選択肢でもある。
  論文  参考訳（メタデータ） (2020-05-15T03:54:53Z)
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
  本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。 統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。 また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
  論文  参考訳（メタデータ） (2020-02-05T00:24:53Z)

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

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