論文の概要: Improved Active Learning via Dependent Leverage Score Sampling
- arxiv url: http://arxiv.org/abs/2310.04966v2
- Date: Sat, 4 May 2024 12:33:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-08 00:45:15.125467
- Title: Improved Active Learning via Dependent Leverage Score Sampling
- Title（参考訳）: 依存レバレッジスコアサンプリングによるアクティブラーニングの改善
- Authors: Atsushi Shimizu, Xiaoou Cheng, Christopher Musco, Jonathan Weare,
- Abstract要約: 本研究では,非依存的(逆方向雑音)環境下での能動学習手法の改善方法について述べる。
エンフェボタルサンプリングアルゴリズムに基づく簡単な実装法を提案する。
独立サンプリングと比較して,本手法は,所定の目標精度に到達するために必要なサンプル数を最大50%削減する。
- 参考スコア（独自算出の注目度）: 8.400581768343804
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show how to obtain improved active learning methods in the agnostic (adversarial noise) setting by combining marginal leverage score sampling with non-independent sampling strategies that promote spatial coverage. In particular, we propose an easily implemented method based on the \emph{pivotal sampling algorithm}, which we test on problems motivated by learning-based methods for parametric PDEs and uncertainty quantification. In comparison to independent sampling, our method reduces the number of samples needed to reach a given target accuracy by up to $50\%$. We support our findings with two theoretical results. First, we show that any non-independent leverage score sampling method that obeys a weak \emph{one-sided $\ell_{\infty}$ independence condition} (which includes pivotal sampling) can actively learn $d$ dimensional linear functions with $O(d\log d)$ samples, matching independent sampling. This result extends recent work on matrix Chernoff bounds under $\ell_{\infty}$ independence, and may be of interest for analyzing other sampling strategies beyond pivotal sampling. Second, we show that, for the important case of polynomial regression, our pivotal method obtains an improved bound on $O(d)$ samples.
- Abstract（参考訳）: 本研究では,余剰レバレッジスコアのサンプリングと空間被覆を促進する非独立サンプリング戦略を組み合わせることで,アグノスティック(逆方向雑音)設定におけるアクティブな学習方法の改善方法を示す。
特に,パラメトリックPDEと不確実性定量化の学習に基づく手法によって動機付けられた問題に対して,簡単な実装法を提案する。
本手法は, 個別サンプリングと比較して, 所定の目標精度に達するために必要なサンプル数を最大50\%程度削減する。
理論的には2つの結果が得られた。
まず、弱い 'emph{one-sided $\ell_{\infty}$dependent condition} (ピボットサンプリングを含む) に従う非独立レバレッジスコアサンプリング法は、$O(d\log d)$サンプルを用いて$d$次元線型関数を積極的に学習し、独立サンプリングと一致することを示す。
この結果は、$\ell_{\infty}$独立の下での行列チャーノフ境界に関する最近の研究を拡張し、ピボットサンプリング以外のサンプリング戦略を分析することに興味があるかもしれない。
第二に、多項式回帰の重要な場合において、我々のピボット法は、$O(d)$サンプル上の改善されたバウンダリを得る。
関連論文リスト
- Revisiting Score Function Estimators for $k$-Subset Sampling [5.464421236280698]
離散フーリエ変換を用いて,$k$-subset分布のスコア関数を効率的に計算する方法を示す。
得られた推定器は、正確なサンプルと偏りのない勾配推定の両方を提供する。
特徴選択の実験は、仮定が弱いにもかかわらず、現在の手法と競合する結果を示している。
論文 参考訳（メタデータ） (2024-07-22T21:26:39Z) - Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。
また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
論文 参考訳（メタデータ） (2024-06-03T01:34:34Z) - Data-Efficient Learning via Clustering-Based Sensitivity Sampling:
Foundation Models and Beyond [28.651041302245538]
我々は$k$-meansクラスタリングとサンプリング感度に基づく新しいデータ選択手法を提案する。
線形回帰にどのように適用できるかを示すとともに,レバレッジスコアサンプリングの性能と驚くほど一致した新しいサンプリング戦略がもたらされる。
論文 参考訳（メタデータ） (2024-02-27T09:03:43Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳（メタデータ） (2022-07-16T03:09:30Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。
複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
論文 参考訳（メタデータ） (2020-10-21T13:43:48Z) - A Provably Efficient Sample Collection Strategy for Reinforcement
Learning [123.69175280309226]
オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。
1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
論文 参考訳（メタデータ） (2020-07-13T15:17:35Z) - Learning Entangled Single-Sample Distributions via Iterative Trimming [28.839136703139225]
そこで本研究では, 反復トリミング標本に基づいて, 簡便かつ効率的な手法を解析し, トリミング標本集合上のパラメータを再推定する。
対数反復法では, 誤差が$lceil alpha n rceil$-th ノイズ点の雑音レベルにのみ依存する推定値が出力されることを示す。
論文 参考訳（メタデータ） (2020-04-20T18:37:43Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。