Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always

Introduction

The interplay between the structure of saddle points and the performance of first order algorithms is a critical aspect of non-concave maximization. In the unconstrained setting, there have been many recent results indicating that gradient descent (GD) avoids strict saddle points with random initialization , (see also for the analogue in min-max optimization). Moreover by adding noise, it is guaranteed that GD converges to a local maximum in polynomial time (see , and references therein). By adding a non-smooth function in the objective (e.g., the indicator function of a convex set) it can be shown that there are stochastic first order methods that converge to a local minimum point in the constrained case under the assumption of oracle access to the stochastic (sub)gradients. What is less understood is the problem of convergence to second order stationary points in constrained optimization (under the weaker assumption that we do not have access to the subgradient of the indicator of the feasibility set; in other words when projection to the feasibility set is not a trivial task). In the case of constrained optimization, we also note that the techniques of are not applicable in a straightforward way.

In this paper we focus on solving problems of the form

where $P$ is a non-concave, twice continuously differentiable function and $D$ is some compact set, which will be a product of simplices for our purposes, i.e., $D=\{(x_{ij})|x_{ij}\geq 0,\sum_{j=1}^{M}x_{ij}=1\textrm{ for all }1\leq i\leq N\}$, where $N,M$ are natural numbers. As a result, vector $\mathbf{x}$ can be also interpreted as a collection of $N$ probability distributions (having $N$ players), where each distribution $\mathbf{x}_{i}$ has support of size $M$ (strategies). For this particular problem (1), one natural algorithm that is commonly used is the Baum-Eagon dynamics (2) (see the seminal paper by Baum and Eagon ) with many applications to inference problems, Hidden Markov Models (HMM) in particular (see also discussion in Section 4).

Despite its power, Baum-Eagon dynamics has its limitations. First and foremost, the Baum-Eagon dynamics is not always well-defined; the denominator term \sum_{s}x^{t}_{is}\frac{\partial P}{\partial x_{is}}\big{|}_{\mathbf{x}^{t}} must be non-zero at all times and moreover the fraction in equations (2) should always be non-negative. This provides a restriction to the class of functions $P$ to which the Baum-Eagon dynamics can be applied. Moreover, it turns out that the update rule of the Baum-Eagon dynamics is not always a diffeomorphism.A function is called a diffeomorphism if it is differentiable and a bijection and its inverse is differentiable as well. In fact, as we show even in simple settings (see section 2.3) the Baum-Eagon dynamics may not be even a homeomorphism or one-to-one. This counterexample disproves a conjecture by Stebe. Since the map is not even a local diffeomorphism one cannot hope to leverage the power of Center-stable manifold theorem to argue convergence towards local maxima.

To counter this, in this paper we focus on multiplicative weights update algorithm (MWU) which can be interpreted as an instance of Baum-Eagon dynamics in the presence of learning rates. Introducing learning rates gives us a lot of flexibility and will allow us to formally prove strong convergence properties which would be impossible without this adaptation. Assume that $\mathbf{x}^{t}$ is the $t$-th iterate of MWU, the equations of which can be described as follows:

We will need the following two definitions (well-known in optimization literature, as applied to simplex constraints):

$\mathbf{x}^{*}$ is called a stationary point as long as it satisfies the first order KKT conditions for the problem (1). Formally, it holds

The stationary point is called strict if the last inequalities hold strictly.

$\mathbf{x}^{*}$ is called a second order stationary point as long as it is a stationary point and moreover it holds that:

for all $\mathbf{y}$ such that $\sum_{j=1}^{M}y_{ij}=0$ (for all $1\leq i\leq N$) and $y_{ij}=0$ whenever $x^{*}_{ij}=0$, i.e., it satisfies the second order KKT conditions.

Assume that $P$ is twice continuously differentiable in a set containing $D$. There exists small enough fixed stepsizes $\epsilon_{i}$ such that the set of initial conditions $\mathbf{x}^{0}$ of which the MWU dynamics (3) converges to fixed points that violate second order KKT conditions is of (Lebesgue) measure zero.

The following corollary is immediate from Theorem 1.3 and the Baum-Eagon inequality for rational functions (see Section 2).

Assume $\mu$ is a measure that is absolutely continuous with respect to the Lebesgue measure and $P$ is a rational function (fraction of polynomials) that is twice continuously differentiable in a set containing $D$, with isolatedA stationary point is isolated if there exists a neighborhood around it so that there is no other stationary point in that neighborhood. stationary points. It follows that with probability one (randomness induced by $\mu$), MWU dynamics converges to second order stationary points.

It is obvious that when the learning rates $\epsilon_{i}=0$, MWU (3) is trivially the identity map. On the other hand, whenever the dynamics is well defined in the limit $\epsilon\rightarrow\infty$ (i.e. when $P$ is sufficiently well behaved, e.g. a polynomial with positive coefficients) this corresponds to the well known class of Baum-Eagon maps .

We conclude our results by showing that it is unlikely that MWU dynamics converges fast to second (or even first) order stationary points when MWU is applied to solve problem (1). The problem of finding first (resp. second) order stationary points are inherently connected with the problem of finding mixed (resp. pure) Nash equilibria in congestion games. Currently, no polynomial time algorithms are known for computing mixed Nash in congestion games (the problem lies between P and CLSCLS is a computational complexity class that captures continuous local search. It lies on the intersection of the mores well studied classes of PLS and PPAD.) , whereas computing pure Nash Nash equilibria even in linear congestion games, is known to be PLS-complete . The reductions between the problems is based on the fact that congestion games are potential games and hence (3) captures the behavior of self-interested learning agents playing a congestion game.

Our techniques

The first step of the proof given in Section 3 is to prove that MWU converges to fixed points for all rational functions and any possible set of learning rates (as long as the dynamics is well defined). The proof of this statement leverages recently discovered connections between MWU and the Baum-Eagon dynamics . However, this does not even allow us to exclude very suboptimal fixed points (i.e. saddle points or even local minima) from having a positive region of attraction.

The other two steps of the proof work on weeding out the ”bad” stationary points and showing that the set of initial conditions that converge to them is of measure zero. The key tool for proving that type of statements is the Center-stable manifold theorem . However, in order to leverage the power of the theorem we first show in Theorem 2.3 that for small enough learning rates MWU is a diffeomorphism. The second and third step of the proof respectively is to show that fixed points that do not satisfy the first (resp. second) order stationary point conditions are unstable under MWU.

Even for the first step of the proof (lemma 3.1), we have to use ad-hoc techniques to deal with problems due to the constraints. Specifically, we start by projecting the domain $D$ to a subspace that is full dimensional (for example simplex of size $n$ is mapped to the Euclidean subspace of dimension $n-1$). Next, we show that non-first order stationary points result to fixed points where the Jacobian of MWU has eigenvalue larger than $1$. Proving a similar statement for the fixed points that correspond to non-second order stationary fixed points (lemma 3.2) is the most technical part of the proof as we have to deal with the asymmetry of the resulting Jacobian. Nevertheless we manage to do so by using Sylvester’s law of inertia and exploiting newly discovered decompositions for this class of matrices. Putting everything together results in our main theorem (Theorem 1.3).

Notation Throughout this article, $D$ is the product of $N$ simplices of size $M$ each, $D=\{(x_{ij})|x_{ij}\geq 0,\sum_{j=1}^{M}x_{ij}=1\textrm{ for all }1\leq i\leq N\},$ where we interpret $i$ as the index for the $N$ agents and $j$ the index of strategies $M$. We also use boldfaces to denote vectors, i.e., $\mathbf{x}$ and $[N]$ denotes $\{1,...,N\}$.

Optimization with Baum-Eagon Algorithm

In this section, we state the important result of Baum and Eagon providing a method to increase the value of a polynomial with nonnegative coefficients and (later generalized for) rational functions with nonzero denominators. The update rule defined by (6) increases the value of the polynomial $P$ if the initial point is not a fixed point of Baum-Eagon dynamics.

Let $P$ be a polynomial with real positive coefficients and variables $x_{ij}$, $i=1,...,k,j=1,...,n_{i}$. Let $n=\sum_{i=1}^{k}n_{i}$. Let $D$ be the product of simplexes. Define $\mathbf{x}^{\prime}:=T(\mathbf{x})$ as the vector in $D$ with component $ij$ given by

Let $P(\{x_{ij}\})$ be a polynomial with non-negative coefficients homogeneous of degree $d$ in its variables $\{x_{ij}\}$. Let $\mathbf{x}=\{x_{ij}\}$ be any point of the domain $D=\{x_{ij}\geq 0,\sum_{j=1}^{n_{i}}x_{ij}=1,i=1,2,...,k,j=1,2,...,n_{i}\}$. For $\mathbf{x}=\{x_{ij}\}\in D$, let $T(\mathbf{x})=T(\{x_{ij}\})$ be the point of $D$ whose $i,j$ coordinate is

Then $P(T(\mathbf{x}))>P(\mathbf{x})$ unless $T(\mathbf{x})=\mathbf{x}$.

2 Optimization for rational functions

According to , one can define a Baum-Eagon dynamics for rational functions $R(\mathbf{x})=\frac{S_{1}(\mathbf{x})}{S_{2}(\mathbf{x})}$ with positive denominator so that the update rule of the Baum-Eagon dynamics increases the value of the rational function $R$ for any given vector $\mathbf{y}$ unless $\mathbf{y}$ is a fixed point. This can be done by starting with the Baum-Eagon map of the following polynomial: Let $\mathbf{y}\in D$ be an arbitrary point.

where $d$ is the degree of $P_{\mathbf{y}}(\mathbf{x})$ and $N_{\mathbf{y}}$ is a constant such that $P_{\mathbf{y}}(\mathbf{x})+C_{\mathbf{y}}(\mathbf{x})$ only has nonnegative coefficients. It is proved in that $R(T(\mathbf{y}))>R(\mathbf{y})$ along the Baum-Eagon dynamics (update rule $T$) induced by polynomial $Q_{\mathbf{y}}(\mathbf{x})$.

3 Bad example on Baum-Eagon dynamics

L. Baum has an unpublished result claiming that the Baum-Eagon map $T$ is a homeomorphismA function is called a homeomorphism if it is continuous and a bijection and its inverse is continuous as well. Thus if a function is not a homeomorphism, then it is not a diffeomorphism. of $D$ onto itself if and only if the polynomial $P$ can be expressed as a sum that contains monomials of the form $c_{i,j}x_{i,j}^{w_{i,j}}$ for all $i=1,...,k,j=1,...,n_{i}$ where $c_{i,j}>0$ and $w_{i,j}$ is an integer greater than zero (this means that $P$ might also contain other terms, i.e, products of different variables). But this condition is incorrect and we give a counter example below. We note that our example indicates that the Baum-Eagon dynamics does not satisfy the nice property of being a diffeomorphism.

For a special case, we focus on the map $\tau$ defined on a single simplex (with $n$ variables)

The map defined in equation (8) can be expressed as a composition of $\tau_{1}$ and $\tau_{2}$ defined in the following way:

Consider 1-dimensional simplex as an example (i.e, $n=2$), $\tau_{1}$ maps the simplex $\Delta_{1}$ to a curve and $\tau_{2}$ maps points on the curve back to $\Delta_{1}$ by scaling.

From Figure 1(a), we notice that a necessary condition for $\tau$ to be a homeomorphism is that the curve $\tau_{1}(\Delta_{1})$ (image of $\Delta_{1}$ under $\tau_{1}$, see thick, black curve in Figure 1(a), 1(b)) does not cross twice (or more times) any line that passes through the origin and has slope non-negative (see also Figure 1(b)). A necessary condition for $\tau$ to be a homeomorphism is that $\tau$ must be one to one. In 1-dimensional case, the ratio

must be monotone with respect to $x_{1}$. The following example is a polynomial that satisfies Baum’s condition, however it holds that function $k$ is not monotone with respect to $x_{1}$.

Suppose $P=x_{1}+x_{1}^{7}x_{2}+x_{2}^{7}$, then

As it is shown in Figure 2, the ratio $k=x_{1}\frac{\partial P}{\partial x_{1}}/x_{2}\frac{\partial P}{\partial x_{2}}$ is not monotone with respect to $x_{1}$. So the Baum-Eagon map is not one to one implying that it is not a homeomorphism.

For any twice continuously differentiable function $P$, there exists a positive number $\delta$ depending on $P$, such that for any $\epsilon<\delta$, the Baum-Eagon map applied to $Q=\sum_{ij}x_{ij}+\epsilon P$ is a diffeomorphism.

Firstly, we prove that the Baum-Eagon map of $Q$ is a local diffeomorphism. For a fixed $i$, denote

Since the roots of the characteristic polynomial of a matrix vary continuously as a function of coefficients (see Theorem VI.1.2 in ), let $J_{\epsilon}$ be the Jacobian of the function $T(\mathbf{x})$, i.e., of the update rule of the Baum-Eagon dynamics induced by function $Q=\sum_{ij}x_{ij}+\epsilon P$ (note that $T$ coincides with the MWU dynamics for function $P$ with same stepsize $\epsilon$ (i.e., same learning rates)). The determinant $|J_{\epsilon}|$ is continuous with respect to $\epsilon$. When $\epsilon\rightarrow 0$, it holds that $|J_{\epsilon}|\rightarrow 1$ at each point $p\in D$ where the Jacobian is computed, thus for each point $p\in D$ there exists $\epsilon_{p}$, such that for all $\epsilon<\epsilon_{p}$, we get that $|J_{\epsilon}(p)|>1/2$.

Since the determinant is also continuous with respect to points in $D$, for $\epsilon_{p}$, there is a neighborhood of $p$, denoted as $U(p,\epsilon_{p})$, such that for all $\mathbf{x}\in U(p,\epsilon_{p})$, $|J_{\epsilon_{p}}(\mathbf{x})|>1/2$. Thus we have obtained an open cover of $D$, which is $\bigcup_{p\in D}U(p,\epsilon_{p})$. Since $D$ is compact, there is a finite subcover of $\bigcup_{p\in D}U(p,\epsilon_{p})$, denoted as $\bigcup_{i=1}^{n}U(p_{i},\epsilon_{p_{i}})$. Then the minimum of $\{\epsilon_{p_{i}}\}$ gives the $\delta$ in the lemma.

To prove that the Baum-Eagon map $T$ of $Q$ is a global diffeomorphism, one needs Theorem 2 in . Since $T$ is proper (preimage of compact set is compact) and $D$ is simply connected and path connected, we conclude that $T$ is a homeomorphism on $D$ (we suggest the reader to see the supplementary material for all the missing definitions). ∎

The above theorem essentially can be generalized for different stepsizes (learning rates) $\epsilon$ for each player. The idea is that we should apply the same techniques on the function $\sum_{i=1}^{N}\frac{1}{\epsilon_{i}}\sum_{j=1}^{M}x_{ij}+P$.

Convergence Analysis of MWU for Arbitrary Functions

In this section we provide the proof of Theorem 1.3. As has already been proven in previous section (Theorem 2.3), the update rule of the MWU dynamics is a diffeomorphism for appropriately small enough learning rates. Following the general framework of , we will also make use of the Center-stable manifold theorem (Theorem A.1). The challenging part technically in this paper is to prove that every stationary point $\mathbf{x}$ that is not a local maximum has the property that the Jacobian of the MWU dynamics computed at $\mathbf{x}$ has a repelling direction (eigenvector).

We focus on multiplicative weights updates algorithm. Assume that $\mathbf{x}^{t}$ is the $t$-th iterate of MWU. Recall the equations:

where $\epsilon_{i}$ the stepsize of the dynamics. Let $T:D\to D$ be the update rule of the MWU dynamics (11). Fix indexes $i,i^{\prime}$ for players and $j,s$ for strategies. Set $S_{i}=1+\epsilon_{i}\sum_{j^{\prime}}x_{ij^{\prime}}\frac{\partial P}{\partial x_{ij^{\prime}}}$. The equations of the Jacobian look as follows:

for all $i\in[N],$ $j,s\in[M],$ $j\neq s$ and

for all $i,i^{\prime}\in[N],$ $j,s\in[M],$ with $i\neq i^{\prime}$.

2 Stability and proof of Theorem 1.3

We prove the following important lemma that characterizes (partially) the unstable fixed points (meaning the spectral radius of the Jacobian computed at the fixed point is greater than one) of the MWU dynamics and relates them to the stationary points.

Let $\mathbf{y}$ be a fixed point of MWU dynamics that violates the first order KKT conditions (is not a first order stationary point). It holds that the projected Jacobian computed at $\mathbf{y}$ (formally now is the projected point $\mathbf{y}\in D_{\mathbf{y}}$) has an eigenvalue with absolute value greater than one.

Since $\mathbf{y}$ is not a stationary point, there exist $i,j$ and so that $y_{ij}=0$ but \frac{\partial P}{\partial x_{ij}}\big{|}_{\mathbf{x}=\mathbf{y}}>\sum_{j^{\prime}}y_{ij^{\prime}}\frac{\partial P}{\partial x_{ij^{\prime}}}\big{|}_{\mathbf{x}=\mathbf{y}}. The projected Jacobian computed at $\mathbf{y}$ has the property that for variable $x_{ij}$, the corresponding row has entries zeros, apart from the corresponding diagonal entry that is $\frac{1+\epsilon_{i}\frac{\partial P}{\partial x_{ij}}}{1+\epsilon_{i}\sum_{j^{\prime}}x_{ij^{\prime}}\frac{\partial P}{\partial x_{ij^{\prime}}}}>1$ (from the definition of stationary point). Since the projected Jacobian has as eigenvalue $\frac{1+\epsilon_{i}\frac{\partial P}{\partial x_{ij}}}{1+\epsilon_{i}\sum_{j^{\prime}}x_{ij^{\prime}}\frac{\partial P}{\partial x_{ij^{\prime}}}}$ the claim follows. ∎

The following technical lemma gives a full characterization among the unstable fixed points of MWU dynamics and the second order stationary points (local maxima). This lemma is more challenging than the stability analysis in due to the fact that we have constraints on simplex.

Let $\mathbf{x}^{*}$ be a fixed point of MWU dynamics that is a stationary point (satisfies first order KKT conditions) and violates the second order KKT conditions (is not a second order stationary point). It holds that the projected Jacobian computed at $\mathbf{x}^{*}$ (formally now is the projected point $\mathbf{x}^{*}\in D_{\mathbf{x}^{*}}$) has an eigenvalue with absolute value greater than one.

Because of Lemma 3.1 we may assume that $\mathbf{x}^{*}$ in the interior of $D$ (all coordinates are positive). Set S_{i}=1+\epsilon_{i}\sum_{j^{\prime}=1}^{M}x^{*}_{ij^{\prime}}\frac{\partial P}{\partial x_{ij^{\prime}}}\big{|}_{\mathbf{x}=\mathbf{x}^{*}} for $i\in[N]$. Set

where $D_{xs}$ is a diagonal matrix with positive diagonal entries and $D_{xx}$ has rank $N$. The Jacobian (not projected) of MWU dynamics computed at $\mathbf{x}^{*}$ can be expressed in a compact form (see Section 3.1 for the equations of the Jacobian) as

We can now prove our second main Theorem 1.3.

As long as we establish the idea of projecting the Jacobian, then the proof follows the lines of work of , and is rather generic. We shall show that the set of initial conditions so that MWU dynamics converges to unstable fixed points (meaning that the spectral radius of the Jacobian computed at the fixed point is greater than one) is of measure zero and then by Lemma 3.1, the proof follows. Let $\mathbf{y}$ be an unstable fixed point of the MWU (as a dynamical system) with update rule a function $T_{\mathbf{y}}:\mathcal{S}\to\mathcal{S}$. For such unstable fixed point $\mathbf{y}$, there is an associated open neighborhood $B_{\mathbf{y}}\subset\mathcal{S}$ promised by the Stable Manifold Theorem A.1.

Define $W_{\mathbf{y}}=\{\mathbf{x}^{0}\in D_{\mathbf{y}}:\lim_{t\to\infty}\mathbf{x}^{t}=\mathbf{y}\}$. Fix a point $\mathbf{x}^{0}\in W_{\mathbf{y}}$. Since $\mathbf{x}^{k}\to\mathbf{y}$, then for some non-negative integer $K$ and all $t\geq K$, $T_{\mathbf{y}}^{t}(\mathbf{x}^{0})\in B_{\mathbf{y}}$ ($T_{\mathbf{y}}^{t}$ denotes composition of $T_{\mathbf{y}}$ $t$ times). We mentioned above that $T_{\mathbf{y}}$ is a diffeomorphism in $\mathcal{S}$. By Theorem A.1, $Q_{\mathbf{y}}:=\cap_{k=0}^{\infty}T^{-k}_{\mathbf{y}}(B_{\mathbf{y}})$ is a subset of the local center-stable manifold which has co-dimension at least one, and $Q_{\mathbf{y}}$ is thus measure zero.

Finally, $T_{\mathbf{y}}^{K}(\mathbf{x}^{0})\in Q_{\mathbf{y}}$ implies that $\mathbf{x}^{0}\in T_{\mathbf{y}}^{-K}(Q_{\mathbf{y}})$. Since $K$ is unknown we union over all non-negative integers, to obtain $\mathbf{x}^{0}\in\cup_{j=0}^{\infty}T_{\mathbf{y}}^{-j}(Q_{\mathbf{y}})$. Since $\mathbf{x}^{0}$ was arbitrary, we have shown that $W_{\mathbf{y}}\subset\cup_{j=0}^{\infty}T_{\mathbf{y}}^{-j}(Q_{\mathbf{y}})$. Using Lemma 1 of page 5 in and that countable union of measure zero sets is measure zero, $W_{\mathbf{y}}$ has measure zero. The claim follows since by mapping $W_{\mathbf{y}}$ to the set $W$ (which is defined by padding the removed variables), then $W$ is the set of initial conditions that MWU dynamics converges to $\mathbf{y}$ and is of measure zero in $D$. ∎

3 On the speed of convergence

In this section we argue about the limitations of any algorithm that aims at solving maximization problem subject to simplex constraints (even for polynomial objectives), i.e., problem (1). We conclude that it is unlikely that MWU dynamics (or any other algorithm) converges in polynomial time to a local maximum (for problem (1)). In fact, as we will show providing a polynomial time algorithm for finding even first order stationary points for an arbitrary polynomial function is at least as hard as computing Nash equilibria for general congestion games, a problem for which no polynomial time algorithm is known and whose time complexity lies in CLS . Computing second order stationary points even for general bilinear functions, specifically even for function of the form $f(\mathbf{x})=\sum_{i,i^{\prime},i\neq i^{\prime}}\sum_{j,j^{\prime}}a_{ii^{\prime}jj^{\prime}}x_{ij}x_{i^{\prime}j^{\prime}}+\sum_{i}\sum_{j}b_{ij}x_{ij}$ is strongly connected with the problem finding pure Nash equilibria even in linear congestion games that is known to be PLS-complete .

Specifically, it suffices to focus on a special class of congestion games which are called threshold games. These are congestion games in which the set of resources $R$ is divided into two disjoint subsets $R_{in}$ and $R_{out}$. The set ${R}_{out}$ contains a resource $r_{i}$ for every player $i\in N$ . This resource has a fixed delay $T_{i}$ called the threshold of player $i$. Each player $i$ has exactly two strategies: a strategy $S_{i}^{out}=\{r_{i}\}$ with $r_{i}\in R_{i}^{out}$, and a strategy $S_{i}^{in}\subseteq R_{in}$. Agent $i$ prefers strategy $S_{i}^{in}$ to strategy $S_{i}^{out}$ if the total cost of playing $S_{i}^{in}$ is smaller than the threshold cost $T_{i}$. Quadratic threshold games are a subclass of threshold games in which the set $R_{in}$ contains exactly one resource $r_{ii^{\prime}}$ for every unordered pair of players $\{i,i^{\prime}\}\subset N$. For every player $i\in N$ of a quadratic threshold game, his strategy set $S_{in}=\{r_{ii^{\prime}}|i^{\prime}\in N,ji^{\prime}\neq i\}$. Without loss of generality let any resource $r_{ii^{\prime}}$ have a linear delay function of the form $c_{ii^{\prime}}(k)=a_{ii^{\prime}}k$ with $a_{ii^{\prime}}>0$. Furthermore, all thresholds can be assumed to be positive. proves that computing a Nash equilibrium of a quadratic threshold game with nondecreasing delay functions is PLS-complete.

Finding a first-order stationary point for a general polynomial function $f$ is at least as hard as computing a Nash equilibrium for general congestion games. Let $f(\mathbf{x})=\sum_{i,i^{\prime},i\neq i^{\prime}}\sum_{j,j^{\prime}}a_{ii^{\prime}jj^{\prime}}x_{ij}x_{i^{\prime}j^{\prime}}+\sum_{i}\sum_{j}b_{ij}x_{ij}$, where for all $i$, $\sum x_{ij}=1$. Finding a second-order stationary point of $f(x)$ is at least as hard as computing a pure Nash equilibrium in a generic quadratic threshold game.

Firstly, any first order stationary point of the expected value of the potential is a Nash equilibrium, since the gradient of the potential corresponds to the vector of deviating payoffs for all agents and all strategies. Thus. first order stationarity implies that only strategies that give maximal payoff are played with positive probability, i.e. the strategy is a Nash equilibrium. The expected value of the potential function of a quadratic threshold congestion games is a bilinear function. This is trivially true since each resource can only be used by at most two agents. Specifically the expected value of the potential function of the game when each agent $i$ is using mixed strategy $(x_{iS_{i}^{in}},x_{iS_{i}^{out}})$ is equal to $\sum_{i\in N}x_{iS_{i}^{in}}T_{i}+\sum_{i\in N}x_{iS_{i}^{out}}\sum_{i^{\prime}\neq i}a_{ii^{\prime}}+\sum_{i,i^{\prime},i\neq i^{\prime}}x_{iS_{i}^{out}}x_{i^{\prime}S_{i^{\prime}}^{out}}a_{ii^{\prime}}$. By the genericity assumption we can assume that the number of fixed points of MWU are finite and isolated, e.g. . If this Nash equilibrium is pure then we are done. Suppose not, in which case there exist some agents that play mixed strategies with support equal to $2$. Since the potential is a bilinear function it can be computed without error using its gradient and Hessian via Taylor expansion. Second order stationarity now implies that for any coordinated set of deviations of two of the randomizing agents the potential can still not improve. Consider the continuum of strategy profiles $(\zeta_{i},x_{-i})$ where $i$ was a randomizing agent that now deviates and plays strategy $S_{i}^{in}$ with arbitrary probability $\zeta_{i}\in$. Since the original strategy profile $x$ is a NE, agent $i$ is still indifferent between his two actions. As we have argued any profile that exactly two randomizing agents deviate does not affect the value of the expected potential for so the value of the potential does not change. So, even if agent $i^{\prime}$ was to deviate to strategy $\zeta_{i}^{\prime}\in$, the value of the potential at $(\zeta_{i},\zeta_{i}^{\prime},x_{-i,i^{\prime}})$ cannot be higher that its value at $(\zeta_{i},x_{-i})$ and $x$. So, none of the randomizing agents at any strategy profile $(\zeta_{i},x_{-i})$ can profit by deviating. Each point on the line segment $(\zeta_{i},x_{-i})$ with $\zeta_{i}\in$ is a stationary point of MWU, and we reach a contradiction to our genericity assumption. Thus, the second order stationary point of the potential is a pure Nash. ∎

Applications

One application of Baum-Eagon algorithm is parameter estimation via maximum likelihood. Suppose that $X_{1},...,X_{n}$ are samples from a population with probability density function $f(x|\theta_{1},...,\theta_{k})$, the likelihood function is defined by

Maximum likelihood estimator has many applications in machine learning and statistics (e.g., regression) and when is consistent, the problem of estimation boils down to maximizing the likelihood function. This can be achieved via the E-M algorithm based on the Baum-Eagon inequality. For example, the estimation of the parameters of hidden Markov models (motivated by real world problems, see for an example on speech recognition) result in the maximization of rational functions over a domain of probability values. The rational functions are conditional likelihood functions of parameters $\theta=(\theta_{1},...,\theta_{k})$. The Baum-Eagon dynamics is used to estimate the parameters of hidden Markov models. Our main result indicates that MWU dynamics should be used for the optimization part as MWU has some nice properties (well-defined, update rule is a diffeomorphism, avoids non-stationary points) in which Baum-Eagon dynamics might not have.

Below we provide a pictorial illustration of MWU dynamics applied to a non-concave function (not rational). The function we consider is $P(x,y)=cos(8x)sin(6y)$ and we want to optimize it over $R=\{(x,y):0\leq x\leq 1,0\leq y\leq 1\}$ (see Figure 3 for the landscape). The aforementioned instance is captured by our model for $N=M=2$, in which we have essentially projected the space by using one variable for each player (for player one, the second variable is $1-x$ and for player two is $1-y$). The equations of MWU dynamics boil down to the following:

We demonstrate in Figure 4 the “vector field” of MWU dynamics (because it is a discrete time system it is not precisely vector field, at point $(x,y)$ we plot a vector with direction $T(x,y)-(x,y)$, where $T$ is the update rule of dynamics (13)). The three dots indicate the local maxima of $P$ and the rest of the points do not satisfy the second order KKT conditions. We see that MWU dynamics avoids those points that do not satisfy the second order KKT conditions (avoids those that are not local maxima).

References

Appendix A Stable manifold theorem

Let $x^{*}$ be a fixed point for the $C^{r}$ local diffeomorphism $g:\mathcal{X}\to\mathcal{X}$. Suppose that $E=E_{s}\oplus E_{u}$, where $E_{s}$ is the span of the eigenvectors corresponding to eigenvalues of magnitude less than or equal to one of $Dg(x^{*})$, and $E_{u}$ is the span of the eigenvectors corresponding to eigenvalues of magnitude greater than one of $Dg(x^{*})$Jacobian of function $g$.. Then there exists a $C^{r}$ embedded disk $W^{cs}_{loc}$ of dimension $dim(E^{s})$ that is tangent to $E_{s}$ at $x^{*}$ called the local stable center manifold. Moreover, there exists a neighborhood $B$ of $x^{*}$, such that $g(W^{cs}_{loc})\cap B\subset W^{cs}_{loc}$, and $\cap_{k=0}^{\infty}g^{-k}(B)\subset W^{cs}_{loc}$.

Appendix B Preliminaries on Topology

This section provides fundamentals used in the proof of Theorem 2.3. For more information on proper maps and the fundamental group, see and .

$X$ is a Hausdorff space if for every pair of points $p,q\in X$, there are disjoint open subsets $U,V\subset X$ such that $p\in U$ and $q\in V$.

Let $X$ and $Y$ are topological spaces. A map from $X$ to $Y$, denoted $f:X\rightarrow Y$, is called proper if the inverse of each compact subset of $Y$ is a compact subset of $X$.

A topological space $X$ is connected if there are no disjoint open subsets $U,V\subset X$, such that $U\cup V=X$.

A path from a point $x$ to a point $y$ in a topological space $X$ is a continuous function $f:\rightarrow X$ with $f(0)=x$ and $f(1)=y$. The space $X$ is said to be path-connected if there exists a path joining any two points in $X$. A homotopy of paths in $X$ is a family $f_{t}:\rightarrow X$, $0\leq t\leq 1$, such that

The endpoints $f_{t}(0)=x_{0}$ and $f_{t}(1)=x_{1}$ are independent of $t$.

The associated map $F:\times\rightarrow X$ defined by $F(s,t)=f_{t}(s)$ is continuous.

When two paths $f_{0}$ and $f_{1}$ are connected in this way by a homotopy $f_{t}$, they are said to be homotopic. The notation for this is $f_{0}\simeq f_{1}$.

The relation of homotopy on paths with fixed endpoints in any space is an equivalence relation.

The equivalence class of a path $f$ under the equivalence relation of homotopy is denoted $[f]$ and called the homotopy class of $f$. Given two paths $f,g:\rightarrow X$ such that $f(1)=g(0)$, there is a product path $f\cdot g$ that traverses first $f$ and then $g$, defined by the formula

The paths with the same starting and ending point are called loops, and the common starting and ending point is called the basepoint. The set of all homotopy classes $[f]$ of loops $f:\rightarrow X$ at the basepoint $x_{0}$ is denoted $\pi_{1}(X,x_{0})$.

$\pi_{1}(X,x_{0})$ is a group with respect to the product $[f][g]=[f\cdot g]$.

And the group $\pi_{1}(X,x_{0})$ is called the fundamental group.

A topological space $X$ is simply connected if it is path-connected and has trivial fundamental group.

The space $D$ that is a product of simplexes is simply-connected.

The following theorem (used in the proof of Theorem 2.3) gives a sufficient and necessary condition under which a local homeomorphism $f:X\rightarrow Y$ becomes a global homeomorphism.

Let $X$ be path-connected and $Y$ be simply-connected Hausdorff spaces. A local homeomorphism $f:X\rightarrow Y$ is a global homeomorphism of $X$ to $Y$ if and only if the map $f$ is proper.