論文の概要: Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms

• arxiv url: http://arxiv.org/abs/2106.04881v1
• Date: Wed, 9 Jun 2021 08:05:36 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-11 04:32:34.250624
• Title: Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
• Title（参考訳）: 確率最適化アルゴリズムのフラクタル構造と一般化特性
• Authors: Alexander Camuto, George Deligiannidis, Murat A. Erdogdu, Mert G\"urb\"uzbalaban, Umut \c{S}im\c{s}ekli, Lingjiong Zhu
• Abstract要約: 最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
• 参考スコア（独自算出の注目度）: 71.62575565990502
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Understanding generalization in deep learning has been one of the major challenges in statistical learning theory over the last decade. While recent work has illustrated that the dataset and the training algorithm must be taken into account in order to obtain meaningful generalization bounds, it is still theoretically not clear which properties of the data and the algorithm determine the generalization performance. In this study, we approach this problem from a dynamical systems theory perspective and represent stochastic optimization algorithms as random iterated function systems (IFS). Well studied in the dynamical systems literature, under mild assumptions, such IFSs can be shown to be ergodic with an invariant measure that is often supported on sets with a fractal structure. As our main contribution, we prove that the generalization error of a stochastic optimization algorithm can be bounded based on the `complexity' of the fractal structure that underlies its invariant measure. Leveraging results from dynamical systems theory, we show that the generalization error can be explicitly linked to the choice of the algorithm (e.g., stochastic gradient descent -- SGD), algorithm hyperparameters (e.g., step-size, batch-size), and the geometry of the problem (e.g., Hessian of the loss). We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden-layered neural networks) and algorithms (e.g., SGD and preconditioned variants), and obtain analytical estimates for our bound.For modern neural networks, we develop an efficient algorithm to compute the developed bound and support our theory with various experiments on neural networks.
• Abstract（参考訳）: ディープラーニングの一般化を理解することは、過去10年間の統計的学習理論における大きな課題の1つだ。 近年の研究では、有意義な一般化境界を得るためにデータセットとトレーニングアルゴリズムを考慮に入れなければならないことが示されているが、データとアルゴリズムのどの特性が一般化性能を決定するのかは理論的には定かではない。 本研究では,動的システム理論の観点からこの問題にアプローチし,確率的最適化アルゴリズムをランダム反復関数系(IFS)として表現する。 力学系の文献でよく研究され、穏やかな仮定の下で、そのようなISFはフラクタル構造を持つ集合上でしばしば支持される不変測度でエルゴードであることが示される。 我々の主要な貢献として,確率的最適化アルゴリズムの一般化誤差は,その不変測度の根底にあるフラクタル構造の'複雑度'に基づいて限定可能であることを証明した。 力学系理論の結果を利用して、一般化誤差はアルゴリズムの選択(例えば、確率勾配勾配 - SGD)、アルゴリズムのハイパーパラメータ(例えば、ステップサイズ、バッチサイズ)、および問題の幾何学(例えば、損失のヘシアン)に明示的に関連付けることができることを示す。 我々はさらに,特定の問題(線形・ロジスティック回帰,隠れ層ニューラルネットワークなど)やアルゴリズム(sgdやプリコンディション型など)に対して,解析的な推定値を得ることを特化している。現代のニューラルネットワークでは,開発した境界を計算し,ニューラルネットワークの様々な実験で理論を支援できる効率的なアルゴリズムを開発する。

関連論文リスト

• Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms [15.473123662393169]
  ディープニューラルネットワーク(DNN)は、顕著な一般化特性を示す。 これらの能力の源泉は依然として解明され、確立された統計的学習理論を否定している。 近年の研究では、訓練軌跡の性質が一般化の指標であることが示されている。
  論文  参考訳（メタデータ） (2024-07-11T17:56:03Z)
• Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection [25.29451529910051]
  本稿では,アルゴリズムの特徴に基づくアルゴリズム選択の証明可能な最初の保証を提案する。 アルゴリズムの特徴に関連する利点とコストを分析し、一般化誤差が様々な要因にどのように影響するかを考察する。
  論文  参考訳（メタデータ） (2024-05-18T17:38:25Z)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  本稿では,アルゴリズム安定性の概念を活用して,浅層ニューラルネットワーク(SNN)の一般化挙動について検討する。 我々は、SNNを訓練するために勾配降下(GD)と勾配降下(SGD)を考慮する。
  論文  参考訳（メタデータ） (2022-09-19T18:48:00Z)
• On the generalization of learning algorithms that do not converge [54.122745736433856]
  ディープラーニングの一般化解析は、訓練が一定の点に収束すると仮定するのが一般的である。 最近の結果は、実際には勾配降下に最適化されたディープニューラルネットワークの重みは、しばしば無限に振動することを示している。
  論文  参考訳（メタデータ） (2022-08-16T21:22:34Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks [19.99615698375829]
  一般化誤差は 'peristent homology dimension' (PHD) という概念で等価に有界であることを示す。 我々は,現代のディープニューラルネットワークの規模でPHDを推定する効率的なアルゴリズムを開発した。 実験の結果,提案手法はネットワークの固有次元を様々な設定で効率的に計算できることがわかった。
  論文  参考訳（メタデータ） (2021-11-25T17:06:15Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks [23.038631072178735]
  我々は、一般的に使用される最適化アルゴリズムの幅広いクラスについて考察する。 その結果、ニューラルネットワークの収束挙動を利用することができる。 このアプローチは他の最適化アルゴリズムやネットワーク理論にも拡張できると考えています。
  論文  参考訳（メタデータ） (2020-10-25T17:10:22Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  経験的最適化は現代の機械学習の中心であるが、その成功における役割はまだ不明である。 分散による離散乗法雑音のパラメータによく現れることを示す。 最新のステップサイズやデータを含む重要な要素について、詳細な分析を行い、いずれも最先端のニューラルネットワークモデルで同様の結果を示す。
  論文  参考訳（メタデータ） (2020-06-11T09:58:01Z)

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

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