Title: OPTIMIZATION ON MULTIPLE MANIFOLDS

Abstract: Optimization on manifold has been widely used in machine learning, to handle optimization problems with constraint. Most previous works focus on the case with a single manifold. However, in practice it is quite common that the optimization problem involves more than one constraints, (each constraint corresponding to one manifold). It is not clear in general how to optimize on multiple manifolds effectively and provably especially when the intersection of multiple manifolds is not a manifold or cannot be easily calculated. We propose a unified algorithm framework to handle the optimization on multiple manifolds. Specifically, we integrate information from multiple manifolds and move along an ensemble direction by viewing the information from each manifold as a drift and adding them together. We prove the convergence properties of the proposed algorithms. We also apply the algorithms into training neural network with batch normalization layers and achieve preferable empirical results.

1. INTRODUCTION:

Machine learning problem is often formulated as optimization problem. It is common that the optimization problem comes with multiple constraints due to practical scenarios or human prior knowledge that adding some of them help model achieve a better result. One way to handle these constraints is adding regularization terms to the objective, such as the 1 and 2 regularization. However, it is hard to adjust the hyper-parameters of the regularization terms to guarantee that the original constraints get satisfied.

Another way to deal with the constraints is to optimize on manifolds determined by the constraints. Then the optimization problem becomes unconstrained on the manifold, which could be easy to solve technically. Furthermore, optimization on manifold indicates optimizing on a more compact space, and may bring performance gain when training neural networks, e.g., (Meng et al., 2018; Cho & Lee, 2017) .

Most previous works on manifold optimization focus on a single manifold (Zhang & Sra, 2016; Wei et al., 2016) . However, in practice, we often face more than one constraints, each of them corresponding to one manifold. If we still solve the optimization problem with multiple constraints by method on manifold, we need to handle it on the intersection of multiple manifolds, which may no longer be a manifold (Pathak et al., 2015) . Due to this, traditional optimization methods on manifold does not work in this case.

In this paper, we consider the problem of optimization on multiple manifolds. Specifically, the problem is written as arg min

EQUATION

where each M i is a manifold. We propose a method solving this problem by choosing the moving direction as -∇f (x)(on manifold is -gradf (x)) with several drifts which are derived from the descent information on other manifolds. By this method, we get sequence that has information from all manifolds.

1.1. RELATED WORK:

There are several articles discussing the problem of optimization on manifold. Most of them focus on a single manifold. Readers can find a good summary about this topic and the advantages of op-timization on manifold in (Absil et al., 2009) . Recently, popular first order algorithms in Euclidean space are studied in the manifold setting, e.g., the convergence of gradient descent (Zhang & Sra, 2016; Boumal et al., 2017) , sub-gradient method (Hosseini & Uschmajew, 2017) , stochastic variance reduction gradient (SVRG) (Zhang et al., 2016) and the gradient descent with momentum (Liu et al., 2017) .

Riemann approaches (Cho & Lee, 2017; Huang et al., 2017) have also been applied to train deep neural network by noticing that the parameters of the neural network with batch normalization live on Grassmann manifold and Oblique manifold, respectively.

1.2. CONTRIBUTION:

(1) This paper introduces an algorithm to deal with optimization with multiple manifolds. The algorithm adds drifts obtained from other manifolds to the moving direction, in order to incorporate the information from multiple manifolds during the optimization process.

(2) We prove the convergence of this algorithm under a very general framework. The proof is also applicable to the convergence of many other algorithms including gradient descent with momentum and gradient descent with regularization. Moreover, our proof does not depend on the choices of Retr x on the manifold.

2. OPTIMIZATION WITH MULTIPLE MANIFOLDS:



2.1. BASIC DEFINITION AND LEMMA:

The specific definition of manifold M can be found in any topology book. For better understanding, we introduce several properties of manifold here. A manifold is a subspace of R n . For a given point x ∈ M, it has a tangent space T x M which is a linear space but M may not. For gradient descent method, the iterates are generated via

x k+1 = x k -η∇f (x k ),

η is step length. However, the iterate generated by gradient descent may not on manifold anymore because manifold is not a linear space. To fix this, we introduce a retraction function Retr x (η) : T x M → M to determine how point moves on manifold. Specifically, if M is R n , the Retr x becomes x + η. We can consider η in Retr x as the moving direction of the iterating point. Then, the gradient descent on manifold (Boumal et al., 2017; Zhang & Sra, 2016) is given by

EQUATION

where gradf (x) is Riemannian gradient. Riemannian gradient is the orthogonal projection of gradient ∇f (x) to tangent space T x M as ∇f (x) may not in tangent space T x M and the moving direction on manifold is only decided by the vector in T x M. All of notations related to manifold can be referred to (Absil et al., 2009) .

We next use a lemma to describe a property of the minimum point of the problem arg min x∈M f (x), which is a special case of Yang et al., 2014, Corollary 4.2 and Boumal et al., 2017 , Proposition 1.

Lemma 2.1 Let x be a local optimum for the optimization problem arg min x∈M f (x), which means there exists a neighborhood

U x of x satisfy f (x) ≤ f (y) for y ∈ U x . If f (x) is differential in x, then gradf (x) = 0.

We see that gradf (x) plays a role of ∇f (x) on manifold. Similar as Boumal et al. (2017) discussed, we assume function has the property of Lipschtiz gradient. The definition of Lipschtiz gradient is Definition 2.1 (Lipschtiz gradient) For any two points x, y in the manifold M, f (x) satisfy:

f (y) ≤ f (x) + gradf (x), Retr -1 x (y) + L 2 Retr -1 x (y) 2

Then we say that f satisfies the Lipschtiz gradient condition.

We next introduce a condition that guarantees the convergence of iterative algorithms.

Definition 2.2 (Descent condition) For a sequence {x k } and a k > 0, if

f (x k ) -f (x k+1 ) ≥ a k gradf (x k ) 2 ,

then we say the sequence satisfies the descent condition.

2.2. GRADIENT DESCENT ON TWO MANIFOLDS:

First, we introduce a theorem to describe the convergence when the object function f is lower finite, i.e., there exists a f * such that f (x) ≥ f * > -∞ for all x, and the iterates satisfy descent condition. This theorem plays a key role in proof of the rest theorems.

Theorem 2.1 If f is lower finite, and the iteration sequence {x k } satisfies the descent condition for any given {a k }, where each a k > 0. Then lim inf k→∞ a k gradf (x k ) = 0

Proof 1 The proof is available in Supplemental.

For better presentation, we first describe the algorithm under the circumstance of two manifolds.

Considering the objective function f constrained on two manifolds M 1 , M 2 , we aim to find the minimum point on M 1 M 2 . Since M 1 M 2 may not be a manifold, previous methods on manifold optimization cannot apply directly. We propose a method that integrates information from two manifolds over the optimization process.

Specifically, we construct two sequences {x k }, {y k }, each on one manifold respectively. We add a drift which contains information from the other manifold to the original gradient descent on manifold (equation 2). The updating rules are

EQUATION

EQUATION

EQUATION

If b k = 0 in (equation 3) and (equation 4), the updating rules reduce to normal gradient descent on manifold equation 2. The drift h k is in the tangent space T x M of each manifold, which represents information from the other manifold. We call this algorithm gradient descent on manifold with drifting, whose procedure is described in Algorithm 1.

Algorithm 1 Gradient descent with drift on manifold

Input δ > 0, x 0 ∈ M 1 , y 0 ∈ M 2 , Retr x , ε > 0 k → 0 while gradf (x k ) > ε or gradf (y k ) > ε do δ ≤ a (1) k ≤ 2 δ ≤ a (2) k ≤ 2 Calculating gradf (x k ) = P (1) x k ∇f (x k ), gradf (y k ) = P (2) y k ∇f (y k ). P (1)

x k and P

(2)

y k are respectively projection matrix of tangent space T x k , T y k . Obtain h (1) k ∈ T x k M 1 and h (2) k ∈ T y k M 2 . b (1) k = 2(1-a (1) k ) gradf (x k ),h (1) k h (1) k 2 b (2) k = 2(1-a (2) k ) gradf (y k ),h (2) k h (2) k 2 x k+1 = Retr x k [-1 L (a (1) k gradf (x k ) + b (1) k h (1) k )] update step y k+1 = Retr y k [-1 L (a (2) k gradf (y k ) + b (2) k h (2) k )] update step k ← k + 1 end while return x k , y k

We next present the convergence theorem of this algorithm, which illustrates how we set a k and b k in the algorithm.

Theorem 2.2 For function f (x) is lower finite, and Lipschtiz gradient. If we construct the sequence {x k } like equation (3), and for any 0

EQUATION

)

then x k convergence to a local minimizer.

Proof 2 The proof is based on construction of the descent condition (equation 12) and is available in Supplemental.

From the construction of b k , we can see that the smaller the correlation between gradf (x k ) and h k is, the smaller effect the information from M 2 brings. In fact, we set h

(1) k := gradf (x k ) P (1)

x k gradf (y k )

P (1)

x k gradf (y k )

, where P

(1)

x k is the projection matrix to tangent space

T x k M 1 . Sim- ilarly we set h (2)

k which exchanges x k and P

(1)

x k with y k and P

(2) y k (projection matrix of tangent space T y k M 2 ). The drift intuitively gives x k a force moving towards the minimizer on the other manifold. If the two manifolds are R n , then x k and y k are symmetry with each other. We have

EQUATION

EQUATION

If the equation system is stable and x 0 , y 0 are mutually close, the distance between x k and y k will be small when k → ∞. By Schwarz inequality, we see b

k ≤ 2(1 -a k ). Since h k = gradf (x k )

, the scale of the drift is the same as the original Riemannian gradient. Hence, information from another manifold will not affect much, when the points x k and y k are close to a minimizer. We can control the contribution of the information from the other manifold by adjusting a k . For instance, a k = 1 indicates we do not integrate information from the other manifold.

We can also prove the convergence rate of this algorithm.

Theorem 2.3 If f is lower finite satisfy f (x) ≥ f * > -∞, we choose a k as max{ 1 k+1 , δ}, 0 < δ < 2. Then, for any ε > 0, making sure gradf (x k ) < ε needs at most exp f (x0)-f * ε 2 + π 2 12 - 1 ∧ 2(f (x0)-f * ) ε 2 (2δ-δ 2 ) iterations.

Proof 3 The proof is delegated to Supplemental.

Theorem 2.3 states the number of iterations we need to achieve a specific accuracy. Here we can adjust a k as long as δ < a k < 2.

2.3. GRADIENT DESCENT ON n MANIFOLDS:

In this subsection, we describe our algorithm for the case with multiple (more than 2) manifolds. Suppose we have n manifolds, M 1 , • • • , M n , and sequence on manifold M i is denoted as {x

(i) k }.

In the following, we use sequence {x

(1) k } on M 1 as an example, and other sequences on other manifolds can be derived accordingly. Let g

(i) k ∈ T x M 1 denote the drift from manifold M i (g (1) k is gradf (x (1) k ).

Then let the updating rule be

EQUATION

)

Since f satisfies Lipschtiz gradient condition(2.1), we have

f (x (1) k ) -f (x (1) k+1 ) ≥ 1 L g (1) k , n i=1 a (i) k g (i) k - 1 2L n i=1 a (i) k g (i) k 2 = 1 L {(a (1) k - a (1)2 k 2 ) g (1)

k , g

(1) k + n i=2 [a (i) k g (1)

k , g

(i) k - 1 2 a (1) k a (i) k g (1)

k , g

EQUATION

k ]}.

We choose a

(1)

k such that 0 < δ < a (1) k < 2. For j = 2 • • • n, we choose a (j) k such that n j=2 a (j) k g (i) k , g (j) k = 2(1 -a (1) k ) g (1)

k , g

(i) k for i = 2 • • • n (8) then a (i) k g (1)

k , g

(i) k - 1 2 n j=1 a (i) k a (j) k g (i) k , g (j) k - 1 2 a (1) k a (i) k g (1)

k , g

(i) k = 0 for i = 2 • • • n.

The way of choosing a

(j)

k is to obtain the descent condition. Specifically, when n = 2, the solution of (equation 8) becomes b k in (equation 5). If a (j) k solve the linear equation system (8), we get the descent condition (equation 12). From theorem 2.1, we prove the convergence of the updating rule (equation 7) for the case with n manifolds. Writing (equation 8) in the matrix form, we have

EQUATION

k ) ij , i, j from 2 to n, and α k = (a

(2) k , • • • , a (n) k ) T , β k = (2(1 - a (1) k ) g (1) k , g (2) k , • • • , 2(1 -a (1) k ) g (1) k , g (n) k ) T . If G k

is invertible, the linear equation system has an unique solution.

3 APPLY OUR ALGORITHM TO TRAIN NEURAL NETWORK 3.1 NEURAL NETWORK WITH BATCH NORMALIZATION Batch normalization has been widely used since its proposition (Ioffe & Szegedy, 2015) . It transforms the input value to a neuron from z = w T x to

BN (w) = z -E(z) V ar(z) = w T (x -E(x)) w T V x w .

We can calculate the derivative as follows

∂BN (w) ∂w = x -E(x) w T V x w - w T (x -E(x))V x w (w T V x w) 3 2

.

For any a = 0, a ∈ R, we see that BN (w) = BN (aw) and ∂BN (aw

) ∂aw = 1 a ∂BN (w) ∂w

. These equations mean that after a batch normalization, the scale of parameter has no relationship with the output value, but scale of gradient is opposite with the scale of parameter. Cho & Lee (2017) have discussed that batch normalization could have an adverse effect in terms of optimization since there can be an infinite number of networks, with the same forward path but different scaling, which may converge to different local optima owing to different gradients.

To avoid this phenomenon, we can eliminate the effect of scale by considering the weight w on the Grassmann manifold or Oblique manifold. On these two manifolds, we can ignore the scale of parameter. Cho & Lee (2017) ; Huang et al. (2017) respectively discuss that BN (w) has same image space on G(1, n) and St(n, 1) as well as R n , where G(1, n) is a Grassmann manifold and St(n, 1) is an Oblique manifold. Due to these, we can consider applying optimization on manifold to batch normalization problem. However, the property of these two manifold implies that we can actually optimize on the intersection of two manifolds. Since optimization on a manifold rely on Riemannian gradient gradf (x) and Retr x , for a specific Retr x (9) of Grassmann manifold G(1, n), we get a unit point x when η = -gradf (x) = 0 in formula (9). The condition gradf (x) = 0 means we obtain a unit critical point on Grassmann manifold which is also on Oblique manifold.

The specific discussion of Grassmann manifold and Oblique manifold can be found in (Absil et al., 2009) . G(1, n) is a quotient manifold defined on a vector space, it regards vector with same direction as same element. For example (1, 1, 1) and (10, 10, 10) correspond to same element. We represent elements on G(1, n) with same direction by choosing one of them as representation element. Oblique manifold is given by St(n, p) = {X ∈ R n×p : ddiag(X T X) = I p }, where ddiag(•) is diagonal matrix of a matrix.

We have discussed above that iteration point on G(1, n) would be a unit point when it's a local minimizer. Due to this, the local minimizer we find is actually live on the intersection of St(n, 1) and G(1, n). Hence, training neural network with batch normalized weights can be converted to the problem arg min

x∈G(1,n) St(n,1) f (x).

Let Riemannian gradient be projection of ∇f (x) to tangent space of x. On G(1, n), we have

EQUATION

On St(n, 1), we have

P (2) x (η) = η -xddiag(x T η) gradf (x) = P (2) x (∇f (x)) = ∇f (x) -xddiag(x T ∇f (x))

Retr (2) x (η) =

x + η x + η the P x is the projection matrix onto the tangent space at x. These results can be derived from the general formulas from (Absil & Gallivan, 2006) and (Edelman et al., 1999) .

In backward process of training neural network, weight parameter of each layer is a matrix. Hence, we get gradient to a matrix in every layer. To make calculation easier, we treat the gradient matrix and parameters matrix as vector. For example a m × n gradient matrix can be viewed as a m × n dimensional vector. Then we apply Algorithm 1 to update parameters, which means we optimize on a product manifold

G(1, k 1 ) × • • • G(1, k n ), St(k 1 , 1) × • • • St(k n , 1)

k i is number of parameters for the i-th hidden layer, and n is number of hidden layers. We need to operate algorithm for parameter vector on each hidden layer. In other words, we update parameters layer by layer.

3.2. EXPERIMENT:

In this section, we use data set CIFAR-10 and CIFAR-100 (Krizhevsky & Hinton, 2009) to test our algorithm. These two data sets are color images respectively have 10 and 100 classes, each of them has 50,000 training images and 10,000 test images. The deep neural network we used is Wide-ResNet (Zagoruyko & Komodakis, 2016) , it output a vector which describe the probability of a data divided into each class.

In every hidden layer of neural network, we apply batch normalization to weight parameters and treat them as a vector. We have already discussed that minimizers of a neural network with batch normalized weights live on the intersection of Grassmann manifolds and Oblique manifold. Hence, we can train neural network with batch normalized weights by our algorithm(1). The biases of every hidden layer is unrelated to batch normalization and are updated by SGD. For every training step, we calculate mean loss 1 S xi∈S l(f (x i , θ), y i ) of a mini batch to substitute the real loss function E x [l(f (x, θ), y)], where S is batch size.

The process of algorithm on two manifolds follows Algorithm 1, where the two manifolds are G(1, n) and St(n, 1), respectively. In Algorithm 1, we choose

h (1) k = gradf (x k ) P (1)

x k gradf (y k )) P

(1)

x k gradf (y k ) , h (2) k = gradf (y k ) P (2) y k gradf (x k )) P (2) y k gradf (x k ) and a (1) k = a (2) k = max{ 1 k+1 , δ}.

In the updating rules of x k and y k , we add a norm-clip to vectors (a

(1) k gradf (x k ) + b (1) k h (1) k ) and (a (2) k gradf (y k ) + b (2) k h (2)

k ). Then we times η to the two vectors, where η is the learning rate.

In the experiments, we compare three methods: 1) stochastic gradient descent on manifold with drifting (Drift-SGDM), 2) stochastic gradient descent on manifold Boumal et al. (2017) (SGDM), and 3) stochastic gradient descent (SGD). In Algorithm 1, we can get two sequences each corresponding to a model on a manifold. We predict output class by adding two output vectors of two models and choosing the biggest as prediction class.

For Drift-SGDM (Algorithm 1), we set δ = 0.9 and initial learning rate η m = 0.4 for weights parameters which is multiplied by 0.4 at 60, 120, and 160 epochs. Initial learning rate η for biases is 0.01 which is multiplied by 0. About Drift-SGDM and SGDM, the loss is achieved from the average of two model. The parameter scale of the two model can be different, because they respectively live on Grassmann manifold and Oblique manifold. Due to this, the comparing between Drift-SGDM and SGDM is more reasonable. We also give the accuracy curve and a tubular of accuracy rate on test sets to validate our algorithms. We see that our algorithm perform better on larger neural network. Our algorithm does not have regularization term, and it does not perform well in the aspect of generalization. We can actually add a regularization term like in (Cho & Lee, 2017) to achieve better generalization.

Dataset:

We choose δ in Algorithm 1 as 0.9. Since b

(i) k ≤ 2(1 -a (i)

k ) where i = 1, 2 as we have discussed in section 2, we see drift term b

(i) k h (i)

k in Algorithm 1 doesn't affect much to iteration point. We can actually set a smaller δ to enhance the influence of drift term b

(i) k h (i) k .

4. CONCLUSION:

In this paper, we derive an intuitively method to approach optimization problem with multiple constraints which corresponds to optimizing on the intersection of multiple manifolds. Specifically, the method is integrating information among all manifolds to determine minimum points on each manifold. We don't add extra conditions to constraints of optimization problem, as long as each constraint can be converted to a manifold. In the future, we may add some conditions to manifolds which derive a conclusion that minimum points on each manifold achieved by our algorithm are close with other. If this conclusion is established, the problem of optimization on intersection of multiple manifolds is solved.

According to the updating rule (equation 3), we can derive many other algorithms, because the drift h k in (equation 3) is flexible. On the other hand, Retr x on our algorithm does not limit to a specific one. Since there are some results for Retr x = Exp x , for example Corollary 8 in (Zhang & Sra, 2016) , we may get more elegant results by using Exp x as retraction function in our algorithm.

The manifolds we encounter in optimization are mainly embedded sub-manifold and quotient manifold (Absil et al., 2009) . Embedded sub-manifold is F -1 (y) for a smooth function F : M 1 → M 2 , where M 1 , M 2 are two manifolds and y ∈ M 2 . Quotient manifold is a quotient topology space generalized by a specific equivalence relationship ∼. In this paper, we use Oblique manifold and Grassmann manifold which are embedded sub-manifold and quotient manifold respectively.

The difficulty we faced in optimization on manifold is calculating tangent space T x M and Riemannian gradient gradf (x). Giving a exact formula of a tangent space T x M is not a easy problem. On the other hand, since Riemannian gradient is ∇f (x) projected to a tangent space T x M, finding projection matrix to a specific space T x M is nontrivial.

A DISCUSSION ABOUT THE FRAMEWORK OF GRADIENT DESCENT WITH DRIFT A.1 CONNECTION WITH CLASSICAL ALGORITHMS:

In this section, we study the frame work of gradient descent with drift. In a special case, we regard R n as a manifold. Then, Rienmann gradient gradf (x) = ∇f (x), tangent space T x M = R n and Retr x (η) = x + η. In Algorithm (1), we set

h k+1 = - 1 L (a k ∇f (x k ) + b k h k ),

where

δ < a k < 2, b k = 2(1 -a k ) ∇f (x k ), h k h k 2 .

Then we have

x k+1 = x k - 1 L (a k ∇f (x k ) + b k h k ) = x k - 1 L (a k ∇f (x k ) - b k L (a k-1 ∇f (x k-1 ) + b k-1 h k-1 )),

which is exactly a kind of gradient descent with momentum. And this algorithm is convergence as we proved. On the other hand, if choosing h k as gradient of a regularization term R(x) on x k . For example, h k becomes 2x k when R(x) = x 2 . The iteration point in Algorithm ( 1) is achieved by gradient descent with regularization term.

A.2 A STOCHASTIC DRIFT:

The drift in (equation 3) we have discussed is non-stochastic. But actually, we can change the drift as a stochastic term to construct a non-descent algorithm. Meanwhile, stochastic drift gives iteration sequence ability of jumping from local minimizer. The update rule is

EQUATION

where ξ k is a random vector with mean vector µ, covariance matrix Σ. The process of this algorithm is Algorithm 2.

Algorithm 2 Non-descent method with stochastic noise Input 0 < δ < 2, x 0 ∈ M, Retr x , ε > 0 k → 1 while gradf (x) > ε do Sample ξ k with mean vector µ and covariance matrix Σ

b k = 1 k 2 a k = 1 - 1 k gradf (x k ) gradf (x k ) ≥ 1 k δ gradf (x k ) < 1 k x k+1 = Retr x k [-1 L (a k gradf (x k ) + b k P x k ξ k )] update step P x k is projection matrix to tangent space T x M k ← k + 1 end while return x k

We give convergence theorem of Algorithm 2. The proof implies that this algorithm is non-descent, it also shows how we set a k and b k .

Theorem A.1 For function f (x) ≥ f * > -∞, and Lipschtiz gradient. If we construct the sequence

EQUATION

)

where 0 < δ < 2, we have lim inf k→∞ gradf (x k ) 2 = 0.

In this theorem, b k control the speed of back fire. The noise ξ k in (equation 10) has small effect to iteration process when k is large, because sequence is about to be stable after enough iterations. But in beginning of iteration procedure, noise ξ k effects much which give iteration sequence ability of jumping from local minimizer.

B PROOF OF THEOREMS:

In this section, we give proof of theorems in this paper. The proof of Theorem 2.1 is Proof 4 (proof of Theorem 2.1) According to definition 2.2 of descent condition, we have

f (x 0 ) -f (x k ) ≥ k-1 i=0 a i gradf (x i ) 2 ,

for any k. Since f is lower finite, we have

∞ i=0 a i gradf (x i ) 2 ≤ f (x 0 ) -f * < ∞, where f (x) ≥ f * > -∞, it means lim inf k→∞ a k gradf (x k ) = 0.

The proof of Theorem 2.2 is Proof 5 (proof of Theorem 2.2) Since f satisfy Lischtiz gradient(2.1), we have

f (x k ) -f (x k+1 ) ≥ 1 L (a k - a 2 k 2 ) gradf (x k ) 2 + 1 L b k (1 -a k ) gradf (x k ), h k - b 2 k 2L h k 2 .

By the definition of b k , we got

EQUATION

) Since a k - a 2 k 2 > 0, by Theorem 2.1, we have lim inf k→∞ (a k - a 2 k 2 ) gradf (x k ) 2 = 0.

The definition of a k implies that gradf (x) 2 → 0.

The proof of Theorem 2.3 gives convergence rate of gradient descent on manifold with drift.

Proof 6 (proof of Theorem 2.3) For any ε > 0, assuming gradf (

x i ) ≥ ε, i ∈ N until i = k. Then f (x 0 ) -f (x k ) ≥ k-1 i=0 [( 1 i + 1 - 1 2(i + 1) 2 ) ∨ (δ - δ 2 2 )] gradf (x i ) 2 ≥ [(log (k + 1) - ∞ i=0 1 2(i + 1) 2 ) ∨ k(δ - δ 2 2 ) gradf (x i ) 2 ,

here we use the relationship log

(1 + x) ≤ x when x ≥ 0. Since ∞ i=0 1 2(i+1) 2 = π 2 12 < ∞(Zorich, 2002), for i ≤ k -1, we have log (k + 1) ≤ f (x 0 ) -f * gradf (x i ) 2 + π 2 12 and k ≤ f (x 0 ) -f * (δ -δ 2 2 ) gradf (x i ) 2 . Since gradf (x i ) ≥ ε when i ≤ k -1, k ≤ exp f (x0)-f * ε 2 + π 2 12 -1 ∧ 2(f (x0)-f * ) ε 2 (2δ-δ 2 ) .

Before proof Theorem A.1, we need two lemmas. Here we use Rayleigh theorem of theorem 2.4. (Wang et al., 2003) Proof 8 (proof of Theorem A.1) Since P x k is a projection matrix, which is a symmetric idempotent matrix. Because f satisfies Lipschtiz gradient(2.1), we have

f (x 1 ) -f (x k ) ≥ 1 L k-1 i=1 (a i - a 2 i 2 ) gradf (x i ) 2 + b i (1 -a i )ε i - b 2 i 2 η i ,

where ε i = (P xi gradf (x i )) T ξ i = gradf (x i )) T ξ i , η i = ξ T i P T xi P xi ξ i = ξ T i P xi ξ i . Due to the two random variables, algorithm (2) is not necessary descent. Σ is a symmetric positive definite matrix. By Schwarz equality and definition of a i , we have

E k-1 i=1 [b i (1 -a i )ε i ] ≤ E k-1 i=1 b i (1 -a i ) gradf (x i ) ξ i ≤ k-1 i=1 b i E(1 -a i ) 2 gradf (x i ) 2 1 2 E ξ i 2 1 2 = k-1 i=1 b i E(1 -a i ) 2 gradf (x i ) 2 1 2 [ µ 2 + tr(Σ)] 1 2 ≤ [ µ 2 + ≤ tr(Σ)] 1 2 k-1 i=1 b i i .

By Fatou's lemma, we have (a i -

E lim inf k→∞ [ k-1 i=1 b i (1 -a i )ε i ] ≤ lim inf k→∞ E[ k-1 i=1 b i (1 -a i )ε i ] ≤ lim k→∞ [ µ 2 + ≤ tr(Σ)] 1 2 k-1 i=1 b i i = [ µ 2 + ≤ tr(Σ)] 1 2 ∞ i=1 b i i < ∞,

a 2 i 2 ) gradf (i k ) 2 ≤ L(f (x 1 ) -f * ) -lim inf k→∞ k-1 i=1 b i (1 -a i )ε i + ∞ i=1 b 2 i 2 η i < ∞ a.s.

then we have

EQUATION

)

by the definition of a k (equation 11), equation ( 13) is equivalent to lim inf k→∞ gradf (x k ) 2 = 0 almost surely.

:



Figures and Tables:

4 at 60, 120, and 160 epochs. Norm clip is 0.1. Training batch size is 128. The number of training epochs is 200.For SGDM, we choose a = 1 in Algorithm 1. The other settings are the same as Drift-SGDM. That a = 1 in Algorithm 1 means that SGDM optimizes on each manifold individually We set SGD as baseline. The learning rate is 0.2 which is multiplied by 0.2 at epoch 60,120 and 160. Weight decay is set as 0.0005, but we do not apply weight decay for algorithms on manifold. All other settings are the same as the above two algorithms.

Figure 1: Some results based on Wide-ResNet. WRN-d-k denotes a wide residual network that has d convolutional layers and a widening factor k

A random vector with Ex = µ and Covx = Σ. Then for any symmetric matrix A, we have E(x T Ax) = µ T Aµ + tr(AΣ). This lemma can be derived from Wang et al. (2003)'s theorem 3.2.1 of Page 57. The other lemma is Lemma B.2 If A and Σ are n × n symmetric matrix, then tr(AΣ) ≤ tr(A)λ max , where λ max is the largest engine value of Σ Proof 7 (proof of Lemma B.2) According to spectral decomposition of symmetric matrix A, A can be written as n i=1λ i γ i γ T i , where λ i is engine value of A and γ i is engine vector corresponding to λ i . They satisfyγ T i γ j = δ ij , δ ij is Kronecker delta. Hence tr(AΣ) = n i=1 tr(λ i γ i γ T i Σ) = n i=1 tr(λ i γ T i Σγ i ) ≤ λ max n i=1tr(λ i ) = λ max tr(A).

1 -a i )ε i < ∞ a.s.Since tr(P xi ) = rank(P xi ) and the largest engine value of P x k is 1, we haveE(η i ) = E(ξ T i P xi ξ i ) = µ T P xi µ + tr(P xi Σ) ≤ µ 2 + λ max d, where d is the dimension of x and λ max is the largest engine value of Σ. By Levy's theorem, we have

Accuracy rate on test sets of data.

Table content: <table><tr><td/><td/><td>CIFAR-10</td><td/><td/><td>CIFAR-100</td><td/></tr><tr><td>Model</td><td colspan="6">SGD Drift-SGDM SGDM SGD Drift-SGDM SGDM</td></tr><tr><td>WRN-52-1</td><td>93.3</td><td>92.88</td><td>93.11</td><td>71.07</td><td>69.61</td><td>69.58</td></tr><tr><td colspan="2">WRN-16-4 94.46</td><td>94.16</td><td>94.16</td><td>74.74</td><td>76.4</td><td>76.04</td></tr><tr><td colspan="2">WRN-28-10 95.59</td><td>95.07</td><td>94.79</td><td>78.88</td><td>78.92</td><td>79.37</td></tr></table>

Peer review (iclr2019):
 The paper proposes a novel algorithm for optimization on multiple manifolds. The moving direction fuses gradient information from each manifolds via correlation. More importantly, the convergence is guaranteed. However, the empirical results seems not very good compared to SGD. My concerns: 1) How you ensure each step is descent? 2) How is the performance of the proposed algorithm compared to the ADMM which is well-suited for this problem. The presentation needs to be improved.