Many optimization problems that arise in science and engineering are those in which we only have a stochastic approximation to the underlying objective (e.g. estimation problems such as linear regression). That is, given some distribution $\mathcal{D}$ over functions $\psi$, we wish to minimize $P(x) = \mathbb{E}_{\psi \sim \mathcal{D}}[\psi(x)]$, using as few samples from $\mathcal{D}$ as possible. In the absence of computational constraints, the empirical risk minimizer (ERM) -- the minimizer on a sample average of observed data -- is widely regarded as the estimation strategy of choice due to its desirable statistical convergence properties. Our goal is to do as well as the empirical risk minimizer, on every problem, while minimizing the use of computational resources such as running time and space usage.