Alternating Mirror Descent for Constrained Min-Max Games
- URL: http://arxiv.org/abs/2206.04160v1
- Date: Wed, 8 Jun 2022 20:48:16 GMT
- Title: Alternating Mirror Descent for Constrained Min-Max Games
- Authors: Andre Wibisono and Molei Tao and Georgios Piliouras
- Abstract summary: We study two-player bilinear zero-sum games with constrained strategy spaces.
We analyze the alternating mirror descent algorithm, in which each player takes turns to take action following the mirror descent algorithm for constrained optimization.
- Score: 44.46086335474311
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we study two-player bilinear zero-sum games with constrained
strategy spaces. An instance of natural occurrences of such constraints is when
mixed strategies are used, which correspond to a probability simplex
constraint. We propose and analyze the alternating mirror descent algorithm, in
which each player takes turns to take action following the mirror descent
algorithm for constrained optimization. We interpret alternating mirror descent
as an alternating discretization of a skew-gradient flow in the dual space, and
use tools from convex optimization and modified energy function to establish an
$O(K^{-2/3})$ bound on its average regret after $K$ iterations. This
quantitatively verifies the algorithm's better behavior than the simultaneous
version of mirror descent algorithm, which is known to diverge and yields an
$O(K^{-1/2})$ average regret bound. In the special case of an unconstrained
setting, our results recover the behavior of alternating gradient descent
algorithm for zero-sum games which was studied in (Bailey et al., COLT 2020).
Related papers
- Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization [3.802030070947573]
We propose a zeroth-order mirror descent (ZO-SMD) algorithm available for both smooth and non-smooth MERO.
The proposed algorithm is proved to converge at optimal convergence rates of $mathcalOleft (1/sqrttright)$ on the estimate of $R_i*$ and $mathcalOleft (1/sqrttright)$ on the optimization error of both smooth and non-smooth MERO.
arXiv Detail & Related papers (2024-08-22T08:35:41Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
We study the Shortest Path (SSP) problem with a linear mixture transition kernel.
An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost.
Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
arXiv Detail & Related papers (2024-02-14T07:52:00Z) - Mirror Natural Evolution Strategies [10.495496415022064]
We focus on the theory of zeroth-order optimization which utilizes both the first-order and second-order information approximated by the zeroth-order queries.
We show that the estimated covariance matrix of textttMiNES converges to the inverse of Hessian matrix of the objective function.
arXiv Detail & Related papers (2023-08-01T11:45:24Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
We introduce two oblivious mirror descent algorithms based on a complementary composite setting.
Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function.
We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
arXiv Detail & Related papers (2023-06-30T08:34:29Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
This work studies problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth.
We consider two kinds of zero-order projected gradient descent algorithms.
arXiv Detail & Related papers (2023-06-03T17:05:13Z) - Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
Existing methods either require two gradient calls or two projections in each iteration, which may costly in some applications.
In this paper, we first show that a variant of the Optimistic Gradient (RGOG) has a rich set of non-comonrate min-max convergence rate problems.
Our convergence rates hold for standard measures such as and the natural and the natural.
arXiv Detail & Related papers (2022-10-06T17:50:42Z) - A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback [93.57603470949266]
We present a novel gradient estimator based on two function evaluation and randomization.
We consider two types of assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise.
We provide an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem.
arXiv Detail & Related papers (2022-05-27T11:23:57Z) - Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance [17.199063087458907]
We quantify the convergence rate of the Mirror Descent algorithm with a class of uniformly convex mirror maps.
This algorithm does not require any explicit gradient clipping or normalization.
We complement our results with information-theoretic lower bounds showing that no other algorithm using only first-order oracles can achieve improved rates.
arXiv Detail & Related papers (2022-02-23T17:08:40Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary.
Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
arXiv Detail & Related papers (2021-06-02T22:03:36Z) - Block majorization-minimization with diminishing radius for constrained
nonconvex optimization [9.907540661545328]
Block tensor regularization-minimization (BMM) is a simple iterative algorithm for non constrained optimization that minimizes major surrogates in each block.
We show that BMM can produce a gradient $O(epsilon-2(logepsilon-1)2)$ when convex surrogates are used.
arXiv Detail & Related papers (2020-12-07T07:53:09Z)
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.