\begin{document}
\maketitle
\begin{abstract}
Descent directions such as movement towards Frank-Wolfe vertices, away steps, in-face away steps and pairwise directions have been an important design consideration in conditional gradient descent (CGD) variants. In this work, we attempt to demystify the impact of movement in these directions towards attaining constrained minimizers. The best local direction of descent is the directional derivative of the projection of the gradient, which we refer to as the {\it shadow} of the gradient. We show that the continuous-time dynamics of moving in the shadow are equivalent to those of PGD however non-trivial to discretize. By projecting gradients in PGD, one not only ensures feasibility but \textcolor{teal}{is also} able to ``wrap'' around the convex region. We show that Frank-Wolfe (FW) vertices in fact recover the maximal wrap one can obtain by projecting gradients, thus providing a new perspective \hme{on} these steps. We also claim that the shadow steps give the best direction of descent emanating from the convex hull of all possible \textcolor{teal}{away-steps}. Viewing PGD movements in terms of shadow steps gives linear convergence, dependent on the number of faces. We combine these insights into \textcolor{teal}{a novel} {\sc Shadow-CG} method that uses FW steps and shadow steps, while enjoying linear convergence. Our analysis develops properties of the curve \textcolor{teal}{formed} by projecting a line on a polytope, which may be of independent interest. 

\end{abstract}

\section{Introduction}\vspace{-0.2cm}
\input{introduction.tex}

\section{Preliminaries}\label{sec: prelims}
\vspace{-0.2cm}
\input{preliminaries.tex}

\section{Structure of the Parametric Projections Curve}\label{sec:structure}\vspace{-0.2cm}
\input{derivative}

\vspace{-0.1cm}
\section{Continuous-time Dynamics and {\sc Shadow-Walk} Algorithm}\label{sec:appODE}
\input{Ode}

\vspace{-0.1cm}
\section{Shadow Conditional Gradient Method} \label{sec:shadowCG}\vspace{-0.1cm}
\input{speedupusingCG}

\vspace{-0.1cm}
\section{Computations}\label{sec: computations - main body}\vspace{-0.2cm}
\input{Appcomputations}

\vspace{-5 pt}
\section{Acknowledgements}
\vspace{-5 pt}
The research presented in this paper was partially supported by the NSF grant CRII-1850182, the Research Campus MODAL funded by the German Federal Ministry of Education and Research (grant number 05M14ZAM), and the Georgia Institute of Technology ARC TRIAD fellowship. We would also like to thank Damiano Zeffiro for pointing out a missing case in the statement of Theorem \ref{invariance} in an earlier version of this paper, which is now corrected.

\singlespacing

\bibliographystyle{IEEEtran}
\bibliography{related}
\newpage
\appendix

\setcounter{footnote}{0}

\input{traceopt}


\input{appendix2}


\input{appdescent}

\input{prelims_conver}


\input{ODEanddiscretization}


\end{document}
{"config": "arxiv", "file": "2006.08426/main.tex"}