Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a new generalized FW strategy that captures many existing approximate MAP strategies as a special case.  They demonstrate that this new approach is easy to implement and can yield improvements over a CNN alone using a joint CRF/CNN framework for image segmentation.
main_review: Originality:  While the key ideas are based primarily on existing work, this work does make several key contributions related to rates of convergence and accuracy of rounding that are worthwhile in this specific context.

Quality:  1) My only criticism is the somewhat limited experiments.  I think that the one experiment does indeed showcase the strengths (and some of the weakness) of the proposed approach, but as the strategy is widely applicable, it would have been nice to see a more diverse set of experiments.  Still, the paper is already jam-packed, so I don't consider it a significant drawback.

2) There is a lot of work on FW for approximate inference / learning that isn't cited here (of course it would be tough to get it all).  One citation that comes to mind is:

Kui Tang, Nicholas Ruozzi, David Belanger, and Tony Jebara. Bethe learning of graphical models via MAP decoding. Nineteenth International Conference on Artificial Intelligence and Statistics (AISTATS), May 2016.

3) Some comparison of constant versus diminishing stepsize would be interesting in the experimental section.

Clarity:  The paper is well-written and easy to follow (some of this is due to most of the technical proofs being relegated to the appendix).  My only complaint: All of your figures need axis labels.

Significance:  New and improved approximate MAP / learning algorithms promise to reinvigorate works that have, at least until recently, explored the benefits of combined approaches.
limitations_and_societal_impact: Yes, more remains to be done, but the work is a promising start.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Semantic segmentation is a widely-studied problem in computer vision, and over the years a range of techniques have been popular. This paper re-visits the use of dense CRF layers on top of a neural network, which can be used to model pairwise connectivity across output labels. They contribute a new optimization method for mean field inference in the CRF that converges quickly (provably), and is differentiable (such that the whole model can be trained end-to-end). The paper pushes the SOTA on two popular segmentation benchmarks.
main_review:  **originality**
The authors draw on sophisticated optimization techniques (regularized Frank-Wolfe) that have not been applied in the context of mean-field CRF inference. Care needs to be taken because the optimization technique also needs to be differentiable, so that the model can be learned end-to-end. 

**clarity/quality**

The writing is generally high-quality and the paper's contributions are placed carefully in the context of related work.  The paper carefully reproduces recently-published models on a popular computer vision benchmark using the standard evaluation setup.

I don't have technical background to evaluate the theoretical statements about convergence rates in Sec 4. Hopefully another reviewer does, and I defer to their judgment.

I am familiar with the CRF literature, and found the exposition sound.

**significance**
Dense CRFs were popular for semantic segmentation, but have fallen out of interest in recent years. This paper combines dense CRFs with new feature extraction networks and a new way to do CRF inference.The authors hope that this will spark renewed interest in dense CRFs. With that in mind, the paper is significant, as it provides SOTA results and could help the research dialog pivot towards new methods.

My primary hesitation (see below) is that I am unsure if the magnitude of improvement on this task is characteristic of papers that get published based on pushing SOTA. Hopefully the authors can clarify in their response.

**magnitude of accuracy improvement**

I'm unfamiliar with the recent literature on semantic segmentation. Is the magnitude of performance increase in Table 3 characteristic of recently-published papers? How do you know that this difference is statistically significant?

**related work**
The idea of using FW to do marginal inference was established in earlier work. See, for example, "Bethe Learning of Conditional Random Fields via MAP Decoding" and " New outer bounds on the marginal polytope"

Can you comment on the relationship between this and your work?

**end-to-end learning**
Could you learn details of the FW algorithm (e.g., the step size schedule) end-to-end as well?

**vanishing/exploding gradients**
I didn't follow the argument in L377 about vanishing/exploding gradients. Since each update of FW adds something to the current iterate, it resembles a residual network, which is known to suffer less from these issues. Why is unrolled FW different? Is the issue that the unrolled optimization is unstable (e.g., the step size is too big)?

**test-time usage**
What happens when you train with 5 iterations, but use more (e.g., 25) at test time?

**zero gradients**

L336 suggests that the projection step  is problematic, since it yields zero gradients. However, doesn't this contradict 354, where you use \ell_2 because it performs the best?

**fine-grained analysis**
I would appreciate some anecdotes regarding cases where your method seems to meaningfully improve performance over the baseline that doesn't use a CRF layer. Is there some story to where the CRF is useful?

limitations_and_societal_impact: The authors write N/A for "Did you discuss any potential negative societal impacts of your work?"

I understand the thought process: they are contributing core algorithms for a task that is well-established. However, it would have been helpful if the authors commented on the potential biases (e.g., geographical) in this benchmarking dataset.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a general algorithm for CRF learning and inference.  The algorithm is a regularized version of the classical FW algorithm.  It generalizes several existing algorithms , such as mean field and the concave-convex procedure.  Empirical studies on semantic segmentation tasks demonstrate intriguing properties of the proposed regularized FW algorithm. 
main_review: Contributions:  

The authors presents a generic FW algorithm:  regularized FW, and there are various FW variants that can be viewed as special cases of the regularized FW.  In terms of originality,  it is more appropriate to be stated as a summarization of FW variants and giving unified analysis.  



Clarity and related work:  

The presentation is clear and well-organized, the main technical details are well stated.  It is a pleasure to read the paper.  

Regarding mean field algorithms, recently it is shown that classical mean field problems  enjoys  provable guarantees with submodular/supermodular energies sovled by the DR-DoubleGreedy algorithm [1], it would be 
interesting to see whether the regularized FW has some guanrantees/advantages for this class of problems: 

[1] Bian, Y., Buhmann, J., & Krause, A. (2019, May). Optimal continuous dr-submodular maximization and applications to provable mean field inference. In International Conference on Machine Learning (pp. 644-653). PMLR.


Experiments:  

The authors conducted extensive experimental evaluations againgst several baselines, such as PGD, ADMM, and MF,  with two variants of FW:  l2-FW and eFW.  They found that dense CRFs can achieve improvements over the strong DeepLabv3+ CNN baselines.  the best variant of regularized FW achieves an mIoU score of 88 on the PASCAL VOC test set.  The experimental evaluations are solid, in my point of view.  



limitations_and_societal_impact: No. 

For the semantic segmentation task, could discuss potential  threat to user privacy when it is used for surveillance tasks.
review_title: null

Meta-review: The paper is well written and the experiments are convincing. The authors spent a lot of effort addressing reviewer comments and all reviewers increased their score to 7. I would therefore like to accept the paper.

At first, generalized Frank-Wolfe seems like an odd choice for solving (6). Indeed, (6) can be solved by PG or MD, which have a better convergence rate than generalized FW. Moreover, since adding L2 or entropic regularization leads to Euclidean or KL projections instead of usual LMOs, the proposed algorithm is quite similar to PG and MD. I would therefore encourage the authors to further justify their choice. One justification is the connection with parallel mean field, provided that it doesn't hold for MD. In my understanding, another justification would be that FW-like step sizes require no tuning, which is important for backpropagability. In contrast, PG or MD would require either knowledge of the Lipschitz constant or a line search.

A few of minor comments on the technical side:

  * The rates are not state of the art. The authors mention a 1/\sqrt{t} rate for the "adaptive" step-size, but a O(1/t) rate is known for that class of step-sizes, see for instance http://proceedings.mlr.press/v54/locatello17a/locatello17a.pdf and/or https://arxiv.org/pdf/1806.05123.pdf

  * The analysis of the generalized FW algorithm with a strongly convex regularizer is very similar (although not fully identical) to the analysis with strongly convex set. I encourage the authors to mention and/or compare against this line of work, see for instance https://arxiv.org/pdf/2011.03351.pdf  

  * The adaptive step-size still requires to know constants that can be difficult to compute in practice or crude upper bounds. This should be clarified.

* Generalized FW algorithms are also proposed in

F. Bach. Duality between subgradient and conditional gradient methods. SIAM Journal of Optimization
Decision: Accept (Poster)