論文の概要: Statistical-Query Lower Bounds via Functional Gradients

• arxiv url: http://arxiv.org/abs/2006.15812v2
• Date: Thu, 22 Oct 2020 21:10:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 14:11:44.839432
• Title: Statistical-Query Lower Bounds via Functional Gradients
• Title（参考訳）: 関数勾配による統計的照会下限
• Authors: Surbhi Goel, Aravind Gollakota, Adam Klivans
• Abstract要約: 我々は、寛容$n- (1/epsilon)b$の統計クエリアルゴリズムは、一定の$bに対して少なくとも$2nc epsilon$クエリを使用する必要があることを示す。 実数値学習では珍しいSQ学習アルゴリズムが一般的である(相関学習とは対照的に)。
• 参考スコア（独自算出の注目度）: 19.5924910463796
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give the first statistical-query lower bounds for agnostically learning any non-polynomial activation with respect to Gaussian marginals (e.g., ReLU, sigmoid, sign). For the specific problem of ReLU regression (equivalently, agnostically learning a ReLU), we show that any statistical-query algorithm with tolerance $n^{-(1/\epsilon)^b}$ must use at least $2^{n^c} \epsilon$ queries for some constant $b, c > 0$, where $n$ is the dimension and $\epsilon$ is the accuracy parameter. Our results rule out general (as opposed to correlational) SQ learning algorithms, which is unusual for real-valued learning problems. Our techniques involve a gradient boosting procedure for "amplifying" recent lower bounds due to Diakonikolas et al. (COLT 2020) and Goel et al. (ICML 2020) on the SQ dimension of functions computed by two-layer neural networks. The crucial new ingredient is the use of a nonstandard convex functional during the boosting procedure. This also yields a best-possible reduction between two commonly studied models of learning: agnostic learning and probabilistic concepts.
• Abstract（参考訳）: ガウス辺数(例えば、relu、sgmoid、sign)に関して非多項活性化を無知に学習するための最初の統計クエリ下限を与える。 ReLU回帰の特定の問題(等しくはReLUを学習する)に対して、許容値が$n^{-(1/\epsilon)^b}$の統計クエリアルゴリズムは、ある定数$b, c > 0$に対して少なくとも$2^{n^c} \epsilon$クエリを使用しなければならず、$n$は次元であり、$\epsilon$は精度パラメータであることを示す。 実数値学習問題では一般的ではない(相関学習とは対照的に)sq学習アルゴリズムは除外した。 本手法は,2層ニューラルネットワークで計算した関数のSQ次元上でのDiakonikolas et al. (COLT 2020) とGoel et al. (ICML 2020) による最近の下界の「増幅」のための勾配促進手順を含む。 重要な新しい成分は、ブースティング手順中に非標準凸関数を用いることである。 これはまた、一般的に研究されている2つの学習モデル、すなわち無依存学習と確率的概念の間の最善の還元をもたらす。

関連論文リスト

• Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals [10.850101961203752]
  正方形損失目標を持つガウスの辺縁部における任意のバイアスのReLU活性化(あるいはニューロン)を学習する問題を考察する。 我々の主な成果は時間統計クエリ(SQ)アルゴリズムであり、任意のバイアスに対して最初の定数係数近似を与える。 我々のアルゴリズムは、勾配降下に基づく既存のアルゴリズムから興味深い逸脱を示す。
  論文  参考訳（メタデータ） (2024-11-21T17:43:51Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Generalization and Stability of Interpolating Neural Networks with Minimal Width [37.908159361149835]
  補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。 トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。 m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
  論文  参考訳（メタデータ） (2023-02-18T05:06:15Z)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。 また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
  論文  参考訳（メタデータ） (2022-06-26T06:51:31Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  そこで我々は,二元性LPを用いて,多種多様な問題に対するサンプルのハードファミリーを見つける手法を開発した。 L1$-regression は本質的には最適であり、概念クラスを学習する際の計算困難さは、クラスから任意の関数を近似するのに要する次数と密接に関連していることが示される。
  論文  参考訳（メタデータ） (2021-02-08T18:06:32Z)
• Learning to extrapolate using continued fractions: Predicting the critical temperature of superconductor materials [5.905364646955811]
  人工知能(AI)と機械学習(ML)の分野では、未知のターゲット関数 $y=f(mathbfx)$ の近似が共通の目的である。 トレーニングセットとして$S$を参照し、新しいインスタンス$mathbfx$に対して、このターゲット関数を効果的に近似できる低複雑さの数学的モデルを特定することを目的としている。
  論文  参考訳（メタデータ） (2020-11-27T04:57:40Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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