Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper studies the performance of the mirror gradient method when applied to the overparameterized network. The authors claim that the SMD method could find the regularized global minimize for different potential functions, in terms of minimal Bregman distance. Further experiments are carried out to back up the authors' claim.

However, the drawbacks of this paper are listed in these several points:

1) The regularization w.r.t. Bregman distance is quite different from the regularization used in network training: instead of $\|w - w_0\|$, we use $\|w\|$ more often, therefore, the virtue of sparsity shared by 1-norm is not exploited.

2) The authors' assumption in Assumption 3.1 is too fuzzy: instead of detailed analysis in the papers related to the overparameterized network, the author does not give ANY relationship between the $\epsilon$ and these three important parameters: a) network width, b) probability introduced by random initialization, c) the number of input data.

3) Therefore, according to the too strong and fuzzy assumption mentioned in the last point, Assumption 3.1 simply makes the network equals to the linear model, which leads to minor contributions according to the study of the overparameterized network.

4) The `over parameterized network' discussed now, including the work of (Li & Liang, 2018; Du et al., 2018; Azizan & Hassibi, 2019; Allen-Zhu et al., 2019; Cao & Gu, 2019), are mainly focused on the `network of infinite width', however, in the authors' experiment, the network architecture, e.g. ResNet18, is more to be a `very deep network' rather than a `very wide network'. Therefore, the authors' theory is built on Assumption 3.1, which is based on `network of infinite width', while the experiment is built on the `very deep network'. The result of the experiments is not enough to support the authors' theorem.

In conclusion, I am convinced that the authors' work is over-claimed in this paper.
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors study the behavior of stochastic mirror descent on overparameterized nonlinear models. Especially, the authors show that for appropriate initialization, SMO converges to a global minimum with a minimal distance to the initialization. The authors also report some experimental results to verify this theory.

The implicit regularization of SGD/SMD is widely studied in the literature. Although it is claimed that the paper improved existing results by either considering nonlinear models or identify more precise implication regularization, the contribution is a bit minor. In particular, the fundamental identity in Lemma 6 is exactly a specific case of Lemma 4 in  Azizan & Hassibi (2018) with no noises. Moreover, Azizan & Hassibi (2018) also discussed the implicit regularization of SMD in their Theorem 10 for nonlinear models with some localization arguments. This paper considers similar localization arguments with some different assumptions.

After rebuttal:
I am sorry to select by mistake a N/A for the correctness of experiments.  
I have read the authors' rebuttal and would not like to change my score. The fundamental identity in Lemma 6 was already derived in Azizan & Hassibi (2018). This paper identifies some assumptions to show the implicit regularization studied in Azizan & Hassibi (2018) with heuristic argument. However, these assumptions are very strong and with the assumptions the argument follows similarly to those in Azizan & Hassibi (2018). Indeed, as stated in Azizan & Hassibi (2018), the convergence in linear case depends on the non-negativity of $D_{L_i}(w,w_{i-1})$. In this paper, the authors just assume that this non-negativity holds locally in Assumption 1. In my opinion, this seems not a rigorous way to formulate assumptions.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper studies the optimization behaviour of stochastic mirror descent (SMD) on over-parametrized nonlinear models. It shows, rigorously and empirically, that SMD finds global minimizer that is approximately the closet global minimizer to the initial point, under the same Bregman divergence.  The paper is well written and easy to follow. 

Pros:
1. The main contribution of this paper is extending the previous results on linear case into nonlinear setting, which is much more general. The results are non-trivial and interesting. 
2. The empirical studies in the paper is clean and significant. It also supports the developed theory.

The main concern I have is about assumption 1 in the paper.  While in the paper the authors tend to claim that it is reasonable/mild, it is not obvious to me. 
    a. Many factors are actually involved in this assumption: smoothness of \psi, smoothness of L_i and f_i, number of parameters etc.. I am not sure if it is still a high probability, when \eps needs to be small enough so that the intuition behind Figure 2 still holds. 
    b. Is this assumption also made in the referred papers on the top of page 6? Could the authors develop a concrete result, given smoothness coefficients of \psi and L_i, for this assumption?  
    c. Without a proper justification of assumption 1, the significance of this paper seems much weaker. For example, one can also assume the PL inequality locally true for over-parametrized function, and develop a convergence result. 

review_title: Official Blind Review #1

Meta-review: This paper takes results related to the convergence and implicit regularization of stochastic mirror descent, as previously applied within overparameterized linear models, and extends them to the nonlinear case.  Among other things, conditions are derived for guaranteeing convergence to a global minimizer that is (nearly) closest to the initialization with respect to a divergence that depends upon the mirror potential.  Overall the paper is well-written and likely at least somewhat accessible even for non-experts in this field.

That being said, two reviewers voted to reject while one chose accept; however, during the rebuttal period the accept reviewer expressed a somewhat borderline sentiment.  As for the reviewers that voted to reject, a common criticism was the perceived similarity with reference (Azizan and Hassibi, 2019), as well as unsettled concerns about the reasonableness of the assumptions involved (e.g., Assumption 1).  With respect to the former, among other similarities the proof technique from both papers relies heavily on Lemma 6.  It was then felt that this undercut the novelty somewhat.   

Beyond this though, even the accept reviewer raised an unsettled issue regarding the ease of finding an initialization point close to the manifold that nonetheless satisfies the conditions of Assumption 1.  In other words, as networks become more complex such that points are closer to the manifold of optimal solutions, further non-convexity could be introduced such that the non-negativity of the stated divergence becomes more difficult to achieve.  While the author response to this point is reasonable, it feels a bit like thoughtful speculation forged in the crunch time of a short rebuttal period, and possibly subject to change upon further reflection.  In this regard a less time-constrained revision could be beneficial (including updates to address the other points mentioned above), and I am confident that this work can be positively received at another venue in the near future.
Decision: Reject