I am currently facing the following problem :
Let $(X_1,Z_1),\ldots,(X_n,Z_n)$ be $n$ i.i.d. sample points from some distribution $p$ supported on $\mathcal X\times\{-1,1\}$ where $\mathcal X\subseteq \mathbb R^d$ is some compact subset. From this sample, I can define a function $$g :\lambda\mapsto g(\lambda\ |\ (X_i,Z_i)_{1\le i\le n})=:\theta_\lambda\in\mathbb R^p$$ Defined for any $\lambda >0$. I do not know the explicit relation between $g$ and the $(X_i,Z_i)$ (it is the unique argmin of a function of the sample), but I know that $g$ is Lipschitz-continuous with respect to $\lambda$ (it is even differentiable if that helps).
I would like to bound $\|\theta_\lambda-\theta_{\lambda/2}\| $ in probability. That is, for any positive $\varepsilon>0$, I would like to get $$\mathbb P\left(\|\theta_\lambda-\theta_{\lambda/2}\| >\varepsilon\right)\le G(\varepsilon,n)\tag1 $$ Where $G$ is some deterministic function that goes to zero when $n$ goes to infinity. Here, the choice of norm $\|\cdot\| $ doesn't really matter since all norms in $\mathbb R^p$ are equivalent.
My question : How to prove (or disprove ?) inequality $(1)$ ? Are some additional assumptions on $g$ needed for it to hold ? This a a bit different from usual concentration inequalities so I'm not sure how to proceed here.
Thanks for any help.
Update : I'm not 100% there yet, but I've made some progress. The way of getting an upper bound involving $n$ that occurred to me is by using a martingale difference sequence :
First off, let's define the function $F:\lambda\mapsto\|g(\lambda)-g(\lambda/2)\|$ and the Martingale sequence $Y_k(\lambda) := \mathbb E[F(\lambda)\ |\ X_1,\ldots,X_k] $.
In my setting, $Y_0=0$ and so it follows that $Y_n =\sum_{k=1}^{n} Y_k - Y_{k-1} $. By Azuma-Hoeffding inequality, it follows that
$$\mathbb P\left(Y_n(\lambda)\ge\varepsilon\right) =\mathbb P\left(\|\theta_\lambda-\theta_{\lambda/2}\|\ge\varepsilon\right) \le\exp\left(\frac{-2\varepsilon^2}{2\sum_{k=1}^{n}c_k^2}\right) $$
Where the $c_k$ are such that $|Y_k(\lambda) - Y_{k-1}(\lambda)|\le c_k$.
Now this isn't quite the desired result as the $c_k$ are not necessarily small enough (I want them of order $1/n$), but they can be upper bounded as follows : $$\begin{align}|Y_k-Y_{k-1}|&=\left|\mathbb E[F(\lambda)\ |\ X_1,\ldots,X_k]-\mathbb E[F(\lambda)\ |\ X_1,\ldots,X_{k-1}]\right|\\ &\le\mathbb E[F(\lambda)\ |\ X_1,\ldots,X_k]+\mathbb E[F(\lambda)\ |\ X_1,\ldots,X_{k-1}]\tag1\\ &=\mathbb E[\|g(\lambda)-g(\lambda/2)\|\ |\ X_1,\ldots,X_k]+\mathbb E[\|g(\lambda)-g(\lambda/2)\| |\ X_1,\ldots,X_{k-1}]\\ &\le\mathbb E[L_g\cdot \lambda/2\ |\ X_1,\ldots,X_k]+\mathbb E[L_g\cdot \lambda/2\ |\ X_1,\ldots,X_{k-1}]\tag2\\ &= \lambda/2\cdot\big(\mathbb E[L_g\ |\ X_1,\ldots,X_k]+\mathbb E[L_g\ |\ X_1,\ldots,X_{k-1}]\big)\end{align} $$ Where I used triangle inequality in $(1)$ and Lipschitz continuity of $g$ in $(2)$. Now, for my desired result to hold, it is sufficient that there exists some constant $G$ such that the Lipschitz constant of $g$ is bounded by $G/n$, but I think this is rather harsh...
Can this approach be refined in any way to get the result under less restrictive assumptions ?
I initially though that I could circumvent the problem by introducing a partition $$\lambda/2=:\lambda_0<\lambda_1<\ldots<\lambda_K:=\lambda $$ Such that each $|\lambda_i-\lambda_{i-1}|$ is smaller than $1/n$, which would then allow me to conclude by splitting the probability accordingly, but sadly the subdivision depends on $n$ so it is not helpful...
