論文の概要: Training (Overparametrized) Neural Networks in Near-Linear Time
- arxiv url: http://arxiv.org/abs/2006.11648v2
- Date: Wed, 9 Dec 2020 02:02:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 22:39:31.639578
- Title: Training (Overparametrized) Neural Networks in Near-Linear Time
- Title（参考訳）: 近距離時間でのトレーニング(Overparametrized)ニューラルネットワーク
- Authors: Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein
- Abstract要約: 本稿では,ReparamLUネットワークをトレーニングするための[CGH+1]アルゴリズムの高速化について述べる。
我々のアルゴリズムの中心はガウスニュートンを$ell$-reconditionとして再構成することである。
- 参考スコア（独自算出の注目度）: 21.616949485102342
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The slow convergence rate and pathological curvature issues of first-order
gradient methods for training deep neural networks, initiated an ongoing effort
for developing faster $\mathit{second}$-$\mathit{order}$ optimization
algorithms beyond SGD, without compromising the generalization error. Despite
their remarkable convergence rate ($\mathit{independent}$ of the training batch
size $n$), second-order algorithms incur a daunting slowdown in the
$\mathit{cost}$ $\mathit{per}$ $\mathit{iteration}$ (inverting the Hessian
matrix of the loss function), which renders them impractical. Very recently,
this computational overhead was mitigated by the works of [ZMG19,CGH+19},
yielding an $O(mn^2)$-time second-order algorithm for training two-layer
overparametrized neural networks of polynomial width $m$.
We show how to speed up the algorithm of [CGH+19], achieving an
$\tilde{O}(mn)$-time backpropagation algorithm for training (mildly
overparametrized) ReLU networks, which is near-linear in the dimension ($mn$)
of the full gradient (Jacobian) matrix. The centerpiece of our algorithm is to
reformulate the Gauss-Newton iteration as an $\ell_2$-regression problem, and
then use a Fast-JL type dimension reduction to $\mathit{precondition}$ the
underlying Gram matrix in time independent of $M$, allowing to find a
sufficiently good approximate solution via $\mathit{first}$-$\mathit{order}$
conjugate gradient. Our result provides a proof-of-concept that advanced
machinery from randomized linear algebra -- which led to recent breakthroughs
in $\mathit{convex}$ $\mathit{optimization}$ (ERM, LPs, Regression) -- can be
carried over to the realm of deep learning as well.
- Abstract（参考訳）: ディープニューラルネットワークのトレーニングのための1次勾配法の緩やかな収束率と病理学的曲率問題により、一般化エラーを補うことなく、SGDを超えてより高速な$\mathit{second}$-$\mathit{order}$最適化アルゴリズムの開発が進められた。
その顕著な収束率($\mathit{independent}$ of the training batch size $n$)にもかかわらず、二階アルゴリズムは$\mathit{cost}$ $\mathit{per}$ $\mathit{iteration}$(損失関数のヘシアン行列を反転させる)という大胆なスローダウンを引き起こします。
最近では、この計算オーバーヘッドは [ZMG19,CGH+19} の研究により緩和され、多項式幅$m$の2層過パラメータニューラルネットワークをトレーニングするための$O(mn^2)$-time 2次アルゴリズムが得られた。我々は、フル勾配(ヤコビアン)行列の次元(mn$)のほぼ直線であるトレーニング用$\tilde{O}(mn)$-timeバックプロパゲーションアルゴリズム(英語版)のアルゴリズムをいかに高速化するかを示す。
我々のアルゴリズムの中心は、ガウス・ニュートンの反復を$\ell_2$-regression問題として再構成し、その後、$m$とは独立に、基礎となるグラム行列を$\mathit{precondition}$に高速jl型の次元縮小を用いて、$\mathit{first}$-$\mathit{order}$ 共役勾配で十分良い近似解を見つけることである。
我々の結果は、ランダム化された線形代数から先進的な機械($\mathit{convex}$ $\mathit{optimization}$ (ERM, LPs, Regression))が深層学習の領域にもたらされるという概念実証を提供する。
関連論文リスト
- Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - 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) - Nearly Optimal Algorithms with Sublinear Computational Complexity for
Online Kernel Regression [13.510889339096117]
後悔と計算コストのトレードオフは、オンラインカーネル回帰の根本的な問題である。
AOGD-ALDとNONS-ALDの2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-14T07:39:09Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。
以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
論文 参考訳（メタデータ） (2020-10-22T00:32:12Z) - 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) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳（メタデータ） (2020-07-09T07:09:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。