論文の概要: Improved Active Learning via Dependent Leverage Score Sampling
- arxiv url: http://arxiv.org/abs/2310.04966v1
- Date: Sun, 8 Oct 2023 01:51:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 13:55:07.937516
- Title: Improved Active Learning via Dependent Leverage Score Sampling
- Title（参考訳）: 依存レバレッジスコアサンプリングによるアクティブラーニングの改善
- Authors: Atsushi Shimizu, Xiaoou Cheng, Christopher Musco, Jonathan Weare
- Abstract要約: 非依存的なサンプリング戦略とレバレッジスコアサンプリングを組み合わせることで、非依存的(逆方向雑音)設定における能動的学習法の改善方法を示す。
独立サンプリングと比較して,本手法は,所定の目標精度に到達するために必要なサンプル数を最大50%削減する。
- 参考スコア（独自算出の注目度）: 9.177032088236125
- 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 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 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 of $O(d)$
samples.
- Abstract（参考訳）: 本研究では,余剰レバレッジスコアのサンプリングと空間被覆を促進する非独立サンプリング戦略を組み合わせることで,アグノスティック(逆方向雑音)設定におけるアクティブな学習方法の改善方法を示す。
特に,パラメトリックpdesの学習に基づく手法と不確かさの定量化によって引き起こされる問題について検証するpivotal samplingアルゴリズムに基づく簡易実装手法を提案する。
本手法は, 個別サンプリングと比較して, 所定の目標精度に達するために必要なサンプル数を最大50\%程度削減する。
2つの理論的結果が得られた。
まず,弱片面$\ell_{\infty}$独立条件に従う非独立レバレッジスコアサンプリング法(重要なサンプリングを含む)は,o(d\log d)$サンプルを用いて,d$次元線形関数を積極的に学習し,独立サンプリングと一致することを示す。
この結果は、行列チャーノフ境界に関する最近の研究を$\ell_{\infty}$ independenceで拡張し、重要なサンプリング以外のサンプリング戦略を分析することにも興味がある。
第二に、多項式回帰の重要な場合において、我々のピボット法は、改良された$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。