Non-stationary Stochastic Optimization

Understand

We consider a non-stationary variant of a sequential stochastic optimization problem, in which the underlying cost functions may change along the horizon.

• We propose a measure, termed variation budget, that controls the extent of said change, and study how restrictions on this budget impact achievable performance.
• We identify sharp conditions under which it is possible to achieve long-run-average optimality and more refined performance measures such as rate optimality that fully characterize the complexity of such problems.
• In doing so, we also establish a strong connection between two rather disparate strands of literature: adversarial online convex optimization; and the more traditional stochastic approximation paradigm (couched in a non-stationary setting).