論文の概要: Complexity of Stochastic Dual Dynamic Programming

• arxiv url: http://arxiv.org/abs/1912.07702v9
• Date: Tue, 9 May 2023 13:52:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-10 21:33:46.089149
• Title: Complexity of Stochastic Dual Dynamic Programming
• Title（参考訳）: 確率的双対動的プログラミングの複雑性
• Authors: Guanghui Lan
• Abstract要約: まず, 簡単な多段最適化問題の解法として, 基本的動的切削平面法が要求する反復数, すなわち複雑性を確立する。 次に、これらの基本的なツールを洗練し、決定論的および双対動的プログラミング手法の反復複雑性を確立する。
• 参考スコア（独自算出の注目度）: 7.177693955272473
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic dual dynamic programming is a cutting plane type algorithm for multi-stage stochastic optimization originated about 30 years ago. In spite of its popularity in practice, there does not exist any analysis on the convergence rates of this method. In this paper, we first establish the number of iterations, i.e., iteration complexity, required by a basic dynamic cutting plane method for solving relatively simple multi-stage optimization problems, by introducing novel mathematical tools including the saturation of search points. We then refine these basic tools and establish the iteration complexity for both deterministic and stochastic dual dynamic programming methods for solving more general multi-stage stochastic optimization problems under the standard stage-wise independence assumption. Our results indicate that the complexity of some deterministic variants of these methods mildly increases with the number of stages $T$, in fact linearly dependent on $T$ for discounted problems. Therefore, they are efficient for strategic decision making which involves a large number of stages, but with a relatively small number of decision variables in each stage. Without explicitly discretizing the state and action spaces, these methods might also be pertinent to the related reinforcement learning and stochastic control areas.
• Abstract（参考訳）: 確率的双対動的プログラミングは、約30年前に考案された多段確率最適化のための切削平面型アルゴリズムである。 実際にはその人気にもかかわらず、この手法の収束率に関する分析は存在していない。 本稿では,探索点の飽和を含む新しい数学的ツールを導入することにより,比較的単純な多段階最適化問題を解くための基本動的切削平面法に必要な反復数,すなわち反復複雑性を最初に確立する。 次に、これらの基本ツールを改良し、より一般的な多段階確率最適化問題を標準段階独立仮定の下で解くための決定論的および確率的双対動的プログラミング手法の反復複雑性を確立する。 以上の結果から,これらの手法の決定論的変異の複雑性は段数$T$で軽度に増大し,実際に割引問題に対して$T$に線形に依存することが明らかとなった。 したがって、それらは多くの段階を含むが、各段階において比較的少ない決定変数を持つ戦略的意思決定に効率的である。 状態空間と行動空間を明確に区別しなければ、これらの手法は関連する強化学習や確率的制御領域にも関係する可能性がある。

関連論文リスト

• Bayesian Optimization for Non-Convex Two-Stage Stochastic Optimization Problems [2.9016548477524156]
  知識に基づく獲得関数を定式化し,第1段と第2段の変数を協調的に最適化する。 可変型間の寸法と長さの差が2段階アルゴリズムの非効率性をもたらすことを示す。
  論文  参考訳（メタデータ） (2024-08-30T16:26:31Z)
• Optimization-Driven Adaptive Experimentation [7.948144726705323]
  実世界の実験には、バッチで遅延したフィードバック、非定常性、複数の目的と制約、そして(時には)パーソナライゼーションが含まれる。 これらの課題にプロブレム単位で対処するための適応的手法の調整は不可能であり、静的設計はデファクトスタンダードのままである。 本稿では,多種多様な目的,制約,統計的手順を柔軟に組み込む数学的プログラミングの定式化について述べる。
  論文  参考訳（メタデータ） (2024-08-08T16:29:09Z)
• Transformer-based Stagewise Decomposition for Large-Scale Multistage Stochastic Optimization [1.3124513975412255]
  本稿では,トランスフォーマーに基づく段階分解アルゴリズムであるTrranSDDPを紹介する。 本研究では,値関数の分数次線形近似を効率よく生成することを示す。
  論文  参考訳（メタデータ） (2024-04-03T09:08:15Z)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。 メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
  論文  参考訳（メタデータ） (2023-10-27T23:24:37Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。 凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。 切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
  論文  参考訳（メタデータ） (2023-03-28T01:30:40Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Statistically Guided Divide-and-Conquer for Sparse Factorization of Large Matrix [2.345015036605934]
  統計的問題をスパース係数回帰として定式化し、分割コンカレントアプローチでそれに取り組む。 第1段階分割では、タスクを1組の同時並列推定(CURE)問題に単純化するための2つの潜時並列アプローチについて検討する。 第2段階分割では、CUREの全解を効率的に追跡するために、一連の単純な増分経路からなる段階学習手法を革新する。
  論文  参考訳（メタデータ） (2020-03-17T19:12:21Z)

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

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