Before revision:  The nonconvexity-nonconcavity of f means that the problem of finding a global \varepsilon-min-max point cannot be solved in \mathrm{poly(d, 1{\varepsilon}) evaluations of f.
After revision:  In many of these applications f may be nonconvex-nonconcave, and finding a global \varepsilon-min-max point cannot be solved in \mathrm{poly(d, 1{\varepsilon}) evaluations of f.