2025/08/17 by Chinmay Maheshwari, Maheshwari, Chinmay, Chinmay Pimpalkhare +3
Computer Science · #65K05 #68Q32 #90C26 #90C47 #91A06 #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #FOS: Mathematics #General Economics (econ.GN) #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2508.12479
openalex publication_date 2025/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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~\citebartlett2019simple. 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.