Online Stochastic Optimization is a class of problems that capture decision making under uncertainty. The algorithm has to make real time decisions as it sees new input without knowing future arrival. The initial motivating applications, from online advertising, were formulated as linear programs, but many extensions need a convex programming formulation. Some mild stochastic assumptions about the input such as random arrival order can give near optimal algorithms. One such algorithm is a primal-dual algorithm, where the dual update is done via no-regret online learning. Convexity not only captures a broader class of problems but also clarifies the primaI-dual aspect and the connection to online learning. Finally, I will show how game theoretic considerations lead to formulations that are beyond convexity.
Back to the workshop page