Best algorithm for stochastic optimization where payoff can be decomposed among multiple similar units?

I have a estimation problem with ~100 parameters, and a payoff calculated as sum of errors over ~300 independent units. Problem is not very smooth; I have had some success with patternsearch and fminsearch (better than interior point and sqp in fmincon; but still pretty slow). A key feature is that an external function returns the errors for any subset of units I call (and is rather expensive to calculate). So for example I could do the optimization on a small subset of units, getting approximate results in early iterations, before fine tuning with full sample of 300 units at the peak. Essentially I can get more precise function calculations by paying more computation cost. Are there standard stochastic optimization algorithms out there that allow me to utilize this feature of the problem and save on the optimization time?