Title: Dynamic Stochastic Approximation for Multi-stage Stochastic Optimization,
Abstract: In this paper, we consider multi-stage stochastic optimization problems with
convex objectives and conic constraints at each stage. We present a new
stochastic first-order method, namely the dynamic stochastic approximation
(DSA) algorithm, for solving these types of stochastic optimization problems.
We show that DSA can achieve an optimal ${\cal O}(1/\epsilon^4)$ rate of
convergence in terms of the total number of required scenarios when applied to
a three-stage stochastic optimization problem. We further show that this rate
of convergence can be improved to ${\cal O}(1/\epsilon^2)$ when the objective
function is strongly convex. We also discuss variants of DSA for solving more
general multi-stage stochastic optimization problems with the number of stages
$T > 3$. The developed DSA algorithms only need to go through the scenario tree
once in order to compute an $\epsilon$-solution of the multi-stage stochastic
optimization problem. To the best of our knowledge, this is the first time that
stochastic approximation type methods are generalized for multi-stage
stochastic optimization with $T \ge 3$.