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 considers self-maps of metric spaces where the range is strictly smaller than the domain. Under this condition this tries to show that such a map has a fixed point. Now the paper suggests that such a "weakly contractive" map has a fixed point and tries to use such maps to find the global minima of functions. Even if all the proofs in this paper were right I do not see what this has anything to do with learning and why such a paper has been submitted to ICLR! This paper should probably be submitted to an optimization journal! The basic proofs here are completely unclear. Like in Lemma 1.2, its not even clear what the variable "x" is in the limit! The limit is being taken over the sequence index as far as I can see. Top of page 3 tries to describe an algorithm which can leverage weak contraction to get the global minima if it exists. But this description is hardly making any sense to me. I don*t see how the function to be optimized is being used to define the weakly contractive "T" map in the paragraph just below the proof of Lemma 1.4. (How is that parameter "h" even chosen in the definitions of X^{>} and X^{.leq}?) Without a clear pseudocode there is almost nothing concrete in the paper to judge correctness by. The experiments are all set-up on standardized functions which have nothing to do with learning setups. So the relevance of the experiments is completely unclear, let alone the fact that the description is too muddled up. Also the notation used in the paper is highly non-standard and that makes reading very difficult. For example "D" seems to be the symbol for diameter of the metric space. So D is a property of the metric space (X,d) and its not a part of the definition of the metric-space as the weird notation "(X,d and D)" seems to suggest! Also the definition 2 is ambiguous because it uses a {.cal R} which doesnt seem to have been defined anywhere!