Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management

Yi Feng, Xiao Wang, Tian XieAAAI 2025 · DOI

TL;DR

This paper introduces the Langevin Multiplicative Weights Update (LMWU) algorithm, a novel approach for solving complex, non-convex optimization problems over product of simplices. LMWU enhances the classic Multiplicative Weights Update (MWU) by incorporating noise inspired by geometric Brownian motion on Riemannian manifolds, enabling it to escape local minima and converge to global optima. The authors demonstrate its effectiveness in polynomial portfolio management, showing superior performance compared to existing methods.

What Problem Does This Paper Address?

Many real-world optimization problems, particularly in areas like multi-agent systems, game theory, and machine learning (e.g., finding Nash equilibria, training neural networks), involve optimizing objective functions that are non-convex and constrained to a product of simplices. While standard optimization algorithms like projected gradient descent can struggle with such problems, and even advanced methods like MWU often only guarantee convergence to local or second-order stationary points, finding the true global minimum remains a significant challenge. The paper specifically addresses the gap in algorithms that can provably converge to global optima in these constrained, non-convex settings, especially within frameworks relevant to game theory and distributed optimization.

Methods

The core contribution is the Langevin Multiplicative Weights Update (LMWU) algorithm. LMWU builds upon the established Multiplicative Weights Update (MWU) framework, which is known for its effectiveness in constrained optimization and game theory. The key innovation is the integration of a noise term that is scaled according to the non-Euclidean geometry of the simplex, specifically leveraging the Shahshahani geometry. This noise is inspired by the Langevin algorithm, which uses stochastic differential equations to sample from probability distributions and has shown promise in escaping local minima.

The derivation of LMWU involves:

  • Geometric Brownian Motion on Riemannian Manifolds: The noise is derived from the geometric Brownian motion on a simplex, which is treated as a Riemannian manifold with the Shahshahani metric.
  • Discretization: The continuous-time geometric Brownian motion is discretized to be incorporated into the iterative update rule of MWU.
  • Theoretical Analysis: The authors provide a non-asymptotic convergence analysis, proving that LMWU converges to interior global minima in expectation under certain assumptions about the objective function (e.g., M-smoothness, existence of a lower bound on the gradient's directional derivative, and log-Sobolev inequality for the target distribution).

Datasets

The paper uses a dataset of daily stock entries for 10 NASDAQ stocks from January 3, 2011, to December 31, 2021 (2517 periods). This data is used to evaluate portfolio optimization strategies in a rolling-window, out-of-sample forecasting setting. No new benchmarks are introduced; rather, the dataset is used to test the proposed algorithm against existing methods in a practical application.

Key Insights and Ideas

  • Bridging MWU and Langevin Dynamics: The paper successfully merges the strengths of MWU (efficiency on simplex constraints, game theory relevance) with the global convergence properties of Langevin-based methods (escaping local minima).
  • Geometry Matters: The non-Euclidean geometry of the simplex (Shahshahani geometry) is crucial for correctly scaling the noise term, allowing the algorithm to navigate the constraint space effectively.
  • Provable Global Convergence: Unlike many existing methods that only guarantee local convergence, LMWU is theoretically shown to converge to global optima under specific conditions, which is a significant theoretical advancement.
  • Practical Efficacy: The algorithm demonstrates superior performance in a realistic portfolio management scenario, suggesting its practical utility beyond theoretical guarantees.

Key Results

  • Theoretical Convergence: The paper provides a theoretical guarantee that LMWU converges to interior global minima in expectation.
  • Empirical Performance: In the polynomial portfolio optimization task, LMWU consistently outperformed the standard MWU, Accelerated MWU, and Projected Langevin algorithms across various risk preference settings. For instance, under the "Degenerate" preference, LMWU achieved a score of 70.8930, better than MWU's 74.7203. For Mean-Variance (MV) and Mean-Variance-Skewness (MVS) preferences, LMWU achieved scores of 0.8464 and 0.8314, respectively, outperforming MWU's 0.8561 and 0.8391.
  • Escaping Local Minima: Experimental results on non-convex test functions (Figure 1 and 2) show LMWU escaping local minima and finding smaller function values compared to other algorithms, which often get stuck.

Limitations and Future Work

  • Assumptions: The theoretical guarantees rely on several assumptions about the objective function, including M-smoothness, a lower bound on the gradient's directional derivative, and the log-Sobolev inequality for the target distribution. The applicability of these assumptions to all real-world problems might be a limitation.
  • Time-Varying Environments: The paper notes that its current work does not address time-varying environments, which are common in applications like portfolio management.
  • Future Work: The authors suggest investigating time-varying portfolio management as a future direction. They also mention that future experiments will focus on demonstrating how LMWU's trajectories avoid local minima and converge to global ones.

Summary updated

BibTeX
@inproceedings{feng2025langevin,
  author = {Yi Feng and Xiao Wang and Tian Xie},
  title = {{Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33220},
}
Figure