a consequence of the margin behavior analyzed in Proposition \[thm:margin\] (Section \[s:margin\]).

More precisely, when ${\varepsilon}$ is chosen at least of the order of $\sqrt{d/n} \log(n)$ (in order to kill the exponential term), the estimation error bound above is roughly of the order of $\min\bigl\{{\varepsilon}, {\varepsilon}^2/\Delta_d\bigr\}$. In particular, if $\Delta_d$ is bounded from below, then the estimation error is at most of the order of ${\varepsilon}^2 \approx d \log^2(n)/n$. On the other hand, if no lower bound is available for $\Delta_d$, then the only estimation error bound we get is a slower rate of the order of ${\varepsilon}\approx \sqrt{d/n} \log(n)$.

Convergence rate under a smoothness assumption {#subsection:upper_bound}
----------------------------------------------

We now state the main result of this paper. We upper bound the excess risk $\mathcal{R}_{f,g}({\widehat}\Phi_d) - \mathcal{R}_{f,g}(\Phi^\star)$ of our classifier when $f$ and $g$ belong to subsets of the Sobolev ball ${\mathcal{H}_s}(R)$ defined in . These subsets are parametrized by a separation distance $\Delta$: a larger value of $\Delta$ makes the classification problem easier, as reflected by the non-increasing bound below.

\[prop:minmax\] There exist an absolute constant $c>0$ and a constant $N_{s,R} {\geqslant}86$ depending only on $s$ and $R$ such that the following holds true. For all $s,R > 0$ and 