論文の概要: Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes
- arxiv url: http://arxiv.org/abs/2311.10972v1
- Date: Sat, 18 Nov 2023 04:41:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-22 13:07:47.089321
- Title: Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes
- Title（参考訳）: ReLUネットワークトレーニングのための多項式時間解:Max-CutとZonotopeによる複雑度分類
- Authors: Yifei Wang and Mert Pilanci
- Abstract要約: 我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
- 参考スコア（独自算出の注目度）: 70.52097560486683
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the complexity of training a two-layer ReLU neural network
with weight decay regularization. Previous research has shown that the optimal
solution of this problem can be found by solving a standard cone-constrained
convex program. Using this convex formulation, we prove that the hardness of
approximation of ReLU networks not only mirrors the complexity of the Max-Cut
problem but also, in certain special cases, exactly corresponds to it. In
particular, when $\epsilon\leq\sqrt{84/83}-1\approx 0.006$, we show that it is
NP-hard to find an approximate global optimizer of the ReLU network objective
with relative error $\epsilon$ with respect to the objective value. Moreover,
we develop a randomized algorithm which mirrors the Goemans-Williamson rounding
of semidefinite Max-Cut relaxations. To provide polynomial-time approximations,
we classify training datasets into three categories: (i) For orthogonal
separable datasets, a precise solution can be obtained in polynomial-time. (ii)
When there is a negative correlation between samples of different classes, we
give a polynomial-time approximation with relative error $\sqrt{\pi/2}-1\approx
0.253$. (iii) For general datasets, the degree to which the problem can be
approximated in polynomial-time is governed by a geometric factor that controls
the diameter of two zonotopes intrinsic to the dataset. To our knowledge, these
results present the first polynomial-time approximation guarantees along with
first hardness of approximation results for regularized ReLU networks.
- Abstract（参考訳）: 重み減衰正則化を用いた2層ReLUニューラルネットワークのトレーニングの複雑さについて検討する。
従来の研究では、この問題の最適解は、標準コーン拘束凸プログラムを解くことで得られることが示されている。
この凸定式化を用いて、ReLUネットワークの近似の硬さがマックス・クート問題の複雑さを反映するだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$\epsilon\leq\sqrt{84/83}-1\approx 0.006$の場合、目的値に関して相対誤差$\epsilon$を持つreluネットワーク目的の近似大域最適化器を見つけることはnp困難である。
さらに,半定値マックスカット緩和のゴーマンス・ウィリアムソン丸みを反映するランダム化アルゴリズムを開発した。
多項式時間近似を提供するため、トレーニングデータセットを3つのカテゴリに分類する。
(i)直交分離可能なデータセットの場合、多項式時間で正確な解が得られる。
(ii)異なるクラスのサンプル間に負の相関がある場合、相対誤差$\sqrt{\pi/2}-1\approx 0.253$の多項式時間近似を与える。
(iii)一般データセットでは、問題を多項式時間で近似できる程度は、データセットに固有の2つのゾノトペの直径を制御する幾何学的因子によって制御される。
これらの結果は,正規化reluネットワークに対する近似結果の第一硬度とともに,多項式時間近似の最初の保証を示す。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics [21.55547541297847]
平均場ランゲヴィンアルゴリズムを用いて学習した2層ニューラルネットワークを用いて,高次元のマルチインデックスモデルを学習する問題について検討する。
軽度の分布仮定の下では、サンプルと計算の複雑さの両方を制御する実効次元 $d_mathrmeff$ を特徴づける。
論文 参考訳（メタデータ） (2024-08-14T02:13:35Z) - Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
本稿では,2層ReLULUネットワーク間における重み減衰と凸緩和の最適性ギャップについて検討する。
私たちの研究は、なぜローカルメソッドがうまく機能するのかを理解することに新たな光を当てています。
論文 参考訳（メタデータ） (2024-02-06T01:29:35Z) - From Monte Carlo to neural networks approximations of boundary value problems [0.0]
ポアソン方程式の解はモンテカルロ法により超ノルムで数値的に近似できることを示す。
また、得られたモンテカルロ解法は、ポアソン問題に対する建設的なReLUディープニューラルネットワーク(DNN)の解法を示す。
論文 参考訳（メタデータ） (2022-09-03T14:17:58Z) - 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) - 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) - Implicit Convex Regularizers of CNN Architectures: Convex Optimization
of Two- and Three-Layer Networks in Polynomial Time [70.15611146583068]
本稿では,ReLUアクティベーションを用いた畳み込みニューラルネットワーク(CNN)のトレーニングについて検討する。
我々は,データサンプル数,ニューロン数,データ次元に関して,厳密な凸最適化を導入する。
論文 参考訳（メタデータ） (2020-06-26T04:47:20Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。