論文の概要: The Limits of Assumption-free Tests for Algorithm Performance
- arxiv url: http://arxiv.org/abs/2402.07388v1
- Date: Mon, 12 Feb 2024 03:19:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 15:41:52.012848
- Title: The Limits of Assumption-free Tests for Algorithm Performance
- Title（参考訳）: アルゴリズム性能に対する仮定フリーテストの限界
- Authors: Yuetian Luo and Rina Foygel Barber
- Abstract要約: 与えられたモデリングタスクにおいてアルゴリズムはどの程度うまく機能し、どのアルゴリズムが最善を尽くすか?
一方、特定のトレーニングデータセットに対して$A$を実行して生成された特定の適合モデルが$n$であるのか?
- 参考スコア（独自算出の注目度）: 6.7171902258864655
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Algorithm evaluation and comparison are fundamental questions in machine
learning and statistics -- how well does an algorithm perform at a given
modeling task, and which algorithm performs best? Many methods have been
developed to assess algorithm performance, often based around cross-validation
type strategies, retraining the algorithm of interest on different subsets of
the data and assessing its performance on the held-out data points. Despite the
broad use of such procedures, the theoretical properties of these methods are
not yet fully understood. In this work, we explore some fundamental limits for
answering these questions with limited amounts of data. In particular, we make
a distinction between two questions: how good is an algorithm $A$ at the
problem of learning from a training set of size $n$, versus, how good is a
particular fitted model produced by running $A$ on a particular training data
set of size $n$?
Our main results prove that, for any test that treats the algorithm $A$ as a
``black box'' (i.e., we can only study the behavior of $A$ empirically), there
is a fundamental limit on our ability to carry out inference on the performance
of $A$, unless the number of available data points $N$ is many times larger
than the sample size $n$ of interest. (On the other hand, evaluating the
performance of a particular fitted model is easy as long as a holdout data set
is available -- that is, as long as $N-n$ is not too small.) We also ask
whether an assumption of algorithmic stability might be sufficient to
circumvent this hardness result. Surprisingly, we find that this is not the
case: the same hardness result still holds for the problem of evaluating the
performance of $A$, aside from a high-stability regime where fitted models are
essentially nonrandom. Finally, we also establish similar hardness results for
the problem of comparing multiple algorithms.
- Abstract（参考訳）: アルゴリズムの評価と比較は、機械学習と統計学における基本的な問題です -- 特定のモデリングタスクでアルゴリズムはどの程度の性能を持ち、どのアルゴリズムが最適か?
アルゴリズムの性能を評価するために多くの手法が開発され、しばしばクロスバリデーション型の戦略に基づいて、データの異なるサブセットに対する関心のアルゴリズムを再訓練し、保持されたデータポイントでそのパフォーマンスを評価する。
このような方法が広く用いられているにもかかわらず、これらの手法の理論的性質はまだ完全には理解されていない。
本研究では,これらの疑問に限られたデータで答える基本的な限界について検討する。
特に、2つの質問を区別する: アルゴリズムが、サイズが$n$のトレーニングセットから学習する問題に対して、アルゴリズムが$a$、サイズが$n$のトレーニングデータセットで$a$を実行して生成された特定の適合モデルがどの程度優れているか?
我々の主な結果は、アルゴリズムの$A$を 'black box'' として扱うテスト(つまり、$A$の振る舞いを経験的にしか研究できない)に対して、利用可能なデータポイントの数が $n$ のサンプルサイズの $n$ よりも何倍も大きい場合を除いて、$A$のパフォーマンスを推論する能力に根本的な制限があることを証明している。
(一方で、特定の適合モデルの性能を評価することは、ホールドアウトデータセットが利用可能である限り簡単であり、つまり、$N-n$が小さすぎる限りである)。
また,アルゴリズム安定性の仮定が,この困難さを回避できるかどうかを問う。
驚くべきことに、これはそうではない:同じ硬さの結果は、収まるモデルが本質的に非ランダムな高安定性な状態を除いても、$A$のパフォーマンスを評価する問題に依然として当てはまる。
最後に、複数のアルゴリズムを比較する問題に対して、同様の硬度結果を確立する。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Subset-Based Instance Optimality in Private Estimation [23.173651165908282]
我々は、幅広いデータセット特性を推定する際に、インスタンス最適性の概念を実現するプライベートアルゴリズムを構築する方法を示す。
提案アルゴリズムは,分布的な仮定の下で,既存のアルゴリズムの性能を同時に一致または超過する。
論文 参考訳（メタデータ） (2023-03-01T18:49:10Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
本稿では,軽度条件下での有限個の判定問題に対して,対話型意思決定のための最初のインスタンス最適化アルゴリズムを設計する。
本研究の結果は, 具体的問題に着目し, 多腕バンディットの古典的ギャップ依存境界と, 線形バンディットに関する先行研究を復元した。
論文 参考訳（メタデータ） (2022-06-06T02:56:10Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳（メタデータ） (2022-05-03T11:00:59Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - An Empirical Comparison of Off-policy Prediction Learning Algorithms in
the Four Rooms Environment [9.207173776826403]
我々は,11の非政治予測学習アルゴリズムと2つの小さなタスクに対する線形関数近似を経験的に比較した。
アルゴリズムの性能は、重要サンプリング比によって引き起こされるばらつきに強く影響される。
強調的なTD($lambda$)は、他のアルゴリズムよりもエラーが少ない傾向にあるが、場合によってはよりゆっくりと学習することもある。
論文 参考訳（メタデータ） (2021-09-10T21:15:41Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。