Title: WEAK CONTRACTION MAPPING AND OPTIMIZATION / CONFERENCE SUBMISSIONS

Abstract: 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.

1. INTRODUCTION:

Many gradient-based optimization methods, such as gradient descent method, Newton's method and so on, face great challenges in finding the global minimum point of a function. As is known, searching for the global minimum of a function with many local minima is difficult. In principle, the information from the derivative of a single point is not sufficient for us to know the global geometry property of the function. For a successful minimum point convergence, the initial point is required to be sufficiently good and the derivative calculation need to be accurate enough. In the gradientbased methods, the domain of searching area will be divided into several subsets with regards to local minima. And eventually it will converge to one local minimum depends on where the initial point locates at.

Let (X,d) be a metric space and let T:X → X be a mapping. For the inequality that, d(T (x), T (y)) ≤ qd(x, y), ∀x, y ∈ X.

(

EQUATION

2). The gradient-based methods are usually nonexpansive mapping the solution exists but is not unique for general situation. For instance, if the gradient descent method is written as a mapping T and the objective function has many local minima, then there are many fixed points accordingly. From the perspective of spectra of bounded operator, for a nonexpansive mapping any minima of the objective function is an eigenvector of eigenvalue equation T (x) = λx ,in which λ = 1. In the optimization problem, nonexpansive mapping sometimes works but their disadvantages are obvious. Because both the existence and uniqueness of solution are important so that the contractive mapping is more favored than the nonexpansive mapping(3; 4).

Banach fixed-point theorem is a very powerful method to solve linear or nonlinear system. But for optimization problems, the condition of contraction mapping T : X → X that d(T (x), T (y)) ≤ qd(x, y) is usually too strict and luxury. In the paper, we are trying to extend the Banach fixedpoint theorem to an applicable method for optimization problem, which is called weak contraction mapping.

In short, weak contraction mapping is a self mapping that always map to the subset of its domain.

It is proven that weak contraction mapping admits a fixed-point in the following section. How to apply the weak contraction mapping to solve an optimization problem? Geometrically, given a point, we calculate the height of this point and utilize a hyperplane at the same height to cut the objective function, where the intersection between the hyperplane and the objective function will form a contour or contours. And then map to a point insider a contour, which the range of this mapping is always the subset of its domain. The iteration of the weak contraction mapping yields a fixed-point, which coincides with the global minimum of the objective function.

2. WEAK CONTRACTION MAPPING AND THE FIXED-POINT:

In this section, the concept of weak contraction mapping and its fixed-point will be discussed in detail. Definition 1. Let (X, d and D) be a metric space. Both the metric measurement d and D are defined in the space. And the metric measurement D(X) refers to the maximum distance between two points in the vector space X:

EQUATION

Definition 2. Let (X, d and D) be a complete metric space. Then a mapping T : X → X is called weak contraction mapping on X if there exists

X 0 ⊆ X that D(X 0 ) < ∞, X i+1 = R(T (X i )) ⊂ X i , ∀i ∈ N 0 and a q ∈ [0, 1) such that D(X i+1 ) ≤ qD(X i ).

The weak contraction mapping is an extension of contraction map with a looser requirement that

D(X i+1 ) ≤ q(X i ), X i+1 ⊂ X i , T (x i ) ∈ X i+1 and x i ∈ X i . Theorem 1.

Let (X, d and D) be a non-empty complete metric space with weak contraction mapping T : X → X. Then T admits a unique fixed-point x * in X when X 0 is decided.

Let x 0 ∈ X be arbitrary and define a sequence {x n } be setting:

x n = T (x n-1

). The Theorem.1 is proven in the following lemmas.

By definition, there exists q ∈ [0, 1) such that D(X i+1 ) ≤ qD(X i ), ∀X i indicate the X 1 must be bounded such that D(X 1 ) < ∞. Lemma 1.1. {x n } is a Cauchy sequence in (X, d and D) and hence converges to a limit x * in X 0 .

Proof.Let m, n ∈ N such that m > n. d(x m , x n ) ≤ D(X n ) ≤ q n D(X 0 )

Let > 0 be arbitrary, since q ∈ [0, 1), we can find a large N ∈ N such that q N ≤ D(X 0 ) .

Hence, by choosing m, n large enough:

d(x m , x n ) ≤ q n D(X 0 ) ≤ D(X 0 ) D(X 0 ) = .

Thus, {x n } is Cauchy and converges to a point

x * ∈ X 0 . Lemma 1.2. x * is a fixed-point of T in X 0 .

Proof.

lim x→∞ x n = lim n→∞ T (x n-1 ) lim x→∞ x n = T ( lim n→∞ x n-1 )

Thus,x * = T (x * ).( 6)

Lemma 1.3. lim i→∞ D(X i ) = 0 Proof. lim i→∞ D(X i ) ≤ lim i→∞ q n D(X 0 ) = 0 Lemma 1.4.

x * is the only fixed-point of T in (X, d) with regards to a specific X 0 .

Proof. Suppose there exists another fixed-point y that T (y) = y, then choose the subspace X i that both the x * and y are the only elements in X i . By definition, X i+1 = R(T (X i )) so that, both the x * and y are elements in X i+1 , namely,

EQUATION

)

Let a hyperplane L cut the objective function f(x), the intersection of L and f(x) forms a contour (or contours). Observing that the contour (or contours) will divide X into two subspaces the higher subspace X > := {x | f (x) > h, ∀x ∈ X} and the lower subspace

X ≤ := {x | f (x) ≤ h, ∀x ∈ X} . The map T : X → X that x i+1 = T (x i ) ∈ X ≤ and there exists q ∈ [0, 1) such that D(X ≤ i+1 ) ≤ qD(X ≤ i ).

Geometrically, the range of weak contraction mapping shrinks over iterates, such that,

X ⊇ X ≤ 0 ⊃ X ≤ 1 ⊃ • • • ⊃ X ≤ i .

Based on lemma.1.3, the D(X i ) measurement converges to zero as i goes to infinity, namely,

lim i→∞ D(X i ) = 0

And the sequence of iteration x i+1 = T x i that x 0 , x 1 = T x 0 , ...,x i+1 = T i x 0 is Cauchy sequence that converge to the global minimum of objective function f(x) if the f(x) has a unique global minimum point. Lemma 1.5. Provided there is a unique global minimum point of an objective function, then x * is the global minimum point of the function.

Proof. The global minimum point must be insider the lower space {X ≤ i , ∀i ∈ N 0 }. Similar to the proof of uniqueness of fixed-point, suppose the global minimum point x min of objective function is different from x * . By measuring the distance between fixed-point X * and the global minimum point x min ,

0 ≤ d(x * , x min ) ≤ lim i→∞ D(X ≤ i ) = 0

The inequality above indicates d(x * , x min ) = 0, thus x * = x min .

Compared with contraction map, the weak contraction map is much easier to implement in the optimization problem as the requirement D(T

(x i )) ≤ D(x i ) is looser than d(T (x), T (y)) ≤ d(x, y).

Different from d(T (x), T (y)) ≤ d(x, y), the inequality D(T (x i )) ≤ D(x i ) doesn't require x i in sequence {x n } must move closer to each other for every step but confine the range of x i to be smaller and smaller. Therefore, the sequence {x n } can still be a Cauchy and has the asymptotic behavior to converge to the fixed-point.

3. OPTIMIZATION ALGORITHM IMPLEMENTATION:

Given the objective function f (x) has a unique global minimum point, the task is to find a weak contraction mapping T : X → X such that the unique fixed-point of mapping is the global minimum point of the function. The weak contraction map for the optimization problem can be implemented in following way. First, provide one arbitrary initial point x 0 to the function and calculate the height L = f (x 0 ) of the point and this height is the corresponding contours' level; Second, given the initial point map to another point inside the contour. One practical way is to solve the equation f (x) = L and get n number of roots which locate on a contour(or contours) and then the average of these roots is the updated searching point. And then repeat these process until the iteration of searching point converge.

This contour-based optimization algorithm utilizes the root-finding algorithm to solve the equation f (x) = L and get n number of roots. The starting point for the root-finding algorithm is generated by a random number generator. This stochastic process will help the roots to some extent widely distribute over the contour rather than concentrate on somewhere.

The inequality d(x m , x n ) ≤ q n D(X 0 ) indicates the rate of convergence, namely, the smaller q is the high rate of convergence will be achieved. Geometrically, the equation f (x) = L is the intersection of the objective function and a hyperplane whose height is L. We hope the hyperplane move downward in a big step during each iterate and the centroid of the contour refers to the most likely minimum position. Therefore, averaging the roots as an easy and effective way to map somewhere near the centroid. And there is a trade-off between the number of roots on the contour and the rate of convergence. The larger amount of roots on the contour, the more likely the average locates closer to the centroid of the contour, and then the less iterates are required for convergence. In another words, the more time spend on finding roots on a contour, the less time spend on the iteration, vice verse.

The global minimum point x * is the fixed-point of the iteration x i+1 = T x i and solves the equation T (x * ) = x * .( 8) And based on the above theorem, the sequence x, T (x), T 2 (x), T 3 (x)...T n (x)... is Cauchy that converge to the fixed-point.

First of all, the optimization algorithm has been tested on a convex function the Sphere function f (x) = x 2 i . The minimum is (0,0,0), where f (0, 0, 0) = 0. The iterations of roots and contours is shown in FIG. 1 and the update of searching point is shown in TABLE.1.

:



Figures and Tables:

Peer review (iclr2019):
 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 , the -sublevel set of is found using a root-finding algorithm, and the next point 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 , which is just as hard as optimizing 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 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 , however, consider the function in 1 dimension for all , and . For this function, the -sublevel sets are the entire domain until . 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 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 , and a function such as this could be obfuscated by writing it down with a long, complicated expression making it hard to identify 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."