- Sample Complexity of Smooth Stochastic Optimization Benjamin Armbruster(armbrusterstanford.edu) Abstract: Let $N(\epsilon,\delta)$ be the number of samples needed when solving a stochastic program such that the objective function evaluated at the sample optimizer is within $\epsilon$ of the true optimum with probability $1-\delta$. Previous results are of the form $N(\epsilon,\delta)=O(\epsilon^{-2}\log \delta^{-1})$. However, a smooth objective function is often locally quadratic at an interior optimum. For that case we use results on the convergence of the sample optimizers, to show that $N(\epsilon,\delta)=O(\epsilon^{-1}\log\delta^{-1})$. These results are both bounds and asymptotics. Hence we show for a common case (smooth objective functions with an interior optimum), that the number of samples needed is $O(\epsilon^{-1})$. This suggests that stochastic optimization is a practical approach for such problems. Keywords: Category 1: Stochastic Programming Citation: Download: [PDF]Entry Submitted: 12/28/2007Entry Accepted: 12/29/2007Entry Last Modified: 12/28/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.