論文の概要: 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} 逆元が公開鍵暗号の存在を暗示するという意味では避けられない。
関連論文リスト
- 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) - Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - TIC-TAC: A Framework To Learn And Evaluate Your Covariance [119.82937345718378]
State-of-the-art method predict the mean $f_theta(x)$ and covariance $textrmCov(f_theta(x))$ of the target distribution through the two neural network using the negative log-likelihood。
1)予測共分散は予測平均のランダム性を真に捉えているのか?
論文 参考訳(メタデータ) (2023-10-29T09:54:03Z) - 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) - Subsampling Suffices for Adaptive Data Analysis [8.231050911072755]
ほとんどの古典的なテクニックは、データセットがアナリストのクエリとは独立していると仮定し、データセットが複数の適応的に選択されたクエリのために再利用される一般的な設定に分解する。
クエリが適応的に選択された場合でも、クエリが引き続き表現されるという、非常に単純な仮定のセットを特定します。
このサブサンプルベースのフレームワークの単純さにより、以前の作業でカバーされていないさまざまな現実世界のシナリオをモデル化することができる。
論文 参考訳(メタデータ) (2023-02-17T02:47:54Z) - Ensemble Multi-Quantiles: Adaptively Flexible Distribution Prediction
for Uncertainty Quantification [4.728311759896569]
本稿では,機械学習における不確実性を定量化するために,分布予測の新しい,簡潔かつ効果的な手法を提案する。
これは回帰タスクにおいて$mathbbP(mathbfy|mathbfX=x)$の適応的に柔軟な分布予測を組み込む。
UCIデータセットからの大規模な回帰タスクでは、EMQが最先端のパフォーマンスを達成することを示す。
論文 参考訳(メタデータ) (2022-11-26T11:45:32Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。