SGD CONVERGES TO GLOBAL MINIMUM IN DEEP LEARNING VIA STAR-CONVEX PATH
Stochastic gradient descent (SGD) has been found to be surprisingly effective in training a variety of deep neural networks. However, there is still a lack of understanding on how and why SGD can train these complex networks towards a global minimum. In this study, we establish the convergence of SGD to a global minimum for nonconvex optimization problems that are commonly encountered in neural network training. Our argument exploits the following two important properties: 1) the training loss can achieve zero value (approximately), which has been widely observed in deep learning; 2) SGD follows a star-convex path, which is verified by various experiments in this paper. In such a context, our analysis shows that SGD, although has long been considered as a randomized algorithm, converges in an intrinsically deterministic manner to a global minimum.
This paper attempts to account for the success of SGD on training deep neural networks. Starting from two empirical observations: (1) deep neural networks can almost achieve zero training loss; (2) the path of iterates generated by SGD on these models follow approximately the “star convex path”, under the assumptions that individual functions share a global minima with respect to which the path of iterates generated by SGD satisfies the star convexity properties, the papers shows that the iterates converges to the global minima. 
In terms of clarity, I think the paper can definitely benefit if the observations/assumptions/definitions/theorems are stated in a more formal and mathematically rigorous manner. For example:
- On page 3, “fact 1”: I don’t think “fact” is the right word here. “Fact” refers to what has been rigorously proved or verified, which is not the case for what is in the paper here. I believe “observation” is more appropriate. Also the assumption that l_i is non-negative should be formally added.
- On page 3, section 3.1: the x^* here is the last iteration produced by SGD. Then how can it be called the “global minima”? The caption of Figure 1 on page 4 is simply misleading.
- On page 4, the statement in definition 1 is more like a theorem than a definition. It is giving readers the impression that any path generated by SGD satisfies the star-convex condition, which is not the case here. A definition should look like “we call a path generated by SGD a star-convex path if it satisfies …”. Definition 2 on page 6 has the similar issue.
In terms of quality, while I believe the paper is technically correct,  I have one minor question here:
Page 3, Fact 1: How can you conclude that the set of common global minimizers are bounded? In fact I don’t believe this is true at all in general. If you have a ReLu network, you can scale the parameters as described in [1], then the model is invariant. Therefore, the set of common minimizer is definitely NOT bounded. 
In terms of significance, I think this paper is very interesting as it attempts to draw the connection between the aforementioned observations and the convergence properties of SGD. Unfortunately I think that this paper is less significant than it has appeared to be, although the analysis appears to be correct. 
First of all, all the analysis of this paper is based on one very important and very strong assumption, namely, all individual functions $l_i$ share at least one common global minimizer. The authors have attempted to justify this assumption by empirical evidences (figure 1). However, achieving near-zero loss is completely different from achieving exact zero because only when the model achieves exact zero can you argue that a common global minimizer exists. 
Secondly, the claim that the iterate converges to the global minima is based on the assumption that the path follows an “epoch-wise star-convex” property. From this property, it only takes simple convex analysis to reach the conclusion of theorem 1 and 2. Meanwhile, the assumption that the path does follow the “epoch-wise start-convex” properties is not at all informative. It is not clear why or when the path would follow such a path. Therefore theorem 1 and 2 are not more informative than simply assuming the sequence converges to a global minimizer. 
In fact, it is well-known that SGD with constant stepsize converges to the unique minimizer if one assumes the loss function F is strongly convex and the variance of the stochastic gradient g_k is bounded by a multiple of the norm-square of the true gradient:
Var(g_k) <= M ||∇F(x_k)||^2
Which is naturally satisfied if all individual functions share a common minimizer. Therefore, I don’t think the results shown in the paper is that surprising or novel. 
With respect to the empirical evidence, the loss function l_i is assumed to be continuously differentiable with Lipschitz continuous gradients, which is not true for networks using ReLU-like activations. Then how can the paper use models like Alexnet to justify the theory? Also, if what the authors claim is true, then the stochastic gradient would have vanishing variance as it approaches x^*. Can the authors show this empirically?
In summary, I think this paper is definitely interesting, but the significance is not as much as it would appear.
Ref: 
[1] Dinh, L., Pascanu, R., Bengio, S., & Bengio, Y. (2017). Sharp minima can generalize for deep nets. arXiv preprint arXiv:1703.04933.