Technical Note—Improved Sample-Complexity Bounds in Stochastic Optimization
分析了随机优化中需要从概率分布中抽取多少样本才能有效处理不确定性，发现所需样本数远少于此前已知，从而加速了多种随机优化算法。
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.