Consistency of the minimizer of the convex loss This is an exercise from the Stanford Stat 300B course, which I am auditing and don't have the solutions for. It is taken from the following source (Q2.6): https://web.stanford.edu/class/stats300b/Exercises/all-exercises.pdf. I have been stuck on the question for quite a while and think that I am missing some important part.
Let $\mathcal{X}$ be a measurable space and $X_i \sim P$ be i.i.d, where $P$ is a probability distribution on $\mathcal{X}$. Let $\Theta \subset \mathbb{R}^d$ be an open set and let $l :\Theta \times \mathcal{X} \to \mathbb{R}^{+}$ be a loss function. Define the risk functional $R(\theta) := E_P [l(\theta, X)]$, which is the expected loss of a vector $\theta$. Let $ \theta^* := \arg \min_{\theta\in\Theta} R(\theta)$. Define the empirical risk functional as $\hat{R}_n := \frac{1}{n}\sum_1^n l(\theta, X_i)$. Let $ \hat{\theta}_n := \arg \min_{\theta\in\Theta} \hat{R}_n(\theta)$.
We also have the following assumptions:

*

*$\theta \to l(\theta, x)$ is convex

*$\nabla^2 R(\theta^*) \succ 0$ i.e. the Hessian of the risk is positive definite at $\theta^*$

*$\theta^* \in \text{interior of }\Theta$

*There is a function $H : X → R^+$ such that $E[H^2(X)] < \infty$ and the Hessian $\nabla^2l(\theta, x)$ is $H(x)$-Lipschitz in $\theta$, that is, $$|| \nabla^2l(\theta, x) - \nabla^2l(\theta', x)||_{op} \leq H(x)||\theta - \theta'||~~\forall \theta,\theta'\in\Theta$$

*Assume that gradients and Hessians can be passed through all expectations and integrals and as many moments of $\nabla l$ as you need.

*Also assume the following theorem holds true. If $f$ is convex and satisfies $\nabla^2 f(x) 
 - \lambda I\succ 0$ for all $x$ such that $||x - x_0|| \leq c$, then: $$ f(x) \geq f(x_0) + \nabla f(x_0)(x - x_0) + \frac{\lambda}{2}\min(||x-x_0||^2, c||x-x_0||)$$
Need to show that under these assumptions: $\hat{\theta}_n \to \theta^*$ in probability.
I feel hopelessly overwhelmed by all the details. I am not sure how to approach the problem.
 A: Careful: this proof requires one additionnal technical assumption, that is, that for any $\theta$, $\nabla^2 l(\theta,X)$ be $L^1$ (or, equivalently given condition 4, that $\nabla^2 l(\theta^*,X)$ be $L^1$).
Here's how the proof roughly goes (there's a slight technicality, but this is how the proof works if $\Theta$ is bounded): we show (part two) that there exists some integer $N_0$ such that for any $\theta$ and any $n \geq N_0$, with high probability, the inequality $|\hat{R_n}(\theta)-R(\theta)| \leq \epsilon$ holds.
Thus, with high probability, we have $R(\hat{\theta_n})\leq \hat{R_n}(\hat{\theta_n})+\epsilon \leq \hat{R_n}(\theta^*) +\epsilon\leq R(\theta^*)+2\epsilon$.
Now, $R(\theta)$ is convex, and we know that its minimum is reached at $\theta$ in the interior of the domain, and we know that $R(\hat{\theta_n})$ is close to said minimum (with high probability), which will imply (part one) that $\hat{\theta_n}$ is close to $\theta^*$.
$ $
First part: the convex analysis
By assumption, $R(\theta)$ is a convex function, twice differentiable, with $\theta^*$ as a global minimum, and $\nabla^2 R(\theta^*)$ is positive definite. Let $\lambda > 0$ be its smallest eigenvalue.
Moreover, we have $\|\nabla^2 R(\theta)-\nabla^2R(\theta')\|_{op}\leq\mathbb{E}_{x \sim P}[\|\nabla^2 l(\theta,x)-\nabla^2 l(\theta',x)\|_{op}] \leq \mathbb{E}_x[H(x)\|\theta-\theta'\|] \leq C\|\theta-\theta'\|$, that is $\nabla^2 R$ is Lipschitz continuous with constant $C$. Note that $C,\lambda$ are parameters of the problem.
Let $\theta \in \Theta$ (which we assume is convex), then consider $f(t)=R((1-t)\theta^*+t\theta)$. Then $f$ is $C^2$, convex, minimal at zero (thus increasing), $f'(0)=0$ and $f''(0) \geq \lambda \|\theta-\theta^*\|^2$. We want to show that if $f(1)-f(0)$ is small, then so must be $\delta=\|\theta-\theta^*\|^2$.
Indeed, let $\tau = \lambda/C$ (up to choosing a larger $C$, we assume $\tau < 1$). For $t \leq 1$, $f''(t) \geq \delta(\lambda-Ct)$, so for $t \leq \tau$, $f'(t)\geq \delta\lambda t-\delta Ct^2/2$ and thus $f(t)-f(0) \geq \delta \lambda t^2/2-\delta C t^3/6$. In particular $f(1)-f(0) \geq f(\tau)-f(0) \geq \frac{1}{6}\delta \tau^2 (3\lambda-\tau C)=\frac{\delta \tau^2 \lambda}{3}$.
Thus, we have, for any $\theta \in \Theta$, $$\|\theta-\theta^*\|^2 \leq \frac{3}{\tau^2 \lambda}(R(\theta)-R(\theta^*)).$$
$ $
Second part: the probability
We want to find a uniform bound on $\theta \in \Theta$ on the probability that $|\hat{R_n}(\theta)-R(\theta)|\geq \epsilon$. It turns out that the estimate we really can use (in absence of a $L^2$ moment bound for $l$ which is uniform in $\theta$) requires using derivatives, and thus we'll need to set a positive bound $B>0$ and consider only the $\theta$ such that $\|\theta-\theta^*\| \leq B$.
Now, by Taylor, if $\theta_t=(1-t)\theta^*+t\theta$, $$\hat{R_n}(\theta)-R(\theta) = \hat{R_n}(\theta^*)-R(\theta^*)+\nabla (\hat{R_n}-R)(\theta^*)\cdot (\theta-\theta^*) + \frac{1}{2}(\theta-\theta^*)^T\times \nabla^2(\hat{R_n}-R)(\theta^*)\times (\theta-\theta^*) + \int_0^1{(1-t)(\theta-\theta^*)^T \times (\nabla^2(\hat{R_n}-R)(\theta_t)-\nabla^2(\hat{R_n}-R)(\theta^*)) \times (\theta-\theta^*)\,dt}$$.
Let $V(X) = l(\theta^*,X)$, $G(X)=\nabla l(\theta^*,X)$, $L(X)=\frac{1}{2}\nabla^2 l(\theta^*,X)$. Finally, define $W^{\theta}(X) = \int_0^1{(1-t)(\nabla^2 l(\theta_t,X)-\nabla^2 l(\theta^*,X))\,dt}$.
By the weak law of large numbers, we know that there is a $N=N^0_{\epsilon}(\theta^*,B)$ such that for all $n \geq N$:

*

*$P\left(|\hat{V}_n-\mathbb{E}[V]| \geq \frac{\epsilon}{8}\right) \leq \frac{\epsilon}{8}$.

*$P\left(\|\hat{G}_n-\mathbb{E}[G]\| \geq \frac{\epsilon}{8(B+1)}\right) \leq \frac{\epsilon}{8}$.

*$P\left(\|\hat{L}_n-\mathbb{E}[L]\|_{op} \geq \frac{\epsilon}{8(B+1)^2}\right) \leq \frac{\epsilon}{8}$.

Finally, note that $$\mathbb{E}[\|W^{\theta}\|^2_{op}] \leq \int_0^1{(1-t)^2\mathbb{E}[\|\nabla^2 l(\theta_t,X)-\nabla^2 l(\theta^*,X)\|_{op}^2]\,dt} \leq \int_0^1{(1-t)^2\mathbb{E}[H^2]\|\theta_t-\theta^*\|^2\,dt} = \|\theta-\theta^*\|^2\mathbb{E}[H^2] \int_0^1{(1-t)^2t^2\,dt} \leq C'B^2$$ for some $C' > 0$.
Thus, reasoning coordinate-wise, and recalling that the variance of a $L^2$ random variable $A$ is at most $\mathbb{E}[A^2]$, we have $P\left(\|(\hat{W^{\theta}})_n-\mathbb{E}[W^{\theta}]\|^2 \geq \frac{\epsilon^2}{64(B+1)^4}\right) \leq \frac{64C'B^2(B+1)^4}{n\epsilon^2}$.
So if $n$ is large enough, with probability at least $1-\epsilon/8$ that $|(\theta-\theta^*)^T \times ((\hat{W^{\theta}})_n - \mathbb{E}[W^{\theta}]) \times (\theta-\theta^*)| \leq \frac{\epsilon}{8}$.
It follows from this that with for $n \geq N_{\epsilon}(\theta^*,B)$, for any $\theta \in \Theta$ at distance at most $B$ of $\theta^*$, with probability at least $1-\epsilon/2$, $|\hat{R}_n(\theta)-R(\theta)| \leq \frac{\epsilon}{2}$.
$ $
Part three: the complete proof
Fix $B > \sqrt{\frac{3}{\tau^2 \lambda}}$, some $0 < \epsilon < 1$ and take $n \geq N_{\epsilon}(\theta^*,B)$.
Now choose $\theta$ on the line segment linking $\hat{\theta_n}$ to $\theta^*$ and at distance at most $B$ of $\theta^*$.
Then with probability $1-\epsilon$, the inequalities $\hat{R_n}(\theta^*) \leq R(\theta^*)+\frac{\epsilon}{2}$ and $\hat{R_n}(\theta) \geq R(\theta)-\frac{\epsilon}{2}$ both hold.
Now, $t \in [0,1] \longmapsto \hat{R_n}((1-t)\theta^*+t\hat{\theta_n})$ is convex, minimal at $t=1$, and thus is nonincreasing, and $\hat{R_n}(\theta)$ is some $f(t)$ with $0 \leq t \leq 1$, which implies that $\hat{R_n}(\theta) \leq \hat{R_n}(\theta^*)$.
Therefore, with probability $1-\epsilon$ at least, $R(\theta) \leq \hat{R_n}(\theta) +\frac{\epsilon}{2} \leq \hat{R_n}(\theta^*)+\frac{\epsilon}{2} \leq R(\theta^*)+\epsilon$.
So by part one, for any $\theta \in [\theta^*,\hat{\theta_n}]$ with distance at most $B$ from $\theta^*$, with probability at least $1-\epsilon$, $\|\theta-\theta^*\|^2 \leq \frac{3\epsilon}{\tau^2 \lambda}$. In particular, if we choose the farthest possible $\theta$ from $\theta^*$, (still with probability at least $1-\epsilon$), the inequality $\min(B,\|\hat{\theta_n}-\theta^*\|) \leq \sqrt{\frac{3\epsilon}{\tau^2\lambda}}$ holds. By the definition of $B$, it follows that with probability $1-\epsilon$ at least, $\|\theta^*-\hat{\theta_n}\| \leq \sqrt{\frac{3\epsilon}{\tau^2\lambda}}$, which concludes.
