論文の概要: Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree

• arxiv url: http://arxiv.org/abs/2002.00492v2
• Date: Tue, 17 Nov 2020 23:29:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-04 19:55:54.863018
• Title: Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree
• Title（参考訳）: オーバーフィッティングは基礎追跡には無害ですが ある程度は
• Authors: Peizhong Ju, Xiaojun Lin, Jia Liu
• Abstract要約: 圧縮センシング文献におけるBasis Pursuit (BP) として知られる$ell$-normを最小化するオーバーフィッティング法について検討した。 広い範囲の$p$に対して、サンプル数$n$で指数関数的に増加する極限に対して、BPのモデル誤差は$p$で減少する値によって上界であることが示される。
• 参考スコア（独自算出の注目度）: 20.408693108187542
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, there have been significant interests in studying the so-called "double-descent" of the generalization error of linear regression models under the overparameterized and overfitting regime, with the hope that such analysis may provide the first step towards understanding why overparameterized deep neural networks (DNN) still generalize well. However, to date most of these studies focused on the min $\ell_2$-norm solution that overfits the data. In contrast, in this paper we study the overfitting solution that minimizes the $\ell_1$-norm, which is known as Basis Pursuit (BP) in the compressed sensing literature. Under a sparse true linear regression model with $p$ i.i.d. Gaussian features, we show that for a large range of $p$ up to a limit that grows exponentially with the number of samples $n$, with high probability the model error of BP is upper bounded by a value that decreases with $p$. To the best of our knowledge, this is the first analytical result in the literature establishing the double-descent of overfitting BP for finite $n$ and $p$. Further, our results reveal significant differences between the double-descent of BP and min $\ell_2$-norm solutions. Specifically, the double-descent upper-bound of BP is independent of the signal strength, and for high SNR and sparse models the descent-floor of BP can be much lower and wider than that of min $\ell_2$-norm solutions.
• Abstract（参考訳）: 近年、過パラメータ化・過適合化体制下での線形回帰モデルの一般化誤差のいわゆる「二重発散」の研究に大きな関心が寄せられ、なぜ過パラメータ化深層ニューラルネットワーク(DNN)がまだ一般化されているのかを理解するための第一歩として期待されている。 しかしながら、これらの研究のほとんどは、データに過度に適合するmin $\ell_2$-normソリューションに焦点を当てている。 対照的に,本研究では圧縮センシング文献において基底追従(bp)として知られる$\ell_1$-normを最小化するオーバーフィッティング解について検討する。 p$ i.i.d.ガウス的特徴を持つまばらな真の線形回帰モデルの下では、サンプル数n$で指数関数的に増加する限界まで、広範囲の p$ に対して、bp のモデル誤差は、$p$ で減少する値によって上限を上回ることを示します。 我々の知る限りでは、これは文献における最初の分析結果であり、有限$n$と$p$に対する過剰適合BPの二重双曲性を確立する。 さらに, BPとmin $\ell_2$-norm溶液の二重発色に有意な差が認められた。 具体的には、BPの二重蛍光上界は信号強度とは独立であり、高いSNRおよびスパースモデルでは、BPの降下床はmin$\ell_2$-norm溶液よりもはるかに小さく、より広い。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Scaling Laws in Linear Regression: Compute, Parameters, and Data [86.48154162485712]
  無限次元線形回帰セットアップにおけるスケーリング法則の理論について検討する。 テストエラーの再現可能な部分は$Theta(-(a-1) + N-(a-1)/a)$であることを示す。 我々の理論は経験的ニューラルスケーリング法則と一致し、数値シミュレーションによって検証される。
  論文  参考訳（メタデータ） (2024-06-12T17:53:29Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime [22.666759017118796]
  機械学習の最近の進歩は、トレーニングデータの近くにトレーニングされた過度にパラメータ化されたモデルを使用することによって達成されている。 モデル複雑性と一般化はパラメータ数$p$にどのように依存するか? 特に、RFRRは近似と一般化パワーの直感的なトレードオフを示す。
  論文  参考訳（メタデータ） (2024-03-13T00:59:25Z)
• Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification [16.0817847880416]
  ヒルベルト空間上の様々な線形予測問題を含む統一的なフレームワークを提供する。 誤特定レベル $epsilon$ に対して、これらの推定器は、文献で最もよく知られたレートと一致する、$O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$ の誤差率を達成する。
  論文  参考訳（メタデータ） (2022-01-06T08:51:08Z)
• Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers [13.244654316770815]
  我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。 スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。 PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
  論文  参考訳（メタデータ） (2021-11-04T15:59:44Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes [15.76663241036412]
  モデルがトレーニングのごく一部を記憶している場合、そのソボレフ・セミノルムは低い有界であることを示す。 実験によって初めて、(iv)ミンノルム補間器の堅牢性における多重発色現象が明らかになった。
  論文  参考訳（メタデータ） (2021-06-04T17:52:50Z)
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap [66.75488143823337]
  また, 指数的標本複雑度は, 一定の準最適ギャップを仮定しても, 未だに保持していることを示した。 おそらく驚くことに、これはオンラインrl設定と生成モデル設定の指数関数的な分離を意味する。
  論文  参考訳（メタデータ） (2021-03-23T17:05:54Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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