Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper is well written, but severely overestimates the core contributions embedded in section 3.

Firstly, the idea of using drop out for matrix sensing seems to be a somewhat trivial extension of the work on dropout for matrix factorization -- http://proceedings.mlr.press/v84/cavazza18a/cavazza18a.pdf.  I am surprised that this work is not cited with its due credit in the writing. I hope to see some concrete statement about the difference between the authors' contribution and the existing literature. It is fine to propose an incremental improvement as long as the original work receives the required credit.

Dropout has been an extensive area of theoretical research for the past few years. The overly simplistic statement about the limitation of our understanding of how dropout works are a little disappointing, particularly so when the authors themselves list this literature in the related work section. That dropout training can be perceived as an adaptive regularization is also very well known and researched. These arguments weaken the second and third contribution of the paper. I do understand though that extending the results of deep linear networks to a single hidden layer RELU network is non-trivial. The derivations also suggest so and the authors deserve credit for attempting these derivations.

I am also quite doubtful about the setting of the experiments in section 4.1. That changing the batch-size or learning rate does not significantly influence the eventual performance is very counter-intuitive. 

Overall, the paper appeared quite promising in the beginning, but the claims in the introduction are not well supported through the rest of the paper. 

review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: Summary:
This work studies the effect of regularization through dropout on generalization bounds for Matrix Sensing and linear regression with deep neural network task. For both matrix sensing task and linear regression task, authors derive an explicit regularization term due to dropout. Authors give elegant interpretations of dropout regularizer. For matrix sensing: dropout can be thought of as the inducing trace-norm regularization when matrices are standard gaussian. For matrix completion: dropout can be thought of as weighted trace-norm regularizer.
Authors then give a generalization bound for matrix completion with dropout.
In the context of deep neural networks, under assumptions on the input distribution authors show that the explicit regularizer associated with dropout is exactly the squared l2 path-norm of the network.
Authors give a bound on the Rademacher complexity of deep nerual networks with dropout. Using the bound on Rademacher complexity, authors derive the a generalization bound for squared error loss.

I recommend rejecting this submission. Following are my concerns:

1. Authors derive the bound on the Rademacher complexity in Lemma 1 and claim that this bound holds for any neural network, but in the proof they make assumptions on the output of the neural network that are not stated clearly. Assumptions, as far as I understand, are 1) expected output under the data distribution of the jth unit is bounded by 1 and 2) the second moment is also equal to 1. I believe that this is not true for most of the neural networks with RELU nonlinearity for the output units.

2. For the proof of Theorem 2, authors derive the supremum deviation between the true labels and those predicted by the neural network. I don’t believe the 5th inequality on page 19. Authors bound the worst case output of the neural network by the expected output of the neural network which is not true.

3. I am not yet convinced by the experiments section of the paper where they evaluate the generalization gap for datasets. In particular, the theorems derived in the paper has assumptions on the sample complexity. These assumptions are not verified for the datasets used in the experiment section and I suspect that lower bound on n can be too large for the bounds to be meaningful.

4. There is no comparison to existing literature on generalization bounds due to dropout as a regularizer. Following paper derives PAC-Bayes bound for dropout procedure:
	McAllester, D.A. (2013). A PAC-Bayesian Tutorial with A Dropout Bound. ArXiv, abs/1307.2118. 
review_title: Official Blind Review #4

final_score: rating: 1: Reject
review_content: Post Discussion Update: 

The authors vehemently disagree with my critiques about discussion of / attribution to prior work.  They seem to think that the differences from Cavazza et al. [AIStats 2018] would be obvious to "even someone who has taken a basic course in machine learning."  However, both Reviewer #2 and Reviewer #3 mentioned the same issues, saying "much of the technical leverage exploited in this paper comes from earlier work...results a lot like Proposition 2 can be found in [Cavazza et al.]" (#2), and "I am surprised that [Cavazza et al.] is not cited with its due credit in the writing. I hope to see some concrete statement about the difference between the authors' contribution and the existing literature" (#3).  Since 3 out of 4 reviewers did not recognize a clear distinction, it is fair to say the differences to which the authors refer in their rebuttal should be discussed at length in the paper.  However, the authors have not posted a revised draft or any sample text , leaving me to keep my recommendation at 'reject.'

______________________________________________________________________________________________________________________________________
Summary:  This paper studies (Bernoulli) Dropout regularization in the context of matrix sensing and neural networks (when dropout is applied to only the last hidden layer).  The paper first focuses on matrix sensing, showing an explicit regularizer with connections to trace norm regularization and proving a generalization bound.  The paper then moves to neural networks, first showing an explicit regularizer in the case of a squared loss and dropout on the last hidden layer only.  When the input distribution is symmetric and isotropic, the explicit regularizer is shown to have connections to path norm regularization.  From this explicit regularizer, the authors then derive an upper bound on the generalization gap (Theorem 2).  Experiments are reported that show (#1) (stochastic) dropout does improve generalization in a matrix completion task and (#2) the theoretical results do predict generalization as tested on MNIST and CIFAR-10.          

Pros:  Extending dropout to other tasks and understanding its general method of action is an important problem, thus making the paper well motivated.  Moreover, the approach of deriving explicit regularizers from the stochastic objective is a commendable strategy that could improve the stability and speed of converge.  Furthermore, understanding the generalization properties of neural networks is important, and as dropout seems to be a well-established tool for improving generalization, the paper’s approach is sensible.  

Cons:  I find this paper to severely over-claim its contributions---in particular #1 and #3 from the introduction...

(#1) Dropout for matrix completion:  Claimed contribution #1 is incremental as it merely adapts the dropout strategy of Cavazza et al. [AIStats 2018] to matrix sensing.  Cavazza et al. [AIStats 2018]’s procedure “drop[s] columns of the factors” (a quote from their abstract), and this is exactly what is done in this paper: “...a procedure that randomly drops the columns of the factors during training” (p 1).  I find it suspicious that the only time Cavazza et al. [AIStats 2018]’s work is mentioned is in the Introduction’s long list of citations of previous dropout work.  In effect, this equates Cavazza et al. [AIStats 2018]’s work with much less related work (e.g. Bayesian interpretations).  The Cavazza et al. [AIStats 2018] work should surely be cited in the vicinity of Equation 2.  Furthermore, Cavazza et al. also discuss connections to trace norm regularization (Section 4) and should also be included in the paper’s discussion on page 3.  

(#3) Dropout in NNs: The explicit regularizer derived in Prop 3 was previously derived by Wang & Manning [ICML 2013]; see their Section 3.1.  This work is not cited---another significant oversight.  However, the resulting complexity bounds derived from Wang & Manning [ICML 2013]’s explicit regularizer are original, to the best of my knowledge.  

In general, the paper makes several claims that are at best ungenerous to previous work.  For instance, the Introduction claims “none of these [previous] works adequately address the following basic question: how does dropout control the capacity of deep neural networks?” (p 1).  This is an unsubstantiated claim given that the paper contains no Related Work section, which is needed since there have been dozens of papers written on dropout.  Moreover, this work considers only the case in which dropout is applied to the last hidden layer, not to the full network (which is a valid and sensible restriction).  Yet this essentially reduces the results to a study of dropout in linear models (except perhaps in Prop 4) and therefore I don’t see how one could claim the previous work of Wager et al. [NeurIPS 2013], which also studies dropout for linear models, doesn't address similar questions.  For another example, the paper claims on page 3: “These observations are specifically important because they connect dropout, an algorithmic heuristic in deep learning, to strong complexity measures that are empirically effective as well as theoretically well understood.”  I agree that the connections are important, but similar connections have already been established by (at least) Cavazza et al. [AIStats 2018], Wang & Manning [ICML 2013], and Wager et al. [NeurIPS 2013].  Such connections are not unique to this paper, as the text implies.  

As for experiments, the matrix completion results to not validate any of the results in Section 2.  A comparison of training under the stochastic objective vs with the explicit regularizer is never performed (as is done in Cavazza et al. [AIStats 2018]).  Similarly, the generalization bounds are not shown to be useful.  The only thing that is shown is that the stochastic objective (again, which is a minor adaptation from Cavazza et al. [AIStats 2018]) does improve generalization.  

Minor comments:

> ERM is never defined as an initialism for “empirical risk minimization” 

> While the assumptions of an isotropic and symmetric input distribution in Prop 4 are unrealistic in general, such conditions would be satisfied by hybrid architectures defined by making the early layers of the network a (isotropic Gaussian) normalizing flow [Nalisnick et al., ICML 2019].

Final Evaluation:  I find the paper's only original and validated contribution to be using Wang & Manning [ICML 2013]’s explicit regularizer to derive the complexity upper bound in Lemma 1.  Due to the paper's lack of discussion and, at times, mischaracterization of previous work, the text needs to be significantly revised before it can be accepted.  A proper Related Work section must be added to discussion the previous literature on understanding dropout.        



__References__

Nalisnick, Eric, et al. "Hybrid Models with Deep and Invertible Features." International Conference on Machine Learning. 2019.

Wang, Sida, and Christopher Manning. "Fast dropout training." International Conference on Machine Learning. 2013.

review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: The authors prove bounds on the generalization of models produced using dropout.  They conduct experiments showing that dropout improves over SGD without dropout, and plotting generalization gaps and their bounds.

Much of the technical leverage exploited in this paper comes from earlier work.  Their acknowledgement of these contributions is somewhat uneven.  For example, results a lot like Proposition 2 can be found in [1].  In their treatment
of deep networks, because only the last layer is dropped out, dropout is essentially applied to a linear model,
and Proposition 3 of this paper  follows from (10) of [2], which was pointed out 12 lines below (10) in that paper.  

The statement of Theorem 1 does not appear to be
rigorous to me.  For random data, the probability
that any minimizer of the dropout ERM objective
satisfies their bounds on the lengths of the
rows of U and V could be less than 1 - 2 delta, in which case in some
cases where the displayed equation in Theorem 1
is said to apply, there is no U and V to apply it to.  
(The parameter gamma is not quantified in the statement 
of that theorem.  It is conceivable to me that if gamma is
constrained to be large, possibly relative to d_0, d_1 and d_2,
then the statement of the theorem could make sense.)

Theorem 2 has a similar issue.  How is M quantified?  
How do we know that a minimizer that satisfies the constraints
on M exists with probability at least 1 - 2 delta?

The authors' claim that "changing the learning rate or the batch size does not significantly improve the
performance of any of these algorithms" is a little hard to believe.  My impression is that these choices
affect the implicit regularization of SGD (along with the initialization).  Some more detail about what
they tried would be helpful.  

There is some interesting new content in the paper, even if, on the whole, it is a bit conceptually and technically
incremental. 

(This review has been edited in light of the response.)


[1] Cavazza, Jacopo, et al. "Dropout as a Low-Rank Regularizer for Matrix Factorization." International Conference on Artificial Intelligence and Statistics. 2018.

[2] Wager, Stefan, Sida Wang, and Percy S. Liang. "Dropout training as adaptive regularization." Advances in neural information processing systems. 2013.

review_title: Official Blind Review #2

Meta-review: The authors study dropout for matrix sensing and deep learning, and show that dropout induces a data-dependent regularizer in both cases. In both cases, dropout controls quantities that yield generalization bounds. 

Reviewers raised several concerns, and several of these were vehemently rebutted. The rhetoric of the back and forth slid into unfortunate territory, in my opinion, and I'd prefer not to see this sort of thing happen. On the one hand, I can sympathize with the reviewers trying to argue that (un)related work is not related work. On the other hand, it's best to be generous, or you run into this sort of mess.

In the end, even the expert reviewers were unswayed. I suspect the next version of this paper may land more smoothly.

While many of the technical issues are rebutted, one that caught my attention pertained to the empirical work. Reviewer #4 noticed that the empirical evaluations do not meet the sample complexity requirements for the bounds to be valid (nevermind loose). The response suggests this is simply a fact of making the bounds looser, but I suspect it may also change their form in this regime, potentially erasing the empirical findings. I suggest the authors carefully consider whether all assumptions are met, and relay this more carefully to readers.
Decision: Reject