論文の概要: Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence

• arxiv url: http://arxiv.org/abs/2411.08798v1
• Date: Wed, 13 Nov 2024 17:25:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-14 16:11:55.334857
• Title: Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence
• Title（参考訳）: 勾配流を伴うガウス多次元モデルの学習:時間複雑度と方向収束
• Authors: Berfin Simsek, Amire Bendjeddou, Daniel Hsu,
• Abstract要約: この研究は、相関損失を用いてマルチインデックス関数を近似するニューラルネットワークモデルのフローダイナミクスに焦点を当てる。 指数ベクトル間のドット積が一定の閾値を超えると、相関損失は失敗することを示す。
• 参考スコア（独自算出の注目度）: 11.06159595271586
• License:
• Abstract: This work focuses on the gradient flow dynamics of a neural network model that uses correlation loss to approximate a multi-index function on high-dimensional standard Gaussian data. Specifically, the multi-index function we consider is a sum of neurons $f^*(x) \!=\! \sum_{j=1}^k \! \sigma^*(v_j^T x)$ where $v_1, \dots, v_k$ are unit vectors, and $\sigma^*$ lacks the first and second Hermite polynomials in its Hermite expansion. It is known that, for the single-index case ($k\!=\!1$), overcoming the search phase requires polynomial time complexity. We first generalize this result to multi-index functions characterized by vectors in arbitrary directions. After the search phase, it is not clear whether the network neurons converge to the index vectors, or get stuck at a sub-optimal solution. When the index vectors are orthogonal, we give a complete characterization of the fixed points and prove that neurons converge to the nearest index vectors. Therefore, using $n \! \asymp \! k \log k$ neurons ensures finding the full set of index vectors with gradient flow with high probability over random initialization. When $ v_i^T v_j \!=\! \beta \! \geq \! 0$ for all $i \neq j$, we prove the existence of a sharp threshold $\beta_c \!=\! c/(c+k)$ at which the fixed point that computes the average of the index vectors transitions from a saddle point to a minimum. Numerical simulations show that using a correlation loss and a mild overparameterization suffices to learn all of the index vectors when they are nearly orthogonal, however, the correlation loss fails when the dot product between the index vectors exceeds a certain threshold.
• Abstract（参考訳）: この研究は、相関損失を用いて高次元標準ガウスデータ上の多重インデックス関数を近似するニューラルネットワークモデルの勾配流れのダイナミクスに焦点を当てる。 具体的には、我々が考える多重インデックス関数は、ニューロンの和 $f^*(x) \! =\! \sum_{j=1}^k \! v_1, \dots, v_k$ は単位ベクトルであり、$\sigma^*$ はそのエルミート展開において第一および第二エルミート多項式を欠いている。 シングルインデックスの場合($k\! =\! 探索フェーズを克服するには多項式時間の複雑さが必要となる。 まず、この結果を任意の方向のベクトルによって特徴づけられる多重インデックス関数に一般化する。 サーチフェーズ後、ネットワークニューロンがインデックスベクトルに収束するか、あるいは準最適解で立ち往生するかは明らかでない。 指数ベクトルが直交であるとき、固定点の完全な特徴づけを与え、ニューロンが最も近い指数ベクトルに収束することを証明する。 したがって$n \! \asymp \! k \log k$ ニューロンは、ランダム初期化よりも高い確率で勾配流を持つ指数ベクトルの完全な集合を見つけることを保証している。 v_i^T v_j \! =\! \beta \! \geq \! 0$ for all $i \neq j$, we prove the existence of a sharp threshold $\beta_c \! =\! c/(c+k)$ ここで、インデックスベクトルの平均を計算する固定点は、サドル点から最小点へ遷移する。 数値シミュレーションでは、相関損失と緩やかな過パラメータ化を用いることで、ほぼ直交するときにすべての指標ベクトルを学習できるが、指数ベクトル間のドット積が一定の閾値を超えると相関損失は失敗する。

関連論文リスト

• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Universality of max-margin classifiers [10.797131009370219]
  非ガウス的特徴に対する誤分類誤差の高次元普遍性と大域化写像の役割について検討する。 特に、オーバーパラメトリゼーションしきい値と一般化誤差はより単純なモデルで計算できる。
  論文  参考訳（メタデータ） (2023-09-29T22:45:56Z)
• 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)
• Convergence of a Normal Map-based Prox-SGD Method under the KL Inequality [0.0]
  我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
  論文  参考訳（メタデータ） (2023-05-10T01:12:11Z)
• Generalization and Stability of Interpolating Neural Networks with Minimal Width [37.908159361149835]
  補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。 トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。 m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
  論文  参考訳（メタデータ） (2023-02-18T05:06:15Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics [8.90202564665576]
  一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。 3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
  論文  参考訳（メタデータ） (2022-03-19T07:26:45Z)
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
  2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。 過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
  論文  参考訳（メタデータ） (2020-07-09T07:09:28Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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