論文の概要: Generalization in the Face of Adaptivity: A Bayesian Perspective
- arxiv url: http://arxiv.org/abs/2106.10761v1
- Date: Sun, 20 Jun 2021 22:06:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 06:31:42.753337
- Title: Generalization in the Face of Adaptivity: A Bayesian Perspective
- Title(参考訳): 適応性の面における一般化:ベイズ的視点
- Authors: Moshe Shenfeld and Katrina Ligett
- Abstract要約: 差分プライバシーは、適応的なクエリにもかかわらず、一般化を保証するツールを提供する。
本稿では,適応データ解析のコア問題に照らし出す,シンプルな特徴を与える。
- 参考スコア(独自算出の注目度): 8.772052142760883
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Repeated use of a data sample via adaptively chosen queries can rapidly lead
to overfitting, wherein the issued queries yield answers on the sample that
differ wildly from the values of those queries on the underlying data
distribution. Differential privacy provides a tool to ensure generalization
despite adaptively-chosen queries, but its worst-case nature means that it
cannot, for example, yield improved results for low-variance queries. In this
paper, we give a simple new characterization that illuminates the core problem
of adaptive data analysis. We show explicitly that the harms of adaptivity come
from the covariance between the behavior of future queries and a Bayes
factor-based measure of how much information about the data sample was encoded
in the responses given to past queries. We leverage this intuition to introduce
a new stability notion; we then use it to prove new generalization results for
the most basic noise-addition mechanisms (Laplace and Gaussian noise addition),
with guarantees that scale with the variance of the queries rather than the
square of their range. Our characterization opens the door to new insights and
new algorithms for the fundamental problem of achieving generalization in
adaptive data analysis.
- Abstract(参考訳): 適応的に選択されたクエリによるデータサンプルの反復使用は、すぐに過剰フィッティングにつながり、発行されたクエリは、基礎となるデータ分散上のクエリの値と大きく異なるサンプルの回答を導き出す。
ディファレンシャルプライバシは、適応的なchosenクエリにもかかわらず、一般化を保証するツールを提供するが、最悪の場合、例えば、低分散クエリに対する結果が改善されないことを意味する。
本稿では,適応型データ解析の核となる問題を照らし出す簡易な新しいキャラクタリゼーションを提案する。
適応性の悪影響は,過去のクエリに対する応答において,データサンプルに関する情報がどの程度エンコードされたかを示すベイズ因子に基づく尺度と,将来のクエリの振る舞いの共分散から生じることを示す。
私たちはこの直観を利用して新しい安定性概念を導入し、最も基本的なノイズ付加機構(ラプラスノイズとガウスノイズ付加)の新たな一般化結果を証明するためにそれを使い、その範囲の2乗ではなく、クエリの分散にスケールすることを保証します。
適応データ解析における一般化の基本的な問題に対する新しい洞察と新しいアルゴリズムの扉を開く。
関連論文リスト
- pEBR: A Probabilistic Approach to Embedding Based Retrieval [4.8338111302871525]
埋め込み検索は、クエリとアイテムの両方の共有セマンティック表現空間を学習することを目的としている。
現在の産業実践では、検索システムは典型的には、異なるクエリに対して一定数のアイテムを検索する。
論文 参考訳(メタデータ) (2024-10-25T07:14:12Z) - Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳(メタデータ) (2024-10-22T10:19:27Z) - Benchmarking Private Population Data Release Mechanisms: Synthetic Data vs. TopDown [50.40020716418472]
本研究では、TopDownアルゴリズムとプライベート合成データ生成を比較し、クエリの複雑さによる精度への影響を判定する。
この結果から,TopDownアルゴリズムは,分散クエリに対して,評価したどの合成データ手法よりもはるかに優れたプライバシー-忠実トレードオフを実現することがわかった。
論文 参考訳(メタデータ) (2024-01-31T17:38:34Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Tackling Diverse Minorities in Imbalanced Classification [80.78227787608714]
不均衡データセットは、様々な現実世界のアプリケーションで一般的に見られ、分類器の訓練において重要な課題が提示されている。
マイノリティクラスとマイノリティクラスの両方のデータサンプルを混合することにより、反復的に合成サンプルを生成することを提案する。
提案するフレームワークの有効性を,7つの公開ベンチマークデータセットを用いて広範な実験により実証する。
論文 参考訳(メタデータ) (2023-08-28T18:48:34Z) - Non-Stochastic CDF Estimation Using Threshold Queries [3.6576781735746513]
実験的な分布を2つの課題で推定する問題に取り組む。
まず、アルゴリズムはデータを直接観察するのではなく、サンプルについて限られた数のしきい値クエリしか要求しない。
第二に、データは独立で同一の分散であると仮定されず、代わりにサンプルを生成する任意のプロセスが可能である。
論文 参考訳(メタデータ) (2023-01-13T18:00:57Z) - Conformal Frequency Estimation using Discrete Sketched Data with
Coverage for Distinct Queries [35.67445122503686]
本稿では、非常に大きな離散データセットにおいて、問合せ対象の周波数に対する信頼区間を構築するための共形推論手法を開発する。
提案手法は,シミュレーションにおける既存の頻繁主義者やベイズ的な代替手法と比較して,経験的性能が向上したことを示す。
論文 参考訳(メタデータ) (2022-11-09T00:05:29Z) - Partial Identification with Noisy Covariates: A Robust Optimization
Approach [94.10051154390237]
観測データセットからの因果推論は、しばしば共変量の測定と調整に依存する。
このロバストな最適化手法により、広範囲な因果調整法を拡張し、部分的同定を行うことができることを示す。
合成および実データセット全体で、このアプローチは既存の手法よりも高いカバレッジ確率でATEバウンダリを提供する。
論文 参考訳(メタデータ) (2022-02-22T04:24:26Z) - Differentially Private Query Release Through Adaptive Projection [19.449593001368193]
我々は,$k$-way マージンのような膨大な統計クエリに対する回答を解放するための新しいアルゴリズムを提案し,実装し,評価する。
我々のアルゴリズムは、単純な摂動を用いて、プライベートデータセット上のクエリに応答するプロジェクションメカニズムの連続緩和を適応的に利用する。
特に,プライバシ予算が小さい場合や,クエリクラスが大きい場合など,既存のアルゴリズムよりも優れていることが判明した。
論文 参考訳(メタデータ) (2021-03-11T12:43:18Z) - Oblivious Data for Fairness with Kernels [1.599072005190786]
感度・非感度特性が利用できる場合のアルゴリズムフェアネスの問題について検討する。
このような不愉快な特徴を生成するための重要な要素は、ヒルベルト空間評価条件予測である。
本稿では,プラグインアプローチを提案し,推定誤差の制御方法を示す。
論文 参考訳(メタデータ) (2020-02-07T16:59:24Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳(メタデータ) (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。