We design an algorithm which finds an $\\epsilon$-approximate stationary point\n(with $\\|\\nabla F(x)\\|\\le \\epsilon$) using $O(\\epsilon^{-3})$ stochastic\ngradient and Hessian-vector products, matching guarantees that were previously\navailable only under a stronger assumption of access to multiple queries with\nthe same random seed. We prove a lower bound which establishes that this rate\nis optimal and---surprisingly---that it cannot be improved using stochastic\n$p$th order methods for any $p\\ge 2$, even when the first $p$ derivatives of\nthe objective are Lipschitz. Together, these results characterize the\ncomplexity of non-convex stochastic optimization with second-order methods and\nbeyond. Expanding our scope to the oracle complexity of finding\n$(\\epsilon,\\gamma)$-approximate second-order stationary points, we establish\nnearly matching upper and lower bounds for stochastic second-order methods. Our\nlower bounds here are novel even in the noiseless case.\n