  We consider distributionally robust optimization (DRO) problems, reformulated
as distributionally robust feasibility (DRF) problems, with multiple
expectation constraints. We propose a generic stochastic first-order
meta-algorithm, where the decision variables and uncertain distribution
parameters are each updated separately by applying stochastic first-order
methods. We then specialize our results to the case of using two specific
versions of stochastic mirror descent (SMD): (i) a novel approximate version of
SMD to update the decision variables, and (ii) the bandit mirror descent method
to update the distribution parameters in the case of $\chi^2$-divergence sets.
For this specialization, we demonstrate that the total number of iterations is
independent of the dimensions of the decision variables and distribution
parameters. Moreover, the cost per iteration to update both sets of variables
is nearly independent of the dimension of the distribution parameters, allowing
for high dimensional ambiguity sets. Furthermore, we show that the total number
of iterations of our algorithm has a logarithmic dependence on the number of
constraints. Experiments on logistic regression with fairness constraints,
personalized parameter selection in a social network, and the multi-item
newsvendor problem verify the theoretical results and show the usefulness of
the algorithm, in particular when the dimension of the distribution parameters
is large.
