EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914593061732352 |
|---|---|
| author | Maheshwari, Chinmay Pimpalkhare, Chinmay Chatterjee, Debasish |
| author_facet | Maheshwari, Chinmay Pimpalkhare, Chinmay Chatterjee, Debasish |
| contents | Min-max optimization arises in many domains such as game theory, adversarial machine learning, etc. For these problems, gradient-based methods are well understood and enjoy strong guarantees. However, in the absence of convexity or concavity, existing approaches study convergence to an approximate saddle point or first-order stationary points, which may be arbitrarily far from global optima. In this work, we present an algorithmic framework for computing the global minimax value in convex--non-concave and non-convex--concave min-max optimization. For convex--non-concave min-max problems, we use a reformulation that transforms the problem into a non-concave--convex max-min optimization problem with suitably defined feasible sets and objective function. This reformulation can be viewed as an extension of Sion's minimax theorem to the convex--non-concave setting. We then introduce EXOTIC -- an Exact, Optimistic, Tree-based algorithm for solving the reformulated max-min problem. EXOTIC combines an iterative convex optimization solver for the inner minimization with an optimistic hierarchical tree search for the outer maximization, inspired by StroquOOL~\cite{bartlett2019simple}. Unlike StroquOOL, which assumes stochastic zero-mean noisy evaluations, EXOTIC handles deterministic, biased, and budget-dependent evaluation errors arising from finite-time solutions of the inner convex subproblems. We establish an upper bound on its optimality gap. The same framework also applies to non-convex--concave min-max optimization. Empirically, EXOTIC outperforms gradient-based methods on popular benchmarks from the literature. Finally, we demonstrate the utility of EXOTIC by computing security strategies in multi-player games with three or more players -- a computationally challenging task that, to our knowledge, no prior method solves exactly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_12479 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization Maheshwari, Chinmay Pimpalkhare, Chinmay Chatterjee, Debasish Optimization and Control Artificial Intelligence Computer Science and Game Theory Multiagent Systems General Economics Economics 90C26, 90C47, 68Q32, 91A06, 65K05 Min-max optimization arises in many domains such as game theory, adversarial machine learning, etc. For these problems, gradient-based methods are well understood and enjoy strong guarantees. However, in the absence of convexity or concavity, existing approaches study convergence to an approximate saddle point or first-order stationary points, which may be arbitrarily far from global optima. In this work, we present an algorithmic framework for computing the global minimax value in convex--non-concave and non-convex--concave min-max optimization. For convex--non-concave min-max problems, we use a reformulation that transforms the problem into a non-concave--convex max-min optimization problem with suitably defined feasible sets and objective function. This reformulation can be viewed as an extension of Sion's minimax theorem to the convex--non-concave setting. We then introduce EXOTIC -- an Exact, Optimistic, Tree-based algorithm for solving the reformulated max-min problem. EXOTIC combines an iterative convex optimization solver for the inner minimization with an optimistic hierarchical tree search for the outer maximization, inspired by StroquOOL~\cite{bartlett2019simple}. Unlike StroquOOL, which assumes stochastic zero-mean noisy evaluations, EXOTIC handles deterministic, biased, and budget-dependent evaluation errors arising from finite-time solutions of the inner convex subproblems. We establish an upper bound on its optimality gap. The same framework also applies to non-convex--concave min-max optimization. Empirically, EXOTIC outperforms gradient-based methods on popular benchmarks from the literature. Finally, we demonstrate the utility of EXOTIC by computing security strategies in multi-player games with three or more players -- a computationally challenging task that, to our knowledge, no prior method solves exactly. |
| title | EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization |
| topic | Optimization and Control Artificial Intelligence Computer Science and Game Theory Multiagent Systems General Economics Economics 90C26, 90C47, 68Q32, 91A06, 65K05 |
| url | https://arxiv.org/abs/2508.12479 |