Complexity of Stochastic Dual Dynamic Programming

• URL: http://arxiv.org/abs/1912.07702v9
• Date: Tue, 9 May 2023 13:52:40 GMT
• Title: Complexity of Stochastic Dual Dynamic Programming
• Authors: Guanghui Lan
• Abstract summary: We first establish the number of iteration, i.e., complexity, required by a basic dynamic cutting plane method for solving simple multi-stage optimization problems. We then refine these basic tools and establish the iteration complexity for both deterministic and dual dynamic programming methods.
• Score: 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.

Related papers

• Bayesian Optimization for Non-Convex Two-Stage Stochastic Optimization Problems [2.9016548477524156]
  We formulate a knowledgeient-based acquisition function to jointly optimize the first and second-stage variables. We show that differences in the dimension and length scales between the variable types can lead to inefficiencies of the twostep algorithm.
  arXiv  Detail & Related papers  (2024-08-30T16:26:31Z)
• Optimization-Driven Adaptive Experimentation [7.948144726705323]
  Real-world experiments involve batched & delayed feedback, non-stationarity, multiple objectives & constraints, and (often some) personalization. Tailoring adaptive methods to address these challenges on a per-problem basis is infeasible, and static designs remain the de facto standard. We present a mathematical programming formulation that can flexibly incorporate a wide range of objectives, constraints, and statistical procedures.
  arXiv  Detail & Related papers  (2024-08-08T16:29:09Z)
• Transformer-based Stagewise Decomposition for Large-Scale Multistage Stochastic Optimization [1.3124513975412255]
  We introduce TranSDDP, a novel Transformer-based stagewise decomposition algorithm. We show it efficiently generates a piecewise linear approximation for the value function.
  arXiv  Detail & Related papers  (2024-04-03T09:08:15Z)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  We introduce contextual bilevel optimization (CSBO) -- a bilevel optimization framework with the lower-level problem minimizing an expectation on some contextual information and the upper-level variable. It is important for applications such as meta-learning, personalized learning, end-to-end learning, and Wasserstein distributionally robustly optimization with side information (WDRO-SI)
  arXiv  Detail & Related papers  (2023-10-27T23:24:37Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP) Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
  arXiv  Detail & Related papers  (2023-03-28T01:30:40Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function. $nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-12-01T22:55:23Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  We consider non-SBO problems that have many applications in machine learning. This paper proposes fast randomized algorithms for non-SBO problems.
  arXiv  Detail & Related papers  (2021-05-05T18:28:42Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Statistically Guided Divide-and-Conquer for Sparse Factorization of Large Matrix [2.345015036605934]
  We formulate the statistical problem as a sparse factor regression and tackle it with a divide-conquer approach. In the first stage division, we consider both latent parallel approaches for simplifying the task into a set of co-parsesparserank estimation (CURE) problems. In the second stage division, we innovate a stagewise learning technique, consisting of a sequence simple incremental paths, to efficiently trace out the whole solution of CURE.
  arXiv  Detail & Related papers  (2020-03-17T19:12:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.