Let $f: \mathbb{R}^n \to \mathbb{R}$ be a $C^2$ function with $L$-Lipschitz continuous gradients such that for some $L > 0$:
\begin{gather*} {\lVert \nabla f(x) - \nabla f(y) \rVert} \le L {\lVert x - y \rVert}, \quad \forall x,y \in \mathbb{R}^n \tag{1} \\ \end{gather*}
which implies that:
\begin{gather*} % Based on Lipschitz gradients. Looser proof in HW1 3.a and in slides. f(y) \le f(x) + \nabla f(x)^T (y-x) + \frac{L}{2} {\lVert y-x \rVert}^2, \quad \forall x,y \in \mathbb{R}^n \tag{2} \\ \end{gather*}
Let $\theta \in [0,1)$ be a constant. Let $x_{k+1} = x_k + \alpha_k p_k$ be an optimization iteration where direction vector $p_k$ is chosen such that:
\begin{gather*} {\lVert p_k + \nabla f(x_k) \rVert}_2 \le \theta {\lVert \nabla f (x_k) \rVert}_2 \tag{3} \\ \end{gather*}
which implies:
\begin{gather*} p_k^T \nabla f(x_k) \le \frac{1}{2} (\theta^2 -1) {\lVert \nabla f (x_k) \rVert}_2^2 - \frac{1}{2} {\lVert p_k \rVert}_2^2 \tag{4} \\ \end{gather*}
and step length $\alpha_k$ is chosen such that for some $c_1 \in (0,1)$, $\tau \in (0,1)$:
\begin{gather*} \alpha_k \ge \frac{2 \tau (c_1 - 1) \nabla f(x_k)^T p_k}{L {\lVert p_k \rVert}_2^2 } \tag{5} \\ \end{gather*}
Show that:
\begin{gather*} \alpha_k \ge \frac{2 \tau (1 - c_1)}{(1 + \theta) L} \\ \end{gather*}
I tried substituting (4) into (5), but this doesn't seem to help or go anywhere:
\begin{gather*} \alpha_k \ge \frac{\tau (c_1 - 1) \left[ (\theta^2 -1) {\lVert \nabla f (x_k) \rVert}_2^2 - {\lVert p_k \rVert}_2^2 \right] }{L {\lVert p_k \rVert}_2^2 } \\ \end{gather*}
Working backwards, we need to show that:
\begin{gather*} \frac{2 \tau (c_1 - 1) \nabla f(x_k)^T p_k}{L {\lVert p_k \rVert}_2^2 } \ge \frac{2 \tau (1 - c_1)}{(1 + \theta) L} \\ \frac{(c_1 - 1) \nabla f(x_k)^T p_k}{{\lVert p_k \rVert}_2^2 } \ge \frac{(1 - c_1)}{(1 + \theta)} \\ % \frac{\nabla f(x_k)^T p_k}{{\lVert p_k \rVert}_2^2 } \le \frac{1}{(1 + \theta)} \\ \nabla f(x_k)^T p_k \le \frac{ {\lVert p_k \rVert}_2^2 }{(1 + \theta)} \\ % (1 + \theta) \nabla f(x_k)^T p_k \le {\lVert p_k \rVert}_2^2 \\ \end{gather*}
and to show that, we would need to show that:
\begin{gather*} \frac{1}{2} (\theta^2 - 1) {\lVert \nabla f (x_k) \rVert}_2^2 - \frac{1}{2} {\lVert p_k \rVert}_2^2 \le \frac{ {\lVert p_k \rVert}_2^2 }{(1 + \theta)} \\ (1 + \theta) (\theta^2 - 1) \frac{ {\lVert \nabla f (x_k) \rVert}_2^2 }{ {\lVert p_k \rVert}_2^2 } - (1 + \theta) \le 2 \\ \left( \frac{ {\lVert \nabla f (x_k) \rVert}_2 }{ {\lVert p_k \rVert}_2 } \right)^2 \le \frac{3 + \theta}{(\theta + 1)^2 (\theta - 1)} \\ \end{gather*}
From there I'm stuck. How do I show that? Or what else can I try here?