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/2007
Entry Accepted: 12/29/2007
Entry Last Modified: 12/28/2007

Modify/Update this entry