Related work.
In the past years, projection free first order methods have been extensively investigated.
In particular, the Frank-Wolfe (FW) algorithm [1]} (also known as conditional gradient method)
is explored, e.g., in [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}.
This approach avoids projections and instead assumes that one can efficiently solve an optimization problem with linear objective over the constraints in each round. Unfortunately, the latter assumption holds only in special cases. In general, this linear minimization might be non-trivial and have the same complexity as the initial problem. Moreover, FW is in general unable to enjoy the fast convergence rates that apply to standard gradient based methods Note that for some special cases like simplex constraints one can ensure fast rates for FW [10]}, [4]}. In general, FW requires \(O(1/\varepsilon )\)  calls to an oracle providing the solution to linear-minimization oracle to obtain \(\varepsilon \) -accurate solutions.. In particular, FW does not achieve the linear rate obtained by projected gradient descent in the case of smooth and strongly-convex problems. Moreover, FW does not enjoy the accelerated rate obtained by projected Nesterov's method for smooth and convex problems.
