論文の概要: Vector-output ReLU Neural Network Problems are Copositive Programs:
Convex Analysis of Two Layer Networks and Polynomial-time Algorithms
- arxiv url: http://arxiv.org/abs/2012.13329v1
- Date: Thu, 24 Dec 2020 17:03:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-25 12:51:08.715596
- Title: Vector-output ReLU Neural Network Problems are Copositive Programs:
Convex Analysis of Two Layer Networks and Polynomial-time Algorithms
- Title（参考訳）: ベクトル出力reluニューラルネットワーク問題は共陽性プログラムである:2層ネットワークの凸解析と多項式時間アルゴリズム
- Authors: Arda Sahiner, Tolga Ergen, John Pauly and Mert Pilanci
- Abstract要約: 2層ベクトル無限ReLUニューラルネットワークトレーニング問題の半出力グローバル双対について述べる。
特定の問題のクラスに対して正確であることが保証されるソリューションを提供する。
- 参考スコア（独自算出の注目度）: 29.975118690758126
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We describe the convex semi-infinite dual of the two-layer vector-output ReLU
neural network training problem. This semi-infinite dual admits a finite
dimensional representation, but its support is over a convex set which is
difficult to characterize. In particular, we demonstrate that the non-convex
neural network training problem is equivalent to a finite-dimensional convex
copositive program. Our work is the first to identify this strong connection
between the global optima of neural networks and those of copositive programs.
We thus demonstrate how neural networks implicitly attempt to solve copositive
programs via semi-nonnegative matrix factorization, and draw key insights from
this formulation. We describe the first algorithms for provably finding the
global minimum of the vector output neural network training problem, which are
polynomial in the number of samples for a fixed data rank, yet exponential in
the dimension. However, in the case of convolutional architectures, the
computational complexity is exponential in only the filter size and polynomial
in all other parameters. We describe the circumstances in which we can find the
global optimum of this neural network training problem exactly with
soft-thresholded SVD, and provide a copositive relaxation which is guaranteed
to be exact for certain classes of problems, and which corresponds with the
solution of Stochastic Gradient Descent in practice.
- Abstract（参考訳）: 本稿では2層ベクトル出力ReLUニューラルネットワークトレーニング問題の凸半無限双対について述べる。
この半無限双対は有限次元表現を許すが、その支持は特徴付けが難しい凸集合上のものである。
特に,非凸ニューラルネットワークトレーニング問題は,有限次元凸コ陽性プログラムと等価であることを示す。
私たちの研究は、ニューラルネットワークのグローバルな最適化と、共陽性プログラムの強いつながりを初めて特定しました。
そこで本研究では,ニューラルネットワークが半負の行列因子分解によって共負のプログラムを暗黙的に解こうとしていることを示す。
本稿では,ベクトル出力ニューラルネットワークトレーニング問題の最小値を求めるアルゴリズムについて述べる。これは固定データランクのサンプル数に多項式であるが,次元は指数関数的である。
しかし、畳み込みアーキテクチャの場合、計算複雑性は他の全てのパラメータのフィルタサイズと多項式のみにおいて指数関数的である。
本稿では,このニューラルネットワーク学習問題のグローバル最適化をソフトスレッショルドsvdを用いて正確に把握し,ある種の問題に対して正確であることが保証され,実際に確率的勾配降下の解に対応する共負緩和を提供する。
関連論文リスト
- LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。
本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文 参考訳（メタデータ） (2024-07-18T22:05:21Z) - Path Regularization: A Convexity and Sparsity Inducing Regularization
for Parallel ReLU Networks [75.33431791218302]
本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。
我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
論文 参考訳（メタデータ） (2021-10-18T18:00:36Z) - Global Optimality Beyond Two Layers: Training Deep ReLU Networks via
Convex Programs [39.799125462526234]
我々は凸最適化のレンズを通して隠れ正規化機構を明らかにするための新しい統一フレームワークを開発した。
我々は、合成データセットと実データセットの両方を含む実験を通して、理論的結果を数値的に検証する。
論文 参考訳（メタデータ） (2021-10-11T18:00:30Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - Achieving Small Test Error in Mildly Overparameterized Neural Networks [30.664282759625948]
時間内にこれらの点の1つを見つけるアルゴリズムを示す。
さらに、我々は、完全に接続されたニューラルネットワークのために、データ分布に追加の仮定で、時間アルゴリズムがあることを証明します。
論文 参考訳（メタデータ） (2021-04-24T06:47:20Z) - Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization
of Polynomial Activation Neural Networks in Fully Polynomial-Time [31.94590517036704]
2次活性化を持つ2層数値ネットワークの完全凸最適化定式化を考案する。
本研究では,全入力データの複雑度とサンプルサイズが半定常的なニューラル・グローバル最適化であることを示した。
提案手法は, 標準バックプロパゲーション法に比べ, テスト精度が大幅に向上した。
論文 参考訳（メタデータ） (2021-01-07T08:43:01Z) - Neural network approaches to point lattice decoding [6.025026882312586]
voronoi-reduced基底は二元集合への解の空間を制限するために導入された。
CPWL復号関数におけるアフィンの個数を数え、復号問題の複雑さを特徴づける。
論文 参考訳（メタデータ） (2020-12-13T10:53:34Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z) - The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural
Networks: an Exact Characterization of the Optimal Solutions [51.60996023961886]
コーン制約のある凸最適化プログラムを解くことにより,グローバルな2層ReLUニューラルネットワークの探索が可能であることを示す。
我々の分析は新しく、全ての最適解を特徴づけ、最近、ニューラルネットワークのトレーニングを凸空間に持ち上げるために使われた双対性に基づく分析を活用できない。
論文 参考訳（メタデータ） (2020-06-10T15:38:30Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。