If the objective function contains $$n$$ variables (e.g. $$f(x_1, ..., x_n)$$) in the Nelder-Mead algorithm (or other direct search methods), is there any known lower/upper bounds on how many times the algorithm needs to evaluate $$f$$ to achieve the desired value by precision $$\epsilon$$?

For instance, suppose $$f(x_1,x_2) = \text{Tr}(x_1x_2)$$ is defined on $$2$$-dimensional parameters $$(x_1,x_2) \in R^2$$, where $$-1 \leq x_1, x_2 \leq 1$$. Starting from random sets of parameters of $$v = (v_1, v_2), w = (w_1, w_2), y = (y_1, y_2)$$, the Nelder-Mead algorithm starts from a triangle in 2D and evaluate $$f(v), f(w), f(y)$$ and either reflect/expand/contract/shrink, and repeat the procedure until it converges to desired values of $$|f_{target} - f| \leqslant \epsilon$$. Is there theoretical bounds on how many times the algorithm evaluate $$f$$ until the convergence is taken?

There are no guarantees. In the worst case, if the function $$f$$ is particularly unfriendly, any optimization algorithm might need to evaluate $$f$$ on every possible combination of values, to find the optimum. (Consider a function $$f$$ that is zero on all points except for a single point, where it is very large or very small.) So, in effect, there are no bounds on the number of evaluations of $$f$$ needed.

With some optimization algorithms, one can obtain some bounds if we have additional conditions on $$f$$ (e.g., that it is Lipschitz), but my sense is that these bounds are typically not terribly useful in practice.

• Thanks. I'm looking into arxiv.org/pdf/1410.0390.pdf this morning, which seems to give $O(n^2/\epsilon^2)$ as the bound for minimizing gradient-free direct search algorithm for convex cost function. Apr 24, 2022 at 22:40
• @JonMegan, Yup! Looks like the kind of theoretical result I was thinking of. These papers need to be read carefully -- you may have overlooked some additional assumptions made in that paper. In particular, they assume that $f$ is Lipschitz (see Section 2). See the last paragraph of my answer for my comments on that style of result.
– D.W.
Apr 24, 2022 at 23:11
• I get it, thank you. I'm just wondering on the L-smooth function: do all smooth functions also $L$-smooth function? The reason I'm asking this is basically I have this form of function that I know it's smooth (i.e. differentiable in all domain) but I'm wondering how to prove the function is $L$-smooth, and if the statement above is true, then I can skip this proof and directly use the result from the paper. Apr 25, 2022 at 23:37
• @JonMegan, I don't know whether all smooth functions are Lipschitz, but it looks like the answer might be no (please investigate and verify for yourself): en.wikipedia.org/wiki/Lipschitz_continuity#Examples, math.stackexchange.com/q/2552893/14578
– D.W.
Apr 26, 2022 at 6:24
• Thanks, I agree that smooth functions are not Lipschitz, but am wondering if smooth functions are Lipschitz continuous gradient. I'll examine by myself. I have one more additional question: in the Table 1 in the paper above, do you know why the goal for nonconvex function is not $||f(x) - f(x^*)|| \leq \epsilon$ but rather $||\nabla f(x) || \leq \epsilon$? Apr 26, 2022 at 17:18