Suppose $(X,Y), (X_1,Y_1),(X_2,Y_2),\dots$ is a $\mathbb{P}$-i.i.d. sequence of pairs of real-valued random variables such that the support of $\mathbb{P}_{(X,Y)}$ is contained in the square $[-1,1] \times [-1,1]$.

Assume that there exists a noisy linear relation with slope $m \in [-1,1]$ between $X$ and $Y$, i.e., $\mathbb{E}[Y \mid X] = mX$.

Our goal is to give a reliable estimate of $m$ having access to a sample of size $T\in \mathbb{N}$, say $S_T := \big((X_1,Y_1), \dots , (X_T,Y_T)\big)$. Our performances will be measured via the square loss, i.e., if we predict $\hat{m}$, we pay the loss \begin{equation*} \ell(\hat{m}) :=\mathbb{E}\big[(Y-\hat{m}X)^2\big]\;, \end{equation*} which has its minimum at $\hat{m} = m$ (since $\mathbb{E}[Y \mid X] = mX$).

A viable strategy seems to minimize a proxy of $\ell$, for example its empirical version based on the sample $S_T$ we have access to: \begin{equation*} \hat{\ell}_{S_T}(\hat{m}) := \frac{1}{T} \sum_{t=1}^T(Y_t-\hat{m}X_t)^2\;, \end{equation*} whose minimum occurs at \begin{equation*} \hat{m}_{S_T} := \frac{\sum_t^T X_tY_t}{\sum_{t=1}^T X_t^2}\;. \end{equation*}

I'm interested in high-probability exponential guarantees about the performance of the estimator $\hat{m}_{S_T}$ in the spirit of Hoeffding's inequality. Specifically:

Can we guarantee that there exists constants $c,d\ge0$ such that \begin{equation*} \forall \varepsilon >0, \forall T \in \mathbb{N}, \qquad \mathbb{P}\big[|\hat{m}_{S_T} - m| \ge \varepsilon \big] \le c \cdot \exp (- d \cdot \varepsilon ^2 \cdot T) \end{equation*}

If that's true, how do these two constants $c,d$ look like?

If that's not true, which kind of guarantees can we give?


1 Answer 1


I was thinking about something along the following line. Assume that we know a constant $a \in (0,1)$ for which $\mathbb{E}[X^2] \ge a$. We have

\begin{align*} |\hat{m}_{S_T} - m| &\le \Bigg|\frac{\frac{1}{T} \sum_{t=1}^T X_t Y_t}{\frac{1}{T} \sum_{t=1}^T X_t^2} - \frac{\frac{1}{T} \sum_{t=1}^T X_t Y_t}{\mathbb{E}[X^2]} \Bigg| + \Bigg|\frac{\frac{1}{T} \sum_{t=1}^T X_t Y_t}{\mathbb{E}[X^2]} - m \Bigg| \\ &\le \Bigg|\frac{1}{\frac{1}{T} \sum_{t=1}^T X_t^2} - \frac{1}{\mathbb{E}[X^2]} \Bigg| + \Bigg|\frac{\frac{1}{T} \sum_{t=1}^T X_t Y_t}{\mathbb{E}[X^2]} - m \Bigg| \\ &= \Bigg|\frac{\mathbb{E}[X^2]-\frac{1}{T} \sum_{t=1}^T X_t^2}{\mathbb{E}[X^2]\frac{1}{T} \sum_{t=1}^T X_t^2} \Bigg| + \Bigg|\frac{1}{T} \sum_{t=1}^T \frac{X_t Y_t}{\mathbb{E}[X^2]} - m \Bigg| \;. \end{align*}

Now, we know that \begin{equation*} \mathbb{P}\Big[ \frac{1}{T} \sum_{t=1}^T X_t^2 < \mathbb{E}[X^2] - \frac{a}{2}\Big] \le \exp\Big(-\frac{1}{8} a^2 T \Big) \end{equation*} Now, if $\frac{1}{T} \sum_{t=1}^T X_t^2 < \mathbb{E}[X^2] - \frac{a}{2}$ we have that \begin{equation*} \Bigg|\frac{\mathbb{E}[X^2]-\frac{1}{T} \sum_{t=1}^T X_t^2}{\mathbb{E}[X^2]\frac{1}{T} \sum_{t=1}^T X_t^2} \Bigg| \le \frac{2}{a^2} \Big| \mathbb{E}[X^2]-\frac{1}{T} \sum_{t=1}^T X_t^2 \Big| \end{equation*} and so, for any $\varepsilon \in (0,1)$, using a union bound, we get: \begin{align*} \mathbb{P} &\Big[ |\hat{m}_{S_T} - m| \ge \varepsilon \Big] \\ &\le \exp\Big(-\frac{1}{8} a^2 T \Big) + \mathbb{P}\bigg[ \frac{2}{a^2} \Big| \mathbb{E}[X^2]-\frac{1}{T} \sum_{t=1}^T X_t^2 \Big| \ge \frac{\varepsilon}{2} \bigg] + \mathbb{P}\Bigg[\Bigg|\frac{1}{T} \sum_{t=1}^T \frac{X_t Y_t}{\mathbb{E}[X^2]} - m \Bigg| \ge \frac{\varepsilon}{2}\Bigg] \\ &\le \exp\Big(-\frac{1}{8} a^2 T \Big) + 2\exp\Big(-\frac{a^4}{32} \varepsilon^2 T \Big) + 2\exp\Big(-\frac{a^2}{8} \varepsilon^2 T \Big) \\ &\le 5 \cdot \exp\Big(-\frac{a^4}{32} \cdot \varepsilon^2 \cdot T \Big) \;. \end{align*}

However, for this line of thought to work, we need an a priori knowledge of a lower bound $a$ on $\mathbb{E}[X^2]$. Also, the bound depends on $a$ in a dreadful way.

If someone has better ideas, please post other answers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.