Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this manuscript, the authors study the trajectory of mirror descent to optimize the unregularized empirical risk functional to solve low-rank matrix estimation problems. They characterize the trajectory of mirror descent with different mirror maps and showcase an implicit bias towards certain structures in solutions. In particular, when equipped with either the spectral hypentropy map or spectral entropy map, they show that mirror descent converges to a global minimizer that minimizes a particular quantity depending on the singular values of the resulting matrix. This quantity interpolates between the nuclear norm and Frobenius norm for the spectral hypentropy map and is a linear combination of the nuclear norm and von Neumann entropy for the spectral entropy map. They also show algorithmic guarantees for mirror descent to solve matrix sensing and matrix completion problems that operate with sample complexities on par with traditional nuclear norm minimization approaches, without explicit regularization. Finally, a connection between gradient descent over the parameterization $UU^T - VV^T$ and mirror descent is shown and toy experiments show mirror descent and gradient descent behave similarly.
main_review: # Originality

There has been a flurry of interest in understanding implicit bias in matrix factorization problems, and this work provides an interesting perspective by studying the solutions chosen by mirror descent methods for various mirror maps. Similar results have been reported in [13], but the proof techniques in this work (direct analysis of mirror descent trajectory) and [13] (KKT conditions) differ from one another. The precise formulae presented on which minimizers are chosen appear to be novel as well. The shown equivalence between exponentiated gradient and mirror descent is nice, but not entirely novel as it appears in [35] for the vector-valued case.

# Quality

- Strengths: - The paper is well-written. - To the reviewers knowledge, applying mirror descent to solve matrix factorization problems and analyzing its implicit bias towards low-rank solutions appears novel. Moreover, the characterization of their preferred solutions holds in fairly general settings (e.g., no assumptions on the measurement matrices $A_i$ aside from the existence of a $0$ loss matrix). - The results on recovery guarantees for matrix sensing/completion hold with sample complexity on par with convex nuclear norm minimization techniques. - The connection between exponentiated gradient and mirror descent is interesting and extends previously known results to show the convergence of mirror descent to small nuclear norm solutions in the small initialization scale regime. 

- Weaknesses: - Mirror descent would not be a practical algorithm to use due to computational complexity and seems to perform essentially the same as standard gradient descent - No convergence rates are provided in the theoretical analysis of applying mirror descent to matrix sensing/completion. The results only establish convergence to a neighborhood of the underlying low-rank matrix. Moreover, these neighborhoods depend logarithmically on the parameters $\beta$ (for hypentropy) and $\alpha$, the initialization size, for the entropy map so that to achieve $\epsilon$ precision, one would need $\beta$ or $\alpha$ to behave like $\exp(-1/\epsilon)$. In addition, in the matrix completion setting, a term depending on the sample complexity appears in the estimation bound, which would require $m = \Omega(nn’\log^2(n’))$ to make small, but the theorem operates in the $\Omega(r (n + n’)\log^2(n’))$ regime. Hence, while the sample complexity in the theorem does scale in the same way as nuclear norm approaches, the resulting error bounds could potentially be quite large even for exponentially small $\beta$ or $\alpha$. Could the authors comment on this point and, perhaps, why the error bound scales this way? My main concern is that the bound may be vacuous when operating in the traditional nuclear norm sample complexity regime.

# Clarity

Overall, the paper is well-written and easy to follow. Related work seems to be cited well and the authors do a good job of discussing their results in relation to others on implicit bias in matrix factorization. Here are a couple of typos I found:
- pg 1 line 33 “when then” -> “when the”, pg 3 line 105 “numercal” -> “numerical”, pg 3 line 109 “largeg” -> “large”

# Significance

This work shows that mirror descent in matrix estimation problems exhibits an implicit bias towards certain structured solutions, and precisely characterizes this structure. I think that this does inspire research into further analyzing the role of mirror maps in other estimation problems and in analyzing the potential implicit bias of other first order algorithms.
limitations_and_societal_impact: There are no clear societal impacts of this work. The authors discuss some of the downsides and limitations of their approach (namely, the computational cost of applying mirror descent). Another limitation that should also be discussed is the potential looseness of the error bounds.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper provides the convergence analysis of mirror descent for matrix sensing to particular minimum norm solutions. The updates that are studied are induced by the hypentropy and von Neumann divergences. The authors analyze multiple interesting cases including matrix completion and the case where the instances satisfy the RIP. They also provide some experimental evaluations to validate their findings.
main_review: The paper studies an interesting problem and greatly generalizes the results in [13] and [14]. There are a few remarks about the analysis:

1) Although hypentropy is an interesting divergence, it is only an approximation of the squared Euclidean and KL divergence in the limit cases. A more natural extension is the tempered KL divergence which was partially analyzed in [1]. I believe most of the analysis may carry over.

2) The construction in Eq. (15) is interesting, but not exactly related to the reparameterization of the Exponentiated Gradient Unnormalized (EGU) algorithm. The exact reparameterization for the vector case was discussed in (Amid and Warmuth, 2020) along with regret bounds for the discrete case. It would be interesting to extend the analysis to the matrix case where matrix U is updated using gradient descent.

Reference:
Ehsan Amid and Manfred K. Warmuth. "Winnowing with Gradient Descent". COLT, 2020.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors analyze the convergence of  mirror descent  in matrix sensing for specific selection of mirror maps. Specifically, they prove that when the mirror map is the spectral hypentropy or spectral entropy then MD converges to global minimizers of the empirical objective minimize quantities related to the nuclear, the Frobenius or the Von Neumann entropy. 
main_review: 
Strengths
- The main contribution of the paper is the derivation of Theorems 1 and 2 which establish convergence of mirror descent (MD) to global minimizers of the empirical loss of the matrix sensing problem that minimize certain quantities related to nuclear norm, Frobenius norm and von Neumann entropy. These results are interesting and provide an insight into the interplay between the geometries induced in mirror descent and the implicit regularization phenomena that are brought up. 
- Theorems 3 and 4 present recovery guarantees for the proposed mirror descent algorithm, the first of this kind in the framework of implicit regularization.

Weaknesses
- The contribution of these results to already existing work is somewhat limited given Theorem 1 of [19], which proves that MD converges to minimizers of the Bregman divergence. That being said, though the authors provide an alternative proof and focus on specific mirror maps, the added knowledge seems not to be  that significant.  The authors should make more clear the advantage of their proof as compared to the one followed in Theorem 1 of [19]. 
- From a practical point of view, the selection of the mirror maps gives rise to computationally expensive SVD steps per iteration of the algorithm. That being said, it is so clear what are the advantages of an implicitly regularized algorithm compared to an explicitly regularized one.

Minor comments 

- The first 3 paragraphs of Section 1.1  present the contribution without explicitly referring to the added knowledge to the existing literature. The authors should rewrite that part and clarify what point is new and what is not.
- Typos: 
 - line 105 : numerical
- line 109 : large
- line 146: identity
-line 164: descent
-line 345: regularization
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the implicit regularization of a particular algorithm, mirror descent, for matrix recovery problems. 
main_review: I think the paper presents an interesting phenomenon that is also present in mirror descent.  I believe the paper only attempts to explain some phenomenon in mirror descent, rather than arguing that the mirror descent method is the correct or a competitive method in solving matrix recovery problems.   

I have a few questions that I would like to hear the author's responses. 

1. In theorem 1, does the stepsize eta depends on the parameter beta as well? 

2. I wonder how beta affects the algorithmic performance, i.e., the convergence speed of the algorithm? Can the author comment on the relationship between the magnitude of beta and the speed of the mirror descent method?

3. I notice that the bias/difference between X_infty and X* in Theorem 3 and 4 depends logarithmically on the parameter beta. So one wants to choose a very smaller beta to reduce the bias. It seems in Theorem 4, one needs beta to be exp(-n^(1/2)) so the RHS of (13) can be smaller than ||X*||_*. Is there a tradeoff between computational complexity, and statistical error, i.e., the difference between  X_infty and X*,  in choosing beta? 

4. I think characterizing the implicit regularization phenomenon is interesting by itself. But I wonder whether there are any broader applications/impacts of the results or techniques used in the paper. 
limitations_and_societal_impact: A few limitations are discussed in the end.
review_title: null

Meta-review: All reviewers are satisfied by the authors' response and agree that this is well-written paper with solid contributions, though some of the results could be considered incremental given the existing work in [13,35]. The authors are encouraged to provide additional discussion on the points raised by the reviewers.
Decision: Accept (Poster)