<p>I am looking for generalisation bounds under the squared loss, specifically for the class <span class="math-container">$\mathcal{F}_{\text{lin}} = \{f(x) = \langle w, x \rangle : \|w\| \leq C\}$</span> of bounded linear predictors. I am aware of standard risk bounds for the risk <span class="math-container">$\mathcal{L}(f)$</span> of a predictor <span class="math-container">$f$</span> using the Rademacher complexity (see Thm 3 of [1]) :
<span class="math-container">$$
\mathcal{L}(f) \leq \hat{\mathcal{L}}(f) + 2L_{\ell}\mathcal{R}_{n}(\mathcal{F}) + c\sqrt{\frac{\log(1/\delta)}{2n}}
$$</span>
where <span class="math-container">$\hat{\mathcal{L}}(f)$</span> is the empirical loss of <span class="math-container">$f$</span>, <span class="math-container">$L_{\ell}$</span> is the Lipschitz constant of the loss function <span class="math-container">$\ell$</span>, <span class="math-container">$n$</span> is the number of data points,  <span class="math-container">$c$</span> is a constant which upper bounds <span class="math-container">$\ell$</span>, and <span class="math-container">$\mathcal{R}_{n}$</span> is the Rademacher complexity.</p>
<p>If <span class="math-container">$\|x\| \leq D$</span> for all <span class="math-container">$x \in \mathcal{X}$</span> (where <span class="math-container">$\mathcal{X}$</span> is the input space) then <span class="math-container">$\max_{f \in \mathcal{F}, x \in \mathcal{X}} \langle w, x\rangle \leq DC$</span>. If we further assume the label space <span class="math-container">$\mathcal{Y}$</span> is a subset of <span class="math-container">$[-DC,DC]$</span> we can then argue that the square loss is  Lipschitz with constant <span class="math-container">$2DC$</span>. Following the bound on the Rademacher complexity of <span class="math-container">$\mathcal{F}_\text{lin}$</span> (again, see Thm 1 of [1]) we have:
<span class="math-container">$$
\mathcal{L}(f) \leq \hat{\mathcal{L}}(f) + 4D^{2}C^{2}\sqrt{\frac{1}{n}} + 4D^{2}C^{2}\sqrt{\frac{\log(1/\delta)}{2n}}
$$</span></p>
<p>Can we do better than this for the squared loss? I have taken a fairly generic approach here with Rademacher complexity. Is there an approach which gives better guarantees for the squared loss, which either improves the constants, or relaxes some of the assumptions made on the boundedness of <span class="math-container">$\mathcal{X}$</span> or <span class="math-container">$\mathcal{F}_{\text{lin}}$</span>?</p>
<p>[1] On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization, Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari, 2008</p>

CC BY-SA 4.0
2022-06-10T18:47:22.170Z
your reference [1] is not showing
kodlu
CC BY-SA 4.0
2022-06-10T19:19:49.620Z
@kodlu thanks for letting me know i have added it!
Nick Bishop
<machine-learning><pac-learning><sample-complexity>
PAC guarantees for linear prediction under the squared loss
Nick Bishop
# PAC guarantees for linear prediction under the squared loss

(Asked by: username_0 on 2022-06-10)

I am looking for generalisation bounds under the squared loss, specifically for the class $\mathcal{F}\_{\text{lin}} = \{f(x) = \langle w, x \rangle : \|w\| \leq C\}$ of bounded linear predictors. I am aware of standard risk bounds for the risk $\mathcal{L}(f)$ of a predictor $f$ using the Rademacher complexity (see Thm 3 of [1]) :
$$
\mathcal{L}(f) \leq \hat{\mathcal{L}}(f) + 2L\_{\ell}\mathcal{R}\_{n}(\mathcal{F}) + c\sqrt{\frac{\log(1/\delta)}{2n}}
$$
where $\hat{\mathcal{L}}(f)$ is the empirical loss of $f$, $L\_{\ell}$ is the Lipschitz constant of the loss function $\ell$, $n$ is the number of data points, $c$ is a constant which upper bounds $\ell$, and $\mathcal{R}\_{n}$ is the Rademacher complexity.

If $\|x\| \leq D$ for all $x \in \mathcal{X}$ (where $\mathcal{X}$ is the input space) then $\max\_{f \in \mathcal{F}, x \in \mathcal{X}} \langle w, x\rangle \leq DC$. If we further assume the label space $\mathcal{Y}$ is a subset of $[-DC,DC]$ we can then argue that the square loss is Lipschitz with constant $2DC$. Following the bound on the Rademacher complexity of $\mathcal{F}\_\text{lin}$ (again, see Thm 1 of [1]) we have:
$$
\mathcal{L}(f) \leq \hat{\mathcal{L}}(f) + 4D^{2}C^{2}\sqrt{\frac{1}{n}} + 4D^{2}C^{2}\sqrt{\frac{\log(1/\delta)}{2n}}
$$

Can we do better than this for the squared loss? I have taken a fairly generic approach here with Rademacher complexity. Is there an approach which gives better guarantees for the squared loss, which either improves the constants, or relaxes some of the assumptions made on the boundedness of $\mathcal{X}$ or $\mathcal{F}\_{\text{lin}}$?

[1] On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization, Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari, 2008

**Tags:** machine-learning, pac-learning, sample-complexity

> **Comments:**
> **username_1**: your reference [1] is not showing  
> **username_0**: @username_1 thanks for letting me know i have added it!  

---

## 0 answers

