Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposes a "gamma principle" for stochastic updates in deep neural network optimization. First, the authors propose if Eq. (2) is satisfied then convergence is guaranteed (Thm. 1). Second, they use experimental results of Alexnet and Resnet-18 on cifar10/100 to show that Eq. (2) is satisfied by SGD, SGD with momentum, and Adam, with different activations and tricks like batch normalization, skip connection.

Pros:
1. This paper is well written and the presentation is clear.
2. The experiments are extensive.

Cons:
1. Before Eq. (2), it is assumed that over-parameterized NNs are used as \theta. But there is no quantization how many parameters are enough? Are the Alexnet/Resnet-18 in experiments enough over-parameterized and how can we tell that? Some quantitative conditions should be provided to show what kind of models this principle hold.

2. The connection between Eq. (2) and Thm. 1 is too obvious and the gamma is just to characterize the progress of each update. Of course, large progress corresponds to fast convergence. Eq. (2) is a strong assumption rather than a theoretical contribution.

3. Experiments are used to show that Eq. (2) is a "principle". However, the experiments are problematic as follows.
First, "we set \theta^* to be the network parameters produced in the last training iteration", then how do we make sure \theta in the last training iteration is \theta^*, even if the loss is close to (but not exactly) zero? For this point, I suggest using a teacher-student setting, where the optimal \theta^* is already known.
Second, using \theta in the last training iteration makes the experiments show the following simple fact, that methods/tricks/activations with faster convergence to certain parameter will have larger every update progress to that parameter, which is, of course, true and does not reveal an optimization principle of deep learning.
Third, it is difficult to claim that this is a principle for general deep learning by using experiments on two datasets.

Overall, I found the theory not inspiring and experiments not convincing.

========Update=========
Thanks for the rebuttal.
I have read it and using teacher-student setting is an improvement to resolve my question with respect to \theta^*.
However I would maintain my rating since
1) the theoretical contribution is actually marginal;
2) the argument that this "gamma principle" holds for over-parameterized NNs is vague in the sense (and the author did not resolve my concern of this) that for what kinds of over-parameterized NNs this would work and for what kinds of NNs it does not hold. In particular, mentioning other theory work of over-parameterized NNs is not enough, because usually in these work, the numbers of parameters in NNs are poly(n), like O(n^4), O(n^6), where n is number of training data. There is an obvious gap between poly(n) and the number of parameters in experiments. From this perspective, the experiments cannot verify the claim that this "principle" holds for over-parameterized NNs that mentioned by authors in the rebuttal.
3) experiments on two datasets are not enough to claim this is a general "principle".
Considering this claim is for general over-parameterized NN optimization, I think it lacks of specifying types of NNs for which this claim would hold (of course it cannot hold for any NNs, but it possibly can hold for some NNs, and what are these NNs?), and experiments are not enough to show the generality of this claim.
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: The paper proposes a new condition: $\gamma$-optimization principle. 
The principle states that the inner product between the difference between the current iterate and a fixed global optimum and the stochastic gradient (or more general) is larger than the squared the gradient norm, plus the product of squared norm of the difference between the initialization and the global minimum, and the loss of the current iterate.

Under this condition, the paper shows sublinear convergence.

Main Comments：
The proposed conditions are similar to many previous works, as pointed out by authors. With these kinds of conditions, proving global convergence is trivial. 
One question is that the condition holds uniformly for all models and every sampled data point. There is no randomness in the condition. I would expect a condition that has some "randomness" in it, e.g., the condition holds in expectation over random sampling over the data.
The condition also requires a specific global minimizer. Because of the randomness in initialization and stochastic training, I expect the target global minimizer can change from iteration to iteration, but the current condition does not reflect that.


--------------------------------------------------------------------------------------------
I have read the rebuttal and I maintain the score. 
Note in the student-teacher setting even though teacher is unique, there can be multiple optimal students. I don't think this resolves my concern.
review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: Summary: 

This paper proposes an optimization principle that is called \gamma-optimization principle for stochastic algorithms (SA) in nonconvex and over-parametrized optimization. The author(s) provide convergence results under this “\gamma-optimization principle” assumption. Numerical experiments are conducted on classification datasets CIFAR-10 and CIFAR-100 for Alexnet and Resnet-18 with different activation functions. 

Comments: 

1) Could you please explain how you could achieve the value of \theta* (common global minimizer for the loss on all individual component functions)? It is unclear to me how you could obtain it. 

2) You have not mentioned the loss function that you are using for your numerical experiments. From my view, you are using softmax cross-entropy loss for classification problems (CIFAR-10, CIFAR-100). Can you show that Fact 1 is true for softmax cross-entropy loss? I wonder how you could train the total loss to achieve zero for this loss. 

3) Fact 1 with over-parameterized model could be true if the loss, for example, is mean square (for regression problems). Therefore, I would suggest you to consider other numerical examples rather than classification problems. If not, the numerical part is not very consistent with the theoretical part. 

4) The assumption that the author(s) use in the paper, that is, \gamma-optimization principle in Definition 1, is indeed strong and not reasonable. You simply assume what you want in order to achieve the convergence result. It is not easy to verify this assumption since you include \theta* unless it has only a unique solution. Note that the learning rate (eta) and gamma are very sensitive here and it is not clear how to determine these values. 

5) There is related work that you may need to consider: Vaswani et al 2019, "Fast and Faster Convergence of SGD for Over-Parameterized Models (and an Accelerated Perceptron)" in AISTATS 2019. 

I think the paper still needs lots of work to be ready. Theoretical result is not strong and the numerical experiments are not convincing. I do not support the publication for this paper at the current state. 

Minor: 
1) I am not really why you have a question mark (?) in the title. 

review_title: Official Blind Review #1

Meta-review: The paper is rejected based on unanimous reviews.
Decision: Reject