Gradient Descent Ascent converges to von-Neumann solution in hidden zero-sum games.
problem Understanding dynamics of zero-sum games with hidden structure.
method Gradient Descent Ascent applied to hidden zero-sum games with specific convex-concave structure.
result Gradient Descent Ascent converges to von-Neumann solution in strictly convex-concave hidden games.
Efficiently minimizes regret in non-convex games with gradient-based methods.
problem Computational intractability of standard regret minimization in non-convex games.
method Defining a new notion of regret and using gradient-based optimization methods.
result Achieves optimal regret, leading to convergence to equilibrium.
New theorem guarantees approximate equilibrium in non-convex games.
problem No guarantee of equilibrium in non-convex games.
method Introduced a minimax theorem for non-convex games involving neural networks.
result Provided an approximate minimax theorem for non-convex games.
Gradient-descent-ascent dynamics can exhibit various behaviors in non-convex non-concave games.
problem Gradient-descent-ascent dynamics in non-convex non-concave games can lead to recurrent behavior and spurious equilibria.
method Combines optimization theory, game theory, and dynamical systems.
result Gradient-descent-ascent dynamics can exhibit Poincaré recurrence and converge to spurious equilibria.
We describe two nonconventional algorithms for linear regression, called GAME and CLASH. The salient characteristics of these approaches is that they exploit the convex ℓ1-ball and non-convex ℓ0-sparsity constraints jointly in sparse recovery. To establish the theoretical approximation guarantees of GAME an…
New algorithm solves non-convex, non-differentiable min-max games.
problem Limited theoretical understanding of non-smooth min-max games.
method Proximal gradient descent-ascent algorithm for convex-strongly convex games.
result Algorithm converges to ε-Nash equilibrium with polynomial gradient evaluations.
This work provides lower bounds for differentiable games and defines a new condition number.
problem Understanding the fundamental limits of convergence in differentiable games.
method The authors cast saddle-point and min-max problems as 2-player games and use tools from single-objective convex optimization to derive linear lower bounds for convex-concave games. They also introduce a new condition number for games.
result The authors provide linear lower bounds for differentiable games, including n-player games, and introduce a new condition number that captures the possibility of linear rates in games without strong convexity or concavity. The paper explains how simple methods can converge to optimal solutions in complex neural games.
problem Finding optimal solutions in neural games with non-convex objectives.
method Theoretical framework using hidden convexity and overparameterization, with path-length bounds and PŁ conditions.
result Simple gradient methods can converge to Nash equilibria in non-convex min-max games under certain conditions.
Paper studies how to combine regret minimizers for solving complex games.
problem Solving large-scale extensive-form games with constraints.
method Derives a calculus for constructing regret minimizers for composite convex sets.
result Local regret minimizers for simpler sets can be combined into an aggregate for composite sets.
Faster rates achieved for computing equilibria in convex-concave games.
problem Computing equilibria in convex-concave games efficiently.
method Optimistic prediction algorithms and no-regret techniques.
result Achieved O(1/T2) rate for equilibrium computation. This paper analyzes saddle points and minimax points in non-convex smooth games.
problem Understanding local optimal points in non-convex smooth games.
method Comprehensive analysis of local minimax points, including their optimality conditions and stability.
result Local saddle points are uniformly local minimax points under mild continuity assumptions.
Extended Blackwell approachability to quitting games, providing conditions for weak approachability.
problem Designing strategies for repeated games with quitting actions.
method Extending Blackwell approachability to generalized quitting games and providing geometric conditions.
result Characterization of weak approachability in quitting games, proving equivalence and full characterization.
This paper tackles global Nash equilibrium in non-convex multi-player games.
problem Challenges in finding global Nash equilibrium due to non-convexity.
method Conjugate transformation and variational inequality formulation to prove existence and design algorithms.
result Designs an ODE-based algorithm with exponential convergence rate and proves its effectiveness in practical scenarios.
Paper solves non-convex min-max games using gradient descent-ascent.
problem Solving saddle point games in non-convex settings.
method Iterative gradient descent-ascent algorithms for both players.
result First order stationary points found efficiently.
Paper provides convergence rates for rectifier convnets.
problem Understanding why rectifier networks perform well empirically.
method Introduces gated games to capture rectifier units' gating function.
result Gradient descent on rectifier convnets converges to a critical point.
The thesis explores prediction games with different opponents and moves, revealing intrinsic barriers and efficient algorithms.
problem Understanding and designing efficient algorithms for prediction games with various opponents and move orders.
method Geometric insights into three types of prediction games: general learning task, prediction with expert advice, and online convex optimization.
result Revealed intrinsic barriers and developed computationally efficient learning algorithms with strong theoretical guarantees.
OMWU shows last iterate convergence in convex-concave games.
problem Optimizing in constrained min-max optimization landscapes.
method OMWU (Optimistic Multiplicative-Weights Update) in the no-regret online learning framework.
result OMWU exhibits last iterate convergence for convex-concave games, generalizing previous results.
New model shows online and statistical learning are computationally equivalent with optimization oracle.
problem Online learning in non-convex games with adversarial settings.
method Strengthening the oracle model to make online and statistical learning computationally equivalent.
result Efficient computation of non-convex game equilibria, including GANs, with optimization oracle.
New method finds Nash equilibria faster in multiplayer games.
problem Finding Nash equilibria in multi-player games, especially in noisy environments.
method Extra-gradient with player sampling and variance reduction.
result Proves better convergence rate than full extra-gradient for noisy games.
Paper optimizes insurer's investment strategy in a fluctuating market with memory effects.
problem Optimizing insurer's investment in a market with regime switching and noisy memory.
method Formulated as a stochastic differential delay game, solved using BSDE approach.
result Derives analytical solutions for a specific case of a quadratic penalty function.
We use martingale and stochastic analysis techniques to study a continuous-time optimal stopping problem, in which the decision maker uses a dynamic convex risk measure to evaluate future rewards. We also find a saddle point for an equivalent zero-sum game of control and stopping, between an agent (the "stopper") who c…
Paper resolves ambiguity in non-convex bilevel optimization problems.
problem Ambiguity in bilevel optimization with non-convex lower-level objectives.
method Introduces selection maps to define critical points and resolves ambiguity.
result Validates new analytical tools in Morse theory for implicit differentiation.
Policy-gradient algorithms fail to converge to Nash equilibria in continuous state and action space games.
problem Policy-gradient algorithms lack convergence guarantees in multi-agent continuous state and action space games.
method Analysis of gradient-play in linear quadratic games, showing non-convexity and counterexamples.
result Policy-gradient algorithms can avoid Nash equilibria in certain continuous state and action space games.
Gradient methods converge exponentially in concave network games.
problem Finding Nash equilibria in concave network zero-sum games.
method Gradient Ascent and Optimistic Gradient Ascent analyses.
result Exponential convergence rates in various game settings.
A new game-theoretic approach tackles non-convex constrained optimization.
problem Non-convex constrained optimization with non-differentiable constraints.
method Proxy-Lagrangian formulation, two-player game approach.
result Classifier size is significantly reduced to m+1 models.
Improves bandit convex optimization with gradient variations.
problem Bandit Convex Optimization with Gradient Variations.
method Refined analysis of non-consecutive gradient variation.
result Improved dimension dependence for convex and strongly convex functions.
Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, O(T−1/2) accuracy. In approachability with full monitoring there are two types of conditions that are known to be equivalent for convex sets: a primal and a dual condition. The primal one is of the form: a set C is approachable if and only all containing half-spaces are approachable in the one-shot game; while the dual one is of the form…
Reward suffices for convex MDPs, expanding RL to new problems.
problem Capturing goals as convex functions of stationary distribution.
method Reformulated as a min-max game using Fenchel duality.
result Convex MDPs require non-stationary reward functions.
Paper analyzes GANs training difficulties and proposes a control framework.
problem Difficulties in training GANs, especially for financial time series.
method Stochastic control framework for hyper-parameters tuning.
result Explicit forms for optimal adaptive learning rate and batch size derived.
New approach to GANs using convex loss functions and kernel-based discriminators.
problem Minimizing the f-divergence between true and fake data distributions.
method Introducing a minimizing general loss viewpoint and using kernel-based discriminators.
result Maximizing the general loss is equivalent to the min-max problem in GAN.
New method accelerates smooth games using spectral shape analysis.
problem Accelerating optimization in smooth games with complex numerical challenges.
method Matrix iteration theory and spectral shape analysis to characterize and manipulate acceleration.
result Identified a continuum of optimization strategies from convex minimization to gradient descent.
Study analyzes portfolio liquidation games influenced by self-exciting order flow.
problem Analyzing portfolio liquidation strategies with market order dynamics.
method Mean-field control problem, novel FBSDE system, sufficient maximum principle.
result Existence and uniqueness of open-loop Nash equilibria proved.
This paper shows how to learn variational inequalities fast with strong monotonicity.
problem Learning variational inequalities efficiently.
method Extending convex optimization techniques to variational inequalities with strong monotonicity.
result Fast generalization rates of Θ(1/ε) for learning variational inequalities. APAC-Net solves high-dimensional stochastic MFGs using neural networks.
problem High-dimensional stochastic mean-field games.
method Alternating population and control neural networks, parameterizing value and density functions.
result Solves up to 100-dimensional MFG problems.
Proposes a new training algorithm for zero-sum games to avoid convergence issues.
problem Gradient-based training leads to weak convergence and cyclic dynamics in zero-sum architectures.
method Follow the perturbed leader algorithm with neural mediating agent.
result Guarantees convergence to mixed Nash equilibrium without cyclic behaviors.
Negative momentum accelerates convergence in minimax games but at a suboptimal rate.
problem The convergence rate of negative momentum in minimax games is suboptimal.
method Extending variational inequality formulation, connecting momentum method with Chebyshev polynomials.
result Negative momentum accelerates convergence locally but at a suboptimal rate.
New method improves convergence for smooth games.
problem Improving convergence for smooth games.
method Stochastic Hamiltonian Gradient Methods (SHGD).
result SHGD converges linearly to the neighbourhood of a stationary point.
New algorithm finds optimal sample complexity for pure exploration with multiple good answers.
problem Determining the optimal number of samples needed to explore multiple good answers in a bandit problem.
method Derive lower bound using game equilibrium, extend Track-and-Stop algorithm to multiple answers.
result New algorithm has asymptotic sample complexity matching the derived lower bound.
Calibrated strategies can be obtained by performing strategies that have no internal regret in some auxiliary game. Such strategies can be constructed explicitly with the use of Blackwell's approachability theorem, in an other auxiliary game. We establish the converse: a strategy that approaches a convex B-set can be…
Algorithmic traders optimize execution and arbitrage in markets with hidden information.
problem Optimal execution and statistical arbitrage in markets with latent factors.
method Solve a large stochastic game with mean-field game limit, using convex analysis and FBSDE.
result Prove the MFG equilibrium is an ε-Nash equilibrium for finite player games.
A new game-theoretic approach optimizes complex rate metrics.
problem Optimizing non-decomposable performance metrics and rate constraints.
method Extending two-player game approaches to a three-player game, seeking equilibrium.
result Generalizes and improves upon existing algorithms for constrained optimization.
Unified analysis of gradient-based methods for finding Nash equilibria in games.
problem Finding Nash equilibria in games using gradient-based methods.
method Unified analysis of extragradient (EG), optimistic gradient (OG), and consensus optimization (CO) methods.
result Unified convergence rates for EG, OG, and CO across different game types.
Study examines large banks' role in interbank markets using game theory.
problem Understanding systemic risk in interbank markets with large banks.
method Mean-field game framework, convex analysis, Monte Carlo simulations.
result Large banks can positively or negatively impact market stability.
Paper examines financial engineering problems and introduces AlphaZero for better replication strategies.
problem Replication portfolio construction in incomplete markets with non-convex constraints.
method Introduces AlphaZero-based system to compare with deep hedging method.
result AlphaZero outperforms deep hedging in non-convex environments, finding near-optimal strategies.
Gradient-based Nikaido-Isoda function helps find Nash equilibria efficiently.
problem Efficient computation of Nash equilibria in multi-player games.
method Gradient-based Nikaido-Isoda (GNI) function for computing first-order stationary points.
result Gradient descent converges sublinearly to a first-order stationary point of the GNI function.
A game-theoretic approach to multi-criteria ranking from ordinal data.
problem Ranking objects from ordinal data with multiple criteria.
method Generalizing von Neumann winner to multi-criteria setting using Blackwell's approachability.
result The Blackwell winner can be computed as a convex optimization problem and achieves near-optimal sample complexity.
Simple regret bound for online optimization with adversarial delays.
problem Online strongly-convex optimization with adversarial delays.
method Online Gradient Descent algorithm with a specific regret bound.
result Simple regret bound of \Oh{\sum_{t=1}^T \log (1+ \frac{d_t}{t})}