A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Gradient methods converge exponentially in concave network games.
Gradient Descent Ascent converges to von-Neumann solution in hidden zero-sum games.
New algorithm solves minimax games with linear constraints.
Recent successes of game-theoretic formulations in ML have caused a resurgence of research interest in differentiable games. Overwhelmingly, that research focuses on methods and upper bounds on their speed of convergence. In this work, we approach the question of fundamental iteration complexity by providing lower boun…
We study a wide class of non-convex non-concave min-max games that generalizes over standard bilinear zero-sum games. In this class, players control the inputs of a smooth function whose output is being applied to a bilinear zero-sum game. This class of games is motivated by the indirect nature of the competition in Ge…
Adversarial training, a special case of multi-objective optimization, is an increasingly prevalent machine learning technique: some of its most notable applications include GAN-based generative modeling and self-play techniques in reinforcement learning which have been applied to complex games such as Go or Poker. In p…
We consider the use of no-regret algorithms to compute equilibria for particular classes of convex-concave games. While standard regret bounds would lead to convergence rates on the order of , recent work \citep{RS13,SALS15} has established rates by taking advantage of a particular class of optimi…
We study the problem of super-replication for game options under proportional transaction costs. We consider a multidimensional continuous time model, in which the discounted stock price process satisfies the conditional full support property. We show that the super-replication price is the cheapest cost of a trivial s…
The paper explains how simple methods can converge to optimal solutions in complex neural games.
In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of \t…
Recent applications that arise in machine learning have surged significant interest in solving min-max saddle point games. This problem has been extensively studied in the convex-concave regime for which a global equilibrium solution can be computed efficiently. In this paper, we study the problem in the non-convex reg…
In this paper we extend the setting of the online prediction with expert advice to function-valued forecasts. At each step of the online game several experts predict a function, and the learner has to efficiently aggregate these functional forecasts into a single forecast. We adapt basic mixable (and exponentially conc…
New algorithm AG-OG optimizes separable convex-concave problems efficiently.
Negative momentum accelerates convergence in minimax games but at a suboptimal rate.
PAPAL algorithm finds mixed Nash equilibria in continuous games.
New method improves convergence for smooth games.
Last-iterate guarantees for learning in co-coercive games under noisy feedback.
In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the…
New algorithm solves non-convex, non-differentiable min-max games.
This paper concerns the recursive utility maximization problem under partial information. We first transform our problem under partial information into the one under full information. When the generator of the recursive utility is concave, we adopt the variational formulation of the recursive utility which leads to a s…
This work finds mixed equilibria in machine learning problems using measures and simultaneous gradient ascent-descent.
Study on convergence of Langevin dynamics for zero-sum games in probability distributions.
We present APAC-Net, an alternating population and agent control neural network for solving stochastic mean field games (MFGs). Our algorithm is geared toward high-dimensional instances of MFGs that are beyond reach with existing solution methods. We achieve this in two steps. First, we take advantage of the underlying…
Improved FTPL algorithm reduces regret in predictable minimax games.
New algorithm improves self-play reinforcement learning for competitive games.
Investigates probability of error in structured thresholding bandit problems.
Convergence to a saddle point for convex-concave functions has been studied for decades, while recent years has seen a surge of interest in non-convex (zero-sum) smooth games, motivated by their recent wide applications. It remains an intriguing research challenge how local optimal points are defined and which algorith…
Many problems in machine learning and game theory can be formulated as saddle-point problems, for which various first-order methods have been developed and proven efficient in practice. Under the general convex-concave assumption, most first-order methods only guarantee an ergodic convergence rate, that is, the uniform…
New algorithm solves min-max optimization problems in a decentralized manner.
Near-logarithmic regret per switch achieved for mixable/exp-concave losses.
This paper studies two important signal processing aspects of equilibrium behavior in non-cooperative games arising in social networks, namely, reinforcement learning and detection of equilibrium play. The first part of the paper presents a reinforcement learning (adaptive filtering) algorithm that facilitates learning…
New algorithms solve nonconvex-nonconcave minimax optimization problems.
Researchers develop methods to recover agent behavior from sparse data using Gaussian processes.
Paper studies convergence of Mean-Field GDA dynamics for MNE of continuous games.
We solve a continuous-time game-theoretic problem for Kihlstrom-Mirman preferences.
Alt-GDA outperforms Sim-GDA in minimax games with near-optimal local convergence.
Prompted by a recent experiment by Victor Haghani and Richard Dewey, this note generalises the Kelly strategy (optimal for simple investment games with log utility) to a large class of practical utility functions and including the effect of extraneous wealth. A counterintuitive result is proved : for any continuous, co…
We extend the Frank-Wolfe (FW) optimization algorithm to solve constrained smooth convex-concave saddle point (SP) problems. Remarkably, the method only requires access to linear minimization oracles. Leveraging recent advances in FW optimization, we provide the first proof of convergence of a FW-type saddle point solv…
We propose a computationally efficient random walk on a convex body which rapidly mixes and closely tracks a time-varying log-concave distribution. We develop general theoretical guarantees on the required number of steps; this number can be calculated on the fly according to the distance from and the shape of the next…
Improved convergence rates for saddle-point optimization algorithms.
New algorithms reduce variance in solving complex mathematical problems.
Algorithm identifies correct hypothesis from alternatives in bandit problems.
Despite remarkable empirical success, the training dynamics of generative adversarial networks (GAN), which involves solving a minimax game using stochastic gradients, is still poorly understood. In this work, we analyze last-iterate convergence of simultaneous gradient descent (simGD) and its variants under the assump…
Paper tackles robust online learning with worst-case distributions.
New method achieves both universality and adaptivity in online convex optimization.
The paper establishes conditions for strict power concavity in convolutions.
The paper develops a new algorithm for constructing minimax estimators using online learning techniques.
Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al \cite{DISZ17} and follow-up work of Liang and Stokes \cite{LiangS18} have established that a variant of the widely used Gradient Descent/Ascent procedure, called "Optimistic Gradient Descent/Asce…