Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond
Year: 2021

Abstract:
We introduce regularized Frank-Wolfe, a general and effective algorithm for inference and learning of dense conditional random fields (CRFs). The algorithm optimizes a nonconvex continuous relaxation of the CRF inference problem using vanilla Frank-Wolfe with approximate updates, which are equivalent to minimizing a regularized energy function. Our proposed method is a generalization of existing algorithms such as mean field or concave-convex procedure. This perspective not only offers a unified analysis of these algorithms, but also allows an easy way of exploring different variants that potentially yield better performance. We illustrate this in our empirical results on standard semantic segmentation datasets, where several instantiations of our regularized Frank-Wolfe outperform mean field inference, both as a standalone component and as an end-to-end trainable layer in a neural network. We also show that dense CRFs, coupled with our new algorithms, produce significant improvements over strong CNN baselines.

heading: 1 Introduction
text: Fully-connected or dense conditional random fields (CRFs) [34]—combined with strong pixel-level classifiers such as a convolutional neural network (CNN) [25, 42]—have been a highly-successful paradigm for semantic segmentation. Top-performing systems on the PASCAL VOC benchmark [22] used to include a CRF as either a post-processing step [13, 14, 15, 20, 43, 44, 45] or a trainable component [4, 49, 64, 68, 73, 76]. However, as CNNs got stronger, the improvements that CRFs brought decreased over time, and as a result they fell out of favor since 2017 [45].
In this paper, we revisit dense CRFs with two contributions. First, on the theoretical side, we propose regularized Frank-Wolfe, a new class of algorithms for inference and learning of CRFs that perform better than the popular mean field [34, 35, 58]—the method of choice in the aforementioned works. Regularized Frank-Wolfe optimizes a nonconvex continuous relaxation of the CRF inference problem (§2) by performing approximate conditional-gradient updates (§3.1), which is equivalent to minimizing a regularized energy using the generalized Frank-Wolfe method [53] (§3.2). Several of its instantiations lead to new algorithms that have not been studied before in the MAP inference literature (§3.3). Moreover, we show that it also includes several existing methods, including mean field and the concave-convex procedure [75], as special cases (§3.4). This generalized perspective allows a unified analysis of all these old and new algorithms in a single framework (§4). In particular, we show that they achieve a sublinear rate of convergence O(1/ p k) for suitable stepsize schemes, and in certain cases (such as strongly-convex regularizer or concave energy) this can be improved to O(1/k) (§4.1). Furthermore, we provide a tightness analysis for the resulting nonconvex relaxation of the regularized energy, recovering some existing tightness results [10, 41, 61] as special cases (§4.2). The proposed algorithms are easy to implement, converge quickly in practice, and have (sub)differentiable iterates. Such properties are important for successful gradient-based learning via backpropagation [47, 62].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Our second contribution lies on the practical side. In addition to mean field and regularized FrankWolfe variants, we re-implement several existing first-order inference methods [39, 41, 48]—those that are amenable to gradient-based learning—for comparison. Remarkably, we find that dense CRFs can still achieve important improvements over the strong DeepLabv3+ [17] CNN model for all these solvers (§5). In particular, our best variant of regularized Frank-Wolfe achieves a mean intersection-over-union (mIoU) score of 88.0 on the PASCAL VOC test set (§5.3), improving over DeepLabv3+. We hope that these encouraging results could attract interest from the community in considering dense CRFs (again) for tasks such as semantic segmentation. Our source code is made publicly available under the GNU general public license for this purpose.1

heading: 2 Background

heading: 2.1 Inference in CRFs
text: Let s 2 S1 ⇥ · · · ⇥ Sn denote an assignment to n discrete random variables S1, . . . , Sn, where each variable Si takes values in a finite set of states (or labels) Si. Let G = (V, E) be a graph of n nodes (V = {1, 2, . . . , n}). A Markov random field (MRF) defined by G encodes a family of joint distributions that can be factorized as follows, where i : Si ! R+ and ij : Si ⇥ Sj ! R+ are the so-called unary and pairwise (respectively) potential functions, and Z is a normalization factor:
p(s) = 1
Z
Y i2V i(si) Y ij2E ij(si, sj). (1)
Note that (1) can also include conditional distributions, i.e., p(s |o) with observed variables o. In this case the potentials may also depend on o, e.g., i(si;o), and this model is referred to as conditional random field (CRF) [37]. We will present later (§5.1) such a model for image segmentation. In the following, we use MRF and CRF interchangeably. We assume further that all nodes have the same set of labels: Si = S 8i, with cardinality d = |S|. It is convenient to express p(s) as 1Z exp( e(s)), where the so-called energy e(s) is defined as
e(s) = X
i2V ✓i(si) +
X ij2E ✓ij(si, sj), with ✓i(si) = log i(si) (idem for ✓ij). (2)
The task of maximum a posteriori (MAP) inference consists in finding the most probable joint assignment, also known as energy minimization (which is NP-Hard in general [65]):
s⇤ = argmax s2Sn p(s) = argmin s2Sn e(s). (3)

heading: 2.2 Continuous relaxation of MAP inference
text: Let xis be a binary variable such that xis = 1 iff label s is assigned to node i. Then, xi = (xis)s2S 2 {0, 1}d denotes the one-hot vector for node i. Let x 2 {0, 1}nd be the concatenation of all xi, and let ✓i = (✓i(s))s2S 2 Rd, ⇥ij = (✓ij(s, t))s2St2S 2 Rd⇥d. The energy (2) is then
E(x;✓) = X
i2V ✓ > i xi +
X ij2E x> i ⇥ijxj , (4)
where ✓ is a parameter vector composed of all ✓i and⇥ij . The MAP inference problem (3) transforms to minimizing E(x;✓) over the new variables x. A natural approach is to relax the binary constraint and solve the continuous relaxation minx2X E(x;✓) with
X = x 2 Rnd : x 0,1>xi = 1 8i 2 V . (5)
This continuous relaxation is known to be tight [10, 41, 61]. For convenience, we represent the unary potentials as a vector u(✓) = (✓i)i2V 2 Rnd, and the pairwise potentials as a symmetric n⇥ n block matrix P(✓) 2 Rnd⇥nd, where the (i, j) block is ⇥ij . The problem is reduced to
min x2X E(x;✓) , 1 2 x>P(✓)x+ u(✓)>x. (6)
1https://github.com/netw0rkf10w/CRF
The reason we have made ✓ explicit in (4) and (6) is to provide more clarity when discussing the differentiability of their solutions for the learning task. Note that an optimal solution x⇤ to (4) and (6) is a function of ✓, and thus should be written as x⇤(✓). Therefore, when we say a solution is differentiable, it is understood that it is so with respect to ✓. When there is no ambiguity, we omit ✓ and write simply E(x),P, and u. We will be interested in problem (6) in the rest of the paper, though it should be noted that our method also applies to the so-called linear programming (LP) relaxation, which takes the form minx2XLP ELP(x;✓), where ELP(x;✓) = ✓>x and XLP is the so-called local polytope [72]. We refer to Appendix A for the details.

heading: 2.3 Vanilla Frank-Wolfe algorithm for MAP inference
text: Since the continuous energy is differentiable, it is natural to apply first-order methods such as FrankWolfe [23] to solving (6) [41]. Starting from a feasible x0 2 X , Frank-Wolfe approximately solves (6) by iterating the following steps, where ↵k 2 [0, 1] follows some stepsize scheme:
pk 2 argmin p2X
⌦ rE(xk),p ↵ , xk+1 = xk + ↵k(p k xk). (7)
The same idea has also been successfully applied to other types of continuous relaxations of (6), such as linear programming (LP) [52] or convex quadratic programming (QP) [21, 61].

heading: 3 Regularized Frank-Wolfe for inference
text: In this section, we introduce the proposed regularized Frank-Wolfe as a general class of algorithms for MAP inference. The motivation and general framework are presented in §3.1 and §3.2. We show that several new inference algorithms can be obtained using different regularizers (§3.3). Moreover, regularized Frank-Wolfe also includes a number of existing algorithms as special cases (§3.4).

heading: 3.1 A smoothing perspective
text: We have seen in §2.3 the (vanilla) Frank-Wolfe method for solving MAP inference. Unfortunately, from a learning perspective, this algorithm is problematic. Indeed, CRF learning with stochastic gradient descent (SGD) is typically done by backpropagating through the optimization steps [35, 63, 76], but the iterate pk in (7) is piecewise constant and thus its gradient (w.r.t. ✓) is zero almost everywhere (§C.1), which makes learning not possible.2 This issue will be illustrated later in the experiments. A potential solution is to add a (typically strongly-)convex regularization term:
pk 2 argmin p2X
⌦ rE(xk),p ↵ + r(p) , xk+1 = xk + ↵k(p k xk). (8)
With appropriately chosen regularizers, (8) becomes suitable for gradient-based learning.
The technique of approximating an update step by a regularized one is quite standard in the optimization literature. For example, the classical proximal gradient method [48] can be interpreted the same way. Our update (8) is inspired by Nesterov’s smoothing [56], and thus is similar in spirit to its many applications [31, 57, 66]. In the next section, we present a different, more general perspective to view (8), which offers more flexibility in designing new algorithms, in making connections to existing ones, and in analyzing their theoretical properties in a unified manner.

heading: 3.2 A regularized energy perspective
text: Instead of approximating the local updates of a given algorithm (in this case: vanilla Frank-Wolfe) to minimize the same objective function, one may choose to keep the algorithm, and approximate instead the objective. At first glance, however, this idea does not seem to be a good one. Indeed, if we replace E by some function E0 and apply vanilla Frank-Wolfe, the updates (7) remains piecewise constant, thus we have the same zero-gradient issue. It turns out that, if we choose a more appropriate “given algorithm”, this idea can work. Such a choice is the generalized Frank-Wolfe algorithm [5, 12, 53].
2Note that backpropagation typically requires the operations to be differentiable (at least) almost everywhere, which pk satisfies. Therefore, the issue here does not lie in differentiability, but in the resulting zero gradients. Blackbox differentiation [60] can deal with this scenario, but it is limited to LP relaxations.
Consider the following problem, where f : Rm ! R [ {+1} is differentiable but possibly nonconvex, and g : Rm ! R[ {+1} is proper, closed, and convex but possibly non-differentiable:
min x
F (x) , f(x) + g(x). (9)
Generalized Frank-Wolfe solves (9) by iterating
pk 2 argmin p
⌦ rf(xk),p ↵ + g(p) , xk+1 = xk + ↵k(p k xk). (10)
If g is the indicator function X of X (i.e., X (x) = 0 if x 2 X and X (x) = +1 otherwise), then the algorithm clearly reduces to vanilla Frank-Wolfe (7) for minx2X f(x). Therefore, generalized Frank-Wolfe applied to (6) with f = E and g = X will yield exactly the same updates (7). Now let us apply this algorithm to an approximate objective Er(x) = E(x) + r(x) for some function r. Choosing f = E and g = r + X , it is straightforward that (10) reduces to (8). Therefore, we have recovered the same algorithm as in §3.1, but this time through different machinery.
This framework offers a great flexibility as one can choose f and g in many different ways to obtain new algorithms. The only conditions are f being differentiable and g being convex, so that the subproblem in (10) is well-defined and globally solvable.3 For example, instead of choosing f = E and g = r+ X as above, one can choose f(x) = 12x
>Px and g(x) = u>x+r(x)+ X (x). We will recover later in §3.4 some existing algorithms (as special cases) through this kind of decomposition. Finally, we present Algorithm 1 for (approximately) solving MAP inference (6).
Algorithm 1 Generic regularized Frank-Wolfe for (approximately) solving MAP inference (6). 1: Choose a regularizer r such that there exist f (differentiable) and g (convex) satisfying f + g =
E + r + X . Typically (but not necessarily) r is convex on X and is constant on X \ {0, 1} nd.
2: Initialization: k 0, x0 2 X , number of iterations N . 3: Compute pk 2 argminp ⌦ rf(xk),p ↵ + g(p) and compute the stepsize ↵k. 4: Update xk+1 = xk + ↵k(pk xk). Let k k + 1 and go to Step 3 until k = N . 5: Rounding: convert x to a discrete solution and return.
While the choice of (r, f, g) can be highly flexible, it would make little sense to optimize a function that has nothing to do with the original objective (i.e., the discrete energy). Let X = X \ {0, 1}nd
denote the discrete domain of our problem. If we choose r such that it is constant on X (as suggested in Step 1 above), then minimizing E on X is equivalent to minimizing E+r on X , and thus Algorithm 1 actually solves the continuous relaxation of a (different) discrete problem that is equivalent to MAP inference. Further discussion on this matter, as well as on the rounding Step 5, are deferred until §4.2.
Finally, we should note that adding a strongly-convex regularizer is not new in the MAP inference literature [29, 31, 52, 67, 69]. In particular, some previous work even applied (vanilla) Frank-Wolfe to optimizing such regularized energy [52, 67, 69]. All these algorithms, however, suffer from the aforementioned zero-gradient issue, as already explained in the beginning of this section.

heading: 3.3 Particular instantiations
text: The previous section presents regularized Frank-Wolfe as a general algorithm for inference. We now discuss concrete examples of its instantiations. To the best of our knowledge, all the algorithms presented in this section are new and have not been studied previously in the MAP inference literature. In particular, despite some similarities with proximal gradient [48] and mirror descent [8, 55], our following euclidean and entropic variants are actually different from these methods.4
Euclidean Frank-Wolfe Perhaps the most natural choice is `2 regularization. In Algorithm 1, let us choose f(x) = E(x) and r(x) = 2 kxk 2 2, where > 0 is a regularization weight. Let ⇧X (v) be the projection of a vector v onto X . It can be shown (§D.1) that Step 3 in Algorithm 1 becomes
pk = argmin p2X
⇢⌦ Pxk + u,p ↵ +
2 kpk22 = ⇧X
✓ 1
(Pxk + u) ◆ 8k 0. (11)
3Further mild conditions are required for convergence (§4.1). 4In proximal gradient and mirror descent, the current iterate is constrained to stay close to the previous one,
while this is not the case in our method. See Appendix D for the details.
Entropic Frank-Wolfe In Algorithm 1, let us choose f(x) = E(x) and r(x) = H(x), where > 0 is a regularization weight and H(x) = P i2V P s2S xis log xis is the entropy of x over X . It can be shown (§D.2) that Step 3 in Algorithm 1 becomes
pk = argmin p2X
⌦ Pxk + u,p ↵ H(p) = softmax
✓ 1
(Pxk + u) ◆ 8k 0, (12)
where v = softmax(x) with x 2 Rnd means v 2 Rnd and vis = exp(xis)P t2S exp(xit) 8i 2 V, 8s 2 S. The resulting algorithm has a tight connection with (parallel) mean field [34, 35] (discussed in §3.4).
Other variants One can consider more sophisticated regularizers, e.g., a weighted combination of `2 norm and entropy. Other options include the many different regularizers that have been used in diverse machine learning applications, such as `p norm [57], lasso variants [57], or binary entropy [3]. Although these variants also lead to new MAP inference algorithms, their implementations are more sophisticated since their subproblems (10) require numerical solutions as no closed form ones exist.

heading: 3.4 Recovering existing algorithms as special cases
text: In addition to the above new algorithms, regularized Frank-Wolfe also includes several existing ones as special cases. We present some of them below and refer to Appendix A for further details.
Mean field This is a special case of the above Entropic Frank-Wolfe. Indeed, if we choose = 1 in (12) and a constant stepsize ↵k = 1 8k 0 in Algorithm 1, then it is straightforward that this algorithm is reduced to the following update step, where Ni is the set of neighbors of node i:
xk+1 = softmax( Pxk u) () xk+1 is = 1 Zi exp
✓ ✓i(s) P j2Ni P t2S ✓ij(s, t)x k jt ◆ 8i 2 V, s 2 S .
This is precisely a (parallel) mean field update [34, 35]. To conclude, parallel mean field is an instance of Entropic Frank-Wolfe with unit regularization weight and unit stepsize. Interestingly, the update (12) is the well-known softmax function with temperature in the deep learning literature [28]. One could have easily come up with such a simple extension of mean field by adding a temperature to softmax (yet surprisingly this has not been tried before), but here we have provided a principled way to achieve that. As shown later in the experiments, with suitable , this extension yields much better results than vanilla mean field. Finally, we should note that the tight connection between mean field and first-order methods has been noticed before. Krähenbühl and Koltun [35] proposed several mean-field-type variants based on the concave-convex procedure [75], while closely similar variants can also be obtained through proximal gradient [2, 6], but unlike our generalized algorithm, these algorithms cannot recover exactly the original mean field of Krähenbühl and Koltun [34].
Concave-convex procedure CCCP [75] solves (9), assuming f is concave and g is convex, by updating xk+1 as a solution to rf(xk) 2 @g(xk+1),5 which is precisely (10) with stepsize ↵k = 1. We conclude that CCCP is a special case of generalized Frank-Wolfe with f concave and unit stepsize. As a result, many existing CCCP-based inference algorithms [21, 35] can be seen as special cases of regularized Frank-Wolfe. For example, the ones presented by Desmaison et al. [21] are instantiations of the proposed algorithm with either f(x) = x> diag(c)x and r(x) = E(x) + x> diag(c)x (where c 2 Rnd is large enough so that r(x) is convex), or f(x) = x>(P C)x and r(x) = u>x + x>Cx (where C is some matrix such that f is concave and r is convex). Note that in these instantiations, Step 3 in Algorithm 1 requires an iterative (numerical) solution. Finally, all the algorithms presented by Krähenbühl and Koltun [35] are also instantiations of the proposed method because they are based on CCCP. We refer to Appendix A for further details.
Vanilla Frank-Wolfe This is trivially a special case of regularized Frank-Wolfe and we briefly discuss it for completeness. Choosing f(x) = E(x) and r(x) = 0 we obtain the algorithm by Lê-Huu and Paragios [41]. Likewise, the one by Desmaison et al. [21] corresponds to f(x) = E(x) c>x+ x> diag(c)x and r(x) = 0, where c 2 Rnd is large enough for f to be convex. In addition, we can also recover existing LP-based algorithms by choosing X = XLP, r(x) = 0, and f(x) = ELP(x) +R(x) with suitable R(x). Indeed, the one by Meshi et al. [52] takes R(x) as the squared `2-norm of linear constraints, while the ones by Sontag and Jaakkola [67] and Tang et al. [69] correspond to R(x) being an entropy approximation and its generalization, respectively (see §A).
5In the original CCCP [75], g is differentiable, thus the update becomes rf(xk) = rg(xk+1).

heading: 4 Theoretical analysis

heading: 4.1 Convergence
text: We provide a convergence analysis for the generalized Frank-Wolfe algorithm, and the results for CRF inference special cases will then follow as a consequence. Convergence of vanilla Frank-Wolfe has been well studied in the literature [24, 30, 36, 38]. For generalized Frank-Wolfe, different analyses exist for the case where both f and g in (9) are convex [5, 26, 51, 74]. We are particularly interested in the general case where f is nonconvex,6 as the CRF energy is often highly so in practice. Mine and Fukushima [53] (and subsequently Bredies et al. [12]) proved the global convergence of the algorithm under mild conditions, though no rate of convergence was given. Recently, Beck [7] obtained an O(1/ p k) rate of convergence for convex g under adaptive or line-search stepsizes. We extend their analysis with several contributions. First, we include the case where g is strongly convex, which is important as our main variants for inference (e.g., mean field or `2-Frank-Wolfe) use strongly-convex regularizers. Second, to also include CCCP [75] as a special case, we relax their Lipschitz smoothness assumption on f to semi-concavity (which is weaker, as any L-smooth function is also L-concave). Third, we also consider much weaker stepsize schemes such as constant or non-summable ones. We show that for either concave f or strongly-convex g, a better O(1/k) rate of convergence can be achieved, even under the (weak) constant stepsize. It should be noted that our results are new.
All the results in this section are stated under the following assumptions, where Lf and g are non-negative constants and k·k denotes the `2 norm. Their proofs are given in Appendix B.
Assumption 1. f is differentiable and Lf -semi-concave (i.e., f(x) Lf2 kxk 2 is concave) on dom f , which is assumed to be open and convex. When Lf = 0, f is concave.
Assumption 2. g is proper, closed, and g-strongly-convex (i.e., g(x) g2 kxk 2 is convex), and dom g ✓ dom f is compact. When g > 0, g is strongly convex.
Let px denote a solution of minp {hrf(x),pi+ g(p)} and let pk = pxk . The following quantity, called the conditional gradient norm [7], will serve as an optimality measure:
S(x) = hrf(x),x pxi+ g(x) g(px). (13)
Lemma 1. S(x) g2 kx pxk 2 8x 2 dom f , and S(x) = 0 iff x is a stationary point of (9).
The following theorem contains our convergence results for the most common stepsize schemes, including the following adaptive and line-search stepsizes, respectively:
↵k = min
( 1,
1
Lf + g
S(xk)
kpk xkk2 +
g
2
!) , ↵k = argmin
↵2[0,1] F (xk +↵(pk xk)). (14)
Theorem 1. Let F ⇤ be the minimum value of F , ⌦ be the diameter of dom g, k = F (xk) F ⇤, ! = g
Lf+ g , ⇢(↵) = ↵min 1, 2 ↵ ! , ⌘(↵) = 12 [(Lf + g)↵ g], and µ =
p 2Lf 0. For any
k 0, we have min0ik S(xi)  Bk, where the bound Bk is given as follows:
constant stepsize constant step length non-summable adaptive or line search (14)↵k = ↵ > 0 8k ↵k = ↵
kpk xkk 8k
P+1 k=0 ↵k = 1
convex g 0↵(k+1) + Lf⌦
2↵
2 0⌦ ↵(k+1) + Lf⌦↵ 2
0+ Lf⌦
2
2
Pk i=0 ↵
2 iPk
i=0 ↵i max
2 0 k+1 , µ⌦p k+1
strongly convex g 0 ↵(k+1)+ ⌘(↵)⌦ 2 8↵ 2! 0
⇢(↵)(k+1) 8↵<2!
⇣ 0
↵ p 2 g(k+1) +
(Lf+ g)↵
2 p
2 g ⌘2 k(!)Pk i=k(!) ↵i
0 !(k+1)
concave f 0↵(k+1) 0⌦ ↵(k+1) 0Pk i=0 ↵i
2 0 k+1
In the above, k(!) = min {k : ↵i < 2! 8i k}, with further assumption that limk!1 ↵k = 0 for (jointly) non-concave f and non-summable ↵k. For the non-highlighted cases, we have limk!1 S(xk) = 0 and any limit point of the sequence (xk)k 0 is a stationary point of (9).
The table in Theorem 1 also provides rates of convergence for the algorithm. Prior to our work, the O(1/ p k) rate for the adaptive or line-search stepsizes (top-right cell of the table, due to Beck [7])
6Note that g is still assumed to be convex, so that the subproblem (10) can be solved to global optimality.
was the best for nonconvex objectives.7 We have improved this rate to O(1/k) when f is concave or g is strongly convex, even under weaker stepsize schemes. In particular, convergence is guaranteed for all considered stepsize schemes when f is concave, for which the best bound is obtained when ↵k = 1 8k, which explains the default unit stepsize in CCCP [75] (see §3.4). Convergence is also guaranteed for the (diminishing) non-summable scheme (which includes common stepsizes such as ↵k = 2/(k + 2) or ↵k = 1/ p k), but the rate depends on the rate of divergence of P k
i=0 ↵i. More detailed results and analyses can be found in Appendix B.
Convergence for MAP inference For all the instantiations of regularized Frank-Wolfe presented in §3.3 and §3.4, it is easy to check that Assumptions 1 and 2 are satisfied. In addition, the regularizers in most of them (euclidean or entropic variants, including mean field) are strongly convex, thus we would expect a rate of convergence of at least O(1/k) in practice for these algorithms under the adaptive, line search, or (suitable) constant stepsizes. Note that the adaptive scheme requires to know Lf and g, which is possible in our case: a lower bound on g is for both euclidean and entropic variants, while an upper bound on Lf is kPk2 for the energy (6). In practice, however, these bounds could be too loose to yield good convergence.
Convergent mean field It is well-known that parallel mean field may diverge [35]. Our Entropic Frank-Wolfe can be viewed as an improved variant of mean field that is globally convergent for different stepsize schemes, without resorting to a concave approximation as done by Krähenbühl and Koltun [35]. Our above analysis also provides an explanation for a known phenomenon [6]: damped mean field (corresponding to Entropic Frank-Wolfe with = 1 and ↵k = ↵ < 1 8k) is more likely (than mean field) to guarantee convergence when the energy is not concave.

heading: 4.2 Tightness of the relaxation
text: We have seen that regularized Frank-Wolfe (Algorithm 1) minimizes a modified continuous energy. It is thus reasonable to ask whether doing so also minimizes the original discrete energy (which is the main objective). In this section, we partially answer this question by providing some tightness guarantee for this regularized continuous relaxation. Our analysis is quite general and also includes several existing tightness results [10, 41, 61] as special cases. All proofs can be found in Appendix C.2.
The last step in Algorithm 1 consists in converting x to a discrete solution. We consider two such rounding schemes. The simplest one is perhaps nearest rounding, which assigns each node i with the label si 2 argmaxt2S xit. Intuitively, this sets xi to the nearest vertex of the simplex xi 2 Rd+ : 1>xi = 1 . The second scheme, called BCD rounding [41, 61], consists in minimizing E(x) over xi while keeping all xj (j 6= i) fixed (i.e., block coordinate descent), which amounts to iteratively assigning each node i with label si 2 argmins2S n ✓i(s) + P j2Ni P t2S ✓ij(s, t)xjt o . In practice, we only use nearest rounding because BCD rounding is too expensive for dense graphs. However, an important property of the latter is that it does not increase the energy, which is useful for our theoretical analysis. The following theorem provides an additive bound on the energy. Theorem 2. Let x⇤
r be a global minimum of Er(x) = E(x) + r(x) over X , x̄⇤r be the dis-
crete solution rounded from x⇤ r , and E⇤ be the minimum discrete energy. Assume that r(x) is bounded:8 m  r(x)  M 8x 2 X . We have E⇤  E(x̄⇤ r )  E⇤ + M m + C, where
C = q n 1 1
d (kuk2 + p n kPk2) for nearest rounding and C = 0 for BCD rounding.
Let us derive the energy BCD bound for some particular cases (see §C.2 for details). Obviously with no regularization (r = 0), we have M = m = 0 and thus E(x̄⇤
r )  E⇤  E(x̄⇤ r ), yielding
E(x̄⇤ r ) = E⇤, i.e., the relaxation is tight. We have thus recovered a previously known result [10, 41, 61]. For r(x) = c>x + x> diag(c)x with c 0, we have M = 0 and m = 141 >c, which recovers exactly the additive bound given by Ravikumar and Lafferty [61] for the convex QP relaxation. For the `2 regularizer r(x) = 2 kxk 2 2, we have M = n 2 and m = n
2d , thus we obtain a bound of n2 1 1 d . For the entropy regularizer r(x) = H(x), we have M = 0 and m = n log d, thus the bound is n log d, which is worse than the `2 bound for any d 5. 7If both f and g are convex, a better rate of O(1/k) exists [5, 7, 74]. In addition, if g is the indicator function of a convex set X (i.e., vanilla Frank-Wolfe) and either f or X is strongly convex, a linear rate can be obtained [32, 50, 59]. Note that we use quite different machinery from all these analyses, due to the nonconvexity.
8A sufficient condition is r being continuous, as X is compact.
Note that the bound provided by Theorem 2 is achieved from a global minimum of the regularized relaxation. This can be attained in some cases, e.g., when the energy is submodular or when the (convex) regularizer is large enough to make the objective convex. In the general case, however, the algorithm is only guaranteed to reach a stationary point, and the (theoretical) quality of such point remains unknown. It would be interesting to investigate whether the algorithm can provide an approximation guarantee for some classes of energies (e.g., supermodular ones), similar to some existing algorithms [11]. These open questions are left for future work.

heading: 5 Experiments
text: We compare regularized Frank-Wolfe with existing methods on the semantic segmentation task, in terms of both inference and learning performance. Two variants, namely Euclidean Frank-Wolfe (`2FW) and Entropic Frank-Wolfe (eFW) (§3.3), will be compared to the following methods: Mean field (MF) [34, 35] (which is our baseline), nonconvex vanilla Frank-Wolfe (FW) [41] (§2.3), projected gradient descent (PGD) [39, 41], fast proximal gradient method (PGM) [9, 48], and alternating direction method of multipliers (ADMM) [40, 41]. Convex vanilla Frank-Wolfe [21] and (entropic) mirror descent [8, 55] were found to perform poorly in our experiments, and thus excluded from the presentation. Other methods based on CCCP [21] or LP relaxation [1, 21] are also excluded due to their sophisticated implementations. For all methods, we set the initial solution to x0 = softmax( u), following previous work [34]. Further details on implementation, running time, and memory footprint can be found in Appendices D–E.

heading: 5.1 Experimental setup
text: Our segmentation model is a standard combination of a CNN and a CRF [35, 76] (Appendix E.1). For the CNN part, we consider two strong architectures: DeepLabv3 with ResNet101 backbone [16], and DeepLabv3+ with Xception65 backbone [17]. The CRF part is a fully-connected one [34] in which any pair of pixels (i, j) is an edge with potential ✓ij(s, t) = µ(s, t)k(fi, fj) 8s, t 2 S, where µ : S ⇥ S ! R is called label compatibility function, and k is a Gaussian kernel over image features based on pixel coordinates and colors. The setup of our models are similar to Zheng et al. [76]. We use the Potts compatibility function: µ(s, t) = w [s 6=t] with w = 1 for the inference experiments in §5.2, and also for CRF initialization in the learning experiments in §5.3. For all experiments, a fully-trained CNN is needed. We follow closely the published recipes [16, 17] for this task. We first pretrain DeepLabv3 and DeepLabv3+ on the COCO dataset [46] and then finetune them on PASCAL VOC (trainaug) and Cityscapes (train) to obtain similar results to previous work [16, 17] (Table 1, CNN column). Finally, we perform experiments on two popular datasets: (augmented) PASCAL VOC [22] and Cityscapes [19]. Further details are given in Appendix E.

heading: 5.2 Inference performance
text: In this section, we compare the performance of regularized Frank-Wolfe against the competing methods in terms of inference. We consider a Potts CRF on top of a CNN, which is the typical setup for using dense CRF in post-processing. Figure 1a shows the discrete energy per inference iteration for each method, averaged over the 1449 val images of PASCAL VOC, using DeepLabv3+. One can observe that Frank-Wolfe variants completely outperform the other methods. In addition, regularized Frank-Wolfe outperforms all the other methods for a large range of , as shown in Figure 1b.
Table 1 shows the performance on the validation sets of PASCAL VOC and Cityscapes, for a Potts CRF with both DeepLabv3 and DeepLabv3+ as backbone. In this experiment, we run all the methods for 10 iterations. One can observe that `2FW achieved the best performance, followed by eFW.
We should note some inconsistency compared to the energy results previously presented in Figure 1a. For example, eFW achieved much lower energy than MF, yet the mIoU gap is marginal; also, FW accuracy is slightly worse than MF while the energy is much better (lower). This can
be explained by the fact that the Potts model is not a perfect representation (i.e., lower energy in this model does not necessarily translate to higher accuracy). In the next section, we will see how the methods perform when the CRF parameters are learned from data.

heading: 5.3 Learning performance
text: In this section, we evaluate the performance of the methods for joint CNN-CRF end-to-end training. The CNN is initialized with its fully-trained weights on the corresponding dataset, and the CRF is initialized with the Potts model with random noise added. We train the model for 20 epochs with 5 CRF iterations,9 using the same poly schedule as before. As the CNN has been already fully-trained, we set its learning rate to a small value of 0.0001. For the CRF, we tried 4 different values of initial learning rates ⌘0 2 {1.0, 0.1, 0.01, 0.001} and found that 1.0 is too high (training diverges quickly) while 0.001 is too low (slow progress) for all methods. For the remaining candidates {0.1, 0.01}, we perform 4 additional trainings for each method (i.e., a total of 5 runs for each configuration).
Let us summarize our findings. First, we observe that (vanilla) FW fails to learn. This is illustrated in Figure 1c, where we show the validation accuracy per epoch on PASCAL VOC for each method: FW did not make any progress. We tried a different optimizer (Adam [33]) and obtained similar results. This is expected as the gradient in vanilla FW is zero almost everywhere, as previously discussed in §3.1 (see also §C.1). Our second observation is that training is quite unstable for PGD, PGM, ADMM, eFW.3, and `2FW. In particular, ⌘0 = 0.1 is still too high for these methods, and even with ⌘0 = 0.01, some of the runs produced bad results. By contrast, MF and eFW.7 are stable for both learning rates, with 0.1 being slightly better. A possible explanation is that PGD, PGM, ADMM, and `2FW all employ a simplex projection step that is not fully differentiable (but only so almost everywhere). For eFW.3 (which is fully differentiable), we hypothesize that the low regularization makes the problem less “smooth”, which may also harm gradient-based training. Finally, with the above training scheme, we observe that none of the CRF methods could improve over the CNN (but rather the opposite) on Cityscapes. We have seen that the Potts CRF was able to achieve some marginal improvements (Table 1), thus it is reasonable to expect even better performance with end-to-end training.
In view of the above observations, we present a simple trick to make CRF training more stable. The idea is to replace the CRF output x⇤ with 12 (x
⇤ + x0), where we recall that the initialization x0 is the softmax of the CNN logits. Intuitively, this adds a skip connection from the CNN to the CRF output in the computation graph, which makes the gradient of the loss propagate directly to the CNN. We found that this trick also slightly improves eFW.7, but has a negative effect on MF. Therefore, it is applied to all methods except MF. Finally, as Cityscapes requires a very high number of epochs, we set this value to 100. Also because training on Cityscapes requires a lot more computing resources, we only perform a single run on DeepLabv3+. The results are presented in Table 2.
9While we use the same number of iterations at test time to simplify the evaluation protocol, it should be noted that using more iterations could be beneficial. See Appendix F.3 for some results.
Again, `2FW consistently achieves the best results. Interestingly, while eFW.3 achieved similar performance to `2FW in terms of energy minimization (Figure 1a and Table 1), its performance is worse in joint training. Compared to Table 1, we see that joint training produced much larger
improvements over the CNNs, up to 2.25% on PASCAL VOC and 0.4% on Cityscapes.
Performance on the test sets We select the best performing method (DeepLabv3+ with `2FW CRF) for evaluation on the test sets. For PASCAL VOC, we further train our model on the union of the train and val subsets for 50 epochs. For Cityscapes, we further train 200 epochs on train and train_extra, using the high-quality annotations provided by Tao et al. [70] (for train_extra). At the 150th epoch, we replace train_extra with val. For this fine-
tuning step, learning rates were set to 0.001 for CNN and 0.1 for CRF. For prediction, we apply test time augmentation including left-right flipping and multi-scales. For reference, we train DeepLabv3+ alone using the same recipes. Table 3 shows that we were able to closely match the performance reported by Chen et al. [17]. Adding the `2FW CRF yields an improvement of 0.4 points on PASCAL VOC. Unfortunately we only observe a marginal improvement on Cityscapes.

heading: 5.4 Ablation studies
text: Trainable ↵k and It is possible to learn ↵k and from data by simply setting them to be trainable. We carried out such an experiment with `2FW and eFW but did not observe significant improvements, though we should note that a more sophisticated training recipe (e.g., using custom learning rates for these variables) might lead to better results. Details are provided in Appendix F.2.
Fine-grained analysis We observe that CRF improved over CNN on most of the semantic classes. In particular, on bicycle (known to be the most challenging class of PASCAL VOC [16]), `2FW and eFW achieved improvements of over 10% absolute in mIoU. See Appendix F.3 for the details.

heading: 6 Discussion & conclusion
text: Why does it work? Theoretically, all the methods in §5 should reach a stationary point, so how can one be better than another? In fact, Figure 1a only shows that Frank-Wolfe variants work better than the other methods in the first few iterations, but not necessarily in a later stage. Indeed, the same conclusion no longer holds after 100 iterations (see §F.4), but this long regime is not practical because it would lead to vanishing/exploding gradients [76] and to potentially prohibitive memory consumption. As to why Frank-Wolfe achieves lower energy in the early stage, we hypothesize that this could be due to the discreteness of its iterates (7). With small , the solution by regularized FrankWolfe should be close to the vanilla one, and thus also benefits from this property. It is important to note that the benefit of regularized Frank-Wolfe does not lie in the extra (sometimes small) energy improvement over vanilla Frank-Wolfe, but in its ability to seamlessly solve the zero-gradient issue.
How to tune ? We found that similar curves to Figure 1b can be obtained using a small random subset (e.g., 10 samples) of the data, which suggests a quick way of tuning by random subsampling. In practice, this step takes only a few seconds, which is negligible in most training scenarios.
Limitations While one variant of regularized Frank-Wolfe (`2FW) consistently achieves the best results, the difference compared to the other methods is sometimes small. In addition, the improvement of dense CRFs over CNNs is marginal on the Cityscapes test set. Nevertheless, we hope the encouraging results on PASCAL VOC could attract interest from the community in CRF research, potentially leading to creative ways of overcoming these limitations.
Societal impact Semantic segmentation models can be used in surveillance systems, which might raise potential privacy concerns. Furthermore, the datasets that our models were trained on are known to present strong built-in bias [71], thus they should be used with caution.
Acknowledgments and Disclosure of Funding
This work was supported in part by the ANR grant AVENUE (ANR-18-CE23-0011), and was partly done when the first author was affiliated with Manifold Perception (mption.com). The experiments were performed using HPC resources from GENCI-IDRIS (Grants 2020-AD011011321 and 2020- AD011011881). The authors thank the anonymous reviewers and meta-reviewer for their constructive feedback that helped improve the manuscript.

Review summaries:
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.

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.