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^+$ ?



Your Answer

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