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.
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