Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
Authors: Julien Grand-Clément
Christian Kroer
Venue: NeurIPS 2021 Poster (2021)
Keywords: Saddle-point
Distributionally Robust Optimization
Regret Minimizer
Parameter-Free Algorithm
Blackwell Approachability
Regret Matching

Abstract: 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.

Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
Julien Grand- Grand-Clément"
Christian Kroer
ISOM Department HEC Paris grand-cllement@hec.c. fr
IEOR Department
Columbia University
christian kww.rr@olummi...eee...
Abstract
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, Conic Blackwell Algorithm* (CBA*), which attains O(IVT)) 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 simplexes. We show how to implement CBA* for the simplex, Ep 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 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.
Introduction
We interested in solving saddle-point problems (SPPs) of the form
min max F(x, y), yEy
where X' C R C. I. are convex, compact sets, and F X'x + R is subdifferentiable convex- concave function. Convex-concave SPPs arise a number of practical problems. For example, the problem of computing a Nash equilibrium of zero-sum game can be formulated as a convex-concave SPP, and this the foundation of most methods for solving sequential zero-sum games [vS96] ZJBPO7 TBBB15, KWKKS20) They also arise in imaging [CP1]] Lo -regression (ST18) Markov Decision Processes [[ye05] [KRT3] [STI8, and distributionally robust optimization, where the max term represents the distributional uncertainty (ND16] [THKMI5), In this paper propose efficient, parameter-free algorithms for solving I in many settings, i.c., algorithms that not require any uning 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 i consists of one player choosing æ; E X, the other player choosing y: E Y, and then the players observe the payoff F( 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 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 (NcurIPS 2021).

---

for D. 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):
E++1 arg min (nfi, x) + D(x)|aa),
(2)
where f. E 3, Fa yr) (O, denotes here the set of subgradients as regards the variable a:), P(-II-) 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(VT) after T iterations. This regret can be achieved either by choosing a fixed step size 17 a/LVT, where the subgradients visited (ft) or by choosing adaptive step sizes π a/vt,, for a > 0. This is problematie, 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 a can be time- and resource- consuming, and even practically infeasible for very large instances, since we won't know if the step size will cause 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)
an upper bound on the norms of
The above issues can be circumvented by employing adaptive variants of OMD or FTRL, which lead 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 large- sale game-solving where vegret-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-fre 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 segret-minimization schemes for instantiat- ing the above framework. Our work is motivated by recent advances 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 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 Al challenge, where poker AIs beat human poker players [BITTI5 MSB+ 17 BST8 BST9) The CFR framework itself is a decomposition of the overall regret of the bilinear SPP into local regrets at each decision point in sequential game [KSS19a) The key to the practical performance of CFR- cFRebased 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 by 2t 2t/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 I 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 (T) have convex sets X,Y that are not simplexes, c.g., box constraints or norm-balls for distributionally robust optimization [BTHKMI5). In principle, regret matching arises from a general theory called Blackwell approachability [Bl556] 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 [ABHI]], 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, ly balls, and intersections of the &g ball with hyperplanc
2

---

(with focus on the case where an &g ball is intersected with simplex, which arises naturally as confidence region). This yields an algorithm which we will refer 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 thresholding operation similar to the one employed by RM We call this algorithm CBA
Our contributions We introduce CBA*, a frree algorithm which achieves O D(VT) regret in the worst-case and generalizes the strong performances of RM* for bilinear, simplex saddle-poing 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 '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 []. 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 new class of algorithms for solving convex- convex-concave SPPs. As long as efficient projection operations can be performed (which we show for several practical domains, including the simplex, lp balls and confidence regions in the simplex), one can apply the repeated game framework on (I). where one can use either CBA or CBA* as regret minimizer for X' and y along with polynomial averaging on the generated iterates to solve ①T) at a rate of O (I/VT).
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 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-core 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 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 should be seriously considered as a practical approach for solving convex-coneee SPPs in various settings.
Finally, we make brief note accelerated methods. Our algorithms have rate of convergence towards a saddle point of O (T) similar to OMD and FTRL. In theory, it is possible to obtain faster O (1/T) rate of convergence when F is differentiable with Lipschitz gradients, for example via mirror prox [Ne004] or other primal-dual algorithms (C166) 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 OLL/T) rate of convergence. A similar conclusion has been drawn in the context of sequential game solving, where the fastest O(1/ (1) CFR-based algorithms have better practical performance than the theoretically-supeet a similar vein, using error-bound conditions, it is possible to achieve linear rate, e.g., when solving bilinear saddle-point problems over polyhedral decision sets using the extragradient method (Tse95] or optimistic gradient descent-ascent [WI.2120)] However, these linear rates rely on unknown constants, and may not be indicative of practical performance.
O (1/T))
methods KWKK KFS18).
3

---

2
Game setup and Blackwell Approachability
As stated in Section DI we will solve T using a repeated game framework. The first player chooses strategies from X in order to minimize the sequence of payoff's in the repeated game, while the second player chooses strategies from y in order to maximize payoffs. There are iterations with indices f
T. : In this framework, each iteration t consists of the following steps:
1. Each player chooses strategies Ry E X, yr EY
2. First player observes ft E F ye) and uses f. when computing the next strategy
3. Second player observes E F yi) and uses gr when computing the next strategy
The goal of each player is to minimize their regret Ro Rr across the T iterations:
T RT = (fr,,
T (fr.
T
T Σ gg yn)-
min xEX
RT
max yEY
g y)
The reason this repeated game framework leads to a solution to the SPP problem ① 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 (I).
1 ET, (xt, yt) for any (21)121 (g1)221
Theorem 2.1 (Theorem 1, [Kr220]) Let (æT, 9r) = T Then
max F(2r, y) min gr), S (Rr, + RT.T =Ex
yEY
Therefore, when each player runs regret minimizer that guarantees regret the order of O (ær, (T) converges to solution to ① at rate of O (I/VT). Later we will show general- ization 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 [ for zero-sum games, variants of regret matching used in practice.
Black Approachability Regret matching arises from the Blackwell approachability frame- work [Ba56]]. In Blackwell approachability, a decision maker repeatedly takes decisions 2; from some convex decision set X' (this set plays the same role as X' or 3 in (T). After taking decision æ, the player observes a vector-valued affine payoff function u, (x: E I.. The goal for the decision maker is to force the average payoff 7 - ut (xx) to approach some convex target S. Blackwell proved that convex target set S can be approached if and only if for every halfspace H 2 S, there exists æ E X' such that for every possible payoff function u..). u(x) is guaranteed to lie in H. The action æ is said to force H. Blackwell's proof is via an algorithm: at iteration t, his algorithm projects :-1 Σ (x,) onto S, and then the decision maker chooses an action ar that forces the tangent halfspace to generated by the normal ù (ū), where s the orthogonal projection of ū onto S. We call this algorithm Blackwell's 's algorithm; it approaches S at rate of O(1/VT) 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 way to compute the forcing actions needed at each iteration, i.e., to compute su)
the average payoff = 1
Details on Regret Matching Regret matching arises by instantiating Blackwell approachability with the decision space X' equal to the simplex A(n), the target set S equal to the nonpositive orthant R", and the vector-valued payoff function uxxx)) = J. (fr, z))e equal to the regret associated to each of the n actions (which correspond to the corners of A(n)). Here e E R" has one on every component. [HMC00) showed that with this setup, playing each action with probability proportional to its positive regret up to time satisfies the forcing condition needed in Blackwell's algorithm. Formally, regret matching (RM) keeps a running sum T2 = Σ (fr - (fr, x). and then action i is played with probability Tt+1,1 //.l+/E/ ///>>/ir [rr.]* where I-] denotes thresholding at zero. By Blackwell's approachability theorem, this algorithm converges to zero average regret at rate of ((1/VT) In zero-sum game-solving, it was discovered that 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 every iteration: "; rr- + f: (ft. e. and then actions are again played proportional to rt- In the next section, we describe more general class of regret-minimization algorithms based on Blackwell's algorithm for general sets X, introduced in [АBHI]] Note that similar construction of a general class of algorithms can be achieved through the Lagrangian Hedging framework of [Gor07]. would be interesting construct CBA* algorithm and efficient projection approaches for this framework as well.
3 Conic Blackwell Algorithm
We present the Conic Blackwell Algorithm Plus (BAA), a no-regret algorithm which uses a variation of Blackwell's 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 L,, Ty (that we do not need to know), such that
|lfll & Lz |lgl| S Ly V E E.E.YYEE.EE
((lx.)).VVe. 2y
(3)
CBA* is best understood as a combination of two steps. The first is the basic CBA algorithm, derived from Blackwell's 's algorithm, which we describe next. To convert Blackwell's s algorithm to regret minimizer on X, we use the reduction from [BНIТ] which considers the conic hull max || 22- The Blackwell approachability problem is then
C = (fx] X)) where instantiated with as the decision set, target set equal to the polar C = {z (z, 2) I 0, V4 E C} of C, and payoff vectors ((fr, Iz), -f). The conic Blackwell algorithm (CBA) is implemented by projecting the average payoff vector onto C, calling this projection a x) with a 2 0 and x E X, and playing the action æ.
The second step in CBA* is to modify CBA to make analogous to RM rather than to RM. To do this, the algorithm does not keep track of the average payoff vector. Instead, we keep running aggregation 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 [ This pscudocode relics on two functions: CHOOSEDECISIONCEN* : I=+ - R", which maps the aggregate payoff vector u, to decision in X, and UPDATEPAYOFF which controls how aggregate payoffs. Given an aggregate payoff vector u = (ū, ú) E IR x RR",, we have
CHOOSEDEECIION(CRN" (u) = (K/ū)ū.
If ū 0, we just let CHOOSEDDECISION (u) 2n for some chosen E X.
The function UPDATEPAYOFF is implemented by adding the most recent payoff to the aggre- gate payoffs, and then projecting onto C. More formally, it is defined as
S sut W S) ( s
UPDATEPAYOFFCEN.
(u, (1,
S + (f, ((,
where w is the weight assigned the most recent payoff and S the weight assigned the previous aggregate payoff u. Because of the projection step in UPDATEPAYOFF CBA* we always have u E C, which in turn guarantees that CHOOSEDECISIONCe.. (u) E X, since cone (n) x X))
Let us give some intuition on the effect of projection onto In a geometric sense, it is easier to visualize things in R with C = R2 and C R2. The projection on C moves the vector along the edges of Co maintaining the distance to C and moving toward the vector 0. This is illustrated in Figure 5 in Appendix B. From a same-theoretie standpoint, the projection on C = E eliminates the components of the payoffs that are negative. It enables CBA+ to be less pessimistic than CBA, which may accumulate negative payoffs actions for a long time and never resets the components of the aggregated payoff to O, 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 Te(u) in UPDATEPAYOFF CBA* by suboptimal solution the projection problem. Let us also note the difference between CBA+ and the algorithm introduced in [AHH]] which we have called
5

---

Algorithm 1 Conic Blackwell Algorithm Plus (CBA+)
1: Input A convex, compact set X' C R", K max | x X3.
2: Algorithm parameters Weights (w-)r21 E IR
3: Initialization t = 1, I1 E X.
4: Observe fi then set t1 = (ff1 a1) -1) ERXE".
5: for 2 1 do
6: Choose 24++1 = CHOOSEDECISION.En. (u:).
7: Observe the loss fi+1 E R
8: Update U UPDATEPAYOFF CBA+ (Ue, 2e+1, fi+1, W1+1 Er Wr).
9: Increment & - +tt1 1.
CBA. CBA uses different UPDATEPAYOFF and CHOOSEDECISION functions. In CBA the payoff update is defined as
UPDATEPAYOFFGBA
f. S) S+ S+w (ffx)//,-ff)
S
w
Note in particular the lack of projection as compared to CBA', analogous to the difference between RM and RM* The CHOOSEDECISIONcRA. function then requires projection onto C:
CHOOSEDECISIONCaA (w) = CHOOSEDECISION (πe(u)).
Based upon the analysis in [la56], ABНIT show that CBA with uniform weights (both on payofl's and decisions) guarantees (1/vVT) 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 detailed proof in Appendix B
Theorem 3.1. Consider (z)) generated by CBA* with uniform weights: = 1, T 2 1. Ler
I, = max fl tt 1} and ń = max{||æ||2 x E X. Then
Σ t(f., x1) min ET= t(fe,z) = (KL/VTT)
T
Note that in Theorem 3.1
we have uniform weights on the sequence payoff's (ur) but linearly increasing weights on the sequence of decisions. The proof relies on properties specific 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 (RL/VT)
convergence rates when using a weighted average on both the decisions and the payoff's (Theorems 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 Appendix B
We can compare the O (KL/vV vT)
average regret for CBA* with the O (QL/VV) average regret
for OMD NY83 BTNO1] and FTRL AHR09 McMIl], where Q = max x' 2'|l2 | x' E X). We can always recenter X to contain O. in which case the bounds for OMD/FTRL and CBA' are equivalent since и < Ω < 2k. Note that the bound on the average regret for Optimistic OMD O 12) and Optimistic FTRL (-FFRRL (RST3) is O (Q'L/T) in the game setup, a prion better than the bound for CBA* as regards the number of iterations T. Nonetheless, will see in Section 4 that the empirical performance of CBA* is better than that of (11/T) methods. A similar situation occurs for RM* compared to O-OMD and O-FFRL for solving poker games FKSS9b KWKKS20)
The following theorem gives the convergence rate of CBA' for solving saddle-points I. based on convergence rate the regret of each player (Theorem B.I.. The proof is in Appendix C
Theorem 3.2. Let (ĀT, ÿr) 2 ΣT= (æt, y:) / (T(++))) where (xx) (y:)c20 are generated
by the repeated game framework with CBA* with uniform weights: W, 1,Y T 1. Let L =
max Ln: L,y defined in (3) and k = max (max [| || [1vll2) x E N.y E y). Then
min F(x, 9T) = = (nL/VT). =
max F (TT, y) y

---

3.1 Efficient implementations of CBA*
To obtain an implementation of CBA* and CBA, we need to efficiently resolve the functions CHOOSEDECISIONGEa* and UPDATEPAYOFF In particular, we need to compute <c(u). the orthogonal projection of onto the cone C, where C = (xn) x X):
Tc( E arg min l
21.2.
Even for CBA this problem must be resolved, since [ABHI]] did not study whether (4) can be efficiently solved. 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 Moreau's Decomposition Theorem [CR13], which states that Te (T) can be recovered from Teo (u) and vice-versa, because ne(u) c 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 [FKST9a]. Here, is the number of actions of a player and E Ann) represents randomized strategy. In this case, (C( can be computed in O (n)). Note that RM and RM* obtained by choosing suboptimal solution to 4 avoiding the O (n)lo((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 every iteration. In our numerical experiments, we will see that CBA slightly outperforms RM* and CFR+ in terms of iteration count.
This is of interest for instance in distributionally robust optimization [THKMIS ND16), lo regression (ST18] and saddle-pone point reformulation of Markov Decision Process [S20]. For p in closed-fort form, i.e., in (n) arithmetic operations. For E {1, 0o), we can compute Tc(u) in On (n)( arithmetic operations using a sorting algorithm.
lp balls This is when X (x E R" | < 1 with > I or
compute Te(u)
Ellipsoidal confidence region in the simplex Here, X' is ellipsoidal subregion of the simplex, defined as X = {ær E ((n) || zoll2 S e.). This type of decision set widely used because it is associated with confidence regions when estimating probability distribution from observed data [Iye05] BdHP19]. can also used in the Bellman update for robust Markov Decision Process [Lye05 33 GGCI8) We also assume that the confidence region is "entirely contained in the simplex": : components. In this case, using change of basis show that it is possible compute =<( in closed-form, i.e., in (n) arithmetic operations.
{x E R" e = 1 E R" || - Doll2 I 6 S A(n). to avoid degenerate
Other potential sets of interests Other important decision sets include sets based on Kullback- Leibler divergence {x A(n) KL (z, zu) <x). or, more generally, o- divergence [BTDHDW 13). For these sets, we did not find closed-form solution to the projection problem 4 Still, as long the domain X is convex set, computing тe (u) remains convex problem, and it can be solved efficiently with solvers, although this results in a slower algorithm than with closed-fomm computations of ITC (T))
4 Numerical experiments
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-fomm 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.
4.1 Matrix games on the simplex and Extensive-Form Games
Since the motivation for CBA is to obtain the strong empirical performances of RM* and CFR+ on other decision sets than the simplex, start by checking that CBA* indeed provides comparable
7

---

performance on simplex settings. We compare these methods on matrix games
min max (ar, Ay). mEA(n) (EA(m)
where A is the matrix of payoff, and on extensive-form games (EFGs). EFGs can also be writ- ten as SPPs with bilinear objective and X polytopes encoding the players' space of sequential strategies [vS96]. EFGs be solved via simplex-base based regret minimization by using the coun- terfactual regret minimization (CFR) framework to decompose regrets into local regrets at each simplex. Explaining CFR is beyond the scope of this work; point the reader to [ZIBPO7] or newer explanations [FK119c FKS19a]. For matrix games, we generate 70 synthetic 10-dimensional matrix games with As U00.11 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 Ia 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 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
For EFGs, we compare CBA' and CFR on many poker Al benchmark instances, including Leduc, Kuhn, search games and sheriff (see [FKS21] for game descriptions). We present results in Figures 1b l
Additional details and experiments for EFGs are presented in Appendix [E.4] Overall, see in Figure I 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 wide range of algorithms, including Hedge and other first-order methods (Kro20) KFS18 FKS195]. For matrix games, AdaHedge and AdaFTRL are both outperformed by RM and CBA'; we present more experiments compare RM' and CBA' in Appendix EE.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.
(b) EFG: Ledue, 2 (ca EFG: Battleship. 3 (d) EFG: Ledue, 2 players, ranks. Figure 1: Comparison of CBA* with RM* and CFR on matrix games and EFGs.
(a) Matrix game.
ranks.
turns, ship.
4.2
Distributionally Robust Optimization
Problem setup Broadly speaking, DRO attempts 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] [THKM15).
There are m observed feature-label pairs (a;, bx) E R" x {11, and we want to solve
m
min
max 2o 1 (o
Σ vel((z))
(5)
mER" [RR.| no (e
where (z) = log(1 + exp( 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 convex regularization of standard empirical risk minimization instances (DGN11)
We compare CBA (with linear averaging and alternation) with Online Mirror Descent (MD))
Optimistic OMD (O-OMD), Follow-The-Red Rew.eeegglariiee--eeaaaa (FTRL) and Optimistic FTRL (O- FTRL). We provide a detailed presentation of our implementations of these algorithms in Appendix
We note that RM is guaranteed to retain its convergence rate under alternation. In contrast, we leave resolving this property for CBA" to future work.
8

---

a 100
0.00
0 10,000
normal
10-1
Max Loss(x)
10-2
10"
madelon
10-2
10-1
Number of steps
Figure 2: Comparisons of the performances of CBA with OMD FTRL O-OMD and O-FTRL with fixed step sizes, on synthetic (with normal distribution) and real data sets (splice and madelon).
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 De R
10, (I...., 1) (//m)mmmmm /m, À 1/2m in eq. (5).
Synthetic and real instances For the synthetic classification instances, we generate an optimal xx IR", sample a, N(0, I) for E m!) set labels b, sign(a, x and then we flip 10% of them. For the real classification instances, we use the following data sets from the libsvm websita adutt, australian, splice, madelon. Details about the empirical setting, the data and additional numerical experiments are presented in Appendix G
Choice of step sizes One of the main motivation for CBA* is to obtain parameter-free algorithm. Choosing fixed step size for the other algorithms requires knowing bound L the norm of the instantaneous payoffs (see Appendix F.2 for our derivations of this upper bound). This is major limitation in practice: these bounds may be very conservative, leading small step sizes. We highlight this by showing the performance of all four algorithms, for various fixed step sizes n 7/t where a (1, 100, 1, 000, 10, 000) is multiplier and 1/th is the theoretical step size which guarantees the convergence of the algorithms for each instance. We detail the computation of We present the results of numerical experiments on synthetic and real data
7hh Appendix F22
sets in Figure Additional simulations with adaptive step sizes 1/ Σ
f+ Oral are
presented in Figure and in Appendix G
Results and discussion In Figure 2 we present the worst-case loss the current solution &y 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 porammeeee free algorithms (a = 1), CBA* vastly outperforms all of the algorithms. When we take more aggressive step sizes. the non- non-parameter-ffee algorithms become more competitive. For instance, when a = 1, 000, OMD FTRL, (-FTTR synthetic data sets. However, for this same
competitive with CBA for the experiments instance and a = 000, (OOMO diverges, because the step sizes are far greater than the theoretical step sizes guaranteeing convergence. a 10, 000, both OMD O-OMD type of performances also hold for the splice data set. Finally, for the madelon data set, the non
The same

---

CBA
OMD
-+- 0OMD
FIRL
OFTRL
normal
splice
madelon
10
10-3
10
Max Loss (x)
3
10-1
10-3
10"
10
10-2
10
Number of steps
1P"
10
107
Figure Comparisons of the performances of CBA* OMD FTRL O-OMD and O-FTRL with adaptive step sizes, on synthetic (with normal distribution) and real data sets (splice and madelon).
parameter-free algorithms start to be competitive with CBA only when 10, 000. Again, note that this range of step sizes 1) completely outside the values 7/th that guarantee convergence of In contrast, CBA+
the algorithms, and fine-tuning the algorithms is time- and resource-consumile 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 (1/T)) average regret guarantees) may reflect their sensibility to the choice of the step sizes. Additional experiments in Appendix 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-aaxis, 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 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 TRL 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 results in slower overall running time, compared to CBA' with (quasi) closed-form updates each step. The situation is even worse for (0OMD which requires two proximal updates at each iteration. We acknowledge that the same holds for CBA compared RM In particular, CBA* is slightly slower than RM* because of the computation of TT(u)) in On log(n)) operations at every iteration.
vector onto the simplex can be done in On log(n)), this
5 Conclusion
We have introduced CBA', new algorithm for convex-concan saddle-point solving, that is I) simple to implement for many practical decision sets, 2) completely parameter-fiee and does not attempt to lear any step sizes, and 3) competitive with, or even better than, state-of-the-ar approaches for the best choices of parameters, both for matrix games, extensive-fome games, and distributionally robust instances. Our paper is based on Blackwell approachability. which has been used to achieved important breakthroughs in poker Al in recent years, and we hope to generalize the use and imple- mentation of this framework to other important problem instances. Interesting future directions of research include developing theoretical understanding of the improvements related to alternation in our setting, designing efficient implementations for other widespread decision sets (e.g., based on Ballback-Leiblee divergence or @-divergence), and novel accelerated versions based on strong convex-concavity or optimistim.
Societal impact There is priori direct negative societal consequence this work, since methods simply return the same solutions as previous algorithms but a simpler and more efficient way.
10

---

References
[ABHII] Jacob Abernethy, Peter L. Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pages 27-46. JMLR Workshop and Conference Proceedings, 2011.
[AHRO9] Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. 2009.
[BBJT15] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold'em poker is solved. Science, 347(62188:145-149) 2015.
[BdHP19] Dimitris Bertsimas, Dick den Hertog, and Jean Pauphilet. Probabilistic guarantees in robust optimization. 2019.
[Bla56] David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematicx, 6(1):1-8, 1956.
[BMS19] Neil Burch, Matej Moravcik, and Martin Schmid. Revisiting efr+ and alternating updates. Journal of Artificial Intelligence Research, 64:429-443, 2019.
[BS18] Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374:448--224, 2018.
[BS19] Noam Brown and Tuomas Sandholm. Superhuman for multiplayer poker. Science, 365(6456):885-89) 2019.
[BT03] Amir Beck and Mare Tehoulle. Mirror descent nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31()):667-175, 2003.
[BTDHDW* 13] Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2)344-3377, 2013.
[BTHKM15] Aharon Ben-Tal, Flad Hazan, Tomer Koren, and Shie Mannor, Oracle-hased robust optimiza- tion via online learning. Operations Research, 63(3):628-633 2015.
[BTNO1] Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications, volume 2. Siam, 2001.
[CP11] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex prob- lems with applications to imaging, Journal of muthematicul imaging and vision, 40(1):120-
145, 2011.
[CP16] Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of a first-order primal dual algorithm. Mathematical Programming, (59((12):253-222 287, 2016.
[CR13] Patrick L Combettes and Noli N Reyes. Moreau's 's decomposition in banach spaces. Mathe- matical Programming, 139(1):103-114 2013.
[CYL* 12] Chao-Kai Chiang. Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Oaline optimization with gradual variations. In Conference Learning Theory, pages 6-1. JMLR Workshop and Conference Proceedings. 2012.
[DGN21] John C Duchi, Peter W Glynn, and Hongseok Namkoong. Statistics of robust optimization: generalized empirical likelihood approach. Mathematics of Operations Research. 2021.
[DRVEGK14] Steven De Rooij. Tim Van Erven, Peter Grünwald, and Wouter M Koolen. Follow the leader you can, hedge if you must. The Journal of Machine Learning Research, 15(1):1281-1316, 2014.
[DSSSCO8] John Duchi, Shai Shalev-Shwarz. onto the L-1 ball for learning in high dimensions. In Proceedings of the 25th international conference on Machine learning, pages 272-279, 2008
Shwartz. Yoram Singer, and Tushar Chandra. Efficient projections
[EPGMFB V03] Juan José Egozcue, Vera Pawlowsky Glahh, Glòria Mateu-Figueras and Carles Barcelo-Vidal. Isometric logratio transformations for compositional data analysis. Mathematical Geology. 35(3):279-33 2003.

---

[FKS19a] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for se- quential decision processes and extensive-form games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1917-1925, 2019.
[FKS19b] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive-forie games via dilated distance-generatiinn functions. In Advances in Neural Information Processing Systems, pages 5222-5232, 2019.
[FKS19c] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Regret circuits: Composability of regret minimizers. In International Conference on Machine Learning, pages 1863-1872.
2019.
[FKS21] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAI, 2021.
[GCK20a] Julien Grand-Clément and Christian Kroer. First-order methods for Wasserstein distribution- ally robust MDP, arXiv preprint arXi::200.06690) 2020.
[GCK20b] Julien Grand-Clément and Christian Kroer. Scalable first-order methods for robust mdps. arXiv preprint arXiv:2005.05433 2020.
[GGC18] Vineet Goyal and Julien Grand-Clément, Robust Markov decision process: Beyond rectangu- larity. arXiv preprint urXiv:/811.0022 2018.
[GKG19] Yuan Gao, Christian Kroer, and Donald Goldfarh. Increasing iterate averaging for solving saddle-point problems. arXiv preprint 1rX3vvI903..000 2019.
[Gor07] Geoffrey J Gordon. No-regret algorithms for online convex programs. In Advances in Neural Information Processing Systems, pages 489-496. Citeseer, 2007.
[HMC00] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): 127-):112 2000.
[yy05]] Garud Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-288 2005.
[US20] Yujia Jin and Aaron Sidford. Efficiently solving mdps with stochastic mirror descent. In International Conference on Machine Learning, pages 4890-4900, PMLR, 2020.
[KFS18] Christian Kroer, Gabriele Farina, and Tuomas Sandholm. Solving large sequential games with the excessive gap technique. In Advances in Neural Information Processing Systems, pages 864-874, 2018.
[Kro20] Christian Kroer. 1cor8100, Economics, ai, and optimization lecture note 5: Computing Nash equilibrium via regret minimization. 2020.
[KWKKS20] Christian Kroer, Kevin Waugh, Fatma Kilmę- Kilmg-Karzan, and Tuomas Sandholm. Faster algo- rithms for extensive-fome game solving via improved smoothing functions. Mathematical Programming, pages 1-33, 2020.
[McM11] Brendan McMahan.
Follow-the- www.wttherrgulliizze-leeedde and mirror descent: Equivalence theorems and II regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. pages 525-533. JMLR Workshop and Conference Proceedings. 2011.
[MSB+ + 17] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up nomiimit poker. Science. 356(6337):508) -13-5088851,,,11 2017.
[ND16] Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f- f-divergences. In NIPS, volume 29, pages 2208 22166, 2016.
[Nem04] Arkadi Nemirovski. Prox-method with rate of convergence O(1/)) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal Optimization, 15(1):229-251) 2004.
[NY83] Arkadi Nemirovski and David Yudin. Problem complexity and method efficiency in optimiza- tion. 1983.
12

---

[OPI5] Francesco Orabona and Dávid Pál. Scale-free algorithms for online linear optimization. In International Conference Algorithmic Learning Theory, pages 287-301. Springer, 2015.
[Ora19] Francesco Orahona. arX1v:1912.12213, 2019.
A modern introduction to online learning.
arXiv preprint
[RM19] Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv: 0903.95999.,, 2019.
[RS13] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference Learning Theory, pages 993-1019. PMLR, 2013.
[SALS15] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning games. arXiv preprint
2015.
[Shi16] Nahum Shimkin. An online convex optimization approach blackwell's approachabilityy The Journal of Machine Learning Rexearch, 17(1):4434 4456, 2016.
[ST18] Aaron Sidford and Kevin Tian. Coordinate methods for accelerating l-infinity regression and faster approximate maximum flow. In 2018 IEEE 59th Annual Symposium on Foundations Computer Science (FOCS), pages 922-933. IEEE, 2018
[BBJ115] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit Texas hold' em. Twenty-Fourt International Joint Conference on Artificial Intelligence, 2015.
[Tse9]] Paul Tseng. linear convergence iterative methods variational inequality problem.
Journal of Computational and Applied Mathematics, 60(1-2):237-252, 1995.
[vS96] Bernhard von Stengel. Efficient computation hehavior strategies. Games and Economic Behavior, 14(2):220-246, 1996.
[WKR13] W. Wiesemann, D. Kuhn, and B. Rustem. Robust Markov decision processes. Operations Research, 38(1):153-183, 2013.
[WLZZL20] Chen- Wei, Chung- Wei Lec, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate con- vergence in constrained saddle-point optimization. In International Conference on Learning Representations, 2020.
[ZJBP07] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in neural information processing systems, pages 1729 1736, 2007.
13


Reviews:
[{"review_id": "wWtvVUnDm-", "reviewer": "Reviewer_fhFd", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper tackles the interesting convex-concave saddle point problem. It summarizes the related literature nicely. Comparing to existing approaches like OMD, FTRL, Mirror Prox, Primal-dual approaches, CBA+ does not need to select stepsizes and achieves $O(1/\\sqrt{T})$ convergence rate/average regret using a linearly increasing averaging scheme rather than a uniform average scheme. It is slower than the state-of-the-art $O(1/T)$ achieved by mirror prox though numerically better. \n\nCBA+ builds upon the CBA algorithm [ABH11]. Both use the Blackwell approachability.  The paper also demonstrates $O(1/\\sqrt{T})$ convergence rate/average of CBA algorithm. It is interesting to see algorithms originated from a different perspective than the classical mirror descent and etc. The idea of CBA+ comes from how RM+ is derived from RM algorithm in regret matching problems. Comparing to RM+, CBA+ can be applied to other constraints rather than just simplexes. The paper demonstrates strong empirical performance of CBA+ on matrix game and DRO problems. The results are quite interesting and intriguing though theoretical understanding on why CBA+ performs good in experiments is still a bit lacking.\n\nThe paper is overall well written. The proof is easy to follow, and the numerical settings are clear. Although some additional insights and illustration would be welcomed, see below.\n-\tThe CBA+ algorithm differs from the CBA algorithm mainly in when to do projections onto the cone $\\mathcal{C}$. It would be nice to further illustrate the intuition behind switching the projection order between UPDATEPAYOFF function and CHOOSEDECISION function. \n-\tIn terms of theoretical results, both CBA and CBA+ algorithms achieve the $O(1/\\sqrt{T})$ average regret when using weighted average on both the decisions and the payoffs. On the other hand, the numerical performance of CBA+ is even better than $O(1/T)$ average regret algorithm like mirror prox. It remains unclear whether the current analysis of CBA+ is tight. Demonstration of lower bounds ($O(1/\\sqrt{T})$)  or ever tighter upper bounds ($O(1/T)$) for such Blackwell type algorithms would greatly enhance the contribution. Otherwise, the theoretical contribution is a bit limited.\n-\tIn line 288, the paper says, “Numerically it also helps CBA+ but not CBA.” However, the paper did not provide results on CBA with linear increasing weighted average on decisions. It remains unclear which is the key to achieve better numerical performance, the switch of projection order or linear increasing weighted average on decisions. \n-\tIn line 210-211, the paper says, “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.” It would be nice to demonstrate the constants terms in the average regret to justify the numerical observations.\n-\tThe CBA+ algorithm requires to solve projection operator onto closed convex cones optimally, it can be done on three certain cones as shown in the paper. However, for more general constraints, when exact projections to cones are expensive, what should one do?\n\nSome minor issues:\n1.\tLine 499, is it $u_T$ or $u$?\n2.\tIt should be “Blackwell approachability” rather than “Blackwell approchability”. \n3.\tIt would be nice in Thm 3.2 to specify the selection of $w_\\tau$. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper focused on theoretical work. The question is not applicable.", "review_text": "", "extra_scores": {"ethical_concerns": "The paper do not seem to have any ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "t7VdqM7NYN", "reviewer": "Reviewer_BS7v", "summary": "# Summary \n\nIn 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.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Main Review\n\n## Summary of Review\n\nOverall, the  paper makes for a good contribution to the area of no-regret learning and convex/ concave constrained saddle point optimization. However, improvements can be made with respect to connections with related work, including experiments more closely aligned with the theory, and improving clarity regarding connections to CFR and methods for solving extensive-form games (EFGs).\n\n\n\n## Originality and Connections with Previous Work\n\nThe approach on regret minimization (or online linear optimization) being reduced to an approachability game for convex sets actually predates the construction from [1] referenced in the paper. In [2] the method of Lagrangian hedging (LH) explicitly does this, in fact it is more general, the decision set $\\mathcal{X}$ need not be a cone (for example the simplex is not a cone) but they also consider the trick of embedding the set $\\mathcal{X}$ in a higher dimensional space and taking the conic hull. This flexibility allows for LH to exactly recover RM on the simplex, whereas it is unclear whether the construction in [1] and hence the CBA algorithm recovers RM when applied on the simplex. Provided that CBA and CBA+ are strongly influenced by RM and RM+ it would be useful to mention whether or not CBA can recover RM.\n\n### On the originality of CBA+\nIt is likely CBA+ is novel however it might be strongly related to the OGD based approachability algorithm of [3] if not the same. In [3] however, they do not need to apply the conic hull trick of [1] and do a projection step similar to CBA+. Some discussion is needed to compare the two algorigthms.\n In fact [3] shows an explicit connection with follow the regularized leader and Blackwell's algorithm which is equivalent to CBA if one applies the conic hull trick (this connection was also rediscovered in [4]), it would be nice to include a discussion on how CBA fits in the closely related work of LH [2], [3] and [4]. \n\n## Quality\nOverall the paper is well written except for some clarity issues discussed below. However, I have one issue regarding the experiments. It seems that in all cases CBA+ is used with alternation while there is no theory to support its convergence. I do not think it is necessary to have such a result in this paper but there should be at least some experiments in the main body that are consistent with the theory. What happens if alternation is not used with CBA+ is all the performance lost? For example I think it would be useful to see to RM+, CBA+, and other algorithms without alternation. Also it would be nice to see the explicit benefit of having the  averaging of Theorem 3.1 (again without alternation). How much performance is lost without the linear averaging?\n\n## Clarity\nThe paper is mostly clear except for references to sequential games and EFGs.  For example statements like line 231 \"Simplex  $\\Delta(n)$ is the classical setting used for matrix games and extensive-form games.\" This is very confusing since CBA and CBA+ is often compared to CFR and CFR+, indeed there are experiments in the appendix that make such comparisons. This is confusing because CFR minmizes regret with respect to sequence form which in general is not a simplex (a treeplex instead [5]), however, there seems to be no discussion on implementing CBA or CBA+ on the sequence form. One can model and EFGs using the strategic form and hence over the simplex but this is exponential in the number of game states. Is CBA or CBA+ operating over the sequence form or the classical strategic form? More clarification is needed, and as it stands it in unclear how CBA or CBA+ is used to solve EFGs.\n\nFurthermore, if CBA or CBA+ operates over the sequence form then there needs to be discussion on how it compares with the LH algorithms of [3] (see tech report for more details) a regret matching like algorithm is  devised to work over the sequence form and it is also parameter free approachability strategy designed to minmize regret and hence solve EFGs. I would expect some connection with LH with the Euclidean norm to be closely related to CBA, tho I believe a CBA+ like algorithm that works on the sequence is completely novel.\n\n# Significance\n\n\n# Other suggested improvements\n\nBelow I list some suggested improvements:\n1. I believe your framework and results apply to the case when $F$ is not even differentiable but subdifferentiable, this would improve your results as other stated competitors such as mirror-prox cannot achieve a $O(1/T)$ rate in this setting.\n2. Related to the previous point, there is a missing assumption regarding the $O(1/T)$ rate of mirror prox and optimistic methods, the game needs to be smooth in the Lipschitz gradient sense, see for example section 5.2.3 in [6].\n3. Regarding the $O(1/T)$ rate in smooth games of optimistic FTRL and OMD  please include a citation to [7]\n4. On the topic or rates, it should be mentioned that in matrix games it is possible to achieve linear convergence (a.k.a exponential convergence) with a first order  algorithm which is as computationally expensive as mirror prox see the MAIO algorithm in [10]. \n5. Regarding statements on the stepsize selection of FTRL and / or OMD, it is not true that they require \"knowing a bound L on the norm of the instantaneous payoffs\" it suffices to select $\\eta_t \\in O(\\frac{1}{\\sqrt{t}})$ to achieve an anytime regret bound of $O(\\sqrt{T})$ see for example [8] or [9].\n\n\n# References\n\n1. Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret\nlearning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory,\npages 27–46. JMLR Workshop and Conference Proceedings, 2011.\n\n2. Gordon, G.J., 2007. No-regret algorithms for online convex programs. In Advances in Neural Information Processing Systems (pp. 489-496). (for tech report see [here](https://www.cs.cmu.edu/~ggordon/ggordon.CMU-CALD-05-112.no-regret.pdf))\n\n3. Shimkin, N., 2016. An online convex optimization approach to Blackwell's approachability. The Journal of Machine Learning Research, 17(1), pp.4434-4456.\n\n4. Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive\nblackwell approachability: Connecting regret matching and mirror descent. In Proceedings of\nthe AAAI Conference on Artificial Intelligence. AAAI, 2021.\n\n5. Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. “Smooth-ing techniques for computing Nash equilibria of sequential games.” In:Mathematics of Operations Research35.2 (2010), pp. 494–512.\n\n6. Bubeck, S., 2014. Convex optimization: Algorithms and complexity. arXiv preprint arXiv:1405.4980.\n\n7. Syrgkanis, V., Agarwal, A., Luo, H. and Schapire, R.E., 2015. Fast Convergence of Regularized Learning in Games. Advances in Neural Information Processing Systems, 28, pp.2989-2997.\n\n8. Xiao, L., 2010. Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization. Journal of Machine Learning Research, 11(88), pp.2543-2596.\n\n9. Orabona, F., 2019. A modern introduction to online learning. arXiv preprint arXiv:1912.13213.\n\n10. Munos, R., Perolat, J., Lespiau, J.B., Rowland, M., De Vylder, B., Lanctot, M., Timbers, F., Hennes, D., Omidshafiei, S., Gruslys, A. and Azar, M.G., 2020, November. Fast Computation of Nash Equilibria in Imperfect Information Games. In International Conference on Machine Learning (pp. 7119-7129). PMLR.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed throughout the paper and in the conclusions. Potential negative societal impact is also addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "XPjzri0m3a0", "reviewer": "Reviewer_oLRi", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed algorithm looks original for minimax problems, but I do not think it is of significance in the literature of solving convex-concave saddle point problems. \n\n(i) I am not convinced by the motivation of this work. The authors mentioned in line 37--line 41 that choosing the learning rate requires to know number of periods $T$ and the upper bound $L$ on the norms of the gradients and they may be hard to obtain. I disagree with this argument. The reason is that for convex-concave saddle point problems, the parameters for both min and max variables lie in convex and compact sets with known size, so it is usually easy to compute the upper bound of the gradient $L$ based on the size of the domains. The dependency on $T$ is also avoidable, since one can use time varying learning rate such as $O(1/\\sqrt{t})$ to get the same bound. From my viewpoint, the gradient norm upper bound is easy to compute at least for examples included in Section 4.\n\n(ii) The authors should include the exact constants in big O notation (e.g., in Theorem 3.1, Theorem 3.2) and compare it with the standard algorithms (e.g., OMD, FTRL, etc.), especially the dependency in terms of domain size and the upper bound of gradient norm. It is unclear both from the main text and also the supplement.\n\n(iii) The algorithm design and the corresponding theoretical proofs heavily rely on [Abernethy, Bartlett, Hazan, 2011]. For the algorithm design, the main differences come from the projection steps in line 6 and line 9 in Algorithm 1. For theoretical analysis, The authors should have made it clear what is the purpose of modifying these projection steps and the technical innovation in the proofs. \n\nExperiments:\n\n(i) In Figure 1, why only two methods are compared (e.g., CBA+, CFR+)? What about OMD with best-tuned learning rate? Also the advantage of CBA+ over CFR+ is not significant.\n\n(ii) In section 4.2, how is $\\eta_{th}$ chosen? \n\n(iii) In Figure 2, CBA+ still cannot outperform well-tuned OFTRL. \n\n\n=====POST REBUTTAL=====\nThanks for the authors' response. I still think the presentation of this manuscript needs to be improved, which may needs a major revision. The exact advantage of the regret bound of the proposed algorithm compared with other algorithm (e.g., FTRL, OMD) is not clear. It is very subtle since it is an improvement in terms of constant. I would suggest the authors to have a more precise argument about why the traditional method is inferior than the proposed methods in theory. Due to these reasons, I decide not to change my score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}, {"review_id": "V_eOvfhzs_1", "reviewer": "Reviewer_yZ3K", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am not very familiar with Blackwell algorithms, and the overall algorithmic scheme, which seemed similar to Frank-Wolfe method, is actually significantly different enough that I am not fully equipped to evaluate it in the context of similar methods. Therefore I can't judge the work's originality. In terms of significance, if the claims are as the authors state, and it is indeed a new method, then I believe it is significant.\n\nThe clarity of the main paper is very nice. The paper is easy to read, and the big picture comes through. One issue that I couldn't quite resolve, if kappa = max_{x\\in X} ||x|| and the only restriction is that X is closed and convex, couldn't kappa be infinite? Does the set X need also be bounded? \n\nTo check the math, I went through lemma A1 and theorems A2, A3, and I have more significant questions. It is possible that I misunderstood most of it, and await the authors' responses, after which if the issues are reconciled I can increase the score. \n\n - Lemma A.1 statement 4 is not correct. If C = Rn, then C^\\circ = {0}, for example. \n - line 535 I am not sure why uT can be written as 1/S_T sum_t omega_t ut. It does not seem from alg. 1 that you can recurse on x the way you can recurse on u. \n - eq. (8) there should be kappa in front of the first numerator term\n - line 537 why is 2kappa = ||(kappa, x)||_2?\n - (suggestion, not concern) most of the inequalities between (9) and (10) are in fact equalities\n - I am not sure why the statement 541 is designed to hold. \n - The statement for Thm A.2 and A.3 are exactly the same. Is one of the two a mistake?\n - line 553 I am not sure why omega_{t+1}v_{t+1} + S_tu_t = 0. \n - line 560 why is u_t^Tv_{t+1} = 0? \n - Line 562 why is ||v_tau||_2 a bounded sequence?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no negative societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces parameter and scale free algorithms for convex concave saddle point problems, based on the Blackwell approachability algorithm. The resulting algorithmic schemes exhibit standard 1/sqrt(T) regret, but in comparison to existing algorithms do not require the knowledge of the problem parameters. The techniques for proving convergence rely on results from conic optimization. Numerical results on real and synthetic data demonstrate the efficacy of the introduced algorithms.

Overall, the reviews appreciated the novelty and the simplicity of the framework. However, there were several issues raised by the reviews relating to relationship with related work and the overall clarity. The authors should take these comments into account when preparing the revised version of the paper.
Decision: Accept (Poster)