Two Regimes of Generalization for Non-Linear Metric Learning
Authors: Mark Kozdoba
Shie Mannor
Venue: ICLR 2022 Submitted (2022)
Keywords: metric learning
guarantees
sparsity

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,\infty)$-norm at the last layer, and are significantly stronger when the last layer is dense. In addition, we empirically evaluate the behavior of the bounds for networks trained with SGD on the MNIST and 20newsgroups datasets. In particular, we demonstrate that both regimes occur naturally on realistic data.

Under review as a conference paper at ICLR 2022
Two REGIMES OF GENERALIZATION FOR NON- LINEAR METRIC LEARNING
Anonymous authors Paper under double-blind review
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. Specifi- cally, 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)-orms of the weight matrices, while the second regime bounds use the (2, -norm at the last layer, and are sig- nificantly stronger when the last layer is dense. In addition, we empirically eval- uate 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.
INTRODUCTION
Metric Learning, Bellet et al. (0155), the problem finding a metric o on the space of features, such that p reflects some semantic properties of given task. Generally, the input can be thought of as a set of labeled pairs {(<x,, xf), ys) ) where Iú, x4 E RRd are the features, and yi is the label, indicating whether 2; and x should be close in the metric far apart. For instance, in face identification, Schroff et al. (2015). features 2; and x corresponding to the same face should be close in p. 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 3/4 1 I; and w have the same original label and y, 0 otherwise Davis et al. (007)); Weinberger & Saul 20099 Cao et al. () Khosla et (0200: Chicco (2020).
The metric p is typically assumed to be the Euclidean metric taken after linear or non-linear embedding of the features. That is, we consider parametric family G of embeddings into k- dimensional space, Rdd + RR and set
p(a,x') = oo(x, = (19(x) g(x')
As an example, Figure shows (SNE plots, Maaten & Hinton (008)) of the classical 20newsgroups dataset. Figure Ta was generated using the regular bag of words representation of the data (see Sections 5 and D for additional details) while Figure [bb was generated by applying tSNE to an embedding of the data (of the form (3) below) learned by minimizing 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 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 family of embed- dings G. provide bounds, that hold uniformly for all g E G, the difference between the expected value the loss and the average value of the loss on the train set; see Section 2 for a formal defini- tion. Such bounds guarantee, for instance, that the train set would not be overfitted. Given family
Note that p in not strictly a metric. Nevertheless, this terminology common.

---

Under review as a conference paper at ICLR 2022
40
200
(a) Raw features, after normalization and 500 dim. PCA.
(b) Learned embedding, k=50, test set.
tSNE plot of the 20newsgroup data, restricted the first 10 labels. Points are colored according to the label.
Figure I:
of embeddings 9, consider the family FF functions f: R x Rd - of the form
F F= (f - g E 9}.
We refer to these the distance functions, which map 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 the Rademacher complexity H,, (F) of the family of the scalar functions F. Therefore what follows, we discuss directly the upper bounds on R. (F) for various families G. We refer Section for formal definitions and details the relation between FRR, (F), and generalization bounds.
1.1 OVERVIEW OF THE RESULTS
In this paper our goal is to study generalization bounds for neural network type non-linear embed- dings g IR + R given by neural networks of depth L > 1. Specifically, we consider embeddings of the form
(xx) (2(x) d2 (4i. (ÓL-1 (A% ... (Aiz)...)))
(3)
where A = [AI....,A] is a tuple of matrices such that A, e - xk; for i = 1.... . L, and k; the layer widths, with ky = and k2 k. The activations d; R - E are assumed to be Lipschitz, with [l S Pt. and act on vectors R 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, will be denoted by F.
In the context of deep learning generalization guarantees for classification, there exists a large body of work various complexity bounds related to the family of mappings G. The current strongest uniform bounds were given Bartlett et al. (2017) (see also Neyshabur et al. (2018)). Our goal here 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 few norm definitions: For matrix A E Rext || is the spectral norm, and set ||Al,,,1 = Ei= |A where A.; is the i-th column of A. For family A of matrix tuples, A (A1, AL) A, for i S we set
|| sup || and ||A:112,1 = sup ||A:l1., AEA
(4)
AEA
Thus ||A.ll.p I|A: are the largest respective norms of the component A; in A. With this notation, our first result is the following bound (up to logarithmic factors):
2
Ri (F) 50
6² Fn
I1Aillor)
(5)
LA
Here is an upper bound on inputs, || ||ا;|| < for < n. The full statement is given in Section Theorem [] This bound can be regarded natural extension of the bounds of Bartlett
2

---

Under review as a conference paper at ICLR 2022
et al. (2017) to the metric learning setting. Indeed, it uses the same parameters the || and || norms. The quantity (TT Pi [IAellop) 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 dimension free, in the sense that the depth I. and the the layer widths k; 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, now show that in the metric learning setting, one can improve the bound in some situations, by using the ||AA| 2,00 layer. In Theorem
maxis* k |Ailll norm at the last
2
Section
we show the following:
( Vn
L-1 II pi (AAlllp
Ri (F) S0
(6)
||A::
We refer to (5) 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, 1. this case, the bounds read
112
11 Lip
||Allop ||Al|
Hi (F) So
(7)
Vn
and
kb² |001 R. (F) < 0
10112
Lip
||A
2,30
(8)
VT
where the family of weights matrices, E RRdck, & an activation, and ||AI]. . = su |||. where |1- is one of I1-112,1 2l- I1p- Consider first the case where A contains non sparse matrices A E A. These are the weights A where all & neurons have roughly the same norm, or equivalently,
|A * ||Al1,,,00
We refer to this condition as the dense regime. Note that ( holds true for neural networks at initialization, and in Section we observe empirically that this also holds for SGD trained networks on MNIST data. Next, when (9) holds, we also have that
|| ~ /k Al
(10)
2,00 for any A, and p implies ||4|l.p 2 const . V ||Al| (see Lemma 3 in supplementary material A The condition 10) will be also experimentally verified for
Indeed, one has ||All.pp I V |||||
10P into 7 and (). we obtain that in the non-sparse regime, (8) is stronger than (7) by a factor v k, significant improvement. On the other hand, when A is sparse, with most output neurons zeroed out (e.x. ||A||2_1
MNIST data. Now, substituting 99)
|| op = l| 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, 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 the dependence on & is similar: With all other k; fixed, (6) will be better by a factor of Ve 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 de- pendence of the bound the coefficients of the weights in (5) and (6) is quadratic. As show in Section this in general unavoidable, due to the quadratic form of the metric (T). However, if the highest activation, ΦL is bounded, such for instance the sigmoid o(x) (I (1+c -e-=)-1 then one can obtain linearly homogeneous dependence on the layer weights. thus potentially significantly improving the bounds. These bounds are given in (18) and (2T) Theorems and respectively. For comparison, in the single layer case the sparse and non-sparse bounded Φ bounds are given by
R, (F) 50 (
Vib [1 | rap ||A1|2.1 and R. (F) (F) 50
kb |1 10]l 1,A
/n.
vn
(11)
3

---

Under review as a conference paper at ICLR 2022
where |/ is the upper bound on the values of Φ.
1.2 METHODS
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 (002)) with the analysis of the specific structure induced by the metric learning problem, l.e. the structure of the family F(g), when G is fixed.
Theorems I and 2 exploit this structure differently. In Theorem Twe directly estimate the covering numbers of F in terms of those of g. Note that, for instance, and G are function families on different domains, and thus such estimates require some care. Once the estimates obtained, however, we bound R., (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 ① This allows a decomposition of the problem into problems, each of which has k 1, and yields bounds which depend on || and k, rather than on || ||AA|1,,- While this may seem rougher bound at first glance, as discussed above it is in fact much stronger than Theorem T in some situations.
sum.
Finally, we note that up now generalization for metric learning was only studied in the linear case (see Section for a detailed discussion). In particular, uniform bounds were derived in Verma & Branson (2155) and in Cao et al. (2016). Interestingly, already in the basic situation where L but ((z) + (i.e. single layer but non-linear activation), one can not deduce our bounds 77) 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 (I). As result, somewhat surprisingly, even to obtain the linear instead of quadratic homogenity, as in [I] 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 non- linear metric learning. In particular, we introduced two types of bounds, which are appropriate for sparse and non-sparse weights Ag. We have also shown that by using a bounded last layer activation, one may avoid the quadratic dependence of the bound 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 follows: In Section 2 we overview the necessary background on metric learning and generalization. Literature and related work are discussed in Section In Section 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 and concluding remarks are given in Section 6
4
2 METRIC LEARNING BACKGROUND
In this paper we are assuming that the training data is given as set {((2,, x.). of labeled feature pairs, which we assume to be sampled independently form some distribution D on gd x Rd Y. where 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. 2! may depend on 2;.
The quality of the embedding 9 on a data point ((x, x²), y) is measured via a loss function which usually depends on ((x, ", y) only through the metric. That is, given embedding g E G, let I T F be the corresponding distance function, f(x,aa') = Pg (xt, a') (see (2). We assume that there is fixed function data point x'), 3) is given by Ly((a, x').)) v) = ((f(x,, x4). y1) = E(p, (2, x4), v1). A typical
R Y + [0, 1], such that the loss of the distance function f E F on
example of loss is the following version of the margin loss:
(s. RRLU (a S) yf-=1 ReLU (D a)
(12)
otherwise,
where (z) max (). As discussed in Section I this loss embodies the principle that x') should be close iff y = 1, by penalizing distances above S when y = 1 and penalizing distances below D otherwise.
4

---

Under review as a conference paper at ICLR 2022
The overall loss the data, or the empirical risk, is given by
Σ (() 1 72
R
(13)
The expected risk is given by Ry ((x='')) ((1, v'), The uniform generalization prob- lem 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, Ry R,, is small for all f F.
Finally, since {((x;, 2(), == are independent, standard results imply that to control the uniform generalization bounds of the risk, it 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).
log 8-1
sup R2- Rg S 21 R, (F)
FEF
2n
holds with probability at least Here R. (F) is the Rademacher complexity of F and || is the Lipschitz constant of & as function of its first coordinate. In particular, we have [|e]lzsp for losses defined by (2)).
3 LITERATURE
General surveys of the field of metric learning can be found in Bellet et al. (2015) and Kulis (2012). See also Chicco (2020) for survey of recent applications in deep learning contexts. In these situa- tions, the metric learning loss is sometimes referred to as a Siamese network.
Up now, generalization guarantees in metric learning were only studied in the linear setting, i.e. for embeddings of the form (3) where L = and d(x) = x. In particular, all literature cited in this section deals with the linear case.
As discussed in Sections T and2 in this paper we use the formal metric learning setting introduced in Verma & Branson (2015). where we assume that the data comes as a of iid feature pairs with a label per pair, ((x;, z(), 31 )= - In this setting, the empirical risk is given by (13). In the special
case where the data comes with a label per feature, (I,, 4) one can use an alternative notion of empirical risk, given by
R n(n 1) jهن
EE L, ( ((.,))))
(14)
which is viewed second order U-statistic, see Cao al. (2016). That is, instead of considering the input set of independently sampled pairs, which can be obtained from the (x;,4)" 4)," by, for instance, creating pairs out of consecutive samples, (14) one considers all possible pairs. On one hand, compared to the risk ft defined by (3). for small datasets RG might make a somewhat better use of the data. On the other hand, Rg is less general, since the data does not necessarily have be generated by the label-per-featur setting. Indeed, consider the celebrated word2vec text embedding technique, [Mikolov et al. (2013)), Mikolov et al. (2013a). In word2vec, tokens æ and x' should be mapped similar vectors 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 one can attach to the tokens such that the distribution ((z, z²), y) can be described via the samples (z, 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 quadratic in dataset size.
above, with i.i.d
The generalization framework considered in this paper is that of the uniform generalization bounds, see Mohri et al. (2018). Alternatively, in Wang 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 al. (2020)). In these works, stability, and consequently
5

---

Under review as a conference paper at ICLR 2022
generalization bounds, were obtained for appropriately regularized empirical risk minimization (ERM) procedure. We note that these methods rely strongly on the (uniform) convexity of the un- derlying problem, and are unlikely to be generalized to non linear settings. In [Bellet & Habrard Christmann & Zhoo (2016), linear metric learning was studied in the framework of algorith- mic robustness, Xu & Mannor (2012).
Finally, uniform bounds for the linear case were studied in Verma & Branson 2013), and similar results for the version of risk as in (14) were obtained in Cao (2016). In particular it was shown in Verma & Branson (2015) that
6 A A | |
Rr (F)
(15)
Vn
where ||-||= is the Frobenius norm. Interestingly, when ((x)) I, can derive the single layer
inequalities (7) and 8 from
(15). Indeed, since ||-IIp is a matrix norm, Bhatia (1997). we have |All op || for any A. This in turn can be bounded either as |A as ||A op || S V1l1-A12,.0 v ||All2,.0 However, as there likely is no way to obtain the general (i.e. non- mon-linear) statements 7
||AA' I ||| op
||AAllop ||A|| < ||
op
discussed in Section
1.2
and (8) directly from the purely linear (15)
The bound (15) itself is derived in Verma & Branson 2013) 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 non-linear settings other arguments are required.
4 RESULTS
In this Section introduce the full statements of the main results, Theorems and and overview the main ideas of the proofs. The full proofs are given in supplementary material Sections B and
4.1 NOTATION
We begin with some necessary notation. For vector v (Vi,..., ......,uuu. Umn) E R the lp norm is
denoted by ||u||, (E/z (1s))) 1/p For matrix A E naxk and 1 S p,
denote
||Allp.s = (1 ...., [.A.xllp) 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 2.2 ||Al]] is the Frobenius norm. Denote by ||All.op the spectral norm of A. Throughout á R - R will denote activation/non- linearity, with Lipschitz constant ||oll and such that <(0) 0.
The input features ((x,, =1))=111111 C Rd x Rd, (see Sections 2 may be alternatively organized as two matrices, X, X' E Rnxd with rows I; and x respectively. If F is a family of functions from Rd x Rdd to R, the Rademacher complexity of F given the imputs X, X' is defined by
1
R, (F) = Ri (F, X') = Eg sup
oi off(,,
(16)
n fEF 1=1
where o, are independent Bernoulli variables with P Po, = 1) IP (a, = -1)
11== =
Finally, recall that if A is family of matrix tuples, A = (AI,... At), and ||-11, some norm on matrices, then for S L, [|A:ll, is defined as ||Ai = suD ||Ab||.
4.2 STATEMENTS AND DISCUSSION
We have the following bound:
11
V 1All,,, shown in supplementary material Section

---

Under review as a conference paper at ICLR 2022
Theorem 1. Let A {AA be a famity of matrix tuples, A, Rki-i such that
ko = and KL = k. Denote W = maxısis L ks. Let G be the associated family of embeddings
B]. and F the associated family of distance functions. (2). Let {(I,; =])};=1 be inputs, such that
Fi mill2 |a'lla S for all i I n. Set 0;; = ||A:] op Be = ||iill,, and Pi = 1 Lpp for S L. Then
1 + n
log(2W)
logn + 2 2log( 4bb (IT-= pras)) 12
7
R (F) 50
II piass
vn
(17)
Alternatively
v 110 blog(2W) logn 2og((4V] [
L
Rn 50
- +
1
II pia
n
(18)
The general structure of this bound inherited from the covering number bounds of g Bartlett et al. (2017). In contrast to the bounds in classification, note that the dependence on the coefficients of A, and on is quadratic. This can not in general be improved upon. Indeed, consider the special case of RelU activations, dx(x)) max {0, J.. Then the family G is positively homogeneous with respect to the matrix weights: Let u = (u,,.... .,.....,.. ur.) be a tuple of scalars, u; 2 O, and if A
(Ai,.... A.) denote by u.A the matrix tuple (u1A1,,... AL). Recall that 9. is the embedding
induced by A, given by (3). Then we have
L πI
9uA =
U1
9A-
(19)
Since the definition of F involves the squared norm, it follows from (19 that fuA (IT- ui) fA and thus R. (F) must be quadratically homogeneous in each of u4:
On the other hand, as discussed in Section 1.1 when Φr is bounded, is possible to avoid the quadratic dependence. In this case have the inequality [8] in Theorem I
The argument is based on bounding the covering numbers (Fx,x,, ex) of the set Fx,x² R the restriction of F the input. As mentioned in Section 1.2 given such bounds, we bound RR, (F) by the Dudley entropy integral. To bound
We now briefly sketch the proof of Theorem 1
((Fx,x,,)), E), we represent Fx,x² as (a subset of) Lipschitz image of the Cartesian product Gx x
9x., i.e. 9x 9x : Fx,x' for an appropriate mapping V. Here 9x and Gx 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 x Gx and consequently of Fx,x The full details are given in Section B Here we note that the Lipschitz constant of the mapping 9x x Gx. + Fx.x* can be estimated in two different ways, depending on whether &L is bounded, which result in the bounds (17 and (T8).
We now state our second main result.
Theorem 2. Let A = {(AI,,..,, Ar.) be a family of matrix tuples, A; E Rki-iiks,, such that kn d and kt. k. Denote W maxigist. ky- Let G be the associated family of embeddings B}. and F the associated family of distance functions, (2). Let {(I,, (e,,z))) H be inputs, such that
Telll ||%ا| < b for all < n. Set a, = Aelllo B, = Aill,, and pt | Lip for L. In
addition, set a= = ||.Ar122,0r Then
86k
8k62 log(2W) log
Ri (F) 5
pLa
p:a;;
+
PLa
n
i=1
(20)
8 8112ell
8 811bell.0 kb kblog(2W)
logn
1--1
1-
3
50 Rg 50
Pra
II
pia;
+1
n
n
i=1
(2))

---

Under review as a conference paper at ICLR 2022
MMST Ratios
Marwogrrup Nam Ratios innornaiioe
Lia
14
Li2 Miul 1Ajod
11
Led MaBalleeeeeA
0.0
08
0.0
(a) MNIST, Norm Ratios
(b) 20newsroups, Unnormalized Norm Ratios
Figure 2: Dense and Sparse Regimes Demonstrated on MNIST and 20newsgroups Data
The approach we take here in Theroem is as follows: written as sum
Note that every element f F can be
h
fA(x, (((x,x')=1l9a((1)) 2)(22)1 Ina(s,,'')
(22)
J=1
where (g(z); fixed < k. denote by Gj the family of the coordinate functions, 9j Rd - R. where y E G. and by F3j the corresponding family of differences fz(xxx')) Note that G 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 I we can obtain bounds R, (G)) from the results in Bartlett et al. (2017). However, then we proceed differently. We first bound Ri (F)) in terms of R., (9') (Lemma 9 supplementary
E R is the squared difference on the j-th coordinate. For
material), and then use the decomposition 22 obtain that Ri (F) S Σド= R (F)). The full details are given in supplementary material Section
5 EXPERIMENTS
In this section we are interested in the following question: How do the matrices A - 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
|| 2 const k- ||A||2.00 and || 2 const' vk- ||A||2.00
(23)
holds over 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. the condition (23) holds 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 Theorem If the condition (23) fails, that is, for instance, the ratio ||All (k .|All2..o) exhibits strong decay with k, then say that the problem is in the sparse regime, and the bounds of Theorem 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 & 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 (a, I), (x',2') independently from the train set, and minimize the loss using SGD on batches of such pairs, until convergence. The precise
As discussed in Section 1.1 we have shown that the first condition in 23 implies the second, for large k.
Nevertheless, as sanity check, what follows we evaluate both conditions.
8

---

Under review as a conference paper at ICLR 2022
loss that use is
((x,'',11'' = 9 p(x, - ((=-)) +
2')) ((ser)
(24)
where x²)xx") is the distance after the embedding, given by I). This loss is version of the loss fg,D(a, (a, y) introduced in Section with 5 = 0, = 1, where the same class case is weighted by 9, to compensate for the fact that { }n} 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, I. = 1, with relu activation. That is, we train single layer networks of size d x where d the problem's 's original feature dimension, and & varies in the range 50 to 5000, For each trained network, we evaluate the quantities of interest - the ratios ||All2,1 (k ||A|||, cc) and ||AAllop Dallop//C6 /(vk- 2|Alll, for MNIST, and unnormalized ratios 2 / || and || lop ||All for 20newsgroups (see details below).
These experiments are represented by orange lines in Figures 2b
Figure 2a represents the results for the MNIST dataset. In particular, the solid orange line shows the ratio || (k: (l)) and the punctuated orange line shows the ratio || /VV. 11, To simplify the comparison, since we are only interested in change w.r.t k all curves are normalized to have value 1 at & = 50. In such plot, the perfect dense regime behaviour would look as straight horizontal line with value for all k. While the actual lines exhibit some decay, this decay is slow. Compared to k = 50, at & = 5000 the orange lines drop by a factor of 2.5, while k grows by factor of 100. Thus we conclude that in this case the norms are well described by the dense regime.
Next, Figure 26 represents the results for the 20newsgroups dataset. While MNIST is generally nicely behaved, the 20newgroups not. In particular, it consists of about n = 7500 samples in dimension d = 15000 > and unregularized SGD training would severely overfit the train data. Thus in this case we use the simplest possible regularization term, the & regularization X- A111,1 with = 0.01 in all experiments.
The orange lines in Figure 2b describe the ratios ||Al|,, / /|Al12, (solid) and ||Allop ||Al|2, (punctuated). Note that these ratios are not normalized by k. The curves are still normalized to be at k 50. Thus, the approximately straight lines we observe in Figure 26 indicate that the above norm ratios practically do not change as l grows, implying that the problem is firmly in the sparse regime.
The blue lines in Figure experiments, the size of the first layer A₁ was fixed, d x 500, with leaky (0.2( activation. The second layer, A2, was of size 500 x it ,varying with k. The regualrization term for 2-newsgroups
diguredde describe similar experiments for two layer architecture, L = 2. In these
was A (1141l222//00 /500 + A2ll2, 11k again with À 0.01. The ratios in Figure 2 were this case computed for the second layer, Ag. One can see that the conclusions for I. 2 are similar: MNIST is in the dense regime, while 20newsgroups is sparse.
Each experiment was repeated 6 times, and every value in Figure 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.
6 CONCLUSIONS AND FUTURE WORK
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 weights AL, 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 simple form. As discussed in Section for the linear case there indeed is such bound. It thus would of interest to understand whether one can obtain a similar strengthening for the non linear multilayer case.

---

Under review as a conference paper at ICLR 2022
REFERENCES
20newsgoups Dataset. 20newsgoups dataset.
Betaasets/reaawwordddooo http::attttttteeeeerooo--a--aaa- 2010.
Peter I.. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3, 2002.
Peter I. Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalizedd margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 2240-6249, 2017.
Aurélien Bellet and Amaury Habrard. Robustness and generalization for metric learning. Neuro- computing, 151: 00::2599677,, 2015.
Aurélien Bellet, Amaury Habrard, and Mare Sebban. Metric learning. Synthesis Lectures on Artifi- cial Intelligence and Machine Learning, 9(1):1-15,, 2015.
R. Bhatia. Matrix Analysis. Graduate Texts in Mathematics. Springer New York, 1997.
Olivier Bousquet and André Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. 610-626. PMLR, 2020.
Qiong Cao, Zheng-Chu Guo, and Yiming Ying. Generalization bounds for metric and similarity learning. Machine Learning, 102(1):115-132 2016.
Davide Chicco. Siamese neural networks: An overview. Artificial Neural Networks, pp. 73-94, 2020.
Andreas Christmann and Ding-Xuan Zhou. On the robustness of regularized pairwise learning methods based on kernels. Journal of Complexity, 37:1-33, 2016.
Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon. Information-tthoortic metric learning. Proceedings of the 24th international conference on Machine learning. pp- 209-216 2007.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algo- rithms with nearly optimal rate. COLT, 2019.
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. arXiv preprint 2132:2004.113622. 2020.
Brian Kulis. Metric learning: A survey. Foundations and trends in machine learning, 5(4):287-364, 2012.
Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper Generalization Bounds for Pairwise Learn- ing. In Advances in Neural Information Processing Systems, 2020.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 2008.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint arXiv:1301.378. 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp. 3111-3119, 2013b.
mnist Dataset. Mnist dataset. https: /tta:e///er.... http://///eerreeoo////aaaaaaaaa/ 2005.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning.
The MIT Press, second edition edition, 2018.
10

---

Under review as a conference paper at ICLR 2022
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally- normalized margin bounds for neural networks. International Conference on Learn- ing Representations, 2018.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the IEEE conference on computer vision and pattern recognition, pp. 815-823, 2015.
2015.
Nakul Verma and Kristin Branson. Sample complexity of learning mahalanobis distance metrics. In C. Cortes, N. Lawrence, D. Lee. M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28, 2015.
Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Sci- ence. Cambridge University Press, 1 edition, 2018.
Boyu Wang, Hejia Zhang. Peng Liu, Zebang Shen, and Joelle Pineau. Multitask metric learning: Theory and algorithm. In Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research. PMLR, 2019.
Kilian Q. Weinberger and Lawrence Saul. Distance metric learning for large margin nearest neighbor classification. J. Mach. Learn. Res., 10, 2009.
Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86(3):391-425 423,, 2012.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-550, 2002.


Reviews:
[{"review_id": "bmXMP79ttn_", "reviewer": "Reviewer_zFNY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strengths:\n\nThe paper exploits the structure of metric learning to extend the uniform generalization bound of Bartlett et al 2017 and a new 2-infinity bound for the metric learning setting.\n\nExperiments show both bounds are useful depending on data/training.\n\n\nWeaknesses:\n\nTheorem 1 seems like straightforward application of Bartlett et al 2017\n\nNovel technical insights for the new results e.g. Theorem 2 could be more clearly stated. E.g. the novel technical insight for theorem 2 is very briefly stated (e,g. it would be nice to have informal or formal statement of Lemma 9 in main paper).\n\nThe sparse and non-sparse regimes are defined based on when one bound dominates the other, but it is less clear what data or training properties can result in one or the other. E.g. what regime is expected when MNIST is trained with regularization or 20newsgroups without (or with less regularization). More thorough experiments say with more datasets and degrees of regularization can potentially give interesting insights. ", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall the paper gives interesting generalization bounds for the metric learning setting but does not seem ready for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bAqMulVpkzN", "reviewer": "Reviewer_w4wy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "**Strength**\n\nThe authors show that for the metric learning setting the bounds from Bartlett, Foster, and Telgarsky can be improved by checking if the last layer of the network is dense. \n\nThe authors then show that this setting where the last layer is dense occurs in practice. \n\nThe authors show that their bound matches known bounds for the linear case. \n\n**Weakness**\n\nWhile the bound is an improvement, I do not think the improvement is significant. This is my main concern. See the discussion in the questions section. \n\nI would have liked more discussion on how the bounds translate to generalization error bounds? Specifically, are they meaningful empirically?\n\n**Questions**\n\n1) I am not sure how the bounds are dimension free. The depth $L$ explicitly occurs in the bound, we have products and sums of $L$ terms. Second, as we increase the width, unless we decrease the magnitude of each entries, the matrix norms will increase as well. Hence both factors the width and depth play a factor in the bound. \n\n2) How big do we expect the matrix norms to be? Because that determines that size of the bound. \n\nAt initialization, (if we use something like LeCun initialization), we expect each column to have norm 1 (due to the normalization) and so we expect $\\\\|A\\\\|\\_{2,1} \\sim k$. Then from your lemma we expect $\\\\|A\\\\|\\_{op} \\sim \\sqrt{k}$.   Then if we have a \"square\" network (so $k_i$ are all equal), then \n\n$$\\sum_{i=1}^L \\frac{||A_i||\\_{2,1}^{2/3}}{||A_i||_{op}^{2/3}} \\sim Lk^{1/3}$$. \n\nSo ignoring the log factors, assuming 1-Lipschitz activation maps, we get that the bound from theorem 1 looks like\n\n$$ \\frac{b^2}{\\sqrt{n}}L^{3/2}k^{L+1/2}$$\n\nSo first, this very explicit depends on $k$ and $L$. Second, an improvement of $\\sqrt{k}$ is an improvement, however, if $L$ is large I don't think it is significant. \n\nOkay so this was at initialization, but maybe during training the norms change significantly. Do the authors know if this occurs in practice. My concern is if we are in the large width limit, then the results from Neural Tangent Kernel theory will tells us that training didn't change the norms. \n\n3) I do not fully follow the discussion about the quadratic dependence. Specifically, are the authors claiming that the complexity must be lower bounded by $\\Pi_i \\|A_i\\|_{op})^2$? If so then the improvement in the bound is significant. \n\n\n\n\n", "summary_of_the_paper": "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. \n\nSpecifically for the metric learning setting they show that this bound can be improved. ", "summary_of_the_review": "Overall the paper presents a nice adaptation of the bounds from Bartlett, Foster, and Telgarsky for the problem of metric learning. I think understanding metric learning is an important problem in machine learning. However, I am not convinced that the improvement in the bounds is significant. However, my opinion on this can be changed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RMMuZkxCsrB", "reviewer": "Reviewer_nCbx", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths: \nIt is indeed a promising research direction to regard neural networks as a special nonlinear metric embedding.\n\nWeakness:\n1.\tThis paper only uses metric embedding to tell a story for DNN models and does not provide the specific relationship between metric learning and DNNs. For example, whether the feature transformation obtained by DNN meets the definition of metric (or part of the definition), and whether the perspective of metric embedding can bring new inspiration to the theory of DNNs.\n2.\tThe metric learning theory in this paper basically comes from the generalization theory of neural networks [Bartlett et al. (2017)]. Compared with the previous theoretical results, the metric perspective analysis proposed in this paper does not give better results. From the existing content of this paper, the part of metric learning does not seem to work.\n", "summary_of_the_paper": "This paper tries to provide uniform guarantees for the DNN type metric embeddings.", "summary_of_the_review": "In a word, I think this paper does not provide a new theoretical guarantee for nonlinear metric learning, and its results are basically the same as the existing generalization theory of DNNs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7MwP7ZcuVDI", "reviewer": "Reviewer_Whaa", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "**Caveats:**\n- I am not familiar with the literature in this area, so cannot determine the novelty of the results or whether there are missing citations.\n- I did not read the proofs in detail, so cannot vouch for the correctness of the mathematical results.\n\n\n**Review:**\n\nIn general I found this paper quite difficult to read. This is in part because I am not an expert in the area of the paper, but also because it is somewhat confusingly organised. \n\nTo be explicit: \n- after a brief introduction, the paper states in section 1.1 the bounds which are the main results, only partially defining the mathematical terms being used, and without context explaining why these are interesting. \n- Then in section 1.2, there is a brief discussion of existing literature whose methods they build on. \n- In Section 2, metric learning in general is once more discussed, and in section 3 other literature is again discussed. \n- Much of the crucial mathematical notation used at the beginning of the paper is only defined in Section 4 where the results are formally stated. \n\nI think the paper would benefit significantly from being reorganised. I suspect that this could lead to some space saving as there is currently some repetition. \n\n\nOn the technical side, it is not easy to pick apart the exact contributions of the paper. [I am not an expert in this area, so anyway wouldn't be fully able to evaluate the novelty of the results.] For instance:\n- The results are all about proving bounds on Radermacher complexity. Why is this actually interesting? It is never stated explicitly in the paper.\n- The bounds from Bartlett et al 2017 are mentioned multiple times. What exactly is the difference between those bounds and the ones in this paper?\n- What is the connection between these results and the 'real world'? What are the limitations?\n\n\nMy review should be taken with a pinch of salt because I am not an expert in this area, but in my opinion the paper is not ready for publication in its current form. \n\n\n\n**Other Detailed comments:**\n\nAbstract: \n- I wasn't familiar with (2,1) norms and (2, \\infty) norms. If other reviewers also complain of this, could you consider adding a couple of words to give more context, maybe even just \"(2,1) matrix norm\" or something? \n\n\nPage 1: \n- Last paragraph: I found this sentence a bit confusing, consider rephrasing? \"...difference between the expected value of the loss and the average value of the loss on the train set\". Did you mean, \"expected value of the loss wrt the unknown population distribution vs empirical average over the samples in the train set\"? \n- 20newsgroups: could you cite the dataset here on its first mentioning in the main text?\n\n\nPage 2: \n- After eq (2): Given that the main contribution of the paper is proving upper bounds on the Radermacher complexity of this function class, I think it wouldn't be a bad idea to talk in a little more detail about the importance of Radermacher complexity. \n- Just after equation (3): I think can be helpful to readers to connect the assumptions made with real settings. Could you maybe add a note saying which types of network architectures this framework does and does not encompass? (Without thinking too hard, I guess it does include convolutions and MLPs without biases, but not ResNets, and does include ReLUs, sigmoids. Are there any commonly used activations that are not Lipschitz? Can biases somehow be included WLOG?) \n- Before eq (4): could you define the spectral/operator norm?\n- In eq (4): I found this equation quite confusing for a while and thought there was a mistake with the subscript \"i\"s. It would probably make it a lot clearer if you define \\mathcal{A}_i (I guess this should be the set of all A_i) and then make it sup_{A_i \\in \\mathcal{A}_i}. \n- eq (5): what does the \"O with a line on top\" mean? Could you please define it? (maybe this is standard in this part of the literature and I'm just unfamiliar with it)\n- \"Here b is an upper bound on inputs\" I'm not sure what this means. Also, by 'inputs' do you mean 'features'? (I presume you mean the norm of the features, but please be explicit.)\n\n\n\nPage 4: \n- eq (12) as someone not so familiar with this area, I wondered why the margin constants are called S and D? \n\nPage 6: \n- Can the assumption that \\phi(0)=0 be made WLOG? If not, what generality is lost? \n- Equation 16: In general I found the organisation of this paper a bit confusing, and this is a good example. Why does this definition not appear somewhere near the beginning of the paper? \n\nPage 7:\n- RelU -> ReLU\n\nPage 8: \n- 'Recall that the notion of “dense” in this paper refers [to] the specific condition that' -> I think this is the first time that the definition is actually given in this way. I think it would be clearer to properly define it the first time you use it on page 3. \n- Something has gone wrong with the formatting of citations for MNIST and 20newsgroups datasets. Could you move the citations to the first time you mention the datasets?\n", "summary_of_the_paper": "The authors consider the setting of metric learning. They prove bounds on the Radermacher complexity of embeddings-composed-with-distance-functions for a particular architecture of neural network, with different results for the 'dense' and 'sparse' regimes. \n", "summary_of_the_review": "Paper is not fit for publication in its current form: it should be structured more coherently and the results discussed in more context.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: 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 main contribution of the paper is by extending the techniques of Bartlett et al. from a classification setting to the metric learning setting (which has very different objectives) and consider two regimes. In the first regime the techniques are fairly similar but the second regime is more novel. However, the current version of the paper does not highlight the similarity and differences between the results and techniques with Bartlett et al. 2017; it also does not give sufficient intuition on how the metric learning setting is fundamentally different from the classification setting and how the paper leverage the difference to get improved bounds. All the reviewers had some confusions to different degrees, and the paper would be much stronger if it can explain the intuition and make more explicit comparisons.
Decision: Reject