  We consider robust optimization problems, where the goal is to optimize in
the worst case over a class of objective functions. We develop a reduction from
robust improper optimization to Bayesian optimization: given an oracle that
returns $\alpha$-approximate solutions for distributions over objectives, we
compute a distribution over solutions that is $\alpha$-approximate in the worst
case. We show that de-randomizing this solution is NP-hard in general, but can
be done for a broad class of statistical learning tasks. We apply our results
to robust neural network training and submodular optimization. We evaluate our
approach experimentally on corrupted character classification, and robust
influence maximization in networks.
