Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: # 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.  
main_review: # Main Review

## Summary of Review

Overall, 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).



## Originality and Connections with Previous Work

The 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.

### On the originality of CBA+
It 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.
 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]. 

## Quality
Overall 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?

## Clarity
The 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.

Furthermore, 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.

# Significance


# Other suggested improvements

Below I list some suggested improvements:
1. 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.
2. 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].
3. Regarding the $O(1/T)$ rate in smooth games of optimistic FTRL and OMD  please include a citation to [7]
4. 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]. 
5. 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].


# References

1. 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.

2. 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))

3. Shimkin, N., 2016. An online convex optimization approach to Blackwell's approachability. The Journal of Machine Learning Research, 17(1), pp.4434-4456.

4. 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.

5. 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.

6. Bubeck, S., 2014. Convex optimization: Algorithms and complexity. arXiv preprint arXiv:1405.4980.

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

8. Xiao, L., 2010. Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization. Journal of Machine Learning Research, 11(88), pp.2543-2596.

9. Orabona, F., 2019. A modern introduction to online learning. arXiv preprint arXiv:1912.13213.

10. 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.

limitations_and_societal_impact: Limitations are discussed throughout the paper and in the conclusions. Potential negative societal impact is also addressed.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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. 

(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.

(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.

(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. 

Experiments:

(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.

(ii) In section 4.2, how is $\eta_{th}$ chosen? 

(iii) In Figure 2, CBA+ still cannot outperform well-tuned OFTRL. 


=====POST REBUTTAL=====
Thanks 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. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

CBA+ 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.

The 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.
-	The 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. 
-	In 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.
-	In 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. 
-	In 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.
-	The 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?

Some minor issues:
1.	Line 499, is it $u_T$ or $u$?
2.	It should be “Blackwell approachability” rather than “Blackwell approchability”. 
3.	It would be nice in Thm 3.2 to specify the selection of $w_\tau$. 

limitations_and_societal_impact: This paper focused on theoretical work. The question is not applicable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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.

The 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? 

To 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. 

 - Lemma A.1 statement 4 is not correct. If C = Rn, then C^\circ = {0}, for example. 
 - 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. 
 - eq. (8) there should be kappa in front of the first numerator term
 - line 537 why is 2kappa = ||(kappa, x)||_2?
 - (suggestion, not concern) most of the inequalities between (9) and (10) are in fact equalities
 - I am not sure why the statement 541 is designed to hold. 
 - The statement for Thm A.2 and A.3 are exactly the same. Is one of the two a mistake?
 - line 553 I am not sure why omega_{t+1}v_{t+1} + S_tu_t = 0. 
 - line 560 why is u_t^Tv_{t+1} = 0? 
 - Line 562 why is ||v_tau||_2 a bounded sequence?


limitations_and_societal_impact: There is no negative societal impact
review_title: null

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)