Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: Strengths:

The 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.

Experiments show both bounds are useful depending on data/training.


Weaknesses:

Theorem 1 seems like straightforward application of Bartlett et al 2017

Novel 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).

The 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_review: Overall the paper gives interesting generalization bounds for the metric learning setting but does not seem ready for publication.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper tries to provide uniform guarantees for the DNN type metric embeddings.
main_review: Strengths: 
It is indeed a promising research direction to regard neural networks as a special nonlinear metric embedding.

Weakness:
1.	This 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.
2.	The 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.

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 

main_review: **Caveats:**
- I am not familiar with the literature in this area, so cannot determine the novelty of the results or whether there are missing citations.
- I did not read the proofs in detail, so cannot vouch for the correctness of the mathematical results.


**Review:**

In 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. 

To be explicit: 
- 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. 
- Then in section 1.2, there is a brief discussion of existing literature whose methods they build on. 
- In Section 2, metric learning in general is once more discussed, and in section 3 other literature is again discussed. 
- 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. 

I 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. 


On 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:
- The results are all about proving bounds on Radermacher complexity. Why is this actually interesting? It is never stated explicitly in the paper.
- 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?
- What is the connection between these results and the 'real world'? What are the limitations?


My 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. 



**Other Detailed comments:**

Abstract: 
- 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? 


Page 1: 
- 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"? 
- 20newsgroups: could you cite the dataset here on its first mentioning in the main text?


Page 2: 
- 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. 
- 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?) 
- Before eq (4): could you define the spectral/operator norm?
- 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}. 
- 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)
- "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.)



Page 4: 
- eq (12) as someone not so familiar with this area, I wondered why the margin constants are called S and D? 

Page 6: 
- Can the assumption that \phi(0)=0 be made WLOG? If not, what generality is lost? 
- 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? 

Page 7:
- RelU -> ReLU

Page 8: 
- '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. 
- 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?

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 

Specifically for the metric learning setting they show that this bound can be improved. 
main_review: **Strength**

The 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. 

The authors then show that this setting where the last layer is dense occurs in practice. 

The authors show that their bound matches known bounds for the linear case. 

**Weakness**

While 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. 

I would have liked more discussion on how the bounds translate to generalization error bounds? Specifically, are they meaningful empirically?

**Questions**

1) 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. 

2) How big do we expect the matrix norms to be? Because that determines that size of the bound. 

At 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 

$$\sum_{i=1}^L \frac{||A_i||\_{2,1}^{2/3}}{||A_i||_{op}^{2/3}} \sim Lk^{1/3}$$. 

So ignoring the log factors, assuming 1-Lipschitz activation maps, we get that the bound from theorem 1 looks like

$$ \frac{b^2}{\sqrt{n}}L^{3/2}k^{L+1/2}$$

So 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. 

Okay 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. 

3) 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. 





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.
review_title: null

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