論文の概要: Reproducibility in Learning
- arxiv url: http://arxiv.org/abs/2201.08430v1
- Date: Thu, 20 Jan 2022 19:59:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-24 14:28:48.027760
- Title: Reproducibility in Learning
- Title（参考訳）: 学習における再現性
- Authors: Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell
- Abstract要約: 再現可能な学習アルゴリズムは、サンプルのバリエーションに耐性がある。
強い需要にもかかわらず、統計学や学習におけるいくつかの基本的な問題に対して効率的な再現可能なアルゴリズムが存在する。
- 参考スコア（独自算出の注目度）: 8.386806623480156
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the notion of a reproducible algorithm in the context of
learning. A reproducible learning algorithm is resilient to variations in its
samples -- with high probability, it returns the exact same output when run on
two samples from the same underlying distribution. We begin by unpacking the
definition, clarifying how randomness is instrumental in balancing accuracy and
reproducibility. We initiate a theory of reproducible algorithms, showing how
reproducibility implies desirable properties such as data reuse and efficient
testability. Despite the exceedingly strong demand of reproducibility, there
are efficient reproducible algorithms for several fundamental problems in
statistics and learning. First, we show that any statistical query algorithm
can be made reproducible with a modest increase in sample complexity, and we
use this to construct reproducible algorithms for finding approximate
heavy-hitters and medians. Using these ideas, we give the first reproducible
algorithm for learning halfspaces via a reproducible weak learner and a
reproducible boosting algorithm. Finally, we initiate the study of lower bounds
and inherent tradeoffs for reproducible algorithms, giving nearly tight sample
complexity upper and lower bounds for reproducible versus nonreproducible SQ
algorithms.
- Abstract（参考訳）: 本稿では,再現可能なアルゴリズムの概念を学習の文脈で紹介する。
再現可能な学習アルゴリズムは、サンプルのバリエーションに耐性があり、高い確率で、同じ基礎となる分布から2つのサンプルを実行すると、全く同じ出力を返す。
まず、定義を解き明かし、ランダム性が正確性と再現性のバランスにどのように寄与するかを明らかにする。
再現性がデータ再利用や効率的なテスト容易性といった望ましい特性をどのように持つかを示す再現性アルゴリズムの理論を開始する。
再現性は非常に強い要求にもかかわらず、統計学や学習におけるいくつかの基本的な問題に対して効率的な再現性アルゴリズムが存在する。
まず,任意の統計的問合せアルゴリズムをサンプルの複雑さを緩やかに増やすことで再現可能とし,これを用いて近似重ヒットと中央値を求める再現可能なアルゴリズムを構築する。
これらのアイデアを用いて,再現可能な弱学習器と再現可能なブースティングアルゴリズムを用いて,ハーフスペースを学習するための最初の再現可能なアルゴリズムを与える。
最後に,再現可能アルゴリズムに対する下限と内在的なトレードオフの研究を開始し,再現可能アルゴリズムと非再現可能sqアルゴリズムを上限と下限でほぼ厳密なサンプル複雑性を与える。
関連論文リスト
- Derandomizing Multi-Distribution Learning [28.514129340758938]
マルチディストリビューション学習では、複数のデータ分散でうまく動作する単一の予測子を学習する。
近年の研究では、オラクル効率のアルゴリズムにより、ほぼ最適サンプルの複雑さが達成されている。
これらのアルゴリズムは、複数の分布に対する決定論的予測子を生成するためにデランドマイズできるのだろうか?
論文 参考訳（メタデータ） (2024-09-26T06:28:56Z) - Batch Bayesian Optimization for Replicable Experimental Design [56.64902148159355]
多くの実世界の設計問題は、大規模で異質な観測ノイズのため、複数の実験条件を並列に評価し、各条件を複数回再現する。
本稿では,3つのアルゴリズムを含むReplicable Experimental Designフレームワークのバッチトンプソンサンプリングを提案する。
我々は,アルゴリズムの有効性を,精密農業とAutoMLの2つの実世界の応用例で示す。
論文 参考訳（メタデータ） (2023-11-02T12:46:03Z) - Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and
Luck [35.6883212537938]
オフラインスパースパリティ学習は,多層パーセプトロンの勾配に基づくトレーニングにおいて,統計的クエリの下限を許容する教師付き分類問題である。
理論上, 実験上, 疎初期化とネットワーク幅の増大がサンプル効率を著しく向上させることを示す。
また,合成スパースパリティタスクは,軸方向の特徴学習を必要とする現実的な問題のプロキシとして有用であることを示す。
論文 参考訳（メタデータ） (2023-09-07T15:52:48Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Replicable Reinforcement Learning [15.857503103543308]
本稿では、並列値反復のための証明可能なレプリカブルアルゴリズムと、エピソード設定における証明可能なR-maxのレプリカブルバージョンを提供する。
これらは制御問題に対する最初の公式なレプリカ化結果であり、バッチ学習設定とは異なるレプリケーションの課題を提示している。
論文 参考訳（メタデータ） (2023-05-24T16:05:15Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - A Simplicity Bubble Problem in Formal-Theoretic Learning Systems [1.7996150751268578]
機械学習への現在のアプローチは、十分に大きなデータセットによって、自然または人工的に常に騙され得ることを示す。
本稿では,この誤認現象を回避するための枠組みと追加の経験的条件について論じる。
論文 参考訳（メタデータ） (2021-12-22T23:44:47Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。
エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。
これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
論文 参考訳（メタデータ） (2020-09-15T17:28:42Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Learning with Optimized Random Features: Exponential Speedup by Quantum
Machine Learning without Sparsity and Low-Rank Assumptions [8.08640000394814]
我々は,実行時特性を最適化した分布からサンプリングする量子アルゴリズムを開発した。
我々のアルゴリズムは、このサンプリングタスクの既知の古典的アルゴリズムと比較して、D$の指数的な高速化を実現している。
論文 参考訳（メタデータ） (2020-04-22T18:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。