Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations

Summary

This paper focuses on box-simplex games that are min max of degree 2 polynomials being bilinear in the inner and outer optimization variables. The inner problem is over the simplex and the outer problem is over the unit hypercube. The goal of the paper is to unify the previous framework derived in [She17] with standard Bregman divergence domination conditions. This latter framework [She17] consists on exploiting the primal-dual nature of the min-max problem to setup a regularizer over the unit hypercube. This satisfies the so-called "area convexity" condition instead of strong convexity. The outer loop method relies on an extragradient method and the inner loop relies on an alternating minimization sub-procedure. In order to analyze this framework, the authors explain the connections with relative smoothness and extragradient methods. This yields an algorithm to solve box-simplex games that improves the one of [She17] by a log factor.

Strengths

The paper is well-written and I believe quite clear for non-experts in this field. The authors are willing to bridge the gap between area convexity and more standard convexity tools, that makes the contribution original. The proof sketches sound correct.

Weaknesses

I am not a specialist in this field and with a very limited amount of time (too short to read the 39 pages of supplementary material), it is completely impossible to judge whether the framework is correct or not. The authors stated the main theorems and did provide proof sketches and hints that could possibly convince some readers. I have doubts that this work, possibly sound and surely interesting, could be a good fit with NeurIPS. There are neither concrete algorithmic implementation nor benchmarking in the main submission document.

Questions

- after l72 (2): could you please define Delta^(dxd) (the set of trace 1 PSD matrices)? - In (4) what is h?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

There is no limitation section provided by the authors in the main submission. The authors do not address any limitation and do not provide any further research directions.

Summary

The authors study first-order algorithms for box-simplex games, a special kind of two-player zero-sum bi-affine constrained games. The constraints of these games dictate that the first player selects an action represented by a vector within the n-dimensional box ($[-1,1]^n$), while the second player chooses an action defined by a vector from the d-dimensional simplex ($\Delta_d$). The authors show an algorithm for the computation of an $\epsilon$-approximate saddle point of a box-simplex bi-affine game, expressed as $min_{x\in[-1,1]^n,y\in\Delta_d} x^T A y^T - <b,x> + <c,y>$, in time $O(nnz(A)\cdot L \cdot\log(d)/\epsilon)$, where L is the maximum 1-norm of any column of A, and nnz(A) denotes the number of non-zero entries in matrix A. They advance over the previously best-known first-order method by Sherman, removing logarithmic terms. Box-simplex games has some important applications, and the authors' algorithm introduces a new state-of-the-art, including applications like approximate max flow and optimal transport. In the latter part of the paper, the authors broaden their focus to include a new class of two-player games: box-spectraplex games. This is a generalization of box-simplex games where one player still picks an action in a n-dimensional box ($[-1,1]^n$), but the other player chooses as an action, a positive semi-definite matrix Y with trace equals to 1. An applications of these kind of games include spectral sparcification. The authors present a first-order algorithm to computing an approximate saddle point of a box-spectraplex game. After rebuttal: The author's rebuttal successfully addressed my concerns, and as a result, I have chosen to maintain my original score.

Strengths

This paper studies an interesting class of games with important applications, thereby contributing to the current state-of-the-art algorithm. Moreover, the authors novel reinterpretation of the area-convexity as the more standard relative smoothness allows for the use of more conventional analysis methods, which is interesting on its own. I looked at the statement of the lemmas and they seem reasonable. I only verified the proofs in the main body.

Weaknesses

In the spirit of constructive criticism, I believe that the writing could be improved for better readability. Currently, the appendix appears more like a journal version of the paper rather than serving its intended purpose. A few recommendations to enhance the paper include: - On line 63, defining the notation nnz(A) and $||A||_{1\rightarrow 1}$ earlier might improve clarity. - On lines 105-16, it could be beneficial to define the operator $T_{mv}$ sooner. - Several references to 'outer' and 'inner loop' throughout the paper lacked clarity. Lines 38, 215, and 224 are examples of this. Finally, the move towards box-spectraplex games seems to be more theoretical than practical, with limited application examples. Please see the question section.

Questions

Could the authors provide more examples of problems that could be simplified to box-spectraplex games? I was a bit confused in the proof sketch of Theorem 1. For the telescoping sum to be valid, it appears necessary that $\bar{y}_{t+1}$ must equal $\bar{y}^+_t$ (where $\bar{y}_t$ represents the input to the extra gradient step-oracle at step t, and $\bar{y}^+_t$ indicates the output of the extra gradient oracle at step t). However, upon reviewing Algorithm 3 in the supplementary material, different notation seems to be used. Could the authors provide clarification on this?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors list any assumptions for their theorems, and I do not believe this work can have negative societal impact.

Summary

This paper looks at the bilinear min-max problem Area Convexity framework proposed by Sherman through the lens of Relative Lipschitzness condition of Cohen et al. which relates to the standard Bregman analysis in mirror-type algorithms in first-order optimization. Leveraging this connection, they provide the standard analysis of two-timescale Extragradient method for area convex regularizer based Bregman divergence. Tuning a parameter in the analysis and using the structure of the area convex regularizer, they implement an approximate version of Extragradient where each approximate iteration requires O(nnz(A)) computations. This allows them to remove the log(1/\eps) factor Sherman incurred in the analysis of inner loop. The extend similar result to the case where

Strengths

The paper had a new ideas. E.g., tuning parameter alpha/beta in the regularizer was critical step that allowed for approximate implementation as done in Line 5-9 and Line 12-17 of Algorithm 3.

Weaknesses

The main weakness of the paper is in its presentation. The way main paper differs from the supplementary almost feels like reading a new paper with different orders, equation numbers etc. Also, there are concepts introduced which may not be directly relevant to the problem at hand: E.g. Definition 1 is not used throughout the main paper. I had to dig until Appendix B to understand why there was a fuss about it on the very first technical section, i.e., Section 2.1. The paper borrows key ideas developed by Sherman (which are popular by now) and some previous developments such as Lu et al, and Cohen et al. In particular, the idea of Area Convexity is very much exclusively used for bilinear games and there has been no major movement towards general convex-concave problems. In that sense, this is an incremental work in my opinion.

Questions

My questions below are referring to the supplementary material (or actual paper). 1. It would be best if you can explain how steps 7,8,9 relate to steps in Algorithm 1 with exact parameters used for it. Leaving it as "By observation" may not work for large fraction of readers. Same goes for steps 14-17. It would also be worthwhile to remind the reader that h is the entropy divergence function used here. 2. The proof of Lemma 6 needs to deliberate more on what F to use define f(y-hat) in (13) such that Lemma 4 can be applied. 3. Use x_br for two different purposes in the same section is a bad notation. In particular, Lemma 4 defines x_br as argmin F(x,y) for F defined Section 2.2 of the main paper (again, I could not find it in the supplementary paper). Is this the same used in Lemma 6? 4. Remind the reader about H at the beginning of Section 4. 5. In the Proof of Lemma 8, you use Theorem 3.3 of LS01. It would be better if you provide the result as there is already quite a bit of jumping around while reading the paper. I haven't been able to verify the claims in the proof of this lemma. 6. I have read some of the references in the previous paper of this area. Can you also comment BSW19 paper? As I understand, they also implement Shermans MWU algorithm for inner subproblems and hence incur log(1/\eps) additional factor similar to Sherman or JST19. 7. Can you also compare the result for box-spectraplex case with BBN13, AL17, CDST19? In particular, it will be better to state clearly in what regimes Algorithm in Section 4.4 would be better than box-spectraplex variations of the above papers. BSW19: Faster width-dependent algorithm for mixed packing and covering LPs

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

1 poor

Contribution

2 fair

Limitations

I am giving this paper borderline accept since it was not very well written and almost seems like reading two papers at a time which borrows/uses existing literature heavily (sometimes without giving context). If properly written, this paper can be improved substantially. But that will require significant rewriting and hence, I don't see how it will be justified in this conference set up.

Summary

In this paper, the authors consider box-simplex games, a bilinear min-max optimization problem with box and simplex constraints. The current best-known method for solving such problems is Sherman's algorithm, which is based on the concept of "area convexity". The key insight of this work is to reinterpret area convexity as a more general notion of relative Lipschitzness in the optimization literature. Using this new perspective, they streamline the proof of Sherman's algorithm, propose an improved subproblem solver that eliminates the additional log overhead, and further extend the algorithm to box-spectraplex games.

Strengths

- The authors show that area convexity implies a Bregman divergence bound similar to relative Lipschitzness, which is a simple yet insightful observation. I appreciate that it better clarifies the connection between Sherman's algorithm and the classical extragradient methods, making it conceptually easier to understand and extend. - The proposed subproblem solver improves a $\log(1/\epsilon)$ factor from the original Sherman's algorithm. As a corollary, it leads to the state-of-the-art runtime complexity for optimal transport among first-order algorithms.

Weaknesses

I only wish the presentation of the paper could be more clear. In particular, the proposed extragradient algorithm is not fully described in the main text, but only implicitly in the proof of Theorem 1. It would be better if the authors can present the pseudocode and better explain the steps in the algorithm. Also, it is a bit confusing that the supplement is an extended version of the paper rather than the appendix, which makes it a bit hard to track down the proof.

Questions

- In Definition 4, the notation $V_z^{\alpha}$ is undefined. - If I understand correctly, both the GradStepOracle and XGradStepOracle are designed for solving the same kind of subproblem (at the bottom of page 6). Could you explain why they are implemented differently? And how are they related to the algorithm in [LFN18]?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors addressed the limitations by specifying the considered problem class.

Summary

This paper explores the relationship between area convexity and extragradient methods, and provides improved solvers for subproblems required by variants of the algorithm. The paper also presents a state-of-the-art first-order algorithm for solving box-simplex games and a near-linear time algorithm for a matrix generalization of box-simplex games. The authors demonstrate that their algorithms improve runtimes for combinatorial optimization problems and provide new insights into numerical linear algebra. The contributions of the paper include the development of efficient algorithms with improved convergence rates and computational efficiency, as well as the application of these algorithms to various optimization problems in fields such as optimal transport and min-mean-cycle.

Strengths

Through a deeper understanding of the relationship between box-simplex games and matrix generalization problems, the authors propose improved solvers that leverage the lens of relative smoothness and convex analysis to design efficient algorithms with faster runtimes. These proposed algorithms not only improve runtimes for combinatorial optimization problems but also provide new insights into numerical linear algebra and have applications in various combinatorial optimization problems such as approximate maximum flow, optimal transport, and min-mean-cycle. In addition to its technical contributions, the paper is well-written, well-structured, and effectively communicates its main ideas and contributions. The authors present a rigorous analysis of the proposed algorithms, complete with detailed proofs, explanations, and appropriate use of mathematical notation. The inclusion of appendix sections, examples, illustrations, and a comprehensive literature review further enhance the quality, readability, and accessibility of the work. Overall, the strengths of this paper lie in its thorough exploration of area convexity, its innovative use of relative smoothness, and the development of improved algorithms for solving optimization problems.

Weaknesses

1. The author claims to have improved the runtime for the Box-simplex problem, resulting in increased performance of related applications. However, a detailed comparison with previous results is not provided. Providing such a comparison would help readers better understand the level of improvement and contribution of the paper. 2. The paper mentions the use of a proximal oracle in Algorithm 6, but more details on its implementation and computational complexity would be helpful. It would be valuable for the authors to discuss how the proximal oracle contributes to the overall efficiency of the algorithm and whether there are any limitations or challenges in its practical implementation. 3. The paper could benefit from experimental evaluation to validate the proposed approach. Conducting experiments on real-world or synthetic datasets would provide empirical evidence of the effectiveness and efficiency of the alternating minimization scheme.

Questions

Regarding Weakness 1: The author claims to have improved the runtime of multiple applications by solving the Box-simplex problem. However, a detailed comparison with previous results is not provided. Providing such a comparison would help readers better understand the level of improvement and contribution of the paper. Regarding Weakness 2: The paper mentions the use of a proximal oracle in Algorithm 6. Could the authors provide more details on the implementation and computational complexity of this oracle? It would be helpful to understand how the proximal oracle contributes to the overall efficiency of the algorithm and whether there are any limitations or challenges in its practical implementation.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The paper does not discuss the limitations and any potential negative consequences of their work. However, since their algorithm is focused on optimization problems, the impact on society would largely depend on the specific applications and use cases. A brief discussion on the potential real-world implications and ethical considerations would provide valuable context for readers to better understand the broader implications of the research.