W e introduce regularized Frank-W olfe, 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 inferenc e problem using vanilla Frank-W olfe with approximate updates, which are equivalen t to minimizing a regularized energy function. Our proposed method is a generaliz ation of existing algorithms such as mean field or concave-convex procedure. This p erspective not only offers a unified analysis of these algorithms, but also allow s an easy way of exploring different variants that potentially yield better performa nce. W e illustrate this in our empirical results on standard semantic segmentation datas ets, where several instantiations of our regularized Frank-W olfe outperform mean fie ld inference, both as a standalone component and as an end-to-end trainable layer i n a neural network. W e also show that dense CRFs, coupled with our new algorithms, p roduce significant improvements over strong CNN baselines.