Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies gradient descent optimization of matrix factorization (various forms, including the most generic case) under large learning rate. The authors prove convergence results that apply when the learning rate is larger than 2/L and up to ~4/L, and also show that optimization with large learning rates leads to dynamic balancing between the two matrix factors in the factorization, an effect that does not arise when using small learning rates. In proving some of the theorems, the authors observe the optimization can have two phases: one in which gradient descent is driven to search for flat regions, and a second phase near the global minimum where convergence occurs towards a balanced solution for the factorization problem. 
main_review: Strengths:
--The paper is well-written and very clear. Intuition is given so as to help the reader dissect the results.
--The theorems are interesting and tackle a nontrivial setting, since few works (to my knowledge) have derived strong results for convergence and implicit bias in this regime. They treat both convergence of the optimization but (interestingly) the balancing effect that occurs when using large learning rates.

Weaknesses:
--I could find no significant shortcomings in the paper.
--However, I do think the citations need to be improved. In particular, a number of the findings & discussions in Lewkowycz, et al. (2020) have some overlap with the results proven here but are not cited. For example, Lewkowycz, et al. (2020) found (1) the upper stability limit h~4/L for gradient descent, and a catapult phase that occurs between h> 2/L and < 4/L that involves search (phase 1) & subsequent convergence to a flatter minimum (phase 2). (2) The case n=1, d>1 is essentially the same problem setting analyzed there. (3) The final paragraph in Sec. 6 (starting after L278), discussing relationships to two-layer linear neural networks, was the setting studied in Lewkowycz, et al. (In fact, the u, v notation is identical.)

summary_of_the_review: I think this paper derives useful theoretical results on large learning rate optimization of matrix factorization that will be of interest to the community.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper is concerned with the non-convex matrix factorization problem. This paper considers the square loss, which is optimized via gradient descent. Due to symmetries of the problem, there are infinitely many different global minima. This paper aims to understand to which minima gradient descent with large learning rate (=step size) converges to. 

The main claim of this paper is that gradient descent with large learning rate has an implicit regularization effect, meaning that it converges to factors of the underlying matrix, which are implicitly balanced in norm. To substantiate the claim, the paper provides several theoretical results as well as some numerical experiments.


main_review: Unfortunately, I feel that both the theory and the simulations in this paper do not provide sufficient evidence of the aforementioned claims to merit acceptance. Also I feel that the presentation of the paper could be improved.

My two major concerns are the following:

1. I  feel that the theorems do not really support the claim that only large step size leads to balancing (in contrast to small step size). For example, Theorem 3.2 makes some statement provided the step size h is not too large. Then the theorem gives an upper bound on the balancing between x and y. This bound becomes stronger, if the step size is larger but how does one know that a similar bound is not also available for small step size? Even more importantly, Theorem 3.1 and 3.2 require an assumption on the step size h which depends on the initialization x_0 and y_0 (equation before l. 153). Note that the more unbalanced x_0 and y_0 are, the smaller the learning rate needs to be (and the weaker the statement in Theorem 3.2 becomes.) Hence, this result aper does not apply for unbalanced initialization and large learning rate. Analogous concerns hold for the theorems in Section 4 and Section 5. (One minor(?!) concern: Theorem 5.1 assumes already that there is convergence, i.e. the statement only holds provided that there is already convergence.)

2. The authors could provide much more experimental support. To me it seems that the only experiments which document that larger step size leads to more balancing are provided in Figure 4. However, I feel that much more extensive experiments are needed. (A larger choice of different step sizes and also a larger amount of initializations, for example scale of initialization and balancing at initialization.) Moreover, I feel that these experiments could be made more convincing if not only matrix factorization would have been considered but also the more challenging problems of matrix completion or matrix sensing.

Further comments:

-There is no labeling of the x-axis in Figures 2 and 4. I assume that this should be the number of iterations, right?!

-In both the first and third figure, gradient descent does not converge to zero loss, but the loss does become constant after some amount of iterations. Is this due to the fact that GD has reached machine precision? How do you exclude that scenario? Also it might be made more clear in the caption that the left two figures correspond to one learning rate and the two figures on the right correspond to one learning rate.

-l. 203 " We expect the convergence in (4) is 204 more complicated than ...". What does "more complicated convergence" mean?

-I feel that the readability could be increased if Theorem 3.1 and Theorem 3.2 would have been combined, i.e. one theorem instead of two. The same is true for Theorem 4.1, 4.2, and 4.3.

-I feel that the formulation of Theorem 1.1 is somewhat unclear. First of all, note that the variable "A" has been overloaded. It is the matrix in (1) as well as a scalar defined in Thm 1.1. But more importantly, the statement is unclear. For example, what happens if I set the scalar A=2/h. Then I obtained perfect balancing between X and Y, but this should not be possible?! 


summary_of_the_review: As both of theory and experiments do not substantiate the claims of the paper enough, I unfortunately cannot recommend acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the problem of minimizing matrix factorization squared error with gradient descent. They show convergence with larger learning rates than previously considered. They further show that gradient descent has an implicit bias towards finding matrix factors which are magnitude-balanced in a certain sense.


main_review: The problem is interesting. The proofs seem to be nontrivial. The technical contribution looks significant. However, I am not able to give a recommendation of acceptance due to the following issue:

* In line 160, the upper bound does not seem to be $\frac{4}{L}$. It seems to be closer to $\frac{2}{3L}$ because when $x_0, y_0$ are close to the solution, $x_0 \approx y_0$ and so $L \approx \|x_0\|^2  + \|y_0\|^2 = 2 \langle x_0, y_0 \rangle = 2 \mu.$ Then the bound on $h$ in line 152 becomes $\frac{1}{3\mu} = \frac{2}{3L}$.

Given this problem, I request the authors to argue how the proposed learning rate is large. Specifically, large learning rate compared to what?

summary_of_the_review: With my current understanding, I recommend a reject. However, I am expecting that the authors will answer my question and I will be able to give a higher score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the properties of gradient descent with large learning rate in the matrix factorization problem. The goal is to understand when gradient descent converges to a global minimum where the two factors are roughly balanced in norm, which is a shallow minimum that may be hoped to generalize better. For small learning rates (i.e. where classical optimization results guarantee convergence to a critical point), this does not happen. Hence, this paper considers learning rates beyond this regime.

For two special cases (when the matrices are 1xd or dx1), it is shown that under a large learning rate, gradient descent still converges to a global minimum, and this minimum is roughly "balanced". For the general case, it is shown that for almost any initial point, if the learning rate is such that gradient descent converges to a global minimum, then this minimum is roughly balanced.
main_review: I marginally recommend rejection.

STRENGTHS: This paper tackles an interesting question of whether large learning rate implicitly regularizes gradient descent, which has not  previously received much theoretical attention. For the 1xd and dx1 special cases of matrix factorization, experimental and (very involved) theoretical evidence is given for this regularization. The paper is for the most part very clearly written.

WEAKNESSES: The main weakness, which the paper completely elides, is that the result does not actually extend to the general matrix factorization setting (the paper states "We theoretically show the convergence of GD with large learning rate", but I could not find a theorem statement corroborating this in the general case). In particular, the main theorem for the general case assumes that the learning rate is such that GD converges to a global minimum. This seems to ignore one of the main difficulties, which is proving that even with a large learning rate GD will converge (since classical optimization arguments break down for large learning rate, and it seems quite plausible that GD could have chaotic or periodic behavior). Indeed, under the assumption that GD converges, the proof of the theorem is simply a local argument about the curvature of the various critical points (the "stability analysis"), whereas I would expect that some global argument is necessary to get convergence.

In my opinion, the paper would be much stronger if convergence were properly addressed in the general case.

OTHER COMMENTS:
- The special case proofs are quite technically involved. Is there hope for any insights from these cases that might extend to the general matrix factorization problem?

summary_of_the_review: Although this paper raises an interesting problem of implicit regularization in matrix factorization with large learning rate, and provides evidence in special cases, it does not live up to its claims for the general case: failure to converge is a well-known issue with large learning rates, so the results for the general case which assume convergence are somewhat incomplete. It's also not clear whether the proofs in the special cases can provide any insight for the general case.
review_title: null

Meta-review: The paper studies gradient descent for matrix factorization with a learning rate that is large relative to the a certain notion of the scale of the problem. In particular, they show that the use of large learning rates leads to balancing between the two factors in the factorization.

The discussion between the authors and the reviewers was fruitful in dispelling some of the reviewers' doubts and at the same time improving the paper.

The paper seems to make some contribution on a relevant problem for the ICLR community. However, even in the restricted settings they consider, the problem does not appear to be completely solved. That said, I agree with the majority of the reviewers that the step forward seems enough to warrant the acceptance.

I would still encourage the authors to take into account the reviewers' comments in preparing the camera-ready version. In particular, in the internal discussion it was suggested that the presentation of the paper could be improved by clearly stating the limitations of the current approach (e.g., the assumption of convergence in Theorem 5.1, a better discussion on large vs small learning rates w.r.t. the balancing effect).
Decision: Accept (Poster)