Online Stochastic Convex Optimization: Wasserstein Distance Variation
This work addresses distributionally-robust optimization for time-varying environments, relevant to fields like finance and sociology, but it is incremental as it builds on existing online optimization and control concepts.
The paper tackles the problem of online stochastic convex optimization under time-varying probability distributions, using Wasserstein distance to model distribution drift, and provides dynamic regret bounds for tracking and estimation errors under strong convexity and gradient Lipschitzness, with an exact penalty method to handle computational constraints.
Distributionally-robust optimization is often studied for a fixed set of distributions rather than time-varying distributions that can drift significantly over time (which is, for instance, the case in finance and sociology due to underlying expansion of economy and evolution of demographics). This motivates understanding conditions on probability distributions, using the Wasserstein distance, that can be used to model time-varying environments. We can then use these conditions in conjunction with online stochastic optimization to adapt the decisions. We considers an online proximal-gradient method to track the minimizers of expectations of smooth convex functions parameterised by a random variable whose probability distributions continuously evolve over time at a rate similar to that of the rate at which the decision maker acts. We revisit the concepts of estimation and tracking error inspired by systems and control literature and provide bounds for them under strong convexity, Lipschitzness of the gradient, and bounds on the probability distribution drift. Further, noting that computing projections for a general feasible sets might not be amenable to online implementation (due to computational constraints), we propose an exact penalty method. Doing so allows us to relax the uniform boundedness of the gradient and establish dynamic regret bounds for tracking and estimation error. We further introduce a constraint-tightening approach and relate the amount of tightening to the probability of satisfying the constraints.