Second-Order Mirror Descent: Convergence in Games Beyond Averaging and Discounting

• URL: http://arxiv.org/abs/2111.09982v4
• Date: Fri, 30 Jun 2023 20:18:52 GMT
• Title: Second-Order Mirror Descent: Convergence in Games Beyond Averaging and Discounting
• Authors: Bolin Gao, Lacra Pavel
• Abstract summary: We show that MD2 enjoys no-regret as well as an exponential rate of convergence towards strong VSS upon a slight modification. MD2 can also be used to derive many novel continuous-time primal-space dynamics.
• Score: 1.2183405753834562
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In this paper, we propose a second-order extension of the continuous-time game-theoretic mirror descent (MD) dynamics, referred to as MD2, which provably converges to mere (but not necessarily strict) variationally stable states (VSS) without using common auxiliary techniques such as time-averaging or discounting. We show that MD2 enjoys no-regret as well as an exponential rate of convergence towards strong VSS upon a slight modification. MD2 can also be used to derive many novel continuous-time primal-space dynamics. We then use stochastic approximation techniques to provide a convergence guarantee of discrete-time MD2 with noisy observations towards interior mere VSS. Selected simulations are provided to illustrate our results.

Related papers

• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  Non-ergodic convergence of learning dynamics in games is widely studied because of its importance in both theory and practice. Recent work showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update, can exhibit arbitrarily slow last-iterate convergence. We show that OMWU achieves an $O(T-1/6)$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games.
  arXiv  Detail & Related papers  (2025-03-04T17:49:24Z)
• Lightweight Channel-wise Dynamic Fusion Model: Non-stationary Time Series Forecasting via Entropy Analysis [25.291749176117662]
  We show that variance can be a valid and interpretable proxy for non-stationarity of time series. We propose a novel lightweight textitChannel-wise textitDynamic textitFusion textitModel (textitCDFM) Comprehensive experiments on seven time series datasets demonstrate the superiority and generalization capabilities of CDFM.
  arXiv  Detail & Related papers  (2025-03-04T13:29:42Z)
• DeSiRe-GS: 4D Street Gaussians for Static-Dynamic Decomposition and Surface Reconstruction for Urban Driving Scenes [71.61083731844282]
  We present DeSiRe-GS, a self-supervised gaussian splatting representation. It enables effective static-dynamic decomposition and high-fidelity surface reconstruction in complex driving scenarios.
  arXiv  Detail & Related papers  (2024-11-18T05:49:16Z)
• Mutual Learning for Acoustic Matching and Dereverberation via Visual Scene-driven Diffusion [93.32354378820648]
  We introduce MVSD, a mutual learning framework based on diffusion models. MVSD considers the two tasks symmetrically, exploiting the reciprocal relationship to facilitate learning from inverse tasks. Our framework can improve the performance of the reverberator and dereverberator.
  arXiv  Detail & Related papers  (2024-07-15T00:47:56Z)
• Non-Adversarial Learning: Vector-Quantized Common Latent Space for Multi-Sequence MRI [15.4894593374853]
  We propose a generative model that compresses discrete representations of each sequence to estimate the Gaussian distribution of common latent space between sequences. Experiments using BraTS2021 dataset show that our non-adversarial model outperforms other GAN-based methods.
  arXiv  Detail & Related papers  (2024-07-03T08:37:01Z)
• Chimera: Effectively Modeling Multivariate Time Series with 2-Dimensional State Space Models [5.37935922811333]
  State Space Models (SSMs) are classical approaches for univariate time series modeling. We present Chimera that uses two input-dependent 2-D SSM heads with different discretization processes to learn long-term progression and seasonal patterns. Our experimental evaluation shows the superior performance of Chimera on extensive and diverse benchmarks.
  arXiv  Detail & Related papers  (2024-06-06T17:58:09Z)
• A Poisson-Gamma Dynamic Factor Model with Time-Varying Transition Dynamics [51.147876395589925]
  A non-stationary PGDS is proposed to allow the underlying transition matrices to evolve over time. A fully-conjugate and efficient Gibbs sampler is developed to perform posterior simulation. Experiments show that, in comparison with related models, the proposed non-stationary PGDS achieves improved predictive performance.
  arXiv  Detail & Related papers  (2024-02-26T04:39:01Z)
• Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
  We study online meta-learning with bandit feedback. We learn to tune online mirror descent generalization (OMD) with self-concordant barrier regularizers.
  arXiv  Detail & Related papers  (2023-07-05T13:52:10Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Generative Time Series Forecasting with Diffusion, Denoise, and Disentanglement [51.55157852647306]
  Time series forecasting has been a widely explored task of great importance in many applications. It is common that real-world time series data are recorded in a short time period, which results in a big gap between the deep model and the limited and noisy time series. We propose to address the time series forecasting problem with generative modeling and propose a bidirectional variational auto-encoder equipped with diffusion, denoise, and disentanglement.
  arXiv  Detail & Related papers  (2023-01-08T12:20:46Z)
• Deep Switching State Space Model (DS$^3$M) for Nonlinear Time Series Forecasting with Regime Switching [3.3970049571884204]
  We propose a deep switching state space model (DS$3$M) for efficient inference and forecasting of nonlinear time series. The switching among regimes is captured by both discrete and continuous latent variables with recurrent neural networks.
  arXiv  Detail & Related papers  (2021-06-04T08:25:47Z)
• On Centralized and Distributed Mirror Descent: Exponential Convergence Analysis Using Quadratic Constraints [8.336315962271396]
  Mirror descent (MD) is a powerful first-order optimization technique that subsumes several algorithms including gradient descent (GD) We study the exact convergence rate of MD in both centralized and distributed cases for strongly convex and smooth problems.
  arXiv  Detail & Related papers  (2021-05-29T23:05:56Z)
• Online mirror descent and dual averaging: keeping pace in the dynamic case [11.572321455920164]
  Online mirror descent (OMD) and dual averaging (DA) are fundamental algorithms for online convex optimization. We modify the OMD algorithm through a simple technique that we call stabilization. We show that OMD with stabilization and DA enjoy the same performance guarantees in many applications -- even under dynamic learning rates.
  arXiv  Detail & Related papers  (2020-06-03T23:41:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.