Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents  new techniques to speed up projections to submodular base polytopes.   The techniques are inspired by both discrete and continuous perspectives.  Arranging the proposed tools together, they present the adaptive away-step Frank-Wolfe algorithm.  The runtime of computing certain Bregman projection is improved by a factor of $\Omega(n/log(n))$.
main_review: Contributions:  

This paper presents several techniques to speed up projections over submodular polytopes.  They give solid theoretical proofs of the tools and algorithms.  It can be viewed as a combinations of several existing techniques, say,  Edmonds greedy algorithm, Frank-Wolfe et al.  However, the toolkit proposed surely introduces some new techniqes.  

Overall, I think it is a solid work in terms theorecial exploration of fast projecting to submodular base polytopes.  


Presentation & clarity: 

- Very well structured paper, main technical components are very well presented, e.g., the toolkit T1-T6.  I really like the illustrations in Figures 1 -3.   

- Better to put Alg. 5 (A^2FW) in the main text,  (though I know it was defered to appendix due to space limit).  It is a pretty well designed algorithm.   



Experiments:  

Figure 4 clearly show computational advantages of your techniques on synthetic data. 
It would be great to see some real-world experiments, say, some experiments from submodular function minimizaiton literature or others.   
 


Minor typos:  

- line 306:  weather -> whether 
- line  64:  their -> there 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper provides a faster algorithm for the Bregman projection onto submodular base polytopes.
- For the case the submodular function is cardinality-based and the mirror map is separable convex, the authors show that the Bregman projection can be done in $O(n \\log n + n EO)$ time, where $n$ is the size of the ground set and $EO$ is the running time of the evaluation oracle of the submodular function. This result improved the previous $O(n^2 EO)$ time.
- Furthermore, the authors provided a toolkit to speed up the Bregman projection in practice. In the numerical experiment, the algorithm with the toolkit runs faster in several orders of magnitudes.
main_review: The paper is well-written and easy to read. The improved algorithm for cardinality-based submodular functions seems nice.

On the other hand, the second contribution is difficult to evaluate. The authors gave several interesting tools to speed up the Bregman projection. However, these are simply heuristics and do not yield an improved time complexity. Also, the authors proposed Adaptive Away-steps Frank-Wolfe (A2FW) and proved its linear convergence. But the linear convergence holds only for strongly convex and smooth mirror maps, which do not include important projection in online learning such as KL-projection. So it is unclear whether these results improve the time complexity of OMD. The present paper provides empirical evaluation only.

Note that OMD is a highly theoretical algorithm with the optimal regret guarantee. For a practical purpose, one can use Follow-the-Perturbed-Leader (FPL) because each iteration is very cheap for submodular polytopes. Does FPL perform poorly in practice? How does OMD with the proposed heuristics compare with FPL in running time? The lack of theoretical improvements and comparison is a weak point of the paper.

Overall, the paper has a neat result but is not strong enough from the theoretical perspective.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper focuses on projection-base methods such as mirror descent for problems, where constraint sets are defined by submodular polytopes. These problems are challenging as they contain an exponential number of constraints. These projection-based methods have superior convergence rates in comparison with their Frank-Wolfe counterparts. However, the latter optimizes a linear objective in each iteration that is easier than doing the projection required in the former. The paper precisely addresses this issue and proposes an Away Step Frank-Wolfe method that leverages the submodular structure of the problem to solve the projection step efficiently. 

main_review: The paper focuses on providing ways for speeding up the projection based optimization methods such as mirror descent that have superior convergence rates, but suffer from expensive projection steps. They concentrate on constraints defined by submodular polytopes. This is an interesting contribution and they provide theoretical results on their proposed Away Step Frank-Wolfe for preforming projections; however, I am not convinced that these problems are well-motivated. They briefly mention applications such as principal component analysis subject to k-sets. However, I believe these applications should be presented in more details to provide motivations for the studied algorithm. Presentation of the paper is decent; however, some notations are confusing. For instance, the main class of problems that the paper aims to solve are never explicitly presented using math, which makes following the paper hard. Moreover, the experimental results are lacking and the description of the numerical results is extremely sparse and rushed. Finally, the paper focuses all of its main sections on their Away-Step Frank-Wolf algorithm; however, this method is only interesting in conjunction with projection based optimization methods. It would be interesting to see analysis or theoretical guarantees on combinations of these methods. Moreover, the paper needs to provide more motivations for considering this class of projection-based methods; indeed, in experiments , Online Frank-Wolfe algorithm is mentioned as a competitor, but is not reported in Fig.  4.  

Typos and minor issues

(a) Line 64 exit→ existing 
(b) Line 138 put space before "We" 
(c) Line 192 “Therefore, for cardinality-based polytopes, using a combinatorial 193 algorithm is better than any iterative optimization method.” → I do not see why this method is "better than any iterative optimization method." 

limitations_and_societal_impact: Despite presenting an interesting contribution, I see serious limitations for the current results.

(a) As mentioned, the paper does not provide enough evidence for the interest in the studied class of problems. Moreover, it does not explicitly state the studied class of problems.

(b) The paper focuses on their proposed method for performing projection more precisely; however, it needs to provide stronger  motivations on why the projection based methods are considered in the first place. I understand that the projection based methods come with a superior convergence rate. However, I do not believe that this discredits Frank-Wolfe methods altogether. A more insightful approach would be to state computation complexity along with convergence rates. In this way, we would be able to understand for which problem sizes the projection based methods are more efficient.

(c) The experimental results are quite limited: first, the presentation of data and problems are extremely lacking and confusing. Second, they are reported on one dataset that is not large. Third, the results for Online Frank-Wolfe algorithm is not reported in the figure.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of Bregman projections on Submodular Base polytopes. The authors present several tools that could speed up computation when this projection is computed for several nearby points, as is the case for example in iterative algorithms such as mirror descent. In particular, the authors first present an algorithm for the special case of cardinality-based submodular functions, that improve over current best known running time. Then they present tools, for general submodular functions, to detect tight inequalities, reuse active sets, restrict linear optimization to the detected tight inequalities, and round approximate projections to exact ones. They show how these tools can be incorporated into away-step Frank-Wolfe (AFW). They also provide some empirical results showing a reduction in running time of online mirror descent (OMD) when their proposed variant of AFW is used for computing projections, compared to using regular AFW.
main_review: Originality and significance:
The result presented for the cardinality-based submodular functions is not really new. In particular, Theorem 2 is a special case of Proposition 8.1 in [19]. But to the best of my knowledge, this paper is the first to explicitly state the relation between Bregman projections on cardinality-based submodular polytopes and isotonic optimization, which is useful to highlight. 

The tools presented for general submodular functions to accelerate Bregman projections are novel. Whether or not they indeed lead to a speed up depends on if the conditions assumed hold or not. The empirical results provided show some evidence that these tools could be helpful. Though in certain cases, one of the tools (reusing active sets) doesn't have an effect (see Figure 4, OMD-ASAFW vs OMD-UAFW), and in others some of the tools lead to worst running time (see Figure 6-right, OMD-A^2FW vs OMD-ASAFW). More comprehensive empirical evaluation is needed. 

Quality: I checked most proofs, they are correct. However the experimental results are not convincing enough.
The examples used (both in the main text and appendix) are too small (ground set size n=25). It is also not clear from the reported results how OMD with the proposed variant of AFW compares with simply using online FW. Showing plots of both regret and runtime for all compared methods (and not just variants of AFW) would better highlight this trade-off. It would be good to also compare with other methods of computing projections. I am particularly interested to see a comparison with minimum norm point algorithm, which already includes one of the proposed tools (rounding to optimal face).
Some information about the set-up is missing: what is the submodular function and Bregman divergence in the first example?

Clarity: The paper is written clearly, with only few typos. 

Other comments/suggestions for improvements:

- The proposed rounding to optimal face (T5) is a generalization of rounding done in minimum norm point algorithm. This is stated on lines 117-118, but it would be good to also restate that lemma 2 is a generalization of the same property used in MNP for $h(x) = \tfrac{1}{2} ||x||_2^2$.

- l.68: there's several more recent papers than [34] that provide faster algorithms for submodular function minimization, with the current fastest approximate algorithm having subquadratic time:

"Chakrabarty, D., Lee, Y. T., Sidford, A., and Wong, S. C.-w. Subquadratic submodular function minimization. In
Proceedings of the ACM SIGACT Symposium on Theory of Computing, STOC 2017"  

- is $n = |E|$? if yes, specify that in the preliminaries.

- first footnote on p.4: this is the definition of convex functions not strictly convex

-----After Rebuttal-----
Thanks for the detailed response. 
I want to clarify that by comparison with MNP I did not mean for a single projection, but a comparison of OMD with the proposed variant of AFW used for projection vs OMD with MNP used for projection.
limitations_and_societal_impact: Authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: This paper presents new techniques to speed up projections to submodular base polytopes. The authors gave theoretical results and some experimental evidence regarding the speed-up. I highly appreciated the rebuttal and discussion followed for this paper. 

As reviewers indicated, there is a mismatch between the theory and practice. The experiments are quite small and miss important baselines. So, it is not clear whether the proposed method is really useful. Unless the authors address this issue, the paper may not be accepted in the current format.  
Decision: Accept (Poster)