論文の概要: SGD Through the Lens of Kolmogorov Complexity

• arxiv url: http://arxiv.org/abs/2111.05478v1
• Date: Wed, 10 Nov 2021 01:32:38 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-11 14:59:44.551319
• Title: SGD Through the Lens of Kolmogorov Complexity
• Title（参考訳）: コルモゴロフ錯体のレンズによるSGD
• Authors: Gregory Schwartzman
• Abstract要約: 勾配降下 (SGD) はデータセット全体の分類精度が$ (1-epsilon)$の解を求める。 特定のアーキテクチャやアクティベーション関数を持つためにモデルを必要としないのです。
• 参考スコア（独自算出の注目度）: 0.15229257192293197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that stochastic gradient descent (SGD) finds a solution that achieves $(1-\epsilon)$ classification accuracy on the entire dataset. We do so under two main assumptions: (1. Local progress) There is consistent improvement of the model accuracy over batches. (2. Models compute simple functions) The function computed by the model is simple (has low Kolmogorov complexity). Intuitively, the above means that \emph{local progress} of SGD implies \emph{global progress}. Assumption 2 trivially holds for underparameterized models, hence, our work gives the first convergence guarantee for general, \emph{underparameterized models}. Furthermore, this is the first result which is completely \emph{model agnostic} - we don't require the model to have any specific architecture or activation function, it may not even be a neural network. Our analysis makes use of the entropy compression method, which was first introduced by Moser and Tardos in the context of the Lov\'asz local lemma.
• Abstract（参考訳）: 確率的勾配降下 (sgd) がデータセット全体の分類精度(1-\epsilon)$を達成する解を見つけることを証明している。 1. 局所的な進捗) バッチよりもモデルの精度が一貫した改善がなされている。 (2.単純な関数を計算するモデル) モデルによって計算される関数は単純(コルモゴロフ複雑性が低い)である。 直観的には、sgd の \emph{local progress} は \emph{global progress} を意味する。 仮定 2 は、非パラメータモデルに対して自明に成立するので、我々の研究は、一般に対して最初の収束保証を与える: \emph{underparameterized models}。 さらに、これは完全に \emph{model agnostic} である最初の結果です - 特定のアーキテクチャやアクティベーション関数を持つためにモデルを必要とせず、ニューラルネットワークでさえないのです。 我々の分析では、Lov\'asz局所補題の文脈でモーサーとタルドスが最初に導入したエントロピー圧縮法を用いている。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• NGD converges to less degenerate solutions than SGD [0.5249805590164902]
  モデルの自由パラメータ(次元)の数は、その複雑さを測る簡単な方法である。 しかし、これは正確な複雑さの尺度ではない。トレーニングデータを記憶できるモデルは、高次元にもかかわらずしばしば一般化される。 有効ディメンションは、モデルの機能性を表すのに必要なパラメータの数だけを数えることで、モデルの複雑さをより直接的に捉えることを目的としています。
  論文  参考訳（メタデータ） (2024-09-07T21:27:49Z)
• Latent Semantic Consensus For Deterministic Geometric Model Fitting [109.44565542031384]
  我々はLSC(Latent Semantic Consensus)と呼ばれる効果的な方法を提案する。 LSCは、モデルフィッティング問題をデータポイントとモデル仮説に基づく2つの潜在意味空間に定式化する。 LSCは、一般的な多構造モデルフィッティングのために、数ミリ秒以内で一貫した、信頼性の高いソリューションを提供することができる。
  論文  参考訳（メタデータ） (2024-03-11T05:35:38Z)
• A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width [7.605563562103568]
  我々はIsingモデルの基本パラメータをデータから効率的に学習する問題を再考する。 ノード単位のロジスティック回帰に基づく単純な既存手法が、いくつかの新しい設定で基盤モデルの回復に成功していることを示す。
  論文  参考訳（メタデータ） (2023-11-15T18:41:19Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Adaptive Sparse Gaussian Process [0.0]
  これらの問題に対処できる最初の適応スパースガウスプロセス(GP)を提案する。 まず,変分スパースGPアルゴリズムを変形係数によって適応的に再構成する。 そこで我々は,新しいサンプルが到着するたびに,スパースGPモデルの単一誘導点と残りのモデルパラメータを同時に更新することを提案する。
  論文  参考訳（メタデータ） (2023-02-20T21:34:36Z)
• KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
  モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。 我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
  論文  参考訳（メタデータ） (2022-05-27T19:39:24Z)
• uGLAD: Sparse graph recovery by optimizing deep unrolled networks [11.48281545083889]
  深層ネットワークを最適化してスパースグラフ復元を行う新しい手法を提案する。 我々のモデルであるuGLADは、最先端モデルGLADを教師なし設定に構築し、拡張します。 我々は, 遺伝子調節ネットワークから生成した合成ガウスデータ, 非ガウスデータを用いて, モデル解析を行い, 嫌気性消化の事例研究を行った。
  論文  参考訳（メタデータ） (2022-05-23T20:20:27Z)
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature [61.22680308681648]
  決定論的報酬を有する1層ニューラルネットバンディットにおいても,グローバル収束は統計的に難解であることを示す。 非線形バンディットとRLの両方に対して,オンラインモデル学習者による仮想アセンジ(Virtual Ascent with Online Model Learner)というモデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-08T12:41:56Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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