Venue: ICLR 2017 conference

Reviews:

final_score: rating: null
review_content: In page 3 one reads ``assume that these chains can be flattened...''. Flattened by what kind of operation? 
In the definition from Page 3, should affine spaces not rather be pieces of affine spaces? 
In the same definition, the assumption H_{k+1}\subseteq H_{k} would imply that the hyperplanes are parallel. Are you sure this is what you have in mind? 
At the end of Section 4 one reads about a mean relative error. Is there also a baseline? 
review_title: terminology

final_score: rating: 7: Good paper, accept
review_content: SUMMARY 
This paper discusses how data from a special type of low dimensional structure (monotonic chain) can be efficiently represented in terms of neural networks with two hidden layers. 

PROS 
Interesting, easy to follow view on some of the capabilities of neural networks, highlighting the dimensionality reduction aspect, and pointing at possible directions for further investigation. 

CONS 
The paper presents a construction illustrating certain structures that can be captured by a network, but it does not address the learning problem (although it presents experiments where such structures do emerge, more or less). 

COMMENTS 
It would be interesting to study the ramifications of the presented observations for the case of deep(er) networks. 
Also, to study to what extent the proposed picture describes the totality of functions that are representable by the networks. 

MINOR COMMENTS 
- Figure 1 could be referenced first in the text.  
- ``Color coded'' where the color codes what? 
- Thank you for thinking about revising the points from my first questions. Note: Isometry on the manifold. 
- On page 5, mention how the orthogonal projection on S_k is realized in the network. 
- On page 6 ``divided into segments'' here `segments' is maybe not the best word. 
- On page 6 ``The mean relative error is 0.98'' what is the baseline here, or what does this number mean? 

review_title: review of ``EFFICIENT REPRESENTATION OF LOW-DIMENSIONAL MANIFOLDS USING DEEP NETWORKS''

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper presents an analysis of the ability of deep networks with ReLU functions to represent particular types of low-dimensional manifolds. Specifically, the paper focuses on what the authors call "monotonic chains of linear segments", which are essentially sets of intersecting tangent planes. The paper presents a construction that efficiently models such manifolds in a deep net, and presents a basic error analysis of the resulting construction.

While the presented results are novel to the best of my knowledge, they are hardly surprising (1) given what we already know about the representational power of deep networks and (2) given that the study selects a deep network architecture and a data structure that are very "compatible". In particular, I have three main concerns with respect to the results presented in this paper:

(1) In the last decade, there has been quite a bit of work on learning data representations from sets of local tangent planes. Examples that spring to mind are local tangent space analysis of Zhang & Zha (2002), manifold charting by Brand (2002) and alignment of local models by Verbeek, Roweis, and Vlassis (2003). None of this work is referred to in related work, even though it seems highly relevant to the analysis presented here. For instance, it would be interesting to see how these old techniques compare to the deep network trained to produce the embedding of Figure 6. This may provide some insight into the inductive biases the deep net introduces: does it learn better representations that non-parametric techniques because it has better inductive biases, or does it learn worse representations because the loss being optimized is non-convex?

(2) It is difficult to see how the analysis generalizes to more complex data in which local linearity assumptions on the data manifold are vacuous given the sparsity of data in high-dimensional space, or how it generalizes to deep network architectures that are not pure ReLU networks. For instance, most modern networks use a variant of batch normalization; this already appears to break the presented analyses.

(3) The error bound presented in Section 4 appears vacuous for any practical setting, as the upper bound on the error is exponential in the total curvature (a quantity that will be quite large in most practical settings). This is underlined by the analysis of the Swiss roll dataset, of which the authors state that the "bound for this case is very loose". The fact that the bound is already so loose for this arguably very simple manifold makes that the error analysis may tell us very little about the representational power of deep nets.

I would encourage the authors to address issue (1) in the revision of the paper. Issue (2) and (3) may be harder to address, but is essential that they are addressed for the line of work pioneered by this paper to have an impact on our understanding of deep learning.


Minor comments: 

- In prior work, the authors only refer to fully supervised siamese network approaches. These approaches differ from that taken by the authors, as their approach is unsupervised. It should be noted that the authors are not the first to study unsupervised representation learners parametrized by deep networks: other important examples are deep autoencoders (Hinton & Salakhutdinov, 2006 and work on denoising autoencoders from Bengio's group) and parametric t-SNE (van der Maaten, 2009).
- What loss do the authors use in their experiments? Using "the difference between the ground truth distance ... and the distance computed by the network" seems odd, because it encourages the network to produce infinitely large distances (to get a loss of minus infinity). Is the difference squared?
review_title: Novel analysis, but potentially limited impact

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
In this paper, the authors look at the ability of neural networks to represent low dimensional manifolds efficiently e.g. embed them into a lower dimensional Euclidian space. 
They define a class of manifolds, monotonic chains (affine spaces that intersect, with hyperplanes separating monotonic intervals of spaces) and give a construction to embed such a chain with a neural network with one hidden layer.

They also give a bound on the number of parameters required to do so, and examine what happens when the manifold is noisy. 

Experiments involve looking at embedding synthetic data from a monotonic chain using a distance preservation loss. This experiment supports the theoretical bound on number of parameters needed to embed the monotonic chain. Another experiment varies the elevation and azimuth of of faces, which are known to lie on a monotonic chain, on a regression loss.

Comments:

The direction of investigation in the paper (looking at what happens to manifolds in a neural network), is very compelling, and I strongly encourage the authors to continue exploring this direction.

However, the current version of the paper could use some more work:

The experiments are all with a regression loss and a shallow network, and as part of the reason for interest in this question is the very large, high dimensional datasets we use now, which require a deeper network, it seems important to address this case.

It also seems important to confirm that embedding works well when *classification* loss is used, instead of regression

The theory sections could do with being more clearly written -- I’m not as familiar with the literature in this area, and while the proof method used is relatively elementary, it was difficult to understand what exactly was being proved -- e.g. formally stating what could be expected of an embedding that “accurately and efficiently” preserves a monotonic chain, etc.

review_title: A very interesting direction, but clearer presentation and additional experiments would be more convincing.

Meta-review: There is consensus among the reviewers that the paper presents an interesting and novel direction of study. Having said that, there also appears to be a sense that the proposed construction can be studied in more detail: in particular, (1) an average-case analysis is essential as the worst-case bounds appear extremely loose and (2) the learning problem needs to be addressed in more detail. Nevertheless, this paper deserves to appear at the conference.
Decision: Accept (Poster)