# Generalization bound for margin / ramp loss which is not vacuous when margin tends to zero, but recovers usual generalization bound for 0-1 loss

For any $$t \ge 0$$, consider the ramp loss function $$\phi_t:\mathbb R \to [0,1]$$ defined by $$\phi_t(z) = \begin{cases}0,&\mbox{ if }z \ge t,\\ 1-z/t,&\mbox{ if }z \in (0,t),\\ 1,&\mbox{ if }z \le 0. \end{cases}$$

Note that $$\phi_0$$ is just the 0-1 loss used to measure the quality of a binary classification method.

Let $$F$$ be a collection of functions from $$X$$ to $$\mathbb R$$, and consider a collection of functions $$H_t$$ from $$X \times \{\pm 1\}$$ to $$[0,1]$$ given by $$H_t:=\{(x,y) \mapsto \phi_t(yf(x)) \mid f \in F\}$$. Let $$P$$ be a probability distribution on $$X \times \{\pm 1\}$$, and let $$(x_1,y_1),\ldots,(x_n,y_n)$$ be an iid sample of size $$n$$ from this distribution. I'm interested in upper-bounds on the quantity

$$\epsilon_n(H_t) := \sup_{h \in H_t} |R(h) - \hat R_n(h)|,$$ which hold w.h.p. Here, $$\hat R_n(h) := (1/n)\sum_{i=1}^n h(x_i,y_i)$$ is the empirical loss of a function $$h \in H_t$$, and $$R(h) := \mathbb E_{(x,y) \sim P}h(x,y)$$ is its population loss.

Now, since $$\phi_t$$ is $$1/t$$-Lipschitz, one can show that the Rademacher complexity of $$H_t$$ is at most $$(1/t)Rad_n(F)$$, and so

$$\epsilon_n(H_0) \lesssim \frac{1}{t}Rad_n(F) + \sqrt{\frac{\log(1/\delta)}{n}}\text{ w.p }1-\delta.$$

Also refer to the proof of Theorem 4.4 of this book. Furthermore, if $$F$$ has pseudo-VCDim at most $$d$$ (i.e if the VCDim of $$\mbox{sign}\circ F$$ is at most $$d$$), then $$Rad_n(F) \lesssim \sqrt{d/n}$$, and so the above gives

$$\epsilon_n(H_t) \lesssim \frac{1}{t}\sqrt{\frac{d}{n}} + \sqrt{\frac{\log(1/\delta)}{n}}\text{ w.p }1-\delta. \tag{1}$$

My issue with the bound (1) is that it doesn't recover the bound for the 0-1 loss when $$t \to 0^+$$, i.e it doesn't recover

$$\epsilon_n(H_0) \lesssim \sqrt{\frac{d}{n}} + \sqrt{\frac{\log(1/\delta)}{n}}\text{ w.p }1-\delta. \tag{2}$$

Question. Can (1) be modified (say, by replacing $$1/t$$ by something else, e.g $$1/\max(1,t)$$) so that it works for small $$t$$, and in particular, it gives (2) in the limit $$t \to 0^+$$ ?