Solving Optimization Problems with Blackwell Approachability

Julien Grand-Clément () and Christian Kroer ()
Additional contact information
Julien Grand-Clément: Department of Information Systems and Operations Management, École des Hautes Études Commerciales de Paris (HEC Paris), 78350 Jouy-en-Josas, France
Christian Kroer: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027

Mathematics of Operations Research, 2024, vol. 49, issue 2, 697-728

Abstract: 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 + ( CB A + ), a new parameter- and scale-free regret minimizer for general convex compact sets. CB A + is based on Blackwell approachability and attains O ( T ) regret. We show how to efficiently instantiate CB A + for many decision sets of interest, including the simplex, ℓ p norm balls, and ellipsoidal confidence regions in the simplex. Based on CB A + , we introduce SP-CB A + , 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-CB A + 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-CB A + achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters.

Keywords: Primary: 90C47; secondary: 90C25; Blackwell approachability; no-regret algorithm; parameter-free algorithm; saddle point (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.1376 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:2:p:697-728

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().