[proofplan] The squared loss is a quadratic function of $\beta$, so its first-order Taylor remainder in the direction $\delta$ is exactly the quadratic form displayed in the first step. We first fix the [sparsity cone](/page/Sparsity%20Cone) and the zero-tolerance [restricted strong convexity](/page/Restricted%20Strong%20Convexity) convention, then compute the Taylor remainder explicitly. The RSC inequality is then precisely the [restricted eigenvalue](/page/Restricted%20Eigenvalue) lower bound after squaring, and the converse follows by reversing this algebraic implication. Although the loss is defined using the response vector $Y$, the Taylor remainder cancels the residual terms, so the resulting equivalence depends only on the design matrix $X$. [/proofplan]

[step:Fix the sparsity cone and the zero-tolerance restricted strong convexity condition] Let $X \in \mathbb{R}^{n \times p}$ be the design matrix and let $Y \in \mathbb{R}^n$ be the response vector appearing in the theorem statement. Let $S \subset \{1,\dots,p\}$ be the index set, let $c \geq 0$ be the cone parameter, and let $\alpha\geq0$ be the curvature parameter. For a vector $v \in \mathbb{R}^p$ and an index set $A \subset \{1,\dots,p\}$, let $v_A \in \mathbb{R}^{|A|}$ denote the subvector of $v$ with indices in $A$, and let $A^c := \{1,\dots,p\}\setminus A$ denote the complement of $A$. Define the [sparsity cone](/page/Sparsity%20Cone) \begin{align*} \mathcal C(S,c) := \{\delta \in \mathbb{R}^p : |\delta_{S^c}|_1 \leq c|\delta_S|_1\}. \end{align*} For the squared-loss map $L_n: \mathbb{R}^p \to \mathbb{R}$ defined by \begin{align*} L_n(\beta) := \frac{|Y-X\beta|^2}{2n}, \qquad \beta \in \mathbb{R}^p, \end{align*} restricted strong convexity on $\mathcal C(S,c)$ with curvature $\alpha$ and tolerance $\tau=0$ means that for every $\beta \in \mathbb{R}^p$ and every $\delta \in \mathcal C(S,c)$, \begin{align*} L_n(\beta+\delta)-L_n(\beta)-\nabla L_n(\beta)\cdot \delta \geq \frac{\alpha}{2}|\delta|^2. \end{align*} [/step]

[step:Compute the exact quadratic remainder of the squared loss]Fix $\beta \in \mathbb{R}^p$ and $\delta \in \mathbb{R}^p$. Define the residual vector $r_\beta \in \mathbb{R}^n$ by $r_\beta := Y - X\beta$. Then $Y - X(\beta+\delta) = r_\beta - X\delta$. This is the only point at which $Y$ enters the computation; the residual-linear terms will be subtracted by the first-order Taylor term. Using the Euclidean [inner product](/page/Inner%20Product) on $\mathbb{R}^n$, we expand the square as \begin{align*} |r_\beta - X\delta|^2 = |r_\beta|^2 - 2r_\beta \cdot X\delta + |X\delta|^2. \end{align*} Since $r_\beta \cdot X\delta = (X^\top r_\beta)\cdot \delta$, this gives \begin{align*} L_n(\beta+\delta) = L_n(\beta) - \frac{1}{n}(X^\top r_\beta)\cdot \delta + \frac{1}{2n}|X\delta|^2. \end{align*} Since \begin{align*} \nabla L_n(\beta) = -\frac{1}{n}X^\top(Y-X\beta) = -\frac{1}{n}X^\top r_\beta, \end{align*} we obtain the exact identity \begin{align*} L_n(\beta+\delta)-L_n(\beta)-\nabla L_n(\beta)\cdot \delta = \frac{1}{2n}|X\delta|^2. \end{align*}[/step]

[guided]We want to compare restricted strong convexity with a lower bound on $|X\delta|$. Since $L_n$ is a quadratic map from $\mathbb{R}^p$ to $\mathbb{R}$, the first-order Taylor remainder should be exactly its second-order quadratic term. We now compute that term without hiding any dependence on $\beta$. Fix $\beta \in \mathbb{R}^p$ and $\delta \in \mathbb{R}^p$. Define the residual vector \begin{align*} r_\beta := Y - X\beta \in \mathbb{R}^n. \end{align*} Then the residual after perturbing $\beta$ by $\delta$ is \begin{align*} Y - X(\beta+\delta) = Y - X\beta - X\delta = r_\beta - X\delta. \end{align*} Substituting this into the definition of $L_n$ gives \begin{align*} L_n(\beta+\delta) &= \frac{1}{2n}|r_\beta - X\delta|^2. \end{align*} The Euclidean norm identity $|a-b|^2 = |a|^2 - 2a\cdot b + |b|^2$, applied with $a=r_\beta$ and $b=X\delta$, yields \begin{align*} |r_\beta - X\delta|^2 = |r_\beta|^2 - 2r_\beta \cdot X\delta + |X\delta|^2. \end{align*} Substituting this identity into the preceding display gives \begin{align*} L_n(\beta+\delta) = \frac{1}{2n}|r_\beta|^2 - \frac{1}{n}r_\beta \cdot X\delta + \frac{1}{2n}|X\delta|^2. \end{align*} The first term is exactly $L_n(\beta)$, because $r_\beta=Y-X\beta$. For the linear term, the defining property of matrix transpose gives \begin{align*} r_\beta \cdot X\delta = (X^\top r_\beta)\cdot \delta. \end{align*} Therefore \begin{align*} L_n(\beta+\delta) = L_n(\beta) - \frac{1}{n}(X^\top r_\beta)\cdot \delta + \frac{1}{2n}|X\delta|^2. \end{align*} Differentiating the map $\beta \mapsto |Y-X\beta|^2/(2n)$ gives \begin{align*} \nabla L_n(\beta) = -\frac{1}{n}X^\top(Y-X\beta) = -\frac{1}{n}X^\top r_\beta. \end{align*} Thus the linear term in the expansion is precisely $\nabla L_n(\beta)\cdot \delta$, and subtracting it leaves \begin{align*} L_n(\beta+\delta)-L_n(\beta)-\nabla L_n(\beta)\cdot \delta = \frac{1}{2n}|X\delta|^2. \end{align*} This identity is the whole mechanism of the theorem: for squared loss, [restricted strong convexity](/page/Restricted%20Strong%20Convexity) is not an additional analytic estimate beyond the restricted lower bound on the design matrix; it is the same inequality written as a Taylor remainder. The response vector $Y$ has disappeared from the remainder, so the equivalence is a property of $X$ on the cone $\mathcal C(S,c)$.[/guided]

[step:Derive the restricted eigenvalue lower bound from restricted strong convexity] Assume $L_n$ satisfies [restricted strong convexity](/page/Restricted%20Strong%20Convexity) on $\mathcal{C}(S,c)$ with curvature $\alpha$ and tolerance $\tau=0$, in the sense fixed above. Let $\delta \in \mathcal{C}(S,c)$. Applying that RSC inequality with any fixed $\beta \in \mathbb{R}^p$ gives \begin{align*} L_n(\beta+\delta)-L_n(\beta)-\nabla L_n(\beta)\cdot \delta \geq \frac{\alpha}{2}|\delta|^2. \end{align*} The exact quadratic remainder identity identifies the left-hand side as $|X\delta|^2/(2n)$, so \begin{align*} \frac{1}{2n}|X\delta|^2 \geq \frac{\alpha}{2}|\delta|^2. \end{align*} Multiplying by $2$ gives \begin{align*} \frac{|X\delta|^2}{n} \geq \alpha |\delta|^2. \end{align*} Both sides are non-negative, so taking square roots gives \begin{align*} \frac{|X\delta|}{\sqrt{n}} \geq \sqrt{\alpha}\,|\delta|. \end{align*} Since $\delta \in \mathcal{C}(S,c)$ was arbitrary, the [restricted eigenvalue](/page/Restricted%20Eigenvalue) lower bound holds on $\mathcal{C}(S,c)$. [/step]

[step:Recover restricted strong convexity from the restricted eigenvalue lower bound] Assume that \begin{align*} \frac{|X\delta|}{\sqrt{n}} \geq \sqrt{\alpha}\,|\delta| \end{align*} for every $\delta \in \mathcal{C}(S,c)$. Squaring both sides gives \begin{align*} \frac{|X\delta|^2}{n} \geq \alpha |\delta|^2 \end{align*} for every $\delta \in \mathcal{C}(S,c)$, because both sides of the original inequality are non-negative. Let $\beta \in \mathbb{R}^p$ and $\delta \in \mathcal{C}(S,c)$. Using the exact quadratic remainder identity, \begin{align*} L_n(\beta+\delta)-L_n(\beta)-\nabla L_n(\beta)\cdot \delta = \frac{1}{2n}|X\delta|^2. \end{align*} Combining this identity with the squared restricted eigenvalue bound gives \begin{align*} L_n(\beta+\delta)-L_n(\beta)-\nabla L_n(\beta)\cdot \delta \geq \frac{\alpha}{2}|\delta|^2. \end{align*} This is precisely [restricted strong convexity](/page/Restricted%20Strong%20Convexity) on $\mathcal{C}(S,c)$ with curvature $\alpha$ and tolerance $\tau=0$, according to the definition fixed at the start of the proof. [/step]