Technical Note—Improved Sample-Complexity Bounds in Stochastic Optimization

This is the authors' abstract. We don't add key points for this paper.

Faster Methods to Handle Optimization Problems That Display Uncertainty In the paper “Improved Sample-Complexity Bounds in Stochastic Optimization,” the authors Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu consider a classic approach to modeling uncertainty in optimization problems—stochastic optimization. A general way to model such uncertainty is to assume access to a probability distribution from which the different possible scenarios of an optimization problem can be sampled; a powerful way to work with such access is to sample explicit scenarios a fixed number of times and to then “average over” all these explicit deterministic scenarios. The key question then becomes as follows. How many such scenarios should be sampled? By a careful analysis, this work shows that the number of samples needed is much less than known before, thus speeding up several algorithms for stochastic-optimization problems.