Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### Summary. 
This work proposed a stepsize for the extragradient/mirror-prox method that works both in smooth and non-smooth settings. The stepsize is based on the empirical values of gradient/operator differences, and mirror maps are used to allow for non-euclidian geometry such as KL divergence. The paper offers us three convergence results: 1 bound for the extragradient update (no mirror map) and 2 bounds for the mirror-prox update (convergence of iterates without a rate and convergence of the restricted gap with rates). The theory is followed by simple randomly-generated problems, which is ok for justifying the theory but can't serve a significant contribution on its own. 
Overall, I enjoyed reading this paper and would recommend it for acceptance if not for two issues: 1) it seems to have low relevance to ICLR and I think it will not get much attention; 2) the stepsize is by definition upper-bounded by 1, and therefore will be suboptimal whenever the optimal stepsize is larger than 1.

### Relevance
The paper starts off with a number of interesting applications: GANs, reinforcement learning and adversarial learning. Unfortunately, it's never explained how the proposed algorithms are relevant to these applications. I think it's fine that the theory is derived for monotone operators, since many algorithms designed for convex objectives often work on nonconvex problems as well. However, unlike the algorithm of Bach and Levy, the one presented here does not allow for stochastic gradients, which is crucial in practice. And it seems to me that the motivation in the introduction is disconnected from the rest of the paper, for instance, it's not obvious why the projection step in (EG) plays any role.
I'm particularly confused by the importance of the "Non-Lips. / Unbounded" property of the stepsize. For instance, Table 1 mentions as an application the D-design, which is not a minmax problem, it's a minimization problem [1] (please correct me if you meant something else). Another example is the KL minimization problem, which is again not a minmax problem, and I do not see why it's of any relevance to the conference. I also think that this problem can be solved by methods from [1, 2] (depending on if it's smooth or not) Finally, the problem in Example 5.3 is also not motivated in this paper. Can the authors elaborate on its importance or give an example of some intereseting problem with minmax/VI structure?

### Suboptimality of the stepsize
The constant 1 in the stepsize, namely in the denominator in Equation (8), makes me skeptical about the method's universality. Due to this choice, we always have gamma_t <= 1, which might not be a good choice. Let's say we take an objective with smoothness constant L=10^(-4), then one can use stepsize gamma_t = 10^4, so the proposed stepsize will be quite suboptimal. I think the reason the authors used constant 1 is that it allows them to claim that the method is parameter-agnostic, but the cost of this choice is that it's not really adaptive. To make it adaptive to the problem properties (smoothness or gradient bound), one needs to have some problem-dependent constant in the denominator, but this means we exchanged one parameter (the stepsize itself) for another (the constant in the denominator).

The fact that the stepsize monotonically decreases is another flaw. RMSprop and Adam have been more successful than Adagrad exactly for this reason, and at least for GRAAL the stepsize can increase even close to the end of the training. In terms of GANs, it has been mentioned in several works, for example [3, 4, 5] that extragradient updates work better when combined with Adam stepsizes.

This is why I have strong doubts about the universality of the stepsize and tend to suggest rejection of this paper.

#### Minor issues:
What is a "divergent operator"? This term does not seem to be introduced anywhere. Moreover, one of the references for its importance (the authors mention [1, 21, 55]), [21], has a wrong title (the correct one is "An Adaptive Proximal Method for Variational Inequalities").

The experiments are only a small contribution as they are only given to support the theory, but I still think it would be better if the authors provided their code.

In Lemma 1 of the main part, the authors use the notation $\gamma_{\infty}$, but in the appendix, they use $\alpha$. Please make the notation consistent.

After formulating Lemma 1, the authors write "UniProx enjoys an accelerated O(1/T) rate of convergence under (MS)". I find the word "accelerated" to be confusing since O(1/T) is the standard rate under (MS), I suggest the authors clarify this place.

Typos:
When going from Equation (D.19) to Equation (D.21), you forgot to divide the right-hand side by $\sum_{t=1}^T \gamma_t$.
Page 18: "we readily get that under (MB) we get that:" -> "we readily get that under (MB):"
Page 22: "Therefore, y letting T" -> "by letting"
In the proof of Lemma F.1: "The lemma will proved by induction" -> "will be proved"

[1] Lu et al., "Relatively-Smooth Convex Optimization by First-Order Methods, and Applications"
[2] Lu, ""Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent"
[3] Gidel et al., "A variational inequality perspective on generative adversarial networks"
[4] Mishchenko et al., "Revisiting Stochastic Extragradient"
[5] Chavdarova et al., "Reducing noise in GAN training with variance reduced extragradient"
review_title: The paper is interesting but its relevance to ICLR is not clear and I have strong doubts about the practicality of the proposed stepsize

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper propose a novel algorithm that solves the min-max problems and games based on the extra gradient (EG) framework. One of the main goal of this paper is to achieve the optimal convergence rate for both smooth/nonsmooth setttings without assuming the Lipchitz continuity/boundedness conditions. A "Bregman-Proximal" step was introduced to take place of the traditional Euclidean norm projection norm to depict the geometry or the smoothness properties of the problem. Furthermore, the authors adopt an adaptive step size scheme into the "Mirror-Prox" step to achieve the optimal convergence rate under both settings. 

Strengths: 
+ Achieves the optimal convergence rate in both the smooth case without the Lipchitz continuity assumptions ($O(1/T)$) and the non-smooth case without the boundedness assumption ($O(1/\sqrt{T})$)
+ "Off-the-shelf" design frees the users from tuning parameters
+ The main improvement over previous Bregmen Mirror Prox algorithms (K Antonakopoulos 2019) is the novel nonsmooth analysis under the MB condition

Weaknesses:
- The authos made an effort to show evaluation results on a basic synthetic example, but this is less challenging.
- Some of the details in the experimental sections are missing, for example the choice of the matrix A.
- The analysis of the convergence rate of a mirror step under the MB condition is an application of the techniques in AMP

In summary, the UnixProx algorithm achieves the optimal $1/T$ convergence or $1/\sqrt{T}$ convergence under the smooth/nonsmooth settings, while it does not require Lipchitz/Boundedness assumptions, which is applicable to problems without prior knowledge of the objective smoothness. This work can potentially help in solving games and reinforcement learning problems. However, the authors are encouraged to provide more experimental results to illustrate the practical impact of relaxing the assumptions.

Question:
can the convergence result in Theorem 1 be interpreted as the convergence result in Theorem 4 when K goes to $\infty$?
Without the adaptive step size mechanism designed in your paper, will the same convergence rate still hold under the same assumption? Will the same result hold with constant step size or for example $\gamma_t = 1/\sqrt{t}$?
review_title: Interesting aspect, more experiments needed

final_score: rating: 7: Good paper, accept
review_content: In this paper the authors propose a variant of the extragradient method that i) achieves optimal convergence in the smooth and nonsmooth regimes, ii) allows one to work with singular operators. The paper is written very well and as far as I could check, mathematics is correct (apart from minor details which are easy to fix). Most importantly, in their analysis the authors use a new tool to work with unbounded operators, which may be of interest in its own right.


Although I applaud authors for the use of innovative tools in their analysis, I would like to raise some concerns for a possible discussion.  Mostly, I am not so happy with the practical side of the paper:

1) No concrete important problems intractable before by the standard extragradient but tractable by the proposed version.

2) Quite bad constants. I think at some point the authors forgot one extra $M$ (see my detailed comment below), but even without it the rates are good asymptotically but bad if constants are written explicitly. I like that the authors did provide explicit formulas, but still feel that some discussion about it might be appropriate. Also I think it would help to have explicit constants in the (MS) case, though I understand that it is harder.
For example, no doubts that the rate interpolation is a great property. On the other hand, for the extragradient choosing right steps between $1/L$ or $1/\sqrt{t}$ does not seem to be so difficult, especially if this choice will appear to be much faster in practice.

3) Discussion of how to choose a Finsler metric is missing (apart from simple examples). For example, what if $V$ is well-defined but not Lipschitz, like $V(x) = \exp(x)$? It is not Lipschitz, so looking at Table 1, a reader can think that this case is covered by the proposed analysis. However, it will be cowered only when a suitable $F$ is given, which (i) a non-trivial problem by itself, (ii) probably not even achievable in principle for all such $V$. In other words, can we prove that for any such $V$ described above there exist a suitable $F$? I doubt it, since an unbounded domain must matter here.

4) I feel like the authors unconsciously push me to suspect that the proposed algorithm will not perform well in most cases. First, as I said above, large constants in the rate and omitted discussion of it. Second, not so illuminating numerical results (Figure 2). I believe the algorithm was designed not for solving unconstrained minimax problem. This problem is too easy for any solver (and to be fair, the comparison with other algorithms was quite limited). Where are some demonstrations of its performance for hard problems (with singular operator)? If not a real world problem, then at least the ones that motivated this paper. Not that even Example 5.3 is not very interesting, since for $V(x) = -(1/x_1, \dots)$ and $X=(0,1]$ the solution will be $x=(1,\dots)$, thus the singularity at zero unlikely will play any role. For instance, what about convex minimization with barriers $\min f(x) - \log x$ on $(0,1]$?

Independently of this, I am in favor of proposed analysis.  I think theoretical contribution is much more important here and it is OK for now if a practical performance still lacks behind. However, it would be nice and helpful to warn readers about possible obstacles and also to motivate them for further research.


Below I list some issues I found. Most of them are minor, but some not.


1. page 1 "Originally applied to variational inequalities": I may be wrong, but I think originally it was applied to saddle point problems, though the extension is of course mostly a change of notation.

2. page 1 "if coupled with an iterate averaging scheme -- the mirror-prox...": Not sure what the authors mean. The mirror-prox template is not needed for getting an ergodic $O(1/T)$ rate. Why do we need mirror updates for that?

3. page 2, Contribution #3 "Off-the-shelf": I cannot entirely agree with it. While this is definitely true for rate interpolation, for addressing Lipschitz continuity this is not true. The proposed algorithm still requires a Bregman-Finsler function as an input. In other words, it requires a user to find such a function and verify one of conditions (MB) or (MS). The user just does not need a precise values of $M$ or $L$, which is good of course.

4. page 2 "As an extra feature of our analysis, we also show that the sequence of iterates...": I would not call this as an extra feature, usually it is one of the essential algorithm's attributes in continuous optimization. Moreover, it is not entirely true, since it requires another assumption that is impossible to verify in practice.

5. page 3: I think adding  "there exists $i$" or "for all $i$"  will help to make a definition of smooth/nonsmooth games more clear.

6. page 3, Proposition 1: its formulation is ambiguous at the moment. Should this inequality hold for any collection of vector fields $V$ or is it sufficient to have only one?

7. Eq. (8):  1 in the denominator. How sensitive is it? Obviously, it should matter for the convergence in the end.
8. L is not present in Eq. (9b)

9. page 6: How standard is the given definition of a regular Finsler metric? It is worth to add the reference, if it is standard.

10. page 6 "The KL loss is well-defined..." I didn't understand this sentence. How is it defined when $x = 0$?

11. page 6 "and the only axiom left to verify is..." I got an impression from above that regularity is not an axiom, but just and an additional property that is good to have.

12. page 6 "the norm could be redefined to ... without affecting our results": I am not sure how valid is this remark. First, we should distinguish theoretical results and practical. For theory I agree, though it was needed only for Theorem 2, not Theorem 3, which possibly may be highlighted. For practical purposes though it might be undesirable to change the norm, since we want $h$ to be strongly convex w.r.t. this norm. And if we start to change $h$, then our algorithmic update will be more expensive, etc. Also it is not clear whether $V$ will still satisfy (MB) or (MS): the dual norm will be also different.

13. page 6 "Metrically smooth" definitions is not clear: it is not symmetric to $x, x'$. Maybe some discussion?

14. page 6, Example 5.3: $V$ is not monotone, thus it contradicts to the "blanket assumption". Considering $V$ with $-$ will be better.

15. page 7 "Second, the main difference between Definition 2 and other definitions of Bregman proximal mappings": I think the authors meant Bregman function, the definition of the proximal mapping is standard.

16. I think it is better to mention all assumptions in the statements (even just as abbreviation or references). Currently, they are put everywhere in the paper. For a reader who wants to quickly skim the main results but will not read a full paper it will be quite helpful.

17. page 7, Th.2: Is set $C$ is fixed or not? The same for a solution $x^*$. And of course the condition is a bit strange.

18. Why not to swap Th.2 and 3? The latter is more important and doesn't require an additional assumption. The former looks more like a side result.

19. page 8, Figure 2: What does it mean tuned or untuned for Extragradient? Larger step? Why do we care about it, isn't it obvious that the algorithm should diverge? Why not to take $\gamma =\frac{1}{|A|}$? How $A$ was generated? It is worth to have a better accuracy for plots in right picture. How the problems in right were generated is not clear. If $V$ was contaminated by noise, does it imply that $V$ is not monotone?

20. page 8, "... Fig. 2 confirms that UniProx can provide a fruitful template for adaptive min-max optimization methods that attain optimal rates in smooth/non-smooth problems." Two plots for a smooth problem unlikely can confirm a smooth case and certainly not a non-smooth one.

21. page 12, Lemma B.1. Note that there wasn't given a definition of Bregman function, but only Bregman-Finsler one.

22. page 12, " if and only if $t=0$": why? what if $p=x$. Next sentence: $\psi$ is a function and not a continuous selection. Next: what does it mean for $\phi$ to be differentiable at $t=0$ or $t=1$?

23. page 13: I don't think notation $X^\circ$ was introduced before. What is a local Bregman function?

24. page 13: I did not understand how condition (C.2) is more general. Note that the definition of regularity uses asymptotic language, that is when $|x'-x|_x \to \infty$. The condition (C.2) is global on the other hand. Of course, there is some intersection of two conditions, but not in general. Maybe instead of regularity, the authors should consider (C.2) definition from the very beginning.

25. Lemma C.1, page 14. I have some difficulties with the proof of this lemma. First, I didn't understand the first sentence: why changing the reference point from $X_t$ to $X_{t+1/2}$ will be sufficient for us? Second, I did not understand the derivation (C.7). Apparently the authors use condition (C.2) but they forgot an extra factor in the RHS, i.e, there should be $M$ next to $\beta$. This will worsen the final bound of course.

26. Lemma D.1: In the main part the authors use notation $\gamma_\infty$ instead of $\alpha$.

27. page 16, Eq.(D.12): it should be $\gamma_{T+1}^2$ in the LHS.

28. I think that parts of the proof of Lemma D.1 can be reused in the proof of Theorem 3.

29. Eq. (D.22): the RHS should be divided over $\sum \gamma_t$.

30. page 18, "Hence, $\gamma_t$ is non-increasing...". This fact is definitely not a consequence of the equation above. Also the equation below should have $\gamma_{t+1}^2$.

31. page 18, "For the second term...": that term should be have a dual norm (star is missing). Also everywhere below.

32. page 18: It makes sense to recall what $C$ is. Note that (C.13) for this is good, but (C.4) is not, since it uses a different reference point. Do we actually need (C.4)? Also probably having a set $\mathcal{C}$ and a constant $C$ in the same proof is not the best notation choice.

33. page 18, "we have the following upper-bound": lower.

34. page 18, Eq. (D.30): Note that in the original statement of Th.3 there were exact constants in $O()$.

35. page 18, Eq.(D.31): Why do we need this equation? I think we should apply Lemma D.1 to Eq.(D.24). Otherwise it is not clear how the bound for the gap follows.

36. page 19: I didn't understand (Eq.D.32). Why $\mathrm{dom} (V) = \mathrm{dom} (h)$ and why not just use the same compactness argument as above? Also, it should be $p$ and not $x^*$.

37. page 19, (Eq.D.34): $\gamma_t^2$ is redundant.

38. page 20, (Eq.E.4): $t$ and $j$ are mixed.

39. page 20, Eq. E.8-E.10: Almost the same things are already proven in Lemma C.1. The explanations there are also more transparent.

40. page 21: Wrong reference in Remark 2.

41. page 21: Proposition E.1: Why now equilibrium set and not a solution set?

42. page 21: I think both in the statement of Prop E.1 and in Eq.(E.19) the extra condition from Th.2 should be mention. Otherwise I don't understand how E.19 was obtained.

43. page 21: Summation in Eq.(E.20) should start not from $t=1$. Liminf in E.19 means that that inequality holds for all $t$ starting from $t=t_0$.


review_title: Review on 'Adaptive Extra-Gradient Methods for Min-Max Optimization and Games'

final_score: rating: 7: Good paper, accept
review_content: In this paper, the authors present an adaptive stepsize strategy for extragradient in order to recover both the ergodic 1/sqrt(T) in the nonsmooth case and 1/T in the smooth case (without the knowledge of the Lipchitz constant). The presented method is rather simple but seems effective both in theory and in practice.

The paper is well written: the motivation, context, and basic definitions are especially clear. The algorithm is intersting and the analysis seems sound. I'm in favor of acceptance.

Concerns
---------

* Could the authors comment on X in 2.3? To be compatible with the projection as used in the EG, it probably has to be closed and known in advance. With the inclusion between K and its relative interior, this seems to imply that K has to be closed somehow. 

* The auhors mention that their stepsize strategy adapts to local Lipschitz constants but since the points are uniformly averaged since iteration 1, the local geometry may be a bit lost. Would it be possible to do some kind of restarting to mitigate this effect?

* I have troubles understanding the statemeent of Theorem 2, notably what does gap(*)<0 means or what are the implication of C being relatively closed and disjoint.



Minor Comments:
- First paragraph: 9 citations in a single pair of brackets is not so informative, please consider breaking it down to smaller bits organized bu great topics. (Same remark at the beginning of Section 3).
- Caption of Table 1: algortihm -> algorithm
- In related works: the notions of "interpolation" (as defined in the caption of Tab.1) and "divergent operators" (in the sense of coercive at the boundary?) may not be so clear to the reader. An additional explanation in the text or a footnote would be appreciated. 
- Below (8), I think the authors mean "lim inf \delta_t >0" and not "lim inf \gamma_t >0"
- The examples sometime end with a small triangle, sometimes not.
- It is a small detail but gamma_t is defined in (8) but gamma_{t+1} is defined in (UniProx), this could be made uniform.
- Could the authors comment on the computability of the proximal mapping (16)? Since X may not be closed, there may be problems at the border. This is probably handled by h as in the example but I am not sure it is implied by the conditions (eg the stong convexity in the local metric). 
- Fig. 2 right appears poorly when printed.
- I would have appreciated a last-iterate vs Average iterate behavior comparison as well as locally smooth/nonsmooth examples in the experiments. (For instance, instead of the stochastic case which seems a bit off topic).
- Parts of the proof in the appendix could be more detailed:
-- Precise that you use regularity in C.7
-- When you use Fenchel-Young, you introduce a K without explicitly mentioning it (eg D.8 or D.22).
-- Precise the derivations between D.26 and D.27 (precise that Lemma C.1 is used)

review_title: Review

Meta-review: The paper introduces a new step size rule for the extragradient/mirror-prox algorithm, building upon and improving the results of Bach & Levy for the deterministic convex-concave setups. The proposed adaptation of EG/Mirror-prox -- dubbed AdaProx in the submitted paper -- has the rate interpolation property, which means that it provides order-optimal rates for both smooth and nonsmooth problems, without any knowledge of the problem class or the problem parameters for the input instance. The paper also demonstrates that the same algorithm can handle certain barrier-based problems, using regularizers based on the Finsler metric.

The consensus of the reviews was that the theory presented in the paper is solid and interesting. The main concerns shared by a subset of the reviews were regarding the practical usefulness of the proposed method. In particular, the method exhibits large constants in the convergence bounds and cannot handle stochastic setups. Further, the empirical evidence provided in the paper was deemed insufficient to demonstrate the algorithm's competitiveness on learning problems. If possible, the authors are advised to provide more convincing empirical results in a revised version, or, alternatively, to tone down the claims regarding the practical performance of the method.
Decision: Accept (Poster)