Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
| Autor: | Grand-Cl��ment, Julien, Kroer, Christian |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Computer Science::Computer Science and Game Theory Computer Science - Machine Learning Computer Science - Computer Science and Game Theory TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY MathematicsofComputing_NUMERICALANALYSIS Machine Learning (cs.LG) Computer Science and Game Theory (cs.GT) |
| Popis: | 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/\sqrt{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, $\ell_{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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|