Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming

This paper studies the sample average approximation (SAA) in solving convex or strongly convex stochastic programming problems. Under some common regularity conditions, we show -- perhaps for the first time -- that the SAA's sample complexity can be completely free from any quantification of metric entropy (such as the logarithm of the covering number), leading to a significantly more efficient rate with dimensionality $d$ than most existing results. From the newly established complexity bounds, an important revelation is that the SAA and the canonical stochastic mirror descent (SMD) method, two mainstream solution approaches to SP, entail almost identical rates of sample efficiency, rectifying a long-standing theoretical discrepancy of the SAA from the SMD by the order of $O(d)$. Furthermore, this paper explores non-Lipschitzian scenarios where the SAA maintains provable efficacy, whereas corresponding results for the SMD remain unexplored, indicating the potential of the SAA's better applicability in some irregular settings.