The weak contraction mapping is a self mapping that the range is always a subset of the domain, which admits a unique fixed-point. The iteration of weak contraction mapping is a Cauchy sequence that yields the unique fixed-point. A gradientfree optimization method as an application of weak contraction mapping is proposed to achieve global minimum convergence. The optimization method is robust to local minima and initial point position.
This paper proposes an approach to zeroth order optimization based on the Banach fixed point theorem for contractive maps. They define a "weak contraction map," argue that it will have a unique fixed point, and use this to propose a zeroth order optimization algorithm which iteratively identifies sublevel sets of the objective until convergence to the optimum.
At each iteration $t$, the $f(x_t)$-sublevel set of $f$ is found using a root-finding algorithm, and the next point $x_{t+1}$ is calculated by averaging a collection of points on the boundary of the sublevel set.
My main concern about this paper is that the optimization algorithm works neither in theory nor in realistic practical scenarios. There are two main issues:
(1) Identifying the sublevel sets requires solving equations of the form $f(x) = L$, which is just as hard as optimizing $f$ in the first place! In many realistic scenarios, e.g. machine learning problems, you know what the minimum value of the function is, so you could just solve $f(x) = f^*$ and be done in one step! Even if you don't know the optimal value, you could do some version of binary search. Also, for the two or three dimensional problems with relatively simple expressions that the authors experimented on, finding roots might be possible, but for higher dimensions or more complicated functions, finding these roots would require numerical optimization--which is the problem we are trying to solve in the first place.
(2) The authors seem to imply that this algorithm would work for any $f$, however, consider the function in 1 dimension $f(x) = 1$ for all $x \neq x^*$, and $f(x^*) = 0$. For this function, the $f(x_t)$-sublevel sets are the entire domain until $x_t = x^*$. It is unclear what "points on the contours" would mean in this case, but whatever those contours are, the algorithm would never converge on this function because the function value of $x_0, x_1, ...$ would all be the same, so the contours would remain the same. This function might seem a little ridiculous, but continuous or even Lipschitz version of this counterexample could be constructed by smoothing things out around $x^*$, and a function such as this could be obfuscated by writing it down with a long, complicated expression making it hard to identify $x^*$ by inspection.
There are some typos/typesetting issues. It seems that all of the theorem and lemma statements in Section 2 are missing the bold "Theorem" and "Lemma" heading. In the paragraph after equation (2), "weak contraction mapping" is defined twice, I believe the first definition should be just a "contraction mapping."