Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper asks a very interesting question about implicit bias of neural training - in particular about interpolating depth 2 nets. Instead of trying to ask which of these interpolating nets would some training algorithm find, this paper tries to come up with a geometrical description of a subset of these nets which have a certain minimum norm condition on its parameters - when the input and the output dimension of the net is 1. 

Also the paper chooses to work with an unconventional class of nets which have an additional linear unit. But then one is left to wonder why the authors' didn't frame it as a result about R -> R depth-2 ResNets - which is what this looks like. There are a few  more ambiguities like this which I shall point out in the later parts of the review.  
strength_and_weaknesses: The framing of the question is quite interesting and its generalization implications are intriguing. The paper zones into a very special case and solves it in details. The approach is very appreciable.  

The weakness of the paper is in its organization of the main proof.
clarity,_quality,_novelty_and_reproducibility: The main part of the paper is quite clear and well-motivated. But the proof of the main theorem 1.3 is somewhat hard to piece together. It seems scattered through the Appendix. There needs to be a better organization of this - maybe a summary of the proof in the main paper which walks the reader through the steps.
summary_of_the_review: Its a very nice piece of work and I think it can lead to some very interesting further work. My main complaint is with the writing/organization of the main theorem's proof - and some claims which seem to have feet of clay - like the following line at the end of page 3,  

"The elements of RidgelessReLU(D) can intuitively be thought of as all univariate one layer ReLU networks that minimize a weakly penalized loss...and the strength lambda of the weight decay penalty is infinitesimal."

Either this is a claim that the authors should be be able to put in the proof for - or they should formally state this as a conjecture. 
Currently the wording is quite dodgy.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the implicit bias of univariate one-hidden layer ReLU networks with infinitesimal weight decay. In this setting, the authors derive a geometric description for all the networks that interpolate some given training data and attain the minimal value of the $\ell_2$ norm of the neuron’s weights. Then, the authors use this result to obtain a generalization guarantee for learning $1d$ Lipschitz functions.
strength_and_weaknesses: **Strengths:**
- The paper is well written and explains clearly how the results relate to previous works.
- The generalization guarantee for ReLU networks is an interesting and novel result, to the best of my knowledge.

**Weaknesses:**
* The main weakness is that the setting is quite restricted. The results only apply to univariate one hidden layer ReLU networks which interpolate the training data and minimize a $\ell_2$ penalty. As the authors mention, the penalty does not regularize the linear terms in the ReLU network, which is not standard practice. I think that the results will be much stronger if the authors either:
    + Supply some optimization result that motivates studying this setting.
    + Extend the results to the multivariate setting using the results from Ongie et al (2019).

clarity,_quality,_novelty_and_reproducibility: The paper is well written. The assumptions and results are clearly stated, and the results given in the paper are new, to the best of my knowledge.
summary_of_the_review: Overall, I think that the paper's contributions are not sufficient for acceptance, as discussed under “weaknesses”. Supplying some additional results, as suggested above, will significantly strengthen the paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers a one-layer ReLU network that only considers 1-D input. The authors study a set of solutions RidgelessReLU(D) that has the smallest norm of weights among all interpolators of the training samples. The authors show that the functions in such a set satisfy certain requirements by examining the second-order discrete derivative. Based on these requirements, this paper provides a generalization upper bound on Lipschitz functions when the 1-D input is uniformly spaced (deterministically) in [0, 1], and argues that a similar result also holds if the 1-D input is drawn independently at random from [0, 1].
strength_and_weaknesses: Strength: The presentation is relatively clear.
Weakness: The setup is too restrictive and not justified properly. See my comments below.
clarity,_quality,_novelty_and_reproducibility: The setup is too restrictive (e.g., needs 1-D input) and not justified properly. The following are some detailed comments.

1. Minimizing the l_2-norm of all neuron weights is not weight decay. The authors confirm this at the end of Page~3. While the authors argue that they do not study optimization and do not care whether such a setup has any relationship with the actual gradient descent with weight decay, the title of this paper still highlights the weight decay, which in my opinion is totally misleading and confusing.

2. The requirement of Corollary 1.1 is restrictive, as it needs all training inputs uniformly spaced (deterministically) in [0, 1]. Although the authors argue that a similar result also holds if the 1-D input is drawn independently at random from [0, 1], no rigorous proof is provided and thus such a claim is less convincing.

3. Figs. 1~7 take too much space (almost 2.5 pages) and are repetitive. No simulations on the test error are provided.
summary_of_the_review: I don't think this paper will be helpful in understanding the performance of existing neural networks, because of 1) an oversimplified setup, and 2) no connection/similarity with the actual gradient descent with weight decay used in the neural network.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper attempts to study the generalisation properties of one-dimensional ReLU networks directly, instead of via the usual VC-dimension or Rademacher complexity-type bounds. 

To this end, they *geometrically* characterise the space of one-layer ReLU networks with a single linear unit, which *fit* a given dataset $D \subset \mathbb{R}^2$ *while achieving the minimum possible $\ell_2$ norm among the neuron weights*.  

Main Results: 
A geometric characterisation of all one-layer ReLU networks that exactly fit a univariate dataset $D \subset \mathbb R^2$. Since ReLU networks in this context are just piecewise linear functions, this turns out to be described by the constraint that the network fits the data while achieving as few inflection points as possible. 

Corollary: Interpolating ReLU networks with $\ell_2$ regularisation achieve best possible $\ell_\infty$ generalisation error for one-dimensional Lipschitz functions. 

Their work builds on the observation due to Neyshabur(2014) that $\ell_2$ regularisation in the setting considered is equivalent to penalising the TV distance of the derivative of the network function. This observation applies to any dimension, but the complete characterisation in this paper is only for one-dimensional neural networks. 

strength_and_weaknesses: Weaknesses:
1. The paper does not study optimization, only the generalisation guarantees that are achieved by the minimiser. 
2. Only the one-dimensional setting is studied. 

Strengths: 
1. The authors describe an algorithm which is a consequence of the theorem, that allows them to describe all elements that might minimise the $\ell_2$ norm of the weights while interpolating the dataset. 
2. I personally like the attempt at a geometric characterisation of the min-cost interpolating function, and generalisation guarantees that might arise from that. 

clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is written clearly. 
Quality: I think this is a good paper. 
Novelty: The geometric characterisation is novel. 
Reproducibility: This is not an empirical paper. 

summary_of_the_review: This paper gives a complete characterisation of the $\ell_2$ minimizing univariate ReLU network. 

I think this is a complete result for a simple setting that provides interesting insights into the generalisation as well as geometric properties of the minimiser, and vote to accept it.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper characterizes solution concepts of a certain type of univariate one layer ReLU networks which interpolate. This paper has had quite a bit of discussion, and the reviewers and AC all feel that while achieving results in this area is difficult -- and they take the point that there are not many papers addressing both generalization and optimization -- the present paper still falls short of being a substantial contribution. There was also a discussion about whether the words "Implicit Bias" on the title are misleading. The AC is sympathetic to the extent that these words have been used in varied contexts, but they should probably be removed from this paper as it is talking about solution concepts rather than the behaviour of algorithms. Overall it was not felt that the contributions were of sufficient technical depth or of sufficient interest for a venue like ICLR after a substantial discussion amongst all of the reviewers. 
justification_for_why_not_higher_score: See MetaReview.
Decision: Reject