Our work builds on nonsmooth convex optimization methods [1]}, [2]}, and in particular variants of the Frank-Wolfe algorithm [3]}, [4]} for nonsmooth problems [5]}, [6]}, [7]}, [8]}. The recent algorithm of [8]} is a Frank-Wolfe variant which uses the Moreau envelope like us. Its number of first-order calls is optimal, but this is at the cost of a more complex algorithm with inner loops that make it slow in practice. In our case, since the calculation of the gradient is not a bottleneck, we use the simpler algorithm of [5]}, which applies Frank-Wolfe to the Moreau envelope of the nonsmooth objective.
