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

Ioannis Panageas, Georgios Piliouras, Xiao Wang

Abstract

Non-concave maximization is central to modern machine learning, particularly in deep learning. While first-order methods are known to avoid saddle points in unconstrained settings, constrained optimization presents unique challenges, especially when critical points lie on the boundary of the feasibility set. This paper analyzes the Multiplicative Weights Update (MWU) algorithm for maximizing non-concave, twice continuously differentiable functions over products of simplices. We demonstrate that for sufficiently small stepsizes, MWU converges almost always to second-order stationary points (local maxima), effectively avoiding unstable saddle points.

Introduction

In deep learning, the fear of getting stuck in "saddle points"—points where the gradient is zero but are not local optima—is a major concern. While Gradient Descent (GD) has been proven to avoid these points in unconstrained environments, many real-world applications involve constraints. For instance, training Hidden Markov Models or computing Nash Equilibria requires variables to remain within a "simplex" (non-negative values summing to one).

Standard approaches like Projected Gradient Descent require expensive projection steps at every iteration. This paper explores the Multiplicative Weights Update (MWU) algorithm, a "projection-free" method that naturally respects simplex constraints. We provide a formal guarantee that MWU can navigate these constrained, non-concave landscapes to find high-quality solutions.

Methodology: A Dynamical Systems Approach

The researchers treat the MWU update rule as a discrete-time dynamical system. Their proof of convergence relies on three primary mathematical pillars:

1. The Center-Stable Manifold Theorem

To prove that MWU avoids saddle points, the authors employ the Center-Stable Manifold Theorem. This theorem posits that the set of initial points leading to an unstable equilibrium (like a saddle point) has a measure of zero. Consequently, with random initialization, the algorithm will "almost always" avoid these undesirable points.

2. Ensuring Diffeomorphism

For the Stable Manifold Theorem to be applicable, the update mapping must be a diffeomorphism—a smooth and invertible map. A significant contribution of this paper is identifying that the classic Baum-Eagon dynamics (a precursor to MWU) can be non-invertible.

Figure 1: A well-behaved, injective mapping where distinct points A and B map to distinct points.
Figure 2: A non-invertible mapping where two distinct points A and B map to the same point, violating the diffeomorphism requirement.

The authors demonstrate that the introduction of a small learning rate (step size $\epsilon$) in the MWU formulation is the critical factor that ensures the mapping remains a diffeomorphism, providing the necessary mathematical stability for convergence.

3. Stability and Linear Algebra

By analyzing the Jacobian matrix of the MWU update at stationary points and applying Sylvester’s Law of Inertia, the authors show that saddle points (which violate second-order KKT conditions) result in a Jacobian with at least one eigenvalue greater than one. This makes such points "repelling" within the dynamical system.

Key Insights

  • "Projection for Free": MWU's multiplicative nature ensures that if you start within a simplex, you stay there. This eliminates the computational overhead of projection steps required by standard gradient methods.
  • Boundary Awareness: Unlike previous research that focused on the interior of the feasible set, this work explicitly addresses critical points on the boundary. This is vital for game theory, where Nash Equilibria often reside on the edges of the strategy space.
  • Distributed Computation: MWU can be executed in a distributed, concurrent manner, making it highly suitable for large-scale machine learning tasks.

Results and Complexity

The primary result (Theorem 1.3) guarantees that for small enough stepsizes, MWU converges to second-order stationary points (local maxima) for almost all initial conditions. These points satisfy the standard Karush-Kuhn-Tucker (KKT) conditions for optimality.

However, the paper notes a theoretical "catch": finding these stationary points is PLS-complete. While the algorithm is guaranteed to eventually find a local maximum, it may not do so in polynomial time in the worst-case scenario.

Limitations and Future Directions

While providing strong theoretical foundations, the work notes several areas for further exploration:

  • Step Size Sensitivity: The diffeomorphism property depends on a "small enough" $\epsilon$. Choosing an inappropriate step size in practice could lead to chaotic behavior.
  • Constraint Geometry: The current analysis is specifically tailored to products of simplices. Generalizing these results to other convex or non-convex constraints remains an open challenge.
  • Convergence Rates: While "almost always" convergence is proven, universal bounds on the speed of convergence for general non-concave functions are not yet established.

Summary based on research by Ioannis Panageas, Georgios Piliouras, and Xiao Wang (SUTD).

Summary updated

Abstract

Non-concave maximization has been the subject of much recent study in the optimization and machine learning communities, specifically in deep learning. Recent papers Ge et al, Lee et al (and references therein) indicate that first order methods work well and avoid saddle points. Results as in Lee et al, however, are limited to the \textit{unconstrained} case or for cases where the critical points are in the interior of the feasibility set, which fail to capture some of the most interesting applications. In this paper we focus on \textit{constrained} non-concave maximization. We analyze a variant of a well-established algorithm in machine learning called Multiplicative Weights Update (MWU) for the maximization problem $\max_{\mathbf{x} \in D} P(\mathbf{x})$, where $P$ is non-concave, twice continuously differentiable and $D$ is a product of simplices. We show that MWU converges almost always for small enough stepsizes to critical points that satisfy the second order KKT conditions. We combine techniques from dynamical systems as well as taking advantage of a recent connection between Baum Eagon inequality and MWU (Palaiopanos et al).
BibTeX
@inproceedings{panageas2019multiplicative,
  author = {Ioannis Panageas and Georgios Piliouras and Xiao Wang},
  title = {{Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=HkbSA9b_WH},
}
Figure