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

  • $\begingroup$ your reference [1] is not showing $\endgroup$
    – kodlu
    Commented Jun 10, 2022 at 18:47
  • $\begingroup$ @kodlu thanks for letting me know i have added it! $\endgroup$ Commented Jun 10, 2022 at 19:19


Your Answer

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