  This paper considers online convex optimization (OCO) with stochastic
constraints, which generalizes Zinkevich's OCO over a known simple fixed set by
introducing multiple stochastic functional constraints that are i.i.d.
generated at each round and are disclosed to the decision maker only after the
decision is made. This formulation arises naturally when decisions are
restricted by stochastic environments or deterministic environments with noisy
observations. It also includes many important problems as special cases, such
as OCO with long term constraints, stochastic constrained convex optimization,
and deterministic constrained convex optimization. To solve this problem, this
paper proposes a new algorithm that achieves $O(\sqrt{T})$ expected regret and
constraint violations and $O(\sqrt{T}\log(T))$ high probability regret and
constraint violations. Experiments on a real-world data center scheduling
problem further verify the performance of the new algorithm.
