{'fraction_non_alphanumeric': 0.06878238580833133, 'fraction_numerical': 0.030315882645816816, 'mean_word_length': 3.5926490514905147, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Block Coordinate Descent Only Converge to Minimizers

Given a non-convex twice continuously differentiable cost function with Lipschitz continuous gradient, we prove that all of block coordinate gradient descent, block mirror descent and proximal block coordinate descent converge to a local minimizer, almost surely with random initialization. Furthermore, we show that these results also hold true even for the cost functions with non-isolated critical points.


Introduction
A main source of difficulty for non-convex optimization over continuous spaces is the proliferation of saddle points. Actually, it is easy to find some instances where bad initialization of the gradient descent converges to unfavorable saddle point (Nesterov, 2004, Section 1.2.3). Although there exist such worst case instances in theory, many simple algorithms including the first order algorithms and their variants, perform extremely well in terms of the quality of solutions of continuous optimization.

Related work
Recently, a milestone result of the gradient descent was established by Lee et al. (2016). That is, the gradient descent method converges to a local minimizer, almost surely with random initialization, by resorting to a tool from topology of dynamical systems. Lee et al. (2016) assume that a cost function satisfies the strict saddle property. Equivalently, each critical point 2 x of f is either a local minimizer, or a "strict saddle", i.e., ∇ 2 f (x) has at least one strictly negative eigenvalue. They demonstrated that if f : R n → R is a twice continuously differentiable function whose gradient is Lipschitz continuous with constant L, then the gradient descent with a sufficiently small constant step-size α (i.e., x k+1 = x k −α∇f (x k ) and 0 < α < 1 L ) and a random initialization converges to a local minimizer or negative infinity almost surely.
There is a followup work given by Panageas and Piliouras (2016), which firstly proven that the results in Lee et al. (2016) do hold true even for cost function f with non-isolated critical points. One key tool they used is that for every open cover there is a countable subcover in R n . Moreover, Panageas and Piliouras (2016) have shown the globally Lipschitz assumption can be circumvented as long as the domain is convex and forward invariant with respect to gradient descent. In addition, they also provided an upper bound on the allowable step-size (such that those results hold true).
There are some prior works showing that first-order descent methods can indeed escape strict saddle points with the assistance of near isotropic noise. Specifically, Pemantle (1990) established convergence of the Robbins-Monro stochastic approximation to local minimizers for strict saddle functions and Kleinberg et al. (2009) demonstrated that the perturbed versions of multiplicative weights algorithm can converge to local minima in generic potential games. In particular, Ge et al. (2015) quantified the convergence rate of noise-added stochastic gradient descent to local minima. Note that the aforementioned methods requires the assistance of isotropic noise, which can significantly slowdown the convergence rate when the problem parameters dimension is large. In contrast, our setting is deterministic and corresponds to simple implementations of block coordinate gradient descent, block mirror descent and proximal block coordinate descent.

Our contribution
In this paper, under the assumption that f is twice continuously differentiable function with a Lipschitz continuous gradient over R n , we prove that all the following block coordinate descent methods with constant step size, (1) block coordinate gradient descent; (2) block mirror descent; and (3) proximal block coordinate descent, converge to a local minimizer, almost surely with random initialization. This result even holds for cost function with non-isolated critical points.
In other words, we not only affirmatively answer the open questions whether mirror descent or block coordinate descent does not converge to saddle points in Lee et al. (2016), but also show that the same results hold true for block mirror descent (including mirror descent as a special case) and proximal block coordinate descent. In addition, these results also hold true even for the cost functions with non-isolated critical points, which generalizes the results in Panageas and Piliouras (2016) as well.

Outline of the proof
Recall the main ideas in Lee et al. (2016). Suppose that g : R n → R n is an iterative mapping of an optimization method and the fixed point of g is the critical point of f as well. Then the following key properties of g, (i) g is a diffeomorphism; (ii) x * is a fixed point of g, then there is at least one eigenvalue of the Jacobian Dg(x * ), whose magnitude is strictly greater than one, imply the results in Lee et al. (2016) hold true.
Although the basic idea of the proof presented in this paper comes from Lee et al. (2016), answering the underlying questions for block coordinate type algorithms is not easy and the existing analysis methods are not applicable. In particular, the eigenvalue analysis of the Jacobian of the iterative mapping needs a nontrivial argument.
As compared to Property (ii), Property (i) is easier to verify since we can decompose the entire iterative mapping into multiple one-block updating case and then using the chain rule of diffeomorphism, we prove the entire updating is a diffeomorphism. In contrast, Property (ii) is very challenging because the Jocabian Dg(x * ) of block updating fashion at a saddle point is a non-symmetric matrix and a complex polynominal function of the original ∇f (x * ) with degree p (the number of the blocks of the decision variables). We overcome the above difficulties by the following two steps. Precisely, the first step is to transform the original Jacobian Dg αf (x * ) into a simpler form which can be handled easily. Next, based on the simple form of Dg αf (x * ), the second step is to prove that Dg(x * ) has at least one eigenvalue with magnitude strictly greater than one by resorting to Lemma 9.2 in appendices which follows essentially from Rouche's Theorem in complex analysis.

Notations and organization
Notations. Denote complex number z as z = a + bi, where a and b are real numbers and i is the imaginary unit with i 2 = −1. We also denote a = Re(z) and b = Im(z) as the real part and the imaginary part of z, respectively. For a matrix X, we denote eig(X) as the set of eigenvalues of X, X T as the transpose of X, X H as the conjugate transpose or Hermitian transpose of X, ρ(X) as the spectral radius of X (i.e., the maximum modulus of the eigenvalues of X), and X as the spectral norm of X. When X is a real symmetric matrix, let λ max (X) and λ min (X) denote the maximum and minimum eigenvalues of X, respectively. Moreover, for two real symmetric matrices X 1 and X 2 , X 1 ≻ X 2 (resp. X 1 X 2 ) means X 1 − X 2 is positive definite (resp. positive semi-definite). We use I n to denote the identity matrix with dimension n, and we will simply use I when it is clear from context what the dimension is. For square matrices X s ∈ R ns×ns , s = 1, 2, . . . , p, we denote Diag (X 1 , X 2 , . . . , X p ) as the block-diagonal matrix with X s being the s-th diagonal block. For square matrices X s ∈ R n×n , s = 1, . . . , p, and t, k ∈ {1, 2, . . . , p}, we use k s=t X s to denote the continued products X t · X t+1 . . . X k−1 · X k if t ≤ k and X t · X t−1 . . . X k+1 · X k if t > k, respectively. P ν denotes the probability with respect to a prior measure ν, which is assumed to be absolutely continuous with respect to Lebesgue measure.
Organization. In section 2, we introduce the basic setting and definitions used throughout the paper. Section 3 provides the main results for block coordinate gradient descent method. The main results for block mirror descent and proximal block coordinate descent are given in Section 4 and Section 5, respectively. Section 6 provides several lemmas. Finally, we conclude this paper in Section 7. The detailed proofs of some lemmas and propositions are presented in Section 9 .

Preliminaries
We consider optimization model where we make the following blanket assumption: Assumption 2.1 f is twice continuously differentiable function whose gradient is Lipschitz continuous over R n , i.e., there exists a parameter L > 0 such that ∇f (x) − ∇f (y) ≤ L x − y for every x, y ∈ R n .
(2.2) Throughout this paper, in order to introduce the block coordinate descent method, we assume the vector of decision variables x has the following partition: where x(s) ∈ R ns , n 1 , n 2 , . . ., n p are p positive integer numbers satisfying p s=1 n s = n.
Moreover, we use the notations in Nesterov (2012) and define matrices U s ∈ R n×ns , the s-th block-column of I n , s = 1, . . . , p, such that U 1 , U 2 , . . . , U p = I n .
(2.4) Clearly, according to our notations, we have x(s) = U T s x for every x ∈ R n , s = 1, . . . , p. Consequently, x = p s=1 U s x(s) and the derivative corresponding variables in the vector x(s) can be expressed as

The BCGD method description
For ease of later reference and also for the sake of clarity, based on notations in Section 2, we present a detailed description of the BCGD method (Beck and Tetruashvili, 2013) for problem (2.1) below.
Method 3.1 (BCGD) Step (k = 0, 1, . . .): Set x 0 k = x k and define recursively In what follows, for a given step size α > 0, we use g s αf to denote the corresponding gradient mapping with respect to x(s), i.e., It is clear that, given x k , the above BCGD method generates x k+1 in the following manner, where composite mapping By simple computation, the Jacobian of g s αf is given by By using the chain rule, we obtain the following Jacobian of the mapping g, i.e., where y 1 = x, and y s = g s−1 αf (y s−1 ), s = 2, . . . , p. Given the above basic notations, as mentioned in Section 1, it is sufficient for us to prove that the iterative mapping g αf admits the following two key properties: (i) g αf is a diffeomorphism; (ii) x * is a fixed point of g, then there is at least one eigenvalue of the Jacobian Dg αf (x * ), whose magnitude is strictly greater than one.
In what follows, we will mainly concern with proving the above two properties of g αf . Specifically, Subsections 3.2 and 3.3 present their proofs, respectively.
3.2. The iterative mapping g αf of BCGD method is a diffeomorphism In this subsection, we first present the following Lemma 3.1 which shows that g s αf , s = 1, . . . , p, are diffeomorphisms. Based on this lemma, then we further prove that g αf is a diffeomorphism as well.
Proof. The proof of Lemma 3.1 is lengthy and has been relegated to the Appendix.
Given the above lemma, we immediately obtain the following result.
Proposition 3.1 Under Assumption 2.1, the mapping g αf defined by (3.7) with step size α < 1 L is a diffeomorphism. Proof. It follows from Proposition 2.15 in Lee (2013) that the composition of two diffeomorphisms is also a diffeomorphism. Using this fact and the previous Lemma 3.1, the proof is completed.
Remark 3.1 Note that, in order to guarantee invertibility of Dg αf (x), Eq. (9.145) in the the appendix must hold, which clearly implies that α < 1 L is necessary. 3.3. Eigenvalue analysis of the Jacobian of g αf at a strict saddle point In this subsection, we will analyze the eigenvalues of the Jacobian of g αf at a strict saddle point and show that it has at least one eigenvalue with magnitude greater than one, which is a crucial part in our entire proof. The proof mainly involves two steps.
More specifically, the first step is to transform the original Jacobian Dg αf (x * ) into a simpler form which can be dealt with more easily. Furthermore, based on the simple form of Dg αf (x * ), the second step is to prove that Dg(x * ) has at least one eigenvalue with magnitude strictly greater than one by resorting to Lemma 9.2 in Appendix which follows essentially from Rouche's Theorem in complex analysis.
In what follows, we assume that x * ∈ R n is a strict saddle point. Hence, g s αf (x * ) = x * , s = 1, 2, . . . , p,. By chain rule (3.9), we have (3.10) Since eig (Dg αf (x * )) = eig (Dg αf (x * )) T , it is sufficient for us to analyze the eigenvalues of matrix (Dg αf (x * )) T . In addition, Eq. (3.10) leads to where the second equality is due to (3.8). For the sake of simplicity, we denote matrix ∇ 2 f (x * ) as matrix A ∈ R n×n with p × p blocks. Specifically, and its (s, t)-th block is defined as Furthermore, we denote the s-th block-row of A as (3.14) Based on the above notations, we have and Combining (3.11) and (3.15), we have In order to analyze the eigenvalues of the above matrix, we furthermore define a matrix below: (3.18) or equivalently, (Dg αf (x * )) T = I n − αG. (3.19) The above relation (3.19) clearly means that In the rest of this subsection, our focus is on analyzing the eigenvalues of G. We first introduce the following Lemma 3.2 and Lemma 3.3 which assert a particular relation between G and A.
Lemma 3.2 Assume that x * ∈ R n is a strict saddle point, G is given by (3.18), U s and A s are defined by (2.4) and (3.14), respectively, s = 1, . . . , p. Then, Proof. The proof of Lemma 3.2 is lengthy and has been relegated to the Appendix.
In order to give a clear and simple expression of G, we further define the strictly block lower triangular matrix based on A below: with p × p blocks and its (s, t)-th block is given by Similarly, we denote the s-th block-row ofǍ aš A s Ǎ st 1≤t≤p , s = 1, . . . , p. (3.24) The following lemma plays an important role in this subsection because it gives a simple expression of G in terms of A andǍ, which allows us to analyze the eigenvalues of G more easily.
Lemma 3.3 Let x * ∈ R n be a strict saddle point. Assume that G, A andǍ are defined by (3.18), (3.12) and (3.22), respectively. Then, Proof. We assume that G has the following partition: where G s ∈ R ns×n is the s-th block-row of G, s = 1, 2, . . . , p. Consequently, we have where in the second equality we use Lemma 3.2 and the last equality is due to the definition ofǍ s in (3.24). Since the above equality holds for any s, it immediately follows that which is equivalent to I n + αǍ G = A.
Note that I n +αǍ is an invertible matrix becauseǍ is a block strictly lower triangular matrix. Premultiplying both sides of the above equality by I n + αǍ −1 , we arrive at (3.25). Therefore, the lemma is proved.
The following proposition plays a central role in this subsection because it provides a sufficiently exact description of the distribution of the eigenvalues of G. More importantly, it leads immediately to the subsequent Proposition 3.3 which asserts that, there is at least one eigenvalue of Jacobian of iterative mapping g αf at a strict saddle point, whose magnitude is strictly greater than one.
Proposition 3.2 Assume that x * ∈ R n is a strict saddle point, and G is defined by (3.18) with α ∈ 0, 1 L , where L is determined by (2.2). Then, there exists at least one eigenvalue of G which lies in closed left half complex plane excluding origin, i.e., where Proof. It follows from Lemma 3.3 that G has the following expression: where A andǍ are defined by (3.12) and (3.22), respectively. Since A = ∇ 2 f (x * ) and x * is a strictly saddle point, A has at least one negative eigenvalue. Furthermore, by applying Lemma 6.4 in Section 6 with identifications A ∼ B,Ǎ ∼B, α ∼ β and ρ(A) ∼ ρ(B), we have where Ω is defined by (3.27).
Proposition 3.3 Assume Assumption 2.1 holds. Suppose that BCGD iterative mapping g αf is defined by (3.7) with α ∈ 0, 1 L , L is determined by (2.2), and x * ∈ R n is a strict saddle point. Then Dg αf (x * ) has at least one eigenvalue whose magnitude is strictly greater than one.
Proof. Recalling Eq. (3.20), we have where G = 1 α I n − (Dg αf (x * )) T is defined by (3.18). Combined with (3.30), Proposition 3.2 implies that there exists at least one eigenvalue of (Dg αf (x * )) T which can be expressed as where a + bi belongs to Ω defined by (6.130), or equivalently, Consequently, its magnitude is where the first inequality is due to a ≤ 0 and α > 0; and the second inequality thanks to (a, b) = (0, 0). Note that the eigenvalues of Dg αf (x * ) are the same as those of (Dg αf (x * )) T . Thus, the proof is finished.

Main results of BCGD
We first introduce the following proposition, which asserts that the limit point of the sequence generated by the BCGD method 3.1 is a critical point of f . Proposition 3.4 Under Assumption 2.1, if {x k } k≥0 is generated by the BCGD method 3.1 with 0 < α < 1 L , lim k x k exists and denote it as x * , then x * is a critical point of f , i.e., ∇f (x * ) = 0.
Proof. Since {x k } k≥0 is generated by the BCGD method 3.1, Since g αf is a diffeomorphism, we immediately know that x * is a fixed point of g αf . It follows easily from the definition (3.7) of g αf that ∇f (x * ) = 0. Thus the proof is finished.
Armed with the results established in previous subsections and the above Proposition 3.4, we now state and prove our main theorems of BCGD. Specifically, similar to the proof of Theorem 4 in Lee et al. (2016), the center-stable manifold theorem in Smale (1967); Shub (1987); Hirsch et al. (1977) is a primary tool because it gives a local characterization of the stable set. Hence, we first rewrite it as follows.
Theorem 3.1 (Shub, 1987, Theorem III. 7) Let 0 be a fixed point for the C r local differomorphism φ : U −→ E where U is a neighborhood of zero in the Banach space E and ∞ > r ≥ 1. Let E sc E u be the invariant splitting of R n into the generalized eigenspaces of Df (0) corresponding to eigenvalues of absolute value less than or equal to one, and greater than one. Then there is a local φ invariant C r embedded disc W sc loc tangent to E sc at 0 and a ball B around zero in an adapted norm such that φ(W sc loc ) B ⊂ W sc loc , and φ −k (B) ⊂ W sc loc . The following theorem is similar to Theorem 4 in Lee et al. (2016).
Theorem 3.2 Let f be a C 2 function and x * be a strict saddle. If {x k } is generated by the BCGD method 3.1 with 0 < α < 1 L , then Proof. Proposition 3.4 implies that, if lim k x k exists then it must be a critical point. Hence, we consider calculating the Lebesgue measure (or probability with respect to the prior measure ν) of the set lim Furthermore, since Proposition 3.1 means the BCGD iterative mapping g αf is a diffeomorphism, we replace φ and fixed point by g αf and the strict point x * in the above Stable Manifold Theorem 3.1, respectively. Then the manifold W s loc (x * ) has strictly positive codimension because of Proposition 3.3 and x * being a strict saddle point. Hence, W s loc (x * ) has measure zero. In what follows, we are able to apply the same arguments as in Lee et al. (2016) to finish the proof of the theorem. Since the proof follows a similar pattern, it is omitted.
Given the above Theorem 3.2, we immediately obtain the following Theorem 3.3 and its corollary by the same arguments as in the proofs of Theorem 2 and Corollary 12 in Panageas and Piliouras (2016). Therefore, we omit their proofs.
Theorem 3.3 (Non-isolated) Let f : R n → R be a twice continuously differentiable function and sup x∈R n ∇f (x) ≤ L < ∞. The set of initial points x ∈ R n , for each of which the BCGD method 3.1 with step size 0 < α < 1 L converges to a strict saddle point, is of (Lebesgue) measure zero, without assumption that critical points are isolated.
A straightforward corollary of Theorem 3.3 is given below: Corollary 3.1 Assume that the conditions of Theorem 3.3 are satisfied and all saddle points of f are strict. Additionally, assume lim k g k αf (x) exists for all x in R n . Then where g αf is defined by (3.5) and x * is a local minimum .

The BMD method
In this section, we will extend the above results to the BMD method in Beck and Teboulle (2003) and Juditsky and Nemirovski (2014). In other words, the BMD method, based on Bregman's divergence, converges to minimizers as well, almost surely with random initialization.

The BMD method description
For clarity of notation, recall the vector of decision variables x has been assumed to have the following partition (see (2.3)): . . .
where x(t) ∈ R nt , and n 1 , n 2 , . . ., n p are p positive integer numbers satisfying p t=1 n t = n.
Correspondingly, we assume a set of variables x s k have the following partition as well: . . . where x s k (t) ∈ R nt ; t, s = 1, . . . , p; k = 0, 1, . . .. In order to introduce the BMD method, we assume there are p strictly convex and continuously differentiable functions ϕ t : R nt → R, t = 1, 2, . . . , p. Furthermore, we make the following assumption.
Remark 4.1 We should mention that Bregman divergence is generally defined for a continuously differentiable and strongly convex function which is not necessarily twice differentiable. Here, the twice differentiability of ϕ s seems a necessary and reasonable condition for our subsequent analysis because the existence of the Jacobian of the iterative mapping depends directly on ∇ 2 ϕ t (see (4.47)).
Step (k = 0, 1, . . .): Set x 0 k = x k and define recursively for s = 1, 2, . . ., p : t = 1, 2, . . . , p, If t = s, x s k (t) = arg min (4.39) Note that ϕ s is a strongly convex function. Then it is easily seen from (4.36) that B ϕs (x(s), y(s)) is a strongly convex function with respect to x(s) if y(s) is fixed. Hence, let x s k (s) be the unique solution of problem (4.38). The KKT condition implies that which is equivalent to Combined with the assumption about ϕ s , Lemma 9.4 in Appendix leads immediately to the existence of the inverse mapping of ∇ϕ s . Let [∇ϕ s ] −1 denote its inverse.
It follows from Eqs. (4.34), (4.38), and (4.39) that In what follows, we define ψ s : R ns → R ns as (4.44) It is clear that, given x k , the above BMD method generates x k+1 in the following manner, where the composite mapping Additionally, it follows from (4.44) that, for each s = 1, 2, . . . , p, the Jacobian of ψ s is given below: where the first equality is due to chain rule; the second equality holds because of chain rule and inverse function theorem in Spivak (1965); the last equality follows from the definition of U s and ∇ 2 f (x) = By using the chain rule, we obtain the following Jacobian of the mapping ψ, i.e., where y 1 = x, and y s = ψ s−1 (y s−1 ), s = 2, . . . , p.

The iterative mapping ψ of BMD is a diffeomorphism
In this subsection, we first present the following Lemma 4.1 which shows that ψ s , s = 1, . . . , p, are diffeomorphisms. Based on this lemma, then we further prove that ψ is a diffeomorphism as well.
Proof. The proof is lengthy and has been relegated to the Appendix.
Proposition 4.1 The mapping ψ defined by (4.46) with step size α < µ L is a diffeomorphism.
Proof. It follows from Proposition 2.15 in Lee (2013) that the composition of two diffeomorphisms is also a diffeomorphism. Using this fact and previous Lemma 4.1, the proof is completed.

Eigenvalue analysis of the Jacobian of ψ at a strict saddle point
In this subsection, we will analyze the eigenvalues of the Jacobian of ψ at a strict saddle point and show it has at least one eigenvalue with magnitude greater than one, which is a crucial part.
Suppose that x * ∈ R n is a strict saddle point. Then ∇f (x * ) = 0 and ψ s (x * ) = x * , s = 1, 2, . . . , p. Hence, where the second equality is due to ∇f (x * ) = 0; the third equality thanks to [∇ϕ s ] −1 (∇ϕ s (x * (s))) = x * (s). Furthermore, since the eigenvalues of Dψ (x * ) are the same as those of {Dψ (x * )} T , it suffices to analyze the eigenvalues of {Dψ (x * )} T . It follows from (4.48) that where the third equality uses (4.49) and the last equality is due to definition (3.14) of A s . Similar to the case of BCGD, we furthermore define or equivalently, (Dψ(x * )) T = I n − α G. (4.52) The above relation (4.52) clearly means that In order to achieve a simple form of G, we first introduce the following notations.
Note that A, A st and A s have been defined by (3.12), (3.13) and (3.14), respectively. Then where A st ∈ R ns×nt and A s ∈ R ns×n denote the (s, t)-th block and the s-th block-row of A, respectively. We further define the (s, t)-th block and the s-th block-row of T , respectively. Given the above notations, we further denote the strictly block lower triangular matrix based on T aš with p × p blocks and its (s, t)-th block is given by (4.59) Substituting T s (see its definition (4.57)) into (4.50), we deduce that (4.60) The following Lemma shows that G still has a form similar to G defined by (3.18) . In fact, it just replaces A andǍ in (3.18) by T andŤ , respectively.
Switching the order of the products (4.62) by moving the first component to the last, we get a new matrix (4.63) Note that eig (XY ) = eig (Y X) for any two square matrices, thus eig G = eig G , (4.64) which shows that it suffices to analyze eigenvalues of G. Before presenting Lemma 4.4, the grand result of this subsection, we first provide two special properties of Ψ − 1 2 A Ψ − 1 2 T which will be used in the subsequent analysis.
Lemma 4.3 Let x * ∈ R n be a strict saddle point. Assume that A and Ψ are define by (3.12) and (4.54), respectively. Then, T has at least one negative eigenvalue.
(ii) The spectral radius of the symmetric matrix T is a congruent transformation of A, they have same index of inertia. In addition, x * is a strict saddle point implies that A = ∇ 2 f (x * ) (see its definition (3.12)) has at least one negative eigenvalue. Hence, T has at least one negative eigenvalue as well. (ii) In what follows, we will prove that T L µ I n holds. It follows easily from (2.2) and Lemma 7 in Panageas and Piliouras (2016) (4.66) In addition, Eqs. (4.35) means that where the last inequality is due to the definition of µ (see it definition in (4.37)).
Consequently, combined with the definition (4.54), the above inequalities imply that Multiplying the left-hand side of the above inequalities by Ψ − 1 2 and the right-hand side by Ψ − 1 2 T , respectively, we arrive at (4.70) Thus, the proof is finished.
Based on the above Lemma 4.3 and Lemma 6.4 in Section 6, we will prove that there exists at least one eigenvalue of G defined by (4.63) which belongs to Ω defined by (6.130).
Lemma 4.4 Suppose that x * ∈ R n is a strict saddle point, and is given by (4.63) with α ∈ 0, µ L , where L is determined by (2.2); µ, A andǍ are given by (4.37), (3.12) and (3.22), respectively; and Ψ − 1 2 denotes the unique symmetric, positive definite square root matrix of the symmetric, positive definite matrix Ψ −1 defined by (4.55). Then, there exists at least one eigenvalue of the G which belongs to Ω defined by (3.27).
Proof. Since x * is a strict saddle point and A = ∇ 2 f (x * ) is given by (3.12), T has at least one negative eigenvalue and the spectral radius of the symmetric matrix Ψ , whereǍ is defined by (3.22) . Therefore, by applying Lemma 6.4 in Section 6 with identifications we know, for any α ∈ 0, µ L , there exists at least one eigenvalue ofḠ belonging to Ω defined by (3.27).
In addition, Lemma 4.3 implies that gradient Lipschitz continuous constant Then, the above arguments clearly imply that the proposition holds true.
The following proposition shows that the Jacobian of the BMD iterative mapping ψ defined by (4.46) at a strict saddle point admits at least one eigenvalue whose magnitude is strictly greater than one.
Proposition 4.2 Assume that BMD iterative mapping ψ is defined by (4.46) with α ∈ 0, µ L , and x * ∈ R n is a strict saddle point. Then Dψ (x * ) has at least one eigenvalue whose magnitude is strictly greater than one.
Proof. Note that (4.64) and (4.63) imply that G and G have same eigenvalues. Consequently, Lemma 4.4 means there exists at least one eigenvalue of the G lying in Ω defined by (6.130).
In what follows, with the identifications Dψ (x * ) ∼ Dg αf (x * ), G ∼ G and L µ ∼ L, we are able to apply the same arguments as in the proof of Proposition 3.3 in Subsection 3.3 to finish the proof. Since the proof follows a similar pattern, it is therefore omitted.

Main results of BMD method
We first introduce the following proposition, which asserts that the limit point of the sequence generated by the BMD method 4.1 is a critical point of f . Proof. First, since {x k } k≥0 is generated by the BMD method 4.1, then x k = ψ k (x 0 ) 5 , where the BMD iterative mapping ψ is defined by (4.54). Hence, lim Second, notice that ψ and ψ s are defined by (4.46) and (4.44), respectively. If (4.74) Since Lemma 9.4 in Appendix asserts that ∇ϕ s is a diffeomorphism, then [∇ϕ s ] −1 is a diffeomorphism as well. Thus it follows from (4.74) that We arrive at ∇ s f (x * ) = 0, s = 1, 2, . . . , p, (4.76) or equivalently, x * is a stationary point of f . Thus the proof is finished.
Armed with the results established in previous subsections, we now state and prove our main theorem of the BMD method, whose proof is similar to that of Theorem 3.2 in Subsection 3.4. However, its proof is still given as follows in detail for the sake of completeness.
Theorem 4.1 Let f be a C 2 function and x * be a strict saddle point. If {x k } is generated by the BMD method 4.1 with 0 < α < µ L , then Proof. First, Proposition 4.3 implies that, if lim k x k exists then it must be a critical point. Hence, we consider calculating the Lebesgue measure (or probability with respect to the prior measure ν) of the set lim Second, since Proposition 4.1 means the BMD iterative mapping ψ is a diffeomorphism, we replace φ and fixed point by ψ and the strict saddle point x * in the above Stable Manifold Theorem 3.1 in Subsection 3.4, respectively. Then the manifold W s loc (x * ) has strictly positive codimension because of Proposition 4.2 and x * being a strict saddle point. Hence, W s loc (x * ) has measure zero. In what follows, we are able to apply the same arguments as in Lee et al. (2016) to finish the proof of the theorem. Since the proof follows a similar pattern, it is therefore omitted.
Given the above Theorem 4.1, we immediately obtain the following Theorem 4.2 and its corollary by the same arguments as in the proofs of Theorem 2 and Corollary 12 in Panageas and Piliouras (2016). Therefore, we omit their proofs.
Theorem 4.2 (Non-isolated) Let f : R n → R be a twice continuously differentiable function and sup x∈R n ∇f (x) 2 ≤ L < ∞. The set of initial conditions x ∈ R n so that the BMD method 4.1 with step size 0 < α < µ L converges to a strict saddle point is of (Lebesgue) measure zero, without assumption that critical points are isolated.
A straightforward corollary of Theorem 4.2 is given below: where ψ is defined by (4.54) and x * is a local minimum.

The PBCD method
In this section, we will prove that the PBCD method in Hong et al. (2017); Fercoq and Richtrik (2013); Hong et al. (2015) converges to minimizers as well, almost surely with random initialization.

The PBCD method description
For clarity of notation, recall the vector of decision variables x has been assumed to have the following partition (see (2.3)): . . .
where x(t) ∈ R nt , n 1 , n 2 , . . ., n p are p positive integer numbers satisfying t s=1 n t = n.
Correspondingly, we assume a set of variables x s k has the following partition as well: . . .
where x s k (t) ∈ R nt ; t, s = 1, . . . , p; k = 0, 1, . . .. Given the above notations, the detailed description of the PBCD method for problem (2.1) is given below. (5.80) is a strongly convex function with respect to variable x(s). Hence, let x s k (s) be the unique minimizer of problem (5.79). Then by the KKT condition, which is equivalent to Recall that, for a given step size α > 0, we have used g s αf (see its definition in (3.5)) to denote the gradient mapping of function f with respect to variable x(s), i.e., (5.83) By using same notations, for a given step size α > 0, the gradient mapping of function −f with respect to variable x(s) is It is obvious that Eqs. (5.82) and (5.84) imply that Note that Lemma 5.2 in Subsection 5.2 implies that g s α(−f ) is a diffeomorphism with α ∈ 0, 1 L . We denote its inverse as g s α(−f ) −1 which is a diffeomorphism as well.
Then, (5.85) is further equivalent to −1 (x s−1 k ), s = 1, . . . , p. (5.86) Lemma 5.1 Assume that g s α(−f ) is determined by (5.84), s = 1, . . . , p. Given x k , the above PBCD method generates x k+1 in the following manner, where the composite iterative mapping [g α(−f ) ] −1 denotes the inverse mapping of the following mapping Proof. According to the PBCD method and (5.86), we have x 0 k = x k and Thus the proof is finished.
By simple computation, the Jacobian of g s α(−f ) is given by where Since g α(−f ) (x) is defined by (5.88), the chain rule implies that the Jacobian of the mapping g is where y 1 = x, and y s = g s−1 α(−f ) (y s−1 ), s = 2, . . . , p.
5.2. The iterative mapping [g α(−f ) ] −1 of the PBCD method is a diffeomorphism In this subsection, we first present the following Lemma 5.2 which shows that g s α(−f ) , s = 1, . . . , p, are diffeomorphisms. Based on this lemma, then we further prove that [g α(−f ) ] −1 is a diffeomorphism as well.
Proof. Note that L is also the Lipschitz constant of gradient of −f . By replacing −f with f , Lemma 3.1 in Subsection 3.2 implies that g s α(−f ) is a diffeomorphism with α ∈ 0, 1 L , the proof is completed.
Proof. Note that Lemma 5.2 implies that g s α(−f ) , s = 1, . . . , p, defined by (3.5) are diffeomorphisms and g α(−f ) is defined (5.88) with 0 < α < 1 L . By a similar argument as in the proof of Proposition 3.1 in Subsection 3.2, we know g α(−f ) is a diffeomorphism. Thus its inverse is a diffeomorphism as well, the proof is completed.

Eigenvalue analysis of the Jacobian of [g α(−f ) ] −1 at a strict saddle point
In this subsection, we consider the eigenvalues of the Jacobian of [g α(−f ) ] −1 at a strict saddle point, which is a crucial part in our entire proof.
If x * ∈ R n is a strict saddle point, then ∇f (x * ) = 0. Consequently, which implies that More importantly, the above Eq. (5.94) implies that the Jacobian of [g α(−f ) ] −1 at x * can be expressed as which is due to inverse function theorem in Spivak (1965). Hence, in order to show that there is at least one eigenvalue of D [g α(−f ) ] −1 (x * ) whose magnitude is strictly greater than one, we first argue that Dg α(−f ) (x * ) still has a similar structure as that of Dg αf (x * ) in Section 3. Specifically, chain rule (5.92) and Eq. (5.94) imply (5.96) Moreover, the eigenvalues of Dg α(−f ) (x * ) are the same as those of its transpose. Hence, we compute where the second equality is due to (5.90). Now we define 98) or equivalently, (Dg α(−f ) (x * )) T = I n − αH. (5.99) The above relation (5.99) clearly means that For the sake of clarification, we rewrite A defined by (3.12) below: and its (s, t)-th block is given by with p × p blocks and its (s, t)-th block is given bŷ Based on the above notations, we are able to obtain the following Lemma 5.3 which is similar to Lemma 3.3 in Subsection 3.3. It gives a simple expression of H in terms of A andÂ. In what follows, we proceed now in a way similar to the case of BCGD, although some specific technical difficulties will occur in the analysis.
The following proposition shows that the Jacobian of the PBCD iterative mapping [g α(−f ) ] −1 determined by (5.88) at a strict saddle point admits at least one eigenvalue whose magnitude is strictly greater than one, which plays a key role in this subection.
Proposition 5.2 Assume that PBCD iterative mapping [g α(−f ) ] −1 is determined by (5.88) and x * ∈ R n is a strict saddle point. Then D [g α(−f ) ] −1 (x * ) has at least one eigenvalue whose magnitude is strictly greater than one.
(5.108) It follows from Lemma 5.3 that H has the following expression: where the last equality is due to (5.109).

Main results of PBCD
We first introduce the following proposition, which asserts that the limit point of the sequence generated by the PBCD method 5.1 is a critical point of f . Proof. Notice that {x k } k≥0 is generated by the PBCD method 5.1. We clearly is a diffeomorphism, we immediately know that x * is a fixed point of [g α(−f ) ] −1 .
Equivalently, it is a fixed point of g α(−f ) . It follows easily from the definition (5.88) of g α(−f ) that ∇f (x * ) = 0. Thus the proof is finished.
Armed with the results established in previous subsections and the above Proposition 5.3, we now state and prove our main theorem of PBCD, whose proof is similar to that of Theorem 3.2 in Subsection 3.4. However, its proof is still given as follows in detail for the sake of completeness.
Theorem 5.1 Let f be a C 2 function and x * be a strict saddle point. If {x k } k≥0 is generated by the PBCD method 5.1 with 0 < α < 1 L , then Proof. First, Proposition 5.3 implies that, if lim k x k exists then it must be a critical point. Hence, we consider calculating the Lebesgue measure (or probability with respect to the prior measure ν) of the set lim Second, since Proposition 5.1 means PBCD iterative mapping [g α(−f ) ] −1 is a diffeomorphism, we replace φ and fixed point by [g α(−f ) ] −1 and the strict saddle point x * in the above Stable Manifold Theorem 3.1 in Subsection 3.4, respectively. Then the manifold W s loc (x * ) has strictly positive codimension because of Proposition 5.2 and x * being a strict saddle point. Hence, W s loc (x * ) has measure zero. In what follows, we are able to apply the same arguments as in Lee et al. (2016) to finish the proof of the theorem. Since the proof follows a similar pattern, it is therefore omitted.
Given the above Theorem 5.1, we immediately obtain the following Theorem 5.2 and its corollary by the same arguments as in the proofs of Theorem 2 and Corollary 12 in Panageas and Piliouras (2016). Therefore, we omit their proofs.
Theorem 5.2 (Non-isolated) Let f : R n → R be a twice continuously differentiable function and sup x∈R n ∇f (x) 2 < ∞. The set of initial conditions x ∈ R n so that the PBCD method 5.1 with step size 0 < α < 1 L converges to a strict saddle point is of (Lebesgue) measure zero, without assumption that critical points are isolated.
A straightforward corollary of Theorem 5.2 is given below: Corollary 5.1 Assume that the conditions of Theorem 5.2 are satisfied and all saddle points of f are strict. Additionally, the composite iterative mapping [g α(−f ) ] −1 denotes the inverse mapping of g α(−f ) , assume lim where [g α(−f ) ] −1 denotes the inverse mapping of g α(−f ) defined by (5.88) and x * is a local minimum.

Several Technical Lemmas
In what follows, we will provide several technical lemmas (Lemmas 6.1-6.6), which provide the basis for proving that Jacobian of iterative mappings including g αf defined by (3.7) in Section 3, ψ defined by (4.54) in Section 4 and [g α(−f ) ] −1 defined by (5.87) in Section 5 at a strict saddle point has at least one eigenvalue with magnitude strictly greater than one. In particular, Lemma 6.4 gives a sufficiently exact description of the distribution of the eigenvalues of matrix with the kind of structure as G which is related to g αf and ψ, while Lemmas 6.5 and 6.6 give the similar description of that of the eigenvalues of matrix with the kind of structure as H which is related to g α(−f ) .
Before presenting the grand result of this subsection, we first introduce two notations which will be used in what follows. Assume B ∈ R n×n is symmetric matrix with p × p blocks. Specifically, with p × p blocks and its (s, t)-th block is given bŷ Given the above notations, then we have the following Lemma 6.1, which asserts that, for any unit vector η ∈ C n , the real parts of η HB η and η HB η are both bounded by the spectral radius of B.
Lemma 6.1 Assume that B,B andB are defined by (6.111), (6.113) and (6.115), respectively. Then for an arbitrary n dimensional vector η ∈ C n with η = 1, Assume that η ∈ C n and η = 1. On the one hand, where the first inequality is due to (6.121); the first equality holds because of (6.120); the third equality follows from the fact thatB is a real matrix; and (6.122) amounts to the last inequality.
On the other hand, we also have where the first inequality is due to (6.121); the first equality holds because of (6.120); the third equality follows from the fact thatB is a real matrix; and (6.122) amounts to the last inequality. Clearly, Eqs. (6.123) and (6.124) lead to (6.117). By using the same argument, we know (6.118) holds true.
The following lemma states that, if B is invertible, the real part of the eigenvalues of B −1 I n + βB does not equal zero for any β ∈ 0, 1 ρ(B) .
The following Lemma plays a key role because it provides a sufficiently exact description of the distribution of the eigenvalues of I n + βB −1 B, which has the the same structure as G defined by (3.18).
Lemma 6.4 Assume that B andB are defined by (6.111) and (6.113), respectively. Furthermore if λ min (B) < 0, then, for an arbitrary β ∈ 0, 1 ρ(B) , there is at least one eigenvalue λ of I n + βB −1 B which lies in closed left half complex plane excluding origin, i.e., Proof. The proof is lengthy and has been relegated to the Appendix.
Similar to Lemma 6.4, the following lemma plays a key role in this case because it provides a sufficiently exact description of the distribution of the eigenvalues of β I n + βB −1 B, which has the the same structure as H defined by (5.98).
Lemma 6.5 Assume that B andB are defined by (6.111) and (6.115), respectively. Furthermore if λ max (B) > 0, then, for an arbitrary β ∈ 0, 1 ρ(B) , there is at least one nonzero eigenvalue λ of β I n + βB −1 B such that Proof. The proof is lengthy and has been relegated to the Appendix.
Based on the above Lemma, we directly obtain the following Lemma, which shows there is at least one nonzero eigenvalue of I n − β I n + βB T , whose magnitude is strictly greater than one.
Lemma 6.6 Assume that B andB are defined by (6.111) and (6.115), respectively. Furthermore suppose λ max (B) > 0 and I n − β I n + βB −1 B is invertible, then, for an arbitrary β ∈ 0, 1 ρ(B) , there is at least one nonzero eigenvalue of , whose magnitude is strictly greater than one.
Proof. According to assumptions, (6.133) Hence, the statement of the lemma is equivalent to that there is at least one eigenvalue λ of β I n + βB −1 B such that (6.134) The above inequality is clearly equivalent to In addition, under the same assumptions, Lemma 6.5 shows that there exists at least one eigenvalue λ of β I n + βB −1 B satisfying Thus, the proof is finished.

Conclusion
In this paper, given a non-convex twice continuously differentiable cost function with Lipschitz continuous gradient, we prove that all of BCGD, BMD and PBCD converge to a local minimizer, almost surely with random initialization.
As a by-product, it affirmatively answers the open questions whether mirror descent or block coordinate descent does not converge to saddle points in Lee et al. (2016). More importantly, our results also hold true even for the cost functions with non-isolated critical points, which generalizes the results in Panageas and Piliouras (2016) as well.
By using the similar arguments, it is interesting to further research whether other methods, such as ADMM, BCGD, BMD, PBCD and their variations for the problems with some specially structured constraints, admit similar results or not.

Acknowledgements
The authors would like to thank Prof. Zhi-Quan (Tom) Luo from The Chinese University of Hong Kong, Shenzhen, for the helpful discussions on this work.

Proof of Lemma 3.1
Proof. Firstly, we prove that g 1 αf with step size α < 1 L is a diffeomorphism. The proof is given by the following four steps.
(b) To show g 1 αf is surjective, we construct an explicit inverse function. Given a point y in R n , suppose it has the following partition, . . .
Then we define n − n 1 dimensional vector . . .

y(p)
   (9.138) and define a functionf ·; y − (1) : R n 1 → R, , which is determined by function f and the remained block coordinate vector y − (1) of y. Then, the proximal point mapping of −f ·; y − (1) centered at y(1) is given by For α < 1 L , the function above is strongly convex with respect to x(1), so there is a unique minimizer. Let x y (1) be the unique minimizer, then by the KKT condition, where the second equality is due to the definition of functionf ·; y − (1) . Let x y be defined as where x y (1) is defined by (9.139). Accordingly, where the first equality is due to the definition of y − (1) (see (9.138)); the second equality thanks to (9.140); and the third equality holds because of the definition of x y (see (9.141)).
Hence, x y is mapped to y by the mapping g 1 αf .
(c) In addition, combined with ∇ 2 f (x)U 1 U T 1 ∈ R n×n and U T 1 ∇ 2 f (x)U 1 ∈ R n 1 ×n 1 , Theorem 1.3.20 in Horn and Johnson (1986) means which is the n 1 -by-n 1 principal submatrix of ∇ 2 f (x), it follows from Theorem 4.3.15 in Horn and Johnson (1986) that 9.144) where the last relation holds because of Eq. p(2.2) and Lemma 7 in Panageas and Piliouras (2016). Since α < 1 L , Eqs. (9.142), (9.143) and (9.144) imply that (d) Note that we have shown that g 1 αf is bijection, and continuously differentiable. Since Dg 1 αf (x) is invertible for α < 1 L , the inverse function theorem guarantees g 1 αf −1 is continuously differentiable. Thus, g 1 αf is a diffeomorphism. Secondly, it is obvious that similar arguments can be applied to verify that, g s αf , s = 2, . . . , p, are also diffeomorphisms.

Proof of Lemma 3.2
Proof. First, we define recursively when s = t. If k < s, then the above (9.147) follows that Consequently, if 1 ≤ s < q ≤ p, then (9.149) where the fourth equality is due to (9.147) and the last equality uses the definition (9.146) of G[s]. Particularly if q = p, the above equation becomes From equality (9.150), we further have where (a) uses the definitions of G[s] in (9.146); (b) is due to (9.148); (c) thanks to the definition (2.4) of U t ; (d) uses (9.148) again; (e) holds because of (9.149); (f) follows from G[p] = G. Dividing both sides of the above equation by α, we have (3.21).

Proof of Lemma 6.4
Proof. We divide the proof into two cases. Case 1: B is an invertible matrix. In this case, we clearly have, In what follows, we will prove that (6.129) is true by using Lemma 9.2 in Appendix. Fristly, we define an analytic function with t as a parameter: Moreover, define a closed rectangle in the complex plane as (9.153) with ν being defined below: where the first inequality holds because of β ∈ 0, 1 and t ∈ [0, 1]. Note that the boundary ∂D of D consists of a finite number of smooth curves. Specifically, define (9.156) In order to apply Lemma 9.2, we will show that X t (z) = 0, ∀ t ∈ [0, 1], ∀ z ∈ ∂D. (9.157) On the one hand, since the spectral norm of a matrix is lager than or equal to its spectral radius, the above inequality (9.154) yields that, for any t ∈ [0, 1], every eigenvalue of B −1 I + tβB has a magnitude less than ν. Note that for an arbitrary z ∈ γ 2 ∪ γ 3 ∪ γ 4 , then |z| ≥ 2ν. Consequently, On the other hand, it follows from Lemma 6.2 that, for any t ∈ [0, 1], if λ is an eigenvalue of B −1 I n + tβB , then Re (λ) = 0. Hence, λ / ∈ γ 1 . As mentioned at the beginning of the proof, B −1 I n + tβB is invertible. Hence, there are no zero eigenvalues of B −1 I n + tβB in γ 1 , i.e., X t (z) = 0, ∀ t ∈ [0, 1], ∀ z ∈ γ 1 . (9.159) Combining (9.158) and (9.159), we obtain (9.157). As a result, it follows from Lemma 9.2 in Appendix, Eqs. (9.152), (9.153) and (9.157) that X 0 (z) = det {zI n − B −1 } and X 1 (z) = det zI n − B −1 I n + βB have the same number of zeros in D. Note that λ min (B) < 0 implies that there is at least one negative eigenvalue 1 λ min (B) of B −1 . Recalling the definition (9.154) of ν, we know 1 λ min (B) ≤ ν. Thus 1 λ min (B) must lie inside D. In other words, the number of zeros of X 0 (z) inside D is at least one, which in turn shows the number of zeros of X 1 (z) inside D is at least one as well. Thus, there must exist at least one eigenvalue of B −1 I n + βB lying inside D. We denote it as x + yi, then −2ν < x < 0 and −2ν < y < 2ν. Consequently, 1 x+yi = x−yi x 2 +y 2 is an eigenvalue of I n + βB −1 B with real part x x 2 +y 2 < 0. Hence, 1 x+yi lies in Ω defined by (6.130) and the proof is finished in this case.
Case 2: B is a singular matrix. In this case, we will apply perturbation theorem based on the results in Case 1 to prove (6.129).

Proof of Lemma 4.1
Proof. We first prove that g 1 with step size α < µ L is a diffeomorphism. The proof is given by the following four steps. (a) We first prove that ψ 1 is injective from R n 1 → R n 1 for α < µ L . Suppose that there exist x and y such that ψ 1 (x) = ψ 1 (y), which implies that t = 2, 3, . . . , p.
(b) To show ψ 1 is surjective, we construct an explicit inverse function. Given a point y in R n , suppose it has the following partition, . . . For α < µ L , the function above is strongly convex with respect to x(1), so there is a unique minimizer of the problem (9.215). Let x y (1) be the unique minimizer , then by the KKT condition, ∇ϕ 1 (y(1)) = ∇ϕ 1 (x y (1)) − α∇f x y (1); y − (1) , (9.216) which is equivalent to .
(9.217) Let x y be defined as where x y (1) is determined by (9.217). Accordingly, where the first equality is due to the definition of y − (1) (see (9.213)); the second equality thanks to (9.217); and the third equality holds because of definition of U 1 (see (2.4)); since ψ 1 (x y ) is defined by (4.44), the last equality holds true.
Hence, x y is mapped to y by the mapping ψ 1 .
(c) In addition, recalling (4.47), we have where the second equality is due to the definitions of U 1 and A s1 which are given by (2.4) and (3.13), respectively. The above equality means that Moreover, where the first inequality holds because of A 11 = ∇ 2 11 f (x), (2.2) and Lemma 7 in Panageas and Piliouras (2016); the second inequality is due to α < µ L ; the last inequality thanks to (4.35). Hence, ∇ 2 ϕ 1 (x(1)) − αA 11 is an invertible matrix. Consequently, Dψ 1 (x) is an invertible matrix as well.
Secondly, it is obvious that similar arguments can be applied to verify that, ψ s , s = 2, . . . , p, are also diffeomorphisms. Thus, the proof is completed.
Hence, it is sufficient for us to prove that, for an arbitrary β ∈ 0, 1 ρ(B) , there is at least one nonzero eigenvalue σ of (βB) −1 I n + βB such that σ ∈ Ξ(β, B). (9.233) Subsequently, we will prove that relation (9.233) is true by using Lemma 9.2 in Appendix.
We first define an analytic function with t as parameter: (9.234) In order to construct a closed region, we define where the first inequality holds because of β ∈ 0, 1

ρ(B)
and t ∈ [0, 1]. In addition, let t = 0, the above equation also means that where the second equality is due to the definitions of spectral norm and spectral radius; the third inequality thanks to property of spectral radius; the last inequality holds because of β ∈ 0, 1 ρ(B) . Thus given the above ν satisfying (9.235) and (9.236), we can define a closed rectangle as which is a closed region in the complex plane. Note its boundary ∂D consists of a finite number of smooth curves. Specifically, define then ∂D = γ 1 ∪ γ 2 ∪ γ 3 ∪ γ 4 . (9.239) In order to apply Lemma 9.2, we will show that On the one hand, since the spectral norm of a matrix is lager than or equal to its spectral radius, the above inequality (9.235) yields that, for any t ∈ [0, 1], every eigenvalue of B −1 I + tβB has a magnitude less than ν. Note that for an arbitrary z ∈ γ 2 ∪ γ 3 ∪ γ 4 , then |z| ≥ 2ν. Consequently, On the other hand, if σ is an eigenvalue of (βB) −1 I n + tβB with any t ∈ [0, 1], and Re (σ) > 0, then Lemma 6.3 implies that, Combining (9.241) and (9.244), we obtain (9.240). As a result, it follows from Lemma 9.2 in Appendix, (9.234), (9.237) and (9.240) that X 0 (z) = det zI n − (βB) −1 and X 1 (z) = det zI n − (βB) −1 I n + βB have the same number of zeros in D. Note that λ max (B) > 0 implies that there is at least one positive eigenvalue 1 βλmax(B) of (βB) −1 . Note that 1 βλmax(B) ≥ 1 βρ(B) > 1. Recalling the definition (9.235) of ν, we know 1 βλmax(B) ≤ ν. Thus 1 βλmax(B) must lie inside D. In other words, the number of zeros of X 0 (z) inside D is at least one, which in turn shows the number of zeros of X 1 (z) is at least one as well. Thus, there must exist at least one eigenvalue of (βB) −1 I n + βB lying inside D. We denote it as σ, then Re (σ) > 1 2 . Moreover, Lemma 6.3 means that Re (σ) ≥ 1 2 + 1−βρ(B) βρ(B) . Hence, σ lies in Ξ(β, B) defined by (6.132) and the proof is finished in this case.
Case 2: B is a singular matrix. In this case, we will apply perturbation theorem based on the results in Case 1 to prove (6.131).
Suppose the multiplicity of zero eigenvalue of B is m. For clarity of notation, we rewrite the eigen decomposition (9.160) of B below: where the second equality holds because of (9.252); the last equality is due to (6.116).
Lemma 9.1 (Rouche's Theorem: Conway (1973)) Suppose f and g are meromorphic in a neighborhood ofB(a; R) with no zeros or poles on the circle γ = {z : |z − a| = R}. If Z f and Z g (P f and P g ) are the number of zeros (poles) of f and g inside γ counted according to their multiplicities and if |f (z) + g(z)| < |f (z)| + |g(z)| on γ, then Z f − P f = Z g − P g . Moreover, suppose that D is a closed region and ∂D consists of a finite number of smooth curves. If X t (z) = 0, ∀ t ∈ [0, 1], ∀z ∈ ∂D, (9.275) then, for any t 1 , t 2 ∈ [0, 1], X t 1 (z) and X t 2 (z) have the same number of zeros in D counted according to their multiplicities.
The above analysis shows that zero is not one of the eigenvalues of Θ − λ I n−m + βČ 11 nor I m + βČ 22 . Combined with the expression (9.281), the multiplicity of zero eigenvalue of I n + βB −1 B is exactly m.
To show the gradient map ∇φ is surjective, we construct an explicit inverse function (∇φ) −1 given by Since φ is a σ-strongly convex function, the function above is strongly convex with respect to x. Hence, there is a unique minimizer and we denote it as x y . Then by the KKT condition, ∇φ(x y ) = y.
Thus, x y is mapped to y by the mapping ∇φ. Consequently, ∇φ is bijection. The assumptions also mean it is continuously differentiable.