Year: 2021

Abstract:
A common approach to metric learning is to seek an embedding of the input data that behaves well with respect to the labels. While generalization bounds for linear embeddings are known, the non-linear case is not well understood. In this work we fill this gap by providing uniform generalization guarantees for the case where the metric is induced by a neural network type embedding of the data. Specifically, we discover and analyze two regimes of behavior of the networks, which are roughly related to the sparsity of the last layer. The bounds corresponding to the first regime are based on the spectral and (2, 1)-norms of the weight matrices, while the second regime bounds use the (2,∞)-norm at the last layer, and are significantly stronger when the last layer is dense. In addition, we empirically evaluate the behaviour of the bounds for networks trained with SGD on the MNIST and 20newsgroups datasets. In particular, we demonstrate that both regimes occur naturally in realistic data.

heading: 1 INTRODUCTION
text: Metric Learning, Bellet et al. (2015), is the problem of finding a metric ρ on the space of features, such that ρ reflects some semantic properties of a given task. Generally, the input can be thought of as a set of labeled pairs {((xi, x′i), yi)}ni=1, where xi, x′i ∈ Rd are the features, and yi is the label, indicating whether xi and x′i should be close in the metric or far apart. For instance, in face identification, Schroff et al. (2015), features xi and x′i corresponding to the same face should be close in ρ, while different faces should be far apart.
Note that the above metric learning formulation is fairly general and one can convert supervised clustering, or even standard classification problems into metric learning simply by setting yi = 1 if xi and x′i have the same original label and yi = 0 otherwise Davis et al. (2007); Weinberger & Saul (2009); Cao et al. (2016); Khosla et al. (2020); Chicco (2020).
The metric ρ is typically assumed to be the Euclidean metric taken after a linear or non-linear embedding of the features. That is, we consider a parametric family G of embeddings into a kdimensional space, g : Rd → Rk, and set 1
ρ(x, x′) = ρg(x, x ′) = ‖g(x)− g(x′)‖22 . (1)
As an example, Figure 1 shows tSNE plots, Maaten & Hinton (2008), of the classical 20newsgroups dataset. Figure 1a was generated using the regular bag of words representation of the data (see Sections 5 and D for additional details) while Figure 1b was generated by applying tSNE to an embedding of the data (of the form (3) below) learned by minimizing a loss based on labels, as described above. Clearly, there is no discernible relation between the label and the metric in the raw representation, but there is a strong relation in the learned metric. One can also obtain similar conclusions, and quantify them, by, for instance, replacing tSNE with spectral clustering.
The uniform generalization problem for metric learning is the following: Given a family of embeddings G, provide bounds, that hold uniformly for all g ∈ G, on the difference between the expected value of the loss and the average value of the loss on the train set; see Section 2 for a formal definition. Such bounds guarantee, for instance, that the train set would not be overfitted. Given a family
1Note that ρ in (1) is not strictly a metric. Nevertheless, this terminology is common.
of embeddings G, consider the family F of functions f : Rd × Rd → R of the form F = {f(x, x′) = ρg(x, x′) | g ∈ G} . (2)
We refer to these as the distance functions, which map a pair of features into their distance after the embedding. Well known arguments imply that one can obtain generalization bounds for F by providing upper bounds on the Rademacher complexity Rn (F) of the family of the scalar functions F . Therefore in what follows, we discuss directly the upper bounds on Rn (F) for various families G. We refer to Section 2 for formal definitions and details on the relation between G,F ,Rn (F), and generalization bounds.

heading: 1.1 OVERVIEW OF THE RESULTS
text: In this paper our goal is to study generalization bounds for neural network type non-linear embeddings g : Rd → Rk given by neural networks of depth L ≥ 1. Specifically, we consider embeddings of the form
g(x) = gA(x) = φL ( AtL · ( φL−1 ( AtL−1 . . . φ1 ( At1x ) . . . ))) , (3)
where A = (A1, . . . , AL) is a tuple of matrices such that Ai ∈ Rki−1×ki for i = 1, . . . , L, and ki are the layer widths, with k0 = d and kL = k. The activations φi : R → R are assumed to be Lipschitz, with ‖φ‖Lip ≤ ρi, and act on vectors in Rki coordinatewise. A family of matrix tuples will be generally denoted by A, while the associated embeddings family (3) will be denoted by G and the associated family of distance functions, (2), will be denoted by F . In the context of deep learning generalization guarantees for classification, there exists a large body of work on various complexity bounds related to the family of mappings G. The current strongest uniform bounds were given in Bartlett et al. (2017) (see also Neyshabur et al. (2018)). Our goal here is to translate these bounds to bounds on the Rademacher complexity of the family F , derived from G. That is, we study the aspects of the problem that are specific to the metric learning setting. To state the results, we require a few norm definitions: For matrix A ∈ Rs×t, ‖A‖op is the spectral norm, and set ‖A‖2,1 = ∑t i=1 ‖A·i‖2, where A·i is the i-th column of A. For a family A of matrix tuples, A = (A1, . . . , AL) ∈ A, for i ≤ L we set ‖Ai‖op = sup
A∈A ‖Ai‖op and ‖Ai‖2,1 = sup A∈A ‖Ai‖2,1 . (4)
Thus ‖Ai‖op , ‖Ai‖op are the largest respective norms of the component Ai in A. With this notation, our first result is the following bound (up to logarithmic factors):
Rn (F) ≤ O  1√ n b2 ( L∏ i=1 ρi ‖Ai‖op )2 L∑ i=1 ‖Ai‖ 2 3 2,1 ‖Ai‖ 2 3 op  32  . (5)
Here b is an upper bound on inputs, ‖xi‖2 , ‖x′i‖2 ≤ b for i ≤ n. The full statement is given in Section 4, Theorem 1. This bound can be regarded as a natural extension of the bounds of Bartlett
et al. (2017) to the metric learning setting. Indeed, it uses the same parameters – the ‖A‖op and ‖A‖2,1 norms. The quantity (∏L i=1 ρi ‖Ai‖op ) is the maximal Lipschitz constant of the mappings in G, and it will typically be the dominant term in (5). One of the appealing properties of (5), inherited from the bounds in Bartlett et al. (2017), is that it is dimension free, in the sense that the depth L and the the layer widths ki do not enter the bound explicitly.
As noted above, for the case of classification, the bounds in Bartlett et al. (2017) are currently the strongest known uniform bounds. However, we now show that in the metric learning setting, one can improve the bound in some situations, by using the ‖A‖2,∞ = maxi≤k ‖A·i‖2 norm at the last layer. In Theorem 2, Section 4, we show the following:
Rn (F) ≤ O  k√ n b2 ( ρL ‖AL‖2,∞ L−1∏ i=1 ρi ‖Ai‖op )2L−1∑ i=1 ‖Ai‖ 2 3 2,1 ‖Ai‖ 2 3 op + 1  32  . (6)
We refer to (5) as the sparse bound, and to (6) as the non-sparse bound. To compare the bounds, and to see the relation to sparsity, let us first consider the simpler single layer setting, L = 1. In this case, the bounds read
Rn (F) ≤ O ( b2 ‖φ‖2Lip ‖A‖op ‖A‖2,1√
n
) , (7)
and
Rn (F) ≤ O ( kb2 ‖φ‖2Lip ‖A‖ 2 2,∞√
n
) , (8)
where A is the family of weights matrices, A ∈ Rd×k, φ an activation, and ‖A‖∗ = supA∈A ‖A‖∗ where ‖·‖∗ is one of ‖·‖2,1 , ‖·‖2,∞ , ‖·‖op. Consider first the case where A contains non sparse matrices A ∈ A. These are the weights A where all k neurons have roughly the same norm, or equivalently, ‖A‖2,1 ∼ k ‖A‖2,∞ . (9) We refer to this condition as the dense regime. Note that (9) holds true for neural networks at initialization, and in Section 5 we observe empirically that this also holds for SGD trained networks on MNIST data. Next, when (9) holds, we also have that
‖A‖op ∼ √ k ‖A‖2,∞ . (10)
Indeed, one has ‖A‖op ≤ √ k ‖A‖2,∞ for any A, and (9) implies ‖A‖op ≥ const · √ k d ‖A‖2,∞ (see Lemma 3 in supplementary material A). The condition (10) will be also experimentally verified for MNIST data. Now, substituting (9),(10) into (7) and (8), we obtain that in the non-sparse regime, (8) is stronger than (7) by a factor of √ k, a significant improvement. On the other hand, when A is sparse, with most output neurons zeroed out (e.x. ‖A‖2,1 = ‖A‖op = ‖A‖2,∞), (7) will be much stronger. Such sparse networks can be achieved by adding explicit sparsity regularization terms to the cost. This will be the case for networks trained on the 20newsgroups dataset.
Finally, as evident from (5) and (6), for the multilayer case L > 1, the relation between the sparse and non-sparse bounds is more involved. However, the asymptotics of the dependence on k is similar: With all other ki fixed, (6) will be better by a factor of √ k for non-sparse last layer AL, and (5) will be better otherwise.
We now discuss an additional direction in which the bounds may be improved: Note that the dependence of the bound on the coefficients of the weights in (5) and (6) is quadratic. As we show in Section 4, this is in general unavoidable, due to the quadratic form of the metric (1). However, if the highest activation, φL is bounded, such as for instance the sigmoid φ(x) = (1 + e−x)−1, then one can obtain a linearly homogeneous dependence on the layer weights, thus potentially significantly improving the bounds. These bounds are given in (18) and (21) in Theorems 1 and 2 respectively. For comparison, in the single layer case the sparse and non-sparse bounded φL bounds are given by
Rn (F) ≤ O (√
kb ‖φ‖∞ ‖φ‖Lip ‖A‖2,1√ n
) and Rn (F) ≤ O ( kb ‖φ‖∞ ‖φ‖Lip ‖A‖2,∞√
n
) ,
(11)
where ‖φ‖∞ is the upper bound on the values of φ.

heading: 1.2 METHODS
text: The general proof strategy we take in this paper is to combine the covering number bounds for the family G, due to Bartlett et al. (2017), Zhang (2002), with the analysis of the specific structure induced by the metric learning problem, i.e. the structure of the family F(G), when G is fixed. Theorems 1 and 2 exploit this structure differently. In Theorem 1 we directly estimate the covering numbers of F in terms of those of G. Note that, for instance, F and G are function families on different domains, and thus such estimates require some care. Once the estimates are obtained, however, we bound Rn (F) using a standard Dudley entropy integral argument (Vershynin (2018)). On the other hand, to prove Theorem 2, we use the special structure of the metric (1) as a sum. This allows a decomposition of the problem into k problems, each of which has k = 1, and yields bounds which depend on ‖A‖2,∞ and k, rather than on ‖A‖op , ‖A‖2,1. While this may seem as a rougher bound at first glance, as discussed above it is in fact much stronger than Theorem 1 in some situations.
Finally, we note that up to now generalization for metric learning was only studied in the linear case (see Section 3 for a detailed discussion). In particular, uniform bounds were derived in Verma & Branson (2015) and in Cao et al. (2016). Interestingly, already in the basic situation where L = 1 but φ(x) 6= x (i.e. a single layer but non-linear activation), one can not deduce our bounds (7) or (8), for instance, from the bounds in Verma & Branson (2015) or Cao et al. (2016). Nor one can use the methods employed in these works to obtain such bounds. The reason for this is that there seems to be no simple principle that would “remove the linearity” (such as the Contraction Lemma, Mohri et al. (2018) ) in the case of the cost (1). As a result, somewhat surprisingly, even to obtain the linear instead of quadratic homogenity, as in (11) for L = 1, it appears that one already requires the methods used in this paper.
To summarize, we have obtained the first uniform generalization guarantees for multilayer nonlinear metric learning. In particular, we introduced two types of bounds, which are appropriate for sparse and non-sparse weightsAL. We have also shown that by using a bounded last layer activation, one may avoid the quadratic dependence of the bound on the parameters, and we have empirically verified that both sparse and dense regimes may occur in SGD optimized networks.
The rest of this paper is organized as follows: In Section 2 we overview the necessary background on metric learning and generalization. Literature and related work are discussed in Section 3. In Section 4 we give the full formal statements of the results, and overview the main ideas involved in the proofs. Full proofs are deferred to the supplementary material due to space constraints. Experiments are described in Section 5 and concluding remarks are given in Section 6.

heading: 2 METRIC LEARNING BACKGROUND
text: In this paper we are assuming that the training data is given as a set {((xi, x′i), yi)}ni=1 of labeled feature pairs, which we assume to be sampled independently form some distribution D on Rd × Rd × Y , where Y is some set of label values. It is usually sufficeint to take Y = {0, 1}. Note that there may be dependence within the pair, i.e. x′i may depend on xi.
The quality of the embedding g on a data point ((x, x′), y) is measured via a loss function `, which usually depends on ((x, x′), y) only through the metric. That is, given an embedding g ∈ G, let f ∈ F be the corresponding distance function, f(x, x′) = ρg(x, x′) (see (2)). We assume that there is a fixed function ` : R × Y → [0, 1], such that the loss of the distance function f ∈ F on a data point ((x, x′), y) is given by Lf ((x, x′), y) = `(f(xi, x′i), yi) = `(ρg(xi, x ′ i), yi). A typical example of a loss ` is the following version of the margin loss:
`S,D(a, y) = { ReLU (a− S) if y = 1 ReLU (D − a) otherwise, (12)
where ReLU(x) = max (0, x). As discussed in Section 1, this loss embodies the principle that (x, x′) should be close iff y = 1, by penalizing distances above S when y = 1 and penalizing distances below D otherwise.
The overall loss on the data, or the empirical risk, is given by
R̂f = 1
n n∑ i=1 Lf ((xi, x ′ i), yi). (13)
The expected risk is given by Rf = E((x,x′),y)∼DLf ((x, x′), y). The uniform generalization problem of metric learning is similar to the generalization problem of classification: One is interested in conditions on the family F under which the gap between expected and empirical risks, Rf − R̂f , is small for all f ∈ F . Finally, since {((xi, x′i), yi)}ni=1 are independent, standard results imply that to control the uniform generalization bounds of the risk, it is sufficient to control the Rademacher complexity of the family F . Specifically, we have that (see Mohri et al. (2018) Theorem 3.3 and Lemma 5.7) ,
sup f∈F
Rf − R̂f ≤ 2 ‖`‖LipRn (F) + √ log δ−1
2n
holds with probability at least 1 − δ. Here Rn (F) is the Rademacher complexity of F and ‖`‖Lip is the Lipschitz constant of ` as a function of its first coordinate. In particular, we have ‖`‖Lip = 1 for losses defined by (12).

heading: 3 LITERATURE
text: General surveys of the field of metric learning can be found in Bellet et al. (2015) and Kulis (2012). See also Chicco (2020) for a survey of recent applications in deep learning contexts. In these situations, the metric learning loss is sometimes referred to as a Siamese network.
Up to now, generalization guarantees in metric learning were only studied in the linear setting, i.e. for embeddings of the form (3) where L = 1 and φ(x) = x. In particular, all literature cited in this section deals with the linear case.
As discussed in Sections 1 and 2, in this paper we use the formal metric learning setting introduced in Verma & Branson (2015), where we assume that the data comes as a set of iid feature pairs with a label per pair, ((xi, x′i), yi) n i=1. In this setting, the empirical risk is given by (13). In the special case where the data comes with a label per feature, (xi, li)ni=1, one can use an alternative notion of empirical risk, given by
R̃f = 1 n(n− 1) n∑ i=1 ∑ j 6=i Lf ( (xi, xj),1{li 6=lj} ) , (14)
which is viewed as a second order U-statistic, see Cao et al. (2016). That is, instead of considering the input as a set of independently sampled pairs, which can be obtained from the (xi, li)ni=1 by, for instance, creating pairs out of consecutive samples, in (14) one considers all possible pairs. On one hand, compared to the risk R̂f defined by (13), for small datasets R̃f might make a somewhat better use of the data. On the other hand, R̃f is less general, since the data does not necessarily have to be generated by the label-per-feature setting. Indeed, consider the celebrated word2vec text embedding technique, Mikolov et al. (2013b), Mikolov et al. (2013a). In word2vec, tokens x and x′ should be mapped to similar vectors if x and x′ tend to appear as contexts of each other, and should be mapped to distant vectors otherwise. Equivalently, similar token pairs are extracted from “windows” of the text, while dissimilar pairs are sampled “contrastively”, i.e. i.i.d from a (version of) the marginal distribution. Clearly one can model this using the general setting described in Section 2, adopted in this paper. However, note that there are no labels l one can attach to the tokens x such that the distribution ((x, x′), y) can be described via the label-per-feature as above, with i.i.d samples (x, l). Moreover, even when the label-per-feature setting is applicable, evaluating (14) may be computationally difficult since the number of terms in the sum is quadratic in dataset size.
The generalization framework considered in this paper is that of the uniform generalization bounds, see Mohri et al. (2018). Alternatively, in Wang et al. (2019), Lei et al. (2020), the linear case of metric learning was studied in the framework of algorithmic stability (Bousquet & Elisseeff (2002), Feldman & Vondrak (2019), Bousquet et al. (2020)). In these works, stability, and consequently
generalization bounds, were obtained for an appropriately regularized empirical risk minimization (ERM) procedure. We note that these methods rely strongly on the (uniform) convexity of the underlying problem, and are unlikely to be generalized to non linear settings. In Bellet & Habrard (2015),Christmann & Zhou (2016), linear metric learning was studied in the framework of algorithmic robustness, Xu & Mannor (2012).
Finally, uniform bounds for the linear case were studied in Verma & Branson (2015), and similar results for the version of risk as in (14) were obtained in Cao et al. (2016). In particular it was shown in Verma & Branson (2015) that
Rn (F) ≤ b2 sup(A1)∈A ‖A1At1‖F√
n , (15)
where ‖·‖F is the Frobenius norm. Interestingly, when φ(x) = x, one can derive the single layer inequalities (7) and (8) from (15). Indeed, since ‖·‖F is a matrix norm, Bhatia (1997), we have ‖AAt‖F ≤ ‖A‖op ‖At‖F = ‖A‖op ‖A‖F for any A. This in turn can be bounded either as ‖A‖op ‖A‖F ≤ ‖A‖op ‖A‖2,1 or as ‖A‖op ‖A‖F ≤ √ k ‖A‖2,∞ · √ k ‖A‖2,∞. 2 However, as discussed in Section 1.2, there likely is no way to obtain the general (i.e. non-linear) statements (7) and (8) directly from the purely linear (15).
The bound (15) itself is derived in Verma & Branson (2015) using a relatively short elegant argument involving only the Cauchy Schwartz inequality. However, again, this argument can only be applied when φ is the identity. Similarly to the situation in classification, for the non-linear settings other arguments are required.

heading: 4 RESULTS
text: In this Section we introduce the full statements of the main results, Theorems 1 and 2, and overview the main ideas of the proofs. The full proofs are given in supplementary material Sections B and C.

heading: 4.1 NOTATION
text: We begin with some necessary notation. For a vector v = (v1, . . . , vm) ∈ Rm, the `p norm is denoted by ‖v‖p = (∑m j=1 |vj | p )1/p
. For a matrix A ∈ Rd×k, and 1 ≤ p, s ≤ ∞, denote ‖A‖p,s = ∥∥∥(‖A·1‖p , . . . , ‖A·k‖p)∥∥∥ s . That is, one first computes the p-th norm of the columns and then the s-th norm of the vector of these norms. Note that ‖A‖2,2 = ‖A‖2 is the Frobenius norm. Denote by ‖A‖op the spectral norm of A. Throughout φ : R → R will denote an activation/nonlinearity, with Lipschitz constant ‖φ‖Lip and such that φ(0) = 0.
The input features {(xi, x′i)}ni=1 ⊂ Rd × Rd, (see Sections 1,2) may be alternatively organized as two matrices, X,X ′ ∈ Rn×d, with rows xi and x′i respectively. If F is a family of functions from Rd × Rd to R, the Rademacher complexity of F given the inputs X,X ′ is defined by
Rn (F) = Rn (F , X,X ′) = 1
n Eσ sup
f∈F n∑ i=1 σif(xi, x ′ i), (16)
where σi are independent Bernoulli variables with P (σi = 1) = P (σi = −1) = 12 . Finally, recall that if A is a family of matrix tuples, A = (A1, . . . , AL), and ‖·‖∗ some norm on matrices, then for i ≤ L, ‖Ai‖∗ is defined as ‖Ai‖∗ = supA∈A ‖Ai‖∗.

heading: 4.2 STATEMENTS AND DISCUSSION
text: We have the following bound:
2‖A‖op ≤ √ k ‖A‖2,∞ is shown in supplementary material Section A
Theorem 1. Let A = {(A1, . . . , AL)} be a family of matrix tuples, Ai ∈ Rki−1×ki , such that k0 = d and kL = k. Denote W = max1≤i≤L ki. Let G be the associated family of embeddings (3), and F the associated family of distance functions, (2). Let {(xi, x′i)}ni=1 be inputs, such that ‖xi‖2 , ‖x′i‖2 ≤ b for all i ≤ n. Set αi = ‖Ai‖op, βi = ‖Ai‖2,1 and ρi = ‖φi‖Lip for i ≤ L. Then
Rn (F) ≤ O  1 n + log(2W ) [ log n+ 2 log(4b (∏L i=1 ρiαi ) ) ] √ n b2 ( L∏ i=1 ρiαi )2( L∑ i=1 β 2 3 i α 2 3 i ) 3 2  . (17)
Alternatively,
Rn (F) ≤ O  1 n + √ k ‖φL‖∞ b log(2W ) [ log n+ 2 log(4 √ k ‖φL‖∞) ] √ n ( L∏ i=1 ρiαi )( L∑ i=1 β 2 3 i α 2 3 i ) 3 2  . (18)
The general structure of this bound is inherited from the covering number bounds of G in Bartlett et al. (2017). In contrast to the bounds in classification, note that the dependence on the coefficients of Ai and on b is quadratic. This can not in general be improved upon. Indeed, consider the special case of RelU activations, φi(x) = max {0, x}. Then the family G is positively homogeneous with respect to the matrix weights: Let u = (u1, . . . , uL) be a tuple of scalars, ui ≥ 0, and if A = (A1, . . . , AL) denote by uA the matrix tuple (u1A1, . . . , uLAL). Recall that gA is the embedding induced by A, given by (3). Then we have
guA = ( L∏ i=1 ui ) gA. (19)
Since the definition ofF involves the squared norm, it follows from (19) that fuA = (∏L i=1 ui )2 fA and thus Rn (F) must be quadratically homogeneous in each of ui. On the other hand, as discussed in Section 1.1, when φL is bounded, it is possible to avoid the quadratic dependence. In this case we have the inequality (18) in Theorem 1.
We now briefly sketch the proof of Theorem 1. The argument is based on bounding the covering numbers N (FX,X′ , ε) of the set FX,X′ ⊂ Rn – the restriction of F to the input. As mentioned in Section 1.2, given such bounds, we bound Rn (F) by the Dudley entropy integral. To bound N (FX,X′ , ε), we represent FX,X′ as (a subset of) a Lipschitz image of the Cartesian product GX × GX′ , i.e. GX × GX′ Ψ7−→ FX,X′ for an appropriate mapping Ψ. Here GX and GX′ are the restrictions of G to the inputs. The covering numbers of GX where estimated in Bartlett et al. (2017), and using these estimates we derive bounds on the coverings of GX × GX′ and consequently of FX,X′ . The full details are given in Section B. Here we note that the Lipschitz constant of the mapping GX × GX′ 7→ FX,X′ can be estimated in two different ways, depending on whether φL is bounded, which result in the bounds (17) and (18).
We now state our second main result. Theorem 2. Let A = {(A1, . . . , AL)} be a family of matrix tuples, Ai ∈ Rki−1×ki , such that k0 = d and kL = k. Denote W = max1≤i≤L ki. Let G be the associated family of embeddings (3), and F the associated family of distance functions, (2). Let {(xi, x′i)}ni=1 be inputs, such that ‖xi‖2 , ‖x′i‖2 ≤ b for all i ≤ n. Set αi = ‖Ai‖op, βi = ‖Ai‖2,1 and ρi = ‖φi‖Lip for i ≤ L. In addition, set a = ‖AL‖2,∞. Then
Rn (F) ≤ O 8bk n ( ρLa L−1∏ i=1 ρiαi ) + 8kb2 log(2W ) log n√ n ( ρLa L−1∏ i=1 ρiαi )2(L−1∑ i=1 β 2 3 i α 2 3 i + 1 ) 3 2  . (20)
Rn (F) ≤ O 8 ‖φL‖∞ k n + 8 ‖φL‖∞ kb log(2W ) log n√ n ( ρLa L−1∏ i=1 ρiαi )( L−1∑ i=1 β 2 3 i α 2 3 i + 1 ) 3 2  . (21)
The approach we take here in Theroem 2 is as follows: Note that every element f ∈ F can be written as a sum
fA(x, x ′) = ‖gA(x)− gA(x′)‖22 = k∑ j=1 fj,A(x, x ′), (22)
where fj(x, x′) = (g(x)j − g(x′)j)2 ∈ R is the squared difference on the j-th coordinate. For a fixed j ≤ k, denote by G′j the family of the coordinate functions, gj : Rd → R, where g ∈ G, and by F ′j the corresponding family of differences fj(x, x′). Note that G′j is induced by the same matrix tuples A as the full G, with the exception of the last layer. Similarly to the arguments in Theorem 1, we can obtain bounds on Rn ( G′j )
from the results in Bartlett et al. (2017). However, then we proceed differently. We first bound Rn ( F ′j ) in terms of Rn ( G′j )
(Lemma 9, supplementary material), and then use the decomposition (22) to obtain that Rn (F) ≤ ∑k j=1 Rn ( F ′j ) . The full details are given in supplementary material Section C.

heading: 5 EXPERIMENTS
text: In this section we are interested in the following question: How do the matrices AL – the weight matrices of the last layer of the network – look for networks trained on standard datasets, with standard training procedures. In particular, do we obtain sparse or dense weights?
Recall that the notion of “dense” in this paper refers the specific condition that
‖A‖2,1 ≥ const · k · ‖A‖2,∞ and ‖A‖op ≥ const′ · √ k · ‖A‖2,∞ (23)
holds over a range of values k. That is, we look at several neural networks trained with the metric learning cost (12) on a fixed dataset, where all networks have the same architecture except the size of the output layer k. If the condition (23) holds3 for a range of values k, we say that the problem is in the dense regime. For such a problem, the bounds of Theorem 2 would asymptotically be stronger than the bounds of Theorem 1. If the condition (23) fails, that is, for instance, the ratio ‖A‖2,1 /(k · ‖A‖2,∞) exhibits strong decay with k, then we say that the problem is in the sparse regime, and the bounds of Theorem 1 would be better.
We demonstrate that for MNIST data, trained with SGD and no regularization, i.e. the standard deep learning training procedure, the weights are dense to a good approximation. On the other hand, for the 20newsgroup dataset, trained with `2 regularization, the weights are sparse.
MNIST (mnist Dataset (2005)) is the standard dataset of handwritten digits and the 20newsgroups (20newsgoups Dataset (2010)) consists of newsgroups emails, labeled according to the group. To make computation and illustrations simpler, 20newsgroups is restricted to the first 10 labels.
To perform the optimization, we sample feature/label pairs (x, l), (x′, l′) independently from the train set, and minimize the loss using SGD on batches of such pairs, until convergence. The precise
3As discussed in Section 1.1, we have shown that the first condition in (23) implies the second, for large k. Nevertheless, as a sanity check, in what follows we evaluate both conditions.
loss that we use is
`(x, x′, l, l′) = 9 · ρ(x, x′) · 1{l=l′} +ReLU(1− ρ(x, x′)) · 1{l 6=l′}, (24) where ρ(x, x′) is the distance after the embedding, given by (1). This loss is a version of the loss `S,D(a, y) introduced in Section 2, with S = 0, D = 1, where the same class case is weighted by 9, to compensate for the fact that {l 6= l′} pairs appear 9 time more frequently in the data. Additional details on the setting and the experiments, as well as the implementation source code, are given in supplementary material Section D.
We now describe the results in more detail. Consider first the single layer architecture, L = 1, with relu activation. That is, we train single layer networks of size d×k, where d is the problem’s original feature dimension, and k varies in the range 50 to 5000. For each trained network, we evaluate the quantities of interest – the ratios ‖A‖2,1 /(k · ‖A‖2,∞) and ‖A‖op /( √ k · ‖A‖2,∞) for MNIST, and unnormalized ratios ‖A‖2,1 / ‖A‖2,∞ and ‖A‖op / ‖A‖2,∞ for 20newsgroups (see details below). These experiments are represented by orange lines in Figures 2a,2b.
Figure 2a represents the results for the MNIST dataset. In particular, the solid orange line shows the ratio ‖A‖2,1 /(k · ‖A‖2,∞) and the punctuated orange line shows the ratio ‖A‖op /( √ k · ‖A‖2,∞). To simplify the comparison, since we are only interested in change w.r.t k, all curves are normalized to have value 1 at k = 50. In such plot, the perfect dense regime behaviour would look as a straight horizontal line with value 1 for all k. While the actual lines exhibit some decay, this decay is slow. Compared to k = 50, at k = 5000 the orange lines drop by a factor of 2.5, while k grows by a factor of 100. Thus we conclude that in this case the norms are well described by the dense regime.
Next, Figure 2b represents the results for the 20newsgroups dataset. While MNIST is generally nicely behaved, the 20newgroups is not. In particular, it consists of about n = 7500 samples in dimension d = 15000 > n, and unregularized SGD training would severely overfit the train data. Thus in this case we use the simplest possible regularization term, the `2 regularization λ·‖A1‖2,2 /k , with λ = 0.01 in all experiments.
The orange lines in Figure 2b describe the ratios ‖A‖2,1 / ‖A‖2,∞ (solid) and ‖A‖op / ‖A‖2,∞ (punctuated). Note that these ratios are not normalized by k. The curves are still normalized to be 1 at k = 50. Thus, the approximately straight lines we observe in Figure 2b indicate that the above norm ratios practically do not change as k grows, implying that the problem is firmly in the sparse regime.
The blue lines in Figure 2 describe similar experiments for a two layer architecture, L = 2. In these experiments, the size of the first layer A1 was fixed, d × 500, with leaky relu(0.2) activation. The second layer, A2, was of size 500 × k ,varying with k. The regualrization term for 2-newsgroups was λ ( ‖A1‖2,2 /500 + ‖A2‖2,2 /k ) , again with λ = 0.01. The ratios in Figure 2 were this case computed for the second layer, A2. One can see that the conclusions for L = 2 are similar: MNIST is in the dense regime, while 20newsgroups is sparse.
Each experiment was repeated 6 times, and every value in Figure 2 is a mean over 6 outcome values. Every value also has an error bar which indicates the magnitude of the standard deviation around the mean. However, in most cases, these bars are small compared to the magnitude of the mean are not visible in the figures.

heading: 6 CONCLUSIONS AND FUTURE WORK
text: In this paper we have obtained the first generalization guarantees for multilayer non-linear metric learning. We have introduced two types of bounds, which are appropriate for sparse and non-sparse regimes of the weightsAL, and we have empirically shown that both regimes may occur in common SGD training settings.
We conclude with an open question: When there are two different bounds on the same quantity, it is natural to ask whether there is a third bound, that interpolates both bounds (i.e. is as strong as both of them) and has a simple form. As discussed in Section 3, for the linear case there indeed is such a bound. It thus would be of interest to understand whether one can obtain a similar strengthening for the non linear multilayer case.

Review summaries:
In this paper, the authors look at the Rademacher complexity of the family of Euclidean metrics learned on a data set via an $L$ layer network where the activations functions are Lipschitz. The idea behind the proof is to use the bounds for $\epsilon$ net for the embedding network from Barlett, Foster, and Telgarsky 2017. This net, then provides a net for space of metrics with only requiring a change in the constants. Using this net, the authors then use standard arguments to bound the Rademacher complexity.   Specifically for the metric learning setting they show that this bound can be improved. 

The paper provides two new generalization bounds for non-linear metric learning with deep neural networks, by extending results of Bartlett et al. 2017 to the metric learning setting. The two bounds have been called the 'sparse' and 'non-sparse' bounds and differ in the norm used for the last layer. Experiments are performed where it is shown that either bound may dominate on real datasets.