text:
In this section, we characterize properties of the directional derivative at any ${\x} \in P$ and the structure of the parametric projections curve $g_{\x, \mathbf{w}}(\lambda) = \Pi_P(\mathbf{x} - \lambda \mathbf{w})$, for $\lambda \geq 0$, under Euclidean projections. For brevity, we use $g(\cdot)$ when $\mathbf{x}$ and $\mathbf{w}$ are clear from context. The following theorem summarizes our results and {it} is crucial to our analysis of descent directions:

\begin{theorem} [Structure of Parametric Projections Curve]\label{elephant} Let $P \subseteq \mathbb{R}^n$ be a polytope, with $m$ facet inequalities (e.g., as in \eqref{polytope}). For any $\x_0 \in P, \mathbf{w} \in \mathbb{R}^n$, let $g(\lambda) = \Pi_P(\mathbf{x}_0 - \lambda \mathbf{w})$ be the projections curve at $\x_0$ with respect to $\mathbf{w}$ parametrized by $\lambda \in \mathbb{R}_+$. Then, this curve is piecewise linear starting at $\x_0$: there exist $k$ breakpoints $\x_1, \x_2, \hdots, \x_k \in P$, corresponding to projections with $\lambda$ equal to $0= \lambda_0^{-} \leq \lambda_0^{+} < \lambda_1^{-} \leq \lambda_1^+ < \lambda_2^- \leq \lambda_2^+ \hdots < \lambda_k^{-} \leq \lambda_k^+$, where
\begin{enumerate}[leftmargin = 15pt]
    \item[(a)] $\lambda_i^- \coloneqq \min \{\lambda \geq 0~|~ g(\lambda) = \x_i\}$, $\lambda_i^+ \coloneqq \max \{\lambda \geq 0 ~|~ g(\lambda) = \x_i\}$, for $i\geq 0$,
    \item[(b)] $g(\lambda) = \x_{i-1} + \frac{\x_{i}-\x_{i-1}}{\lambda_i^{-}-\lambda_{i-1}^{+}}(\lambda-\lambda_{i-1}^+)$, for $\lambda \in [\lambda_{i-1}^+, \lambda_i^-]$ for all $i \geq 1$.
\end{enumerate}
Moreover, for each $1 \leq  i \leq k$ and all $\lambda, \lambda^\prime \in (\lambda_{i-1}^+, \lambda_{i}^-)$, the following hold:
\begin{enumerate} [leftmargin = 15pt]
     \item[(i)] {\textbf{\textit{Potentially drop tight constraints on leaving breakpoints:}} $N_P(\x_{i-1}) = N_P(g(\lambda_{i-1}^+)) \supseteq N_P(g(\lambda))$. Moreover, if  $\lambda_{i-1}^{-} < \lambda_{i-1}^{+}$, then the containment is strict.}
    \item[(ii)] \textbf{\textit{Constant normal cone between breakpoints:}} $N_{P}(g(\lambda)) = N_{P}(g(\lambda^\prime))$,
    \item[(iii)] \textbf{\textit{Potentially add tight constraints on reaching breakpoints:}} $N_{P}(g(\lambda)) \subseteq N_{P}(g(\lambda_i^-)) = N_P(\x_i)$.
\end{enumerate}
Further, the following properties also hold:
\begin{enumerate}[leftmargin = 15pt]
\item[(iv)] \textbf{\textit{Equivalence of constant normal cones with linearity:}} If $N_P(g(\lambda)) = N_P(g(\lambda^\prime))$ for some $\lambda < \lambda^\prime$, then the curve between $g(\lambda)$ and $g(\lambda^\prime)$ is linear (Lemma \ref{equivalence}).
    \item[(v)] \textbf{\textit{Bound on breakpoints:}} The number of breakpoints of $g(\cdot)$ is at most the number of faces of the polytope (Theorem \ref{breakpoints}).
    \item[(vi)] \textbf{\textit{Limit of $g(\cdot)$:}} The end point of the curve $g(\lambda)$ is $\lim_{\lambda \rightarrow \infty} g(\lambda) = \x_k \in \argmin_{\x\in P} \innerprod{\mathbf{x}}{\mathbf{w}}$. In fact, $\x_k$ minimizes $\|\y-\x_0\|$ over $\y \in \argmin_{\x\in P} \innerprod{\mathbf{x}}{\mathbf{w}}$ (Theorem \ref{FW limit}, Section \ref{sec:descentdirections}).
\end{enumerate}
\end{theorem}

\begin{figure}[t]
\small
    \centering
    \includegraphics[scale = 0.35]{normal_cone1.png}
    \caption{\small \textcolor{blue}{Figure showing the structure of the projections curve $g(\lambda) = \Pi_P(\x_0 - \lambda \mathbf{w})$ for $\lambda \geq 0$, which is depicted by the orange line. Breakpoints in the curve correspond to $\x_i$ with $g(\lambda_i^-) = g(\lambda_i^+) = \x_i$, and $\lambda_3^+ = \infty$ since $\lim_{\lambda \to \infty} g(\lambda) = \mathbf{v} = \arg\min_{\y\in P} \innerprod{\y}{\mathbf{w}}$. Consider the first linear segment from $\x_0$ to $\x_1$. We have $N_P(g(\lambda)) = N_P(g(\lambda^\prime)) \subset N_P(\x_0)$ for all $\lambda, \lambda^\prime \in (0,\lambda_1^{-})$. Then, another constraint becomes tight at the end point of the first segment $\x_1$, and thus we have $N_P(g(\lambda)) \subset N_P(\x_1)$ for all $\lambda \in (0,\lambda_1^{-})$. This process of dropping and adding constraints (given by Theorem \ref{elephant}$(i)-(iii)$) continues until we reach the endpoint $\mathbf{v}$.}}
    \label{fig:Normal Cone}
\end{figure}

To see an example of the projections curve, we refer the reader to Figure \ref{fig:Normal Cone}. Even though our results hold for any $\mathbf{w}\in \mathbb{R}^n$, we will prove the statements for $\mathbf{w} = \nabla f(\x_0)$ for readability in the context of the paper. Before we present the proof of Theorem \ref{elephant}, we first show that if $-\nabla f(\x_0) \in N_P(\x_0)$, then $g(\lambda)$ reduces down to a single point $\x_0$.
\begin{restatable}{lemma}{basecase}
\label{basecase}
 We have $g(\lambda) = \Pi_P(\x_0 - \lambda \nabla f(\x_0)) = \x_0$ for all $\lambda \in \mathbb{R}_+$ if and only if $- \nabla f(\x_0) \in N_P(\x_0)$.
\end{restatable}
\begin{proof}
Note that $g(\lambda) = \x_0$ if and only if $\x_0$ satisfies the first order optimality condition for $g(\lambda)$: $\innerprod{\x_0 - \lambda \nabla f(\x_0) - \x_0}{\mathbf{z} - \x_0} = \lambda \innerprod{-  \nabla f(\x_0)}{\mathbf{z} - \x_0} \leq 0$ $\text{for all } \mathbf{z} \in P$. Since $\lambda \geq 0$, we can conclude that $g(\lambda) = \x_0$ if and only if $\innerprod{-\nabla f(\x_0)}{\mathbf{z} - \x_0} \leq 0$ for all $\mathbf{z} \in P$. Note that $\innerprod{-  \nabla f(\x_0)}{\mathbf{z} - \x_0} \leq 0$ for all $\mathbf{z} \in P$ is equivalent to saying that $ -\nabla f(\x_0) \in N_P(\x_0)$.
 \end{proof}
Thus, in the notation of Theorem \ref{elephant}, $\lambda_0^+$ is either infinity (when $-\nabla f(\x_0) \in N_P(\x_0)$) or it is zero. In the former case, Theorem \ref{elephant} holds trivially with $g(\lambda)=\x_0$ for all $\lambda\in \mathbb{R}$. We will therefore assume that $\lambda_0^+ = 0$, without loss of generality.

The rest of this section is organized as follows. In Section \ref{sec:piecewise}, we show that the projections curve is piecewise linear as characterized in Theorem \ref{elephant}$(a)$-$(b)$.
In Section \ref{sec:normal cone props}, we prove the normal cone properties of the projections curve from Theorem \ref{elephant}$(i) - (iii)$. Finally in Section \ref{sec:trace} we prove the bound on the number of breakpoints of the projections curve Theorem \ref{elephant}$(v)$ and present our \textsc{Trace} procedure, which traces the projections curve and computes its linear segments.

\subsection{The Projections Curve is Piecewise Linear}\label{sec:piecewise}

We first show that the segment of the projections curve between two projected points with the same normal cones has to be linear (Theorem \ref{elephant}$(iv)$). This result will be crucial to prove that the projections curve is piecewise linear and the bound on the number of breakpoints of the curve.

\begin{restatable}
{lemma}{equivalence}
\label{equivalence}
Let $P \subseteq \mathbb{R}^n$ be a polytope. Let $\x_0\in P$ and we are given $\nabla f(\x_0) \in \mathbb{R}^n$. Let $g(\lambda) = \Pi_P(\x_0 - \lambda \nabla f(\x_0))$ be the parametric projections curve. Then, if $N_P(g(\lambda)) = N_P(g(\lambda^\prime))$ for some $\lambda < \lambda^\prime$, then the curve between $g(\lambda)$ and $g(\lambda^\prime)$ is linear, i.e., $g(\delta\lambda + (1-\delta)\lambda^\prime) = \delta g(\lambda) + (1-\delta)g(\lambda^\prime)$, where $\delta\in[0,1]$.
\end{restatable}

The idea of the proof is to show that $\delta g(\lambda) + (1-\delta)g(\lambda^\prime)$ satisfies the first-order optimality condition of Euclidean projections given in \eqref{first-order optimality of projections} for $g(\delta\lambda + (1-\delta)\lambda^\prime)$ when $N_P(g(\lambda)) = N_P(g(\lambda^\prime))$. The complete proof of this lemma can be found in found in Appendix \ref{app:piecewise proofs}. Note that as an immediate corollary of this lemma we know that the projections curve does not intersect itself. That is, if the projections curve leaves the point $\x \coloneqq g(\lambda)$ for an arbitrary $\lambda > 0$ (i.e. $g(\lambda + \epsilon) \neq \x$ for some $\epsilon > 0$), then $g(\lambda^\prime) \neq \x$ for all $\lambda^\prime > \lambda + \epsilon$.

We next show that the projections curve is in fact piecewise linear and continuous. The proof uses non-expansivity of the Euclidean projection operator to show continuity of the curve, and the previous lemma combined with the fact that the number of distinct normal cones over a polytope is finite (the proof is included in Appendix \ref{app:piecewise proofs}).

\begin{restatable}
{lemma}{continuousandpiecewise} \label{continuous and piecewise}
Let $P \subseteq \mathbb{R}^n$ be a polytope. Let $\x_{0} \in P$ and $ \nabla f(\x_0) \in \mathbb{R}^n$ be given. Further, let $g(\lambda) = \Pi_{P}(\x_0 -\lambda \nabla f(\x_0))$ denote the projections curve. Fix an arbitrary $\lambda > 0$. Then, $\lim_{\lambda^\prime \downarrow \lambda}g(\lambda^\prime) = \lim_{\lambda^\prime \uparrow \lambda} g(\lambda^\prime) = g(\lambda)$. Moreover, there exists $\delta^\prime >0$ and directions $\uline{\bd}, \bar{\bd} \in \mathbb{R}^n$ such that $g(\lambda - \epsilon) = g(\lambda) - \epsilon \uline{\bd}$ and $g(\lambda + \epsilon) = g(\lambda) + \epsilon \bar{\bd}$, for all $\epsilon \in (0, \delta^\prime]$.
\end{restatable}

\textcolor{blue}{Since the projections curve is piecewise linear, we naturally obtain a set of breakpoints $k$ breakpoints $\x_1, \x_2, \hdots, \x_k \in P$, corresponding to projections with $\lambda$ equal to $0= \lambda_0^{-} \leq \lambda_0^{+} < \lambda_1^{-} \leq \lambda_1^+ < \lambda_2^- \leq \lambda_2^+ \hdots < \lambda_k^{-} \leq \lambda_k^+$, satisfying properties in $(a)$ and $(b)$ in Theorem \ref{elephant}:
\begin{enumerate}[leftmargin = 15pt]
    \item[(a)] $\lambda_i^- \coloneqq \min \{\lambda \geq 0~|~ g(\lambda) = \x_i\}$, $\lambda_i^+ \coloneqq \max \{\lambda \geq 0 ~|~ g(\lambda) = \x_i\}$, for $i\geq 0$,
    \item[(b)] $g(\lambda) = \x_{i-1} + \frac{\x_{i}-\x_{i-1}}{\lambda_i^{-}-\lambda_{i-1}^{+}}(\lambda-\lambda_{i-1}^+)$, for $\lambda \in [\lambda_{i-1}^+, \lambda_i^-]$ for all $i \geq 1$.
\end{enumerate}}

Note that we can now establish the existence of the shadow as a corollary of the previous result about the piecewise linearity of $g(\lambda)$. Indeed, since  $g(\lambda) = \x_{0} + \frac{\x_{1}-\x_{1}}{\lambda_1^{-}}\lambda$, for $\lambda \in [0, \lambda_1^-]$, using the definition of $\bd_{\x_0}^\Pi$ we have
\begin{equation}
    \mathbf{d}_{\mathbf{x}_0}^\Pi \coloneqq \lim_{\epsilon \downarrow 0} \frac{\Pi_P(\x_0 - \epsilon \nabla f(\x_0)) - \x_0}{\epsilon}
    = \lim_{\epsilon \downarrow 0}\frac{g(\epsilon) - \x_0}{\epsilon}
    = \frac{\x_1 - \x_0}{\lambda_1^-}, \label{newdirectional1}
\end{equation}
which shows existence and equivalence of the first segment of the projections curve to the shadow, i.e., $g(\lambda) = \x_0 +  \lambda \bd_{\x_0}^\Pi$ for all $\lambda \in [0,\lambda_1^-]$. This will be useful in justifying our continuous-time dynamics later Section \ref{sec:appODE}. This also gives a different proof for existence of $\mathbf{d}_{\mathbf{x}_0}^\Pi$ for polytopes, compared to Tapia et. al \cite{Tapia_1972}.

\subsection{Normal Cone Properties of  the Projections Curve} \label{sec:normal cone props}
We now show the growth and subset properties of normal cones when tracing the projections curve. We first show that $(a)$ movement away from a point along a linear segment can only drop constraints in its neighborhood, and $(b)$ maximum movement along a linear segment must add a tight constraint at the endpoint. The idea of the proof is to simply track the effect of movement along linear directions on the activity and inactivity of the constraints defining the polytope.

\begin{restatable}{lemma}{movementlinear}\label{movement along linear segments}
Let $P \subseteq \mathbb{R}^n$ be a polytope and consider any $\x \in P$. Let $\bd \in \mathbb{R}^n$ be any direction that is feasible at $\x$, and let $\delta = \max\{\lambda \mid \x + \lambda \bd \in P\}$.
Then,
\begin{enumerate}
    \item[(a)] $N_P(\x+\lambda \bd) = N_P(\x+\lambda^\prime \bd) \subseteq N_P(\x)$, for all $0<\lambda<\lambda^\prime < \delta$;
    \item[(b)] $N_P(\x+\lambda \bd) \subset N_P(\x + \delta \bd)$, for all $0<\lambda < \delta$.
\end{enumerate}
\end{restatable}
\begin{proof}
First note that $\delta > 0$ since $\bd$ is feasible at $\x$, and $\delta < \infty$ since $P$ is a polytope and movements along any direction are bounded. For brevity, we let $I$ and $J$ denote the index-set of active and inactive constraints at $\x$ respectively. Fix $\lambda,\lambda^\prime \in (0,\delta)$ arbitrarily such that $\lambda < \lambda^\prime$. We prove the lemma in the next two claims.
\begin{enumerate}
    \item[(a)] {\it We first show that $N_P(\x+\lambda \bd) = N_P(\x+\lambda^\prime \bd) \subseteq N_P(\x)$}. We prove Claim $(a)$ in the next two sub-claims:
\begin{itemize}
    \item[(a.i)] {\it Inactive constraints remain inactive: $N_P(\x + \lambda \bd) \subseteq N_P(\x)$}. Since $\x + \delta \bd \in P$, we have $\A_J (\x + \delta\bd) \leq \mathbf{b}_{J}$, which implies that $\A_J \bd \leq \frac{\mathbf{b}_{J} - \A_J \x}{\delta}$. Moreover, for any $\lambda < \delta$, we have
    \vspace{-8 pt}
\begin{equation*}
    \A_J (\x + \lambda\bd) \leq \A_J\x + \lambda\frac{\mathbf{b}_{J} - \A_J \x}{\delta} = \left( 1 -\frac{\lambda}{\delta} \right)\A_J\x + \mathbf{b}_{J} \frac{\lambda}{\delta} < \mathbf{b}_{J},
    \vspace{-5 pt}
\end{equation*}
where the last (strict) inequality follows from the fact that we are taking a convex combination. This shows $\A_J(\x + \lambda \bd) < \mathbf{b}_J$ (component-wise) for all $\lambda \in (0,\delta)$, i.e., $N_P(\x + \lambda \bd) \subseteq N_P(\x)$.
    \item[(a.ii)] {\it Active constraints are maintained: $N_P(\x+\lambda \bd) = N_P(\x+\lambda^\prime \bd)$}. Since the inactive constraints remain inactive, we just need to check the constraints in the index set $I$. Consider any $i \in I$. Since $\innerprod{\mathbf{a}_i}{\x_0} = b_i$ and $\x_0 + \delta \bd \in P$ $(\delta>0)$, we know that $\innerprod{\mathbf{a}_i}{\bd} \leq 0$. If $\innerprod{\mathbf{a}_i}{\bd} = 0$, then  $\innerprod{\mathbf{a}_i}{\x+\lambda \bd} = b_i$ for all $\lambda \in [0,\delta)$. So the constraint corresponding to $\mathbf{a}_i$ is active at both $\x+\lambda \bd$ and $\x+\lambda^\prime \bd$. On the other hand, if $\innerprod{\mathbf{a}_i}{\bd} < 0$, then $\innerprod{\mathbf{a}_i}{\x+\lambda \bd} < b_i$ for all $\lambda \in [0,\delta)$. Thus, the constraint corresponding to $\mathbf{a}_i$ is inactive at both $\x+\lambda \bd$ and $\x+\lambda^\prime \bd$.
\end{itemize}

\item[(b)] {\it We next show that $N_P(\x+\lambda \bd) \subset N_P(\x+ \delta \bd)$}. Let $\tilde{I}$ denote the index set of active constraints at $\x+\lambda \bd$. Using Claim (a.i), we know that $\tilde{I} \subseteq I$. Therefore, for any $i \in \tilde{I}$, we have
\begin{equation*}
 \innerprod{\mathbf{a}_i}{\x+\lambda \bd} = b_i \implies \innerprod{\mathbf{a}_i}{\bd} = 0 \implies \innerprod{\mathbf{a}_i}{\x + \delta \bd} = b_i,
\end{equation*}
and so the constraint corresponding to $\mathbf{a}_i$ (which is active at $\x+\lambda \bd$) is also active at $\x + \delta \bd$. We have thus shown that $N_P(\x+\lambda \bd) \subseteq N_P(\x+\delta \bd)$. It remains to show that this containment is strict. Since $\bd$ is a feasible direction at $\x$, we have $\innerprod{\mathbf{a}_i}{\bd} \leq 0$ for all $i \in I$. Thus
\begin{equation} \label{max lambda}
    \delta = \min_{\substack{j \in J:\\ \innerprod{\mathbf{a}_j}{\bd} > 0}} \frac{b_j - \innerprod{\mathbf{a}_j}{\x}}{\innerprod{\mathbf{a}_j}{\bd}},
\end{equation}
where the feasible set of the above problem is non-empty, since otherwise this would imply that $\bd$ is a recessive direction (i.e., direction of unboundedness), contradicting the fact that $P$ is a polytope. Let $j^*$ be any optimal index to the optimization problem in \eqref{max lambda}, where by definition $\innerprod{\mathbf{a}_{j^*}}{\x+\delta \bd} = b_{j^*}$. Now, since $\innerprod{\mathbf{a}_{j^*}}{\bd }>0$ and $\lambda < \delta$, we have
$\innerprod{\mathbf{a}_{j^*}}{\x+\lambda \bd} < \innerprod{\mathbf{a}_{j^*}}{\x + \delta \bd}$,
implying that the constraint $\mathbf{a}_{j^*}$ is not active at $\x+\lambda \bd$. Thus, $N_P(\x+\lambda \bd) \subset N_P(\x+\delta \bd)$.
\end{enumerate}
 This completes the proof since $\lambda,\lambda^\prime$ were chosen arbitrarily.
 \end{proof}

We show next that the projections curve is piecewise linear.
Note that Lemma \ref{movement along linear segments} and Lemma \ref{normal cone props} together prove the normal cone properties in in Theorem \ref{elephant}${(i)}$ - ${(iii)}$.

\begin{lemma}
\label{normal cone props}
Let $P \subseteq \mathbb{R}^n$ be a polytope. Let $\x_{0} \in P$ and $\nabla f(\x_0) \in \mathbb{R}^n$ be given. Further, let $\x_{i-1} \in P$ be the $i$th breakpoint in the projections curve $g(\lambda) = \Pi_{P}(\x_0 -\lambda \nabla f(\x_0))$, with $\x_{i-1}=\x_0$ for $i=1$. Define $\lambda_{i-1}^- \coloneqq \min\{\lambda \mid g(\lambda) = \x_{i-1}\}$, $\lambda_{i-1}^+ \coloneqq \max\{\lambda \mid g(\lambda) = \x_{i-1}\}$, and let $k$ be the number of breakpoints of $g(\lambda)$. Then, the following properties hold for all $1 \leq i \leq k$ and $\lambda, \lambda^\prime \in (\lambda_{i-1}^+, \lambda_{i}^-)$:
\begin{enumerate} [leftmargin = 35pt]
\setlength{\itemsep}{-1 pt}
     \item[$(i)$]  $N_P(\x_{i-1}) = N_P(g(\lambda_{i-1}^+)) \supseteq N_P(g(\lambda))$. Moreover, if  $\lambda_{i-1}^{-} < \lambda_{i-1}^{+}$, then the containment is strict,
     \item[$(ii)$]  $N_{P}(g(\lambda)) = N_{P}(g(\lambda^\prime))$, and
    \item[$(iii)$] $N_{P}(g(\lambda)) \subseteq N_{P}(g(\lambda_i^-)) = N_P(\x_i)$.
\end{enumerate}
\end{lemma}

\begin{proof}
Consider a breakpoint $\x_{i-1}$ of $g(\lambda)$, where $1 \leq i \leq k$. Using Theorem \ref{elephant}$(a)$-$(b)$, we know that $g(\lambda) = \x_{i-1} + (\lambda-\lambda_{i-1}^+) \bd$ for $\lambda \in [\lambda_{i-1}^+, \lambda_i^-]$ and some direction $\bd \in \mathbb{R}^n$. Using the normal cone properties given in Lemma \ref{movement along linear segments} applied with $\x \coloneq \x_{i-1}$ and parameter $(\lambda-\lambda_{i-1}^+)$ in place of $\lambda$, we immediately have that the first part of property $(i)$ ($N_P(\x_{i-1}) = N_P(g(\lambda_{i-1}^+)) \supseteq N_P(g(\lambda))$ for all $\lambda \in (\lambda_{i-1}^+, \lambda_{i}^-)$), $(ii)$ and $(iii)$ hold. It remains to show that if $\lambda_{i-1}^{-} < \lambda_{i-1}^{+}$, then the containment in $(i)$ is strict. Suppose for a contradiction that $\lambda_{i-1}^{-} < \lambda_{i-1}^{+}$ but $N_P(g(\tilde{\lambda})) = N_P(\x_{i-1})$ for some $\lambda_{i-1}^{+} <\tilde{\lambda} < \lambda_{i}^-$. Since $\lambda_{i-1}^+ < \infty$ (as $i - 1 < k$), it follows that $g(\tilde{\lambda}) \neq \x_{i-1}$. Using Lemma \ref{equivalence} (linearity of projections), we know that $g(\lambda_{i-1}^{+}) = \theta g(\lambda_{i-1}^{-}) + (1 - \theta) g(\tilde{\lambda})$ for $\theta = \frac{\lambda_{i-1}^+ - \lambda_{i-1}^-}{\tilde{\lambda} - \lambda_{i-1}^-} \in (0,1)$. This is a contradiction since $g(\lambda_{i-1}^+) = g(\lambda_{i-1}^-) = \x_{i-1}$ but $g(\tilde{\lambda}) \neq \x_{i-1}$.
 \end{proof}

\subsection{Tracing the Projections Curve} \label{sec:trace}
We next show how to iteratively trace the projections curve $g(\lambda)$ and construct all of its linear segments for all $\lambda\geq 0$. Consider a breakpoint $\x_{i-1}$ of $g(\lambda)$ where $i \geq 1$. Then, depending on the structure current breakpoint (see Theorem \ref{invariance} below and also Figure \ref{fig:pyramidal width}), the next linear segment and breakpoint $\x_i$ of the curve can be obtained by either (a) projecting $\nabla f(\mathbf{x}_0)$ onto the tangent cone at $\x_{i-1}$ (i.e. computing the shadow ${\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))$ at $\x_{i-1}$ with respect to $\nabla f(\mathbf{x}_0)$), and moving maximally along that direction using line search; or (b) by projecting $\nabla f(\mathbf{x}_0)$ onto the minimal face of $\x_{i-1}$ (i.e. computing the in-face shadow $\hat{\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))$ at $\x_{i-1}$ with respect to $\nabla f(\mathbf{x}_0)$), and moving along that direction until the curve $g(\lambda)$ leaves the minimal face:

\begin{restatable}[Tracing the projections curve]{theorem}{invariance}
\label{invariance}
Let $P \subseteq \mathbb{R}^n$ be a polytope. Let $\x_{i-1} \in P$ be the $i$th breakpoint in the projections curve $g(\lambda) = \Pi_{P}(\x_0 -\lambda \nabla f(\x_0))$, with $\x_{i-1}=\x_0$ for $i=1$. Suppose we are given $\lambda_{i-1}^-, \lambda_{i-1}^+ \in \mathbb{R}$ so that they are respectively the minimum and the maximum step-sizes $\lambda$ such that $g(\lambda) = \x_{i-1}$. If $\bd_{\x_{i-1}}^\Pi(\nabla f(\x_0)) = \mathbf{0}$, then $\lim_{\lambda \to \infty}g(\lambda) = \x_{i-1}$ is the end point of $g(\lambda)$. Otherwise, $\bd_{\x_{i-1}}^\Pi(\nabla f(\x_0)) \neq \mathbf{0}$, in which case we claim that:
\begin{enumerate} [leftmargin = 10pt]
 \vspace{-1 pt}
\setlength{\itemsep}{-1 pt}
 \item [(a)] {\bf Shadow steps:} If $\innerprod{\x_0- \lambda_{i-1}^{+} \nabla f(\x_0) - \x_{i-1}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0)} = 0$, then the projections curve moves maximally in the shadow direction, i.e.,  $\x_{i} \coloneqq g(\lambda_{i}^-)=\mathbf{x}_{i-1} + (\lambda_{i}^- - \lambda_{i-1}^+)\mathbf{d}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$ where $\lambda_{i}^- \coloneqq \lambda_{i-1}^+ + \max \{\delta : \mathbf{x}_{i-1} + \delta \mathbf{d}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0)) \in P\}$.
    \item [(b)] {\bf In-face steps:} Otherwise, $\innerprod{\x_0- \lambda_{i-1}^{+} \nabla f(\x_0) - \x_{i-1}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0)} \neq 0$. Let $\hat{\lambda}_{i-1} \coloneqq {\sup}\{\lambda \mid N_P(g(\lambda^\prime)) = N_P(\x_{i-1}) \; \forall \lambda^\prime \in [\lambda_{i-1}^-,\lambda)\}$. Then, $\hat{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0)) \neq {\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$, $\lambda_{i-1}^+ < \hat{\lambda}_{i-1} < \infty$, and the next breakpoint in the curve occurs by walking in-face up to $\hat{\lambda}_{i-1}$, i.e., $\x_{i} \coloneqq g(\hat{\lambda}_{i-1}) =\mathbf{x}_{i-1} + (\hat{\lambda}_{i-1} - \lambda_{i-1}^+)\hat{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$ and $\lambda_{i}^- \coloneqq \hat{\lambda}_{i-1}$.
\end{enumerate}

 \vspace{-1 pt}
\end{restatable}

\textcolor{blue}{The idea of the proof is as follows. Consider a breakpoint $\x_{i-1} \coloneqq g(\lambda_{i-1}^+)$ that is not the endpoint of the projections curve. For brevity, let $\mb{p}_{i-1} \coloneqq \x_0- \lambda_{i-1}^{+} \nabla f(\x_0) - \x_{i-1}$ denote the normal vector of the projection at $\x_{i-1}$. Since the projections curve is piecewise linear (Theorem \ref{elephant}), we know that $g(\lambda) = \x_{i-1} + (\lambda_i^- - \lambda_{i-1}^+) \bd$ for $\lambda \in [\lambda_{i-1}^+, \lambda_i^-]$ and some direction $\bd \in \mathbb{R}^n$. We also know that
$N_P(g(\lambda)) \subseteq N_P(\x_{i-1})$ for $\lambda \in (\lambda_{i-1}^+, \lambda_i^-)$, so that the direction $\bd$ either $(i)$ relaxes some of the active constraints at $\x_{i-1}$, or $(ii)$ is an in-face direction. Using first-order optimality of conditions at $g(\lambda_{i+1}^+)$ and $g(\lambda_{i+1}^+ + \epsilon)$, for any $\epsilon \in (0, \lambda_i^- - \lambda_{i-1}^+)$, and Moreau's decomposition theorem\footnote{\textbf{Moreau's decomposition theorem} \cite{moreau1962}: Let $\mathcal{K}$ be a closed convex cone and let $\mathcal{K}^\circ$ be its polar cone,  that is, the closed convex cone defined by $\mathcal{K}^\circ=\{\mathbf{y} \in \mathbb{R}^n \,\mid\, \innerprod{\x}{\y} \leq 0,\,\forall \x \in\mathcal{K}\}$. Then, for $\x,\y, \mathbf{z} \in \mathbb{R}^n$, the following statements are equivalent: (i) $\mathbf{z}=\x+\y$, $\x \in \mathcal{K}$, $\y \in \mathcal{K}^\circ$, and $\innerprod{\x}{\y}=0$; (ii) $\x = \Pi_{\mathcal{K}}(\mathbf{z})$ and $\y = \Pi_{\mathcal{K}^\circ}(\mathbf{z})$.} \cite{moreau1962}, we show that: in case $(i)$ we have $\bd = {\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$ and the next breakpoint $\x_{i}$ is obtained by walking maximally along the shadow; in case $(ii)$ we have $\bd = \hat{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$ and the next $\x_i$ is obtained by walking along the in-face shadow until the projections curve leaves the minimal face at $\x_{i-1}$. Moreover, as a byproduct of our constructive proof we show that we take a shadow step if and only if $\innerprod{\mb{p}_{i-1}}{{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))} = 0$. For example, in Figure \ref{fig:pyramidal width}-right at the first breakpoint $\x_1$ we have $\innerprod{\mb{p}_{1}}{{\bd}_{\mathbf{x}_{1}}^\Pi(\nabla f(\x_0))} \neq 0$ in which case we take an in-face step, whereas at $\x_2$ we have $\innerprod{\mb{p}_{2}}{{\bd}_{\mathbf{x}_{2}}^\Pi(\nabla f(\x_0))} = 0$, in which case we take a shadow step. The complete proof is in Appendix \ref{app:missing proofs for trace}.}

\paragraph{Remark 1.} We now add a few remarks about the previous theorem:
\begin{enumerate}
\item [$(a)$] Theorem \ref{invariance} applied at $\x_0$ implies that the first segment of the projections curve is given by walking maximally along the shadow. This generalizes our earlier discussion about the first segment of the projections curve.
    \item[$(b)$] Whenever we take a shadow step in case $(a)$, we are guaranteed to add a tight constraint at the subsequent breakpoint. This follows by Lemma \ref{movement along linear segments} since the next breakpoint is obtained by taking the maximum movement along the directional derivative $\mathbf{d}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$. However this need not be true in case $(b)$, unless the maximum movement along the in-face shadow takes place, i.e., $\hat{\lambda}_{i-1} = \lambda_{i-1}^+ + \max \{\delta : \mathbf{x}_{i-1} + \delta \hat{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0)) \in P\}$.
\end{enumerate}

\begin{algorithm}[t] \small
\caption{Tracing Parametric Projections Curve: $\textsc{Trace}(\x_0, \mathbf{x}, \mathbf{w}$, $\lambda_\x$)}
\label{alg: tracing PW proj}
\begin{algorithmic}[1]
\INPUT Polytope $P \subseteq \mathbb{R}^n$, starting point of the projections curve $\x_0 \in P$, $\mathbf{w} \in \mathbb{R}^n$, and a point on the projections curve $\x \in P$ such that $g(\lambda_\x) =  \Pi_P(\x_0 - \lambda_\x \mathbf{w}) = \x$, for a given $\lambda_\x$.
\OUTPUT Next breakpoint $\y$ (if any) and step-size $\lambda_{\y} $ such that $g(\lambda_\y) = \y$.
\State Compute $\mathbf{d}_{\mathbf{x}}^\Pi \coloneqq \lim_{\epsilon \downarrow 0} \frac{\Pi_P(\mathbf{x}- \epsilon \mathbf{w}) - \mathbf{x}}{\epsilon}$.
\If {$\mathbf{d}_{\mathbf{x}}^\Pi \neq \mathbf{0}$} \Comment{\texttt{check if we are at endpoint}}
\If{$\innerprod{\x_0 - \lambda_\x \mathbf{w} - \x}{\mathbf{d}_{\mathbf{x}}^\Pi} = 0$} \Comment{\texttt{determine if we take shadow step}}
\State Compute $\gamma^{\max} = \max \{\delta \mid \mathbf{x} + \delta \mathbf{d}_{\mathbf{x}}^\Pi \in P\}$ \Comment{ \texttt{line-search in shadow direction}}
\State Set $\bd = \mathbf{d}_{\mathbf{x}}^\Pi$. \Comment{ \texttt{next linear direction we move in}}
\Else  \State $\hat{\bd}_{\mathbf{x}}^\Pi, \gamma^{\max} = \textsc{Trace-In-Face}(\x_0, \mathbf{x}, \mathbf{w},\lambda_\x)$.  \Comment{\texttt{in-face step}}
\State Set $\bd = \hat{\bd}_{\mathbf{x}}^\Pi$. \Comment{ \texttt{next linear direction we move in}}
\EndIf
\State Compute next break point $\mathbf{y}= \mathbf{x}+ (\gamma^{\max})\mathbf{d}$
\State Update $\lambda^-_\y = \lambda_\x + \gamma^{\max}$. \Comment{\texttt{keep track of total step-size accrued}}
\Else \Comment{\texttt{$\x$ is the endpoint of the curve}}
\State Set $\y = \x$ and $\lambda_\y = \lambda_\x$ \Comment{\texttt{output does not change}}
\EndIf
\RETURN $\mathbf{y}$, $\lambda_\y$
\end{algorithmic}
\end{algorithm}

\iffalse
\begin{algorithm}[t] \small
\caption{Tracing Parametric Projections Curve: $\textsc{Trace}(\mathbf{x}, \mathbf{w}$, $\lambda$)}\textcolor{teal}{
\label{alg: tracing PW proj}
\begin{algorithmic}[1]
\INPUT Polytope $P \subseteq \mathbb{R}^n$, initialization $\x \in P$, and total step-size to trace to $\lambda$
\State  Let $\x_0 = \x$ and $\gamma^{\text{total}} = 0.$ \Comment{\texttt{fix starting point and initialize total step size}}
\State Compute $\mathbf{d}_{\mathbf{x}}^\Pi \coloneqq \lim_{\epsilon \downarrow 0} \frac{\Pi_P(\mathbf{x}- \epsilon \mathbf{w}) - \mathbf{x}}{\epsilon}$.
\If{$\mathbf{d}_{\mathbf{x}}^\Pi \neq \mathbf{0}$} \Comment{\texttt{check if we are at endpoint}}
\If{$\innerprod{\x_0 - \gamma^{\text{total}}\mathbf{w} - \x}{\mathbf{d}_{\mathbf{x}}^\Pi} = 0$} \Comment{\texttt{determine if we take shadow step}}
\State Compute $\gamma^{\max} = \max \{\delta \mid \mathbf{x} + \delta \mathbf{d}_{\mathbf{x}}^\Pi \in P\}$ \Comment{ \texttt{line-search in shadow direction}}
\State Set $\bd = \mathbf{d}_{\mathbf{x}}^\Pi$. \Comment{ \texttt{next linear direction we move in}}
\Else  \State $\hat{\bd}_{\mathbf{x}}^\Pi, \gamma^{\max} = \textsc{Trace-In-Face}(\x_0, \mathbf{x}, \mathbf{w},\gamma^{\text{total}})$.  \Comment{\texttt{in-face step}}
\State Set $\bd = \hat{\bd}_{\mathbf{x}}^\Pi$, \Comment{ \texttt{next linear direction we move in}}
\EndIf
\If{$\gamma^{\text{total}} + \gamma^{\max} \geq \lambda$} \Comment{\texttt{we have reach desired step size}}
\State Update $\mathbf{x}= \mathbf{x}+ (\lambda - \gamma^{\text{total}})
\mathbf{d}$.
\State \textbf{break}
\Else
\State Update $\gamma^{\text{total}} = \gamma^{\text{total}} + \gamma^{\max}$. \Comment{\texttt{keep track of total step-size accrued}}
\State Update $\mathbf{x}= \mathbf{x}+ (\gamma^{\max})\mathbf{d}$.
\State Recompute $\mathbf{d}_{\mathbf{x}}^\Pi \coloneqq \lim_{\epsilon \downarrow 0} \frac{\Pi_P(\mathbf{x}- \epsilon \mathbf{w}) - \mathbf{x}}{\epsilon}$
\EndIf
\EndIf
\RETURN $\mathbf{x}$
\end{algorithmic}}
\end{algorithm}
\fi
\begin{algorithm}[!t] \small
\caption{Tracing in-face movement: $\textsc{Trace-in-face}(\x_0, \mathbf{x}, \mathbf{w}, \lambda_\x)$}
\label{alg: tracing PW proj in-face}
\begin{algorithmic}[1]
\INPUT Polytope $P \subseteq \mathbb{R}^n$, starting point of projections curve $\x_0 \in P$, current breakpoint $\x \in P$, direction $\mathbf{w} \in \mathbb{R}^n$, and $\lambda_\x$ satisfying  $g(\lambda_\x) =  \Pi_P(\x_0 - \lambda_\x \mathbf{w}) = \x$.
\State Compute $\hat{\bd}_{\mathbf{x}}^\Pi = (\mathbf{I}- \mathbf{A}_{I(\mathbf{x})}^\dagger \mathbf{A}_{I(\mathbf{x})})(-\mathbf{w})$ \Comment{\texttt{in-face directional derivative at $\x$}}
\State Evaluate $\hat{\lambda} = \sup\{\lambda \mid N_P(g(\lambda^\prime)) = N_P(\x_{i-1}) \; \forall \lambda^\prime \in [\lambda_\x,\lambda)\}$ \Comment{\texttt{see remark 3}}

\RETURN $\hat{\bd}_{\mathbf{x}}^\Pi, \hat{\lambda}$
\end{algorithmic}
\end{algorithm}

Assuming oracle access to compute $\mathbf{d}_{\mathbf{x}}^\Pi(\mathbf{w})$ and {$\hat{\lambda}_{i-1}$} for any $\mathbf{x} \in P$, Theorem \ref{invariance} gives a constructive method for tracing the whole piecewise linear curve of $g_{\x, \mathbf{w}}(\cdot)$. We include this as an algorithm, {\sc Trace}$(\x_0, \x, \mathbf{w}, \lambda_\x)$, which traces the projections curve until a target step-size $\lambda$, and give its complete description in Algorithm \ref{alg: tracing PW proj}. The following remarks about the \textsc{Trace} algorithm (Algorithm \ref{alg: tracing PW proj}) will be useful to understand its implementation and correctness. We first remark that the \textsc{Trace} algorithm correctly keeps track of the total step-sizes accrued. This is important since given a breakpoint $\x$, the \textsc{Trace-in-face} procedure requires $\lambda_\x$ satisfying  $g(\lambda_\x) =  \Pi_P(\x_0 - \lambda_\x \mathbf{w}) = \x$ ($\mathbf{w}$ is the direction we are computing the projections curve with respect to).

\paragraph{Remark 2.} \textbf{The \textsc{Trace} algorithm identifies when the projections curve does not change with the same speed as the step-size $\lambda$.} Suppose that \textsc{Trace} starts with a point on the projections curve $\x \in P$ such that $g(\lambda_\x) =  \Pi_P(\x_0 - \lambda_\x \mathbf{w}) = \x$, for a given $\lambda_\x$. Similar to before, let $\lambda_{\x}^-, \lambda_{\x}^+ \in \mathbb{R}$ respectively be the minimum and maximum step-sizes $\lambda$ such that $g(\lambda) = \x$. Now suppose that $\x$ is not the endpoint of $g(\lambda)$ (i.e. $\bd_{\x}^\Pi  \neq \mb{0}$) and that we have $\lambda_{\x} < \lambda_{\x}^+ < \infty$, so that the projections curve moves in-face trivially in the interval $[\lambda_{\x},\lambda_{\x}^+]$. Then, in a such a case, we take an in-face step with an in-face direction $\hat{\bd}_{\x}^\Pi=\mb{0}$, where we still have $\y = \x$ but correctly update $\lambda_\y$ to $\lambda_{\x}^+$. At this point we can run another iteration of \textsc{Trace} initialized with $\y$ and $\lambda_\y$ to obtain the next breakpoint of the curve.

\paragraph{Remark 3.} \textbf{Computing maximum in-face movement.} Suppose that we are at a breakpoint $\x$ and we have that  $\innerprod{\x_0- \lambda_{\x} \nabla f(\x_0) - \x}{\bd_{\x}^\Pi} \neq 0$. First, compute the maximum feasible movement along $\hat{\bd}_{\mathbf{x}}^\Pi$, i.e.,  $\hat{\gamma}^{\max} = \max \{\delta \mid \mathbf{x} + \delta \hat{\mathbf{d}}_{\mathbf{x}}^\Pi \in P\}$. We know that $\hat{\lambda} \in [\lambda_{\x}, \gamma^{\max}]$. We first check if $\hat{\lambda} = \gamma^{\max}$ by checking the first-order optimality:
\begin{equation}\label{inner prod test}
\innerprod{\x_0 - (\lambda_\x + \hat{\gamma}^{\max}) \mathbf{w} - ( \x + \hat{\gamma}^{\max} \hat{\bd}_{\mathbf{x}}^\Pi)}{\mathbf{z} - ( \x + \hat{\gamma}^{\max} \hat{\bd}_{\mathbf{x}}^\Pi} \leq 0 \quad \forall \mathbf{z} \in P,
\end{equation}
which could be checked using a linear program. If first order-optimality holds, then $\hat{\lambda} = \gamma^{\max}$.
Otherwise, we know that $\hat{\lambda} < \hat{\gamma}^{\max}$ and thus $\hat{\lambda} = \max\{\lambda \mid N_P(g(\lambda^\prime)) = N_P(\x) \; \forall \lambda^\prime \in [\lambda_\x,\lambda]\}$. Computing $\hat{\lambda}$ amounts to finding the maximum $\lambda$ such that $\x_0 - \lambda \mathbf{w} - ( \x + (\lambda - \lambda_\x) \hat{\bd}_{\mathbf{x}}^\Pi) \in N_P( \x + (\lambda - \lambda_\x) \hat{\bd}_{\mathbf{x}}^\Pi)$, which can again be computed by the solving the following linear program:
\begin{equation} \label{lo impl}
    \begin{aligned}
        \max~ &\lambda \\
    \text{s.t. } & \x_0 - \lambda \mathbf{w} - \x - (\lambda - \lambda_\x) \hat{\bd}_{\mathbf{x}}^\Pi = \mathbf{A}_{I(\mathbf{x})} ^\top \mathbf{\mb{\mu}}\\
    &\mb{\mu} \geq 0.
    \end{aligned}
    \end{equation}
Note that $\lambda = \lambda_\x$ is a feasible solution to \eqref{lo impl}, which is also the optimal solution when the projections curve is moving to another facet and not moving in-face (case $(b)$ in Theorem \ref{invariance}). Furthermore, we know that optimal solution $\lambda^*$ to the above LP satisfies $\lambda^* < \hat{\gamma}^{\max}$. Hence, \eqref{lo impl} is always feasible and bounded, and thus always has an optimal solution.

\begin{figure}[t]
    \centering

    \includegraphics[scale = 0.6]{pyramidal.png}
    \hspace{10 pt}
    \includegraphics[scale = 0.3]{Trace.png}
    \caption{\textbf{Left:} Figure from Lacoste-Julien and Jaggi's work \cite{Lacoste2015} showing the pyramidal width $\delta$ of a simple triangle domain as a function of the angle $\theta$. \textbf{Right:} An example of the projections curve, showing how the structure of the normal vectors $\mb{p}_{i} \coloneqq \x_0- \lambda_{i}^{+} \nabla f(\x_0) - \x_{i}$ determine whether we take an in-face step or shadow step\protect\footnotemark.}
    \label{fig:pyramidal width}
\end{figure}
\footnotetext{This example is inspired by Damiano Zeffiro.}

We now establish the correctness of \textsc{Trace} and prove the bound on the number of breakpoints of projections curve:
\begin{restatable}[Bound on breakpoints in parametric projections curve]{theorem}{breakpoints}
\label{breakpoints}
Let $P \subseteq \mathbb{R}^n$ be a polytope, with $m$ facet inequalities (e.g., as in \eqref{polytope}) and fix $\mathbf{x}_0 \in P$. Consider any point $\x \in P$ on the projections curve $g(\lambda) =  \Pi_P(\x_0 - \lambda \mathbf{w})$  with an accompanying step-size $\lambda_\x$ satisfying $g(\lambda_\x) =  \Pi_P(\x_0 - \lambda_\x \mathbf{w}) = \x.$ Then, the procedure $\textsc{Trace}(\x_0, \x, \nabla f(\x), \lambda_\x)$ is correct and traces the projections piecewise linear curve until the subsequent breakpoint. Moreover, the total number of breakpoints of the projections curve is at most $O(2^m)$ steps.
\end{restatable}
\begin{proof}
$\textsc{Trace}(\x_0, \x, \nabla f(\x_0), \lambda_\x)$ correctly traces the curve $g(\lambda) = \Pi_P(\mathbf{x}_0 - \lambda \nabla f(\mathbf{x}))$, due to the constructive proof given for Theorem \ref{invariance}. Once the curve leaves the interior of a face, it can no longer visit the face again, since the equivalence of normal cones at two projections implies the projections curve is linear between the two points (which must necessarily lie on the same face) (Lemma \ref{equivalence}). Therefore, the number of breakpoints can be at most the number of faces, i.e.,  $O(2^m)$.
\end{proof}

\section{Descent Directions}\label{sec:descentdirections}
Having characterized the properties of the parametric projections curve, we highlight connections with descent directions in conditional gradient and projected gradient methods. We first highlight a connection between the shadow and the \emph{gradient mapping}. Given any scalar a scalar
$\eta > 0$, the gradient mapping is defined as $G_\eta(\x) \coloneqq \eta (\x - \Pi_P (\x - \nabla f(\x)/\eta)) = \eta (\x - g(1/\eta))$
\footnote{Note that $g(1/\eta)$ can be obtained using $\textsc{Trace}(\mathbf{x}, \nabla f(\x), 1/\eta)$.}. Observe that if $\eta \leq \lambda_{1}^-$, then we have that $G_\eta(\x) = -\eta^2\mathbf{d}_{\mathbf{x}}^\Pi$ using the fact $g(\lambda) = \x +  \lambda \bd_{\x}^\Pi, \text{ for all } \lambda \in [0,\lambda_1^-]$ \eqref{newdirectional1}.

\iffalse
\begin{definition}[Gradient mapping] \label{grad mapping}
Given a convex set $C \subseteq \mathbb{R}^n$, a differentiable function $f : C \to \mathbb{R}$, and a scalar
$\eta > 0$, the gradient mapping of $f$ w.r.t. $\eta$, $C$ is defined by:
\begin{equation} \label{grad map form}
    G_\eta(\x) = \eta \left(\x - \Pi_C \left(\x - \frac{1}{\eta} \nabla f(\x)\right)\right).
\end{equation}
\end{definition}
\fi

We next claim that the shadow is the best local feasible direction of descent in the following sense: it has the highest inner product with the negative gradient at $\x$ compared to any other normalized feasible direction.
\begin{restatable}[Steepest \underline{feasible} descent of Shadow Steps]{lemma}{bestlocaldirection}
\label{best local direction}
Let $P$ be a polytope defined as in \eqref{polytope} and let $\mathbf{x} \in P$ with gradient $\nabla f(\x)$. Let $\mathbf{y}$ be any feasible direction at $\mathbf{x}$, i.e., $\exists \gamma > 0$ s.t. $\mathbf{x} + \gamma \mathbf{y} \in P$. Then
\begin{equation} \label{best local direction equation}
     \innerprod{-\nabla f(\mathbf{x})}{\frac{\mathbf{d}_{\mathbf{x}}^\Pi}{\|\mathbf{d}_{\mathbf{x}}^\Pi\|}}^2  =  \|\mathbf{d}_{\mathbf{x}}^\Pi \|^2 \geq \innerprod {\mathbf{d}_{\mathbf{x}}^\Pi}{\frac{\y}{ \|\y\|}}^2 \geq \innerprod {-\nabla f(\mathbf{x})}{\frac{\y}{ \|\y\|}}^2.
\end{equation}
\end{restatable}

This result is intuitive as $\mathbf{d}_{\mathbf{x}}^\Pi$ is projection of $-\nabla f(\mathbf{x})$ onto the set of feasible directions at $\x$; this is the fact crucially used to prove this result (proof in Appendix \ref{app: proof of best local direction}). The above lemma will be useful in the convergence proof for our novel {\sc Shadow-CG} (Theorem \ref{alg converg2}) and {\sc Shadow-CG$^2$} (Theorem \ref{alg converg3}) algorithms. We also show that the shadow gives a true estimate of convergence to optimal\footnote{{Lemma \ref{best local direction} with $\y = \x^* - \x$ can be used to estimate the primal gap: $\|\mathbf{d}_{\x}^\Pi \|^2 \geq 2 \mu (f(\x) - f(\x^*))$ (see \eqref{deriv performance1})}.}, in the sense that $\|\mathbf{d}_{\mathbf{x}_t} ^\Pi\| = 0$ if and only if $\x_t = \arg\min_{\x\in P} f(\x)$ (Lemma \ref{primal gap optimality}). On the other hand, note that $\|\nabla f(\x_t)\|$ does not satisfy this property and can be strictly positive at the constrained optimal solution. Hence, $\|\mathbf{d}_{\mathbf{x}_t}^\Pi\|$ is a natural quantity for estimating primal gaps without any dependence on geometric constants like those used in other CG variants such as away steps FW and pairwise FW.

\begin{restatable}[Primal gap estimate]{lemma}{primalgapoptimality} \label{primal gap optimality}
Let $P$ be a polytope defined as in \eqref{polytope} and fix $\mathbf{x} \in P$. Then, $\|\mathbf{d}_{\mathbf{x}}^\Pi\| = 0$ if and only if $\x = \x^*$, where $\x^* = \argmin_{\x \in P}f (\x)$.
\end{restatable}

The proof follows from first-order optimality and can be found in Appendix  \ref{sec:app primal gap proof}. We next show that the end point of the projections curve is in fact the FW vertex under mild technical conditions. In other words, FW vertices are the projection of an infinite descent in the direction of the negative gradient (Theorem \ref{FW limit}). Thus, FW vertices are able to obtain the maximum movement in the negative gradient direction while remaining feasible compared to PGD, thereby giving FW steps a new perspective.

\begin{restatable}[Optimism of FW vertex]{theorem}{FWlimit}
\label{FW limit}
Let $P \subseteq{R}^n$ be a polytope and let $\mathbf{x} \in P$. Let $g(\lambda) = \Pi_P(\mathbf{x} - \lambda \nabla f(\mathbf{x}))$ for $\lambda\geq0$. Then, the end point of this curve is:
$
    \lim_{\lambda \to \infty} g(\lambda) = \mathbf{v}^* = \argmin_{\mathbf{v} \in F} \|\mathbf{x} - \mathbf{v}\|^2,
$
where $F = \argmin_{\mathbf{v} \in P} \innerprod{\nabla f(\mathbf{x})}{\mathbf{v}}$ is the face of $P$ that minimizes the gradient $\nabla f(\x)$. In particular, if $F$ is a vertex, then $\lim_{\lambda \to\infty} g(\lambda) = \mathbf{v}^*$ is the FW vertex.
\end{restatable}

\begin{proof}
If $\nabla f(\x) =0$, then $g(\lambda) = \x$ for all $\lambda\in \mathbb{R}^n$, and the theorem holds trivially. We therefore assume that $\nabla f(\x) \neq 0$. Let $\x_{i} \in P$ be the $i$th breakpoint in the projections curve $g(\lambda) = \Pi_{P}(\x_0 -\lambda \nabla f(\x_0))$, with $\x_{i}=\x$ for $i=0$. Using Theorem \ref{breakpoints}, we know that the number of breakpoints curve $k \leq 2^m$. Consider the last breakpoint $\x_k$ in the curve and let $\lambda_k^- = \min \{\lambda \geq 0~|~ g(\lambda) = \x_k\}$. We will now show that $\x_k = \mathbf{v}^*$.
\begin{itemize}
    \item[(i)] We first show that $\x_k \in F$, i.e. $-\nabla f(\x) \in N_P(\x_k)$. Suppose for a contradiction that this not true. Then there exists some $\mathbf{z} \in P$ such that $\innerprod{-\nabla f(\x)}{\mathbf{z} - \x_k} > 0$. Consider any scalar $\bar{\lambda}$ satisfying $\bar{\lambda}  >  \max\{-\frac{\innerprod{\x - \x_k}{\mathbf{z} - \x_k}}{\innerprod{-\nabla f(x)}{\mathbf{z} - \x_k}},\lambda_k^-\}$. Then, using the choice of $\bar{\lambda}$ we have
    \begin{align*}
        &\innerprod{\x - \x_k}{\mathbf{z} - \x_k} + \bar{\lambda}  \innerprod{-\nabla f(\x)}{\mathbf{z} - \x_k} > 0 \\
        &\implies \innerprod{\x -\x_k - \bar{\lambda} \nabla f(\x)}{\mathbf{z} - \x_k} > 0.
    \end{align*}

Now, since  $g(\lambda) = \x_k$ for $\lambda \geq \lambda_k^{-}$, we know that $g(\bar{\lambda}) = \x_k$. Thus, the above equation could be written as
\begin{equation*}
 \innerprod{\x - \bar{\lambda}\nabla f(\x) - g(\bar{\lambda})}{\mathbf{z} -g(\bar{\lambda})} > 0,
\end{equation*}
which contradicts the first-order optimality for $g(\bar{\lambda})$.

    \item[(ii)] We will now show that $\x_k$ is additionally the closest point to $\x$ in $\ell_2$ norm. Again, suppose for contradiction that this not true. Let $\epsilon := \|\x_k - \mathbf{v}^*\| > 0$. First, note that by definition, $g(\lambda) =\argmin_{\y \in P} \left \{ \frac {\| \x - \y \|^2}{2\lambda}   + \innerprod{\nabla f(\x) }{\y} \right\}$ for any $\lambda > 0$. Then, since $g(\lambda_k^-) = \x_k$ we have
\begin{equation} \label{opt of prox1}
    \frac {\| \x -  \x_k\|^2}{2\lambda_k^-}   + \innerprod{\nabla f(\x) }{ \x_k} \leq  \frac {\| \x -  \mathbf{z}\|^2}{2\lambda_k^-}   + \innerprod{\nabla f(\x) }{\mathbf{z}}, ~~{\forall \mathbf{z}\in P}.
\end{equation}

    Moreover, the first-order optimality condition for $\mathbf{v}^*$ (for minimizing $\|\x-\mathbf{y}\|^2$ over $\mathbf{y}\in F$) implies $\innerprod{\mathbf{v}^* - \x}{\mathbf{z} - \mathbf{v}^*} \geq 0$ for all $\mathbf{z} \in F$. In particular, $(\mathbf{v}^* - \x)^T(\x_k - \mathbf{v}^*) \geq 0$ since $\x_k \in F$. Therefore,
\begin{align}
    \|\x - \mathbf{v}^*\|^2 +  \|\x_k - \mathbf{v}^*\|^2 &= \|\x\|^2 + 2\|\mathbf{v}^*\|^2 - 2\x^T\mathbf{v}^* + \|\x_k\|^2 - 2\x_k^T\mathbf{v}^*\\
    &=\|\x_k - \x\|^2 - 2(\mathbf{v}^* - \x)^T(\x_k - \mathbf{v}^*)\\
    &\leq  \|\x_k - \x\|^2. \label{theorem 4 - eq 2}
\end{align}

But then, since $\x_k \in F$, we know that $\innerprod{\nabla f(\x) }{ \x_k} = \innerprod{\nabla f(\x) }{\mathbf{v}^*}$, which implies
\begin{align*}
    \frac {\| \x -  \mathbf{v}^*\|^2}{2\lambda_k^-} + \innerprod{\nabla f(\x)}{ \mathbf{v}^*} & \leq \frac {\|\x_k - \x\|^2 - \|\x_k - \mathbf{v}^*\|^2}{2\lambda_k^-} + \innerprod{\nabla f(\x)}{ \mathbf{v}^*} &&(\text{using \eqref{theorem 4 - eq 2}})\\
    &= \frac {\|\x_k - \x\|^2 - \epsilon}{2\lambda_k^-} + \innerprod{\nabla f(\x)}{ \mathbf{v}^*} &&(\|\x_k - \mathbf{v}^*\| = \epsilon)\\
    &< \frac {\|\x_k - \x\|^2}{2\lambda_k^-} + \innerprod{\nabla f(\x) }{\x_k}, &&(\epsilon > 0)
\end{align*}
contradicting optimality of $\x_{k}$ \eqref{opt of prox1}.
\end{itemize}
   \end{proof}

Next, we show that the shadow steps also give the best away direction emanating from away-vertices in the minimal face at any $\x\in P$ (which is precisely the set of \emph{possible} away vertices (see Appendix \ref{sec: shadow-away}), using Lemma \ref{best local direction} and the following result:

\begin{restatable}[Away steps]{lemma}{awayshadow}
\label{lemma away-shadow}
Let $P$ be a polytope defined as in \eqref{polytope} and fix $\mathbf{x} \in P$. Let $F = \{\mathbf{z} \in P: \A_{I(\x)} \mathbf{z} = \mathbf{b}_{I(\x)}\}$ be the minimal face containing $\x$. Further, choose $\delta_{\max} = \max \{\delta : \mathbf{x} - \delta \mathbf{d}_{\mathbf{x}}^\Pi \in P\}$ and consider the away point $\mathbf{a}_{\x} = \mathbf{x} - \delta_{\max} \mathbf{d}_{\mathbf{x}}^\Pi$ obtained by moving maximally along the the direction of the negative shadow. Then, $\mathbf{a}_{\x}$ lies in $F$ and the corresponding away-direction is simply $\x - \mathbf{a}_{\x} = \delta_{\max} \mathbf{d}_{\x}^{\Pi}$.
\end{restatable}

Lemma \ref{lemma away-shadow} states that the away point obtained by  the maximal movement along the negative shadow from $\x$, $\mathbf{a}_{\x}$, lies in the convex hull of $A \coloneqq \{\mathbf{v} \in \mathrm{vert}(P)\cap F\}$. The set $A$ is precisely the set of all possible away vertices (see Appendix \ref{sec: shadow-away}). Thus, the shadow gives the best direction of descent emanating from the convex hull of all possible away-vertices. We include a proof of this lemma in Appendix \ref{sec: shadow-away}.

config: arxiv


TITLE: Deformation of finite regular languages
QUESTION [2 upvotes]: Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA.
Let $C$ be some class of acyclic DFAs.
Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\sigma$ to a string $w$ of length $n$ by permuting symbols of $w$ according to $\sigma$ and  we denote the new string by $\sigma(w)$.
Let $L(\sigma)=\{\sigma(w) \mid w \in L\}$.
What interesting classes $C$ one can define s.t for any finite regular language $L$, either $L$ has a DFA in the class $C$ (L is recognized by a DFA which satisfies properties of class C) or there is a permutation $\sigma$ such that $L(\sigma)$ has a DFA in the class $C$.
Effect of permutation, an example: $L =\{ww | w \in \{0,1\}^n\}$ has only acyclic DFA of size $\Omega(2^n)$ but there is a $\sigma$ such that $L(\sigma) =\{w_1^2w_2^2\cdots w_n^2 | w \in \{0,1\}^n\}$ has $O(n)$ size DFA. I refer $L(\sigma)$ as a deformation of $L$.
Is there some references for study of these kind? are similar questions for CFL studied?
Thank you.

REPLY [3 votes]: 1) Here is a paper that studies your question in the case of finite languages $L$, and shows that if a finite language $L$ can be decided by an $n$-state DFA, then any permutation of $L$ can be decided by an $m$-state DFA for some $m \leq \frac13 (n^2 + n + 1)$:

Palioudakis A., Cho DJ., Goč D., Han YS., Ko SK., Salomaa K. (2015) The State Complexity of Permutations on Finite Languages over Binary Alphabets. In: Shallit J., Okhotin A. (eds) Descriptional Complexity of Formal Systems. DCFS 2015. Springer Lecture Notes in Computer Science, vol 9118.

See slides here.
2) You might be interested in studies of read-once (algebraic) branching programs. Technically, this is a setting where the order of the input matters, but many of the results in this area apply regardless of how the input is ordered. While ro(A)BPs are slightly stronger than DFAs, they are closely related.


TITLE: Average over the Bloch sphere
QUESTION [0 upvotes]: Consider you have a function of a two-level wave quantum state $f(\vert \psi \rangle ) $, with $\vert \psi \rangle = \alpha \vert 0 \rangle + \beta e^{\rm i \phi} \vert 1 \rangle$.
With no loss of generality, I rewrite $f$ as function of $f( \beta, \phi)$, as the constraint $\sqrt{\alpha^2 + \beta ^ 2} = 1$ allows me to do. In case I want the average value of this function $\langle f \rangle$ over all the possible states, I consider the integral $$\langle f \rangle = \frac{1}{2 \pi} \int\int \, d\beta d\phi f(\beta, \phi).$$
In case I want to average over the Bloch sphere, I find myself in a problematic spot. Naively, what I would do is consider the transformation $\alpha = \sin \theta/2$ and $\beta = \cos \theta/2$, and write:
$$\langle f \rangle = \frac{1}{4 \pi} \int \int \, d \theta d \phi f'(\theta, \phi) \sin \theta.
$$
Unfortunately, the two integrals above are not equivalent. Then, my question is: which one is correct? Where is my mistake?

REPLY [2 votes]: In spherical coordinates, you inserted a factor of $ \frac{1}{4\pi}\sin \theta $.
You did this because the spherical area element is
$$ \frac{1}{4\pi}\sin \theta d\theta d\phi $$
not just $d\theta d\phi$. (In particular, this is the area element you get from restricting the Euclidean metric on three-dimensional space to the surface of a two-dimensional sphere). Similarly, in your $\beta,\phi$ parameterization, the area element is not just $\frac{1}{2\pi}d\beta d\phi$. It's easiest to find it by considering the transformation $\phi \rightarrow \phi, \theta \rightarrow \beta = \cos \frac{\theta}{2} $. We get
$$d\phi \rightarrow d\phi$$
$$ d\theta \rightarrow -\frac{1}{2}\sin\frac{\theta}{2}d\beta $$
so our new area element is
$$ \frac{1}{4\pi}\sin \theta d\theta d\phi \rightarrow -\frac{1}{8\pi}\sin\cos^{-1}\beta d\beta d\phi $$
$$ = -\frac{1}{8\pi}\sqrt{1 - \beta^2} d\beta d\phi $$
This area element is oriented, but for your application you can probably just ignore the minus sign.
Notice that you could have gone the other way, and instead found an area element with $\theta,\phi$ which matches your "natural" area element for $\beta,\phi$. However, the metric on the Bloch sphere is physically meaningful, since it's the unique rotationally-invariant measure on a qubit. The other metric doesn't have any physical meaning as far as I know, so it's probably not the one you're interested in.


TITLE: What am I doing wrong in my proof?
QUESTION [5 upvotes]: If $f$ is continuously differentiable on $[a,b]$, then show that for all $x,y\in(a,b)$ using the definition of derivative
  $$
|f(x)-f(y)|\leq|x-y|\sup_{x\in[a,b]}|f'(x)|
$$

My attempt: Since $f'$ is continuous on $[a,b]$, it is bounded so there is $M>0$ such that $|f'(y)|\leq M$ for all $y\in[a,b]$. On the other hand, the extreme value theorem implies that $\sup_{y\in[a,b]}|f'(y)|$ exists so we can have
$|f'(y)|\leq\sup_{y\in[a,b]}|f'(y)|$ for all $y\in[a,b]$. Since $f$ is differentiable at $y$ by the definition of derivative I have
$$
f'(y)=\lim_{x\to y}\frac{f(x)-f(y)}{x-y}
$$
By using the precise definition of limit and some manipulations I get: for $\epsilon=1$ there exists $\delta>0$ such that
$$
0<|x-y|<\delta\Longrightarrow|f(x)-f(y)|\leq(1+|f'(y)|)|x-y|
$$
But because of $|f'(y)|\leq\sup_{y\in[a,b]}|f'(y)|$ for all $y\in[a,b]$, I get
$$
0<|x-y|<\delta\Longrightarrow|f(x)-f(y)|\leq\left(1+\sup_{y\in[a,b]}|f'(y)|\right)
|x-y|
$$
which is different from what I was supposed to prove!

REPLY [3 votes]: If you keep dividing a closed interval repeatedly into two halves and pick one of the sub-intervals at each step the there will be  a unique point in the intersection. (The left end points form an increasing sequence and the right end points form an decreasing sequence, so they both have a limit and the lengths of the intervals tends to 0. Hence there is a unique point in the intersection).  If you are willing to use this fact then a proof can be given without any other theorem: suppose there exist $x,y$ such that $|f(x)-f(y)|>M|x-y|$ where $M>\sup \{|f'(x)|:a\leq x \leq b\}$. We may suppose $x<y$ Let $u= \frac {x+y} 2$. Then either $|f(x)-f(u)|>M|x-u|$ or $|f(u)-f(y)|>M|u-y|$. In the first case consider the interval $[x,u]$ and in the second case consider $[u,y]$. Repeating this process we get a decreasing sequence of intervals $[u_n,v_n]$ such that $|f(u_n)-f(v_n)|>M|u_n-v_n|$ for all $n$. Let $z$ be the unique point in the intersection of these intervals. Then $x_n \to z$ and $y_n \to z$. Since $\frac {f(u_n)-f(v_n)} {u_n-v_n} \to f'(z)$ we get a  contradiction by letting $n \to \infty$ in the inequality $|f(u_n)-f(v_n)|>M|u_n-v_n|$


text:
\subsection{Related Work}
\paragraph{Second order Optimization} Second order optimization has received a lot of attention in the recent years in the distributed setting owing to its attractive convergence speed. The fundamentals of second order optimization is laid out in \cite{dane}, and an extension with better convergence rates is presented in \cite{aide}. Recently, in GIANT \cite{giant} algorithm, each worker machine computes an approximate Newton direction in each iteration and the center machine averages them to obtain a \emph{globally improved} approximate Newton direction.  Furthermore, DINGO \cite{dingo} generalizes second order optimization beyond convex functions by extending the Newton-MR \cite{newtonmr} algorithm in a distributed setting. Very recently, \cite{deter} proposes Determinantal averaging to correct the inversion bias of the second order optimization. A slightly different line of work (\cite{wangsketched}, \cite{oversketched}, \cite{newtonsketch}) uses Hessian sketching to solve a large-scale distributed learning problems.

\paragraph{Byzantine Robust Optimization:} In the seminal work of \cite{feng},  a generic framework of one shot median based robust learning has been proposed and analyzed in the distributed setting.  The issue of Byzantine failure is tackled by grouping the servers in batches and computing the median of batched servers in
\cite{chen} (the median of means algorithm). Later in \cite{dong,dong1}, co-ordinate wise median, trimmed mean and iterative filtering based algorithm have been proposed and
optimal statistical error rate is obtained. Also,  \cite{mhamdi2018hidden,Damaskinos} consider adversaries may steer convergence to bad local minimizers for non-convex optimization problems.


TITLE: Show that $Y_n$ converges to Y almost surely.
QUESTION [0 upvotes]: Let $Y_1$, $Y_2$,... be a sequence of random variables on a probability space ($\Omega$ , F , $\mu$). Assume that there is a random variable Y on the same probability space such that for any $\epsilon$>0, $$\sum_{n=1}^\infty P\{\lvert Y_n-Y \lvert > \epsilon \} < \infty.$$ Show that $Y_n$ converges to Y almost surely.

What I believe to be the definition of almost sure convergence is,
$$ P(w: \lim_{n \rightarrow \infty}Y_n = Y) = P( \bigcup_{\epsilon>0 \ rationals}  \bigcap_{m=1}^{\infty} \bigcup_{n > m}^{\infty} \ \{ |Y_n - Y| < \epsilon \}) = 1  $$
Like the answer below suggested. We the apply the Borel-Cantelli Lemma which states
$$ \ If \ \sum_{n=1}^{\infty} P(A_n)< \infty, \ then \ P(A_n \ i.o) = P(  \limsup_{n \rightarrow \infty}\ A_n) = P(\bigcap_{m=1}^{\infty} \bigcup_{n = m}^{\infty}A_n)=0.$$
From our assumptions, since we know for any $\epsilon>0$, $\sum_{n=1}^\infty P\{\lvert Y_n-Y \lvert > \epsilon \} < \infty$.
If we define $A_n= {|Y_n -Y|>\epsilon}$, we can say $$P(\bigcup_{\epsilon>0  \ rationals \ } \bigcap_{m=1}^{\infty} \bigcup_{n = m}^{\infty} \{|Y_n-Y|> \epsilon \})=0.$$
Thus applying De-Morgans Law we can say, $$ P(\bigcap_{\epsilon>0 \ rationals \ } \bigcup_{m=1}^{\infty} \bigcap_{n=m}^{\infty} \{ |Y_n-Y| < \epsilon\}) = 1. $$
This implies $$ P( \bigcup_{\epsilon > 0 \ rationals}\bigcup_{m=1}^{\infty} \bigcap_{n=m}^{\infty} \{ |Y_n-Y| < \epsilon\}) = 1. $$
We can also note $$\bigcup_{m=1}^{\infty} \bigcap_{n=m}^{\infty} \{ |Y_n-Y| < \epsilon\} \subset  \bigcap_{m=1}^{\infty} \bigcup_{n = m}^{\infty} \{|Y_n-Y|> \epsilon \}$$.
Is this enough to show it converges almost surely? I remember being told you also have to show the two sets on both the LHS and RHS have the same elements? If so how would you go about doing this?

REPLY [3 votes]: Since $\sum_{n=1}\mathbb P(|Y_n-Y|>\varepsilon)<\infty$, the Borel-Cantelli lemma implies that
$$\mathbb P\left(\limsup_{n\to\infty} |Y_n-Y|>\varepsilon\right) = 0. $$
From this we conclude that $Y_n\to Y$ a.s.