Motivated by an energy systems application, we study efficient algorithms to find approximately optimal solutions to stochastic min-max formulations. The standard approach is to solve a large-sample approximation to the true problem. Many common large-scale statistical learning formulations (e.g. regularized risk minimization, multiple kernel learning, robust machine learning) are special instances of this large-sample approximate form. Standard cutting-plane or column generation methods are applied to this large-scale formulation, but computational speed suffers from having to generate sub-gradient information over the entire large sample set. We propose an alternative stochastic first-order (gradient following) recursion procedure to solve the outer (minimization) problem, where gradient information is gathered from the inner (maximization) problem similar to the cutting-plane methods. However, under this approach, it is sufficient to compute the gradients from small subsamples of the entire dataset, and convergence is guaranteed as long as the sample set size growth satisfies some regularity conditions. The method can also be computationally efficient (in a certain precise sense) if the rate at which this set grows is carefully controlled. We characterize the regimes when the fastest possible convergence rates are achieved. Preliminary numerical results show the efficacy of our approach.