論文の概要: Convex Relaxations of ReLU Neural Networks Approximate Global Optima in
Polynomial Time
- arxiv url: http://arxiv.org/abs/2402.03625v1
- Date: Tue, 6 Feb 2024 01:29:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 17:08:28.568920
- Title: Convex Relaxations of ReLU Neural Networks Approximate Global Optima in
Polynomial Time
- Title(参考訳): 多項式時間におけるReLUニューラルネットワーク近似グローバルオプティマの凸緩和
- Authors: Sungyoon Kim, Mert Pilanci
- Abstract要約: 本稿では, 重み劣化と凸緩和に則った2層ReLUネットワーク間の最適性ギャップについて述べる。
トレーニングデータがランダムである場合、元の問題と緩和の間の相対的な最適性ギャップは、サンプルの勾配によって境界付けられることを示す。
- 参考スコア(独自算出の注目度): 54.01594785269913
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study the optimality gap between two-layer ReLU networks
regularized with weight decay and their convex relaxations. We show that when
the training data is random, the relative optimality gap between the original
problem and its relaxation can be bounded by a factor of $O(\sqrt{\log n})$,
where $n$ is the number of training samples. A simple application leads to a
tractable polynomial-time algorithm that is guaranteed to solve the original
non-convex problem up to a logarithmic factor. Moreover, under mild
assumptions, we show that with random initialization on the parameters local
gradient methods almost surely converge to a point that has low training loss.
Our result is an exponential improvement compared to existing results and sheds
new light on understanding why local gradient methods work well.
- Abstract(参考訳): 本稿では,2層ReLUネットワーク間における重み劣化と凸緩和の最適性ギャップについて検討する。
トレーニングデータがランダムである場合、元の問題と緩和の間の相対的最適性ギャップは、トレーニングサンプルの数である$n$ の係数 o(\sqrt{\log n})$ で境界される。
単純な応用は、元の非凸問題を対数係数まで解くことが保証される、扱いやすい多項式時間アルゴリズムに繋がる。
さらに, 軽度の仮定の下では, パラメータのランダム初期化により, 局所勾配法がトレーニング損失の少ない点にほぼ確実に収束することを示す。
その結果,既存の結果と比較して指数関数的な改善が得られ,局所勾配法がうまく機能する理由の解明に新たな光を当てることができた。
関連論文リスト
- Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳(メタデータ) (2023-11-18T04:41:07Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model
Classes and Cone Decompositions [41.337814204665364]
ReLUアクティベーション機能を持つ2層ニューラルネットワークの凸最適化アルゴリズムを開発した。
凸ゲート型ReLUモデルでは,ReLUトレーニング問題に対するデータ依存の近似バウンダリが得られることを示す。
論文 参考訳(メタデータ) (2022-02-02T23:50:53Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳(メタデータ) (2021-11-12T01:51:50Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳(メタデータ) (2021-06-06T19:08:53Z) - Combining resampling and reweighting for faithful stochastic
optimization [1.52292571922932]
損失関数が複数の項の和であるとき、一般的な方法は勾配降下である。
損失関数における複数の項のリプシッツ定数の差は、異なる最小値における異なる分散への勾配降下を引き起こすことを示す。
論文 参考訳(メタデータ) (2021-05-31T04:21:25Z) - Sparse Signal Reconstruction for Nonlinear Models via Piecewise Rational
Optimization [27.080837460030583]
劣化した信号を非線形歪みと限られたサンプリングレートで再構成する手法を提案する。
本手法は,不正確な適合項と罰則として定式化する。
シミュレーションの利点の観点から,この問題の活用方法を示す。
論文 参考訳(メタデータ) (2020-10-29T09:05:19Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。