Skip to yearly menu bar Skip to main content


( events)   Timezone:  
Poster
Wed Dec 08 12:30 AM -- 02:00 AM (PST)
Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
Julien Grand-Clément · Christian Kroer
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.