Our contribution.
We propose a generic and scalable approach for projecting onto a small number of convex smooth constraints.
Our approach applies generally for any constraint set that can be described by Eq. (REF ). Moreover, our approach extends beyond the projection objective to any strongly convex and smooth objective.
The overall runtime of our method for finding an approximate projection is \(O(n m^{2.5}\log ^2(1/\varepsilon ) + m^{3.5}\log (1/\varepsilon ))\)  (see Thm. REF  and the discussion afterwards).
Thus, the runtime of our method scales linearly with \(n\) , making it highly suitable for solving high-dimensional problems that are ubiquitous in ML. Furthermore, in contrast to the Frank-Wolfe (FW) algorithm [1]}, our approach is generic (i.e., does not require a linear minimization oracle) and depends only logarithmically on the accuracy.
