  We develop an approach to risk minimization and stochastic optimization that
provides a convex surrogate for variance, allowing near-optimal and
computationally efficient trading between approximation and estimation error.
Our approach builds off of techniques for distributionally robust optimization
and Owen's empirical likelihood, and we provide a number of finite-sample and
asymptotic results characterizing the theoretical performance of the estimator.
In particular, we show that our procedure comes with certificates of
optimality, achieving (in some scenarios) faster rates of convergence than
empirical risk minimization by virtue of automatically balancing bias and
variance. We give corroborating empirical evidence showing that in practice,
the estimator indeed trades between variance and absolute performance on a
training sample, improving out-of-sample (test) performance over standard
empirical risk minimization for a number of classification problems.
