Solving Optimization Problems with Blackwell Approachability.

In this paper, we propose a new algorithm for solving convex-concave saddle-point problems using regret minimization in the repeated game framework. To do so, we introduce the Conic Blackwell Algorithm⁺ (CBA+), a new parameter- and scale-free regret minimizer for general convex compact sets. CBA+ is based on Blackwell approachability and attains O(T) regret. We show how to efficiently instantiate CBA+ for many decision sets of interest, including the simplex, ℓp norm balls, and ellipsoidal confidence regions in the simplex. Based on CBA+ , we introduce SP-CBA+ , a new parameter-free algorithm for solving convex-concave saddle-point problems achieving a O(1/T) ergodic convergence rate. In our simulations, we demonstrate the wide applicability of SP-CBA+ on several standard saddle-point problems from the optimization and operations research literature, including matrix games, extensive-form games, distributionally robust logistic regression, and Markov decision processes. In each setting, SP-CBA+ achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters. Funding: J. Grand-Clément is supported by the Agence Nationale de la Recherche [Grant 11-LABX-0047] and by Hi! Paris. C. Kroer is supported by the Office of Naval Research [Grant N00014-22-1-2530] and by the National Science Foundation [Grant IIS-2147361]. [ABSTRACT FROM AUTHOR]