  We consider online convex optimization with stochastic constraints where the
objective functions are arbitrarily time-varying and the constraint functions
are independent and identically distributed (i.i.d.) over time. Both the
objective and constraint functions are revealed after the decision is made at
each time slot. The best known expected regret for solving such a problem is
$\mathcal{O}(\sqrt{T})$, with a coefficient that is polynomial in the dimension
of the decision variable and relies on the Slater condition (i.e. the existence
of interior point assumption), which is restrictive and in particular precludes
treating equality constraints. In this paper, we show that such Slater
condition is in fact not needed. We propose a new primal-dual mirror descent
algorithm and show that one can attain $\mathcal{O}(\sqrt{T})$ regret and
constraint violation under a much weaker Lagrange multiplier assumption,
allowing general equality constraints and significantly relaxing the previous
Slater conditions. Along the way, for the case where decisions are contained in
a probability simplex, we reduce the coefficient to have only a logarithmic
dependence on the decision variable dimension. Such a dependence has long been
known in the literature on mirror descent but seems new in this new constrained
online learning scenario.
