Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints

• URL: http://arxiv.org/abs/2609.13925v1
• Date: Sat, 12 Sep 2026 13:14:10 GMT
• Title: Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints
• Abstract summary: We study the stability and convergence of augmented primal-dual dynamics when constraint values are estimated from samples.<n>Unbiased constraint observations can produce a biased augmented multiplier signal, shifting the equilibria of the mean dynamics.
• Score: 8.980346173234201
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work studies the stability and convergence of augmented primal-dual dynamics when constraint values are estimated from samples. Unbiased constraint observations can produce a biased augmented multiplier signal, shifting the equilibria of the mean dynamics. For componentwise inequalities, we give a necessary and sufficient condition for preserving the Karush-Kuhn-Tucker (KKT) equilibria and construct a convex example with a locally exponentially stable equilibrium that violates complementarity. To address this bias, constraint values are estimated recursively before forming the augmented multiplier signal. For smooth convex conic problems, a joint energy analysis establishes boundedness of the primal, dual, and estimation states, vanishing estimation error, and almost sure convergence of the primal-dual iterates to a single KKT point under global regularity and bounded conditional second moments. The result allows nonunique solutions and multipliers while keeping the number of samples per iteration fixed. Numerical studies illustrate the predicted equilibrium bias and examine convergence with nonunique KKT points and nonlinear constraints.

Related papers

• Robust CHSH Self-Testing with Finite-Energy GKP States [42.71287663143178]
  We present a full-oscillator analysis of a finite-energy GKP CHSH test.<n>The observed score yields robust Bell-pair self-testing.
  arXiv  Detail & Related papers  (2026-08-11T16:33:28Z)
• Sample complexity of unbalanced entropic OT [19.649505951280137]
  This paper studies the sample complexity of entropic unbalanced OT at the level of the optimal coupling.<n>We develop a translation-invariant dual formulation, prove compactness and strong convexity properties for the intrinsic dual variables.<n>The results clarify why regularization is a practical necessity in machine learning applications.
  arXiv  Detail & Related papers  (2026-06-23T14:25:47Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Asymmetric regularization mechanism for GAN training with Variational Inequalities [1.529943343419486]
  We formulate the training of generative adversarial networks (GANs) as a Nash equilibrium seeking problem.<n>We propose an asymmetric regularization mechanism based on the classic Tikhonov step and on a novel zero-centered gradient penalty.
  arXiv  Detail & Related papers  (2026-01-20T12:50:18Z)
• From Tail Universality to Bernstein-von Mises: A Unified Statistical Theory of Semi-Implicit Variational Inference [0.12183405753834557]
  Semi-implicit variational inference (SIVI) constructs approximate posteriors of the form $q() = int k(| z) r(dz)$<n>This paper develops a unified "approximation-optimization-statistics'' theory for such families.
  arXiv  Detail & Related papers  (2025-12-05T19:26:25Z)
• Wasserstein Distributionally Robust Nash Equilibrium Seeking with Heterogeneous Data: A Lagrangian Approach [10.82417971001311]
  We study a class of distributionally robust games where agents are allowed to heterogeneously choose their risk aversion with respect to distributional shifts of the uncertainty.<n>We then formulate the distributionally robust Nash equilibrium problem and show that under certain assumptions it is equivalent to a finite-dimensional variational inequality problem with a strongly monotone mapping.
  arXiv  Detail & Related papers  (2025-11-18T01:56:33Z)
• Global Convergence of Over-parameterized Deep Equilibrium Models [52.65330015267245]
  A deep equilibrium model (DEQ) is implicitly defined through an equilibrium point of an infinite-depth weight-tied model with an input-injection. Instead of infinite computations, it solves an equilibrium point directly with root-finding and computes gradients with implicit differentiation. We propose a novel probabilistic framework to overcome the technical difficulty in the non-asymptotic analysis of infinite-depth weight-tied models.
  arXiv  Detail & Related papers  (2022-05-27T08:00:13Z)
• Simultaneous Transport Evolution for Minimax Equilibria on Measures [48.82838283786807]
  Min-max optimization problems arise in several key machine learning setups, including adversarial learning and generative modeling. In this work we focus instead in finding mixed equilibria, and consider the associated lifted problem in the space of probability measures. By adding entropic regularization, our main result establishes global convergence towards the global equilibrium.
  arXiv  Detail & Related papers  (2022-02-14T02:23:16Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  We significantly expand the understanding of last-rate uniqueness for Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) We show that when the equilibrium is unique, linear lastiterate convergence is achieved with a learning rate whose value is set to a universal constant. We show that bilinear games over any polytope satisfy this condition and OGDA converges exponentially fast even without the unique equilibrium assumption.
  arXiv  Detail & Related papers  (2020-06-16T20:53:04Z)

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.