Transformers are Deep Infinite-Dimensional Non-Mercer Binary Kernel Machines
Authors: Matthew A Wright
Joseph E. Gonzalez
Venue:  (2021)
Keywords: Transformer models
attention models
kernel methods
reproducing kernel Banach spaces

Abstract: Despite their ubiquity in core AI fields like natural language processing, the mechanics of deep attention-based neural networks like the ``Transformer'' model are not fully understood. In this article, we present a new perspective towards understanding how Transformers work. In particular, we show that the ``"dot-product attention" that is the core of the Transformer's operation can be characterized as a kernel learning method on a pair of Banach spaces. In particular, the Transformer's kernel is characterized as having an infinite feature dimension. Along the way we generalize the standard kernel learning problem to what we term a "binary" kernel learning problem, where data come from two input domains and a response is defined for every cross-domain pair. We prove a new representer theorem for these binary kernel machines with non-Mercer (indefinite, asymmetric) kernels (implying that the functions learned are elements of reproducing kernel Banach spaces rather than Hilbert spaces), and also prove a new universal approximation theorem showing that the Transformer calculation can learn any binary non-Mercer reproducing kernel Banach space pair. We experiment with new kernels in Transformers, and obtain results that suggest the infinite dimensionality of the standard Transformer kernel is partially responsible for its performance. This paper's results provide a new theoretical understanding of a very important but poorly understood model in modern machine learning.

Under review as a conference paper at ICLR 2021
TRANSFORMERS ARE DEEP BINARY KERNEL MACHINES
Anonymous authors Paper under double-blind review
ABSTRACT
Despite their ubiquity in core AI fields like natural language processing, the me- chanics of deep attention-based neural networks like the "Transformer" model are not fully understood. In this article, we present new perspective towards understanding how Transformers work. In particular, we show that the "dot-product attention" that is the core of the Transformer's operation can be characterized as a kernel learning method on pair of Banach spaces, In particular, the Transformer's kernel is characterized as having an infinite feature dimension. Along the way we generalize the standard kernel learning problem to what we term "binary" kernel learning problem, where data come from two input domains and response is defined for every cross-domain pair. We prove a new representer theorem for these binary kernel machines with non-Mercer (indefinite, asymmetric) kernels (implying that the functions learned are elements of reproducing kernel Banach universal approximation
spaces rather than Hilbert spaces), and also prove theorem showing that the Transformer calculation can learn any binary non-Mercer reproducing kernel Banach space pair. We experiment with new kernels in Trans- formers, and obtain results that suggest the infinite dimensionality of the standard Transformer kernel is partially responsible for its performance. This paper's 's results provide a new theoretical understanding of a very important but poorly understood model in modern machine learning.
INTRODUCTION
Since its proposal by Bahdanau et al. (2015), so-called neural attention has become the backbone of many state-of-the-art deep learning models. This is true in particular natural language processing (NLP), where the Transformer model of Vaswani et al. (2017) has become ubiquitous. This ubiquity such that much of the last few years' NLP breakthroughs have been due to developing new training regimes for Transformers (Radford al., 2018: 8; Devlin et al., 2019; Yang et al., 2019; Liu et al., 2019; Wang et al., 201 9a; Joshi et al., 2020; Lan et al., 2020; Brown et al., 2020, etc.).
Like most modern deep neural networks, theoretical understanding of the Transformer has lagged behind the rate of Transformer-base performance improvements on Al tasks like NL.P. Recently, several authors have noted Transformer operations' relationship to other, better-understood topics in deep learning theory, like the similarities between attention and convolution (Ramachandran et al., 2019; Cordonnier et al., 2020) and the design of the residual blocks in multi-layer Transformers (e.g., Lu et al. (2019); see also the reordering of the main learned (fully- connected attentional) operation, elementwise nonlinearity, and normalization the original Transformer authors' official reference codebase (Vaswani et al., 2018) 8) and in some more recent studies of deeper Transformers (Wang et al., 2019b) to the "pre-norm" ordering of normalize, learned operation, nonlinearity, add residual ordering of modern ("v2") Resnets (He et al., 2016)).
In this paper, we propose a new lens to understand the central component of the Transformer, its "dot-product attention" operation. In particular, we show dot-product attention can be characterized as a particular class kernel method (Schölkopf & Smola, 2002). More specifically, it is a so-called indefinite and asymmetric kernel method, which refer to two separate generalizations of the classic class of kernels that does not require the classic assumptions of symmetry and positive (semi-) definiteness (Ong et al., 2004; Balean et al., 2008; Zhang al., 2009; Wu et al., 2010; Loosli et al.,

---

Under review as a conference paper at ICLR 2021
2016; Oglic & Gärtner, 2018; 2019, etc.). We in fact show in Theorem below that dot-product attention can learn any asymmetric indefinite kernel.
This insight has several interesting implications. Most immediately, it provides some theoretical justification for one the more mysterious components the Transformer model. also potentially opens the door for the application of decades of classic kernel method theory towards understanding one of today's 's most important neural network models, perhaps similarly to how tools from digital signal processing are widely used study convolutional neural networks. We make a first step this last point in this paper, proposing generalization of prior kernel methods we call "binary" kernel machines, that learns how to predict distinct values for pairs of elements across two input sets, similar to an attention model.
The remainder of this paper organized as follows. Section reviews the mathematical background of both Transformers and classic kernel methods. Section 3 presents the definition of kernel machines on reproducing kernel Banach spaces (RKBS's) that we use to characterize Transformers. particular we note that the Transformer can be described as having infiniteddimensional feature space. Section 4 begins our theoretical results, explicitly describing the Transformer terms of reproducing kernels, including explicit formulations of the Transformer's kernel feature maps and its relation to prior kernels. Section 5 discusses Transformers as kernel learners, including a new representer theorem and attention networks as approximate kernel learners. In Section 6, we present empirical evidence that the infinite-dimensee Transformer kernel may be somewhat responsible for the model's effectiveness. Section 7 concludes and summarizes our work.
characterization of stochastic- stochasti--gradien--eeee
character of the
BACKGROUND AND RELATED WORK
2.1 TRANSFORMER NEURAL NETWORK MODELS
The Transformer model (Vaswani et al., 2017) has become ubiquitous in many core AI applications like natural language processing. Here, we review its core components. Say we have two ordered sets of vectors, a set of "source" elements {s1, $2. ................................ sg). 8j E Rdd. and set of "target" elements {t1, .2..... tr J. t; E R In its most general form, the forms the backbone of the Transformer model is to compute, for each t,, a t.-specific embedding of the source sequence {s));=1'
"attention" operation that
The particular function used in the Transformer is the so-called "scaled dot-product" attention, which takes the form
atj ((W
exp(a.))
s
aij ΣS= exp(ar))
t
W 8y
(1)
Vd
j=1
where WV, WK E Rd.xd and WQ E Rdxx are learnable weight matrices, usually called the "value," "key," and "query" weight matrices, respectively. Usually multiple so-called "attention heads" with independent parameter matrices implement several parallel computations of (1), with the Cartesian product (vector concatenation) of several d-dimensional head outputs forming the final output f.. Usually the unnormalized dzy" is are called attention scores or attention logits, and the normalized a:y' 's are called attention weights.
In this paper, we restrict our focus to the dot-product formulation of attention shown in (1). Several other alternative forms of attention that perform roughly the same function (i.e., mapping from Rd Rd to R) have been proposed (Bahdanau et al., 2015; Luong al., 2015; Veličković et al., 2018; Battaglia et al., 2018, etc.) but the dot-prr formulation the Transformer is by far the most popular.
2.2 KERNEL METHOOS AND GENERALIZATIONS OF KERNELS
Kernel methods (Schölkopf& Smola, 2002; Steinwart & Christmann, 2008, etc.) are a classic and powerful class of machine learning methods. The key component of kernel methods are the namesake
Often, the source and target sets are taken to be the same, t; Vi. This instance of attention is called self attention.
2

---

Under review as a conference paper at ICLR 2021
kernel functions, which allow the efficient mapping of imput data from low--ooeeessseee diw-emmnnsionll data domain, where linear solutions to problems like classification or regression may not be possible, to a high- or dnfinie-dimensionn embedding domain, where linear solutions can be found.
Given two nonempty sets X and V. a kernel function A is a continuous function k X x 3 + R. In the next few sections, we will review the classic symmetric and positive (semi-) definite, Mercer, kernels, then discuss more general forms.
2.2.1 SYMMETRIC AND POSITIVE SEMIDEFINITE (MERCER) KERNELS
If X v, and for all 23 E X = y, particular kernel i has the properties
symmetry: k(ar, xz) = K())
(2a)
positive (semi-) definiteness: c¹ Ke VCE i,j 1,
EEN
(2b)
where K in (2b) is the Gram matrix, defined as Kú = ke(2,, 2.)) then ii is said be a Mercer kernel. For Mercer kernels, it is well-known that, among other facts, (i) we can define Hilbert space of functions on X. denoted Hi (called the reproducing kernel Hilbert space, or RKHS, associated with the reproducing kernel k), (ii) Hy has for each æ (continuous) unique element 82 called a point evaluation functional, with the property f(x) = 62 62) of E Hax (iii) k has the so-called reproducing property, (f, k(Z, -)) f(z) vf E Hys where (..)H. Hre is the inner product on H... and (iv) can define a "feature map" Φ - FH. where Fiz is another Hilbert space sometimes called the feature space, and k( y) (T (x). ((v)) (where (r is the inner product associated with Fx). This last point gives rise to the kernel trick for RKHS's.
From machine learning and optimization perspective, kernels that are symmetric and positive (semi-) definite (PSD) are desirable because those properties guarantee that empirical-risk-mmnnniaa kernel learning problems like support vector machines (SVMs). Gaussian processes, etc. are convex. Convexity gives appealing guarantees for the tractability of learning problem and optimality of solutions.
2.2.2 LEARNING WITH NON-MERCER KERNELS
Learning methods with non-Mercer kernels, or kernels that relax the assumptions (2), have been studied for some time. One line of work (Lin & Lin, 2003; Ong et al., 2004; Chen & Ye, 2008; Luss & D' aspremont, 2008; Alabdulmohsin et al., 2015; Loosli et al., 2016; Oglic & Gärtner, 2018; 2019, etc.) has focused on learning with symmetric but indefinite kernels, i.e., kernels that do not satisfy (2b). Indefinite kernels have been identified reproducing kernels for so-called reproducing kernel Kreīn spaces (RKKS's) s since Schwartz (1964) and Alpay (1991).
Replacing Mercer kernel in a learning problem like SVM with an indefinite kernel makes the optimization problem nonconvex in general (as the kernel Gram matrix K is no longer always PSD). Some early work in learning with indefinite kernels tried ameliorate this problem by modifying the spectrum of the Gram matrix such that it again becomes PSD (e.g.. Graepel et al., 1998; Roth al., 2003; Wu al., 2005). More recently, Loosli et al. (2016): Oglic & Gärtner (2018), among others, have proposed optimization procedures to learn in the RKKS directly. They report better performance on some learning problems when using indefinite kernels than either popular Mercer kernels or spectrally modiifee indefinite kernels, suggesting that sacrificing convexity can empirically give performance boost. This conclusion of course reminiscent of the concurrent experience of deep neural networks, which are hard to optimize due to their high degree of non-convexity, yet give superior performance to many other methods.
Another line of work has explored the application of kernel methods to learning in more general Banach spaces, i.e., reproducing kernel Banach spaces (RKBS's) (Zhang et al., 2009). Various constructions to serve as the reproducing kernel for Banach space (replacing the inner product of an RKHS) have been proposed, including semi-inme cami-inner products (Zhang et al., 2009), positive-definity bilinear forms via a Fourier transform construction (Fasshauer et al., 2015), and others (Song et al., 2013; Georgiev et al., 2014, etc.). In this work, we consider RKBS's whose kernels may be neither symmetric nor PSD. A definition of these spaces is presented next.
3

---

Under review as a conference paper at ICLR 2021
3 GENERAL REPRODUCING KERNEL BANACH SPACES
Recently, Georgiev et al. (2014), Lin et al. (2019), and Xu & Ye (2019) proposed similar definitions and constructions of RKBS's and their reproducing kernels meant encompass prior definitions. In this paper, we adopt fusion of the definitions and attempt to keep the notation as simple as possible be sufficient for our purposes.
Definition 1 (Reproducing kernel Banach space (Xu & Ye, 2019, Definition 2.1; Lin et al., 2019, Definitions 1.1 1.2; Georgiev al., 2014)). Let X' and y be nonempty sets, K. measurable function called a kernel, K : X' x 3 - R, and Bx and By Banach spaces of real measurable functions on X' and y/ respectively. Let (.,')xx xBy Bx x By + R be a nondegenerate bilinear mapping such that
x(xx,) E By
for all x E X; for all x E X Bxi
(3a)
(f. () Bx = f(x)
(3b)
x(:,)) E Bx
for all y E y; and
(3c)
(x(-, v), g) B, =(v) for all y E V,9 E By-
(3d)
Then, Bx and By are a pair of reproducing kernel Banach spaces (RKBS's) on X and y, respectively, and R is their reproducing kernel.
Line (3a) (resp. (3c)) says that, if we take K, function of two variables æ E X and y E V, and fix x (resp. y), then we get a function of one variable. This function of one variable must be element of By (resp. Bx). Lines (3b) and (3d) are the reproducing properties of K.
For our purposes, it will be useful to extend this definition include "feature map" characterization similar to the one used in some explanations of RKHS's (Schölkopf & Smola, 2002, Chapter 2).
Definition (Feature maps for RKBS's (Lin al., 2019, Theorem 2.1; Georgiev et al., 2014)), For a pair of RKBS's as defined in Definition I, suppose that there exist mappings 4x X - Fx, By y - Fy, where Fx and Fy are Banach spaces we will call the feature spaces, and nondegenerate bilinear mapping (,, Fx Fx x Fy + R such that
<(x, = ( (z),,
for all x E X, E V..
(4)
In this case, the spaces 3x and By can be defined as (Xu & Ye, 2019; Lin et al., 2019)
Bx fo fo: x R: fo
FxxFy i Fy,
(5a)
By {gu : (3) (u. By ( FxXF, tu Fx,BE
(5b)
Remark 1. We briefly discuss how to understand the spaces given by (5). Consider (5a) for example. is a space real-valued functions of one variable x, where the function is also parameterized by a v. Picking
Fy in (5a) defines manifold of functions in Bx This manifold of functions with fixed varies with the function xx Evaluating a function fa in this manifold at point & is defined by taking the bilinear product of 4 (x) and the chosen v. This also means that we can combine (4) and (5) to say
x(xx v) = (1xx Dy(()) FxXFy (fox(z)) (1ox())))0 (v) B Xyy for all x E X, E y.
(6)
Remark 2.
If xx))x and (y) can be represented countable
of real-valued measurable
functions, for ( and (oy(v)ekeN for (Øx)e X + R and (øy)e : y + R (i.c., Fy C IlEN E); and () FxxFF EtEn 42d8 for E Fx E Fy: then the "feature map" construction, whose notation we borrow from Lin et al. (2019), corresponds to the "generalized Mercer kernels" of Xu & Ye (2019).
4 DOT-PRODUCT ATTENTION AS AN RKBS KERNEL
We now formally state the formulation for dot-product attention as an RKBS learner. Much like with RKHS's, s, for given kernel and its associated RKBS pair, the feature maps (and also the bilinear mapping) are not unique. In the following, we present a feature map based on classic characterizations of other kernels such RBF kernels (e.g., Steinwart et al. (2006)).
4

---

Under review as a conference paper at ICLR 2021
The (scaled) dot dot-product attention calculation of (1) is reproducing kernel for an RKBS in the sense of Definitions 1 and 2, with the input sets X and y being the vector spaces from which the target elements {til tú E R& and source elements {s, }=)=:: R are drawn, respectively; the feature maps
Proposition 1.
nl
1/2 d
Σ 2x(()) Pi-Pat tptttttee
d=
(g)) )c
(7a)
P1-p2!... .......pal paa
nl Pilpp!....Pp
1/2
8y(8)
Σ
d 1/1
(7b)
n=0 P2t"rtuu
t=1
where qe is the Eth element of q W ke is the lth element of k WK WO Rdxd. WK E Rdxd, with d S d,, de and rank(WQ) = rank W*) d; the bilinear mapping (Dx(t), ()())
(x)(t) (sy(s); and the Banach spaces
Bx = (x(()) = =exp ((W9t)Tk/Vd) k kE
(8a)
By = (g((s) = exp (q (WWKs)/VV) ; FE
(8b)
with the "exponentiated query-key kernel."
(W2L)TWWA
k(t, = ()x()))))((t
= (fx)))) BxxB, = exp
(9)
Vd
the associated reproducing kernel.
The proof of Proposition straightforward and involves verifying (9) by multiplying the two infinite series in (7), then using the multinomial theorem and the Taylor expansion of the exponential.
In the above and when referring to Transformer-type models in particular rather than RKBS's in general, we use f, 8, q. and & for x, V, and v, respectively, to draw the connection between the elements of the RKBS's 's and the widely-used terms "target," "source," "query," and "key."
The rank requirements on W and W mean that span (1 (t), span(( (8), v)) = Fy. This in turn means that the bilinear mapping is nondegenerate.
X)) Fx and
Remark 3. Now that we have an example of a pair of RKBS's, s,, we can make more concrete some of the discussion from Remark 1. Examining (8a), for example, we that when select a k Fy. we define manifold of functions in Bx where is fixed, but Wº can vary. Similarly, selecting a q Fx defines a manifold in By. Selecting an element from both Fx and Fy locks us into one element each from Xx and By, which leads to the equality in (6).
Remark 4. Examining (9), we can see that the element drawn from Fy that parameterizes the element of Ex, as shown in (8a), is a function of Φy (and vice-versa for (8b)). This reveals the exact mechanism in which the Transformer-tyne attention computation is a generalization of the RKBS's considered by Fasshauer et al. (2015), Lin et al. (2019), Xu Ye (2019), etc., for applications like SVMs, where one of these function spaces is considered fixed.
Remark 5. Since the feature maps define the Banach spaces (5), the fact that the parameters WQ and W K are learned implies that Transformers learn parametric representations of the RKBS's themselves. This is in contrast to classic kernel methods, where the kernel (and thus the reproducing space) is usually fixed. In fact, in Theorem 2 below, we show that (a variant of) the Transformer architecture can approximate any RKBS mapping.
Remark 6. The symmetric version of the exponentiated dot product kernel is known to be re- producing kernel for the so-called Bargmann space (Bargmann, 1961) which arises in quantum mechanics.
Remark 7. Notable in Proposition is that we define the kernel of dot- not-product attention as including the exponential of the softmax operation. The output of this operation is therefore not the attention scores aij but rather the unnormalized attention weights, ā.j = aij E, Oij-- Considering the exponential as a part of the kernel operation reveals that the feature spaces for the Transformer are in fact infinite-de dimensional in the same sense that the RBF kernel is said to have seffnite-dimnssin feature space. In Section 6, we find empirical evidence that this infinite dimensionality may be partially responsible for the Transformer's effectiveness.
5

---

Under review as a conference paper at ICLR 2021
5 TRANSFORMERS AS KERNEL LEARNERS
5.1 THE BINARY RKBS LEARNING PROBLEM AND ITS REPRESENTER THEOREM
Most kernel learning problems take the form of empirical risk minimization problems. For example. if we had a learning problem for a finite dataset (I1, 21)......... .............................. (Iyu &n), T; E X, 2 E IR and wanted to learn a function f : + R in an RKHS His the learning problem might be written as
24, 1 + (x + +
f = arg min JEH,
(10)
where L X' X - R is a convex loss function, R [0. oo) + R is a strictly increasing regularization function, and À is scaling constant. Recent references that consider learning in RKBS's (Georgiev et al., 2014; Fasshauer et al., 2015; Lin et al., 2019; Xu & Ye, 2019) consider similar problems to (10), but with the RKHS H replaced with an RKBS.
The kernel learning problem for attention, however, is different from (10) in that, as we discussed in the previous section, need to predict response 2ij (i.e., the attention logit) for every pair (t,, 8z). This motivates generalization of the classic class of kernel learning problems that operates on pairs of input spaces. We discuss this generalization now.
Definition 3 (Binary kernel learning problem regularized empirical risk minimization). Let X and y be nonempty sets, and Bx and By RKBS's on X' and V, respectively. Let (.,'),x x Bx x By + R be a bilinear mapping on the two RKBS's. Let 2x : X + Fx and By y - FF be fixed feature mappings with the property that (#x( (y(())) FxxFy (foy(e) (0x(2) By
Say fII,..., Fn....,,p,lll 1 J. Fg E X. fyI...... Yn,, J. yj E V. and {zzg leighi=........ ay,,.., 2g E R is finite dataset where response 2ij is defined for every (i.j) pair of x; and yz- Let L
X x y' x x - IR be loss function that convex for fixed (Iz Vj, ). and Rx : (0, 00) - TR and Ry [0, 20) - IR be convex, strictly increasing regularization functions.
binary empirical risk minimization kernel learning problem for learning on a pair of RKBS's takes the form
f.
arg min feBx.9EBy
Tii (i: Zigi ( (exxx)))) Bx BxxBy)
my
(11)
+ >xxxx(1 + Ay (o
where Ax and ny are again scaling constants.
Remark 8. The idea of a binary kernel problem that operates over pairs of two sets is not wholly new: there is prior work both in the collaborative filtering (Abernethy et al., 2009) and tensor kernel method (Tao et al., 2005; Kotsia & Patras, 2011; He et al., 2017) literatures. Our problem and results new in the generalization to Banach rather than Hilbert spaces: as prior work in the RKBS literature (Micchelli al., 2004; Zhang& & Zhang, 2012; Xu & Ye, 2019, etc.) notes, RKBS learning problems are distinct from RKHS ones in their additional nonlinearity and/or nonconvexity. An extension of binary learning problems to Banach spaces is thus motivated by the Transformer setting, where kernel method is in context of a nonlinear and nonconvex deep neural network, rather than as a shallow learner like an SVM matrix completion. For more discussion, see Appendix A.
Virtually all classic kernel learning methods find solutions whose forms are specified by so-called representer theorems. Representer theorems state that the solution to a regularized empirical risk minimization problem over a reproducing kernel space can be expressed as a linear combination of evaluations of the reproducing kernel against the dataset. Classic solutions to kernel learning problems thus reduce to finding the coefficients of this linear combination. Representer theorems exist in the literature for RKHS's (Kimeldorf & Wahba, 1971; Schölkopf et al., 2001; Argyriou et al., 2009), RKKS's 's (Ong et al., 2004; Oglic& & Gärtner, 2018), and RKBS's (Zhang et al., 2009; Zhang & Zhang, 2012; Song et al., 2013; Fasshauer et al., 2015; Xu & Ye, 2019; Lin et al., 2019).
Fasshauer et al. (2015, Theorem 3.2), Xu & Ye (2019, Theorem 2.23), and Lin et al. (2019, Theorem 4.7) provide representer theorems for RKBS learning problems. However, their theorems only deal

---

Under review as a conference paper at ICLR 2021
with learning problems where datapoints come from only one of the sets which the reproducing kernel is defined (i.e., only X' but not )), which means the solution sought an element of only one of the Banach spaces (e.g.. f X + R. Bx). Here, state and prove theorem for the more-relevant-tor tateevvannttt--Traofoomeee binary case presented in Definition 3.
Theorem 1. Suppose we have a kernel learning problem of the form (11). Let K X y - IR be the reproducing kernel of the pair of RKBS's Bx and By satisfying Definitions and 2. Then, given some conditions on Bx and By (see Appendix B), the regularized empirical risk minimization problem (11) has a unique solution pair (f*,"") with the property that
df) = - ())(
((9)) = Σ Mg)(-11))-
(12)
j=1
where u(f) (resp. ((9) denotes the Gáteaux derivative of the norm of (resp. with the convention that (0) 0, and where Ei. Cj E IR
Proof. See Appendix B.
5.2 A NEW APPROXTMATE KERNEL LEARNING PROBLEM AND UNIVERSAL APPROXIMATION THEOREM
The downside of finding solutions to kernel learning problems like (10) (11) of the form (12) as suggested by representer theorems is that they scale poorly to large datasets. It is well-known that for RKHS learning problem, finding the scalar coefficients by which multiply the kernel evaluations takes time cubic in the size of the dataset, and querying the model takes linear time. The most popular class of approximation techniques are based the so-called Nyström method, which constructs a low-rank approximation of the kernel Gram matrix and solves the problem generated by this approximation (Williams & Seeger, 2001). recent line of work (Gisbrecht & Schleif, 2015; Schleif & Tino, 2017; Oglic & Gärtner, 2019) has extended the Nyström method to RKKS learning.
In this section, we characterize the Transformer learning problem as a new class of approximate kernel methods- "distillation" approach, one might call it. We formally state this idea now.
Proposition 2 (Parametric approximate solutions of binary kernel learning problems). Consider the setup of binary kernel learning problem from Definition 3. We want find approximations the solution pair (f", "f",")). In particular, we will say we want an approximation R X x y - R such that
R(x, y) x (f ( xx for all x X and E E.
(13)
Comparing (13) to (6) suggests solution: to learn a function & that approximates k. In particular, (6) suggests learning explicit approximations of the feature maps. i.e.
R(x,8) 8) = (2xx2))4y(x)) by(()) Fxx33'
In fact, it turns out that the Transformer query-key mapping (1) does exactly this. That is. while the Transformer kernel calculation outlined Propostion is fiiie-dimensional it can in fact approximate the potentially infinite-dimensios optimal solution (f" characterized in Theorem 1. This fact proved next.
Theorem 2. Let X TR and y C B.d,, be compact; X,8 E y; and let qe X - R and k2 : y + R for E = 1 1....,d be two-layer neural networks with m hidden units. Then, for any continuous function F X y IK and >> there are integers m, d > 0 such that
F(t, s)
Σ qe(t)ke(s) <c toraltt
(14)
Proof. See Appendix C.
We now outline how Theorem relates to Transformers. If we concatenate the outputs of the two-layer neural networks {g: id and 1d into d-dimensional vectors q Re + Rd and k dd Rdd then the dot product T k(()) denoted by the in (14) can approximate any
7

---

Under review as a conference paper at ICLR 2021
real-valued continuous function on X' V Minus the usual caveats in applications of universal approximation theorems (i.e., in practice the output elements share hidden units rather than having independent ones), this dot product is exactly the computation of the attention logits agj. ie., F(t, s) x log x(t, s) for the F in (14) and the R in (9) up scaling constant vd.
Since the exponential mapping between the attention logits and the exponentiated query-key kernel used in Transformers then we can use a Transformer's dot-product attention to approximate the optimal solution to any RKBS solution arbitrarily well.
one-to-one mapping. if take F(t, s) log (fay(s) (t) Bx xBy"
The core idea of an attention-based deep neural network is then to learn parametric representations of qe and k2 via stochastic gradient descent. Unlike traditional representer-theoree-bbanl functions, training time of attention-based kernel machines like deep Transformers (generally, but with no guarantees) scale sub-cubically with dataset size, and evaluation time stays constant regardless of dataset size.
learned
IS THE EXPONENTIATED DOT PRODUCT ESSENTIAL TO TRANSFORMERS?
Table 1: Test BLEU scores for Transformers with various kernels on machine translation (case- sensitive sacreBLEU). Values are mean + std. dev over training runs with different random seeds.
EDP
RBF
L2 Distance
Quadratic
IWSLT14 DE-EN
30.41 + 0.03
30.32 0.22
19.45 + 0.16
30.84 + 0.27
29.56 0.19
WMT14 EN-FR
0.08 0.25
28.41
34.51
0.35
EDP = Exponentiat dot product; El Exponentiated intersection kernel
We study modifications of the Transformer with several kernels used in classic kernel machines. We train on two standard machine translation datasets and two standard sentiment classification tasks. For machine translation, IWSLT14 DE-EN is relatively small dataset. while WMT14 EN-FR is a considerably larger one. For sentiment classification, we consider SST-2 and SST-5, We retain the standard asymmetric query and key feature mappings, i.e., q W and k W and only modify the kernel κ : Rdd x Rid >> IR RR In the below, T >> O and E TR. are per-head learned scalars.
Our kernels of interest
1. the (scaled) exponentiated dot product (EDP), x(g, exp(2" Transformer kernel;
(f k/vd), i.e., the standard
2. the radial basis function (RBF) kernel, k(q, t) exp(1I 7/Va(q k) 1)))2) where ||. ll2 is the standard 2-norm. is well-known that the RBF kernel a normalized version of the exponentiated dro-pr,, with the normalization making it translation translation-invariant;
3. the vanilla L2 distance, <<g, t) = r/vallq q kl|2;
4. an exponentiated version of the intersection kernel, x(q, ex min(ge, ke)). The symmetric version of the intersection kernel was popular in kernel machines for computer vision applications (Barla et al., 2003; Grauman Darrell, 2005; Maji et al., 2008, etc.), and is usually characterized as having associated RKHS that is subspace of the function space 2 (i.e., it aninite-dimensione in the sense of having a feature space of continuous functions, opposed to the
exp(Ei=
infinite series of the EDP and RBF kernels);
5. quadratic polynomial kernel, k(q, k) = (1/vaq k + 7)2.
Full implementation details are provided in Appendix D.
Results for machine translation are presented in Table 1. Several results stand out. First, the exponentiated dot product, RBF, and exponentiated intersection kernels, which are said to have dinent--immnsionall feature spaces, indeed do perform better than kernels with lower-dimensional feature maps such as the quadratic kernel. In fact, the RBF and EDP kernels perform about the same, suggesting that deep Transformer may need the
that makes the RBF
8

---

Under review as a conference paper at ICLR 2021
Table 2:
Test accuracies for Transformers with various kernels sentiment classification. Values mean + std. dev over 5 training runs with different random seeds.
EDP
RBF
L2 Distance
El
Quadratic
SST-2 (%)
76. 70 + 0.36 39.44 + 0.47
74.24 + 0.39
76. + 0.67 39.44 + 1.33
74.90 + 1.32
76.24 = 0.65 39.34 + 0.80
SST-5 (%)
39.04 + 0.62
37.74 + 0.48
EDP= Exponentiated dot product; EI Exponentiated intersection kernel
kernel preferred to the EDP in classic kernel machines. Intriguingly, the (unorthodox) exponentiated intersection kernel performs about the same as the two than the EDP and RBF kernels on IWSLT14 DE-EN, but slightly worse on WMT14 EN-FR. As mentioned, the EDP and RBF kernels have feature spaces of infinite series, while the intersection kernel corresponds to a feature space of continuous functions. On both datasets, the quadratic kernel performs slightly worse than the best infmite-dimensional kernel, while the L,2 distance performs significantly worse.
Results for sentiment classification appear in Table 2. Unlike the machine translation experiments, the kernels do not appear strictly superior to the unite-dimensiona ones on this task. In fact, the apparent loser here is the exponentiated intersection kernel, while the 1.2 distance, which performed the worst on machine translation, is within a standard deviation of the top-performing kernel. Notably, however, the variance of test accuracies on sentiment classification means that it is impossible to select statistically significant "best" on this task. It is possible that the small inter-kernel variation relates to the relative simplicity of this problem (and relative smallness of the dataset) vs. machine translation: perhaps Transformer-level performance on this learning problem.
dimenioad feature space is not needed to obtain
It is worth noting that the exponentiated dot product kernel (again, the standard Transformer kernel) a consistent high performer. This may be experimental evidence for the practical usefulness of the universal approximation property they enjoy (c.f. Theorem 2).
The relatively small yet statistically significant performance differences between kernels is reminiscent of the same phenomenon with activation functions (ReLU, ELU, etc.) for neural nets. Moreover, the wide inter-kernel differences in performance for machine translation, compared against the much smaller performance differences on the SST sentiment analysis tasks, demonstrates an opportunity for future study on this apparent task- and dataset-dependenn As a whole, these results suggest that kernel choice may be an additional design parameter for Transformer networks.
7 CONCLUSION
In this paper, drew connections between classic kernel methods and the state-of-the-art Trans- former networks. Beyond the theoretical interest in developing new RKBS representer theorems and other kernel theory, we gained new insight into what may make Transformers work. Our experimental results suggest that the infinite dimensionality of the Transformer kernel makes it good choice in application, similar to how the RBF kernel is the standard choice for e.g. SVMs. Our work also reveals new avenues for Transformer research. For example, choice of Transformer kernel acts as similar design choice as activation functions in neural net design. Among the new open research questions are (1) whether the exponentiated dot-product should be always preferred, or if different kernels are better for different tasks (c.f. how GELUs have recently become very popular replacements for ReLUs in Transformers), (2) any relation between vector-valuee kernels used for structured prediction (Álvarez et al., 2012) and, e.g., multiple attention heads, and (3) the extension of Transformer- deep kernel learners to oon-Euclidean data (using, e.g., graph kernels or kernels on manifolds).
experimental results suggest that
REFERENCES
Jacob Abernethy, Francis Bach, Theodoros Evgeniou, and Jean-Philippe Vert. A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization. Journal of Machine Learning Research, 10:803-824 March 2009.

---

Under review as a conference paper at ICLR 2021
N. L. Akhiezer and M. G. Krein. Some Questons in the Theory of Moments. Number 2 in Translations of Mathematical Monographs. American Mathematical Society, Providence, RI, 1962. ISBN 18118-1552-00
Ibrahim Alabdulmohsin, Xin Gao, and Xiangliang Zhang. Support vector machines with indefinite kernels. In Proceedings of the Sixth Asian Conference Machine Learning, volume 39, pp. 32 47. PMLR, 2015.
Daniel Alpay. Some Remarks on Reproducing Kernel Krein Spaces. Rocky Mountain Journal of Math- ematics, 21(4): 1900)11891-2555 December 1991. ISSN 0035-7596. doi: 1e.10...16//// //16/m 18 1072903.
Mauricio A. Álvarez, Lorenzo Rosasco, and Neil D. Lawrence. Kernels for Vector-Valued Functions: Review. Foundations and Trends@ in Machine Learning, 195):195-266, 2012. ISSN 1935-8237, 1935-8245. doi:10. 1561/22000000036
Andreas Argyriou, Charles A Micchelli, and Massimiliano Pontil. When There a Representer Theorem? Vector Versus Matrix Regularizers. Journal of Machine Learning Research, 10:2507- 2529, November 2009.
Raman Arora, Peter Bartlett, Poorya Mianjy, and Nathan Srebro. Dropout: Explicit Forms and Capacity Control. arXiv:2003.03397 [cs, stat], March 2020.
Jean-Gabriel Attali and Gilles Pagès. Approximations of Functions by a Multilayer Perceptron: A New Approach. Neural Networks, 1066) August 1997. ISSN 08936080. doi:10. 1016/0993- 6080(97)00010-55
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural Machine Translation by Jointly Learning to Align and Translate. In International Conference on Learning Representations, 2015.
Maria-Florina Balcan, Avrim Blum, and Nathan Srebro. A theory of learning with similarity functions. Machine Learning, 72(1-2):99-112, August 2008. ISSN 0885-6125, 1573-0565. doi: 10i:10.11000 11111000007/111994-00----5533150
Pierre Baldi and Peter Sadowski. Understanding Dropout. In Advances in Neural Information Processing Systems, volume 26, pp. 2814-2822. Curran Associates, Inc., 2013.
V. Bargmann. On a Hilbert space analytic functions and an associated integral transform part I. Communications Pure and Applied Mathematics, 14(3):187-214, August 1961. ISSN 00103640, 10970312, doi: 10::10.11000 1002/..p... 3160140300 40303.
A. Barla, F. Odone, and A. Verri. Histogram intersection kernel for image classification. In Proceedings 2003 International Conference on Image Processing (Cat. No.03CH37429), volume 2. pp. 111-513-16. Barcelona, Spain, 2003. IEEE. ISBN 978-0-7803-7750-9 doi: 10910.0.09// 12.....29000..1.94.... 1247294.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song. Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv: vrXiv:1806.01) 0006.0066..6666 [cs, stat], June 2018
Garrett Birkhoff. Orthogonality in linear metric spaces. Duke Mathematical Journal, 1(2):169-172. June 1935. ISSN 0012-7094, 1547-7398. doi: 10..111555002227794433..00
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language Models are Few-Shot Learners. arXiv:2005. 14165 [cs], June 2020.
10

---

Under review as a conference paper at ICLR 2021
Jianhui Chen and Jieping Ye. Training SVM with indefinite kernels. In Proceedings of the 25th International Conference on Machine Learning ICML '08, pp. 136-143, Helsinki, Finland, 2008. ISBN 978- 1------66582----
James A. Clarkson. Uniformly convex spaces. Transactions of the American Mathematical Society, 40(3):396-398 396, March 1936. ISSN 0002-9947. doi: 110..000000/000099999---100090 1501880-4
rean-Baptiste Cordonnier, Andreas Loukas, and Martin Jaggi. On the Relationship between Self- Attention and Convolutional Layers. In International Conference Learning Representations, 2020.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, December 1989. ISSN 1435-568X. 1007://0000/// 274.
Mahlon M. Day. Reflexive Banach spaces not isomorphic uniformly convex spaces. Bulletin of the American Mathematical Sociery, 47(44:313-318, April 1941. ISSN 0002-9900 9904. doi: 1090/S0002-
9904-1941-07451-3.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, volume 1, pp. 4171-4186, Minneapolis, Minnesota, June 2019.
Ivar Ekeland and Roger Témam. Conver Analysis and Variational Problems, volume 28 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, January 1999. ISBN
978-0-89871 149800 978- 178---6117--08-8 doi: 1tt:10..13770
Ivar Ekeland and Thomas Turnbull. Infinite-Dimen Dimensional Optimization and Convexity. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, 1983, ISBN 978-0-226-19987-1
1e..0-222-11988--
Gregory E. Fasshauer, Fred J. Hickernell, and Qi Ye. Solving support vector machines in reproducing kernel Banach spaces with positive definite functions. Applied and Computational Harmonic Analysis, 38(1):115-133) January 2015. ISSN 1063-5203. 10.:10.100 1et::0001166jaaee 1016666..ccc..2222 200....ach.221.3...0
Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Newral Networks, 2(3):183-192) January 1989. ISSN 08936080. 1001100000600899-000000099)0
8.
Pando G. Georgiev, Luis González, and Panos M. Pardalos. Construction of Pairs of Reproducing Kernel Banach Spaces. In Vladimir F. Demyanov, Panos M. Pardalos, and Mikhail Batsyn (eds.), Constructive Nonsmooth Analysis and Related Topics, pp. 39-57. Springer New York, New York, NY, 2014. ISBN 978- 1-441--86111---- 100:100.0077/78-11-1 1-117788----41---1----222
Andrej Gisbrecht and Frank-Michael Schleif. Metric and non-metric proximity transforma- tions at linear costs. Neurocomputing, 167:643-657, November 2015. ISSN 09252312. hww.::0111.mmmmmmm011.5...55
Thore Graepel, Ralf Herbrich, Peter Bollmann-Sdore and Klaus Obermayer. Classification on Pairwise Proximity Data. Advances in Neural Information Processing Systems, volume 11, pp. 438 444, 1998.
K. Grauman and T. Darrell. The pyramid match kernel: Discriminative classification with sets of image features. In Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, pp. 1458-1465 Vol. 2, Beijing, China, 2005. IEEE. ISBN 978-0-7695-2334-7.
1oi: 100.111100///CC22200002222
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity Mappings in Deep Residual Networks. In European Conference on Computer Vision, pp. 630-645, July 2016.
Lifang He, Chun Ta Lu, Guixiang Ma, Shen Wang, Linlin Shen, Philip S Yu, and Ann B Ragin. Kernelized Support Tensor Machines. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 1451. PMLR, July 2017.
11

---

Under review as a conference paper at ICLR 2021
David P. Helmbold and Philip M. Long. Surprising properties of dropout in deep networks. The Journal of Machine Learning Research, 18(1):7284-3311 January 2017. ISSN 1532-4435.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359 366, January 1989. ISSN 0893-6080.
doi: 10. 10116/0893--008889999002222
Robert C. James. Orthogonality and Linear Functionals in Normed Linear Spaces. Transactions of the American Mathematical Society, 61(2):255-292, 1947. ISSN 0002-9947, do:110.2307/1990222..
Mandar Joshi, Dangi Chen, Yinhan Liu. Daniel S. Weld, Luke Zettlemoyer, and Omer Levy. SpanBERT: Improving Pre-training by Representing and Predicting Spans. Transactions of the Association for Computational Linguistics, 8:64-77, January 2020. ISSN 2307-387X. doi: 1oi:10.1162/tall a_00300.
George Kimeldorf and Grace Wahba. Some results on Tchebycheffian spline functions. Jour- nal of Mathematical Analysis and Applications, 33(1):82-95, January 1971. ISSN 0022-247X. doi: 1at110011111 110.1101166000222777719900000000
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations, 2015.
Irene Kotsia and Ioannis Patras. Support Tucker Machines. In CVPR 20/ pp. 633-640, Colorado Springs, CO, USA, June 2011. IEEE ISBN 278-1-4577-0399-22. 1oi: 100.1110//VPP.2000 1.55999666..
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. ALBERT: Lite BERT for Self-supervised Learning of Language Representations. In International Conference on Learning Representations, 2020.
Hsuan-Tices Lin and Chih-Jen Lin. A Study on Sigmoid Kernels for SVM and the Training of non-PSD Kernels by SMO-type Methods. Technical report, National Taiwan University, Taipei, Taiwan, 2003.
Rongrong Lin, Haizhang Zhang, and Jun Zhang. On Reproducing Kernel Banach Spaces: Generic Definitions and Unified Framework of Constructions. arXiv: [cs, math, stat], January 2019.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: Robustly Optimized BERT Pretraining Approach. arXiv:1907.11660 11692 [cs]. July 2019.
Gaëlle Loosli, Stéphane Canu, and Cheng Soon Ong. Learning SVM in Krein Spaces. IEEE Transactions on Puttern Analysis and Machine Intelligence, 38(6): 204-1216, June 2016. ISSN 1939-3539. doi: 10. 209 5.477833..
Yiping Lu, Zhuohan Li, Di He, Zhiqing Sun, Bin Dong, Tao Qin, Liwei Wang, and Tie-Yan Liu. Understanding and Improving Transformer From a Multi-Particle Dynamic System Point of View. 022702 [cs, stat], June 2019.
Minh-Thang Luong, Hieu Pham, and Christopher D. Manning. Effective Approaches Attention- based Neural Machine Translation. arXiv:1508.04400 04025 [cs], August 2015.
Ronny Luss and Alexandre D' d'aspremont. Support Vector Machine Classification with Indefinite Kernels. In Advances Neural Information Processing Systems, volume 20, pp. 953-960, 2008
Subhransu Maji, Alexander C. Berg, and Jitendra Malik. Classification using intersection kernel support vector machines is efficient. In 2008 IEFE Conference on Computer Vision and Pat- tern Recognition, pp. 1-8, Anchorage, AK, USA, June 2008. IEEE. ISBN 978-1-4244-2242-5 doi: 1oi:10.1109/00 11w.1..11///..P.22000 2008 4587630.
Robert E. Megginson. An Introduction to Banach Space Theory, volume 183 of Graduate Texts in Mathematics. Springer New York, New York, NY, 1998. ISBN 978-1-4612-1 1-4612-6835-2 978-1- 0603-3. doi: 10. 1077977-114461-0660
12

---

Under review as a conference paper at ICLR 2021
Charles A. Micchelli, Massimiliano Pontil, John Shawe-Taylor Taylor, and Yoram Singer. A Function Representation for Learning in Banach Spaces. Learning Theory, volume 3120, pp. 255-269. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. ISBN 978-3-540-2228222 978-3-540-278199
1. doi:10. (007/978-3-540-277)
Dino Oglic and Thomas Gärtner. Learning in Reproducing Kernel Krein Spaces. In Proceedings of the 35th International Conference Machine Learning, volume 80, pp. 3859-3867. PMLR, 2018.
Dino Oglic and Thomas Gärtner. Scalable Learning in Reproducing Kernel Krein Spaces. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 4912- 4921. PMLR, 2019.
Akifumi Okuno, Tetsuya Hada, and Hidetoshi Shimodaira. A probabilistic framework for multi-view feature learning with many-to-many associations via neural networks. In Proceedings of the 35th International Conference Machine Learning. volume 80, pp. 3888-3897. PMLR, June 2018.
Cheng Soon Ong, Xavier Mary, Stéphane Canu, and Alexander J. Smola. Learning with non-positive kernels. In Proceedings of the st International Conference on Machine Learning, pp. 639-646, Banff, Alberta, Canada, 2004. ACM Press. 16::10.1145/1115330.0000
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli, Fairseq: fast, extensible toolkit for sequence modeling. Proceedings of NAACL-HLL 2019: Demonsirations, 2019, doi: 10..11665/////1119000000
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorcc: Imperative Style, High-Performant Deep Learning Library. In Advances in Neural Information Processing Systems, volume 32, pp. 8026-8037. Curran Associates, Inc., 2019.
Matt Post. A Call for Clarity in Reporting BLEU Scores. Proceedings of the Third Conference on Research Pupers, pp. 186-191, Belgium, Brussels, 2018. Association for Computational Linguistics. doi: 10. 1
Machine Translation:
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language Models are Unsupervised Multitask Learners. Technical report, OpenAT, 2018.
Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jonathon Shlens. Stand-Alone Self-Attention in Vision Models. arXiv: 9066009009 [cs), June 2019.
V. Roth, Laub, M. Kawanabe, and J.M. Buhmann. Optimal cluster preserving embedding of nonmetric proximity data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25 (12):1540-1551 December 2003. ISSN 1939-3539. doi:10.1 101/110MMIL...M 2003. 1251147.
Frank-Michael Schleif and Peter Tino. Indefinite Core Vector Machine. Pattern Recognition, 71: 187-195, November 2017. ISSN 00313203. doi:10. pttl://.pacco........ 2011.0..017.06.003
Bernhard Schölkopf and Alexander Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, 2002. ISBN 978-0-262-25693-3.. doi: 1ttp:///5511mmmppps///1/.5...00
Bernhard Schölkopf, Ralf Herbrich, and Alex Smola. A Generalized Representer Theorem. In David Helmbold and Bob Williamson (eds.), Computational Learning Theory, Lecture Notes in Computer Science, pp. 416-426, Berlin, Heidelberg, 2001. Springer. ISBN 978-3-540-44581-1 doi: 0b0:10.100773-54444881--11
Laurent Schwartz. Sous-espaces hilbertiens d' d'espaces vectoriels topologiques et noyaux sociés (Noyaux reproduisants). Journal d'Analyse Mathématique, 13(1):115-25) 1964.
13

---

Under review as a conference paper at ICLR 2021
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural Machine Translation of Rare Words with Subword Units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational I Linguistics. doi:10. 10111886511111111
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference Empirical Methods in Natural Language Processing, pp. 1631-1642, 2013.
Guohui Song, Haizhang Zhang, and Fred J. Hickemell. Reproducing kernel Banach spaces with the norm. Applied and Computational Harmonic Analysis, 34(1):96-116,, January 2013, ISSN 1063-5203. doi:10. 101 //t.:///.aaaaa. 2012.00.2200000
I. Steinwart, D. Hush, and C. Scovel. An Explicit Description of the Reproducing Kernel Hilbert Spaces of Gaussian RBF Kernels. IEEE Transactions Information Theory, 22(10):463544643 October 2006. ISSN 0018-9448. 10010..119/TTT.2000660
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Information Science and Statistics. Springer New York, New York, NY, 2008. ISBN 072-3377777721177777------777777 4. doi::101100779733--3387-777
Dacheng Tao, Xuelong Li, Weiming Hu, Stephen Maybank, and Xindong Wu. Supervised Tensor Learning. In Fifth IEEE International Conference Data Mining (ICDM'05), pp. 450-457, Houston, TX, USA, 2005. IEEE. ISBN 978-0-7695-2278-4 doi:10. 10011000.0002000.111
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need. In Advances Neural Information Processing Systems, volume 30, pp. 5998-6008, 2017.
Ashish Vaswani, Samy Bengio, Eugene Brevdo, Francois Chollet, Aidan N. Gomez, Stephan Gouws, Llion Jones, Lukasz Kaiser, Nal Kalchbrenner, Niki Parmar, Ryan Sepassi, Noam Shazeer, and Jakob Uszkoreit. Tensor2Tensor for Neural Machine Translation. arXiv: 07416 [cs, stat], March 2018
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations, 2018.
Stefan Wager, Sida Wang, and Percy S Liang. Dropout Training as Adaptive Regularization. In Advances in Neural Information Processing Systems, volume 26, pp. 351-359. Curran Associates, Inc., 2013.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. GLUE: A Muski Benchmark and Analysis Platform for Natural Language Understanding. In Interna- tional Conference on Learning Representations, 2019a.
Qiang Wang, Bei Li, Tong Xiao, Jingbo Zhu, Changliang Li, Derek F. Wong, and Lidia S. Chao. Learning Deep Transformer Models for Machine Translation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 1810-1822, 1822. Florence, Italy, July 2019b. Association for Computational Linguistics. 11..111651111191111111
Christopher K. I. Williams and Matthias Seeger. Using the Nyström Method to Speed Up Kernel Machines. In Advances in Neural Information Processing Systems, volume 13, pp. 682-688. MIT Press. 2001.
Gang Wu, Edward Y Chang, and Zhihua Zhang. An Analysis of Transformation Non-Positive Semidefinite Similarity Matrix for Kernel Machines. Technical report, University of California, Santa Barbara, June 2005.
Wei Wu, Jun Xu, Hang Li, and Satoshi Oyama. Asymmetric Kernel Learning. Technical report, Microsoft Research, June 2010.
14

---

Under review as a conference paper at ICLR 2021
Yuesheng Xu and Qi Ye. Generalized Mercer Kernels and Reproducing Kernel Banach Spaces, volume 258 of Memoirs of the American Mathematical Society. American Mathemati-
cal Society, March 2019. ISBN 978-1-4704-3550-9 978-1-4704-5077-9 -78-1-4700-50778- 1oi: 1tt::00.1000/mmm/22453
Zhilin Yang, Zihang Dai, Yiming Yang. Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. XLNet: Generalized Autoregressive Pretraining for Language Understanding, arXiv:1906.088. 08.337 [cs], June 2019.
Haizhang Zhang and Jun Zhang. Regularized learning in Banach spaces an optimization problem: Representer theorems. Journal of Global Optimization, 54(2):235-250, October 2012. ISSN 1573-2916. doi:10. 100:1000007/100800 10880000009- -10-955.....
Haizhang Zhang, Yuesheng Xu, and Jun Zhang. Reproducing kernel Banach spaces for machine learning. Journal of Machine Learning Research, 10:2741-2775, December 2009.
15

---

Under review as a conference paper at ICLR 2021
A DEEP NEURAL NETWORKS LEAD TO BANACH SPACE ANALYSIS
Examining the kernel learning problem (11), it may not immediately clear why the reproducing spaces on X' and )/ need be Banach spaces rather than Hilbert spaces. Suppose for example that we have two RKHS's Hy and Hy on X' and V/ respectively. Then, we can take their tensor product H.x @ Hy as an RKHS on X' x V. with associated reproducing kernel [x @ 1/, & y2) = Kx (21, k (1, V2), where Kx and Ky are the reproducing kernels of H.x and Hy, respectively, and 21 09 y1, F2 @ y/2 E X' 8 y. The solutions to a regularized kernel problem like (11) would then be drawn from H.x and Hy: This setup is similar to those studied in, e.g., Abernethy et al. (2009); He et al. (2017).
In shallow kernel learner like an SVM, the function in the RKHS can be characterized via its norm. Representer theorems allow for the norm of the function in the Hilbert space to be calculated from the scalar coefficients that make up the solution. On the other hand, for a Transformer layer in multilayer neural network, regularization is usually not done via norm penalty as shown in (11). In most applications, regularization is done via dropout on the attention weights ai as well as via the implicit regularization obtained from subsampling the dataset during iterations of stochastic gradient descent. While dropout has been characterized as a form of weight decay (i.e., a variant p-norm penalization) for linear models (Baldi & Sadowski, 2013; Wager et al., 2013, etc.), recent work has shown that dropout induces a more complex regularization effect in deep networks (Helmbold & Long, 2017; Arora et al., 2020, etc.). Thus, it is difficult to characterize the norm of the vector spaces we are traversing when solving the general problem (11) in the context of a deep network. This can lead to anbiguity to whether the norm being regularized as traverse the solution space is Hilbert space norm. If f and are infinite series or LP functions, for example, their resident space is only Hilbert space if the associated norm is the f2 or T,2 norm. This motivates the generalization of kernel learning theorems to the general Banach space setting when in the context of deep neural networks.
B PROOF OF THEOREM 1
B. PRELIMINIARIES
To prove this theorem, we first need some results and definitions regarding various properties of Banach spaces (Megginson, 1998). These preliminaries draw from Xu Ye (2019) and Lin et al. (2019).
Two metric spaces (M, dm) and dy) are said be isometrically isomorphic if there exists a bijective mapping T : -M + N, called an isometric isomorphism, such that for all m E M, (T)) = (m) (Megginson, 1998, Definition 1.4.13).
The dual space of vector space V over field F, which we will denote V", is the space of all continuous linear functionals on V, i.e.,
{g : V + -.E linear and continuous).
(B.1)
normed vector space V is reflexive if it is isometrically isomorphic to y*", the dual space of its dual space (a.k.a. its double dual).
For a normed vector space V, the dual bilinear product, which we will denote (s:hv (i.e., with only one subscript, opposed e.g..
is defined on V and V as
(f.g/v 2 g() for f V.
Given a normed vector space V and its dual space V", let U4 C V and W C V The annihilator of LI in V and the annihilator of W in V. denoted 4 and -W respectively, are (Megginson, 1998, Definition 1. 1.1).14)
4- = (gEv (1.9/= 0 V VSEU
- E (f.9/v Vg W).
16

---

Under review as a conference paper at ICLR 2021
A normed vector space V is called strictly convex if | + (1 - t)e2llv whenever || ||v || = 1, 0 < < 1, where V1. 82 V and || ly denotes the norm of V (Megginson, 1998, Definition 5.1.1; citing Clarkson, 1936 and Akhiezer & Krein, 1962).
nonempty subset A metric space (M, d is called Chebyshev set if, for every element m M, there is exactly one element e A such that dm c) dm A) (Megginson, 1998, Definition 5.1.17) (where recall the distance between a point m and set AA in a metric space is equal infor d. (m, c)). If normed vector space reflexive and strictly convex, then every nonempty closed convex subset of V is Chebyshev set (Megginson, 1998, Corollary 5.1.19; citing Day, 1941).
For normed vector space V and E V. the Gâteaux derivative of the norm (Megginson, 1998, Definition 5.4.15) in the direction of is defined
|/ + twlly |elly
lim 800
If the Gâteaux derivative of the norm at in the direction of w exists for all w E V, then ||. is said to be Gâteaux differentiable at v. normed vector space called Gâteaux differentiable or smooth if its norm is Gåteaux differentiable at all v E V (Megginson, 1998, Corollary 5.4.18).
The smoothness of a normed vector space V implies that, if we define a "norm operator", / on V, p(v) & ||l||a, then for each V {0), there exists a continuous linear functional dep(e) on such that (Xu & Ye. 2019, p. 24)
|| tw ly | for all w E V.
(w. dop(u))v = -iim (-0
t Since the Gâteaux derivative of the norm is undefined at O, following Xu & Ye (2019, Equation 2.16); Lin et al. (2019, p. 20); etc., we define regularized Gâteaux derivative of the norm operator on V,
c(v) dap(v) when / 0
(B.2)
when
for E V.
Given two vector spaces V and W defined over a field I,, the direct sum, denoted V @ W, the vector space with elements (v, w) E V @ W for V. W with the additional structure
(U1, w1) + (D2, w2) = (v1 + U2, wi + w2) for U1, 022 E V, W1, W2 E W c(v, w) (cv,
for E V, w E W, E F.
V and W are normed vector spaces with norms || 1lv and || Ilw respectively. then we will say V W has the norm
(B.3) Megginson (1998, Definition 1.8.1) calls (B.3) "I-norm" direct sum norm, but notes that other norm-equivalent direct sum norms such as 2-norm and infinity-nori are possible. Some other useful facts about direct sums are:
||u, welwww - ||l/y + ||ll for E V, E W.
if V and W are both strictly convex, then V + W is strictly convex (Megginson, 1998, Theorem 5.1.23);
if V and W are both reflexive, then Ve W is reflexive (Megginson, 1998, Corollary 1. 1.11;00); and if V and W are both smooth, then V W is smooth (Megginson, 1998, Theorem 5.4.22).
An element of normed vector space V is said to be orthogonal (or Birkhoff- orthogonal) to another element w E if (Birkhoff, 1935; James, 1947)
|| + tw]ly v 2 ||u||y for all E TR.
If WWC C V, then we say E V is orthogonal to W if is orthogonal to all w E W.
Now can state lemma regarding orthogonality in RKBS's.
Lemma (Xu & Ye, 2019, Lemma 2.21). If the RKBS B is smooth, then f E B orthogonal to
g E B if and only if (g, (f)) O, where { means the dual bilinear product given in (B.1) and 1 the regularized Gâteaux derivative from (B.2). Also, an f E B \ {0} is orthogonal to subspace N C. B and only if (),,())) 0 for all h E N.
17

---

Under review as a conference paper at ICLR 2021
B.2 MINIMUM-NORM INTERPOLATION (OPTIMAL RECOVERY)
Following Fasshauer et al. (2015); Xu & Ye (2019); Lin et al. (2019), we first prove a representer theorem for simpler problem that of perfect interpolation while minimizing the norm of the solution - before proceeding to the representer theorem for the empirical risk minimization problem (11) in the next section.
Definition 4 (Minimum-nee Bx and By RKBS's on X and y/ respectively. Let (3 Bx xB - be bilinear mapping on the two RKBS's, 2x X' - Fx and By 3 Fy. Let n( 8:) (xx(z), (y))) (foy(m))
interpolation in pair of RKBS's). Let X' and ) be nonempty sets, and
xBy be a reproducing kernel of and y satisfying Definitions and 2. Say (21,...., In.,,,,Tn,, h. 2. E X. (yi..... Un, Mi E V. and (ayjiet........ jo Fiy E is a finite dataset where a response Zij defined for every (i,5) pair of an xy and Mjj The minimum-norm interpolation problem
f arg min
|lfl + Illlla
Teöx WEBy such that (f,g) Nx.,2
(B.4)
where
Nx ((f.g) Bx @ By s.t. (fey(u)) (0x()))))))))))))))))))))))) xB = zij V (j
(B.S)
To discuss the solution of (B.4), we first need establish the condition for the existence of solution. The following is a generalization of result from Section 2.6 of Xu & Ye (2019).
lineurly independent in By, the set {m(r;,5)}}= is linearly independent Bx, and the bilinear mapping ( Bx Bx x By + R is nondegenerate, then Nx.y.2 (B.5) is nonempty.
Lemma 2. If the set (((x),)))
Proof. From the definition of (3) and the bilinearity of Bx write that
Σ cs (f,n(zzs ((.K(x))))Bx000
Σ c((()) for all Bx
Bx x By
for Cj E R, and that
n2
Σ Cg)((188)..)) BxxBy
oj (1(.,88).. xBy
Σ ()0(8)) for all g E By
for Cj E R. This means that
The
Σ qx( = 0 if and only if
Σ cf(x,) = for all f Bx
and
Σ j=1
cyk(s U3) = 0 and only if Σ c5)(1,) = 0 for all E By. j=1
This shows that linear independence of {5(#,, Pa and {s(- y) ) imply linear independence of (f and " respectively. Then, considering the nondegeneracy of the bilinear mapping (c, ") xBy we can say that
cgn(- Hy),
Σ c -)
=0
BxxBy
if and only if
(f(())) 0 for all / E Bx or Σ C,g(,,)) 0 for all g By
From this, see that linear independence of {n(Z),) > and {N(: u,)1">, and the nonde- generacy of (,, 1x ensure the existence of least (S" 0²) pair in Nx.y2.
n
18

---

Under review as a conference paper at ICLR 2021
Now prove a lemma characterizing the solution to (B.4).
Lemma 3. Consider the minimum-norm interpolation problem from Definition 4. Assume that x and By are smooth, strictly convex, and reflexive, and that {K(Za; -) )3 and {K(;;33) Mj))smm are linearly independent. Then, (B.4) has unique solution pair (f*gg)) with the property that
df) Σ Eun(T),-)
((g') = Σ Sgn(-.us).
5=1
where c(-) is the regularized Gâteaux derivative as defined in (B.2), and where Ea Sf E R.
Proof. The existence of a solution pair is given by the linear independence of { )) and {K(' "=) and Lemma 2. Uniqueness of the solution will be shown by showing that Nx is closed and convex and subset of a strictly convex and reflexive set, which ensures it is a Chebyshev set.
Since 8x and By are strictly convex and reflexive, their direct sum Bx @ By is strictly convex and reflexive, as we noted in section B.I.
Now we analyze Nx.y.2 We first show convexity. Pick any (f.9), g' Nx.vi and t E (0, 1). Then note that for any (Ii, Zi.j)
(15)) (1- (oxx(x)))) Bx Bxx + (11 (yy))))
() Bx BxxBy
+ (1 ( BxxBy (f 9xx(x))) By xBy
= =tay + + -1-t)22,
-Fi
thus showing that Nx.y.2 is convex. Closedness may be shown by the strict convexity of its superset Bx a By and the continuity of (,,) B.x," Thus, the closed and convex Nx. S Bx @ By is Chebyshev set, implying unique (f", E Nx,,, with
xB,
min Ilf" [x (fag)exx.y.x
||fl + llallsy.
Now we characterize this solution gf',g"). Similar to proofs of the classic RKHS representer theorem (Schölkopf al., 2001) and those of earlier RKBS representer theorems (Xu & Ye, 2019; Lin et al., 2019, etc.), we approach this via orthogonal decomposition. Consider the following set of function pairs (f, g) that map all data pairs (I,, 8,) to
Nx ((fg)) Bx @ By ((ex())))) Bx XBy
0;
i= 1.... Nui = 1==,... 1....,,,, n2y
We can see that Nx.y. is closed under addition and scalar multiplication. making it subspace of Bx @ By.
Taking our optimal (f* g'),, we can see that
II("",9) + (JO, ( Ilswa [[(""," ""),"")) for any (f E Nxxy0 thus showing that (f*,"" is orthogonal to the subspace Nx.v. Consider the left and right preimages of Nx. under (,, (xxxx:
(B.7)
(. (1 [xx. = {f E Bx (foylu)):00xee) Bx xxx
= I,.., Mai j=1,... ny); g E By
U1 (x.xroo = { E Bx: (Jey 20x (m.) Bx BxxBy = 0; ==
nzj j j= ;.,,...,, f f Bxx.
As Fasshauer et al. (2015) note, any Hilbert space is strictly convex and smooth, so it seems reasonable to assume that an RKBS also strictly convex and smooth.
19

---

Under review as a conference paper at ICLR 2021
Since Bxxy, xBy [ ? Bx and (f: () BxxBy We.yoo S By, consider them as normed vector spaces with norms || Il and || By, respectively. From (B.7) and the definition of the direct sum norm (B.3),
Ilf + 1Bx 2
for all f (x [Nx,y,o for arbitrary g E By I19" + 1 2 119 |By for all go (f: BBxBy [x.yoo): for arbitrary f Bx. (B.8b)
If |xx
(B.8a)
We can then use (B.8) and Lemma to say
(((())) 0 for all f e (x xBy [W for arbitrary g By
(g, B)y 0 for all E (ʃ, ) Bx (Wx,),)), for arbitrary E Bx
which means
(f*) ((r.) Wx.xoo) for all g E By
(B.9a)
(g") E (1,) (Nx for all f E Bx-
(B.9b)
From (B.9a) and (3a)-(3b),
e' E U (1,) (x.vrol = {s E Bx: (fxx))))) BxxBy = g g
gEBy
i i= -=.....,,aa
uzi j -.,...,9 ,,)
= (s E Bx (So)(us): 11) BxxBy =
span (N((1))) -); i= ,,...,
j 1...., nyy
i i= 1=_....,n nn = + span (N(I;;
(B.10)
And from (B.9b) and (3c)-(3d),
g" E U (f.))x [x..x,o = {g e By : (feylus) 90 (oxxti)))) BxxBy =0; f e Bxi
JEBx
i= ,....,na.: j -....,,11. ,,y]
= og By : (h', foy(v)) BxxBy =
h' span {x(-; Hy)s J ny..
= ",...,,''!! mx)
+ span {k(-, I,..., m
(B.11)
Combining (B.9a) and (B.10), we get (f*) E (+ span(s(æ;,) :); i i= l,..,, nn spanfk(as, :) i i= nw. and by combining (B.9b) and (B.11), we get
(B.12)
(gg)) (+ ('span(((( M)); j I,...,,yyll nyy) where in both 12) and (B.)3) we use Proposition 2.6.6 of Megginson (1998) regarding properties of annihilators.
span (pan(k(s (o((,18)) j 1.....;
(B.13)
From (B.12) and (B.13) we can write that there exist two sets of parameters En...., E and SI...., Sn, E IR such that
n2
((t)
Σ
(n((a
((g)) = 2 Sp((-155)
1=1
thus proving the claim.
20

---

Under review as a conference paper at ICLR 2021
B.3
MAIN PROOF
Before beginning the proof, we state the following lemma regarding the existence of solutions of convex optimization problems Banach spaces:
Lemma 4 (Ekeland & Témam, 1999. Chapter II, Proposition 1.2). Let B be a reflexive Banach space and S closed, convex, and bounded (with respect || ((B) subset of B. Let f :S R ( } be convex function with closed epigraph (i.., it satisfies the condition that Ve E R U (+oo), the set {u E S: [(v) S of is closed). Then, the optimization problem
inf VES
(v)
has at least one solution.
Xu & Ye (2019) and Lin et al. (2019) also reference Ekeland & Turnbull (1983) as source for Lemma 4.
We now restate Theorem 1 with the conditions on Bx and By filled in.
Theorem 1, Revisited. Suppose we have a kernel learning problem of the form in (11). Let K. X x y R. k( y.) = (œx(x;;) by(y:)) Fx = (foy(g)) (0x(x)) / Bx xBy be reproducing kernel satisfying Definitions 1 and 2. Assume that {rd(1,, ));21 is linearly independent in By and that {K(, y/) ) linearly independent in Bx. Assume also that Bx and By are reflexive, strictly convex, and smooth. Then, the regularized empirical risk minimization problem (11) has unique solution pair (f", ("""), with the property that
n1y
(5)) Σ En((s:))
((g") Σ (n((,15)-
where Ex, SJ E R.
Proof. As before, we begin by proving existence and uniqueness of the solution pair (f*, ,g").
We first prove uniqueness using some basic facts about convexity. Assume that there exist two distinct minimizers (i.g)), (Jž, .5) xx @ By. Define (Já, 95) 1/2[(/i, 9i) + (J2. gb)]. Then, since Ex and By are strictly convex, we have
1
If Bxx
(fi + f2)
|1
||
11 lx
Bx
1 +
19g lay
(oT + 25)
|g Bay
2 $lls2llss
2
and since Rx and Ry are convex and strictly increasing,
Rx (1HUT + f2)
1 (11 + : fl [llfálles l1,x
Rx
1xx
$ 2
Rx(1IfilBB + (1x5f1)))
and
Ry(llgglles (lay) = Ry (1
1 1::00 + 2
< By
-
ll Iyy + *21102 111521 11
2
Ry Ry(l l1 By + Ry (1122118))))
Consider the regularized empirical risk minimization cost function (11) T(f.)) C(f.g) + {x + Xy
where we use the shorthand
C(f.g) Ty 3.5
Σ
ris (Ir. Zij. ((xx()).)ox(x))) ByxBy)
21

---

Under review as a conference paper at ICLR 2021
We have that Rx(1 convex functions. The function C(f.9) g) is also convex since all the functions in the summand are convex in and g.
l1xx) and Ry([1 Ilay) are both convex via identities about composition of
Then, since we have assumed that T(fi = T(f2, 92), by plugging in some of the above inequalities we can write
T(f. 05) =5)= (5 (ffi (f2,
=L 2 (ffiigi) (f2.96))
+ Rx
(fi + f2)
18x
11 (of (be
+ Rl
18y
1
(ffiggi)+ ((2
+ Rx (11f1111xx) ) + ブ/ Rx (1lf2 ll
2
2
1
+ Ry (11[1llss) + Ry (1152 Il
1 T(f + ===2222 T52
2
= -(f
contradicting that 9ī) is a minimizer, and thus showing uniqueness of the solution.
We now prove existence via Lemma 4. We already know that T(-) is convex. From the bilinearity of (s ) (xx xB and the convexity of I,, is continuous in f and Since the regularization functions Rx and Ry are convex and strictly increasing, is follows that the functions Rx (I [l and Ry(11g]ls))
are continuous and g. respectively. Thus, T(f.g) g) is continuous. Consider the
& (({9) E Bx By T(,,)) T(0,
The set & is nonempty (it contains at least (0, 0)), and we can see that
= ||]l|xx + |1gllsy S 2 (T((.)) + (T)00)))
showing that is bounded. So, by Lemma 4, we are guaranteed the existence of an optimal solution (f",9").
Pick any (S.g) E Bxx x By and consider the set
( (1i (J (xx) Bx xBxx i= Pla; j = 1, ==1....,,y ny
Di.g =
i.e. the set of pairs of points (I,, yi) along with the value that the function pair (f, gg) maps to via the bilinear form the pair of points (I;, (z).
From Lemma 3, there exists an element (S' E Bx x By such that (f', interpolates Dj.9 perfectly, i.e..
(xx)))))))x)))))))))))) Bx BB (fay(n)) Br i= 1,.... nzi 1,..., ng
whose Gâteaux derivatives of norms satisfy
(f") E spanf :):
1....,... ,
((g') E spanff((-_)) 8y); j nyy.
Further, this element (f'g) obtains the minimum-nome interpolation of D i.e.
|I a |L S Ilf. Bwaysy
This last fact implies
T('' < ((S.9)-
22

---

Under review as a conference paper at ICLR 2021
Therefore, the unique optimal solution (f*.g" also satisfies
(f*) E span { (< )); i == ....., 122)
(gg)) E span k((,9;);; j j= 1................ ny
which implies that suitable parameters E1,...,, En E R and SI...., Sry
IR exist such that
n1 u(f) Σ (un(a))))
n2
(gg) Σ
(gn(:.3))
j=1
proving the claim.
C PROOF OF THEOREM 2
First, we state the following well-known lemma.
Lemma 5. For any two compact Hausdorff spaces X and y, continuous function K: X' IR
and E > O, there exists an integer d > O and continuous functions de X' - R, Ve y - IR L 1, ...., d such that
<<x, v)
Σ (e(x)(e()) <e YzER,yEY.
Proof. The product space of two compact spaces X' and V, X' V, is of course compact by Tychonoff's theorem. Consider the algebra
{ f: f(z,v) = (e(t))elv), xER.EE).
A =
is easy to show (i) that A is an algebra, (ii) that a subalgebra of the real-valued continuous functions V, and (iii) that A separates points. Then, combining the aforementioned facts, by the Goone-Weierstraa theorem A is dense in the set of real-valued continuous functions on X' x X O
Remark 9, In addition to helping us prove Theorem 2 below, Lemma 5 also serves as somewhat of an analog to Mercer's theorem for the more general case of asymmetrie, non-PSD kernels. It is however weaker than Mercer's 's theorem in that the non-PSI nature i means that the functions in the sum cannot be considered eigenfunctions (with Φe- v/r) with associated nonnegative eigenvalues.
Now proceed the proof of Theorem 2.
Proof. To keep the equations from becoming too cluttered, below use q(t), k(s), (()) Rd as the vector concatenation of the sealar functions (te(t), }: (kr(s)), (dr(()), and (vr(s)).
1..... d, respectively. All sup norms with respect to X' y
Our proof proceeds similarly to the proof of Theorem 5.1 of Okuno et al. (2018). We generalize their theorem and proof to non-Mercer kernels and simplify some intermediate steps. First, by applying Lemma 5, we can write that for any 61, there is d such that
|| Φ
*b61 <1
(C.1)
Now consider the approximation of de and the by qe and ke respectively. By the universal approximation theorem of multilayer neural networks (Cybenko, 1989; Hornik et al., 1989; Funahashi. 1989; Attali & Pagès, 1997, etc.). know that for any functions de X IR, 2/e y R and scalar 62 > 0, there an integer m > 0 such that if qe X TR and hig : y + R are two-layer neural networks with m hidden units, then
| gell gellsup <2 and
b kz Sell < <
(C.2)
for all L. Now, beginning from (14), can write
||x- q _k|luup < ||~c TT T
1
kT
(C.3)
23

---

Under review as a conference paper at ICLR 2021
by the triangle inequality. Examining the second term of the RHS of (C.3).
|| | q'kl| - -1 (+ k) (Φ k)< | sup
< | 1)ll (| 9) T]]
sup
- |1 1/ - kllaup + 11 q gllsup || sup
(C.4)
where the first inequality uses the triangle inequality and the second uses the Cauchy-Schwarr inequality. Finally, we can combine (C.1)-(C.4) to write
1 - q Isap S <||k= o tT Iaup + 11 1| - kllaup + 11 - ql sup l
<1 dez(Il@lssmp + 1| de2).
Picking 61 and 62 appropriately, e.g. 6 = s/2 and 62 v /d proof.
+ 1 )222))
completes the
2d
D EXPERIMENT IMPLEMENTATION DETAILS
Datasets The 2014 International Workshop on Spoken Language Translation (IWSLT14) machine translation dataset is a dataset of transcriptions of TED talks (and translations of those transcriptions). We use the popular German to English subset of the dataset. We use the 2014 "dev" set as our test set, and train/validatiin split suggested in demo code for fairseq (Ott et al., 2019), where every 23rd line in the IWSLT14 training data is held out as a validation set.
The 2014 ACL Workshop on Statistical Machine Translation (WMT14) dataset is a collection of European Union Parliamentary proceedings, news stories, and web text with multiple translations. We use newstest2013
validation set and newstest2014
our test set.
The Stanford Sentiment Treebank (SST) (Socher et al., 2013) is a sentiment analysis dataset with sentences taken from movie reviews. We two standard subtasks: binary classification (SST-2) and fine-grained classification (SST-5). SST-2 is subset SST-5 with neutral-labeled sentences removed. We use the standard training/ validation/teesting splits, which gives splits of 6920/872/1821 on SST-2 and 8544/1 101/2210 on SST-5,
Data Preprocessing On both translation datasets, we use sent sentencepiecs to tokenize and train byte-pair encoding (Sennrich et al., 2016) the training set. We use a shared BPE vocabulary across the target and source languages. Our resulting BPE vocabulary size is 8000 for IWSLT14 DE-EN and 32000 for WMT14 EN-FR.
For SST, we train a sentencepiece BPE for each subtask separately, obtaining BPE vocabularies of size 7465 for SST-2 and 7609 for SST-5.
Models Our models are written in Pytorch (Paszke et al., 2019). We make use of the Fa firse (Ott et al., 2019) library for training and evaluation.
In machine translation, we use 6 Transformer layers in both the encoder and decoder. Both Trans- former sublayers (attention and the two fully-connected layers) have a residual connection with the "pre-norm" (Wang al., 2019b) ordering of Layer normalization residual. We use an embedding dimension of 512 for the learned token embeddings. For IWSLT14, the attention sublayers sublayers have a hidden dimension of 1024. For WMT14, following Vaswani et al. (2017)'s "base" model, the attention layers have 8 heads with a per-head dimension d of 64 and the fully-connected sublayers have a hidden dimension of 2048.
Attention FC-> ReLU -> Add
4 heads with per-head dimension of 128 and the fully-connected
For SST, The token embedding dimension is 64, each Transformer self-attention sublayer has heads with per-head dimension d of 16, and the fully-connected sublayers have hidden dimension of 128. To produce a sentence classification, the output of the second Transformer layer is average-pooled over
a very small, encoder-only, Transformer variant, with only Transformer layers.
'https://gi thub. wwm coo/googlee /e e/ sentencppiece
24

---

Under review as a conference paper at ICLR 2021
the non-padding tokens, then passed classification head. This classification head is two-layer neural network with hidden dimension 64 and output dimension equal to the number of classes; this output vector becomes the class logits.
Training We train with the Adam optimizer (Kingma & Ba, 2015). Following Vaswani et al. (2017), for machine translation we the Adam parameters 31 0.9, 32 0.98.
On IWSLT14 DE-EN, we schedule the learning rate to begin at 0.001 and then multiply by factor 0.1 when the validation BLEU does not increase for epochs. FOR WMT14 EN-FR, we decay proportionally to the inverse square root of the update step using Fa i rseq's 's implementation. For both datasets, we also use linear warmup on the learning rate from le-7 0.001 over the first 4000 update steps.
On IWSLT14 DE-EN, we end training when the BLEU score does not improve for 7 epochs on the validation set. On WMT14 EN-FR, we end training after 100k gradient updates (inclusive of the warmup stage), which gives us a final learning rate of 0.0002. We train on the cross-entropy loss and employ label smoothing of 0.1. We minibatches with maximum of about 10k source tokens on IWSLT14 DE-EN and 25k on WMT14 EN-FR Also on WMT14, we ignore sentences with more than 1024 tokens.
For both SST subtasks, we also use a linear warmup from le-7 over 4000 warmup steps, but use an initial wost-warmup learning rate of 0.0001. Similar to IWSLT14, decay the learning rate by multiplying by 0.1 when the validation accuracy does not increase for epochs, and end training when the validation accuracy does not improve for 8 epochs.
Evaluation for machine translation Following Vaswani et al. (2017), we use beam-search decod- ing, with beam length of and a length penalty of 0.6, generate sentences for evaluation. We use sacrebles eu (Post, 2018) to generate BLEU scores. We report whole-word case-sensitive BLEU.
25


Reviews:
[{"review_id": "xug-tgSISbd", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review: This paper demonstrates that transformer models with dot-product attention-based scores are inherently\nlearning feature representations in reproducing kernel Banach spaces. Under some mild regularity conditions,\nthe authors demonstrate that the regularized empirical minimization solutions are unique, (i.e. linear independence\nassumptions in the two reproducing kernel Banach spaces corresponding to the targets and the sources) and that\nusing two-layer neural network with appropriate number of hidden layer units can achieve universal approximation\nproperty.\n \nOverall reasons for score:\nI am leaning toward arguing for acceptance. The paper establishes a connection between a fairly recent method a classical method. It would have been nice to see more experimental results (see below).\n\n+Positives: \n\n+ The paper for the most part is clearly written and establishes a connection between the recent method and the classical\nmethod. I have skimmed through most of the proofs and they seem to be correct.\n \n\nConcerns: \n\n- The experimental section is fairly limited since the majority of the paper focuses on more theoretical aspects of transformers.\nIn particular, it would be interesting to see the authors expand upon whether exponentiated dot products are better on\nmore datasets.\n \n- The theoretical contributions in this paper are interesting but mainly pieces together results.\n\nMinor comments: \n\n* Proposition 1 has typos in Equation 7a and 7b. (q_l)^n -> (q_l)^{p_l} and (k_l)^n -> (k_l)^{p_l}\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XEIkv9ga6ax", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors treat a particular Transformer, \"dot-product attention\", as  an RKBS kernel called \"exponentiated query-key kernel\". The explicit form of feature maps and Bach space are given. Moreover, authors term a binary kernel learning problems within the framework of regularized empirical risk minimization. The problem and the correponding representer theorem is new due to its extension to Banach space. A new approximation theorem is also proved and  some experiements are done. \nPros:\nThe idea of understanding how Transformers work with the help of non-mercer binary kernel  is interesting.\nAs for the theoretical side, authors provide representer theorem to binary kernel learning for Banach space rather than Hilbert space. \n\nCons:\nThe experiment is insufficient because only one dataset is studied.\nI think the proof is just a generalization of kernel learning problems on RKBS, without too much difficulty.", "extra_scores": {}, "extra_text": {}}, {"review_id": "O0-QJKWS7eC", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper aims at providing a mathematical structure for explaining the mechanism behind the attention block characteristic to transformers. The focus of the paper is on the scaled dot-product attention, reviewed in Eq. (1). In my understanding, the whole mechanism can be seen as an instance of the set kernel. The inputs are bags of items, where an item is denoted with $s_j$. The items are embedded into some feature space via matrix multiplication $W^V s_j$. The set kernel representation of a bag is obtained by weighted averaging of item embeddings, where the item-specific weight is the output of an exponential family model. The latter model is obtained by combining embeddings of items and corresponding context vectors, denoted with $t_i$ (see Eq. 1 for more details).\n\nThe paper in itself does not explain this mechanism as a whole but focuses on the un-normalized exponential family model that provides importance weights in the set kernel embedding. In particular, the main focus of the work is to find a bilinear form and, thus, a mathematical structure that could give rise to non-symmetric similarity function defining the un-normalized importance weights in the set kernel described above. More formally, the work seeks a kernel function\n$$\nk(t,s) = \\exp(\\frac{(W^Qt)^{\\top}(W^Ks)}{\\sqrt{d}}) \\ ,\n$$\nwhere $d$ is the rank of W-matrices.\n\nThis is achieved by introducing the so called reproducing kernel Banach space (Sections 3 and 4). Following this, the paper introduces a form of regularized risk minimization problem in reproducing kernel Banach spaces. I fail to see a direct link to transformers and backpropagation used in training of such models. The conclusion is that transformers learn a kernel or similarity function that can be assigned to a reproducing kernel Banach space. I disagree with this because the whole attention mechanism is a set kernel, with the supplied bilinear form amounting to importance weights only. The section 5 concludes with a representer theorem and regularized risk minimization problem in reproducing kernel Banach spaces. Again, this is a completely disconnected part of the paper from the introduction and provided motivation.\n\n#### clarity\nI find the paper clear in most parts and have not had problems following the main arguments. Related work on learning with similarity measures, indefinite symmetric kernels, and general similarity functions seems to be well covered.\n\n#### quality\nI think this paper should really be focusing on learning in reproducing kernel Banach spaces with non-symmetric similarity measures. It is difficult to tell how much novelty it brings compared to relevant related work and how useful it would be in practice. If the authors decide to take this direction, then there should be a detailed experiments section where trade-offs between effectiveness and computational complexity are carefully studied. \n\nIt is unclear to me why this work would be associated with attention models and transformers. The story just does not hold and it does not explain the scaled dot-product attention. At the moment, it just seems as an unfinished work that is unnecessarily associated with attention and transformers.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KLKfYHZcOKD", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper aims at making a link between kernels in RKBS (indefinite and asymmetric kernels) and the dot-product attention of Transformers. The paper contains several contributions on top of this link : it provides a novel kernel machine that can deal with data from 2 distinct input domains and a cross domain output, it show that Transformer can learn such kernels, and it also give hints on what make Transformer efficient.\n\nThe paper manages to present different backgrounds (transformers and exotic kernels) to mix them in a quite clear manner. Notations from two worlds are respected such that, as far as I can say, people from each side can catch things quickly. \nFrom the transformer's perspective, being able to plug any well designed kernel in place of the dot-product attention can have some interesting practical application. The observation that the efficiency of transformer could be linked to the infinite feature map brought be some kernel shapes is appealing but quite weak. \nFrom the kernel machine's perspective, the proposed kernel machine in RKBS is elegant and comes with solid theoretical proofs. It might have been a paper by itself. \nThe choice of content in paper/in supplementary seems good to me.\n\nI vote for accepting the paper, as I find the idea interesting, I can see some applications and the theoretical part seems correct to me. My main concern is about section 6, which contains only one experiment. It illustrates the fact that one can change the kernel in transformers, but not much more. \nI also have difficulties to see how section 5.2 is done in practice, as I find the description of implementation details do not consider those aspects : I would be happy to have more details on the algorithms\n\n- Details :  \n* section 6 : I suggest the order of kernels be the same in table and in text, it would be easier to follow. \n* section 5.2 : I think this reference (https://doi.org/10.1016/j.patcog.2017.06.003) introduces Nystrom for RKKS a couple of years earlier. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers have different views on the paper and after going through the reviews, replies and the papers, we believe that
there is room for improvement here. 

While the part related to  indefinite symmetric kernels, and general similarity functions seems to be well covered, as
well as the part on Transformers, the relation with learning in RKBS and Transformer is far from being clear and Reviewer 4 makes a strong point on this. For instance, 

* what is the goal of the section 5 and Definition 1 . Indeed it is not clear here if the point of the authors is to learn the kernel parameters in equation 9 or to learn to predict the output of a transformer. If it is the latter, the connection with the first part is unclear.

* In Equation 11, I can understand that x and y are the sequences t and s but what is z_ij and how it is obtained? So again, the learning problem drops in without justification and it is not explained how it can be solved. The theoretical results involving the representer theorem is nice though.

* The experiment does not seem very related to the learning problem in Equation 11 introduced by the authors.it seems to me that they are just trying different kernels on top of the dot product.

Decision: Reject