There are two main challenges to address in developing efficient projection-free algorithms for solving (REF ). First, note that denoting the transpose of the Jacobian of \(f_i\)  by \(\nabla f_i\) , the gradient of the objective function \(F(x)\)  in (REF ), is given by \(\nabla F(x) = \nabla f_T(y_T)\nabla f_{T-1}(y_{T-1}) \cdots \nabla f_1(y_1) \) , where \(y_i = f_{i+1} \circ \cdots \circ f_T(x)\)  for \(1 \le i < T\) , and \(y_T = x\) . Because of the nested nature of the gradient \(\nabla F(x)\) , obtaining an unbiased gradient estimator in the stochastic first-order setting, with controlled moments, becomes non-trivial. Using naive stochastic gradient estimators lead to oracle complexities that depend exponentially on \(T\)  (in terms of the accuracy parameter). Next, even when \(T=1\)  in the stochastic setting, projection-free algorithms like the conditional gradient method or its sliding variants invariably require increasing order of mini-batchesWe discuss in detail about some recent works that avoid requiring increasing mini-batches, albeit under stronger assumptions, in Section REF . [1]}, [2]}, [3]}, [4]}, [5]}, which make their practical implementation infeasible.
