On the complexity of stochastic integration

We study the complexity of approximating stochastic integrals with error ep silon for various classes of functions. For Ito integration, we show that t he complexity is of order epsilon (-1), even for classes of very smooth fun ctions. The lower bound is obtained by showing that Ito integration is not easier than Lebesgue integration in the average case setting with the Wiene r measure. The upper bound is obtained by the Milstein algorithm, which is almost optimal in the considered classes of functions. The Milstein algorit hm uses the values of the Brownian motion and the integrand. It is bilinear in these values and is very easy to implement. For Stratonovich integratio n, we show that the complexity depends on the smoothness of the integrand a nd may be much smaller than the complexity of Ito integration.