Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond
Authors: D. Khuê Lê-Huu
Karteek Alahari
Venue: NeurIPS 2021 Poster (2021)
Keywords: mean field
frank-wolfe
conditional gradient
crfs
mrfs
conditional random fields
markov random fields
map inference
semantic segementation

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.

Regularized Frank-Wolfe for Dense CREs:
Generalizing Mean Field and Beyond
D.Khuē Lê-Huu
Karteek Alahari
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK 38000 Grenoble, France
{khue 1e, karteek. alahhri)@iiriis fr
Abstract
We introduce regularized Frank- Frank-Wolfe, a general and effective algorithm for in- ference and learning of dense conditional random fields (CRFs). The algorithm optimizes a nonconvex continuous relaxation of the CRF inference problem using vanilla Frank-Woll with approximate updates, which equivalent minimizing a regularized energy function. Our proposed method a generalization of existing algorithms such as mean field 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 infer- ence, 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.
Introduction
Fully-connected or dense conditional random fields (CRFs) comj-ne with strong pixel-level
classifiers such 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 include CRF as either post-processing step [13, 14, 15, 20, 43, 44, 45] or trainable component [4, 49, 64, 68, 73, 76]. However, CNNs got stronger, the improvements that CRFs brought decreased over time, and as 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- Frank-Wolfe, new class of algorithms for inference and learning of CRFs that perform better than the popular mean field [34, 35, 58h 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-gradin minimizing 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 also includes several existing methods, including mean field and the concave-conwe 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). particular, we show that they achieve a sublinear rate of convergence (l/V/k) 3) for suitable stepsize schemes, and certain cases (such as strongly-convex regularizer or concave energy) this can be improved to O(1/k) (64.1). Furthermore, we provide 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-bant based learning via backpropagation [47, 62].
updates ($3.) I). which is equivalent to
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Our second contribution lies on the practical side. In addition to mean field and regularized Frank- Wolfe variants, we re-implement several existing first-order inference methods [39, 41, [8]-those that are amenable to gradient-based learning- for comparison. Remarkably, we find that dense CRFs can still achieve important improvements over the strong DeepLabbv3+ [17] CNN model for all these solvers ($5). In particular, our best variant of regularized Trank-Wolff achieves mean intersection-over-unioo (mloU) 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 made publicly available under the GNU general public license for this purpose.
2 Background
2.1 Inference in CRFs
Let E S ... x Sn denote an assignment to discrete random variables Si,..., Sp. where each variable S; takes values a finite set of states (or labels) S,. Let g = -V, E) be a graph of n nodes (V {1, 2, ..... n)). A Markov random field (MRF) defined by & encodes a family of joint distributions that can be factorized as follows, where o; : S, - R+ and Φij : :S; x S + R are the so-called unary and pairwise (respectively) potential functions, and Z is a normalization factor:
p(s)
1
II (s)) iEV
II (82, WEEE
Z
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 o, e.g., 08) and this model is referred 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: S, = S Vi, with cardinality d = |S). It is convenient to express p(s) as ž exp(-e(s)). where the so-called energy e(s) is defined
e(s) = Σ 0((s)) + Σ (sy(s,,))) with (s;) = log (s:) (idem for 0:y))
(2)
REV
DEE
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 p(s) = argmin e(s).
sES"
SES*
2.2 Continuous relaxation of MAP inference
Let dis be binary variable such that dis = iff label is assigned to node Then, x; = (rrs)s
{0, 1 denotes the one-hot vector for node i. Let x E 10, be the concatenation of all x,, and
let 0; = (0I(s))<Es E RRd, Oij = (15(,,()))E E IRdxd, The energy (2) is then
Exx; = Σe AT x;
iEV
FEEE
where is parameter vector composed of all 0, and Oij. The MAP inference problem (3) transforms minimizing E(x; f) over the new variables x. natural approach is to relax the binary constraint and solve the continuous relaxation minxex [xx; 0) with
X = {x fx Rnd x h 0, 1 = =
(5)
This continuous relaxation is known be right [10, 41, 61]. For convenience, we represent the unary potentials as vector u(O) jivv E Rndd and the pairwise potentials as symmetric n x block matrix P(0) E ndd where the (i. block is O,g. The problem is reduced to
min E xx 0) & 2 P(())x u XEX
(6)
'https://github http:://hhhhu.oooo////etttt/////

---

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" (4) and (6) is a function of 0, and thus should be written as x" (0). Therefore, when we say solution is differentiable, is understood that it so with respect to 0. When there is no ambiguity, we omit and write simply Ex 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 x ELP(x: f). where ELP 0) 0 x and XLP is the so-called local polytope [72]. We refer to Appendix for the details.
2.3 Vanilla Frank- Wolfe algorithm for MAP inference
Since the continuous energy is differentiable, it is natural to apply first-order methods such Frank- Wolfe [23] to solving (6) [41]. Starting from a feasible x" E X. Frank- approximately solves (6) by iterating the following steps, where ag E [O, 1] follows some stepsize scheme:
pd E argmin (VE(x") pEx
x x + az
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].
3 Regularized Frank- Wolfe for inference
In this section, we introduce the proposed regularized Frank-Wolfs as 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).
3.1 A smoothing perspective
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 ph in (7) piecewise constant and thus its gradient (w.r.t. 0) is zero almost everywhere (SC.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-Jconvve regularization term:
d E argmin ((VE(x*), +r()))
x A+1 - = x (p - -x*)
(
PEX
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 the opti- mization literature. For example, the classical proximal gradient method [48] can be interpreted the same way. Our update (8) is inspired by Nesterov's 's smoothing [56]. and thus is similar in spirit to its many applications [31. 57, 66]. In the next section, 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 unified manner.
3.2 A regularized energy perspective
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 E' 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 more appropriate "given algorithm", this idea can work. Such choice is the generalized Frank- Frank-Wolfe algorithm [5, 12, 53].
NNote that backpropagation typically requires the operations to be differentiable (at least) almost everywhere, which p* 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 is limited to LP relaxations.
3

---

Consider the following problem, where f R" + U {+oo) nonconvex, and g : R + R U {+00) proper, closed, and convex but possibly con-difeerentiale:
} is differentiable but possibly
min F(x) A f(x) + gx)..
x
Generalized Frank- Wolfe solves (9) by iterating
pd E argmin ((V p) g(D))
x++1 =x ax x*).
(10)
g is the indicator function ōxx of X (i.e., 6x = 0 if X and 5x(x) = +00 otherwise), then the algorithm clearly reduces to vanilla Trank-Wolff (7) for minxex f(x). Therefore, generalized Frank- Wolfe applied to (6) with f = E and = òx will yield exactly the same updates (7). Now let us apply this algorithm an approximate objective (x) Exx) + +xx) for some function Choosing f = E and = r + 6x is straightforward that (10) reduces to (8). Therefore, we have recovered the same algorithm in $3.1, but this time through different machinery.
This framework offers great flexibility as one can choose f and g in many different ways to obtain new algorithms. The only conditions are being differentiable and g being convex, so that the subproblem in (10) is well-defined and globally solvable. For example, instead of choosing I /= E and r+ ōx as above, one can choose f'(x x Px and g(x) = u 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 for (approximately) solving MAP inference (6).
Algorithm 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+ E + r + 6x. Typically (but not necessarily) r is convex on X and is constant on X n {0, 1nd
2: Initialization: k 4 0, x" X. number of iterations N.
3: Compute p* E argmin, (Vf(x*), .P) + { and compute the stepsize O*-
),)x)))))).>>))
4: Update x ++1 = x* + (p* x*). Let & <- k - 1 and go to Step 3 until k = N.
5: Rounding: convert x to discrete solution and return.
While the choice of (r; f: be highly flexible, would make little sense optimize function that has nothing to do with the original objective (i.e., the discrete energy). Let X = n (0, 1)"d denote the discrete domain of our problem. If we choose r such that is constant on X (as suggested in Step above), then minimizing E on X is equivalent to minimizing E+ 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) Trank-Wolff to optimizing such regularized energy [52, 67, 69]. All these algorithms, however, suffer from the aforemennioned graddgradeent issue, as already explained in the beginning of this section.
3.3 Particular instantiations
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."
Euclidean Frank-Woo Wolfe Perhaps the most natural choice is l regularization. In Algorithm 1, let us choose fxx Exx) and r(x) = aे ||x where À > 0 is regularization weight. Let (xx(v) be the projection of vector onto X'. can be shown ($D.1) that Step in Algorithm becomes
{
X (Px + u. + |pll
(- -w)
p argmin PEX
IIx
Wk
0.
(11)
Further mild conditions are required for convergence ($4.1). 'In proximal gradient and mirror descent, the current iterate is constrained to stay close to the previous one. while this is not the case in method. See Appendix D for the details.

---

Entropic Frank- Wolfe In Algorithm 1. let us choose f(x) = E(x) and r(x) = - XH (x), where 0 is a regularization weight and (x)) = Liev Exes Iis log Dis is the entropy of x over X. It can be shown ($D.2) that Step 3 in Algorithm becomes
argmin (Pxx u, u. (D)) softmax (- +u) PEX
pd
4k 2 (12)
0,
where softmax(x) with E Rnd means E BRd and Uis Eies exp( Vi E V.Vs E S. The resulting algorithm has a tight connection with (parallel) mean field [34, 35] (discussed $3.4).
exp(atee
Other variants One can consider more sophisticated regularizers, e.g., a weighted combination of l norm and entropy. Other options include the many different regularizers that have been used in diverse machine learning applications, such as lp 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.
3.4 Recovering existing algorithms special cases
In addition to the above new algorithms, regularized 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 special case of the above Entropic Prank-Wolfe Indeed, if we choose À = 1 in (12) and a constant stepsize ay = Ak 2 0 in Algorithm 1, then it is straightforward that this algorithm is reduced to the following update step, where N₁ is the set of neighbors of node i:
-+1 softmax( Px*
x++ 2 exp (s) ESEN, Eics O1,(s, Outt vi S.
This is precisely (parallel) mean field update [34, 35]. To conclude, parallel mean field is an instance of Entropic Trank-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 principled way to achieve that. As shown later in the experiments, with suitable X, this extension yields much better results than vanilla mean field. Finally, 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-tye variants based on the concave-convex procedure [75], while elosely 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 0g(x which is precisely (10) with stepsize ag = 1. updating = as a solution to (x* E
We conclude that CCCP a special case of generalized Frank-Wolfe with I concave and unit stepsize. As a result, many existing CCCP- regularized Frank-Wolfe. For example, the ones presented by Desmaison et al. [21] are instantiations
inference algorithms [21, 35] can be seen as special cases of
of the proposed algorithm with either f(x) = -x' diag(c)x and r(x) = E(x) + diag(c)x (where& c E Rnn is large enough so that r(x) is convex), or f(x) = x (P C)x and r(x) = u x + x Cx (where is some matrix such that ʃ is concave and r is convex). Note that in these instantiations, Step 3 in Algorithm I requires an iterative (numerical) solution. Finally, all the algorithms presented by Krähenbühh 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 special case of regularized Frank- Wolfe and we briefly discuss it for completeness. Choosing f(x) = (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 s(x)
E(x) c x + x diag( c)x and rxx) = 0, where c E Rnd is large enough for f to be convex. In addition, we can also recover existing I.P-baeed algorithms by choosing X' = Xir,, r(x) = 0, and f(x) = Fxr(x) + R(x) with suitable R(x). Indeed, the one by Meshi et al. [52] takes R(x) as the squared nnorm 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 SA).
In the original CCCP [75]. g is differentiable, thus the update becomes -vx(x*) Vg(x*t1).
5

---

4 Theoretical analysis
4.1 Convergence
We provide a convergence analysis for the generalized Frank-Wolfe algorithm, and the results for CRF inference special cases will then follow consequence. Convergence of vanilla Frank-Wood 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, as the CRF energy is often highly so in practice, Mine and Fukushima [53] (and subsequently Bredies 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(L/Vk) 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- Frrnk-Wolffe use strongly-convex regularizers. Second, to also include CCCP [75] as a special case, we relax their Lipschitz smoothness assumption on f to semi- remi-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. better (1//k) rate of convergence can be achieved, even under the (weak) constant stepsize. should be noted that our results are new.
All the results in this section are stated under the following assumptions, where Ly and By are non-negative constants and ||-I| denotes the Eg norm. Their proofs are given in Appendix B.
L. ||x|| is concave) on dom f. Assumption 1. f is differentiable and ---semi-concave (i.e., fxx 2 which is assumed to be open and convex. When L, 0. is concave.
Assumption 2. g is proper, closed, and 0 g g--ttrongyy-comee (i.e., g(x)
dx ||x|] is convex), and 2
domg C dom f is compact. When 0g 0, g is strongly convex.
Let Px denote a solution of min, fxV p) + g())} and let p* = Px The following quantity,
called the conditional gradient norm [7], will serve an optimality measure:
S(x)= (x)) x px) + g(x) g(Px).
(13)
Lemma 1. S(x 2
X
1
2 Vx E dom f, and Sxx) = 0 iff x is 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:
S(x²)
ag = min
1, Li + Jg
+
0g 2
argmin F(x + +a(p"-x*)) -x")). (14) aE/o,1
x*
2
Theorem 1. Let F be the minimum value of F, Q be the diameter of dom g. D Fx(")) F",
T p(a) = a min {1, 3). nT(a) = [[, + og)a og). and μ == /2L For any
k 0, we have minogick S(x²) BR, where the bound By is given follows:
constant stepsize a; V'k
constant step length
non-summable Σk=g ag oc L
adaptive or line search (14)
Vk
p
convex g
u(k+1] +
Ap
L
Anf 1k
LiBa
Agt
>
max
VKFT
strongly
a(k+ij An
An
n(a)EE?
va2l2
Au " (k-)
+ (1yttaa)a
Ak(w)
convex
pla)k+1j
Va
2/20g
W(R+1)
concave f
do
Ao
24g
m(k+1)
a(k+1)
Σl "
In the above, k(w) = min {k: : 0c, < 2n
Vi Vi 2ikk), k), with further assumption that limg O'k
O for (jointly) non-concave f and non-summable ak- For the non-highlighted cases, we have lim S(x*) 0 and any limit point of the sequence (x*) is stationary point of (9).
The table in Theorem 1 also provides rates of convergence for the algorithm. Prior to our work, the O(L/Vk) rate for the adaptive line-search stepsizes (top-right cell of the table, due to Beck [7])
'Note that g is still assumed to be convex, so that the subproblem (10) be solved to global optimality.

---

was the best for nonconvex objectives." We have improved this rate to (11/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 / is concave, for which the best bound is obtained when og = Vk, 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 ag 2/(k + 2) or ogg: = =1/ 1/),), but the rate depends on the rate of divergence of > Otg. 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 rate of convergence of at least ((1/k) in practice for these algorithms under the adaptive, line search, or (suitable) constant stepsizes. Note that the adaptive scheme requires to know Ly and gg. which is possible in case: lower bound 0g is À for both euclidean and entropic variants, while an upper bound on T.g is |Pl|| 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 known phenomenon [6]: damped mean field (corresponding to Entropic Frank-Wolfe with À and ay < 1 4k) is more likely (than mean field) to guarantee convergence when the energy is not concave.
4.2 Tightness of the relaxation
We have seen that regularized Frank- (Algorithm 1) minimizes a modified continuous energy. It is thus reasonable 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 guaran- tee 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 consists in converting rounding schemes. The simplest one is perhaps nearest rounding, which assigns each node i with the label 8; E argmax,es Fit- Intuitively, this sets x; to the nearest vertex of the simplex {x; RR 1 TT,
discrete solution. We consider two such
x; = 1}. The second scheme, called BCD rounding [41, 61], consists in minimizing E(x) over x; while keeping all X, Õ # i) fixed (i.c., block coordinate descent), which amounts to iteratively assigning each node with label 8; E argmin { (,(s)) + EjeM: Eies (sy ()aja 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 be global minimum of Ex(x = E(x) + r(x) over X, X be the dis- crete solution rounded from x,, and E* be the minimum discrete energy. Assume that r(x) is bounded: S r(x)= < M 7x E X. We have Ex < B(x;) S E + M -m + C, where
C= n (1 2) (1ull2 + Vnl Pl2)) for nearest rounding and C = 0. BCD rounding.
L=Vn(e
Let 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;) < F < E(x;),, yielding F(x;) = E., i.e., the relaxation is tight. We have thus recovered a previously known result [10, 41, 61]. For r(x) = -c T T diag(c)x with > O, we have M 0 and which recovers exactly the additive bound given by Ravikumar and Lafferty [61] for the convex QP relaxation. For the & regularizer r(x) = A | we have M = An and m = An
-
27 thus we
2
2
obtain a bound of An (1-1), For the entropy regularizer r(x) = -XH(xx,, we have M = 0 and 2 m An log d, thus the bound is An log d, which is worse than the E2 bound for any d 2 5.
'If both f and g are convex, better rate of O(1kk) exists [5. 7, 74). In addition, if 9 is the indicator function of 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 these analyses, due to the nonconvexity. A sufficient condition is r being continuous, as X is compact.
7

---

Note that the bound provided by Theorem 2 is achieved from 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 (c.g., supermodular ones), similar to some existing algorithms [11]. These open questions are left for future work.
Experiments
We compare regularized Frank-Wolfs with existing methods on the semantic segmentation task, in terms of both inference and learning performance. Two variants, namely Euclidean Frank-Wolfe (f2FW) and Entropic Frank- (cFW) ($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, 41J. 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 CCCP [21] or LP relaxation [1, 21] are also excluded due to their sophisticated implementations. For all methods, we set the initial solution to x" mollmax(-u)) following previous work [34]. Further details on implementation, running time, and memory footprint can be found in Appendices D-F.
5.1 Experimental setup
Our segmentation model is standard combination of CNN and a CRF [35, 76] (Appendix E. For the CNN part, we consider two strong architectures: DeepLabv3 with ResNet101 backbone [16]. and DeepLaby3+ 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 0.y (s, f) = p(s, (E, f,) Vs, S, where ::S. S x 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 [76]. We use the Potts compatibility function: p f) = w [s [s with = 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 (Irain) 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.
5.2 Inference performance
In this section, 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 la 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-Wolfé outperforms all the other methods for a large range of X, as shown in Figure 1b.
Table 1 shows the performance on the validation sets of PASCAL VOC and Cityscapes, for Potts CRF with both DeepLabv3 and DeepLabv3+ 3+ as backbone. In this experiment, we run all the methods for 10 iterations. One can observe that FW achieved the best performance, followed by eFW.
We should note some inconsistency compared to the energy results pre- viously presented in Figure la. 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 en- ergy is much better (lower). This can
CNN PGD PGM ADMM MF
FW
cFW;
cFWs
&FFW
DL3
81.83
82.23
82
82.
82.21
82.27
62.26
82 29 82 29
DL3+ 82.89
83.36 83.37
83
83.15
83.43
83.45
83. 18 83.50
DL3 76.73
76.88 76.86
76.95
76.97
76.86
76.99
76.99
77.03
T DL3+ 79.55 79.64 79.63
79.66
79.63
79.61
79.65
79.66
79.66
Table 1: Validation mlou using Potts CRF top of the pre- trained CNN models. DL. means DeepLab.
8

---

Discrete energe
Discreto energy after 5 iterations
mloti
dPW (((())
PGD
4PN (m43)
PIM
63.60
4PW-1
-19-
1WW
83.05
63.50
PGM
-2-
-2-
ADMM
83.40
PW (Adam)
-2.1m
-21
(25W--1
83.85
10
20
CRP seeations
Regularization weight
Training opechs
(a) Discrete energy comparison.
(b) Effect of regularization weight. (c) Learning failure of vanilla FW.
Figure Results on PASCAL VOC validation set using DeepLabv3+ and Potts dense CRF, (a) Comparison between CRF solvers ( means ag = k/(k + 2) vk) shows that Frank- Wolfe variants elearly outperform the other methods in terms of energy minimization. (b) Performance of regularized Frank-Wolfe can be greatly affected by A, but it can still achieve lower energies than the other methods for large range of X. (c) Vanilla Woolf completely fails learn because of the zero-gradient issue.
be explained by the fact that the Potts model is not 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.
5.3 Learning performance
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 CRF iterations, using the same poly schedule 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 17u E {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 10.1, 0.01), we perform additional trainings for each method (i.e., total of 5 runs for each configuration).
Let us summarize our findings. First, we observe that (vanilla) FW fails to learn. This 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, 1 (see also $C. )). Our second observation that training is quite unstable for PGD, PGM, ADMM, eFW3, and FW. In particular, no 0.1 is still too high for these methods, and even with 7/0- 0.01, some of the runs produced bad results. By contrast, MM and eFW, are stable for both learning rates, with 0.1 being slightly better. A possible explanation is that PGD, PGM, ADMM, and FF all employ a simplex projection step that is not fully differentiable (but only so almost everywhere). For eFWs (which is fully differentiable), less "smooth", which may also harm gradient-base 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.
previously discussed in
hypothesize that the low regularization makes the problem training. Finally, with the above training scheme,
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 1 (x* +x"), where recall that the initialization x" 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,, but has a negative effect on MF. Therefore, is applied to all methods except MF. Finally, Cityscapes requires very high number of epochs, set this value to 100. Also because training on Cityscapes requires a lot more computing resources, we only perform single run on DeepLabv3+, The results are presented in Table 2.
While 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, f2FW consistently achieves the best results. Interestingly, while eFW.3 achieved similar performance to F2FW in terms of energy minimiza- tion (Figure la and Table 1), its per- formance is worse in joint training. Compared to Table 1, we see that
CNN
PGD
PGM
ADMM
MF
<FW,
<FW,
6F
DL3
81.83 83,69 83.
83.68
83.69
83.50
83.25
83
VOC
20.13
DL3+
82.89
84,
84.83
84.87
84.64
84.50
20:33
30.00
CITY DL3+ 79.55 79.80
79.62
79.62
79.74
79.70
79.58
79.95
Table 2: Validation mloU under joint training. For PASCAL VOC, report the mean and standard deviation from 5 runs.
joint training produced much larger improvements over the CNNs, up to 2.25% PASCAL VOC and 0.4% on Cityscapes.
Performance on the test sets We select the best per- forming method (DeepLabv3+ with &zFW CRF) for evalu- ation 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 _xtra, using the high-quality annota- tions provided by Tao et al. [70] (for
Model
VOC
CITY
DeepLabv3+ [17]
87.8
82.1
DeepLabv3+ (this work)
87.6
83.5
Deepl.ahv3+ with &PFW CRF
88.0
83.6
Table 3:
Performance on the test sets. Sub- mission URLs are given in Appendix F.1.
At the 150th epoch, we replace rain_extra with val. For this fine- tuning step, learning rates were set to 0.001 for CNN and 0.1 for CRF. For prediction, apply test time augmentation including left-right flipping and multi-scales. For reference, we train D 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 FW CRF yields an improvement of 0.4 points on PASCAL VOC. Unfortunately we only observe a marginal improvement on Cityscapes.
5.4 Ablation studies
Trainable ag and À is possible to learn ag and from data by simply setting them to be trainable. We carried out such an experiment with F2 and eFW but did not observe significant improvements, though we should note that 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]), &F and eFW achieved improvements of over 10% absolute in mloU. See Appendix F.3 for the details.
Discussion & conclusion
Why does it work? Theoretically, all the methods in $5 should reach stationary point, so how can one be better than another? In fact, Figure la only shows that Frank-War 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 not practical because it would lead to vanishing/exploding gradients [76] and to potentially prohibitive memory consumption. As why Frank- Wolfe achieves lower energy the early stage, we hypothesize that this could be due to the discreteness of its iterates (7). With small X, the solution by regularized Frank- Wolfe 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 X? 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 X by random subsampling. In practice, this step takes only a few seconds, which negligible in most training scenarios.
Limitations While one variant of regularized Frank- Wolfe (L)FW) consistently achieves the best results, the difference compared to the other methods is sometimes small. In addition, the improve- ment of dense CRFs over CNNs is marginal encouraging results on PASCAL VOC could attract interest from the community in CRF research, potentially leading creative ways of overcoming these limitations.
the Cityscapes test set. Nevertheless, hope the
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.
10

---

Acknowledgments and Disclosure of Funding
This work was supported part by the ANR grant AVENUE (ANR-I8-CE23-00) I), 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-AD01 1321 and 2020- AD01101 1881). The authors thank the anonymous reviewers and meta-reviewer for their constructive feedback that helped improve the manuscript.
References
[1] Thalaiyasingam Ajanthan, Alban Desmaison, Rudy Bunel, Mathieu Salzmann, Philip HS Torr, and M Pawan Kumar. Efficient linear programming for dense erfs. In Computer Vision and Pattern Recognition, 2017.
[2] Thalaiyasingam Ajanthan, Puneet K Dokania, Richard Hartley, and Philip HS Torr Proximal mean- field for neural network quantization. In Proceedings of the IEEE International Conference on Computer Vision, pages 4871-4880 2019.
Brandon Amos, Vladlen Koltun, and J Zico Kolter. The limited multi-label projection layer. arXiv preprint arXiv:990600877,, 2019.
[4] Anurag Arnb, Sadeep Jayasumana, Shuai Zheng, and Philip HS Torr. Higher order conditional random fields in deep neural networks. In European Conference on Computer Vision, pages $24-540. Springer. 2016.
Francis Bach. Duality between subgradient and conditional gradient methods. SIAM Journal on Optimiza- rion, 25(1):115-1299 2015.
[6] Pierre Baqué, Timur Bagautdinov, François Fleuret, and Pascal Fua. Principled parallel mean-field inference for discrete random fields. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5848 5857, 2016.
Amir Beek. First-order methods optimization. SIAM, 2017.
[8] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett., 3175):1671775, 2003.
[9] Amir Beck and Mare Teboulle. A fast iterative sarinkage-threshole algorithm for linear inverse problems. SIAM J. Imaging Sci., 2(1): 182-202 2009.
[10] Mare Berthod Definition of consistent laheling a global extremum. In International Conference on Pattern Recognition, pages 339-341, 1982.
[11] Yatao An Bian, Joachim M. Buhmann, and Andreas Krause. Optimal continuous dr-submodular maximiza- tion and applications to provable mean field inference. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 644 653. PMLR, 2019.
[12] Kristian Bredies, Dirk A Lorenz, and Peter Maass. generalized conditional gradient method its connection to an itcrative shrinkage method. Computational Optimization and Applications, Advanced online publication, 2007. doi: 10. 10871/0000900-098883333
[13] Siddhartha Chandra and lasonas Kokkinos. Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian erfs. In European conference computer vision, pages 402-418. Springer, 2016.
[14] Liang-Chie Chich Chen, Yi Yang. Jiang Wang. Wei Xu, and Alan L Yuille. Attention to scale: Scale-aware semantic image segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3640-3649, 2016.
[15] Liang-Chieh Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected erfs. IEEE transactions on pattern analysis and machine intelligence, 40(4):834-848, 2017.
[16] Liang- Chinh Chen, George Papandreou, Florian Schroff, and Hartwig Adam. Rethinking atrous convolution for semantic image segmentation. arXiv preprint arXiv:1706.0 1706.0587... 2017.
11

---

[17] Liang- Chigghhhhhhhhh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam. Encoder-decoder with atrous separable convolution for semantic image segmentation. In Proceedings of the European conference on computer vision (ECCV), pages 801-818, 2018
[18] Laurent Condat. Fast projection onto the simplex and the & ball. Mathematical Programmingg 158(1-2): 575-585, 2016.
[19] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bert Schiele. The cityscapes dataset for semantic urban scene understanding. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3213-3223
2016.
[20] Jifeng Dai, Kaiming He, and Jian Sun. Boxsup: Exploiting bounding boxes supervise convolutional networks for semantic segmentation. Proceedings of the IEEE international conference on computer vision, pages 1635-1643, 2015.
[21] Alban Desmaison, Rudy Bunel, Pushmeet Kohli, Philip HS Torr, and Pawan Kumar. Efficient continuous relaxations for dense erf. In European Conference on Computer Vision, pages 818-833. Springer, 2016.
[22] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual ohject classes (voe) challenge. International journal of computer vision, 88(2):303-338, 2010.
[23] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95- 110. 1956.
[24] Robert M Freund and Paul Grigas. New analysis and results for the frank-wolfe method. Mathematical Programming, 155(1-2):199-2300 2016.
[25] Kunihiko Fukushima. Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position. Biological cybernetics, 36(4):193-202, 1980.
[26] 7aid Harchaoui, Anatoli Juditsky, and Arkadi Nemirovski. Conditional gradient algorithms for norm- regularized smooth convex optimization. Mathematical Programming, 152(1-2)775-112 2015.
[27] Bharath Hariharan, Pablo Arbeláez, Ross Girshick, and Jitendra Malik. Simultancous detection and segmentation. In European Conference on Computer Vision, pages 297-312 Springer, 2014.
[28] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint 15030030,..,531, 2015.
[29] Hu and Guillaume Obozinski. Sdca-powered inexact dual augmented lagrangian method for fast CRF learning. In AISTATS, volume 84 of Proceedings of Machine Learning Research, pages 988-997. PMLR, 2018.
[30] Martin Jaggi. Revisiting frank-wolfs Projection- free sparse convex optimization. Proceedings of the 30th international conference on machine learning, pages 427-435,200 2013.
[31] Vladimir Jojie, Stephen Gould, and Daphne Koller. Accelerated dual decomposition for map inference, In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 503-510, 2010.
[32] Thomas Kerdreux, Lewis Liu, Simon Lacoste-Julien, and Damien Scieur. Affine invariant analysis of frank-wolfe strongly convex sets. In /CML, volume 139 of Proceedings of Machine Learning Research, pages 1398-5408- PMLR, 2021.
[33] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
[34] Philipp Krähenbühl and Vladlen Koltun. Efficient inference in fully connected erfs with gaussian edge potentials. In Advances in neural information processing systems, pages 109-117, 2011.
[35] Philipp Krähenbühl and Vladlen Koltun. Parameter learning and convergent inference for dense random fields. In International Conference Machine Learning, pages 513-521, 2013.
[36] Simon I Lacoste-Julien and Martin Jaggi. On the global lincar convergence of frank-wolfe optimization variants. In Advances in neural information processing systems, pages 496-504, 2015.
[37] John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth International Conference on Machine Learning, ICML '01, pages 282- 289, 2001. ISBN 1-55860-778-1.
12

---

[38] Guanghui Lan. The complexity of large-scale convex programming under linear optimization oracle. arXiv preprint arXiv:1309.5530, 2013.
[39] Mäns Larsson, Anurag Arnab, Fredrik Kahl, Shuai Zheng, and Philipp Torr. A projected gradient descent method for crf inference allowing end-to-end training arbitrary pairwise potentials. In International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pages 564-579. Springer, 2017.
[40] D. Khuê Lê-Huu and Nikos Paragios. Altemating direction graph matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4914-4922, 2017.
[41] D. Khuê Lê-Huu and Nikos Paragios. Continuous relaxation of map inference: A nonconvex perspective. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5533-5541, 2018.
[42] Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applicd to handwritten zip code recognition. Neural computation, I (4):541-55/ 1989.
[43] Xiaoxiao Ziwei Liu, Ping Luo, Chen Change Loy, and Xiaoou Tang. Not pixels are equal: Difficulty- aware semantic segmentation via deep layer cascade. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 31 1193-3202, 2017.
[44] Guosheng Lin, Chunhua Shen, Anton Van Den Hengel, and Ian Reid. Efficient piecewise training of deep structured models for semantic segmentation. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 3194-3203, 2016.
[45] Guosheng Lin, Anton Milan, Chunhua Shen, and lan Reid. Refinenet: Multi Multi-path refinement networks for high-resolution semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1925-1999 1925-193,2222 2017.
[46] Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European conference on computer vision, pages 740-755. Springer, 2014.
[47] Seppo Linnainmaa. The representation of the cumulative rounding error of an algorithm as a taylor expansion of the local rounding errors. Master's 's Thesis (in Finnish), University of Helsinki, pages 6-7, 1970.
[48] Pierre-Louis Lions and Bertrand Mercier. Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6):964-979, 1979.
[49] Ziwei Liu, Xiaoxiao Li, Ping Luo, Chen-Change Lay, and Xiaoou Tang. Semantic image segmentation via deep parsing network. Proceedings of the IEEE international conference on computer vision, pages 1377-1385, 2015.
[50] Francesco Locatello, Rajiv Khanna, Michael Tschannen, and Martin Jaggi. A unified optimization view generalized matching pursuit and folfk-wolfe. In AISTATS, volume 54 of Proceedings of Machine Learning Rexearch, pages 860-868. PMLR, 2017.
[51] Julien Mairal. Optimization with first-order surrogate functions. In International Conference on Machine Learning, pages 783-791, 2013.
[52] Ofer Meshi, Mehrdad Mahdavi, and Alex Schwing. Smooth and strong: Map inference with linear convergence. In Advances in Neural Information Processing Systems, pages 298-306, 2015.
[53] Hisashi Mine and Masao Fukushima. A minimization method for the sum of convex function and continuously differentiable function. Journal of Optimization Theory and Applications, 33(1):9-22 22, 1981.
[54] Miguel Monteiro, Mário AT Figueiredo, and Arlindo I. Oliveira. Conditional random fields as recurrent neural networks for 3d medical imaging segmentation. arXiv preprint 11f.::8807.074444 2018
[55] Arkadij Semenovië Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[56] Yurii Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1): 127-152. 2005. ISSN 0025-5610.
13

---

[57] Vlad Niculae and Mathieu Blondel. A regularized framework for sparse and structured neural attention. In Advances in neural information processing systems, pages 3338-3348, 2017.
[58]
Giorgio Parisi. Statistical field theory. Addison- 1988.
[59] Fabian Pedregosa, Geoffrey Négiar. Armin Askari, and Martin Jaggi. Linearly convergent frank-wolfe without line-search. In AISTATS, volume 108 of Proceedings of Machine Learning Rexearch, pages 1-10. PMLR, 2020.
[60] Marin Vlastelica Pogancic, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinck. Differentiation of blackbox combinatorial solvers. In ICLR. OpenReview.net, 2020.
[61] Pradeep Ravikumar and John Lafferty. Quadratic programming relaxations for metric labeling and markov random field map estimation. In Proceedings of the 23rd international conference on Machine learning, pages 737-744, ACM, 2006.
[62] David E Rumelhart, Geoffrey E Hinton, and Ronald Williams. Learning representations by back- propagating errors. nature, 323(6088):533 536, 1986.
[63] Alexander G Schwing and Raquel Urtasun. Fully connected deep structured networks. arXiv preprint arXiv: 1003v23503.0235. 2015.
[64] Falong Shen, Rui Gan, Shuicheng Yan, and Gang Zeng, Semantic segmentation via structured patch prediction, context orf and guidance crf. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 1953-1961, 2017.
[65] Solomon Eyal Shimony. Finding maps for belief networks is np-hard. Artificial Intelligence, 68(2): 399-410. 1994.
[66] Hyun Oh Song. Ross Girshick, Stefanie Jegelka, Julien Mairal, Zaid Harchaoui, and Trevor Darrell. On learning to localize objects with minimal supervision. In ICML-31st International Conference on Machine Learning, volume 32, pages 1611-1619. JMLR, 2014.
[67] David A. Sontag and Tommi S. Jaakkola. New outer bounds on the marginal polytope. In NIPS, pages 1393-1400. Curran Associates, Inc., 2007.
[68] Haiming Sun, Di Xie, and Shiliang Pu. Mixed context networks for semantic segmentation. arXiv preprint arXiv:6610005854, 2016.
[69] Kui Tang. Nicholas Ruozzi. David Belanger, and Tony Jebara. Bethe learning of graphical models via MAP decoding. In AISTATS, volume 51 of JMLR Workshop and Conference Proceedings, pages 1096-1104. JMLR.org, 2016.
[70] Andrew Tao, Karan Sapra, and Bryan Catanzaro. Hierarchical multi-scale attention for semantic segmenta- tion. arXiv preprint arXiv:2005. 10821, 2020.
[71] Antonio Torralba and Alexei A. Efros. Unbiased look dataset bias. In CVPR, pages 1521-1528. IEEE Computer Society, 2011.
[72] Martin Wainwright, Tommi S Jaakkola, and Alan S Willsky, Map estimation via agreement on trees: message- message-passing and linear programming. IEEE transactions on information theory, 51((1):3697-377 3717, 2005.
[73] Fisher Yu and Vladlen Koltun. Multi-scale context aggregation by dilated convolutions. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedingy, 2016. URL http://arziv.. org/abs/ 1711.07122.
[74] Yaoliang Yu, Xinhua Zhang, and Dale Schuurmans. Generalized conditional gradient for sparse estimation. The Journal of Machine Learning Research, 18(1):2279553 5324, 2017.
[75] Alan Yuille and Anand Rangarajan. The concave-convex procedure (ccep). In Advances in neurul information processing systems, pages 1033-1040, 2002.
[76] Shuai Zheng, Sadeep Jayasumana, Bernardino Pareeds,,,, Vibhav Vineet, Zhizhong Su, Dalong Du, Chang Huang, and Philip HS Torr Couditional random fields recurrent neural networks. In Proceedings of the IEEE international conference on computer vision, pages 5229-1577 2015.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In Section 6.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] Our code is available at https: / //gtttub...tt////// commnettwrkkf10///f
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Some details in the main content and full details the appendix. (c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [No] We use standard datasets freely available for academic research. They are well-known so we did not mention their licenses.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] Our code and pre-trained models are available at https://githut com/ netwOrkf10w/one
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "OA9PaZ9wz2-", "reviewer": "Reviewer_nMc7", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality:  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.\n\n2) 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:\n\nKui 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.\n\n3) Some comparison of constant versus diminishing stepsize would be interesting in the experimental section.\n\nClarity:  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.\n\nSignificance:  New and improved approximate MAP / learning algorithms promise to reinvigorate works that have, at least until recently, explored the benefits of combined approaches.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, more remains to be done, but the work is a promising start.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "GuSCmZu2FVl", "reviewer": "Reviewer_HFqk", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Contributions:  \n\nThe 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.  \n\n\n\nClarity and related work:  \n\nThe presentation is clear and well-organized, the main technical details are well stated.  It is a pleasure to read the paper.  \n\nRegarding 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 \ninteresting to see whether the regularized FW has some guanrantees/advantages for this class of problems: \n\n[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.\n\n\nExperiments:  \n\nThe 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.  \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. \n\nFor the semantic segmentation task, could discuss potential  threat to user privacy when it is used for surveillance tasks.  \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6.5"}, "extra_text": {}}, {"review_id": "-f-ScwN7Pkq", "reviewer": "Reviewer_xtoq", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": " **originality**\nThe 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. \n\n**clarity/quality**\n\nThe 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.\n\nI 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.\n\nI am familiar with the CRF literature, and found the exposition sound.\n\n**significance**\nDense 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.\n\nMy 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.\n\n**magnitude of accuracy improvement**\n\nI'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?\n\n**related work**\nThe 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\"\n\nCan you comment on the relationship between this and your work?\n\n**end-to-end learning**\nCould you learn details of the FW algorithm (e.g., the step size schedule) end-to-end as well?\n\n**vanishing/exploding gradients**\nI 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)?\n\n**test-time usage**\nWhat happens when you train with 5 iterations, but use more (e.g., 25) at test time?\n\n**zero gradients**\n\nL336 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?\n\n**fine-grained analysis**\nI 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors write N/A for \"Did you discuss any potential negative societal impacts of your work?\"\n\nI 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_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)