論文の概要: Adapting to Mixing Time in Stochastic Optimization with Markovian Data
- arxiv url: http://arxiv.org/abs/2202.04428v3
- Date: Thu, 13 Jul 2023 16:05:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-14 17:56:01.882794
- Title: Adapting to Mixing Time in Stochastic Optimization with Markovian Data
- Title(参考訳): マルコフデータを用いた確率最適化における混合時間適応
- Authors: Ron Dorfman, Kfir Y. Levy
- Abstract要約: マルコフ連鎖からデータを引き出す際の最適化問題を考える。
この設定の既存の方法は、チェーンの混合時間を知ることに依存する。
本手法は,適応学習法とともに,マルチレベルモンテカルロ勾配推定(ML)の新たな組み合わせに依存する。
- 参考スコア(独自算出の注目度): 12.709177728330399
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider stochastic optimization problems where data is drawn from a
Markov chain. Existing methods for this setting crucially rely on knowing the
mixing time of the chain, which in real-world applications is usually unknown.
We propose the first optimization method that does not require the knowledge of
the mixing time, yet obtains the optimal asymptotic convergence rate when
applied to convex problems. We further show that our approach can be extended
to: (i) finding stationary points in non-convex optimization with Markovian
data, and (ii) obtaining better dependence on the mixing time in temporal
difference (TD) learning; in both cases, our method is completely oblivious to
the mixing time. Our method relies on a novel combination of multi-level Monte
Carlo (MLMC) gradient estimation together with an adaptive learning method.
- Abstract(参考訳): 我々は、データがマルコフ連鎖から引き出される確率的最適化問題を考える。
この設定の既存の方法は、実世界のアプリケーションでは通常未知の連鎖の混合時間を知ることに依存している。
混合時間に関する知識を必要としない最初の最適化手法を提案するが、凸問題に適用した場合に最適な漸近収束率が得られる。
さらに、我々のアプローチは次のように拡張できることを示す。
(i)マルコフデータを用いた非凸最適化における定常点の探索
(II) 時間差学習における混合時間への依存性が向上し, いずれの場合も, 混合時間には全く依存しない。
本手法は,適応学習法とともに,マルチレベルモンテカルロ勾配推定(MLMC)の新たな組み合わせに依存する。
関連論文リスト
- Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems [0.5156484100374059]
過度にパラメータ化された状態における深度最適化のための最近の線探索手法と運動量方向との関係について検討する。
モーメントパラメータの定義にデータ持続性、共役型ルールの混合を利用するアルゴリズムを導入する。
結果のアルゴリズムは、他の一般的な手法よりも優れていることを実証的に示している。
論文 参考訳(メタデータ) (2024-11-11T16:26:33Z) - Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
半/ライブラリベースのアンミックスのための新しい凸凸モデルを提案する。
スパース・アンミキシングの代替手法の有効性を実証する。
論文 参考訳(メタデータ) (2024-01-23T10:07:41Z) - 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) - Beyond Exponentially Fast Mixing in Average-Reward Reinforcement
Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
本稿では,アクター・アクターとアクター・アクター・アクター・アルゴリズムに埋め込まれた平均報酬に対して,マルチレベルモンテカルロ推定器を用いて混合時間に適応したRL手法を提案する。
不安定な報酬を伴うRL問題において,安定性に要求される技術的条件の緩和効果が,実用上優れた性能に変換されることを実験的に示す。
論文 参考訳(メタデータ) (2023-01-28T04:12:56Z) - The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。
我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文 参考訳(メタデータ) (2022-09-27T09:27:29Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳(メタデータ) (2021-11-01T15:43:36Z) - Nonlinear Independent Component Analysis for Continuous-Time Signals [85.59763606620938]
このプロセスの混合物の観察から多次元音源過程を復元する古典的問題を考察する。
このリカバリは、この混合物が十分に微分可能で可逆な関数によって与えられる場合、多くの一般的なプロセスのモデル(座標の順序と単調スケーリングまで)に対して可能であることを示す。
論文 参考訳(メタデータ) (2021-02-04T20:28:44Z) - Effective Proximal Methods for Non-convex Non-smooth Regularized
Learning [27.775096437736973]
独立サンプリング方式は、一般に使用されている一様サンプリング方式の性能を向上させる傾向にあることを示す。
我々の新しい分析は、サンプリングの速度が今までで最高のものより速いことも示しています。
論文 参考訳(メタデータ) (2020-09-14T16:41:32Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-16T04:26:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。