Accelerated Multiplicative Weights Update Avoids Saddle Points Almost Always

1 Introduction

In this paper we consider non-convex optimization problem with constraint that is a product of simplices, i.e.,

where f : ∆1×...×∆n → R is a sufficiently smooth function and

Especially, we are interested in the Multiplicative Weights Update (MWU) algorithm [Arora et al., 2012], which is commonly used in various fields including game theory, optimization, machine learning and multi-agent systems. We propose an Accelerated Multiplicative Weights Update (A-MWU), and study its saddle point avoidance behavior from a general perspective of Riemannian Accelerated Gradient Descent [Zhang and Sra, 2018].

Escaping saddle points in non-convex optimization has been studied extensively by the Machine Learning community [Ge et al., 2015; Jin et al., 2017; Jin et al., 2018; Lee et al., 2016; Lee et al., 2019; Panageas and Piliouras, 2016; Criscitiello and Boumal, 2019; Sun et al., 2019b; Panageas et al., 2019a; Sun et al., 2019a]. The first-order optimization algorithms can be studied from a dynamical system perspective and results in[Lee et al., 2016; Lee et al., 2019] guarantee that the algorithms asymptotically avoid saddle points in probability 1 with random initialization. The main technique of using Center-Stable Manifold theorem was extended to heavy-ball algorithm on Euclidean space by [Sun et al., 2019a].

∗Contact Author

Despite the aforementioned progresses, the saddle avoidance of accelerated algorithms in non-Euclidean setting is less studied, especially for the case where the step-size is varying with time. The only result on variable step-size is given by [Panageas et al., 2019a], but the Riemannian Accelerated Gradient Gescent is omitted. It is known that MWU on the simplex is a special case of mirror descent with entropy regularizer, and the mirror descent algorithm has many applications in optimization [Dekel et al., 2011; Juditsky et al., 2011]. Using this connection, an accelerated version of mirror descent is provided by [Krichene et al., 2015], in which the authors discretize a system of ODEs of continuous-time mirror descent to get acceleration. However, [Krichene et al., 2015] focuses on convex optimization only and leaves the saddle avoidance in non-convex optimization. [Panageas et al., 2019b] proved that MWU almost always converges to second-order stationary points with constant step-size, but the result for accelerated MWU with variable step-size is missing in the literatures.

Motivated by the question that if there exists an accelerated version of MWU which also provably avoids saddle point, we investigate the Riemannian Accelerated Gradient Descent (RAGD) proposed by Zhang and Sra in [Zhang and Sra, 2018]. The main results and contributions of this paper are the following:

• We propose an Accelerated Multiplicative Weights Update which is derived and simplified from RAGD of [Zhang and Sra, 2018];
• We prove that the RAGD of [Zhang and Sra, 2018] avoids saddle points and moreover, this provides the first saddle avoidance result of Accelerated Multiplicative Weights Update.

Our contributions compared to the most relevant results in literature are illustrated in Table 1.

Riemannian Gradient and Hessian. For differentiable function f : M → R, gradf(x) ∈ TxM denotes the Riemannian gradient of f that satisfies d dt f(γ(t)) = 〈γ ′ (t), gradf(x)〉 for any differentiable curve γ(t) passing through x. The local coordinate expression of gradient is useful in our analysis.

2 Preliminaries

Riemannianmetric and geodesic. A d-dimension Riemannian manifold (M, g) is real, smooth d-dimension manifold M equipped with a Riemannian metric g. For each x ∈ M, let TxM denote the tangent space at x. The metric g induces a inner product 〈·, ·〉x : TxM × TxM → R. We call a curve γ(t) : [0, 1] →M a geodesic if it satisfies

• The curve γ(t) is parametrized with constant speed, i.e. ∥∥ d dt γ(t)∥∥γ(t) is constant for t ∈ [0, 1].
• The curve is locally length minimized between γ(0) and γ(1).

Exponential and logarithmic map. The exponential map Expx(v) maps v ∈ TxM to y ∈ M such that there exists a geodesic γ with γ(0) = x, γ(1) = y and γ ′ (0) = v. For x ∈ M, let Logx denote the logarithmic map at x,

with domain such that this is uniquely defined.

Remark 1. The existence and uniqueness of geodesic is guaranteed by the Fundametal Theorem of ODE, one cannot expect an explicit expression of the geodesic, usually we need to apply a numerical scheme to approximate the solution of the geodesic equation. However, there are cases for which the geodesic equation can be expressed with a closed form, we give the following examples.

Geodesically convex. A set U ⊂M is geodesically convex if for any x, y ∈ U, there is a geodesic γ with γ(0) = x, γ(1) = y and γ(t) ∈ U for t ∈ [0, 1].

Let U be a geodesically convex subset of M. A function f : M → R is called geodesically convex on U if for any x, y ∈ M and any geodesic γ such that γ(0) = x, γ(1) = y and γ(t) ∈ U for all t ∈ [0, 1], it holds that

A function f : M → R is called geodesically µ-convex on U if for any x, y ∈ U and gradient gradf(x) at x, it holds that

where we assume the logarithmic map is well defined in U.

where gij (x) is the ij-th entry of the inverse of the metric matrix {gij(x)} at each point.

The Hessian of f is the covariant derivative of the gradient vector field: Hessf(x)[u] = ∇ugradf(x) for any vector field u on M.

Strict saddle point. A strict saddle point x∗ of f : M →R satisfies

Retraction. A retraction on a manifoldM is a smooth mapping Retr from the tangent bundle TM to M satisfying properties 1 and 2 below: Let Retrx : TxM → M denote the restriction of Retr to TxM.

1. Retrx(0) = x, where 0 is the zero vector in TxM.
2. The differential of Retrx at 0 is the identity map.

Then the Riemannian gradient descent with stepsize α is given as

MultiplicativeWeights Update. The paper focuses on Accelerated Multiplicative Weights Update, for completeness, we recall the linear variant of MWU. Suppose that xi = (xi1, ..., xidi ) is in the i-th component of ∆1 × ... ×∆n. Assume that x(t) is the t-th iterate of MWU, the algorithm is written as follows:

where j ∈ {1, ..., di}.

Algorithm 1 Single-Agent A-MWU

3 Algorithm

We give the Single-Agent version of the Accelerated Multiplicative Weights Update (A-MWU) in Algorithm 1, which is derived from the Riemannian Accelerated Gradient Descent based on the geometry of the positive orthant Rd+. We leave the full multi-agent A-MWU algorithm to Appendix.

Even the derivation of Algorithm 1 is based on the Riemannian Accelerated Gradient Descent, the above implementation is simplified compared to the original algorithm in [Zhang and Sra, 2018]. Since it is impossible to have an explicit form of exponential and logarithmic map in general, all the updates of the algorithm are computed based on the property of Riemannian geometry of the positive orthant Rd+ = {x : xi > 0 for all i ∈ [d]}, [Shahshahani, 1979; Hofbauer and Sigmund, 1998]. We recall the background that is necessary for the interpretation that MWU is indeed a manifold gradient descent. Formally, the positive orthant Rd+ is endowed with a Riemannian metric (called the Shahshahani metric) whose metric matrix {gij (x)} is diagonal with gii(x) = |x| xi where |x| = ∑j xj, The positive orthant Rd+ with the Shahshahani metric is call a Shahshahani manifold. The tangent spaces TxRd+ for all x ∈ Rd+ are all identified with Rd . Now consider a differentiable function f : Rd+ → R, one can define the gradient of f at each point with respect to the Shahshahani metric. The following local-coordinate expression of the Shahshahani gradient for each x ∈ Rd+ is straightforward from (3):

We know from [Hofbauer and Sigmund, 1998] that the exponential map on the positive simplex ∆+ ⊂ Rn+ is

where v = (v1, ..., vn) is a tangent vector of ∆+ at point x. Moreover, the Multiplicative Weights Update given by (5) can be understood as a retraction on ∆+ and the logarithmic map can also be computed explicitly. These makes the formulation of Algorithm 1 possible, and we leave the details in Appendix.

4 Saddle Avoidance Analysis

We show that the Accelerated Gradient Descent on the product manifold M1 × ... ×Mn actually avoids saddle points almost always. The algorithm is extended from the Accelerated Riemannian Gradient Descent of [Zhang and Sra, 2018] with the structure of product manifold.

Suppose that each manifold component Mi is equipped with a Riemannian metric gi, then the product manifold M1 × ... × Mn has the product metric g = g1 ⊗ ... ⊗ gn whose metric matrix is blocked matrix with gi's the non-trivial blocks. Then the gradient is also the Cartesian product of the gradients of each component manifold Mi, i.e.

Recall the Accelerated Riemannian Gradient Descent in [Zhang and Sra, 2018] as follows,

where the 0 < c ≤ αt < 1L , βt > 0, and st, γt, ¯ γt are computed according to st ∈ (0, 1), such that s2t = αt((1 - st)γt + stµ), and

In order to write the distributed Accelerated Riemannian Gradient Descent, we simply compute the exponential and logarithmic map component-wise. We denote

and the t'th update

are computed according to (6) in a distributed manner.

Note that the update rule of RAGD can be written as the composition of three maps, i.e., denote

Therefore, the update rule, which can be viewed as a map ψ(x, v) : M×M →M×M, can be written in the following way:

If x∗ = v∗ where x∗ is a critical point, then the intermediate variable y(x∗ , v∗ ) = x∗ , and ψ(x∗ , v∗ ) = (x∗ , v∗ ). This means that if x∗ is a critical point of f : M → R, the point (x∗ , x∗ ) is a stationary point of the dynamical system defined by iterations of ψ on M ×M.

The main technical step is the proof of "Stable-manifold theorem" for the dynamical system defined by iteration of the augmented map (12), which is a non-autonomous discretetime dynamical system. We state the new stable manifold theorem as follows:

Theorem 2. For a fixed dimension d ≥ 2, there exists s ∈ [d], and positive constant K1,K2 < 1, such that for all t ∈ N, the following holds

Suppose η(t, x) satisfies that η(t, 0) = 0 and for each ϵ > 0, there exists a neighborhod of 0 such that

Then the dynamical system,

where L = diag{Lj(t)}, has a local stable manifold in a small neighborhood of 0.

Note that the Center-Stable Manifold Theorem only secures the existence of local stable manifold, which implies that there exists a small neighborhood of an unstable fixed point x∗ such that the all initial conditions taken from this neighborhood and converges to x∗ must belong to a lower dimensional curved space, thus has measure zero. The local result can be extended to global through an argument in Appendix, for the case when the dynamical system is non-autonomous. In particular, if the update rule ψ of the algorithm is not time-dependent such as the cases of constant step, the above result holds trivially by letting ψ(t, x) ≡ ψ(x). We give the following general version on manifold also for further referrings.

Proposition 3. Let ψ(t, x) : N×M → M be a dynamical system on a finite dimensional manifold M. Suppose that ψ(t, ·) is a local diffeomorphism on M for each t ∈ N. Let A∗ be the set of unstable fixed points. Then the global stable set W s (A∗ ) of A∗ has measure of zero with respect to the volume measure induced by the Riemannian metric on M.

Here the stable and unstable set of a point x are defined to be

• Stable set of x:

• Unstable set of x:

To prove following theorem 4, we leverage the property of the dynamical system induced by the map ψ constructed in (12). Its orbit is the same as the orbit of RAGD and it also satisfies all other conditions in the center-stable manifold theorem. As mentioned above, the theorem tells us in a local neighborhood of a strict saddle point x∗ , all points in this neighborhood that will converge to x∗ under ψ lie in a submanifold, and it's dimension equals to the number of the eigenvalues of the Jacobian of ψ at x∗ that are less than 1. Then we verify DF(x∗ , x∗ ) has a eigenvalue greater or equal to 1. So all initial points in the local neighborhood that will converge to x∗ lies on a low dimension space, thus has measure 0. Now we assume critical points are uncountable. Since points converge to a strict saddle point under RAGD will finally fall into a local neighborhood of this strict saddle point, the set consisted by points in the whole space that will converge to a strict saddle point is a countable union of measure 0 sets, which is also measure 0. If critical points are uncountable, the Lindelof's lemma, which says every open cover there is a countable subcover, leads us to the fact that the set of initial conditions that converge to the set of saddle points (uncountable) is a countable union of measure zero sets, thus, a measure zero set. Formally, it is stated as follows.

Theorem 4. Suppose f : M → R is geodesically µ-convex in neighborhood of local minima. Then the set of initial points (x0, v0) ∈ M ×M converging to saddle points of f under the Riemannian Accelerated Gradient Descent [Zhang and Sra, 2018] has measure (induced by the product metric) of zero.

The proof is left in Appendix.

Corollary 5. Let M = M1 × ... ×Mn. Suppose that f : M→ R is geodesically µ-convex in neighborhood of local minima. Then the set of initial points (-→x 0, -→v 0) ∈M×M converging to saddle points of f has measure (induced by the product metric) of zero.

The proof is completed by trivially consideringMas the manifold in Theorem 4, all the structures of the proof can be carried over. The following corollary is immediate from Theorem 4 and Corollary 5.

Corollary 6. LetM=∆1 × ... ×∆n, where

Suppose f : M → R is C 2 and geodesically convex w.r.t. the product Shahshahani metric. Then the Accelerated Multiplicative Weights Update algorithm avoids interior saddle points almost always, i.e., randomly choose an initial point, the algorithm will avoid interior saddle points with probability one.

Remark 7. In many applications, the constraint is compact, i.e., ∆i = {xi ∈ Rdi : ∑di s=1 xis = 1, xis ≥ 0}, and we might be interested in convergence to second-order stationary points [Panageas et al., 2019b; Lu et al., 2019]. With Theorem 2, Lemma 3.1 and Lemma 3.2 in [Panageas et al., 2019b], one can extend the result of Corollary 6 to convergence to second-order stationary points with compact constraints.

5 Experiments

Algorithms for comparison. The experiments are designed to understand the behavior of A-MWU compared to classic MWU and Accelerated Mirror Descent (A-MD) proposed by [Krichene et al., 2015], especially their behaviors near a saddle point. Since the performance of A-MD is controlled by the parameter r in [Krichene et al., 2015], i.e., the larger r ends up with a smoother curve of convergence, but with a slower rate of convergence. In order to understand exactly how A-MWU performs, we choose different r in Accelerated Mirror Descent while keep the step-size of A-MWU and A-MD the same.

Parameter setting. In our experiments, we set the parameters as follows:

• β = 0.001 and µ = 1 for Rosenbrock function, Figure 1.
• β = 0.1 and µ = 1 for Bohachevsky function, Figure 2.
• β = 0.1 and µ = 0.2 for Test function 1, Figure 3.
• β = 0.001 and µ = 0.001 for Test function 2, Figure 4.
• β = 0.1 and µ = 0.5 for two-agent, Figure 5.

In general, by definition of geodesic convexity, the principle of choosing µ is to estimate a lower bound of the actual geodesic convexity parameter µ. Since when µ > µ0, then the convexity inequality holds for µ0 if it holds for µ. To achieve fast local convergence rate, one can choose β ≈ 15 √µ/L according to [Zhang and Sra, 2018]. There is a further discussion on parameters in Appendix.

Efficiency in convergence. For the local convergence behavior, we use Rosenbrock function and Bohachevsky function as the test functions.

• The Rosenbrock function: (0.5-x)2 +0.25(y -x2 )2 + x + y + z - 1, with initial points (0.2, 0.4, 0.4), and the step sizes are 0.01 for A-MWU, MWU and A-MD, see Figure 1.
• The Bohachevsky function: x2 + 2y2 - 0.3 cos(3πx) - 0.4 cos(4πy) + x + y + z - 1, with initial point (0.35, 0.3, 0.35), and step-size 0.001, see Figure 2.

Compared to the usual definitions of 2-dimension Rosenbrock function and Bohachevsky function, our expression contains an additional term x+y +z -1 to make the function well defined in R3 . But in simplices, x + y + z - 1 = 0 always holds, thus our definition boils down to the original definitions.

Efficiency in escaping saddle points. We compare the curves of convergence and trajectories of A-MWU, A-MD and MWU for the function with many saddle points, in order to illustrate the different efficiency of three algorithms in escaping saddle points.

• Test function 1: cos(8.5x) sin(8.5(y-0.4))+sin(8.5z), with initial point (0.42, 0.24, 0.33), and the step-size is 0.005.
• Test function 2: cos(0.7x) sin(y) sin(0.9z) + x2 , with initial point (0.6, 0.2, 0.2), and the step-size is 0.05

Multiple simplices. We give a final illustration on the behavior of A-MWU in two-agent case. Suppose (x1, x2) ∈ [0, 1]× [0, 1] and satisfies x1 + x2 = 1, (y1, y2) ∈ [0, 1] × [0, 1] and y1 + y2 = 1. The function is of the form cos(10x1) sin(x2) + sin(10y1) cos(y2).

Experimental conclusions. The experimental results indicate the following:

• As expected, all experiments have verified that A-MWU has a better convergence behavior and efficiency in escaping saddle points compared to classic MWU.
• Compared to Accelerated Mirror Descent with entropy regularizer [Krichene et al., 2015], the proposed algorithm A-MWU has the similar acceleration effect as AMD with small r value, and outperforms A-MD with larger r value. See Figure 1 and 2.
• From Figure 3-(a) and Figure 4-(a), we believe that AMWU has potential to outperform A-MD significantly in escaping saddle points.

6 Conclusion

In this paper we study an Accelerated Multiplicative Weights Update from the Riemannian geometric viewpoint. We prove that with locally geometric convexity in local minima, RAGD avoids saddle points with random initialization, which implies that A-MWU avoids saddle points. This indicates that AMWU converges to local minima provided RAGD converges. Our experiments have verified the efficiency of A-MWU in escaping saddle points.

Acknowledgements

Yi Feng acknowledges Grant 202110458 from SUFE. Ioannis Panageas wants to thank a startup grant. Xiao Wang acknowledges Grant 202110458 from SUFE and support from the Shanghai Research Center for Data Science and Decision Technology.