Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a continuously differentiable strongly convex function with a globally $L$-Lipschitz continuous gradient. The normal gradient method for computing the unconstrained minimizer $x^{\star}$ is
$$
x_{k+1} = x_k-\alpha \nabla f(x_k).
$$
Successive steps satisfy the bound
$$
\begin{aligned}
\|x_{k+1} – x_k\|_2 &= \alpha \|\nabla f(x_k)\|_2 = \alpha \|\nabla f(x_k)-\nabla f(x^{\star})\|_2\\
&\leq \alpha L\|x_{k}-x^{\star}\|_2.
\end{aligned}
$$
where I used $\nabla f(x^{\star}) = 0$. This bound has two features (i) it is linear in $\|x_k-x^{\star}\|_2$ and (ii) it is linear in $\alpha$ … very intuitive of course, if the step size is small, you don't move much.
I am looking for a similar bound for the projected gradient descent method
\begin{align}\tag{1}\label{Eq:PGD}
x_{k+1} = \mathrm{Proj}_{X}(x_{k}-\alpha \nabla f(x_k))
\end{align}
where $X$ is a closed non-empty convex set. I will let $\bar{x} \in X$ denote the constrained optimizer. For me, linearity of the bound in $\|x_{k}-\bar{x}\|_2$ is crucial, and it should have the property that it tends to zero as $\alpha \to 0$ (though I can tolerate lack of linearity there). I am recording my best attempts at this below.
Preliminary Inequalities. Let $\mathcal{N}_{X}(x)$ denote the normal cone of $X$ at the point $x \in X$. Recall that
$$
\mathcal{N}_{X}(x) := \{y \in \mathbb{R}^n\,\,:\,\,y^{\sf T}(z-x) \leq 0\quad \forall z \in X\}.
$$
It is well known $\mathrm{Proj}_{X}$ is the so-called resolvent operator associated with the normal cone, expressed as $\mathrm{Proj}_{X}(x) = (\mathrm{Id}+\mathcal{N}_{X})^{-1}(x)$. With this, the PGD update law (\ref{Eq:PGD}) and the optimality condition can be equivalently written as
$$
\begin{aligned}
x_{k} – x_{k+1} – \alpha \nabla f(x_k) &\in \mathcal{N}_{X}(x_{k+1})\\
-\alpha \nabla f(\bar{x}) &\in \mathcal{N}_{X}(\bar{x})
\end{aligned}
$$
Expressing these in terms of the definition of the normal cone, the previous inclusions are precisely that
$$
\begin{aligned}
(x_{k}-x_{k+1}-\alpha \nabla f(x_k))^{\sf T}(z-x_{k+1}) &\leq 0, \quad z \in X\\
-\alpha \nabla f(\bar{x})^{\sf T}(z-\bar{x}) &\leq 0, \quad z \in X
\end{aligned}
$$
In particular, the first holds at $z = x_k$ and $z = \bar{x}$, which quickly yields the two inequalities
\begin{align}\label{Eq:FNE1-a}\tag{2}
\|x_{k+1}-x_{k}\|_2^2 &\leq -\alpha (x_{k+1}-x_{k})^{\sf T}\nabla f(x_k)\\
\label{Eq:FNE1-b}\tag{3}
(x_{k+1}-x_{k})^{\sf T}(x_{k+1}-\bar{x}) &\leq -\alpha (x_{k+1}-\bar{x})^{\sf T}\nabla f(x_k).
\end{align}
A simple identity to re-express the LHS of (\ref{Eq:FNE1-b}) is
\begin{align}\label{Eq:FNE1-c}\tag{4}
(x_{k+1}-x_{k})^{\sf T}(x_{k+1}-\bar{x}) = \tfrac{1}{2}\|x_{k+1}-x_{k}\|_2^2 – \tfrac{1}{2}\left(\|x_{k}-\bar{x}\|_2^2 – \|x_{k+1}-\bar{x}\|_2^2\right)
\end{align}
These two inequalities are in fact equivalent to what one can obtain by applying firm non-expansiveness of the projection operator, which yields the alternative (but again, equivalent) expressions
\begin{equation}\label{Eq:FNE2}
\begin{aligned}
\|x_{k+1}-x_{k}\|_2^2 & \leq \alpha^2 \|\nabla f(x_k)\|_2^2 – \|x_{k} – x_{k+1} – \alpha \nabla f(x_k)\|_2^2\\
\|x_{k+1}-\bar{x}\|_2^2 &\leq \|x_{k}-\alpha \nabla f(x_k) – \bar{x}\|_2^2 – \|x_{k} – x_{k+1} – \alpha \nabla f(x_k)\|_2^2.
\end{aligned}
\end{equation}
Similarly, evaluating the optimality conditions at $z = x_k$ and $z = x_{k+1}$ we obtain
\begin{align}\label{Eq:Optimality-a}\tag{5}
\alpha (x_{k}-\bar{x})^{\sf T}\nabla f(\bar{x}) &\geq 0\\
\label{Eq:Optimality-b}\tag{6}
\alpha (x_{k+1}-\bar{x})^{\sf T}\nabla f(\bar{x}) &\geq 0.
\end{align}
Attempt #1 — Simple Upper Bound Using non-expansiveness of the projection and $x_k = \mathrm{Proj}_{X}(x_k)$ one can compute
$$
\begin{aligned}
\|x_{k+1}-x_{k}\| &= \|\mathrm{Proj}_{X}(x_{k}-\alpha \nabla f(x_k)) – \mathrm{Proj}_{X}(x_k)\|_2\\
&\leq \alpha \|\nabla f(x_k)\|_2\\
&= \alpha \|\nabla f(x_k)-\nabla f(\bar{x}) + \nabla f(\bar{x})\|_2\\
&\leq \alpha L \|x_k-\bar{x}\|_2 + \alpha \|\nabla f(\bar{x})\|_2
\end{aligned}
$$
This resembles the above, but with an additional constant term quantifying how active the gradient of $f$ is at the constrained optimizer. The bound however does not force $\|x_{k+1}-x_{k}\|_2$ to go to zero as $x_k \to \bar{x}$, which is what should happen.
Attempt #2(a) Beginning from the preliminary inequality (\ref{Eq:FNE1-a}), we have
$$
\begin{aligned}
\|x_{k+1}-x_{k}\|_2^2 &\leq -\alpha (x_{k+1}-x_{k})^{T}\nabla f(x_k)\\
&= -\alpha (x_{k+1}-\bar{x}+\bar{x}-x_{k})^{T}\nabla f(x_k)\\
&\leq \alpha (\|x_{k+1}-\bar{x}\|_2 + \|x_{k}-\bar{x}\|_2) \|\nabla f(x_k)-\nabla f(\bar{x})+\nabla f(\bar{x})\|_2\\
\end{aligned}
$$
For small enough step sizes the forward-backward step is a contraction operator and the iterates satisfy
$$
\|x_{k+1}-\bar{x}\|_2 \leq \sqrt{(1-\alpha \mu)} \|x_k-\bar{x}\|_2 = c_{\alpha}\|x_k-\bar{x}\|.
$$
It therefore follows that
$$
\begin{aligned}
\|x_{k+1}-x_{k}\|_2^2 &\leq \alpha (1+c_{\alpha})\|x_{k}-\bar{x}\|_2 (L\|x_{k}-\bar{x}\|_2 + \|\nabla f(\bar{x})\|_2)\\
&= \alpha L(1+c_{\alpha})\|x_k-\bar{x}\|_2^2 + \alpha (1+c_{\alpha})\|\nabla f(\bar{x})\|_2\|x_{k}-\bar{x}\|_2.
\end{aligned}
$$
So we conclude that
$$
\|x_{k+1}-x_{k}\|_2 \leq \sqrt{2\alpha L\|x_k-\bar{x}\|_2^2 + 2\alpha \|\nabla f(\bar{x})\|_2\|x_{k}-\bar{x}\|_2},
$$
On any ball of size $r_0$ around the point $\bar{x}$, we can therefore obtain a bound of the form
$$
\|x_{k+1}-x_{k}\|_2 \leq \sqrt{\alpha\|x_{k}-\bar{x}\|_2}\sqrt{2Lr_0 + 2\|\nabla f(\bar{x})\|_2},
$$
This has the right qualitative behaviour, but it has square-root dependence in $\alpha$ and $\|x_k-\bar{x}\|_2$; for my application of interest, the latter is problematic.
Attempt #2(b) If we instead begin from the other preliminary inequality (\ref{Eq:FNE1-b}) we can compute that
$$
\begin{aligned}
2(x_{k+1}-x_{k})^{\sf T}(x_{k+1}-\bar{x}) &\leq – 2\alpha (x_{k+1}-\bar{x})^{\sf T}[\nabla f(x_k)]\\
&= – 2\alpha (x_{k+1} – \bar{x})^{\sf T}[\nabla f(\bar{x}) + \nabla f(x_k) – \nabla f(\bar{x})]\\
&= – 2\alpha(x_{k+1} – \bar{x})^{\sf T}\nabla f(\bar{x}) – 2\alpha (x_{k+1}-x_{k} + x_{k}-\bar{x})^{\sf T}(\nabla f(x_k) – \nabla f(\bar{x}))\\
&= – 2\alpha(x_{k+1} – \bar{x})^{\sf T}\nabla f(\bar{x})\\
&\qquad – 2\alpha (x_{k+1}-x_{k})^{\sf T}(\nabla f(x_k) – \nabla f(\bar{x}))\\
&\qquad – 2\alpha(x_{k}-\bar{x})^{\sf T}(\nabla f(x_k) – \nabla f(\bar{x}))
\end{aligned}
$$
The first term is non-positive by the optimality condition (\ref{Eq:Optimality-b}). The second term we upper bound using the Lipschitz constant of $f$, and the third term we upper bound using strong convexity of $f$. We quickly obtain
$$
2(x_{k+1}-x_{k})^{\sf T}(x_{k+1}-\bar{x}) \leq -2\alpha m\|x_{k}-\bar{x}\|_2^2 + 2\alpha L \|x_{k+1}-x_{k}\|_2\|x_{k}-\bar{x}\|_2
$$
Using (\ref{Eq:FNE1-c}) to replace the left-hand side, we have
$$
\begin{aligned}
\|x_{k+1}-x_{k}\|_2^2 &\leq \left(\|x_{k}-\bar{x}\|_2^2 – \|x_{k+1}-\bar{x}\|_2^2\right)\\
&\qquad -2\alpha m\|x_{k}-\bar{x}\|_2^2\\
&\qquad + 2\alpha L \|x_{k+1}-x_{k}\|_2\|x_{k}-\bar{x}\|_2
\end{aligned}
$$
Dropping the second term on the RHS and resolving the resulting quadratic,
we obtain the bound
$$
\|x_{k+1}-x_{k}\|_2 \leq \left(\alpha L + \sqrt{1-2\alpha m + \alpha^2L^2}\right)\|x_{k}-\bar{x}\|_2
$$
which has nice linear behaviour in $\|x_{k}-\bar{x}\|_2$ but does not go to zero as $\alpha \to 0$.
Attempt #3 — Using Averaged Operators The projection operator is firmly non-expansive, and is therefore $1/2$-averaged. If $\alpha \in (0,2/L)$, the forward step operator $F(x) = (I-\alpha \nabla f)(x)$ is averaged with parameter $\alpha L/2$, since it can be written as
$$
F(x) = (I-\tfrac{\alpha L}{2})x + \tfrac{\alpha L}{2}\left(x-\frac{2}{L}\nabla f(x)\right).
$$
It follows [Bauschke, Prop 4.32] that the forward-backward operator $T(x) = \mathrm{Proj}_{X}(x-\alpha\nabla f(x))$ is averaged with parameter
$$
\gamma = \frac{2}{1+\frac{1}{\max\{\tfrac{1}{2},\tfrac{\alpha L}{2}\}}} = \begin{cases}
2/3 &\text{if} \quad \alpha \in (0,1/L]\\
\frac{2\alpha L}{2+\alpha L} &\text{if} \quad \alpha \in (1/L,2/L)
\end{cases}
$$
Since $T$ is $\gamma$-averaged, it satisfies the inequality [Bauschke, Prop 4.25(iii)]
$$
\|T(x)-T(y)\|_2^2 \leq \|x-y\|_2^2 – \frac{1-\gamma}{\gamma}\|x – T(x) – y + T(y)\|_2^2.
$$
Set $x = x_{k}$, so that $T(x) = x_{k+1}$, and set $y = \bar{x}$, so that $T(y) = \bar{x}$. Then
$$
\|x_{k+1}-\bar{x}\|_2^2 \leq \|x_{k}-\bar{x}\|_2^2 – \epsilon\|x_{k+1}-x_{k}\|_2^2
$$
where
$$
\epsilon = \frac{1-\gamma}{\gamma} = \begin{cases}
1/2 &\text{if} \quad \alpha \in (0,1/L)\\
\frac{2-\alpha L}{\alpha L} &\text{if} \quad \alpha \in (1/L,2/L).
\end{cases}
$$
For $\alpha \in (0,1/L]$ we therefore obtain
$$
\begin{aligned}
\tfrac{1}{2}\|x_{k+1}-x_{k}\|_2^2 &\leq \|x_{k}-\bar{x}\|_2^2 – \|x_{k+1}-\bar{x}\|_2^2\\
\end{aligned}
$$
Bounding away the second term, we get
$$
\|x_{k+1}-x_{k}\|_2 \leq \sqrt{2}\|x_{k}-\bar{x}\|_2
$$
which slightly improves on Zim's bound, but does not have the right qualitative behaviour as $\alpha \to 0$. Intuitively, the quantity $\|x_{k}-\bar{x}\|_2^2 – \|x_{k+1}-\bar{x}\|_2^2$ should be proportional to $\alpha^2\|x_k-\bar{x}\|_2^2$, but convergence gives me a lower bound on this quantity, not an upper bound.
Simple Lower Bound Not directly what I'm looking for, but interesting and easy. Applying the reverse triangle inequality, we have
$$
\begin{aligned}
\|x_{k+1}-x_{k}\|_2 &= \|x_{k+1}-\bar{x} – (x_{k}-\bar{x})\|_2\\
&\geq \|x_{k}-\bar{x}\|_2 – \|x_{k+1}-\bar{x}\|_2\\
&\geq (1-\sqrt{1-\alpha m})\|x_{k}-\bar{x}\|_2
\end{aligned}
$$
which for small $\alpha$ further implies that
$$
\|x_{k+1}-x_{k}\|_2 \geq \alpha\frac{m}{2}\|x_{k}-\bar{x}\|_2
$$
Best Answer
Unfortunately, it is not possible. What you are looking for is a function $g(\alpha,\mu, L)$ that is dependent only on the Lipschitz constant $L$, the strong convexity constant $\mu$, and the set size $\alpha$, such that $\lim_{\alpha \to 0}g(\alpha, \mu, L)=0$ and \begin{align} ||x_{k+1}-x_{k}|| \leq g(\alpha,\mu,L) ||x_{k}-x^{*}|| \end{align} for any convex set X.
The issue is that the function $g$ has no ''information'' about the set $X$ you are projecting onto, it is independent of the set $X$. Therefore, by choosing the set $X(\alpha)$ as a function of $\alpha$ we can force $g$ to not have the property $\lim_{\alpha \to 0}g(\alpha, \mu, L)=0$.
Consider the following simple example $f(x) = \frac{1}{2}x^{2}$, so $\nabla f(x) = x$. Then $x_{k+1} = P_{X(\alpha)}((1 - \alpha) x_{k})$ and let $P_{X(\alpha)} = \{x\ |\ x\geq 1-\alpha,\ x\in\mathbb{R}\}$. Notice, that the minimizer for the set $X(\alpha)$ is $x^{*} = (1-\alpha)$.
Now let us set $x_0 = 1$, then we see that the condition $||x_{k+1}-x_{k}|| \leq g(\alpha,\mu,L) ||x_{k}-x^{*}||$ at the first iteration is,
\begin{align} ||x_{1}-x_{0}|| &\leq g(\alpha,\mu,L) ||x_{0}-x^{*}|| \\ ||P_{X(a)}((1 - \alpha)1) - 1|| &\leq g(\alpha,\mu,L) ||1-(1-\alpha)|| \\ ||(1 - \alpha) - 1|| &\leq g(\alpha,\mu,L) ||1-(1-\alpha)|| \\ \alpha &\leq g(\alpha,\mu,L) \alpha \\ 1 &\leq g(\alpha,\mu,L) \end{align} This example shows that for any $\alpha \in (0,1)$ you can construct a set $X$ and an initial condition $x_0$ such that $g(\alpha,\mu,L) \geq 1$. Therefore, there is no function $g$ such that $\lim_{\alpha \to 0}g(\alpha, \mu, L)=0$ and \begin{align} ||x_{k+1}-x_{k}|| \leq g(\alpha,\mu,L) ||x_{k}-x^{*}|| \end{align} for any convex set X.