# A Case of Exponential Convergence Rates for SVM

Vivien Cabannes
ENS / INRIA DI ENS, École Normale Supérieure, Université PSL, CNRS, INRIA,
75005 Paris Stefano Vigogna
University of Rome Tor Vergata

###### Abstract

Classification is often the first problem described in introductory machine
learning classes. Generalization guarantees of classification have
historically been offered by Vapnik-Chervonenkis theory. Yet those guarantees
are based on intractable algorithms, which has led to the theory of surrogate
methods in classification. Guarantees offered by surrogate methods are based
on calibration inequalities, which have been shown to be highly sub-optimal
under some margin conditions, failing short to capture exponential convergence
phenomena. Those “super” fast rates are becoming to be well understood for
smooth surrogates, but the picture remains blurry for non-smooth losses such
as the hinge loss, associated with the renowned support vector machines. In
this paper, we present a simple mechanism to obtain fast convergence rates and
we investigate its usage for SVM. In particular, we show that SVM can exhibit
exponential convergence rates even without assuming the hard Tsybakov margin
condition.

##  1 Introduction

To solve a problem with computer calculations, classical computer science
consists in handcrafting a set of rules. In contrast, machine learning is
based on the collection of a vast amount of solved instances of this problem,
and on the automatic tuning of an algorithm that maps inputs defining the
problem to the desired outputs. Denote by $x$ in a space $\mathcal{X}$ the
inputs, by $y\in\mathcal{Y}$ the outputs, and by $f:\mathcal{X}\to\mathcal{Y}$
the input/output mappings. To learn a mapping $f^{*}$, it is customary to
introduce an explicit metric of error, and search for the function that
minimizes it. Define this metric through a loss
$\ell:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}$ that quantifies how bad a
prediction $f(x)$ is when we observe $y$. If we assume the existence of a
distribution over I/O pairs, $\rho\in\Delta_{\mathcal{X}\to\mathcal{Y}}$, that
generates the instances of the problem we mean to solve, we aim to minimize
the average loss value

${\cal
R}(f)=\operatorname{\mathbb{E}}_{(X,Y)\sim\rho}\left[\ell(f(X),Y)\right].$ (1)

In practice, this “risk” ${\cal R}$ can be evaluated approximately with
samples ${\cal D}_{n}=(X_{i},Y_{i})_{i\leq n}$, collected by the machine
learning scientist and assumed to have been drawn independently accordingly to
$\rho$.

We shall focus on the binary classification problem where
$\mathcal{Y}=\left\\{-1,1\right\\}$, and $\ell$ is the zero-one loss
$\ell(y,z)=\mathbf{1}_{y\neq z}$. In this setting, the risk ${\cal R}(f)$
captures the probability of mistakes of a classifier $f$, and its minimizer is
characterized by

$f^{*}=\operatorname*{arg\,min}_{f:\mathcal{X}\to\mathcal{Y}}{\cal
R}(f)=\operatorname{sign}\eta,\qquad\text{where}\qquad\eta(x)=\operatorname{\mathbb{E}}\left[Y\,\middle|\,X=x\right].$
(2)

Ideally, leveraging the dataset ${\cal D}_{n}$, we would like to find a
mapping $f_{{\cal D}_{n}}:\mathcal{X}\to\mathcal{Y}$ that is close to be
optimal, in the sense that the excess of risk ${\cal E}(f_{{\cal
D}_{n}})={\cal R}(f_{{\cal D}_{n}})-{\cal R}(f^{*})$ is as small as it could
be. Since this quantity is actually random, inheriting from the randomness of
the samples, we will focus on controlling its average. We give a brief
historical review of related literature before precising our contributions.

###  1.1 Statistical learning theory

The classical approach to minimize (1) without the knowledge of $\rho$ but
with the sole access to samples ${\cal D}_{n}\sim\rho^{\otimes n}$ is to
restrict the search over functions in a class ${\cal
F}\subset\mathcal{Y}^{\mathcal{X}}$, and look for an empirical risk minimizer

$f^{*}_{{\cal D}_{n}}\in\operatorname*{arg\,min}_{f\in{\cal F}}{\cal R}_{{\cal
D}_{n}},\qquad\text{where}\qquad{\cal R}_{{\cal
D}_{n}}(f)=\frac{1}{n}\sum_{i=1}^{n}\ell(f(X_{i}),Y_{i}).$ (3)

If we denote by $f^{*}_{\cal F}$ the minimizer of ${\cal R}$ in ${\cal F}$,
using the fact that ${\cal R}_{{\cal D}_{n}}(f^{*}_{\cal F})\geq{\cal
R}_{{\cal D}_{n}}(f^{*}_{{\cal D}_{n}})$, the excess of risk can be bounded as

${\cal R}(f_{{\cal D}_{n}}^{*})-{\cal
R}(f^{*})\leq\underbrace{2\sup_{f\in{\cal F}}\left|{\cal R}(f)-{\cal R}_{{\cal
D}_{n}}(f)\right|}_{\text{estimation error}}+\underbrace{{\cal R}(f^{*}_{\cal
F})-{\cal R}(f^{*})}_{\text{approximation error}}.$ (4)

This bound can be seen as highly sub-optimal because it bounds the deviation
of a random function with the worst deviation in the function class. However,
for any class ${\cal F}$, there exists an “adversarial” distribution $\rho$
for which convergence rates (of the excess of risk towards zero as a function
of the number of samples $n\in\mathbb{N}$) derived through this bound can not
be improved beside lowering some multiplicative constants [Vapnik, 1995]. On
the one hand, the estimation error can be controlled with general tools to
bound the supremum of a random process [_e.g._ , Dudley, 1967], and will
decrease with a decrease in the size of the class ${\cal F}$. On the other
hand, the approximation error depends on assumptions of the problem, and the
bigger the size of the class ${\cal F}$, the less restrictive it will be to
assume that $f^{*}$ is not too different from $f_{\cal F}^{*}$. Hence, there
is a clear trade-off between controlling both errors, which should be balanced
in order to optimize a bound on the full excess of risk.

###  1.2 Surrogate methods

In practice, due to the combinatorial nature of discrete-valued functions,
finding the empirical risk minimizer (3) is often an intractable problem
[_e.g._ , Höffgen and Simon, 1992, Arora et al., 1997]. Therefore, people have
approach the original problem with other perspectives. A straightforward
approach is given by _plug-in classifiers_ , _i.e._ , classifiers of the form
$\operatorname{sign}\hat{\eta}$, for $\hat{\eta}$ some estimator of $\eta$.
For example, such an estimator can be constructed as
$\hat{\eta}(x)=\sum_{i=1}^{n}\alpha_{i}(x)Y_{i},$ for $\alpha_{i}(x)$ some
weights that specify how much the observation $Y_{i}$ made at the point
$X_{i}$ should diffuse to the point $x$ [see Friedman, 1994, for an example].
Another popular approach to solve classification problems is provided by
_support vector machines_ (SVM), which were introduced from geometric
considerations to maximize the margin between the classes
$\left\\{x\in\mathcal{X}\,\middle|\,f^{*}(x)=y\right\\}$ for
$y\in\left\\{-1,1\right\\}$ [Cortes and Vapnik, 1995].

These two approaches can be conjointly understood as introducing a surrogate
loss $L:\mathbb{R}\times\mathcal{Y}\to\mathbb{R}$ and looking for a
continuous-valued function $g:\mathcal{X}\to\mathbb{R}$ that solves the
surrogate problem

$f=\operatorname{sign}g,\qquad
g^{*}\in\operatorname*{arg\,min}_{g:\mathcal{X}\to\mathbb{R}}{\cal
R}_{S}(g),\qquad\text{where}\qquad{\cal
R}_{S}(g)=\operatorname{\mathbb{E}}_{(X,Y)\sim\rho}\left[L(g(X),Y)\right],$
(5)

where the notation $S$ stands for “surrogate”. To an estimate
$g:\mathcal{X}\to\mathbb{R}$ of $g^{*}$ we associate an estimate
$f:\mathcal{X}\to\mathcal{Y}$ of $f^{*}$ through the decoding step
$f=\operatorname{sign}g$. In particular, using the variational
characterization of the mean, $\eta$ can be estimated through
$L(z,y)=\left|z-y\right|^{2}$. Regarding SVM, they are related to the _hinge
loss_ [see, _e.g._ , Steinwart and Christmann, 2008]

$L(z,y)=\max\left(0,1-zy\right),$ (6)

Surrogate methods benefits from their relative easiness to optimize and the
quality of their practical results. Arguably, they define the current state of
the art in classification, softmax regression being particularly popular to
train neural networks on classification tasks.

Surrogate methods were studied in depth by Bartlett et al. [2006], who
proposed a generic framework to relate the excess of the original risk to the
excess of surrogate risk through an inequality of the type

${\cal R}(f)-{\cal R}(f^{*})\leq\psi\left({\cal R}_{S}(g)-{\cal
R}_{S}(g^{*})\right),$ (7)

where $f=\operatorname{sign}g$ and $\psi$ is a concave function, uniquely
defined from $L$ and verifying $\psi(0)=0$. The use of a concave function is
motivated by Jensen inequality, allowing to integrate an inequality derived
pointwise (conditionally on an input $x$).

###  1.3 Exponential convergence rates

On the one hand, calibration inequalities (7) are appealing, as they allow to
directly cast rates derived on the surrogate problem to rates on the original
problem. On the other hand, because $\psi$ has to be concave, rates in
$O(n^{-r})$ on the surrogate problem can not be cast as better rates on the
original problem, corresponding to the optimal inequalities where $\psi(x)=cx$
for some $c>0$, Yet, one can find cases where the sign of $\eta$ can be
estimated much faster than $\eta$ itself, even when this sign is estimated
with surrogate methods. In particular, Mammen and Tsybakov [1999] [see also
Massart and Nédélec, 2006] introduced the following condition.

######  Assumption 1 (Hard margin condition).

The binary classification problem defined through the distribution $\rho$ is
said to verify the (Tsybakov) hard margin condition if the conditional mean
$\eta$ is bounded away from zero, i.e.,

$\exists\,\eta_{0}>0;\,x\in\mathcal{X},\qquad\left|\eta(X)\right|>\eta_{0}\qquad\textit{a.s.},$
(8)

where the notation a.s. stands for almost surely. Equivalently,
$\left|\eta\right|^{-1}\in L^{\infty}(\rho_{\mathcal{X}})$.

Indeed, under Assumption 1, leveraging sign equality, we get

$\operatorname{\mathbb{E}}_{{\cal D}_{n}}[{\cal R}(\operatorname{sign}g_{{\cal
D}_{n}})]-{\cal R}(f^{*})\leq\operatorname{\mathbb{P}}_{{\cal
D}_{n}}\left(\left\|g_{{\cal
D}_{n}}-\eta\right\|_{L^{\infty}}>\eta_{0}\right).$

As a consequence, an exponential concentration inequality on the $L^{\infty}$
distance between $g_{{\cal D}_{n}}$ and $\eta$ directly translates to
exponential convergence rates on the average excess of risk. In particular,
estimation methods for $\eta$ based on Hölder classes of functions, such as
local polynomials, are known to be well-behaved with respect to the
$L^{\infty}$ norm [see, _e.g._ , the construction of covering number by
Kolmogorov and Tikhomirov, 1959]. This was leveraged by Audibert and Tsybakov
[2007] in a seminal paper that shows how better rates can be achieved on the
classification problem under Assumption 1 and a variety of weaker conditions
(described later in Assumption 2).

Surprisingly, such an approach has remained somehow less popular than
approaches based on calibration inequalities, and we are missing a framework
to fully apprehend fast rates phenomena. Some results were achieved by
Koltchinskii and Beznosova [2005]. Recently, Cabannes et al. [2021b] showed
that this result generalizes to any discrete output learning problem, and that
approaches that naturally lead to concentration in $L^{2}$ could be turned
into fast rates based on interpolation inequalities that relate the $L^{2}$
norm with the $L^{\infty}$ one (notably reusing the work of Fischer and
Steinwart [2020] on interpolation spaces). Exploiting the work of Marteau-
Ferey et al. [2019], this can be generalized to any self-concordant loss
(using self-concordance to reduce the problem to a least-squares problem);
and, through the work of Lin et al. [2020], to any spectral filtering
technique (beyond Tikhonov regularization), such as stochastic gradient
descent, which was actually shown earlier for binary classification by
Pillaud-Vivien et al. [2018] and Nitanda and Suzuki [2019]. In the same stream
of research, Vigogna et al. [2022] proposed a general framework to study
exponential rates for smooth losses in multiclass classification beyond least-
squares.

###  1.4 Contribution

The proofs of exponential convergence in the works quoted above are all based
on the basic mechanism outlined in Audibert and Tsybakov [2007].
Unfortunately, such a mechanism does not easily extend to the hinge loss. Does
this mean that support vector machines do not exhibit super fast rates, and
thus they are inferior to other surrogate methods? The practice seems to
answer negatively. In this paper, we give a firm theoretical answer to this
question. In particular, we show not only that support vector machines do
achieve exponential rates, but also that they can do so even without assuming
the hard margin condition. Our main contribution is to introduce an general
framework to prove exponential convergence rates, and show how this framework
can be applied to the hinge loss while only considering classical assumptions.

#### Outline.

Our general strategy is illustrated on Figure 1 and consists in first finding
a relation

${\cal R}_{S}(g_{\theta})-{\cal
R}_{S}(g_{\theta^{*}})\geq\left\|\theta-\theta^{*}\right\|,$

for some natural parameter $\theta$ in a Banach space $\Theta$ parameterizing
a class of functions $g_{\theta}\in{\cal F}$, and then show that
$\operatorname{sign}g_{\theta}=\operatorname{sign}g_{\theta^{*}}$ when
$\left\|\theta-\theta^{*}\right\|$ is small enough, that is,

$\exists\,\varepsilon>0;\qquad\left\|\theta-\theta^{*}\right\|\leq\varepsilon\quad\Rightarrow\quad\operatorname{sign}g_{\theta}=\operatorname{sign}g_{\theta^{*}}.$

Assuming that $\operatorname{sign}g_{\theta^{*}}=f^{*}$, we deduce that

$\operatorname{\mathbb{E}}_{{\cal D}_{n}}[{\cal
R}(\operatorname{sign}g_{\theta_{n}})]-{\cal
R}(f^{*})\leq\operatorname{\mathbb{P}}_{{\cal D}_{n}}\left({\cal
R}_{S}(g_{\theta_{n}})-{\cal R}_{S}(g_{\theta^{*}})\geq\varepsilon\right),$

where $g_{\theta_{n}}$ is an estimate of $g_{\theta}$ based on the samples
${\cal D}_{n}$. Finally, we conclude with an exponential concentration
inequality that controls the deviation of the excess of risk based on
classical statistical learning theory.

$\theta^{*}$$\theta_{\lambda}$level lines of ${\cal
R}(\operatorname{sign}g_{\theta_{n}})$path
$\left\\{\theta_{\lambda};\lambda>0\right\\}$region
$\left\\{\theta;\|\theta-\theta_{\lambda}\|<1\right\\}$certified value of
${\cal R}(g_{\theta_{n}})$ when $\|\theta_{n}-\theta_{\lambda}\|<1$ Figure 1:
Our convergence analysis consists in relating natural concentration given by
surrogate methods to the original excess of risk without passing by the
surrogate excess of risk. As the drawing shows, concentration in parameter
space $\Theta$ can be cast as deviation on the original excess of risk. Yet,
such a casting relation depends on the geometry of this picture, which itself
depends on what surrogate is used, what is the function to learn, how a
regularized estimator approached it, and how our empirical estimate
concentrates around the regularized estimator. Note that this figure
illustrates an abstract mechanism that generalizes the simpler mechanism we
use to derive exponential convergence rates.

##  2 Exponential convergence of SVM

This section is devoted to the proof of exponential convergence rates for the
hinge loss. We shall fix the notation ${\cal R}_{S}$ as the surrogate risk
associated with (6). All the proofs are collected in Appendix A.

###  2.1 Refined calibration for the hinge loss

We start by introducing the classical weak margin condition [Mammen and
Tsybakov, 1999].

######  Assumption 2 (Weak margin condition).

The binary classification problem defined through the distribution $\rho$ is
said to verify the (Tsybakov) $p$-margin condition, with $p\in(0,\infty)$, if
there exists a constant $c>0$ such that

$\operatorname{\mathbb{P}}_{\rho_{\mathcal{X}}}(0<\left|\eta(X)\right|<t)\leq
ct^{p},$ (9)

where the notation $\rho_{\mathcal{X}}$ denotes the marginal of $\rho$ over
$\mathcal{X}$.

Assumption 2 is equivalent to asking for the inverse of the conditional mean
$\left|\eta\right|^{-1}$ (with the convention $0^{-1}=0$) to belong to the
Lorentz space $L^{p,\infty}(\rho_{\mathcal{X}})$ (also known as weak-$L^{p}$
space), which is the Banach space endow with the norm (quasi-norm and quasi-
Banach if $p<1$)

$\left\|f\right\|_{p,\infty}=\sup_{t>0}t\operatorname{\mathbb{P}}_{\rho_{\mathcal{X}}}(f(X)>t)^{\frac{1}{p}},$
(10)

where the $\rho_{\mathcal{X}}$ denotes the marginal of $\rho$ with respect to
$\mathcal{X}$. This definition can be extended to the case $p=\infty$ by
setting $L^{p,\infty}(\rho_{\mathcal{X}})=L^{\infty}(\rho_{\mathcal{X}})$,
which characterizes the hard margin condition in Assumption 1. We will also
use $\left\|\cdot\right\|_{p}$, for $p\in[1,\infty]$, to denote the
$L^{p}$-norm on $\mathcal{X}$ endowed with $\rho_{\mathcal{X}}$.

We now relate the excess of risk on the hinge loss to the deviation in these
spaces.

######  Lemma 1 (Weak-$L^{q}$ concentration due to the hinge loss).

For any functions $g_{1},g_{2}:\mathcal{X}\to[-1,1]$,

${\cal R}_{S}(g_{2})-{\cal
R}_{S}(g_{1})=\operatorname{\mathbb{E}}_{\rho_{\mathcal{X}}}[-\eta(X)(g_{2}(X)-g_{1}(X))].$
(11)

In particular, under Assumption 1, for any $g:\mathcal{X}\to\mathbb{R}$,

${\cal R}_{S}(g)-{\cal
R}_{S}(g^{*})\geq\left\|\left|\eta\right|^{-1}\right\|_{\infty}^{-1}\left\|\pi(g)-g^{*}\right\|_{1}.$
(12)

where $g^{*}=\operatorname{sign}\eta$ is a minimizer of ${\cal R}_{S}$ and
$\pi$ is the projection of $\mathbb{R}$ on $[-1,1]$, defined as mapping
$t\in\mathbb{R}$ to $\pi(t)=\operatorname{sign}(t)\max\\{|t|,1\\}$. Similarly,
under Assumption 2, with $q=\nicefrac{{p}}{{p+1}}$,

${\cal R}_{S}(g)-{\cal R}_{S}(g^{*})\geq
2^{-1}\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}^{-1}\left\|\pi(g)-g^{*}\right\|_{q,\infty}.$
(13)

Lemma 1 shows that we can set the minimizer
$g^{*}=f^{*}\in\left\\{-1,1\right\\}^{\mathcal{X}}$. This is a useful fact as
it implies that the excess of the original risk is zero as soon as
$\left\|g-g^{*}\right\|_{\infty}<1$. In essence, the only piece missing to
prove fast convergence rates is an interpolation inequality between
$L^{q,\infty}$ and $L^{\infty}$. In the following, we will leverage Lemma 1
more subtly by considering a class of functions ${\cal G}$ and assumptions on
the distribution $\rho_{\mathcal{X}}$ such that, if an estimate $g\in{\cal G}$
has not the same sign almost everywhere as the estimand $g^{*}$, then
$\left\|g-g^{*}\right\|_{q,\infty}$ is bounded away from zero. By
contraposition, if $g\in{\cal G}$ presents a small excess of surrogate risk,
then $\operatorname{sign}g=\operatorname{sign}g^{*}$. When $\mathcal{X}$ is a
metric space, one way to proceed is to assume that $g$ is Lipschitz-
continuous, together with some minimal mass assumptions. Let us begin with the
minimal mass assumption. We first need the following definition.

######  Definition 1 (Well-behaved sets).

A set $U\subset\mathcal{X}$ is said to be well-behaved with respect to $\rho$
if there exist constants $c,r,d>0$ such that, for any $x\in U$,

$\forall\,\varepsilon\in[0,r];\qquad\rho_{\mathcal{X}}(U\cap{\cal
B}(x,\varepsilon))\geq c\varepsilon^{d}.$ (14)

and ${\cal B}(x,\varepsilon)$ the ball in $\mathcal{X}$ of center $x$ and
radius $\varepsilon$.

The following examples show that the coefficient $d$ that appears in (14)
results from the dimension of the ambient space, the regularity of
singularities of the border of the set, and the decay of the density when
approaching the frontier of the set.

######  Example 1.

The set $[0,1]^{p}$ is well-behaved with coefficients $r=1$, $d=p$ and
$c=2^{-d}\operatorname{vol}(\mathbb{S}^{d-1})$ with respect to the Lebesgue
measure in $\mathbb{R}^{d}$.

######  Example 2.

The set
$\left\\{(x,y)\in\mathbb{R}^{2}\,\middle|\,x\in[0,1],y\in[0,x^{n-1}]\right\\}$
is well-behaved with coefficient $r=1$, $d=n$ and $c=n^{-1}$ with respect to
the Lebesgue measure. Reciprocally, the set $[0,1]$ is well-behaved with
coefficient $r=1$, $d=n$ and $c=n^{-1}$ with respect to the measure whose
density equals $p(x)=x^{n-1}$.

######  Assumption 3 (Minimal mass assumption).

The decision regions
$\mathcal{X}_{y}=\left\\{x\in\operatorname*{supp}(\rho_{\mathcal{X}})\,\middle|\,f^{*}(x)=y\right\\}$
for $y\in\left\\{-1,1\right\\}$ are well-behaved.

Assumption 3 is a weakening of an assumption that is commonly found in the
statistical learning literature. More precisely, it is often assumed that
$\rho$ is absolutely continuous according to the Lebesgue measure $\lambda$ on
$\mathcal{X}$ (assumed to be a Euclidean space), that its density is bounded
away from zero on its support, and that its support has smooth boundary, so
that $\lambda(\operatorname*{supp}\rho_{\mathcal{X}}\cap{\cal
B}(x,\varepsilon))>c^{\prime}\lambda({\cal B}(x,\varepsilon))$ [see the strong
density assumption in Audibert and Tsybakov, 2007].

The minimal mass requirement allows to relate misclassification event to
$L^{q,\infty}$ deviation.

######  Lemma 2.

Under Assumption 3, there exists a constants $c_{0}$ such that if $g$ is
$G$-Lipschitz-continuous for $G>r^{-1}$, for any $q\in(0,1]$

$\exists\,x\in\operatorname*{supp}\rho_{\mathcal{X}};\left|g(x)-g^{*}(x)\right|\geq
1\quad\Rightarrow\quad\left\|g-g^{*}\right\|_{q,\infty}\geq
c_{0}G^{-\frac{d}{q}}.$ (15)

Putting together Lemmas 1 and 2, we obtain the following refined calibration.

######  Proposition 1.

Under Assumptions 2 and 3, if $g$ is $G$-Lipschitz-continuous with $G>r^{-1}$,
we have

${\cal R}_{S}(g)-{\cal R}_{S}(g^{*})\leq
2^{-1}\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}^{-1}c_{0}G^{-\frac{d(p+1)}{p}}\qquad\Rightarrow\qquad{\cal
R}(\operatorname{sign}g)={\cal R}(f^{*}).$ (16)

###  2.2 Trade-off between estimation and approximation errors

We are now left with the research of $g_{{\cal D}_{n}}$ inside a class of
Lipschitz-continuous functions such that ${\cal R}_{S}(g_{{\cal D}_{n}})-{\cal
R}_{S}(g^{*})$ is sub-Gaussian (its randomness being inherited from the
dataset ${\cal D}_{n}$ from which $g_{{\cal D}_{n}}$ is built). To do so, let
us consider a linear class of functions

${\cal
G}_{M,\sigma}=\left\\{x\mapsto\left\langle\theta,\varphi(\sigma^{-1}x)\right\rangle\,\middle|\,\theta\in{\cal
H},\left\|\theta\right\|_{\cal H}\leq M\right\\},$ (17)

where ${\cal H}$ is a separable Hilbert space, $\varphi:\mathcal{X}\to{\cal
H}$ is a $G_{\varphi}$-Lipschitz-continuous mapping, and $\sigma>0$ is a
scaling (or bandwidth) parameter. Such a class of functions can be entirely
described from the kernel
$k(x,x^{\prime})=\left\langle\varphi(x),\varphi(x^{\prime})\right\rangle$ [see
Scholkopf and Smola, 2001, for a primer on kernel methods]. An example for
${\cal G}$ is given by the Gaussian kernel, a.k.a. radial basis function,
$k(x,x^{\prime})=\exp(-\left\|x-x^{\prime}\right\|^{2})$. Using Cauchy-
Schwarz, it is easy to show that any function in ${\cal G}_{M,\sigma}$ is
$MG_{\varphi}\sigma^{-1}$-Lipschitz-continuous.

In order to find a function $g_{{\cal D}_{n}}$ that is likely to minimize
${\cal R}_{S}$ without accessing the distribution $\rho$, but only i.i.d.
samples ${\cal D}_{n}=(X_{i},Y_{i})_{i\leq n}\sim\rho^{\otimes n}$, it is
classical to consider the empirical risk minimizer

$g_{{\cal D}_{n}}\in\operatorname*{arg\,min}_{g\in{\cal
G}_{M,\sigma}}\frac{1}{n}\sum_{i=1}^{n}L(g(X_{i}),Y_{i}).$ (18)

This problem is convex with respect to $\theta$ parameterizing $g\in{\cal
G}_{M,\sigma}$, and is easily optimized with duality. We refer the curious
reader to the extensive literature on SVM [see Cristianini and Shawe-Taylor,
2000, Scholkopf and Smola, 2001, Steinwart and Christmann, 2008, for books on
the matter].

In order to show that ${\cal R}_{S}(g_{{\cal D}_{n}})$ is close to ${\cal
R}_{S}(g^{*})$, one can apply classical results from statistical learning
theory, and in particular (4). The estimation error can be bounded using the
extensive literature on Rademacher complexity for linear classes of functions
on Lipschitz-continuous losses [Bartlett and Mendelson, 2002]. To bound the
approximation error, one needs to make additional assumptions on the problem.
We refer to Steinwart and Scovel [2007], Blaschzyk and Steinwart [2018] for
advanced considerations on the matter. In view of our calibration result (16),
the following additional assumption suffices to prove exponential convergence
of SVM.

######  Assumption 4 (Source condition).

The classification problem verifies the $p$-margin condition 2, and there
exist $M,\sigma$ and a function $g\in{\cal G}_{M,\sigma}$ such that ${\cal
R}_{S}(g)-{\cal R}_{S}(g^{*})\leq
4^{-1}\|\left|\eta\right|^{-1}\|_{p,\infty}^{-1}c_{0}M^{-r}G_{\varphi}^{-r}\sigma^{r}$
with $r=d(p+1)/p$.

It should be noted that Assumption 4, together with Assumption 3, implies that
the decision frontier
$\overline{\mathcal{X}_{-1}}\cap\overline{\mathcal{X}_{1}}$ (the bar notation
corresponding to space closure), inherits from the regularity of $g$, since it
is included in the set $\left\\{x\in\mathcal{X}\,\middle|\,g(x)=0\right\\}$.
In particular, if ${\cal G}_{M,\sigma}$ is included in ${\cal C}^{m}$, this
frontier would be in ${\cal C}^{m}$. Hence, for Assumptions 4 and 3 to hold,
the boundary frontier should match the regularity implicitly defined by ${\cal
G}_{M,\sigma}$.

We are finally ready to state our main result, establishing exponential
convergence rates for SVM.

######  Theorem 1 (Exponential convergence rates for SVM).

Under Assumptions 2, 3 and 4, there exists a constant $c>0$ such that the
empirical minimizer $g_{{\cal D}_{n}}$ defined by (18) verifies

$\operatorname{\mathbb{E}}_{{\cal D}_{n}}{\cal R}(\operatorname{sign}g_{{\cal
D}_{n}})-{\cal R}(f^{*})\leq\exp(-cn).$ (19)

Figure 2:  SVM generalization error as a function of the number of samples
(left) for a problem where $X$ is uniform on $[-1,.-1]\cup[.1,1]$ and
$\eta(x)=\operatorname{sign}(x)\left|x\right|^{p}$ (right). We observe
exponential convergence rates.

###  2.3 Relaxing assumptions

Exponential convergence rates rely on strong assumptions in order to set the
approximation error to zero. To deepen the study of this error, one could
leverage the following geometrical characterization of the risk of
misclassification. For $f:\mathcal{X}\to\left\\{-1,1\right\\}$, we have

${\cal R}(f)-{\cal
R}(f^{*})=\operatorname{\mathbb{E}}[\left|\eta(X)\right|\mathbf{1}_{f(x)\neq
f^{*}(X)}]\leq\operatorname{\mathbb{P}}(f(X)\neq
f^{*}(X))=\rho_{\mathcal{X}}\left(f^{-1}(\\{1\\})\,\triangle\,\mathcal{X}_{1}\right),$
(20)

where $\triangle$ denotes the symmetric difference of sets, i.e. $A\triangle
B=(A\cup B)\setminus(A\cap B)$. In particular, if the function class ${\cal
G}_{M,\sigma}$ is rich enough, and the classes $\mathcal{X}_{1}$ and
$\mathcal{X}_{-1}$ are separated, in the sense that the distance between any
two points in each set is bounded away from zero,111This property is sometimes
referred to as the _cluster assumption_ [Rigollet, 2007] under which even
weakly supervised learning techniques may exhibit exponential convergence
rates [_e.g._ Cabannes et al., 2021a]. then Assumption 4 holds, and the
minimizer $g_{{\cal G}_{M,\sigma}}$ of the surrogate risk in ${\cal
G}_{M,\sigma}$ verifies

$\rho_{\mathcal{X}}\left((\operatorname{sign}g_{{\cal
G}_{M,\sigma}})^{-1}(\\{1\\})\,\triangle\,\mathcal{X}_{1}\right)\leq\psi(M,\sigma),$
(21)

for $\psi$ a function that vanishes for sufficiently large $M$ and small
$\sigma$.

On the one hand, one could control the approximation error by assuming or
deriving inequalities akin (20) and (21), with different profiles of $\psi$.
We conjecture that this can be done by assuming margin conditions that are
well adapted to the geometric nature of SVM, such as the one proposed by
Steinwart and Scovel [2007] [see also Gentile and Warmuth, 1999, Cristianini
and Shawe-Taylor, 2000]. On the other hand, the estimation error can be
controlled by extending the ideas presented in this paper to study the worst
value of the estimation error ${\cal R}(\operatorname{sign}g_{{\cal
D}_{n}})-{\cal R}(\operatorname{sign}g_{{\cal G}_{M,\sigma}})$ under the
knowledge of ${\cal R}_{S}(g_{{\cal D}_{n}})-{\cal R}_{S}(g_{{\cal
G}_{M,\sigma}})$. Fitting $M$ and $\sigma$ to trade estimation and
approximation error, such derivations would open the way to fast polynomial
rates under less restrictive assumptions.

##  3 Numerical analysis

In this section, we provide experiments to illustrate and validate our
theoretical findings. In order to be inline with the current practice of
machine learning, instead of considering the hard constraint
$\left\|\theta\right\|\leq M$ when minimizing a risk functional, we add a
penalty $\lambda\left\|\theta\right\|^{2}$ to the risk to be minimized. Going
from a constrained to a penalized framework does not change the nature of the
statistical analysis, and one might loosely think of $\lambda$ as $1/M$ [see,
for example, Bach, 2023]. All experiments are made with the Gaussian kernel.
Precise details of the different settings are provided in Appendix B.

First, we observe that the regime described in this paper kicks in when the
error is already pretty small. On many real-world problems, we do not expect
the generalization error as a function of the number of data used for training
to exhibit a clear exponential behavior until an unusually big number of
samples is used. This fact is illustrated on Figure 2, where for hard
problems, the exponential behaviors still does not kick in after a thousand of
samples.

Second, this paper shows that, in order to get exponential convergence rates
for SVM, one needs the minimizer $g_{M,\sigma}$ of the surrogate risk over the
selected class of functions to be a perfect classifier, i.e. its sign equals
the sign of $g^{*}$. While this is not constraining under the cluster
assumption, we inspect divergences from this condition on Figure 3. We observe
that, even if $g^{*}$ does not depend on the noise, $g_{M,\sigma}$ does. We
also observe that the regularity of the decision boundary
$\left\\{x\in\mathcal{X}\,\middle|\,\eta(x)=0\right\\}$ should match the
regularity defined implicitly by the kernel $k$ and the scale parameter
$\sigma$.

Figure 3:  Study of the level lines of $g_{\lambda,\sigma}$ when
$\eta^{-1}(0)\in{\cal C}^{\infty}$ (top) and $\eta^{-1}(0)\in{\cal
C}^{0}\setminus{\cal C}^{1}$ (bottom). The function $g^{*}$ takes values $-1$
below the optimal decision frontier plotted in red and $+1$ above,
independently of the noise. We observe that the bias error ${\cal
R}(\operatorname{sign}g_{\lambda,\sigma})-{\cal R}(f^{*})$, which is bounded
by the volume between the level lines
$\left\\{x\in\mathcal{X}\,\middle|\,g_{\lambda,\sigma}(x)=0\right\\}$ and
$\left\\{x\in\mathcal{X}\,\middle|\,\eta(x)=0\right\\}$ (plotted in red),
depends on both the regularity of the latter, and on the noise level. Here,
$\sigma$ is taken to be of the order of 15% of the diameter of the domain,
which explains the regularity of the observed level lines. The noiseless cases
on the right correspond to the situations where
$\operatorname{\mathbb{E}}[Y|X]=\operatorname{sign}\eta(X)$ for $\eta$ plotted
on the left.

Experimental comparisons of different classification approaches have been done
by many people, and our goal is not to showcase the superiority of the SVM
over least-squares, which might be considered as general wisdom that led to
the golden age of SVM in the pre-deep-learning area [see Joachims, 1998, for
example]. In comparison with previous works based on calibration inequalities
[Rosasco et al., 2004, Steinwart, 2007], our analysis proves the robustness of
SVM to noise far away from the decision boundary, in the sense that one does
not need $\eta$ to be bounded away from zero. This is a distinctive aspect of
SVM compared to smooth surrogate methods [Nowak-Vila et al., 2020], such as
softmax regression, that implicitly estimate conditional probabilities and
whose performance depends on the regularity of $\eta$. We illustrate this fact
graphically on Figure 4.

Figure 4:  Comparison of the regularized risk (i.e. ${\cal
R}_{S}(g_{\theta})+\lambda\left\|\theta\right\|^{2}$) minimizer for the hinge
loss surrogate (middle) and the least-squares surrogate (right), when $\eta$
is not regular (left). In this setting, the hinge loss is minimized for
$g=\operatorname{sign}(\eta)$, which can be chosen regular, while the least-
squares loss is minimized for $g=\eta$, which can not be chosen regular. The
reconstruction is made with $\sigma$ about 3% of the domain diameter, and
$\lambda$ relatively small. We assume no density in the middle of the domain,
explaining the absence of definition of $\eta$ and the dashed lines of the
right figures. The oscillation on the later figures are related to the Gibbs
phenomenon [Wilbraham, 1848]. This phenomenon prevents the regularized least-
squares solution from being a perfect classifier.

##  4 Limitations

#### Are surrogate methods only proxy for classification?

From a theoretical perspective, if we are only interested in the optimal
mapping $f:\mathcal{X}\to\mathcal{Y}$, learning surrogate quantities can be
seen as a waste of resources. In essence, this waste of resources is similar
to the one occurring when we learn the full probability function
$(p(y))_{y\in\mathcal{Y}}$ for some probability distribution $p$ on
$\mathcal{Y}$, while we only care about its mode. Yet, in practice, what we
call a “surrogate” problem might actually be a problem of prime interest when
we do not only want to predict $f^{*}(x)$, but we would also like to know how
much we can confidently discard other potential outputs for an input $x$.
Furthermore, assuming that a problem is exactly defined through an “original”
loss that defines a clear and unique measure of error can be questioned when
some practitioners evaluate methods with several metrics of performance
[_e.g._ Chowdhery et al., 2022].

#### Do PAC-bounds provide confidence levels?

Since the parameters in Assumptions 2 and 3 are hard to estimate in practice,
it would be difficult to directly plug our bounds into a practical problem to
derive confidence levels on how much error one might expect when deploying a
model in production. Less ambitiously, we see theorems akin Theorem 1 as
providing theoretical indications that a learning method or a set of
hyperparameters is sound. This is a generic downfall of probably approximately
correct (PAC) generalization bounds [Valiant, 2013], which might explain why
practitioners often prefer to derive error indications from test samples [see,
_e.g._ , Géron, 2017]. Along this line, research on conformal prediction
provides interesting considerations to obtain useful confidence information
from test samples [Vovk and Shafer, 2008]. Finally, all these statistical
methods to get confidence intervals assume representative (if not i.i.d.)
data, an assumption sometimes hard to meet in practice, which is a problem
that has found echoes in the civil society [_e.g._ Benjamin, 2019].

##  5 Conclusion

In this work, we were keen to illustrate a simple mechanism to get exponential
convergence rates for a loss that is quite popular and whose understanding can
not be easily reduced to existing work. In particular, we show that the hard
margin condition is not crucial in order to derive exponential convergence
rates for the SVM.

This provide a crucial step to better understand convergence rates on
classification problems. An extension to generic discrete output problems
could be made by considering polyhedral losses, and deriving variants of Lemma
1 [see Frongillo and Waggoner, 2021, for calibration inequalities for such
losses]. A important follow-up would be to provide a more global picture of
fast polynomial rates for SVM under relaxations of Assumptions 3 and 4.

Finally, Chizat and Bach [2020] have made a link between two-layer wide neural
networks in the interpolation regime (which implies Assumption 1 with
$\eta_{0}=1$) and max-margin classifiers over specific linear classes of
functions. As a consequence, we could directly plug in our analysis to prove
exponential convergence rates for those small neural networks in this
noiseless setting. Studying rates, constants and hyperparameter tuning in this
setting would be of particular interest if it was to provide practical
guidelines to deep learning practitioners in the spirit of Yang et al. [2021].

### Acknowledgments

VC would like to thank Alex Nowak-Vila for sharing precious insights with him
that led to this work, as well as Francis Bach for useful comments. This work
was funded in part by the French government under management of Agence
Nationale de la Recherche as part of the “Investissements d’avenir” program,
reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge
support of the European Research Council (grants SEQUOIA 724063 and REAL
94790).

## References

  * Arora et al. [1997] Sanjeev Arora, László Babai, Jacques Stern, and Elizabeth Sweedyk.  The hardness of approximate optima in lattices, codes, and systems of linear equations.  _Journal of Computer and System Sciences_ , 1997.
  * Audibert and Tsybakov [2007] Jean-Yves Audibert and Alexander Tsybakov.  Fast learning rates for plug-in classifiers.  _The Annals of Statistics_ , 2007.
  * Bach [2023] Francis Bach.  _Learning Theory from First Principles_.  To appear at MIT press, 2023.
  * Bartlett and Mendelson [2002] Peter Bartlett and Shahar Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 2002.
  * Bartlett et al. [2006] Peter Bartlett, Michael Jordan, and Jon McAuliffe.  Convexity, classification, and risk bounds.  _Journal of the American Statistical Association_ , 2006.
  * Benjamin [2019] Ruha Benjamin.  _Race After Technology: Abolitionist Tools for the New Jim Code_.  Polity, 2019.
  * Blaschzyk and Steinwart [2018] Ingrid Blaschzyk and Ingo Steinwart.  Improved classification rates under refined margin conditions.  _Electronic Journal of Statistics_ , 2018.
  * Cabannes et al. [2021a] Vivien Cabannes, Alessandro Rudi, and Francis Bach.  Disambiguation of weak supervision with exponential convergence rates.  In _International Conference on Machine Learning_ , 2021a.
  * Cabannes et al. [2021b] Vivien Cabannes, Alessandro Rudi, and Francis Bach.  Fast rates in structured prediction.  In _Conference on Learning Theory_ , 2021b.
  * Castillo and Rafeiro [2016] René Erlín Castillo and Humberto Rafeiro.  _An Introductory Course in Lebesgue Spaces_.  Springer, 2016.
  * Chang and Lin [2011] Chih-Chung Chang and Chih-Jen Lin.  LIBSVM: A library for support vector machines.  _ACM TIST_ , 2011.
  * Chizat and Bach [2020] Lénaïc Chizat and Francis Bach.  Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss.  In _Conference on Learning Theory_ , 2020.
  * Chowdhery et al. [2022] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel.  PaLM: Scaling language modeling with pathways.  Technical Report 2204.02311, arXiv, 2022.
  * Cortes and Vapnik [1995] Corinna Cortes and Vladimir Vapnik.  Support-vector networks.  _Journal of Machine Learning_ , 1995.
  * Cristianini and Shawe-Taylor [2000] Nello Cristianini and John Shawe-Taylor.  _An Introduction to Support Vector Machines and Other Kernel-based Learning Methods_.  Cambridge university press, 2000.
  * Dudley [1967] Richard Dudley.  The sizes of compact subsets of hilbert space and continuity of Gaussian processes.  _Journal of Functional Analysis_ , 1967.
  * Fischer and Steinwart [2020] Simon Fischer and Ingo Steinwart.  Sobolev norm learning rates for regularized least-squares algorithms.  _Journal of Machine Learning Research_ , 2020.
  * Friedman [1994] Jerome Friedman.  Flexible metric nearest neighbor classification.  Technical report, Department of Statistics, Stanford University, 1994\.
  * Frongillo and Waggoner [2021] Rafael Frongillo and Bo Waggoner.  Surrogate regret bounds for polyhedral losses.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Gentile and Warmuth [1999] Claudio Gentile and Manfred Warmuth.  Linear hinge loss and average margin.  In _Advances in Neural Information Processing Systems_ , 1999.
  * Géron [2017] Aurélien Géron.  _Hands-On Machine Learning with Scikit-Learn & TensorFlow_.  O’Reilly, 2017.
  * Harris et al. [2020] Charles Harris, Jarrod Millman, Stéfan van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis Oliphant.  Array programming with NumPy.  _Nature_ , 2020.
  * Höffgen and Simon [1992] Klaus-Uwe Höffgen and Hans Ulrich Simon.  Robust trainability of single neurons.  In _Computational Learning Theory_ , 1992.
  * Hunter [2007] John Hunter.  Matplotlib: A 2D graphics environment.  _Computing in Science & Engineering_, 2007.
  * Joachims [1998] Thorsten Joachims.  Text categorization with support vector machines: Learning with many relevant features.  In _European Conference on Machine Learning_ , 1998.
  * Kolmogorov and Tikhomirov [1959] Andrey Kolmogorov and Vladimir Tikhomirov.  $\varepsilon$-entropy and $\varepsilon$-capacity of sets in functional spaces.  _Uspekhi Matematicheskikh Nauk_ , 1959.
  * Koltchinskii and Beznosova [2005] Vladimir Koltchinskii and Olexandra Beznosova.  Exponential convergence rates in classification.  In _International Conference on Computational Learning Theory_ , 2005\.
  * Lin et al. [2020] Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher.  Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces.  _Applied and Computational Harmonic Analysis_ , 2020.
  * Mammen and Tsybakov [1999] Enno Mammen and Alexander Tsybakov.  Smooth discrimination analysis.  _The Annals of Statistics_ , 1999.
  * Marteau-Ferey et al. [2019] Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis Bach, and Alessandro Rudi.  Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance.  In _Conference on Learning Theory_ , 2019.
  * Massart and Nédélec [2006] Pascal Massart and Élodie Nédélec.  Risk bounds for statistical learning.  _The Annals of Statistics_ , 2006.
  * Nitanda and Suzuki [2019] Atsushi Nitanda and Taiji Suzuki.  Stochastic gradient descent with exponential convergence rates of expected classification errors.  In _International Conference on Artificial Intelligence and Statistics_ , 2019.
  * Nowak-Vila et al. [2020] Alex Nowak-Vila, Francis Bach, and Alessandro Rudi.  A general theory for structured prediction with smooth convex surrogates.  Technical Report 1902.01958, ArXiv, 2020.
  * Pedregosa et al. [2011] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 2011.
  * Pillaud-Vivien et al. [2018] Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach.  Exponential convergence of testing error for stochastic gradient methods.  In _Conference on Learning Theory_ , 2018.
  * Rigollet [2007] Philippe Rigollet.  Generalization error bounds in semi-supervised classification under the cluster assumption.  _Journal of Machine Learning Research_ , 2007.
  * Rosasco et al. [2004] Lorenzo Rosasco, Ernesto De Vito, Andrea Caponnetto, Michele Piana, and Alessandro Verri.  Are loss functions all the same?  _Neural Computation_ , 2004.
  * Scholkopf and Smola [2001] Bernhard Scholkopf and Alexander Smola.  _Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond_.  MIT press, 2001.
  * Steinwart [2007] Ingo Steinwart.  How to compare different loss functions and their risks.  _Constructive Approximation_ , 2007.
  * Steinwart and Christmann [2008] Ingo Steinwart and Andreas Christmann.  _Support Vector Machines_.  Springer Science & Business Media, 2008.
  * Steinwart and Scovel [2007] Ingo Steinwart and Clint Scovel.  Fast rates for support vector machines using Gaussian kernels.  _The Annals of Statistics_ , 2007.
  * Valiant [2013] Leslie Valiant.  _Probably Approximately Correct_.  Basic Books, 2013.
  * Vapnik [1995] Vladimir Vapnik.  _The Nature of Statistical Learning Theory_.  Springer-Verlag, 1995.
  * Vigogna et al. [2022] Stefano Vigogna, Giacomo Meanti, Ernesto De Vito, and Lorenzo Rosasco.  Multiclass learning with margin: exponential rates with no bias-variance trade-off.  Technical Report 2202.01773, ArXiv, 2022.
  * Vovk and Shafer [2008] Vladimir Vovk and Glenn Shafer.  A tutorial on conformal prediction.  _Journal of Machine Learning Research_ , 2008.
  * Wilbraham [1848] Henry Wilbraham.  On a certain periodic function.  _The Cambridge and Dublin Mathematical Journal_ , 1848.
  * Yang et al. [2021] Greg Yang, Edward Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao.  Tensor programs V: Tuning large neural networks via zero-shot hyperparameter transfer.  In _Advances in Neural Information Processing Systems_ , 2021.

##  Appendix A Proofs

###  A.1 Proof of Lemma 1

The first part follows by integration of a pointwise result. Consider the
function $h_{p}:\mathbb{R}\to\mathbb{R};q\mapsto p(1-q)_{+}+(1-p)(1+q)_{+}$,
where $p\in(0,1)$ represents $\operatorname{\mathbb{P}}(Y=1|X)$ and $q$
represents $g(x)$. The function $h_{p}$ has a slope equal to $-p$ for $q<-1$,
then slope $1-2p$ for $q\in(-1,1)$, and $1-p$ for $q>1$. Therefore, when
$q_{1},q_{2}\in(-1,1)$, we have

$h_{p}(q_{2})-h_{p}(q_{1})=(1-2p)(q_{2}-q_{1}).$

Taking $p=\operatorname{\mathbb{P}}(Y=1|X)$, $q_{2}=g_{2}(X)$ and
$q_{1}=g_{1}(X)$, we get $1-2p=-\operatorname{\mathbb{E}}[Y|X]=-\eta(X)$. By
integration, we obtain the claim. From the previous slope considerations, it
also follows that $h_{p}$ is minimized by $q=\operatorname{sign}(2p-1)$,
meaning that one can take $g^{*}(X)=\operatorname{sign}\eta(X)$.

The second part follows from the fact that projecting on $[-1,1]$ can only
reduce the value of the hinge loss, that $\eta(x)(\pi(g)(x)-g^{*}(x))$ is
always negative, and the reverse Hölder inequality:

${\cal R}_{S}(g)-{\cal R}(g^{*})\geq{\cal R}_{S}(\pi(g))-{\cal
R}(g^{*})=\left\|\eta(\pi(g)-g^{*})\right\|_{1}\geq\left\|\pi(g)-g^{*}\right\|_{q}\left\|\left|\eta\right|^{-1}\right\|_{p}^{-1}.$

A Hölder inequality also holds for weak Lebesgue spaces [see Castillo and
Rafeiro, 2016, Theorem 5.23], whence

${\cal R}_{S}(g)-{\cal
R}(g^{*})\geq\left\|\eta(\pi(g)-g^{*})\right\|_{1}\geq\left\|\eta(\pi(g)-g^{*})\right\|_{1,\infty}\geq\frac{1}{2}\left\||\eta|^{-1}\right\|_{p,\infty}^{-1}\left\|\pi(g)-g^{*}\right\|_{\frac{p}{p+1},\infty}.$

This completes the proof.

###  A.2 Proof of Lemma 2

Assume without restrictions that there exists $x\in\mathcal{X}_{1}$ such that
$|g^{*}(x)-g(x)|\geq 1$. For any event $A=A(X)$, by the law of total
probability we have

$\operatorname{\mathbb{P}}(A)=\rho_{\mathcal{X}}(\mathcal{X}_{1})\operatorname{\mathbb{P}}\left(A\,\middle|\,X\in\mathcal{X}_{1}\right)+\rho_{\mathcal{X}}(\mathcal{X}_{-1})\operatorname{\mathbb{P}}\left(A\,\middle|\,X\in\mathcal{X}_{-1}\right)\geq\rho_{\mathcal{X}}(\mathcal{X}_{1})\operatorname{\mathbb{P}}\left(A\,\middle|\,X\in\mathcal{X}_{1}\right).$

Hence, since $g^{*}(\mathcal{X}_{1})=\left\\{1\right\\}$,

$\displaystyle\left\|g-g^{*}\right\|_{q,\infty}^{q}=\sup_{t>0}t^{q}\operatorname{\mathbb{P}}(\left|g(X)-g^{*}(X)\right|>t)\geq\sup_{t>0}t^{q}\operatorname{\mathbb{P}}\left(\left|g(X)-1\right|>t\,\middle|\,X\in\mathcal{X}_{1}\right)\rho_{\mathcal{X}}(\mathcal{X}_{1}).$

Using the triangular inequality, the $G$-Lipschitz continuity of $g$, and the
definition of $x$, we have that, for any $x^{\prime}\in\mathcal{X}$,

$|g(x^{\prime})-1|\geq|g(x)-1|-|g(x^{\prime})-g(x)|\geq 1-Gd(x,x^{\prime}).$

As a consequence,

$\operatorname{\mathbb{P}}\left(|g(X)-1|>t\,\middle|\,X\in\mathcal{X}_{1}\right)\geq\operatorname{\mathbb{P}}\left(X\in{\cal
B}\left(x,\frac{1-t}{G}\right)\mid
X\in\mathcal{X}_{1}\right)=\frac{\rho_{\mathcal{X}}\left(\mathcal{X}_{1}\cap{\cal
B}\left(x,\frac{1-t}{G}\right)\right)}{\rho_{\mathcal{X}}\left(\mathcal{X}_{1}\right)}.$

Combined with the previous facts, we get

$\left\|g-g^{*}\right\|_{q,\infty}^{q}\geq\sup_{t>0}t^{q}\rho_{\mathcal{X}}\left(\mathcal{X}_{1}\cap{\cal
B}\left(x,\frac{1-t}{G}\right)\right).$

Thanks to Assumption 3, there exists $(c,r,d)$ such that (14) holds for
$\mathcal{X}_{1}$. Hence, when $G^{-1}<r$, we get the following lower bound:

$\left\|g-g^{*}\right\|_{q,\infty}^{q}\geq
cG^{-d}\sup_{t\in[0,1]}t^{q}(1-t)^{d}=cG^{-d}\frac{q^{q}d^{d}}{(d+q)^{d+q}}.$

This proves the statement in the lemma.

###  A.3 Proof of Proposition 1

Suppose ${\cal R}(\operatorname{sign}g)>{\cal R}(f^{*})$. Then, observing that
$\operatorname{sign}(\pi(t))=\operatorname{sign}(t)$ for all $t\in\mathbb{R}$,
and taking $g^{*}=f^{*}$, we know there must be
$x\in\operatorname*{supp}\rho_{\mathcal{X}}$ such that
$\left|\pi(g(x))-g^{*}(x)\right|\geq 1$. Hence, by Lemma 2, we get
$\left\|\pi(g)-g^{*}\right\|_{q,\infty}\geq c_{0}G^{-\frac{d}{q}}$, and
therefore, by Lemma 1, ${\cal R}_{S}(g)-{\cal R}_{S}(g^{*})\geq
2^{-1}c_{0}G^{-\frac{d}{q}}\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}^{-1}.$
Thus, the proposition is proved.

###  A.4 Proof of Theorem 1

From Proposition 1 and Assumption 4, we get, with
$\tilde{L}=\max\left\\{MG_{\varphi}\sigma^{-1},r^{-1}\right\\}$ and
$q=\nicefrac{{p}}{{p+1}}$,

$\displaystyle\operatorname{\mathbb{E}}_{{\cal D}_{n}}[{\cal
R}(\operatorname{sign}g_{{\cal D}_{n}})]-{\cal R}(f^{*})$
$\displaystyle\leq\operatorname{\mathbb{P}}_{{\cal D}_{n}}\left({\cal
R}_{S}(g_{{\cal D}_{n}})-{\cal R}_{S}(g^{*})\geq
2^{-1}\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}^{-1}c_{0}\tilde{L}^{-\frac{d}{q}}\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}_{{\cal D}_{n}}\left({\cal
R}_{S}(g_{{\cal D}_{n}})-{\cal R}_{S}(g_{M,\sigma})\geq
4^{-1}\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}^{-1}c_{0}\tilde{L}^{-\frac{d}{q}}\right).$

To deal with this last quantity, we can reuse the literature on Rademacher
complexity for linear models on convex risks [Bartlett and Mendelson, 2002],
which ensures that

$\operatorname{\mathbb{E}}_{{\cal D}_{n}}\left[\sup_{g\in{\cal
G}_{M,\sigma}}\left|{\cal R}_{S}(g)-{\cal R}_{S,{\cal
D}_{n}}(g)\right|\right]\leq M\left\|\varphi\right\|_{\infty}n^{-1/2}.$

Note that Assumption 3 implies that $\operatorname*{supp}\rho_{\mathcal{X}}$
is compact, hence, if $\varphi$ is Lipschitz-continuous, it is bounded on
$\operatorname*{supp}\rho_{\mathcal{X}}$. This allows us to use McDiarmid
inequality to get the same type of bound on the deviation of ${\cal
R}_{S}(g_{{\cal D}_{n}})$ around its mean, namely, for any $t>0$,

$\operatorname{\mathbb{P}}_{{\cal D}_{n}}\left(\sup_{g\in{\cal
G}_{M,\sigma}}\left|{\cal R}_{S}(g)-{\cal R}_{S,{\cal
D}_{n}}(g)\right|>t+M\left\|\varphi\right\|_{\infty}n^{-1/2}\right)\leq\exp\left(-\frac{nt^{2}}{8}\right).$
(22)

When
$4^{-1}\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}^{-1}c_{0}\tilde{L}^{-\frac{d}{q}}\geq\left\|\varphi\right\|_{\infty}Mn^{-1/2}$,
this leads to

$\displaystyle\operatorname{\mathbb{E}}_{{\cal D}_{n}}[{\cal
R}(\operatorname{sign}g_{{\cal D}_{n}})]-{\cal
R}(f^{*})\leq\exp\left(-\frac{n}{8}\left(4^{-1}\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}^{-1}c_{0}\tilde{L}^{-\frac{d}{q}}-M\left\|\varphi\right\|_{\infty}n^{-1/2}\right)^{2}\right)$
$\displaystyle\quad\leq\exp\left(-\frac{c_{0}^{2}\sigma^{\frac{2d(p+1)}{p}}}{128\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}^{2}(MG_{\varphi})^{\frac{2d(p+1)}{p}}}\cdot
n+\frac{c_{0}\left\|\varphi\right\|_{\infty}}{\left\|\left|\eta\right|^{-1}\right\|_{p,\infty}M^{\frac{d(p+1)}{p}-1}G_{\varphi}^{\frac{d(p+1)}{p}}}\cdot
n^{-1/2}-\frac{M^{2}\left\|\varphi\right\|_{\infty}^{2}}{8}\right).$

The result follows directly from this bound.

##  Appendix B Experimental details

In our experiments, we used the SVM implementation of Chang and Lin [2011]
through its Scikit-learn wrapper [Pedregosa et al., 2011] in Python. We used
Numpy [Harris et al., 2020] to reduce our work to high-level array
instructions, and Matplotlib for visualization [Hunter, 2007]. Randomness in
experiments was controlled with the random seed provided by Numpy, which we
initialized at zero.

Figure 5:  (Left) Similar setting as Figure 2 but with $X$ uniform on
$[-1,1]$. The behavior of the excess of risk is quite different without the
separation in $\mathcal{X}$: no exponential convergence rate is kicking in
after a thousand of samples. (Right) Similar setting as Figure 2, using kernel
ridge regression with the least-squares surrogate. Exponential convergence
rates are observed with a slight delay compared to the hinge loss, and are
explained by the hard-margin condition 1.

Figures 2 and 5 are derived by averaging 100 trials of the following
procedure. We draw uniformly at random $n$ independent samples uniformly
distributed on $\mathcal{X}\in\left\\{[-1,1],[-1,-.1]\cup[.1,1]\right\\}$. We
draw randomly one output $y_{i}$ for each input $x_{i}$, according to
$\eta(x_{i})$. We consider the Gaussian kernel
$k(x,x^{\prime})=\exp(-\left\|x-x^{\prime}\right\|^{2}/2\sigma^{2})$ for
$\sigma=.2$, and solve the empirical risk minimization associated to the hinge
loss with the penalization $\lambda\left\|\theta\right\|^{2}$ (rather than the
hard constraint $\left\|\theta\right\|<M$) for $\lambda=10^{-4}$. The
generalization error is measured through the formula
$\operatorname{\mathbb{E}}[\left\|\eta(x)\right\|\mathbf{1}_{f(x)\neq
f^{*}(x)}]$, with an empirical approximation of this sum with the points
$(x_{i})_{i\leq n}$ chosen such that $\rho_{\mathcal{X}}([x_{i},x_{i+1}])=1/n$
and $\rho_{\mathcal{X}}([x_{n},+\infty))=1/n$, with $n=10^{4}$ (which makes
sure that the exponential behavior observed is not due to the lack of testing
samples). For each $x$, the height of each dark part corresponds to one
standard deviation of the generalization error computed from the 100 trials,
and the solid line corresponds to the empirical average. The fact that the
dark parts are not centered around the averages is due to the fact that we
have drawn $\log$-plots but centered the interval for linearly-scaled plots.

Figure 3 is obtained by considering $\mathcal{X}=[0,1]^{2}$ with uniform input
distribution, the Gaussian kernel with $\sigma=.2$, and the penalty parameter
$\lambda=10^{-3}$ (instead of a hard constraint leading to a parameter $M$ as
in the main text derivations). We take $n=10^{4}=100^{2}$ points uniformly
spread out on $\mathcal{X}$ (on the regular lattice
$\frac{1}{\sqrt{n}}\cdot\mathcal{Z}^{2}\cap\mathcal{X}$) to approximate
$g_{\lambda,\sigma}$ with empirical risk minimization on this curated dataset.
We consider $\eta(x)=\pi_{[-1,1]}(2x_{2}-.5\sin(2\pi x_{1})-1)$, and assign to
each $x$ in the dataset a sample $(x,1)$ weighted by
$\operatorname{\mathbb{P}}\left(Y=1\,\middle|\,X=x\right)=(\eta(x)-1)/2$, and
a sample $(x,-1)$, weighted by
$\operatorname{\mathbb{P}}\left(Y=-1\,\middle|\,X=x\right)$. The “noiseless”
setting denotes the setting where $\left(Y\,\middle|\,X\right)$ is
deterministic, but with the same decision frontier between the classes
$\mathcal{X}_{1}$ and $\mathcal{X}_{-1}$ characterized by
$\left\\{(x,.5+.25\sin(2\pi x))\,\middle|\,x\in[0,1]\right\\}$. Once we fit
the support vector machine with this dataset, we test it with $n=2.5\cdot
10^{5}=500^{2}$ datapoints uniformly spread out on $\mathcal{X}$, and use
Matplotlib to automatically draw level lines.

Figure 6:  Same setting as Figure 4, with $\sigma=.2$ and $\lambda=10^{-6}$
(top), and with $\sigma=1$ and $\lambda=10^{-3}$ (bottom).

Figures 4 and 6 correspond to $\mathcal{X}=[0,3]$ with the input distribution
uniform on $[0,1]\cup[2,3]$. Figure 4 is obtained with $\sigma=.1$ and
$\lambda=10^{-6}$. We derive it by considering $n=100$ points uniformly spread
out on the domain of $\eta$, solving the equivalent curated empirical risk
minimization, that approximates both

$\displaystyle g_{\lambda,\sigma}$
$\displaystyle=\operatorname*{arg\,min}_{g:\mathcal{X}\to\mathbb{R}}\operatorname{\mathbb{E}}_{\rho}[(0,1-Y\left\langle\theta,\varphi\left(\frac{x}{\sigma}\right)\right\rangle)_{+}]+\lambda\left\|\theta\right\|^{2},$
(23) $\displaystyle g_{(\text{LS})}$
$\displaystyle=\operatorname*{arg\,min}_{g:\mathcal{X}\to\mathbb{R}}\operatorname{\mathbb{E}}_{\rho}[\left\|\left\langle\theta,\varphi\left(\frac{x}{\sigma}\right)\right\rangle-Y\right\|^{2}]+\lambda\left\|\theta\right\|^{2}.$
(24)

The robustness of SVM might be understood from its geometrical definition:
when trying to find the maximum separating margin, infinitesimal modifications
that change the regularity properties of $\eta$ do not really matter. The
picture is different for the least-squares surrogate with kernel methods,
where from few point evaluations, the system reconstructs a function by
assuming regularity and inferring information on high-order derivatives. This
is similar to the Runge phenomenon with Hermite interpolation. More precisely,
the Gaussian kernel is linked to a space of functions with rapidly decreasing
Fourier coefficients [see, for example, Bach, 2023, for a more precise link].
The function $\eta$ that needs to be approximated on Figure 4 is similar to
the Heaviside function, whose Fourier coefficients are of the form
$(\frac{1}{i\pi k})_{k\in\mathbb{N}^{*}}$ and do not decrease fast enough to
be all reconstructed. This leads to some high-frequency oscillations missing
in the reconstruction as it appears on Figure 4.


# TransQuest at WMT2020: Sentence-Level Direct Assessment

Tharindu Ranasinghe♢, Constantin Orăsan♡ and Ruslan Mitkov♢
♢Research Group in Computational Linguistics, University of Wolverhampton, UK
♡Centre for Translation Studies, University of Surrey, UK
{t.d.ranasinghehettiarachchige<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

This paper presents the team TransQuest’s participation in Sentence-Level
Direct Assessment shared task in WMT 2020. We introduce a simple QE framework
based on cross-lingual transformers, and we use it to implement and evaluate
two different neural architectures. The proposed methods achieve state-of-the-
art results surpassing the results obtained by OpenKiwi, the baseline used in
the shared task. We further fine tune the QE framework by performing ensemble
and data augmentation. Our approach is the winning solution in all of the
language pairs according to the WMT 2020 official results.

##  1 Introduction

The goal of quality estimation (QE) systems is to determine the quality of a
translation without having access to a reference translation. This makes it
very useful in translation workflows where it can be used to determine whether
an automatically translated sentence is good enough to be used for a given
purpose, or if it needs to be shown to a human translator for translation from
scratch or postediting Kepler et al. (2019). Quality estimation can be done at
different levels: document level, sentence level and word level Ive et al.
(2018). This paper presents TransQuest, a sentence-level quality estimation
framework which is the winning solution in all the language pairs in the WMT
2020 Sentence-Level Direct Assessment shared task Specia et al. (2020).

In the past, high preforming quality estimation systems such as QuEst Specia
et al. (2013) and QuEst++ Specia et al. (2015) were heavily dependent on
linguistic processing and feature engineering. These features were fed into
traditional machine-learning algorithms like support vector regression and
randomised decision trees Specia et al. (2013), which then determined the
quality of a translation. Even though, these approaches provide good results,
they are no longer the state of the art, being replaced in recent years by
neural-based QE systems which usually rely on little or no linguistic
processing. For example the best-performing system at the WMT 2017 shared task
on QE was POSTECH, which is purely neural and does not rely on feature
engineering at all Kim et al. (2017).

In order to achieve high results, approaches such as POSTECH require extensive
pre-training, which means they depend on large parallel data and are
computationally intensive Ive et al. (2018). TransQuest, our QE framework
removes this dependency on large parallel data by using crosslingual
embeddings Ranasinghe et al. (2020) that are already fine-tuned to reflect
properties between languages Ruder et al. (2019). Ranasinghe et al. (2020)
show that by using them, TransQuest eases the burden of having complex neural
network architectures, which in turn entails a reduction of the computational
resources. That paper also shows that TransQuest performs well in transfer
learning settings where it can be trained on language pairs for which we have
resources and applied successfully on less resourced language pairs.

The remainder of the paper is structured as follows. The dataset used in the
competition is briefly discussed in Section 2. In Section 3 we present the
TransQuest framework and the methodology employed to train it. This is
followed by the evaluation results and their discussion in Section 4. The
paper finishes with conclusions and ideas for future research directions.

##  2 Dataset

The dataset for the Sentence-Level Direct Assessment shared task is composed
of data extracted from Wikipedia for six language pairs, consisting of high-
resource languages English-German (En-De) and English-Chinese (En-Zh), medium-
resource languages Romanian-English (Ro-En) and Estonian-English (Et-En), and
low-resource languages Sinhala-English (Si-En) and Nepalese-English (Ne-En),
as well as a a Russian-English (Ru-En) dataset which combines articles from
Wikipedia and Reddit Specia et al. (2020). Each language pair has 7,000
sentence pairs in the training set, 1,000 sentence pairs in the development
set and another 1,000 sentence pairs in the testing set. Each translation was
rated with a score between 0 and 100 according to the perceived translation
quality by at least three translators Fomicheva et al. (2020). The DA scores
were standardised using the z-score. The quality estimation systems have to
predict the mean DA z-scores of the test sentence pairs Specia et al. (2020).

##  3 Methodology

This section presents the methodology used to develop our quality estimation
methods. Our methodology is based on TransQuest our recently introduced QE
framework Ranasinghe et al. (2020). We first briefly describe the neural
network architectures TransQuest proposed, followed by the training details.
More details about the framework can be found in Ranasinghe et al. (2020).

###  3.1 Neural Network Architectures

The TransQuest framework that is used to implement the two architectures
described here relies on the XLM-R transformer model Conneau et al. (2020) to
derive the representations of the input sentences Ranasinghe et al. (2020).
The XLM-R transformer model takes a sequence of no more than 512 tokens as
input, and outputs the representation of the sequence. The first token of the
sequence is always [CLS] which contains the special embedding to represent the
whole sequence, followed by embeddings acquired for each word in the sequence.
As shown below, proposed neural network architectures of TransQuest can
utilise both the embedding for the [CLS] token and the embeddings generated
for each word Ranasinghe et al. (2020). The output of the transformer (or
transformers for SiameseTransQuest described below), is fed into a simple
output layer which is used to estimate the quality of translation. The way the
XLM-R transformer is used and the output layer are different in the two
instantiations of the framework. We describe each of them below. The fact that
TransQuest does not rely on a complex output layer makes training its
architectures much less computationally intensive than alternative solutions.
The TransQuest framework is open-source, which means researchers can easily
propose alternative architectures to the ones TransQuest presents Ranasinghe
et al. (2020).

Both neural network architectures presented below use the pre-trained XLM-R
models released by HuggingFace’s model repository Wolf et al. (2019). There
are two versions of the pre-trained XLM-R models named XLM-R-base and XLM-R-
large. Both of these XLM-R models cover 104 languages Conneau et al. (2020),
potentially making it very useful to estimate the translation quality for a
large number of language pairs.

TransQuest implements two different neural network architectures Ranasinghe et
al. (2020) to perform sentence-level translation quality estimation as
described below. The architectures are presented in Figure 1.

  1. 1.

MonoTransQuest (MTransQuest): The first architecture proposed uses a single
XLM-R transformer model and is shown in Figure 1(a). The input of this model
is a concatenation of the original sentence and its translation, separated by
the [SEP] token. TransQuest proposes three pooling strategies for the output
of the transformer model: using the output of the [CLS] token (CLS-strategy);
computing the mean of all output vectors of the input words (MEAN-strategy);
and computing a max-over-time of the output vectors of the input words (MAX-
strategy) Ranasinghe et al. (2020). The output of the pooling strategy is used
as the input of a softmax layer that predicts the quality score of the
translation. TransQuest used mean-squared-error loss as the objective function
Ranasinghe et al. (2020). Similar to Ranasinghe et al. (2020), the early
experiments we carried out demonstrated that the CLS-strategy leads to better
results than the other two strategies for this architecture. Therefore, we
used the embedding of the [CLS] token as the input of a softmax layer.

  2. 2.

SiameseTransQuest (STransQuest): The second approach proposed in TransQuest
relies on the Siamese architecture depicted in Figure 1(b) which has shown
promising results in monolingual semantic textual similarity tasks Reimers and
Gurevych (2019); Ranasinghe et al. (2019). For this, we fed the original text
and the translation into two separate XLM-R transformer models. Similarly to
the previous architecture, we experimented with the same three pooling
strategies for the outputs of the transformer models Ranasinghe et al. (2020).
TransQuest then calculates the cosine similarity between the two outputs of
the pooling strategy. TransQuest used mean-squared-error loss as the objective
function. Similar to Ranasinghe et al. (2020) in the initial experiments we
carried out with this architecture the MEAN-strategy showed better results
than the other two strategies. For this reason, we used the MEAN-strategy for
our experiments. Therefore, cosine similarity is calculated between the mean
of all output vectors of the input words produced by each transformer.

(a) MTransQuest architecture

(b) STransQuest Architecture

Figure 1: Two architectures of the TransQuest framework.

###  3.2 Training Details

We used the same set of configurations suggested in Ranasinghe et al. (2020)
for all the language pairs evaluated in this paper in order to ensure
consistency between all the languages. This also provides a good starting
configuration for researchers who intend to use TransQuest on a new language
pair. In both architectures, we used a batch-size of eight, Adam optimiser
with learning rate $2\mathrm{e}{-5}$, and a linear learning rate warm-up over
10% of the training data. The models were trained using only training data.
Furthermore, they were evaluated while training using an evaluation set that
had one fifth of the rows in training data. We performed early stopping if the
evaluation loss did not improve over ten evaluation rounds. All of the models
were trained for three epochs. For some of the experiments, we used an Nvidia
Tesla K80 GPU, whilst for others we used an Nvidia Tesla T4 GPU. This was
purely based on the availability of the hardware and it was not a
methodological decision.

###  3.3 Implementation Details

The TransQuest framework was implemented using Python 3.7 and PyTorch 1.5.0.
To integrate the functionalities of the transformers we used the version 3.0.0
of the HuggingFace’s Transformers library. The implemented framework is
available on GitHub111TransQuest GitHub repository -
https://github.com/tharindudr/transQuest.

##  4 Evaluation, Results and Discussion

This section presents the evaluation results of our architectures and the fine
tuning strategies that can be used to improve the results. We first evaluate
the TransQuest framework with the default setting (Section 4.1). Next we
evaluate an ensemble setting of TransQuest in Section 4.2. We finally assess
the performance of TransQuest with augmented data. We conclude the section
with a discussion of the results.

The evaluation metric used was the Pearson correlation ($r$) between the
predictions and the gold standard from the test set, which is the most
commonly used evaluation metric in WMT quality estimation shared tasks Specia
et al. (2018); Fonseca et al. (2019). We report the Pearson correlation values
that we obtained from CodaLab, the hosting platform of the WMT 2020 QE shared
task. As a baseline we compare our results with the performance of OpenKiwi as
reported by the task organisers Specia et al. (2020).

|  | Low-resource | Mid-resource | High-resource
---|---|---|---|---
| Method | Si-En | Ne-En | Et-En | Ro-En | Ru-En | En-De | En-Zh
I | MTransQuest | 0.6525 | 0.7914 | 0.7748 | 0.8982 | 0.7734 | 0.4669 | 0.4779
STransQuest | 0.5957 | 0.7081 | 0.6804 | 0.8501 | 0.7126 | 0.3992 | 0.4067
II | MTransQuest-base | 0.6412 | 0.7823 | 0.7651 | 0.8715 | 0.7593 | 0.4421 | 0.4593
STransQuest-base | 0.5773 | 0.6853 | 0.6692 | 0.8321 | 0.6962 | 0.3832 | 0.3975
III | MTransQuest $\otimes$ | 0.6661 | 0.8023 | 0.7876 | 0.8988 | 0.7854 | 0.4862 | 0.4853
STransQuest $\otimes$ | 0.6001 | 0.7132 | 0.6901 | 0.8629 | 0.7248 | 0.4096 | 0.4159
IV | MTransQuest $\otimes$ \- Aug | 0.6849 | 0.8222 | 0.8240 | 0.9082 | 0.8082 | 0.5539 | 0.5373
STransQuest $\otimes$ \- Aug | 0.6241 | 0.7354 | 0.7239 | 0.8621 | 0.7458 | 0.4457 | 0.4658
V | OpenKiwi | 0.3737 | 0.3860 | 0.4770 | 0.6845 | 0.5479 | 0.1455 | 0.1902
Table 1: Pearson ($r$) correlation between TransQuest algorithm predictions
and human DA judgments. Best results for each language (any method) are marked
in bold. Rows I, II, III and IV indicate the different settings of TransQuest,
explained in Sections 4.1-4.3. OpenKiwi baseline results are in Row V.

###  4.1 TransQuest with Default settings

The first evaluation we carried out was for the default configurations of the
TransQuest framework where we used the training set of each language to build
a quality estimation model using XLM-R-large transformer model and we
evaluated it on a test set from the same language.

The results for each language with default settings are shown in row I of
Table 1. The results indicate that both architectures proposed in TransQuest
outperform the baseline, OpenKiwi, in all the language pairs. From the two
architectures, MTransQuest performs slightly better than STransQuest.

As shown in Table 1, MTransQuest gained $\approx$ 0.2-0.3 Pearson correlation
boost over OpenKiwi in all the language pairs. Additionally, MTransQuest
achieves $\approx$ 0.4 Pearson correlation boost over OpenKiwi in the low-
resource language pair Ne-En.

###  4.2 TransQuest with Ensemble

Transformers have been proven to provide better results when experimented with
ensemble techniques Xu et al. (2020). In order to improve the results of
TransQuest we too followed an ensemble approach which consisted of two steps.
We conducted these steps for both architectures in TransQuest.

  1. 1.

We train TransQuest using the pre-trained XLM-R-base transformer model instead
of the XLM-R-large transformer model in the TransQuest default setting. We
report the results from the two architectures from this step in row II of
Table 1 as MTransQuest-base and STransQuest-base.

  2. 2.

We perform a weighted average ensemble for the output of the default setting
and the output we obtained from step 1. We experimented on weights 0.8:0.2,
0.6:0.4, 0.5:0.5 on the output of the default setting and output from the step
1 respectively. Since the results we got from XLM-R-base transformer model are
slightly worse than the results we got from default setting we did not
consider the weight combinations that gives higher weight to XLM-R-base
transformer model results. We obtained best results when we used the weights
0.8:0.2. We report the results from the two architectures from this step in
row III of Table 1 as MTransQuest $\otimes$ and STransQuest $\otimes$.

As shown in Table 1 both architectures in TransQuest with ensemble setting
gained $\approx$ 0.01-0.02 Pearson correlation boost over the default settings
for all the language pairs.

###  4.3 TransQuest with Data Augmentation

All of the languages had 7,000 training instances that we used in the above
mentioned settings in TransQuest. To experiment how TransQuest performs with
more data, we trained TransQuest on a data augmented setting. Alongside the
training, development and testing datasets, the shared task organisers also
provided the parallel sentences which were used to train the neural machine
translation system in each language. In the data augmentation setting, we
added the sentence pairs from that neural machine translation system training
file to training dataset we used to train TransQuest. In order to find the
best setting for the data augmentation we experimented with adding 1000, 2000,
3000, up to 5000 sentence pairs randomly. Since the ensemble setting performed
better than the default setting of TransQuest, we conducted this data
augmentation experiment on the ensemble setting. We assumed that the sentence
pairs added from the neural machine translation system training file have
maximum translation quality.

Up to 2000 sentence pairs the results continued to get better. However, adding
more than 2000 sentence pairs did not improve the results. We did not
experiment with adding any further than 5000 sentence pairs to the training
set since the timeline of the competition was tight. We were also aware that
adding more sentence pairs with the maximum translation quality to the
training file will make it imbalance and affect the performance of the machine
learning models negatively. We report the results from the two architectures
from this step in row IV of Table 1 as MTransQuest $\otimes$-Aug and
STransQuest $\otimes$-Aug.

This setting provided the best results for both architectures in TransQuest
for all of the language pairs. As shown in Table 1 both architectures in
TransQuest with the data augmentation setting gained $\approx$ 0.01-0.09
Pearson correlation boost over the default settings for all the language
pairs. Additionally, MTransQuest $\otimes$-Aug achieves $\approx$ 0.09 Pearson
correlation boost over default MTransQuest in the high-resource language pair
En-De.

###  4.4 Error analysis

In an attempt to better understand the performance and limitations of
TransQuest we carried out an error analysis on the results obtained on
Romanian - English and Sinhala - English. The choice of language pairs we
analysed was determined by the availability of native speakers to perform this
analysis. We focused on the cases where the difference between the predicted
score and expected score was the greatest. This included both cases where the
predicted score was underestimated and overestimated.

Analysis of the results does not reveal very clear patterns. The largest
number of errors seem to be caused by the presence of named entities in the
source sentences. In some cases these entities are mishandled during the
translation. The resulting sentences are usually syntactically correct, but
semantically odd. Typical examples are _RO: În urmă explorărilor Căpitanului
James Cook, Australia și Noua Zeelandă au devenit ținte ale colonialismului
britanic. (As a result of Captain James Cook’s explorations, Australia and New
Zealand have become the targets of British colonialism.)_ \- _EN: Captain
James Cook, Australia and New Zealand have finally become the targets of
British colonialism._ (expected: -1.2360, predicted: 0.2560) and _RO: O altă
problemă importantă cu care trupele Antantei au fost obligate să se confrunte
a fost malaria. (Another important problem that the Triple Entente troops had
to face was malaria.)_ \- EN: _Another important problem that Antarctic troops
had to face was malaria._ (expected: 0.2813, predicted: -0.9050). In the
opinion of the authors of this paper, it is debatable whether the expected
scores for these two pairs should be so different. Both of them have obvious
problems and cannot be clearly understood without reading the source. For this
reason, we would expect that both of them have low scores. Instances like this
also occur in the training data. As a result of this, it may be that
TransQuest learns contradictory information, which in turn leads to errors at
the testing stage.

A large number of problems are caused by incomplete source sentences or input
sentences with noise. For example the pair _RO: thumbright250pxDrapelul cu
fâșiile în poziție verticală (The flag with strips in upright position)_ \-
_EN: ghtghtness 250pxDrapel with strips in upright position_ has an expected
score of 0.0595, but our method predicts -0.9786. Given that only _ghtghtness
250pxDrapel_ is wrong in the translation, the predicted score is far too low.
In an attempt to see how much this noise influences the result, we run the
system with the pair _RO: Drapelul cu fâșiile în poziție verticală_ \- _EN:
Drapel with strips in upright position_. The prediction is 0.42132, which is
more in line with our expectations given that one of the words is not
translated.

Similar to Ro-En, in Si-En the majority of problems seem to be caused by the
presence of named entities in the source sentences. For an example in the
English translation: _But the disguised Shiv will help them securely establish
the statue._ (expected: 1.3618, predicted: -0.008), the correct English
translation would be _But the disguised Shividru will help them securely
establish the statue._. Only the named entity _Shividru_ is translated
incorrectly, therefore the annotators have annotated the translation with a
high quality. However TransQuest fails to identify that. Similar scenarios can
be found in English translations _Kamala Devi Chattopadhyay spoke at this
meeting, Dr. Ann._ (expected:1.3177, predicted:-0.2999) and _The Warrior Falls
are stone’s, halting, heraldry and stonework rather than cottages. The
cathedral manor is navigable places_ (expected:0.1677, predicted:-0.7587). It
is clear that the presence of the named entities seem to confuse the algorithm
we used, hence it needs to handle named entities in a proper way.

##  5 Conclusion

In this paper we evaluated different settings of TransQuest in sentence-level
direct quality assessment. We showed that ensemble results with XLM-R-base and
XLM-R-large with data augmentation techniques can improve the performance of
TransQuest framework.

The official results of the competition show that TransQuest won the first
place in all the language pairs in Sentence-Level Direct Assessment task.
TransQuest is the sole winner in En-Zh, Ne-En and Ru-En language pairs and the
multilingual track. For the other language pairs (En-De, Ro-En, Et-En and Si-
En) it shares the first place with another system, whose results are not
statistically different from ours. The full results of the shared task can be
seen in Specia et al. (2020).

In the future, we plan to experiment more with the data augmentation settings.
We are interested in augmenting the training file with semantically similar
sentences to the test set rather than augmenting with random sentence pairs as
we did in this paper. As shown in the error analysis in Section 4.4 the future
releases of the framework need to handle named entities properly. We also hope
to implement TransQuest in document level quality estimation too.

## References

  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451, Online. Association for Computational Linguistics.
  * Fomicheva et al. (2020) M Fomicheva, L Specia, S Sun, L Yankovskaya, F Blain, F Guzmán, M Fishel, N Aletras, and V Chaudhary. 2020.  Unsupervised quality estimation for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , Vol 8 (2020).
  * Fonseca et al. (2019) Erick Fonseca, Lisa Yankovskaya, André F. T. Martins, Mark Fishel, and Christian Federmann. 2019.  Findings of the WMT 2019 shared tasks on quality estimation.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 3: Shared Task Papers, Day 2)_ , pages 1–10, Florence, Italy. Association for Computational Linguistics.
  * Ive et al. (2018) Julia Ive, Frédéric Blain, and Lucia Specia. 2018.  deepQuest: A framework for neural-based quality estimation.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 3146–3157, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Kepler et al. (2019) Fabio Kepler, Jonay Trénous, Marcos Treviso, Miguel Vera, and André F. T. Martins. 2019.  OpenKiwi: An open source framework for quality estimation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 117–122, Florence, Italy. Association for Computational Linguistics.
  * Kim et al. (2017) Hyun Kim, Jong-Hyeok Lee, and Seung-Hoon Na. 2017.  Predictor-estimator using multilevel task learning with stack propagation for neural quality estimation.  In _Proceedings of the Second Conference on Machine Translation_ , pages 562–568, Copenhagen, Denmark. Association for Computational Linguistics.
  * Ranasinghe et al. (2019) Tharindu Ranasinghe, Constantin Orasan, and Ruslan Mitkov. 2019.  Semantic textual similarity with Siamese neural networks.  In _Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2019)_ , pages 1004–1011, Varna, Bulgaria. INCOMA Ltd.
  * Ranasinghe et al. (2020) Tharindu Ranasinghe, Constantin Orasan, and Ruslan Mitkov. 2020.  Transquest: Translation quality estimation with cross-lingual transformers.  In _Proceedings of the 28th International Conference on Computational Linguistics_.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence embeddings using Siamese BERT-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3982–3992, Hong Kong, China. Association for Computational Linguistics.
  * Ruder et al. (2019) Sebastian Ruder, Ivan Vulić, and Anders Søgaard. 2019.  A survey of cross-lingual word embedding models.  _J. Artif. Int. Res._ , 65(1):569–630.
  * Specia et al. (2020) Lucia Specia, Frédéric Blain, Marina Fomicheva, Erick Fonseca, Vishrav Chaudhary, Francisco Guzmán, and André FT Martins. 2020.  Findings of the wmt 2020 shared task on quality estimation.  In _Proceedings of the Fifth Conference on Machine Translation: Shared Task Papers_.
  * Specia et al. (2018) Lucia Specia, Frédéric Blain, Varvara Logacheva, Ramón Astudillo, and André F. T. Martins. 2018.  Findings of the WMT 2018 shared task on quality estimation.  In _Proceedings of the Third Conference on Machine Translation: Shared Task Papers_ , pages 689–709, Belgium, Brussels. Association for Computational Linguistics.
  * Specia et al. (2015) Lucia Specia, Gustavo Paetzold, and Carolina Scarton. 2015.  Multi-level translation quality prediction with QuEst++.  In _Proceedings of ACL-IJCNLP 2015 System Demonstrations_ , pages 115–120, Beijing, China. Association for Computational Linguistics and The Asian Federation of Natural Language Processing.
  * Specia et al. (2013) Lucia Specia, Kashif Shah, Jose G.C. de Souza, and Trevor Cohn. 2013.  QuEst - a translation quality estimation framework.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 79–84, Sofia, Bulgaria. Association for Computational Linguistics.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, R’emi Louf, Morgan Funtowicz, and Jamie Brew. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _ArXiv_ , abs/1910.03771.
  * Xu et al. (2020) Yige Xu, Xipeng Qiu, Ligao Zhou, and Xuanjing Huang. 2020.  Improving bert fine-tuning via self-ensemble and self-distillation.  _arXiv preprint arXiv:2002.10345_.