We study methods to assess the optimality gap, as a measurement of the quality of solutions, in stochastic optimization under limited-data situations. We demonstrate how viewing an optimistic bound for these problems through classical symmetric statistics leads to bagging-based approaches that are statistically more efficient than existing ones. We discuss the theoretical guarantees and computational requirements of our methods, and some extensions of our investigation to optimization problems where feasibility is also of interest.