Frank-Wolfe patch release might have broken InferOpt tests

[gdalle]

Hi there @matbesancon and friends,
My colleagues and I recently noticed failing tests for InferOpt.jl, even though our code hasn't changed at all. A careful comparison between the last successful CI run and the first failed CI run seems to suggest that patch releases of FrankWolfe.jl might have played a part, especially PRs #383 or #385. Our tests have to do with implicit differentiation of Frank-Wolfe outputs following this paper. The new bug we found is that the linear solver (GMRES) used within the implicit function theorem sometimes fails to converge. Could one of the two PRs I mentioned have altered your package behavior enough to cause this?

[matbesancon]

hi @gdalle, that's a very good point, we fixed some behavior in these two PRs and they would change the trajectory for the two corresponding functions away and standard FW respectively

[matbesancon]

these two PRs can reduce the gap tolerance, so might it be that the linear solve step is assuming some quasi optimality (up to numerical tolerance) instead of using the final gap?

[gdalle]

Indeed since we're using away FW it was the fault of PR #383. Our default parameters included a not-so-small epsilon (1e-2), so now that it's actually taken into account the optimization doesn't work as well. I brought epsilon down to 1e-4, but then I faced this warning from the adaptive line search:

Smoothness estimate run away -> hard clipping. Convergence might be not guaranteed.

It's not very clear what to do for an outsider, so I looked at the code and decided to switch back to agnostic line search. Now it works 🥳

[matbesancon]

perfect. Yes the line search warning occurs when there are numerical troubles in the line search

[pokutta]

Hey @gdalle,

first of all thanks for reaching out. I would like to add a couple of comments to the discussion:

1. While the agnostic step size works for AFW you might lose a lot of convergence speed. Potentially, from linear to sublinear convergence.
2. It would be great if we can look into the issue a little more closely why you get the warnings. the adaptive line search is a little tricky numerically due to the numerical instabilities induced by the smoothness inequality.
3. As a general remark: you might want to replace AFW with Blended Pairwise Conditional Gradients (BPCG), which has better numerical behavior in general and is typically faster. The interface should be identical as for the AFW algorithm. But that is independent of the numerical issue and more a general remark about the algorithms used.

In short: can you work with us to figure out what exactly the issue with warning so that we can improve the numerical stability of the adaptive line search. As a first step, it would be great if @matbesancon can reproduce the warning on our end and maybe you can also tell us a little bit about the function and feasible region.

Thanks!

[matbesancon]

hi @gdalle, if the issue still comes up, we improved reliability of the line search in numerically harder problems, ping me on slack if this still occurs and we should be able to work through it and see if we can get back to a fast-convergence line search

[gdalle]

Cool thanks, which release would that be? I'll give it a go

[matbesancon]

either master now, or the latest release 0.2.31 with line_search=FrankWolfe.Adaptive(relaxed_smoothness=true)

[gdalle]

Noice. Will try and report back

[gdalle]

ping @BatyLeo

[matbesancon]

@gdalle what's the status here?

[gdalle]

Tring it out in the PR above. First I'm removing the agnostic line search (which should error as before), then I'll activate relaxed_smoothness and see what happens

[matbesancon]

@gdalle update on this: we changed the algorithm performed in Adaptive() in the latest version 0.3.0, it costs more gradient calls per iteration now but will be overall more stable

[matbesancon]

the old step size is AdaptiveZerothOrder

[gdalle]

Good to know! Gonna throw the baby to @BatyLeo on this one

[BatyLeo]

@gdalle It seems the [compat] section of DifferentiableFrankWolfe.jl needs to be updated to allow this new v0.3 of FrankWolfe.jl.