論文の概要: The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals

• arxiv url: http://arxiv.org/abs/2102.04401v1
• Date: Mon, 8 Feb 2021 18:06:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-09 15:47:17.306578
• Title: The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
• Title（参考訳）: ガウス行列における予知学習における多項式回帰の最適性
• Authors: Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
• Abstract要約: そこで我々は,二元性LPを用いて,多種多様な問題に対するサンプルのハードファミリーを見つける手法を開発した。 L1$-regression は本質的には最適であり、概念クラスを学習する際の計算困難さは、クラスから任意の関数を近似するのに要する次数と密接に関連していることが示される。
• 参考スコア（独自算出の注目度）: 47.81107898315438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of agnostic learning under the Gaussian distribution. We develop a method for finding hard families of examples for a wide class of problems by using LP duality. For Boolean-valued concept classes, we show that the $L^1$-regression algorithm is essentially best possible, and therefore that the computational difficulty of agnostically learning a concept class is closely related to the polynomial degree required to approximate any function from the class in $L^1$-norm. Using this characterization along with additional analytic tools, we obtain optimal SQ lower bounds for agnostically learning linear threshold functions and the first non-trivial SQ lower bounds for polynomial threshold functions and intersections of halfspaces. We also develop an analogous theory for agnostically learning real-valued functions, and as an application prove near-optimal SQ lower bounds for agnostically learning ReLUs and sigmoids.
• Abstract（参考訳）: ガウス分布の下での学習の診断の問題を研究する。 本研究では, LP双対性を用いて, 幅広い問題例のハードファミリを求める手法を開発した。 ブール値の概念クラスに対して、$L^1$-regressionアルゴリズムは本質的に最適であり、したがって概念クラスを不可知的に学習する計算困難さは、クラスから任意の関数をノルムで近似するのに必要となる多項式次数と密接に関連していることを示す。 この特徴とさらなる解析ツールを用いて、線形しきい値関数を不可知的に学習する最適なSQ下界と、多項式しきい値関数とハーフ空間の交叉に対する最初の非自明なSQ下界を得る。 また、実数値関数を学習するための類似理論を開発し、ReLUやシグモイドを学習するための準最適SQ下限を証明した。

関連論文リスト

• Robustly Learning Single-Index Models via Alignment Sharpness [40.886706402941435]
  単行数モデル学習の問題点を,無知モデルにおける損失$L2$で検討する。 最適損失に対する定数係数近似を達成し,効率的な学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-27T18:48:07Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [66.26739783789387]
  我々は、強化学習のための新しいアルゴリズム、MQL-UCBを用いたモノトニックQ-Learningを提案する。 MQL-UCBは、$tildeO(dsqrtHK)$の最小限の後悔を実現する。 本研究は,非線形関数近似を用いたサンプル効率およびデプロイメント効率のよいQ-ラーニングの設計に重点を置いている。
  論文  参考訳（メタデータ） (2023-11-26T08:31:57Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)
• Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
  ガウスの下の半空間を不可知的に学習する問題を考察する。 我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
  論文  参考訳（メタデータ） (2021-02-10T18:40:44Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Statistical-Query Lower Bounds via Functional Gradients [19.5924910463796]
  我々は、寛容$n- (1/epsilon)b$の統計クエリアルゴリズムは、一定の$bに対して少なくとも$2nc epsilon$クエリを使用する必要があることを示す。 実数値学習では珍しいSQ学習アルゴリズムが一般的である(相関学習とは対照的に)。
  論文  参考訳（メタデータ） (2020-06-29T05:15:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。