論文の概要: Stochastic Gradient Descent under Markovian Sampling Schemes

• arxiv url: http://arxiv.org/abs/2302.14428v1
• Date: Tue, 28 Feb 2023 09:18:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-01 17:20:33.363096
• Title: Stochastic Gradient Descent under Markovian Sampling Schemes
• Title（参考訳）: マルコフサンプリングスキームにおける確率的勾配の沈み込み
• Authors: Mathieu Even
• Abstract要約: マルコフ型サンプリングスキームにのみアクセス可能なバニラ勾配トークン降下の変動について検討する。 我々は、基礎となるマルコフ連鎖で可能な最小限の制限的な仮定の下で収束率を得ることに焦点をあてる。
• 参考スコア（独自算出の注目度）: 3.04585143845864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a variation of vanilla stochastic gradient descent where the optimizer only has access to a Markovian sampling scheme. These schemes encompass applications that range from decentralized optimization with a random walker (token algorithms), to RL and online system identification problems. We focus on obtaining rates of convergence under the least restrictive assumptions possible on the underlying Markov chain and on the functions optimized. We first unveil the theoretical lower bound for methods that sample stochastic gradients along the path of a Markov chain, making appear a dependency in the hitting time of the underlying Markov chain. We then study Markov chain SGD (MC-SGD) under much milder regularity assumptions than prior works. We finally introduce MC-SAG, an alternative to MC-SGD with variance reduction, that only depends on the hitting time of the Markov chain, therefore obtaining a communication-efficient token algorithm.
• Abstract（参考訳）: 最適化器がマルコフ型サンプリング方式にのみアクセス可能なバニラ確率勾配勾配の変動について検討する。 これらのスキームは、ランダムウォーカによる分散最適化(トークンアルゴリズム)から、RLおよびオンラインシステム識別問題まで幅広い応用を含んでいる。 下位のマルコフ連鎖と最適化された関数に可能な最小制限条件下での収束率の獲得に着目する。 まず,マルコフ連鎖の経路に沿った確率的勾配をサンプリングし,マルコフ連鎖の衝突時間の依存性を表わす手法の理論的下限を明らかにした。 次に、マルコフ連鎖 SGD (MC-SGD) を以前の研究よりも遥かに穏やかな正則性仮定の下で研究する。 最終的に MC-SGD の代替として MC-SAG を導入し,マルコフ連鎖の打上げ時間にのみ依存するため,通信効率のよいトークンアルゴリズムが得られた。

関連論文リスト

• Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks [11.3631620309434]
  エージェントのネットワークをランダムウォーク方式で横断するトークンによって勾配をサンプリングする分散最適化アルゴリズムの一群について検討する。 我々は、正則線型マルコフトークンを非線形マルコフ連鎖、すなわち自己推進ラドムウォーク(SRRW)に従うものに置き換えることで、新しいアプローチをとる。 結果のSA-SRRWの最適化誤差はほぼ確実にゼロに収束し、中心極限定理を証明する。
  論文  参考訳（メタデータ） (2024-01-18T00:50:37Z)
• Stochastic-Constrained Stochastic Optimization with Markovian Data [2.1756081703276]
  マルコフ連鎖からデータサンプルが引き出され、したがって独立性がなく、同一に分布しないような環境について検討する。 ドリフト・プラス・ペナルティの2つの変種を提案する。ひとつは、基礎となるマルコフ鎖の混合時間を知る場合である。 我々のアルゴリズムは、制約関数列がマルコフ連鎖に従うような制約付きオンライン凸最適化のより一般的な設定に適用できる。
  論文  参考訳（メタデータ） (2023-12-07T14:09:27Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains [11.3631620309434]
  ランダムウォーカーは、サンプリングと近傍探索により、ネットワークトポロジ上のターゲット量を近似するように設計されている。 目的とする確率分布に対応するマルコフ連鎖が与えられた場合、過去に頻繁に訪れたノードに遷移する可能性が低く、滅多に訪れないノードに遷移する可能性が低い自己反発ランダムウォーク(SRRW)を設計する。 正の実アルファでパラメータ化されたSRRWのクラスに対して、プロセスの経験的分布がターゲットにほぼ確実に収束することを証明する。
  論文  参考訳（メタデータ） (2023-05-08T23:59:09Z)
• Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
  Annealed Importance Smpling (AIS) は、深層生成モデルの難易度を推定するために使われる一般的なアルゴリズムである。 本稿では、フレキシブルな中間分布を持つパラメータAISプロセスを提案し、サンプリングに少ないステップを使用するようにブリッジング分布を最適化する。 我々は, 最適化AISの性能評価を行い, 深部生成モデルの限界推定を行い, 他の推定値と比較した。
  論文  参考訳（メタデータ） (2022-09-27T07:58:25Z)
• Efficiency Ordering of Stochastic Gradient Descent [9.634481296779057]
  我々は、任意のグラフ上のノイズやランダムウォークを含む一般的なサンプリングシーケンスによって駆動される勾配降下(SGD)アルゴリズムについて検討する。 我々は、マルコフ・チェイン・モンテカルロサンプリング器の性能を比較するためのよく分析されたツールである「効率順序付け」の概念を採用している。
  論文  参考訳（メタデータ） (2022-09-15T16:50:55Z)
• Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradients [7.461223697336269]
  勾配降下(SGD)による包摂的クルバック・リーブラー分岐の最小化は、その勾配が後部上の積分として定義されるため困難である。 本稿では,これらの手法の非漸近収束解析として,混合速度と勾配のばらつきを確立した。
  論文  参考訳（メタデータ） (2022-06-13T16:25:08Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  ハイブリッドモンテカルロ(Hybrid Monte Carlo)は、複素連続分布からサンプリングする強力なマルコフ連鎖モンテカルロ法である。 本稿では,SurVAEフローを用いたモンテカルロ法の拡張に基づく新しい手法を提案する。 本稿では,統計学,計算物理学,機械学習など,様々な分野におけるアルゴリズムの有効性を実証し,代替アルゴリズムと比較した改良点を考察する。
  論文  参考訳（メタデータ） (2021-02-04T02:21:08Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)

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

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