We turn to Frank-Wolfe variants for nonsmooth objectives, since Frank-Wolfe methods are well-suited to our structured ranking problem [1]}, [2]}, [3]}. More precisely, following [4]}, [5]}, [6]}, our algorithm uses the Moreau envelope of GGFs for smoothing. The usefulness of this smooth approximation depends on its gradient, which computation is in some cases intractable [7]}. Our main technical contribution is to show that the gradient of the Moreau envelope of GGFs can be computed in \(O(n \log n)\)  operations.
