論文の概要: Optimal Algorithms for Augmented Testing of Discrete Distributions

• arxiv url: http://arxiv.org/abs/2412.00974v1
• Date: Sun, 01 Dec 2024 21:31:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-04 15:48:17.604140
• Title: Optimal Algorithms for Augmented Testing of Discrete Distributions
• Title（参考訳）: 離散分布の増分試験のための最適アルゴリズム
• Authors: Maryam Aliakbarpour, Piotr Indyk, Ronitt Rubinfeld, Sandeep Silwal,
• Abstract要約: 予測器は3つのプロパティテストタスクすべてに必要なサンプル数を実際に削減できることを示す。 我々のアルゴリズムの重要な利点は、予測の精度への適応性である。 アルゴリズムによって達成されるサンプルの複雑さの改善は、情報理論的に最適であることを示すために、より低い境界を提供する。
• 参考スコア（独自算出の注目度）: 25.818433126197036
• License:
• Abstract: We consider the problem of hypothesis testing for discrete distributions. In the standard model, where we have sample access to an underlying distribution $p$, extensive research has established optimal bounds for uniformity testing, identity testing (goodness of fit), and closeness testing (equivalence or two-sample testing). We explore these problems in a setting where a predicted data distribution, possibly derived from historical data or predictive machine learning models, is available. We demonstrate that such a predictor can indeed reduce the number of samples required for all three property testing tasks. The reduction in sample complexity depends directly on the predictor's quality, measured by its total variation distance from $p$. A key advantage of our algorithms is their adaptability to the precision of the prediction. Specifically, our algorithms can self-adjust their sample complexity based on the accuracy of the available prediction, operating without any prior knowledge of the estimation's accuracy (i.e. they are consistent). Additionally, we never use more samples than the standard approaches require, even if the predictions provide no meaningful information (i.e. they are also robust). We provide lower bounds to indicate that the improvements in sample complexity achieved by our algorithms are information-theoretically optimal. Furthermore, experimental results show that the performance of our algorithms on real data significantly exceeds our worst-case guarantees for sample complexity, demonstrating the practicality of our approach.
• Abstract（参考訳）: 離散分布に対する仮説テストの問題点を考察する。 基礎となる分布へのサンプルアクセスが$p$である標準モデルでは、広範な研究が統一性テスト、アイデンティティテスト(適合性の良さ)、近接性テスト(等価性または2サンプルテスト)の最適境界を確立している。 これらの問題を、過去のデータや予測機械学習モデルから派生した予測データ分布が利用できるような環境で検討する。 このような予測器が3つのプロパティテストタスクすべてに必要なサンプル数を実際に削減できることを実証する。 サンプルの複雑さの減少は、予測器の品質に直接依存し、その総変動距離が$p$から測定される。 我々のアルゴリズムの重要な利点は、予測の精度への適応性である。 具体的には,提案アルゴリズムは,推定精度の事前知識(すなわち,一貫した値)を伴わずに,利用可能な予測精度に基づいて,サンプルの複雑性を自己調整することができる。 さらに、予測が意味のある情報を提供しなくても(つまり、それらは堅牢である)、標準的なアプローチよりも多くのサンプルを使用することはない。 アルゴリズムによって達成されるサンプルの複雑さの改善は、情報理論的に最適であることを示すために、より低い境界を提供する。 さらに,実データ上でのアルゴリズムの性能は,サンプルの複雑さに対する最悪の保証をはるかに上回っており,本手法の実用性を示している。

関連論文リスト

• Investigating the Impact of Hard Samples on Accuracy Reveals In-class Data Imbalance [4.291589126905706]
  AutoMLドメインでは、モデルの有効性を評価するための重要な指標として、テスト精度が宣言される。 しかし、主性能指標としての試験精度の信頼性は疑問視されている。 トレーニングセットとテストセット間のハードサンプルの分布は、これらのセットの難易度に影響を与える。 本稿では,ハードサンプル識別法を比較するためのベンチマーク手法を提案する。
  論文  参考訳（メタデータ） (2024-09-22T11:38:14Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Boost Test-Time Performance with Closed-Loop Inference [85.43516360332646]
  そこで本研究では,モデル性能を高めるために,ループ方式でハードクラス化試験サンプルを予測することを提案する。 まず、追加の推論ループを必要とするハードクラス化テストサンプルを識別するためにフィルタリング基準を考案する。 各ハードサンプルに対して、モデルのキャリブレーションを行うために、元の上位$K$予測に基づいて補助学習タスクを構築する。
  論文  参考訳（メタデータ） (2022-03-21T10:20:21Z)
• Conformal prediction for the design problem [72.14982816083297]
  機械学習の現実的な展開では、次にテストすべきデータを選択するために予測アルゴリズムを使用します。 このような設定では、トレーニングデータとテストデータの間には、異なるタイプの分散シフトがある。 このような環境で予測の不確実性を定量化する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-08T02:59:12Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  実世界の機械学習デプロイメントは、ソース(トレーニング)とターゲット(テスト)ディストリビューションのミスマッチによって特徴づけられる。 本研究では,ラベル付きソースデータとラベルなしターゲットデータのみを用いて,対象領域の精度を予測する手法を検討する。 本稿では,モデルの信頼度をしきい値として学習し,精度をラベルなし例のごく一部として予測する実践的手法である平均閾値保持信頼度(ATC)を提案する。
  論文  参考訳（メタデータ） (2022-01-11T23:01:12Z)
• Sequential Domain Adaptation by Synthesizing Distributionally Robust Experts [14.656957226255628]
  教師付きドメイン適応は、目標分布に近いソース分布からラベル付きトレーニングサンプルを追加することにより、予測精度を向上させることを目的としている。 我々は、提案した頑健な専門家の家系のBernsteinオンライン集約アルゴリズムを用いて、ターゲットサンプルの逐次的ストリームの予測を生成する。
  論文  参考訳（メタデータ） (2021-06-01T08:51:55Z)
• Robust Fairness-aware Learning Under Sample Selection Bias [17.09665420515772]
  サンプル選択バイアス下での頑健で公正な学習のための枠組みを提案する。 テストデータが利用可能で、利用できない場合に、サンプル選択バイアスを処理する2つのアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-05-24T23:23:36Z)
• Improving Uncertainty Calibration via Prior Augmented Data [56.88185136509654]
  ニューラルネットワークは、普遍関数近似器として機能することで、複雑なデータ分布から学習することに成功した。 彼らはしばしば予測に自信過剰であり、不正確で誤った確率的予測に繋がる。 本稿では,モデルが不当に過信である特徴空間の領域を探索し,それらの予測のエントロピーをラベルの以前の分布に対して条件的に高める手法を提案する。
  論文  参考訳（メタデータ） (2021-02-22T07:02:37Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)
• CoinPress: Practical Private Mean and Covariance Estimation [18.6419638570742]
  多変量準ガウスデータの平均と共分散に対する単純な微分プライベート推定器を提案する。 これらの誤差率は最先端の理論的境界値と一致し, 従来手法よりも顕著に優れていたことを示す。
  論文  参考訳（メタデータ） (2020-06-11T17:17:28Z)

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

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