# Can we give high-probability exponential bounds on the slope of the linear regression function?

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?

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.