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

Abstract:
We develop new parameter-free and scale-free algorithms for solving convexconcave 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-ofthe-art methods on synthetic data and real data instances, without the need for any choice of step sizes or other algorithmic parameters.

text: √ 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-ofthe-art methods on synthetic data and real data instances, without the need for any choice of step sizes or other algorithmic parameters.

heading: 1 Introduction
text: We are interested in solving saddle-point problems (SPPs) of the form
min x∈X max y∈Y F (x,y), (1)
whereX ⊂ Rn,Y ⊂ Rm are convex, compact sets, and F : X×Y → R is a subdifferentiable convexconcave function. Convex-concave SPPs arise in a number of practical problems. For example, the problem of computing a Nash equilibrium of a zero-sum game can be formulated as a convex-concave SPP, and this is the foundation of most methods for solving sequential zero-sum games [vS96, ZJBP07, TBJB15, KWKKS20]. They also arise in imaging [CP11], `∞-regression [ST18], Markov Decision Processes [Iye05, WKR13, ST18], and in distributionally robust optimization, where the max term represents the distributional uncertainty [ND16, BTHKM15]. In this paper we propose efficient, parameter-free algorithms for solving (1) in many settings, i.e., algorithms that do not require any tuning or choices of step sizes.
Repeated game framework One way to solve convex-concave SPPs is by viewing the SPP as a repeated game between two players, where each step t consists of one player choosing xt ∈ X , the other player choosing yt ∈ Y , and then the players observe the payoff F (xt,yt). If each player employs a regret-minimization algorithm, then a well-known folk theorem says that the uniform average strategy generated by two regret minimizers repeatedly playing an SPP against each other converges to a solution to the SPP. We will call this the “repeated game framework” (see Section 2). There are already well-known algorithms for instantiating the above repeated game framework
∗Julien Grand-Clément acknowledges the financial support of Hi! Paris for this project.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for (1). For example, one can employ the online mirror descent (OMD) algorithm, which generates iterates as follows for the first player (and similarly for the second player):
xt+1 = arg min x∈X
〈ηft,x〉+D(x‖xt), (2)
where ft ∈ ∂xF (xt,yt) (∂x denotes here the set of subgradients as regards the variable x), D(·‖·) is a Bregman divergence which measures distance between pairs of points, and η > 0 is an appropriate step size. By choosing D appropriately for X , the update step (2) becomes efficient, and one can achieve an overall regret on the order of O( √ T ) after T iterations. This regret can be achieved either by choosing a fixed step size η = α/L √ T , where L is an upper bound on the norms of the subgradients visited (ft)t≥0, or by choosing adaptive step sizes ηt = α/ √ t, for α > 0. This is problematic, as 1) the upper bound L may be hard to obtain in many applications and may be too conservative in practice, and 2) adequately tuning the parameter α can be time- and resourceconsuming, and even practically infeasible for very large instances, since we won’t know if the step size will cause a slow convergence or a divergence until late in the optimization process. This is not just a theoretical issue, as we highlight in our numerical experiments (Section 4) and in the appendices (Appendices F). Similar results and challenges hold for the popular follow the regularized leader (FTRL) algorithm (see Appendix F).
The above issues can be circumvented by employing adaptive variants of OMD or FTRL, which lead to parameter- and scale-free algorithms that estimate the parameters through the observed subgradients, e.g., AdaHedge for the simplex setting [DRVEGK14] or AdaFTRL for general compact convex decisions sets [OP15]. Yet these adaptive variants have not seen practical adoption in largesale game-solving, where regret-matching variants are preferred (see the next paragraph). As we show in our experiments, adaptive variants of OMD and FTRL perform much worse than our proposed algorithms. While these adaptive algorithms are referred to as parameter-free, this is only true in the sense that they are able to learn the necessary parameters. Our algorithm is parameter-free in the stronger sense that there are no parameters that even require learning. Formalizing this difference may be one interesting avenue for explaining the performance discrepancy on saddle-point problems.
Regret Matching In this paper, we introduce alternative regret-minimization schemes for instantiating the above framework. Our work is motivated by recent advances on solving large-scale zero-sum sequential games. In the zero-sum sequential game setting, X and Y are simplexes, the objective function becomes F (x,y) = 〈x,Ay〉, and thus (1) reduces to a bilinear SPP. Based on this bilinear SPP formulation, the best practical methods for solving large-scale sequential games use the repeated game framework, where each player minimizes regret via some variant of counterfactual regret minimization (CFR, [ZJBP07]). Variants of CFR were used in every recent poker AI challenge, where poker AIs beat human poker players [BBJT15, MSB+17, BS18, BS19]. The CFR framework itself is a decomposition of the overall regret of the bilinear SPP into local regrets at each decision point in a sequential game [FKS19a]. The key to the practical performance of CFR-based algorithms seems to be three ingredients (beyond the CFR decomposition itself): (1) a particular regret minimizer called regret matching+ (RM+) [TBJB15] which is employed at each decision point, (2) aggressive iterate averaging schemes that put greater weight on recent iterates (e.g. linear averaging, which weights iterate at period t by 2t/T (T + 1)), and (3) an alternation scheme where the updates of the repeated game framework are performed in an asymmetric fashion. The CFR framework itself is specific to sequential bilinear games on simplexes, but these last three ingredients could potentially be generalized to other problems of the form (1). That is the starting point of the present paper.
The most challenging aspect of generalizing the above ingredients is that RM+ is specifically designed for minimizing regret over a simplex. However, many problems of the form (1) have convex sets X ,Y that are not simplexes, e.g., box constraints or norm-balls for distributionally robust optimization [BTHKM15]. In principle, regret matching arises from a general theory called Blackwell approachability [Bla56, HMC00], and similar constructions can be envisioned for other convex sets. However, in practice the literature has only focused on developing concrete implementable instantiations of Blackwell approachability for simplexes. A notable deviation from this is the work of [ABH11], who showed a general reduction between regret minimization over general convex compact sets and Blackwell approachability. However, their general reduction still does not yield a practically implementable algorithm: among other things, their reduction relies on certain black-box projections that are not always efficient. We show how to implement these necessary projections for the setting where X and Y are simplexes, `p balls, and intersections of the `2 ball with a hyperplane
(with a focus on the case where an `2 ball is intersected with a simplex, which arises naturally as a confidence region). This yields an algorithm which we will refer to as the conic Blackwell algorithm (CBA), which is similar in spirit to the regret matching algorithm, but crucially generalizes to other decision sets. Motivated by the practical performance of RM+, we construct a variant of CBA which uses a thresholding operation similar to the one employed by RM+. We call this algorithm CBA+.
Our contributions We introduce CBA+, a parameter-free algorithm which achieves O( √ T ) regret in the worst-case and generalizes the strong performances of RM+ for bilinear, simplex saddle-points solving to other more general settings. A major selling point for CBA+ is that it does not require any step size choices. Instead, the algorithm implicitly adjusts to the structure of the domains and losses by being instantiations of Blackwell’s approachability algorithm. After developing the CBA+ algorithm, we then develop analogues of another crucial components for large-scale game solving. In particular, we prove a generalization of the folk theorem for the repeated game framework for solving (1), which allows us to incorporate polynomial averaging schemes such as linear averaging. We then show that CBA+ is compatible with linear averaging on the iterates. This mirrors the case of RM and RM+, where only RM+ is compatible with linear averaging on the iterates. We also show that both CBA and CBA+ are compatible with polynomial averaging when simultaneously performed on the regrets and the iterates. Combining all these ingredients, we arrive at a new class of algorithms for solving convex-concave SPPs. As long as efficient projection operations can be performed (which we show for several practical domains, including the simplex, `p balls and confidence regions in the simplex), one can apply the repeated game framework on (1), where one can use either CBA or CBA+ as a regret minimizer for X and Y along with polynomial averaging on the generated iterates to solve (1) at a rate of O ( 1/ √ T ) .
We highlight the practical efficacy of our algorithmic framework on several domains. First, we solve two-player zero-sum matrix games and extensive-form games, where RM+ regret minimizer combined with linear averaging and alternation, and CFR+, lead to very strong practical algorithms [TBJB15]. We find that CBA+ combined with linear averaging and alternation leads to a comparable performance in terms of the iteration complexity, and may even slightly outperform RM+ and CFR+. On this simplex setting, we also find that CBA+ outperforms both AdaHedge and AdaFTRL. Second, we apply our approach to a setting where RM+ and CFR+ do not apply: distributionally robust empirical risk minimization (DR-ERM) problems. Across two classes of synthetic problems and four real data sets, we find that our algorithm based on CBA+ performs orders of magnitude better than online mirror descent and FTRL, as well as their optimistic variants, when using their theoretically-correct fixed step sizes. Even when considering adaptive step sizes, or fixed step sizes that are up to 10, 000 larger than those predicted by theory, our CBA+ algorithm performs better, with only a few cases of comparable performance (at step sizes that lead to divergence for some of the other non parameter-free methods). The fast practical performance of our algorithm, combined with its simplicity and the total lack of step sizes or parameters tuning, suggests that it should be seriously considered as a practical approach for solving convex-concave SPPs in various settings.
Finally, we make a brief note on accelerated methods. Our algorithms have a rate of convergence towards a saddle point of O(1/ √ T ), similar to OMD and FTRL. In theory, it is possible to obtain a faster O (1/T ) rate of convergence when F is differentiable with Lipschitz gradients, for example via mirror prox [Nem04] or other primal-dual algorithms [CP16]. However, our experimental results show that CBA+ is faster than optimistic variants of FTRL and OMD [SALS15], the latter being almost identical to the mirror prox algorithm, and both achieving O(1/T ) rate of convergence. A similar conclusion has been drawn in the context of sequential game solving, where the fastest O(1/ √ T ) CFR-based algorithms have better practical performance than the theoretically-superior O (1/T )-rate methods [KWKKS20, KFS18]. In a similar vein, using error-bound conditions, it is possible to achieve a linear rate, e.g., when solving bilinear saddle-point problems over polyhedral decision sets using the extragradient method [Tse95] or optimistic gradient descent-ascent [WLZL20]. However, these linear rates rely on unknown constants, and may not be indicative of practical performance.

heading: 2 Game setup and Blackwell Approachability
text: As stated in Section 1, we will solve (1) using a repeated game framework. The first player chooses strategies from X in order to minimize the sequence of payoffs in the repeated game, while the second player chooses strategies from Y in order to maximize payoffs. There are T iterations with indices t = 1, . . . , T . In this framework, each iteration t consists of the following steps:
1. Each player chooses strategies xt ∈ X ,yt ∈ Y 2. First player observes ft ∈ ∂xF (xt,yt) and uses ft when computing the next strategy 3. Second player observes gt ∈ ∂yF (xt,yt) and uses gt when computing the next strategy
The goal of each player is to minimize their regret RT,x, RT,y across the T iterations:
RT,x = T∑ t=1 〈ft,xt〉 − min x∈X T∑ t=1 〈ft,x〉, RT,y = max y∈Y T∑ t=1 〈gt,y〉 − T∑ t=1 〈gt,yt〉.
The reason this repeated game framework leads to a solution to the SPP problem (1) is the following folk theorem. Relying on F being convex-concave and subdifferentiable, it connects the regret incurred by each player to the duality gap in (1).
Theorem 2.1 (Theorem 1, [Kro20]). Let (x̄T , ȳT ) = 1
T
∑T t=1 (xt,yt) for any (xt)t≥1 , (yt)t≥1.
Then max y∈Y F (x̄T ,y)− min x∈X F (x, ȳT ) ≤ (RT,x +RT,y)/T.
Therefore, when each player runs a regret minimizer that guarantees regret on the order of O( √ T ), (x̄T , ȳT )T≥0 converges to a solution to (1) at a rate of O ( 1/ √ T )
. Later we will show a generalization of Theorem 2.1 that will allow us to incorporate more aggressive averaging schemes that put additional weight on the later iterates. Given the repeated game framework, the next question becomes which algorithms to employ in order to minimize regret for each player. As mentioned in Section 1, for zero-sum games, variants of regret matching are used in practice.
Blackwell Approachability Regret matching arises from the Blackwell approachability framework [Bla56]. In Blackwell approachability, a decision maker repeatedly takes decisions xt from some convex decision set X (this set plays the same role as X or Y in (1)). After taking decision xt the player observes a vector-valued affine payoff function ut(x) ∈ Rn. The goal for the decision maker is to force the average payoff 1t ∑t τ=1 uτ (xτ ) to approach some convex target S. Blackwell proved that a convex target set S can be approached if and only if for every halfspaceH ⊇ S , there exists x ∈ X such that for every possible payoff function u(·), u(x) is guaranteed to lie inH. The action x is said to forceH. Blackwell’s proof is via an algorithm: at iteration t, his algorithm projects the average payoff ū = 1t−1 ∑t−1 τ=1 uτ (xτ ) onto S, and then the decision maker chooses an action xt that forces the tangent halfspace to S generated by the normal ū− πS(ū), where πS(ū) is the orthogonal projection of ū onto S . We call this algorithm Blackwell’s algorithm; it approaches S at a rate of O(1/ √ T ). It is important to note here that Blackwell’s algorithm is rather a meta-algorithm than a concrete algorithm. Even within the context of Blackwell’s approachability problem, one needs to devise a way to compute the forcing actions needed at each iteration, i.e., to compute πS(ū).
Details on Regret Matching Regret matching arises by instantiating Blackwell approachability with the decision space X equal to the simplex ∆(n), the target set S equal to the nonpositive orthant Rn−, and the vector-valued payoff function ut(xt) = ft − 〈ft,xt〉e equal to the regret associated to each of the n actions (which correspond to the corners of ∆(n)). Here e ∈ Rn has one on every component. [HMC00] showed that with this setup, playing each action with probability proportional to its positive regret up to time t satisfies the forcing condition needed in Blackwell’s algorithm. Formally, regret matching (RM) keeps a running sum rt = ∑t τ=1 (fτ − 〈fτ ,xτ 〉e),
and then action i is played with probability xt+1,i = [rt,i]+/ ∑n i=1[rt,i]
+, where [·]+ denotes thresholding at zero. By Blackwell’s approachability theorem, this algorithm converges to zero average regret at a rate of O(1/ √ T ). In zero-sum game-solving, it was discovered that a variant of
regret matching leads to extremely strong practical performance (but the same theoretical rate of convergence). In regret matching+ (RM+), the running sum is thresholded at zero at every iteration: rt = [rt−1 + ft − 〈ft,xt〉e]+, and then actions are again played proportional to rt. In the next section, we describe a more general class of regret-minimization algorithms based on Blackwell’s algorithm for general sets X , introduced in [ABH11]. Note that a similar construction of a general class of algorithms can be achieved through the Lagrangian Hedging framework of [Gor07]. It would be interesting to construct a CBA+-like algorithm and efficient projection approaches for this framework as well.

heading: 3 Conic Blackwell Algorithm
text: We present the Conic Blackwell Algorithm Plus (CBA+), a no-regret algorithm which uses a variation of Blackwell’s approachability procedure [Bla56] to perform regret minimization on general convex compact decision sets X . We will assume that losses are coming from a bounded set; this occurs, for example, if there exists Lx, Ly (that we do not need to know), such that
‖f‖ ≤ Lx, ‖g‖ ≤ Ly, ∀ x ∈ X ,y ∈ Y,∀ f ∈ ∂xF (x,y),∀ g ∈ ∂yF (x,y). (3)
CBA+ is best understood as a combination of two steps. The first is the basic CBA algorithm, derived from Blackwell’s algorithm, which we describe next. To convert Blackwell’s algorithm to a regret minimizer on X , we use the reduction from [ABH11], which considers the conic hull C = cone({κ} × X ) where κ = maxx∈X ‖x‖2. The Blackwell approachability problem is then instantiated with X as the decision set, target set equal to the polar C◦ = {z : 〈z, ẑ〉 ≤ 0,∀ẑ ∈ C} of C, and payoff vectors (〈ft,xt〉,−ft). The conic Blackwell algorithm (CBA) is implemented by projecting the average payoff vector onto C, calling this projection α(κ,x) with α ≥ 0 and x ∈ X , and playing the action x.
The second step in CBA+ is to modify CBA to make it analogous to RM+ rather than to RM. To do this, the algorithm does not keep track of the average payoff vector. Instead, we keep a running aggregation of the payoffs, where we always add the newest payoff to the aggregate, and then project the aggregate onto C. More concretely, pseudocode for CBA+ is given in Algorithm 1. This pseudocode relies on two functions: CHOOSEDECISIONCBA+ : Rn+1 → Rn, which maps the aggregate payoff vector ut to a decision in X , and UPDATEPAYOFFCBA+ which controls how we aggregate payoffs. Given an aggregate payoff vector u = (ũ, û) ∈ R× Rn, we have
CHOOSEDECISIONCBA+(u) = (κ/ũ)û.
If ũ = 0, we just let CHOOSEDECISIONCBA+(u) = x0 for some chosen x0 ∈ X . The function UPDATEPAYOFFCBA+ is implemented by adding the most recent payoff to the aggregate payoffs, and then projecting onto C. More formally, it is defined as
UPDATEPAYOFFCBA+(u,x,f , ω, S) = πC
( S
S + ω u+
ω
S + ω (〈f ,x〉/κ,−f)
) ,
where ω is the weight assigned to the most recent payoff and S the weight assigned to the previous aggregate payoff u. Because of the projection step in UPDATEPAYOFFCBA+ , we always have u ∈ C, which in turn guarantees that CHOOSEDECISIONCBA+(u) ∈ X , since C = cone({κ} × X ). Let us give some intuition on the effect of projection onto C. In a geometric sense, it is easier to visualize things in R2 with C = R2+ and C◦ = R2−. The projection on C moves the vector along the edges of C◦, maintaining the distance to C◦ and moving toward the vector 0. This is illustrated in
Figure 5 in Appendix B.1. From a game-theoretic standpoint, the projection on C = R2+ eliminates the components of the payoffs that are negative. It enables CBA+ to be less pessimistic than CBA, which may accumulate negative payoffs on actions for a long time and never resets the components of the aggregated payoff to 0, leading to some actions being chosen less frequently.
We will see in the next section that RM+ is related to CBA+ but replaces the exact projection step πC(u) in UPDATEPAYOFFCBA+ by a suboptimal solution to the projection problem. Let us also note the difference between CBA+ and the algorithm introduced in [ABH11], which we have called
Algorithm 1 Conic Blackwell Algorithm Plus (CBA+) 1: Input A convex, compact set X ⊂ Rn, κ = max{‖x‖2 | x ∈ X}. 2: Algorithm parameters Weights (ωτ )τ≥1 ∈ RN. 3: Initialization t = 1, x1 ∈ X . 4: Observe f1 then set u1 = (〈f1,x1〉/κ,−f1) ∈ R× Rn. 5: for t ≥ 1 do 6: Choose xt+1 = CHOOSEDECISIONCBA+(ut). 7: Observe the loss ft+1 ∈ Rn. 8: Update ut+1 = UPDATEPAYOFFCBA+(ut,xt+1,ft+1, ωt+1, ∑t τ=1 ωτ ).
9: Increment t← t+ 1.
CBA. CBA uses different UPDATEPAYOFF and CHOOSEDECISION functions. In CBA the payoff update is defined as
UPDATEPAYOFFCBA(u,x,f , ω, S) = S
S + ω u+
ω
S + ω (〈f ,x〉/κ,−f) .
Note in particular the lack of projection as compared to CBA+, analogous to the difference between RM and RM+. The CHOOSEDECISIONCBA function then requires a projection onto C:
CHOOSEDECISIONCBA(u) = CHOOSEDECISIONCBA+ (πC(u)) .
Based upon the analysis in [Bla56], [ABH11] show that CBA with uniform weights (both on payoffs and decisions) guarantees O(1/ √ T ) average regret. The difference between CBA+ and CBA is similar to the difference between the RM and RM+ algorithms. In practice, RM+ performs significantly better than RM for solving matrix games, when combined with linear averaging on the decisions (as opposed to the uniform averaging used in Theorem 2.1). In the next theorem, we show that CBA+ is compatible with linear averaging on decisions only. We present a detailed proof in Appendix B. Theorem 3.1. Consider (xt)t≥0 generated by CBA
+ with uniform weights: ωτ = 1,∀ τ ≥ 1. Let L = max{‖ft‖2 | t ≥ 1} and κ = max{‖x‖2 | x ∈ X}. Then∑T
t=1 t〈ft,xt〉 −minx∈X ∑T t=1 t〈ft,x〉
T (T + 1) = O
( κL/ √ T ) .
Note that in Theorem 3.1, we have uniform weights on the sequence of payoffs (ut)t≥0, but linearly increasing weights on the sequence of decisions. The proof relies on properties specific to CBA+, and it does not extend to CBA. Numerically it also helps CBA+ but not CBA. In Appendix B, we show that both CBA and CBA+ achieve O ( κL/ √ T )
convergence rates when using a weighted average on both the decisions and the payoffs (Theorems B.2-B.3). In practice, using linear averaging only on the decisions, as in Theorem 3.1, performs vastly better than linear averaging on both decisions and payoffs. We present empirical evidence of this in Appendix B.
We can compare the O ( κL/ √ T ) average regret for CBA+ with the O ( ΩL/ √ T )
average regret for OMD [NY83, BTN01] and FTRL [AHR09, McM11], where Ω = max{‖x− x′‖2|x,x′ ∈ X}. We can always recenter X to contain 0, in which case the bounds for OMD/FTRL and CBA+ are equivalent since κ ≤ Ω ≤ 2κ. Note that the bound on the average regret for Optimistic OMD (O-OMD, [CYL+12]) and Optimistic FTRL (O-FTRL, [RS13]) is O ( Ω2L/T ) in the game setup, a priori better than the bound for CBA+ as regards the number of iterations T . Nonetheless, we will see in Section 4 that the empirical performance of CBA+ is better than that of O(1/T ) methods. A similar situation occurs for RM+ compared to O-OMD and O-FTRL for solving poker games [FKS19b, KWKKS20].
The following theorem gives the convergence rate of CBA+ for solving saddle-points (1), based on our convergence rate on the regret of each player (Theorem 3.1). The proof is in Appendix C.
Theorem 3.2. Let (x̄T , ȳT ) = 2 ∑T t=1 t (xt,yt) /(T (T+1)),where (xt)t≥0 , (yt)t≥0 are generated by the repeated game framework with CBA+ with uniform weights: ωτ = 1,∀ τ ≥ 1. Let L = max{Lx, Ly} defined in (3) and κ = max{max{‖x‖2, ‖y‖2} | x ∈ X ,y ∈ Y}. Then
max y∈Y F (x̄T ,y)− min x∈X
F (x, ȳT ) = O ( κL/ √ T ) .
3.1 Efficient implementations of CBA+
To obtain an implementation of CBA+ and CBA, we need to efficiently resolve the functions CHOOSEDECISIONCBA+ and UPDATEPAYOFFCBA+ . In particular, we need to compute πC(u), the orthogonal projection of u onto the cone C, where C = cone({κ} × X ):
πC(u) ∈ arg min y∈C ‖y − u‖22. (4)
Even for CBA this problem must be resolved, since [ABH11] did not study whether (4) can be efficiently solved. It turns out that (4) can be computed in closed-form or quasi closed-form for many decision sets X of interest. Interestingly, parts of the proofs rely on Moreau’s Decomposition Theorem [CR13], which states that πC(u) can be recovered from πC◦(u) and vice-versa, because πC(u) + πC◦(u) = u. We present the detailed complexity results and the proofs in Appendix D.
Simplex X = ∆(n) is the classical setting used for matrix games. Also, for extensive-form games, CFR decomposes the decision sets (treeplexes) into a set of regret minimization problems over the simplex [FKS19a]. Here, n is the number of actions of a player and x ∈ ∆(n) represents a randomized strategy. In this case, πC(u) can be computed in O(n log(n)). Note that RM and RM+ are obtained by choosing a suboptimal solution to (4), avoiding the O(n log(n)) sorting operation, whereas CBA and CBA+ choose optimally (see Appendix D). Thus, RM and RM+ can be seen as approximate versions of CBA and CBA+, where (4) is solved approximatively at every iteration. In our numerical experiments, we will see that CBA+ slightly outperforms RM+ and CFR+ in terms of iteration count.
`p balls This is when X = {x ∈ Rn | ; ‖x‖p ≤ 1} with p ≥ 1 or p = ∞. This is of interest for instance in distributionally robust optimization [BTHKM15, ND16], `∞ regression [ST18] and saddle-point reformulation of Markov Decision Process [JS20]. For p = 2, we can compute πC(u) in closed-form, i.e., in O(n) arithmetic operations. For p ∈ {1,∞}, we can compute πC(u) in O(n log(n)) arithmetic operations using a sorting algorithm.
Ellipsoidal confidence region in the simplex Here, X is an ellipsoidal subregion of the simplex, defined as X = {x ∈ ∆(n) | ‖x − x0‖2 ≤ x}. This type of decision set is widely used because it is associated with confidence regions when estimating a probability distribution from observed data [Iye05, BdHP19]. It can also be used in the Bellman update for robust Markov Decision Process [Iye05, WKR13, GGC18]. We also assume that the confidence region is “entirely contained in the simplex”: {x ∈ Rn|x>e = 1}⋂{x ∈ Rn | ‖x − x0‖2 ≤ x} ⊆ ∆(n), to avoid degenerate components. In this case, using a change of basis we show that it is possible to compute πC(u) in closed-form, i.e., in O(n) arithmetic operations.
Other potential sets of interests Other important decision sets include sets based on Kullback-Leibler divergence {x ∈ ∆(n) | KL (x,x0) ≤ x}, or, more generally, φdivergence [BTDHDW+13]. For these sets, we did not find a closed-form solution to the projection problem (4). Still, as long as the domain X is a convex set, computing πC(u) remains a convex problem, and it can be solved efficiently with solvers, although this results in a slower algorithm than with closed-form computations of πC(u).

heading: 4 Numerical experiments
text: In this section we investigate the practical performances of our algorithms on several instances of saddle-point problems. We start by comparing CBA+ with RM+ in the matrix and extensive-form games setting. We then turn to comparing our algorithms on instances from the distributionally robust optimization literature. The code for all experiments is available in the supplemental material.

heading: 4.1 Matrix games on the simplex and Extensive-Form Games
text: Since the motivation for CBA+ is to obtain the strong empirical performances of RM+ and CFR+ on other decision sets than the simplex, we start by checking that CBA+ indeed provides comparable
performance on simplex settings. We compare these methods on matrix games
min x∈∆(n) max y∈∆(m)
〈x,Ay〉,
where A is the matrix of payoff, and on extensive-form games (EFGs). EFGs can also be written as SPPs with bilinear objective and X ,Y polytopes encoding the players’ space of sequential strategies [vS96]. EFGs can be solved via simplex-based regret minimization by using the counterfactual regret minimization (CFR) framework to decompose regrets into local regrets at each simplex. Explaining CFR is beyond the scope of this work; we point the reader to [ZJBP07] or newer explanations [FKS19c, FKS19a]. For matrix games, we generate 70 synthetic 10-dimensional matrix games with Aij ∼ U [0, 1] and compare the most efficient algorithms for matrix games with linear averaging: CBA+ and RM+. We also compare with two other scale-free no-regret algorithms, AdaHedge [DRVEGK14] and AdaFTRL [OP15]. Figure 1a presents the duality gap of the current solutions vs. the number of steps. Here, both CBA+ and RM+ use alternation, which is a trick that is well-known to improve the performances of RM+ [TBJB15], where the repeated game framework is changed such that players take turns updating their strategies, rather than performing these updates simultaneously, see Appendix E.1 for details.2
For EFGs, we compare CBA+and CFR+ on many poker AI benchmark instances, including Leduc, Kuhn, search games and sheriff (see [FKS21] for game descriptions). We present our results in Figures 1b-1d. Additional details and experiments for EFGs are presented in Appendix E.4. Overall, we see in Figure 1 that CBA+may slightly outperform RM+ and CFR+, two of the strongest algorithms for matrix games and EFGs, which were shown to achieve the best empirical performances compared to a wide range of algorithms, including Hedge and other first-order methods [Kro20, KFS18, FKS19b]. For matrix games, AdaHedge and AdaFTRL are both outperformed by RM+ and CBA+; we present more experiments to compare RM+ and CBA+ in Appendix E.2, and more experiments with matrix games in Appendix E.3. Recall that our goal is to generalize these strong performance to other settings: we present our numerical experiments for solving distributionally robust optimization problems in the next section.

heading: 4.2 Distributionally Robust Optimization
text: Problem setup Broadly speaking, DRO attempts to exploit partial knowledge of the statistical properties of the model parameters to obtain risk-averse optimal solutions [RM19]. We focus on the following instance of distributionally robust classification with logistic losses [ND16, BTHKM15]. There are m observed feature-label pairs (ai, bi) ∈ Rn × {−1, 1}, and we want to solve
min x∈Rn,‖x−x0‖2≤R max y∈∆(m),‖y−y0‖22≤λ m∑ i=1 yi`i(x), (5)
where `i(x) = log(1 + exp(−bia>i x)). The formulation (5) takes a worst-case approach to put more weight on misclassified observations and provides some statistical guarantees, e.g., it can be seen as a convex regularization of standard empirical risk minimization instances [DGN21].
We compare CBA+ (with linear averaging and alternation) with Online Mirror Descent (OMD), Optimistic OMD (O-OMD), Follow-The-Regularized-Leader (FTRL) and Optimistic FTRL (OFTRL). We provide a detailed presentation of our implementations of these algorithms in Appendix
2We note that RM+ is guaranteed to retain its convergence rate under alternation. In contrast, we leave resolving this property for CBA+ to future work.
F. We compare the performances of these algorithms with CBA+ on two synthetic data sets and four real data sets. We use linear averaging on decisions for all algorithms, and parameters x0 = 0, R = 10,y0 = (1, ..., 1) /m, λ = 1/2m in eq. (5).
Synthetic and real instances For the synthetic classification instances, we generate an optimal x∗ ∈ Rn, sample ai ∼ N(0, I) for i ∈ {1, ...,m}, set labels bi = sign(a>i x∗), and then we flip 10% of them. For the real classification instances, we use the following data sets from the libsvm website3: adult, australian, splice, madelon. Details about the empirical setting, the data sets and additional numerical experiments are presented in Appendix G.
Choice of step sizes One of the main motivation for CBA+ is to obtain a parameter-free algorithm. Choosing a fixed step size η for the other algorithms requires knowing a bound L on the norm of the instantaneous payoffs (see Appendix F.2 for our derivations of this upper bound). This is a major limitation in practice: these bounds may be very conservative, leading to small step sizes. We highlight this by showing the performance of all four algorithms, for various fixed step sizes η = α× ηth, where α ∈ {1, 100, 1, 000, 10, 000} is a multiplier and ηth is the theoretical step size which guarantees the convergence of the algorithms for each instance. We detail the computation of ηth in Appendix F.2. We present the results of our numerical experiments on synthetic and real data
sets in Figure 2. Additional simulations with adaptive step sizes ηt = 1/ √∑t−1
τ=1 ‖fτ‖22 [Ora19] are presented in Figure 3 and in Appendix G.
Results and discussion In Figure 2, we present the worst-case loss of the current solution x̄T in terms of the number of steps T . We see that when the step sizes is chosen as the theoretical step sizes guaranteeing the convergence of the non-parameter free algorithms (α = 1), CBA+ vastly outperforms all of the algorithms. When we take more aggressive step sizes, the non-parameter-free algorithms become more competitive. For instance, when α = 1, 000, OMD, FTRL and O-FTRL are competitive with CBA+ for the experiments on synthetic data sets. However, for this same instance and α = 1, 000, O-OMD diverges, because the step sizes are far greater than the theoretical step sizes guaranteeing convergence. At α = 10, 000, both OMD and O-OMD diverge. The same type of performances also hold for the splice data set. Finally, for the madelon data set, the non
3https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/
parameter-free algorithms start to be competitive with CBA+ only when α = 10, 000. Again, we note that this range of step sizes η is completely outside the values ηth that guarantee convergence of the algorithms, and fine-tuning the algorithms is time- and resource-consuming. In contrast, CBA+ can be used without wasting time on exploring and finding the best convergence rates, and with confidence in the convergence of the algorithm. Similar observations hold for adaptive step sizes (see Figure 3 and Appendix G). The overall poor performances of the optimistic methods (compared to their O(1/T ) average regret guarantees) may reflect their sensibility to the choice of the step sizes. Additional experiments in Appendix G with other real and synthetic EFG and DRO instances show the robustness of the strong performances of CBA+ across additional problem instances.
Running times compared to CBA+ We would like to emphasize that all of our figures show the number of steps on the x-axis, and not the actual running times of the algorithms. Overall, CBA+ converges to an optimal solution to the DRO instance (5) vastly faster than the other algorithms. In particular, empirically, CBA+ is 2x-2.5x faster than OMD, FTRL and O-FTRL, and 3x-4x faster than O-OMD. This is because OMD, FTRL, O-OMD, and O-FTRL require binary searches at each step, see Appendix F. The functions used in the binary searches themselves require solving an optimization program (an orthogonal projection onto the simplex, see (33)) at each evaluation. Even though computing the orthogonal projection of a vector onto the simplex can be done in O(n log(n)), this results in slower overall running time, compared to CBA+ with (quasi) closed-form updates at each step. The situation is even worse for O-OMD, which requires two proximal updates at each iteration. We acknowledge that the same holds for CBA+ compared to RM+. In particular, CBA+ is slightly slower than RM+, because of the computation of πC(u) in O(n log(n)) operations at every iteration.

heading: 5 Conclusion
text: We have introduced CBA+, a new algorithm for convex-concave saddle-point solving, that is 1) simple to implement for many practical decision sets, 2) completely parameter-free and does not attempt to lear any step sizes, and 3) competitive with, or even better than, state-of-the-art approaches for the best choices of parameters, both for matrix games, extensive-form games, and distributionally robust instances. Our paper is based on Blackwell approachability, which has been used to achieved important breakthroughs in poker AI in recent years, and we hope to generalize the use and implementation of this framework to other important problem instances. Interesting future directions of research include developing a theoretical understanding of the improvements related to alternation in our setting, designing efficient implementations for other widespread decision sets (e.g., based on Kullback-Leibler divergence or φ-divergence), and novel accelerated versions based on strong convex-concavity or optimistim.
Societal impact There is a priori no direct negative societal consequence to this work, since our methods simply return the same solutions as previous algorithms but in a simpler and more efficient way.

Review summaries:
# Summary   In light of successful applications of regret matching (RM) -- an instance of Blackwell approachability -- and its variant regret matching+ (RM+) for saddle point optimization  in zero-sum matrix games with simplex decision sets, the paper proposes generalizations beyond this simple setting to address convex concave problems with compact decisions sets. In the way that RM+ improves RM the conic Blackwell algorithm+ is introduced to improve over the approach of conic blackwell approachability (CBA) from [1]. Furthermore, CBA and CBA+ require non trivial Euclidean projections, in this work explicit closed form or efficient approximations are introduced. CBA and CBA+ are extensively tested on a variety of domains, for which CBA+ seems to demonstrate improvements over CBA similar to how RM+ improves RM. Importantly, like RM and RM+, CBA and CBA+ are parameter-free requiring no tuning.  

This manuscript provides a parameter-free algorithm for solving convex-concave saddle point problems. The main ingredient is that the authors propose an a Conic Blackwell Algorithm^+ (CBA^+) which is able to recover the standard $O(1/\sqrt{T})$ rate but does not require any stepsize choices. Several use cases are presented. Experiments include matrix games on a simplex and distributional robust optimization.

This paper describes an online method for saddle point problems, which uses a sequence of linearizations to minimize for each player. The claim is that this method can accommodate conic domains (as opposed to previous methods which focused on simplex domains) and achieves 1/sqrt(T) average regret (the optimal rate). Discussions of efficient implementations and numerical results are also given. 

This paper proposed a conic Blackwell algorithm (CBA+) based on Blackwell approachability for solving convex-concave saddle point problems. The algorithm does not need to select stepsizes and achieves $O(1/\sqrt{T})$ convergence rate/average regret. The paper demonstrates strong empirical performance of CBA+ on matrix game and DRO problems.