Before revision:  The existence follows from an algorithm that converges from any starting point to such a point in a number of evaluations to f, \nabla_{y f(x,y), and  \nabla^2_y f(x,y), that is polynomial in 1/\varepsilon, the dimension d,  and the bounds on f and its Lipschitz constant .
After revision:  We prove the existence of such a point for any smooth function which is bounded and has Lipschitz Hessian. To prove existence, we introduce an algorithm that converges from any starting point to such a point in a number of evaluations to f, \nabla_{y f(x,y), and \nabla^2_y f(x,y), that is polynomial in 1/\varepsilon, the dimension d, and the bounds on f and its Lipschitz constant .