Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically BalancedS
We study the implicit regularization imposed by gradient descent for learning multi-layer homogeneous functions including feed-forward fully connected and convolutional deep neural networks with linear, ReLU or Leaky ReLU activation. We rigorously prove that gradient flow (i.e. gradient descent with infinitesimal step size) effectively enforces the differences between squared norms across different layers to remain invariant without any explicit regularization. This result implies that if the weights are initially small, gradient flow automatically balances the magnitudes of all layers. Using a discretization argument, we analyze gradient descent with positive step size for the non-convex low-rank asymmetric matrix factorization problem without any regularization. Inspired by our findings for gradient flow, we prove that gradient descent with step sizes ⌘ t " O´t´p 1 2` q( 0 † § 1 2 ) automatically balances two low-rank factors and converges to a bounded global optimum. Furthermore, for rank-1 asymmetric matrix factorization we give a finer analysis showing gradient descent with constant step size converges to the global minimum at a globally linear rate. We believe that the idea of examining the invariance imposed by first order algorithms in learning homogeneous models could serve as a fundamental building block for studying optimization for learning deep models.
Edit after author feedback, I do not wish to change my score: - To me balanced positive quantities is not only about their difference. They should have similar order of magnitude, the difference between 1e-13 and 1 is pretty small but they are clearly unbalanced. - The author put a lot of emphasis on boundedness of iterates suggesting connections between their result and boundedness. - The authors do claim more than small difference between consecutive layer weight norm: lines 160 to 163. - I still think that writting down that a polynomial is not smooth in a math paper is not professional. - The author do abuse O notation: it involves a "forall" quantifier on a logical variable: en.wikipedia.org/wiki/Big_O_notation The same goes for "Theta" and "poly" notation. None of the statements of the paper involving these notations has this feature: the variables epsilon, d, d1 and d2 are fixed and are never quantified with a "forall" quantifier. The fact that  a notation is standard does not mean that it cannot be misused.    The authors consider deep learning models with a specific class of activation functions which ensures that the model remains homogeneous: multiplying the weight of a layer by a positive scalar and dividing the weights of another layer by the same amount does not change the prediction of the network. This property is satisfied for relu types activations. A consequence is that the empirical risk is not coercive, a common assumption in convergence analysis of first order methods. In order to circumvent this issue, the authors claim that gradient descent algorithm has a regularization effect, namely that it tends to ballance the magnitude of the weights of each layers such that they remain roughly of the same order. The main results are as follows: - The authors prove that difference of norm squared of consecutive losses is a constant over continuous (sub)-gradient trajectories for relu networks. - The authors use this intuition to provide results for matrix factorization without constraint: convergence to solution for decaying step size and convergence to a solution for constant step size in the rank 1 setting.    Main comments: The abstract and introduction are very motivating and attractive. The idea of looking at invariances is nice and the balancing effect is a neat concept. Unfortunately, the content of the paper does not really reflect what the author claim in the first place: - The continuous time result is not really balancing anything and the authors clearly over interpret what they obtained. - 6 / 8 of the paper is dedicated to continuous subgradient trajectories in deep learning but 1 page of technical proof is dedicated to it (counting duplication) and 9 pages are dedicated to matrix factorization.  While the arguments look correct to me, it looks like the main content of the paper is about gradient descent for unconstrained matrix factorization and the connection with deep learning, despite being a nice observation looks a bit like hand waving. Some elements of the mathematical presentation could be improved.     Details:  $$ About "auto-balancing" $$ The abstract says "This result implies that if the weights are initially small, gradient flow automatically balances the magnitudes of all layers" This is wrong. Nothing in Theorems 2.1 and 2.3 and Corollary 2.1 says that the weights will adjust and balance. Nothing even says that they should be bounded. The difference remains constant, but the weights could well diverge. The paragraph after corollary 2.1 affirms without any supporting arguments that the proposed result explains convergence. In particular, line 161-162 is wrong even in the simple case of matrix factorization. The fact that two numbers a and b satisfy a-b small does not mean that a or b are small. It seems to me that Theorem 2.1 is actually a special case of Theorem 2.3. Why giving a detailed proof for both of them then?    $$ Why Gaussian random initialization? $$ Theorem 3.1 and 3.1 are stated with high probability over the random Gaussian initiailization. This is by no mean sufficient. Is 3/4 a high probability? Do the authors mean that it can be arbitrarily close to 1? How to tune the parameters then? Without a proper quantification, the result is of very little value. This can also be seen in the proof of Lemma 3.1, line 453, the proper way to present it would be to say which event is considered, to condition on that event and to estimate the probability of this event to be observed. Furthermore, I do not understand why the authors need Gaussian initialization. The main proof mechanism is that if initilization is close enough to the origin, then iterates remain bounded. This has nothing to do with Gaussianity. The authors could choose uniformly in a compact set, a hypercube is easy to sample from for example. The proof arguments would follow the same line but hold almost surely over the random initialization. The authors would avoid the non quantitative high probability statement and the incorect use of epsilon / poly(d).   $$ Confusion about smoothness $$ There is a confusion throughout the paper about the notion of smoothness: - Line 35: f is not smooth. - Line 105: the objective is not smooth - Line 106: balancing implies smoothness - Line 162: the objective may have smoothness - Line 402: we prove that f is locally smooth  This is completely misleading and mixes two important notions: - Smoothness is the property of being continuously differentiable, eventually several times, the more times, the more smooth (see wikipedia "smoothness" math page). - Optimization and ML people introduced notions of \beta-smoothness, which is just Lipschitz continuity of the gradient.  The two notions are complementary. From an analysis point of view, being non smooth is the contrary of being smooth: not differentiable or extended valued for example. However being non-smooth is not equivalent to "not being beta-smooth" or more precisely "not being beta-smooth for any beta". To my understanding the appropriate notion of "not being beta-smooth for any beta" is that of stiffness (see for example Convex Analysis and Minimization Algorithms I: Fundamentals, Jean-Baptiste Hiriart-Urruty, ‎Claude Lemarechal page 375), that is smooth but with a modulus so big that it looks like nonsmooth numerically. This notion is pretty common in numerical analysis (see "Stiff equation" on wikipedia).  The discussion in the main text is absolutely missleading: f is not smooth? f is a polynomial, it is infinitely smooth but it does not have a global smoothness modulus. Balancing implies smoothness? Smoothness is already here, twice continuous differentiability implies beta-smoothness on any bounded set. We  prove local smoothness for f? As a polynomial, f is locally smooth, this does not require a proof, the authors actually compute a smoothness modulus.     $$ Is the statement 5 = O(4) true or false? $$ In Theorem 3.1, the authors use N(0, \epsilon / poly(d)). Would 10 be $\espilon / poly(d)$ for example? Similarly in 266, $d_1 = \theta(d_2)$, would $1000$ be $\theta(500)$? or not? Asymptotic notations are asymptotic because they describe limiting behaviour which means stabilisation when some parameter increases or decreases. In the first statement, epsilon and d are fixed, similarly, d_1 and d_2 are fixed in the second statement. In addition to be mathematicaly meaningless, this provides no clue about how to choose variance in Theorem 3.1.    $$ Minor remarks $$ - Notations the notation [.] is both used for the elements of a vector and for a set of integers and this sometimes makes reading not so easy. - Line 139, may be the authors could mention that the only homogeneous functions in one variable are more or less Relu like functions (linear when restricted to R+ and R-). - Equation (5), why should a solution of the differential inclusion exist, why this problem is well posed? - Line 197, it would be nice to have a more precise reference to a particular result and explain why this chain rule should hold for the specific situation considered in this work. - Equation after line 206, an equality is missing. - More explaination would be welcome after line 207. - Line 291, connections between optimization and ODE have been known for a while and investigated extensively in the early 2000s by the mathematical optimization community, in particular Hedy Attouch and his team. - Line 381, typo, theorem 2.3 - Line 435, argument is missing for boundedness of V - Equation (16), there is a typo. - I did not have time to check the rank 1 case proof in the appendix.