It is already known that, for several important sets arising in applications, performing linear minimization can be faster than projection. However, if we consider the class of all nonempty compact convex sets, can we directly compare the computational complexity of linear minimization to that of projection? This talk provides two modest results in this direction: (1) high-precision linear minimization is no slower than projection; and (2) Exact linear minimization is no slower than projection under the additional assumption of polyhedrality.

Keywords: Frank-Wolfe, conditional gradient

Our results can be found here. If errors or typos are found, please let me know via email or this form.