Closing the Gaps: Optimality of Sample Average Approximation for Data-Driven Newsvendor Problems

We study the regret performance of Sample Average Approximation (SAA) for data-driven newsvendor problems with general convex inventory costs. In literature, the optimality of SAA has not been fully established under both α-global strong convexity and (α,β)-local strong convexity (α-strongly convex within the β-neighborhood of the optimal quantity) conditions. This paper closes the gaps between regret upper and lower bounds for both conditions. Under the (α,β)-local strong convexity condition, we prove the optimal regret bound of Θ(log T/α + 1/ (αβ)) for SAA. This upper bound result demonstrates that the regret performance of SAA is only influenced by α and not by β in the long run, enhancing our understanding about how local properties affect the long-term regret performance of decision-making strategies. Under the α-global strong convexity condition, we demonstrate that the worst-case regret of any data-driven method is lower bounded by Ω(log T/α), which is the first lower bound result that matches the existing upper bound with respect to both parameter α and time horizon T. Along the way, we propose to analyze the SAA regret via a new gradient approximation technique, as well as a new class of smooth inverted-hat-shaped hard problem instances that might be of independent interest for the lower bounds of broader data-driven problems.