Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving

We develop new parameter-free and scale-free algorithms for solving convex-concave saddle-point problems. Our results are based on a new simple regret minimizer, the Conic Blackwell Algorithm^+ (CBA^+), which attains O(1/√T) average regret. Intuitively, our approach generalizes to other decision sets of interest ideas from the Counterfactual Regret minimization (CFR^+) algorithm, which has very strong practical performance for solving sequential games on simplexes. We show how to implement CBA^+ for the simplex, ℓp norm balls, and ellipsoidal confidence regions in the simplex, and we present numerical experiments for solving matrix games and distributionally robust optimization problems. Our empirical results show that CBA^+ is a simple algorithm that outperforms state-of-the-art methods on synthetic data and real data instances, without the need for any choice of step sizes or other algorithmic parameters.