論文の概要: Toward $L_\infty$-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields

• arxiv url: http://arxiv.org/abs/2305.00322v1
• Date: Sat, 29 Apr 2023 18:33:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 15:53:57.810828
• Title: Toward $L_\infty$-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields
• Title（参考訳）: l_\infty$-recovery of nonlinear functions: a polynomial sample complexity bound for gaussian random fields
• Authors: Kefan Dong, Tengyu Ma
• Abstract要約: 多くの機械学習アプリケーションは、入力ドメイン全体、すなわち$L_infty$-errorで最小ケースエラーの関数を学習する必要がある。 既存の理論的研究の多くは、$L$-errorのような平均エラーの回復を保証するだけである。 本稿では, 地絡関数のランダム性を生かして, 不合理性以外のいくつかの初期ステップについて述べる。
• 参考スコア（独自算出の注目度）: 35.76184529520015
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Many machine learning applications require learning a function with a small worst-case error over the entire input domain, that is, the $L_\infty$-error, whereas most existing theoretical works only guarantee recovery in average errors such as the $L_2$-error. $L_\infty$-recovery from polynomial samples is even impossible for seemingly simple function classes such as constant-norm infinite-width two-layer neural nets. This paper makes some initial steps beyond the impossibility results by leveraging the randomness in the ground-truth functions. We prove a polynomial sample complexity bound for random ground-truth functions drawn from Gaussian random fields. Our key technical novelty is to prove that the degree-$k$ spherical harmonics components of a function from Gaussian random field cannot be spiky in that their $L_\infty$/$L_2$ ratios are upperbounded by $O(d \sqrt{\ln k})$ with high probability. In contrast, the worst-case $L_\infty$/$L_2$ ratio for degree-$k$ spherical harmonics is on the order of $\Omega(\min\{d^{k/2},k^{d/2}\})$.
• Abstract（参考訳）: 多くの機械学習アプリケーションは入力領域全体、すなわち$L_\infty$-errorという小さな最悪のエラーを持つ関数を学習する必要があるが、既存の理論では$L_2$-errorのような平均エラーの回復しか保証していない。 多項式サンプルからの$L_\infty$-recoveryは、定数ノルム無限幅2層ニューラルネットのような一見単純な関数クラスでは不可能である。 本稿では, 地中関数のランダム性を活用することにより, 予測不可能性を超えた初期ステップを提案する。 ガウス確率場から引き出されたランダム接地構造関数に束縛された多項式サンプル複雑性を証明した。 我々の重要な技術的ノベルティは、ガウス確率場からの函数の次数-$k$球面調和成分が、その$L_\infty$/$L_2$比が高い確率で$O(d \sqrt{\ln k})$で上界であることを証明することである。 対照的に、次数-k$球面調和に対する最悪の場合の$l_\infty$/$l_2$比は、$\omega(\min\{d^{k/2},k^{d/2}\})$である。

関連論文リスト

• Random features and polynomial rules [0.0]
  本稿では,ガウスデータを用いた一般教師付き学習問題に対するランダム特徴モデルの性能の一般化について述べる。 我々は、$Dto infty$と$P/DK$,$N/DL$の間の少なくとも一方が有限である極限から遠く離れた良い合意を見出す。
  論文  参考訳（メタデータ） (2024-02-15T18:09:41Z)
• 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)
• The $L^\infty$ Learnability of Reproducing Kernel Hilbert Spaces [3.2931415075553576]
  カーネル空間の学習可能性(RKHS)を$Linfty$ノルムで解析する。 球面上のドット積核に対しては、ヒルベルトサンプルを用いて$Linfty$学習が達成できる条件を特定する。
  論文  参考訳（メタデータ） (2023-06-05T12:29:13Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Reverse Euclidean and Gaussian isoperimetric inequalities for parallel sets with applications [0.0]
  例えば、$r$-parallel set in $mathbb Rd$ with volume at most $V$ is upper-bounded by $eTheta(d)V/r$, and its Gaussian surface area are upper-bounded by $max(eTheta(d), eTheta(d)/r)$。 また、$r$-パラレル集合に対するブラン・ミンコフスキーの不等式(英語版)の逆形式を導出し、ガウスの滑らかな確率変数に対する逆エントロピーパワー不等式(英語版)(verse entropy power inequality)を導出する。
  論文  参考訳（メタデータ） (2020-06-16T23:58:54Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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