論文の概要: Gradient Descent for Low-Rank Functions

• arxiv url: http://arxiv.org/abs/2206.08257v1
• Date: Thu, 16 Jun 2022 15:58:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-17 16:22:50.151630
• Title: Gradient Descent for Low-Rank Functions
• Title（参考訳）: 低ランク関数の勾配降下
• Authors: Romain Cosson, Ali Jadbabaie, Anuran Makur, Amirhossein Reisizadeh, Devavrat Shah
• Abstract要約: 例えば、深層ニューラルネットワークのトレーニングのような機械学習タスクでは、損失関数は入力のわずか数方向に大きく変化する。 提案した emphLowRank Descent は $mathcalO(plog(1/epsilon))$gd と $mathcalOp/epsilon2)$p/epsilon2)$を識別して $epsilon 勾配関数を求める。
• 参考スコア（独自算出の注目度）: 36.56489593549855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several recent empirical studies demonstrate that important machine learning tasks, e.g., training deep neural networks, exhibit low-rank structure, where the loss function varies significantly in only a few directions of the input space. In this paper, we leverage such low-rank structure to reduce the high computational cost of canonical gradient-based methods such as gradient descent (GD). Our proposed \emph{Low-Rank Gradient Descent} (LRGD) algorithm finds an $\epsilon$-approximate stationary point of a $p$-dimensional function by first identifying $r \leq p$ significant directions, and then estimating the true $p$-dimensional gradient at every iteration by computing directional derivatives only along those $r$ directions. We establish that the "directional oracle complexities" of LRGD for strongly convex and non-convex objective functions are $\mathcal{O}(r \log(1/\epsilon) + rp)$ and $\mathcal{O}(r/\epsilon^2 + rp)$, respectively. When $r \ll p$, these complexities are smaller than the known complexities of $\mathcal{O}(p \log(1/\epsilon))$ and $\mathcal{O}(p/\epsilon^2)$ of {\gd} in the strongly convex and non-convex settings, respectively. Thus, LRGD significantly reduces the computational cost of gradient-based methods for sufficiently low-rank functions. In the course of our analysis, we also formally define and characterize the classes of exact and approximately low-rank functions.
• Abstract（参考訳）: 最近の実験研究では、深層ニューラルネットワークのトレーニングのような重要な機械学習タスクが低ランク構造を示しており、損失関数は入力空間のわずか数方向に大きく変化する。 本稿では,このような低ランク構造を利用して,勾配降下 (gd) などの標準勾配に基づく手法の計算コストを低減した。 提案するlrgdアルゴリズムは、まず、r \leq p$ 有意方向を同定し、その後、r$ 方向のみに沿って方向微分を計算して、各イテレーションにおける真の p$ 次元勾配を推定することにより、p$-次元関数の定点である $\epsilon$-approximate stationary point を求める。 強凸および非凸対象関数に対する lrgd の「方向性オラクル複雑性」は、それぞれ $\mathcal{o}(r \log(1/\epsilon) + rp)$ と $\mathcal{o}(r/\epsilon^2 + rp)$ である。 r \ll p$ の場合、これらの複素性は、強凸および非凸設定でそれぞれ $\mathcal{o}(p \log(1/\epsilon))$ と $\mathcal{o}(p/\epsilon^2)$ of {\gd} の既知の複素性よりも小さい。 したがって、LRGDは十分に低ランク関数に対する勾配に基づく手法の計算コストを大幅に削減する。 分析の過程で、我々はまた、厳密かつ概して低ランクな関数のクラスを正式に定義し、特徴づける。

関連論文リスト

• 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)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• Geometric structure of Deep Learning networks and construction of global ${\mathcal L}^2$ minimizers [1.189367612437469]
  我々は低パラメータ深層学習(DL)ネットワークにおける$mathcalL2$コスト関数の局所的および大域的最小化を明示的に決定する。
  論文  参考訳（メタデータ） (2023-09-19T14:20:55Z)
• Geometric structure of shallow neural networks and constructive ${\mathcal L}^2$ cost minimization [1.189367612437469]
  隠れた1つの層を持つ浅層ニューラルネットワーク、ReLUアクティベーション関数、$mathcal L2$ Schattenクラス(Hilbert-Schmidt)のコスト関数を考える。 我々は、$O(delta_P)$のコスト関数の最小値に対して、$delta_P$の信号とトレーニング入力のノイズ比を測る上限を証明した。 特別の場合、$M=Q$ において、コスト関数の正確な退化局所極小を明示的に決定し、そのシャープ値が a の$Qleq M$ に対して得られる上限値と異なることを示す。
  論文  参考訳（メタデータ） (2023-09-19T07:12:41Z)
• 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)
• On Acceleration of Gradient-Based Empirical Risk Minimization using Local Polynomial Regression [0.491574468325115]
  最近提案された局所多項式補間法(LPIGD)による近似解経験的リスク問題(ERM)の高速化について検討した。 我々は条件数$sigma$と強く凸で滑らかな損失関数にフォーカスする。 LPI-GDに基づく問題を高速化する2つの手法を提案し,その複雑さを$tildeOleft(sqrtsigma md log (1/varepsilon)$とする。
  論文  参考訳（メタデータ） (2022-04-16T02:39:45Z)
• Gradient-Based Empirical Risk Minimization using Local Polynomial Regression [39.29885444997579]
  この論文の主な目標は、勾配降下(GD)や勾配降下(SGD)といった異なるアルゴリズムを比較することである。 損失関数がデータのスムーズな場合、各反復でオラクルを学習し、GDとSGDの両方のオラクル複雑度に打ち勝つことができることを示す。
  論文  参考訳（メタデータ） (2020-11-04T20:10:31Z)
• A One-bit, Comparison-Based Gradient Estimator [29.600975900977343]
  正規化勾配の頑健で信頼性の高い推定器を構築するために、1ビット圧縮センシングのツールを利用する方法を示す。 勾配降下法において,この推定器を用いたSCOBOというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-06T05:01:38Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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