Fugu-MT 論文翻訳(概要): Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks

論文の概要: Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks

arxiv url: http://arxiv.org/abs/2006.13866v2
Date: Sun, 5 Sep 2021 16:41:27 GMT
ステータス: 処理完了
システム内更新日: 2022-11-17 09:34:07.029918
Title: Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
Title（参考訳）: グラフニューラルネットワークの高速トレーニングのための保証付き最小分散サンプリング
Authors: Weilin Cong, Rana Forsati, Mahmut Kandemir, Mehrdad Mahdavi
Abstract要約: 既存のサンプリング手法は主にグラフ構造情報に基づいており、最適化の動的性を無視する。最小分散のノードを適応的にサンプリングする(近似)勾配情報を利用する分離分散低減戦略を提案する。提案手法は,小バッチサイズが小さい場合でも,より高速な収束率とより優れた一般化を必要とすることを理論的,実証的に示す。
参考スコア（独自算出の注目度）: 22.618779809748435
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Sampling methods (e.g., node-wise, layer-wise, or subgraph) has become an indispensable strategy to speed up training large-scale Graph Neural Networks (GNNs). However, existing sampling methods are mostly based on the graph structural information and ignore the dynamicity of optimization, which leads to high variance in estimating the stochastic gradients. The high variance issue can be very pronounced in extremely large graphs, where it results in slow convergence and poor generalization. In this paper, we theoretically analyze the variance of sampling methods and show that, due to the composite structure of empirical risk, the variance of any sampling method can be decomposed into \textit{embedding approximation variance} in the forward stage and \textit{stochastic gradient variance} in the backward stage that necessities mitigating both types of variance to obtain faster convergence rate. We propose a decoupled variance reduction strategy that employs (approximate) gradient information to adaptively sample nodes with minimal variance, and explicitly reduces the variance introduced by embedding approximation. We show theoretically and empirically that the proposed method, even with smaller mini-batch sizes, enjoys a faster convergence rate and entails a better generalization compared to the existing methods.
Abstract（参考訳）: サンプリング手法(ノードワイド、レイヤワイド、サブグラフなど)は、大規模グラフニューラルネットワーク(GNN)のトレーニングを高速化するために必要な戦略となっている。しかし、既存のサンプリング手法は主にグラフ構造情報に基づいており、最適化の動的性を無視し、確率勾配を推定する際に高いばらつきをもたらす。高分散問題は、非常に大きなグラフで非常に顕著に発音され、収束が遅く、一般化が低くなる。本稿では, サンプリング手法の分散を理論的に解析し, 実験的リスクの複合構造により, サンプリング手法の分散を, より高速な収束率を得るために両種類の分散を緩和する必要のある後方段階において, サンプリング手法の分散を, 前方段階において textit{embedding approximation variance} と後方段階において textit{stochastic gradient variance} に分解可能であることを示す。本研究では,(近似)勾配情報を用いて最小分散のノードを適応的にサンプリングし,埋め込み近似による分散を明示的に低減する分散低減戦略を提案する。提案手法は,小型バッチサイズが小さくても,収束速度が速く,従来の手法よりも一般化が進んでいることを理論的に実証的に示す。

関連論文リスト

Stochastic Variance-Reduced Iterative Hard Thresholding in Graph Sparsity Optimization [0.626226809683956]
グラデーションに基づくグラフ空間幅最適化法として,グラフRG-IHTとグラフSG-IHTの2つの手法を提案する。我々は,手法が勾配に基づく枠組みを楽しむことを示す理論解析の一般性を示す。
論文参考訳（メタデータ） (2024-07-24T03:26:26Z)
A Geometric Perspective on Diffusion Models [57.27857591493788]
本稿では,人気のある分散拡散型SDEのODEに基づくサンプリングについて検討する。我々は、最適なODEベースのサンプリングと古典的な平均シフト(モード探索)アルゴリズムの理論的関係を確立する。
論文参考訳（メタデータ） (2023-05-31T15:33:16Z)
Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文参考訳（メタデータ） (2022-02-26T19:10:48Z)
Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文参考訳（メタデータ） (2021-10-20T02:25:25Z)
On the Importance of Sampling in Learning Graph Convolutional Networks [13.713485304798368]
Graph Convolutional Networks (GCNs) は、様々なグラフ関連アプリケーションにおいて、目覚ましい進歩を遂げている。その成功にもかかわらず、大きなグラフ上でのgcnのトレーニングは計算とメモリの問題に苦しむ。メモリ予算下で任意のサンプリングメソッドを高速化できる一般的なtextbftextitdoubly variance reductionスキーマを記述・解析する。
論文参考訳（メタデータ） (2021-03-03T21:31:23Z)
Effective Proximal Methods for Non-convex Non-smooth Regularized Learning [27.775096437736973]
独立サンプリング方式は、一般に使用されている一様サンプリング方式の性能を向上させる傾向にあることを示す。我々の新しい分析は、サンプリングの速度が今までで最高のものより速いことも示しています。
論文参考訳（メタデータ） (2020-09-14T16:41:32Z)
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization [15.82816385434718]
本稿では、滑らかで凸な損失と凸正則化器を最小化するための勾配アルゴリズムの収束解析のための統一定理を提案する。我々は、Gorbunov, Hanzely & Richt'arik (2020) の統一解析を拡張し、損失関数が強く凸であるという要求を下げる。我々の統一解析は、近位SGD、分散還元法、量子化、およびいくつかの座標降下型法などの既存のアルゴリズムのホストに適用できる。
論文参考訳（メタデータ） (2020-06-20T13:40:27Z)
Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
グラフ畳み込みネットワーク(GCN)の訓練を高速化するために, ばらつきを低減したサンプリングアルゴリズムが提案されている。これらのサンプリングアルゴリズムは、グラフ注意ネットワーク(GAT)のような固定重みよりも学習重量を含む、より一般的なグラフニューラルネットワーク(GNN)には適用できない。
論文参考訳（メタデータ） (2020-06-10T12:48:37Z)
Path Sample-Analytic Gradient Estimators for Stochastic Binary Networks [78.76880041670904]
二進的アクティベーションや二進的重みを持つニューラルネットワークでは、勾配降下によるトレーニングは複雑である。そこで本研究では,サンプリングと解析近似を併用した新しい推定法を提案する。勾配推定において高い精度を示し、深部畳み込みモデルにおいてより安定かつ優れた訓練を行うことを示す。
論文参考訳（メタデータ） (2020-06-04T21:51:21Z)
A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate [28.167294398293297]
通信負荷の少ない分散勾配降下法(SGD)を提案する。各イテレーションにおける計算複雑性を低減するために、ワーカノードは、方向微分をゼロ階勾配推定で近似する。
論文参考訳（メタデータ） (2020-03-27T14:02:15Z)
The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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