Solving optimization problems with Blackwell approachability
We introduce the Conic Blackwell Algorithm (CBA) regret minimizer, a new parameter- and scale-free regret minimizer for general convex sets. CBA is based on Blackwell approachability and attains regret. We show how to efficiently instantiate CBA for many decision sets of interest, including the simplex, 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, which achieves a ergodic rate of convergence. In our simulations, we demonstrate the wide applicability of SP-CBA on several standard saddle-point problems, 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.