論文の概要: When Hardness of Approximation Meets Hardness of Learning
- arxiv url: http://arxiv.org/abs/2008.08059v2
- Date: Sun, 23 Aug 2020 13:46:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 20:54:12.376998
- Title: When Hardness of Approximation Meets Hardness of Learning
- Title（参考訳）: 近似の硬さが学習の硬さと出会うとき
- Authors: Eran Malach, Shai Shalev-Shwartz
- Abstract要約: 線形クラスと浅層ネットワークを用いた近似の硬さと,相関クエリと勾配差を用いた学習の硬さを両立させる単一の硬さ特性を示す。
これにより、パリティ関数、DNF式および$AC0$回路の近似の硬さと学習性に関する新たな結果が得られる。
- 参考スコア（独自算出の注目度）: 35.39956227364153
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A supervised learning algorithm has access to a distribution of labeled
examples, and needs to return a function (hypothesis) that correctly labels the
examples. The hypothesis of the learner is taken from some fixed class of
functions (e.g., linear classifiers, neural networks etc.). A failure of the
learning algorithm can occur due to two possible reasons: wrong choice of
hypothesis class (hardness of approximation), or failure to find the best
function within the hypothesis class (hardness of learning). Although both
approximation and learnability are important for the success of the algorithm,
they are typically studied separately. In this work, we show a single hardness
property that implies both hardness of approximation using linear classes and
shallow networks, and hardness of learning using correlation queries and
gradient-descent. This allows us to obtain new results on hardness of
approximation and learnability of parity functions, DNF formulas and $AC^0$
circuits.
- Abstract（参考訳）: 教師付き学習アルゴリズムはラベル付きサンプルの分布にアクセスでき、サンプルを正しくラベル付けする関数(仮説)を返す必要がある。
学習者の仮説は、いくつかの固定された種類の関数(線形分類器、ニューラルネットワークなど)から取られる。
学習アルゴリズムの失敗は、仮説クラス(近似のハードネス)の間違った選択、あるいは仮説クラス(学習のハードネス)の中で最高の関数を見つけるのに失敗する2つの理由により起こりうる。
近似も学習性もアルゴリズムの成功には重要であるが、通常は別々に研究されている。
本研究では,線形クラスと浅層ネットワークを用いた近似の硬さと,相関クエリと勾配descentを用いた学習の硬さを示唆する単一硬さ特性を示す。
これにより、パリティ関数、DNF式および$AC^0$回路の近似と学習性に関する新しい結果が得られる。
関連論文リスト
- Robustly Learning Single-Index Models via Alignment Sharpness [40.886706402941435]
単行数モデル学習の問題点を,無知モデルにおける損失$L2$で検討する。
最適損失に対する定数係数近似を達成し,効率的な学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-27T18:48:07Z) - Learnability, Sample Complexity, and Hypothesis Class Complexity for
Regression Models [10.66048003460524]
この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。
提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。
これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
論文 参考訳（メタデータ） (2023-03-28T15:59:12Z) - Neural Active Learning on Heteroskedastic Distributions [29.01776999862397]
ヘテロスケダスティックデータセット上でのアクティブ学習アルゴリズムの破滅的な失敗を実証する。
本稿では,各データポイントにモデル差分スコアリング関数を組み込んで,ノイズの多いサンプルとサンプルクリーンなサンプルをフィルタするアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-02T07:30:19Z) - Offline Reinforcement Learning with Differentiable Function
Approximation is Provably Efficient [65.08966446962845]
歴史的データを用いて意思決定戦略を最適化することを目的としたオフライン強化学習は、現実の応用に広く適用されている。
微分関数クラス近似(DFA)を用いたオフライン強化学習の検討から一歩踏み出した。
最も重要なことは、悲観的な適合Q-ラーニングアルゴリズムを解析することにより、オフライン微分関数近似が有効であることを示すことである。
論文 参考訳（メタデータ） (2022-10-03T07:59:42Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。
このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
論文 参考訳（メタデータ） (2022-06-01T23:26:51Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-08-22T16:00:45Z) - A Theory of Universal Learning [26.51949485387526]
普遍的な学習の確率は3つしかないことを示す。
任意の概念クラスの学習曲線は指数的あるいは任意に遅い速度で減衰することを示す。
論文 参考訳（メタデータ） (2020-11-09T15:10:32Z) - Learning What Makes a Difference from Counterfactual Examples and
Gradient Supervision [57.14468881854616]
ニューラルネットワークの一般化能力を改善するための補助的学習目標を提案する。
我々は、異なるラベルを持つ最小差の例のペア、すなわち反ファクトまたはコントラストの例を使用し、タスクの根底にある因果構造を示す信号を与える。
このテクニックで訓練されたモデルは、配布外テストセットのパフォーマンスを向上させる。
論文 参考訳（メタデータ） (2020-04-20T02:47:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。