Implicit Regularization in Matrix Sensing via Mirror Descent
Authors: Fan Wu
Patrick Rebeschini
Venue: NeurIPS 2021 Poster (2021)
Keywords: mirror descent
implicit regularization
matrix sensing
sparsity

Abstract: We study discrete-time mirror descent applied to the unregularized empirical risk in matrix sensing. In both the general case of rectangular matrices and the particular case of positive semidefinite matrices, a simple potential-based analysis in terms of the Bregman divergence allows us to establish convergence of mirror descent---with different choices of the mirror maps---to a matrix that, among all global minimizers of the empirical risk, minimizes a quantity explicitly related to the nuclear norm, the Frobenius norm, and the von Neumann entropy. In both cases, this characterization implies that mirror descent, a first-order algorithm minimizing the unregularized empirical risk, recovers low-rank matrices under the same set of assumptions that are sufficient to guarantee recovery for nuclear-norm minimization. When the sensing matrices are symmetric and commute, we show that gradient descent with full-rank factorized parametrization is a first-order approximation to mirror descent, in which case we obtain an explicit characterization of the implicit bias of gradient flow as a by-product.

Implicit Regularization in Matrix Sensing via Mirror Descent
Fan Wu Department of Statistics University of Oxford fan. wu@stats. ox ac uk
Patrick Rebeschini
Department of Statistics
University of Oxford
retrick. mi@sstats.....m..m. ox ac uk
Abstract
We study discrete-time mirror descent applied to the unregularized empirical risk matrix sensing. In both the general case of rectangular matrices and the particular case of positive semidefinite matrices, simple potential- baase analysis in terms the Bregman divergence allows establish convergence of mirror descent wesch different choices of the mirror maps -o a matrix that, among all global minimizers of the empirical risk, minimizes quantity explicitly related the nuclear norm, the Frohenius norm, and the von Neumann entropy. In both cases, this characterization implies that mirror descent, first-order algorithm minimizing the unregularized empirical risk, recovers low-rank matrices under the same set of assumptions that are sufficient guarantee recovery for nuclear-norm minimization. When the sensing matrices are symmetric and commute, we show that gradient descent with full-rank factorized parametrization first-order approximation mirror descent, in which case we obtain an explicit characterization of the implicit bias of gradient flow as by-product.
Introduction
Matrix sensing represents paradigm in modern statistics [8] 26 27], with applications ranging from image compression [2] to collaborative filtering [18] and dimensionality reduction (34), for instance.
The goal is to recover a rank-r matrix X E Raxxn' from a set of linear measurements y; = (A,,X*)
i == 1,...... m, where the sensing matrices A, E gnxa' are observed. This formulation includes the problem of matrix completion, where a subset of the entries of the matrix X* is observed.
Most of the literature on matrix sensing is based on some form of explicit regularization or rank constraint encourage enforce low-rankness of the estimated matrix. A popular approach is based on minimizing the nuclear norm or on using explicit regularization techniques based on the
nuclear norm, e.g. [5 15 23
26
27
30 Another popular approach is based non-convex
optimization and the low-rank factorization X UV with matrices U Rexr V RR xr.
where the factorization itself enforces the low-rankness of X, e.g. 7 8 16
31 39]
The literature implicit regularization for matrix sensing is more recent and less well developed. When X is assumed to be a positive semidefinite matrix, it was first empirically observed in [14] that mininizing the unregularized empirical risk using vanilla gradient descent with parametrization X= = =UUT and random full-rank initialization close to zero yields a low nuclear norm solution, even when U Roxn i.e. when constraint the rank of X is enforced. It was later proved that, with this parametrization, gradient descent minimizes the nuclear norm under the assumption that the sensing matrices A, commute [14], when the sensing matrices satisfy restricted isometry property [19.. Gradient descent with low-rank initialization within specific "capture neighborhood" has been studied in [ which ensures that the iterates of the algorithm stay low-rank. When X* is general rectangular matrix, implicit regularization in matrix sensing has been studied through
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the lenses of deep matrix factorization in [3] 12 20 25 J and empirical and theoretical evidence is provided which suggests that notion of rank minimization is involved in the implicit bias of gradient descent. However, these works do not establish an explicit characterization of the limiting point of the optimization algorithm, e-g. in the form of a quantity that is minimized among all minimizers of the empirical risk. In the special case of full-observation matrix sensing, gradient flow has been shown to learn solutions with gradually increasing rank [[]]
Most theoretical results on implicit regularization in matrix sensing consider the continuous-ting dynamics (i.e. gradient flow), e.g. 9 12
20 25 or assume an infinitesimally small initial- ization, e.g. [4 20). Notable exceptions are III.. which makes commutativity assumption on the data matrices discrete time, and [I9], which assumes a restricted isometry property that leads to suboptimal sample complexity when the sensing matrices belong to a general class of random matrices 27 In the context of linear neural networks, the dependence of the implicit bias of gradient For instance, linear diagonal networks with shared weights were considered in 35 where it was shown that gradient descent minimizes quantity which corresponds to the l -norr in the limit - 0 and to the (weighted) f2-norm in the limit a - oc, where a denotes the initialization size. This result was later generalized in [38] using a tensor formulation, which allows for architectures including linear diagonal networks and linear full-length convolutional networks. However, these results focus on vector- based notions of norm-likk like functions that do not capture matrix-base quantities typically of interest in matrix sensing.
14
descent on the initialization has been studied in 4 22 35 [B
1.1 Our contributions
We study the implicit bias of discrete-time mirror descent in matrix sensing in both the general case of rectangular matrices and the particular case of positive semidefinite matrices. Under the only assumption on the sensing matrices A,' 's that there exists matrix achieving zero training error, we characterize the limiting point as the matrix that minimizes quantity which interpolates between the nuclear norm and Frobenius norm, parametrized by the mirror map parameter, in the rectangular case; and which is linear combination of the nuclear norm and the negative von Neumann entropy, parametrized by the initialization size, in the positive semidefinite case. Compared to results on implicit regularization for gradient descent, our framework for mirror descent is simple, and the same analysis yields results for both the case of general rectangular and positive semidefinite matrices.
In the general case of rectangular matrices, we show that mirror descent, initialized at zero and equipped with the spectral hypentropy mirror map [10] parametrized by B > O, among all global minimizers of the empirical risk, converges to a matrix that minimizes a quantity interpolating between the nuclear norm in the limit 8 + 0 and the Frobenius norm in the limit 3 - co. As consequence, our result implies that, for 3 + O, mirror descent can recover a rank-r matrix X* under the same set of assumptions that is sufficient for nuclear norm minimization to be successful, namely when the sensing matrices A, 's satisfy the restricted isometry property with restricted isometry constant smaller than some absolute constant (27). or if X* satisfies incoherence condition and r(n + n²) (modulo constants and logarithmic term) random entries of X are observed (26). To the best of our knowledge, this is the first recovery guarantee for an implicit regularization-bite based algorithm that does not explicitly enforce low-rankness in general rectangular matrix sensing.
In the particular case of positive semidefinite matrices, we can alternatively consider the spectral entropy mirror map and show that mirror descent, initialized at aI for any a > O, converges to positive semidefinite matrix that minimizes a linear combination of the nuclear norm and the negative von Neumann entropy, where the relative weights are controlled by the initialization size a. While the limit a - 0 corresponds to minimizing the nuclear norm as in the case of rectangular matrices, the limit a + do corresponds to maximizing the nuclear norm. This also translates into guaranteed recovery of a low-rank matrix X for a + O under the same assumptions that are sufficient for nuclear norm minimization 26 27). A comparable result for gradient descent with full-rank factorized parametrization has been established in [19] under stronger assumption on the restricted isometry constant, which is assumed to be smaller than a quantity depending on both the rank and the condition number of the matrix X and translates into a sub-optimal sample complexity.
We establish our results using a potential- based analysis for mirror descent terms of the Bregman divergence, which provides an alternative proof technique to characterize the limiting point of mirror descent compared to the analysis based on KKT optimality conditions used in [3] As by-product, our proof of Theorem yields an alternative proof of Theorem I in [13 The advantage of our

---

approach is that convergence of mirror descent does not need to be assumed a-priori and can instead be established using convexity of the empirical risk. The analysis terms of the Bregman divergence is not limited to convex settings and has been applied to non-convex problems, e.g. [36 37 40 hence can of more general interest to investigate the phenomenon of implicit bias.
and
In the case of square matrices, we show, assuming that the sensing matrices A,'s are symmetric and commute, that gradient descent with full-rank parametrization X UU VV U. R= is a first-order approximation to mirror descent equipped with the spectral hypentropy, where the initialization size corresponds to the mirror map parameter 3. A similar connection between mirror descent and reparametrized gradient descent has been established in the vector-case [T TO 33 36]. Similarly, we show that gradient descent with full-rank parametrization X UU E Fax= is a first-order approximation to mirror descent equipped with the spectral entropy when the sensing matrices are symmetric and commute, thus recovering a generalization of Theorem in [1 which holds for any positive initialization size a > 0 (rather than in the limit - 0).
We present numerical simulations which suggest that, in some regimes, our results on the dependence on the initialization size for mirror descent might be indicative for the behavior of gradient descent, even when the sensing matrices A do not commute. More precisely, the final estimates of gradient descent and mirror descent closely track each other when the number of measurements is sufficiently large for nuclear norm minimization recover a planted low-rant matrix, while gradient descent seems to put more emphasis on lowering the effective rank (28) at the expense of a higher nuclear norm when fewer measurements are available, which supports the empirical observations in 3 20
2 Background
We begin by introducing some notation used throughout this paper. We use boldface upperease letters denote matrices and boldface lowercase letters denote vectors. We write || ||-. Il || and -1l for the nuclear, Frobenius and spectral norm, respectively, and denote by (X,Y) tr(X Y) the standard Frobenius inner product. We write S", s C RR" RR*x for the set of symmetric and positive semidefinite matrices, respectively. Without loss of generality, we will always assume < n'.
We first give a brief overview unconstrained mirror descent (with matrix arguments).
Let D C pnxn' be an open convex set. We say that D + E mirror map it is strictly convex, differentiable, and its gradient takes all possible values, i.e. (VΦ(X): X E D) Raxx'. Given a mirror map 4 the associated Bregman divergence is defined as Dx Y) +(X) o(Y) (V
Then, the mirror descent algorithm to minimize function f D + R is defined by the update (x(X++1) v 7/. V (X.))
where 7/ > 0 is a sequence step sizes. We approach the problem of matrix sensing, where we are given measurements (A,, Yi 1 by minimizing the unregularized empirical risk
1
f(x)
(A,,,) -1))
(3)
2m
using mirror descent equipped with the spectral hypentropy mirror map, which is defined as [10
$ 4 = Σ o. aresinh
ai ( Vo? 32,
(4)
for some / > 0, where {a:)1_ denote the singular values of X. We provide expressions for the gradient 4hg and discuss the per-iteration computational cost of the corresponding mirror descent algorithm in Appendix A
If the optimization is restricted to positive semidefinite matrices X E |R we can replace Bux'' with S" above definitions and consider the spectral entropy (using the convention 0 logg0 = 0)
+ X tr (x log - X),
(5)
which is well-defined the set of positive semidefinite matrices ST.
3

---

3 Algorithmic regularization of mirror descent
In this section, we show that mirror descent, equipped with the spectral hypentropy mirror map (4) in the rectangular case and the spectral entropy mirror map (5) in the positive semidefinite case, converges to a global minimizer of the empirical risk f that minimizes a quantity which interpolates between the nuclear norm and the Frobenius norm in the rectangular case, and is linear combination of the nuclear norm and the negative von Neumann entropy tr(X log X) > X log A in the
positive semidefinite case, where (Ar) denote the eigenvalues of the matrix X E S4.
The following Theorem applies to matrix sensing in the case of general rectangular matrices.
Theorem (Rectangular case). Consider the mirror descent algorithm 22) with mirror map (4) with parameter 3 > 0 and initialization X.- O. Suppose that the step sizes satisfy = rj S. where e. > a constant depending on the sensing matrices A;'s, observations yi 's and parameter B, and that there exists a matrix X' satisfying f(X') = O. Then, mirror descent converges to matrix x lim X₁ which, among all global minimizers of f. minimizes
n2
1, + o, log oc (a((o
of
V +
(6)
where {o;) denote the singular values of X We have, for any t 0,
Do, (X.,, Xo)
((X,) 5
Proof sketch. The following identity is key to our proof and characterizes how the Bregman diver- gence between any reference point X' and the mirror descent iterates X, evolves:
D& ( D& (X' x,) (V((())) - XX' + D2. (X,, X X
(8)
which follows from the definition of the Bregman divergence (T) and the mirror descent update
Letting X' be any global minimizer of f. we can compute (X), X, - -X') 2x)(),) where
used the assumption that there cxists matrix X' achieving zero training eπror f(X') 0. Using
the strong convexity of the spectral hypentropy mirror map, we can bound D (X,, X(+1) to show
Dag X', X(+1) Da, (X', X,) S -xf(X)),
for any global minimizer X' f. Since the Bregman divergence D&, (X', X2) is bounded from below by zero, this means that the empirical risk f(X,) must converge zero, which in turn implies that X, converges to global minimizer of
To which global minimizer mirror descent converges observe that the difference in (8) does not depend on the reference point X', as long as X' is global minimizer of f. This means that the Bregman divergence Dag (X', X.) is decreased by the same amount for all global minimizers X', which then implies that X, must converge to the global minimizer which is closest to X, in terms of the Bregman divergence. From this observation it follows that X lim X, minimizes the quantity in (6) among all global minimizers of f.
The bound (7) on the empirical risk of the last iterate f(X;) can be shown using the smoothness of the empirical risk f and the strong convexity of the spectral hypentropy mirror map. A detailed proof of Theorem can be found in Appendix B.T
We remark that the step size can be chosen independently from the parameter / if 3 is chosen from some interval bounded away from infinity, e.g. B (0, 1).
An analogous result holds for mirror descent equipped with the spectral entropy mirror map optimizing over positive semidefinite matrices.
5 when
Theorem 2 (Positive semidefinite case). Consider the mirror descent algorithu with mirror map
and initialization X, = al for some a >> Suppose that the step sizes satisfy tj. = S G, where O is constant depending the sensing matrices A, 's and observations y 's and that there

---

exists positive semidefinite matrix X' satisfying f(X') = O. Then, mirror descent converges to positive semidefinite matrix x lim, X, which, among all global minimizers of f. minimizes
a 1 log -1) A3 + A log As,
a
where (Ae)i=i denote the eigenvalues of X We have, for any t 2 0,
f(X,) Do(X no, Xo)
(10)
nst
Theorem 2 can be proved the way as Theorem see Appendix
B.2 Neither Theorem requires
any assumptions on the sensing matrices A As beyond the existence of matrix X' achieving zero training error f(X')
which, for instance, is satisfied when {A, are linearly independent and m S nn' in the rectangular case or m S n(n + 1)/2 2 in the positive semidefinite case.
On the implicit bias of mirror descent. The implicit bias of mirror descent in linear models has previously been studied using KKT optimality conditions in [33] Once we have established convergence of mirror descent towards global minimizer of Theorem of [13 to characterize the limiting point of mirror descent. Instead, our analysis of the Bregman divergence Da, (X', X2) reveals that each iteration of the mirror descent algorithm ( decreases Da, [X', X,) by the same amount for all global minmimizers X' of f. provided that
could have alternatively invoked
(V/())) X, - X') = (VI(X.)), -
for any two global minimizers X' and X" of From this observation it immediately follows that mirror descent converges to the global minimizer of that minimizes the quantity De (X', Xn) among all global minimizers of f. Since this equality satisfied under the assumptions of Theorem 1 in [13]. our analysis presents an alternative proof technique for Theorem KKT optimality conditions and hence does not need assume convergence of mirror descent.
[3] that does not use
On the mirror map parameter and initialization size. In the rectangular case, minimizing the quantity in (6) is equivalent to minimizing the nuclear norm in the limit 3 - 0, and equivalent to minimizing the Frobenius norm the limit 3 > xG, see Appendix B.6 for further details. This can be seen matrix analogue of the result in (35). which shows for linear diagonal networks with shared weights that gradient descent minimizes a quantity interpolating between the & and (weighted) lg norms. For network with two layers, this architecture corresponds to the parametrization x = u ④ 11 V O v, where @ denotes the elementwise Hadamard product and with which gradient descent has been shown be first-order approximation to mirror descent equipped with the hypentropy mirror map in the vector-case, see e.g. 33 36. In the positive semidefinite case, minimizing the quantity in (9) also corresponds to minimizing the nuclear norm in the limit while in the limit a - co the coefficient log(1/a) - tends to minus infinity, and minimizing the quantity in ( is equivalent to maximizing the nuclear norm.
4 The estimation problem
In this section, we consider the estimation problem of reconstructing a rank-r matrix X* from a of linear measurements y; (A,, X*), i 1, I,..., m. Theorem [ and Theorem 2 imply that mirror descent, equipped with the spectral hypentropy mirror map (4) or spectral entropy mirror map (5). approximately minimizes the nuclear norm for small mirror map parameter 3 or small initialization size Hence, mirror descent, a first-order algorithm minimizing the unregularized empirical risk, can recover a low-rank matrix X under the same set of assumptions which is sufficient for nuclear norm minimization to be successful.
4.1 Matrix sensing with restricted isometry property
The following restricted isometry property has been shown to be sufficient to guarantee recovery of low-rank matrices using nuclear norm minimization [27), and has also been used in [19] to show that gradient descent with full-rank factorized parametrization recovers X
5

---

Definition 1 (Restricted isometry property (27)) A set of matrices Ai...., Am E Ra satisfies (r, (. restricced isometry property (RIP) for any matrix X E Raxn' with rank at most r, we have
1/2
(1-8)lX = (A
S {1+
With this definition, we have the following recovery guarantee for mirror descent.
Theorem 3. Assume that the set of measurement matrices { {A,) satisfies (5r, 00-rettrd isome-
try property with ò S 0.1. Then, the mirror descent algorithm described in Theorem 7 with parameter 3 <<< 1.05en
X' converges to matrix Xxx lime-poo Xx that satisfies
x X + (1 + AB) log
Xxx - X S
(1I)
Cov3r
where C = 2 3 8(1+ ()) and Ag = [
log( (1.05m)
If, additionally, n' and X* is positive semidefinite, then the mirror descent algorithm described in Theorem 2 with |X* ll= em
converges to a positive semidefinite matrix Xoc that satisfies
X 11 Ax
(12)
Cav3r
where 4a =
|+|]|//)-1 - 1)-1
log
Among the existing results on implicit regularization in matrix sensing, the result that is perhaps most closely related to Theorem Bs Theorem 1.1 in [19]. which considers the positive semidefinite of matrix sensing with full-rank parametrization X UUT, U E TRax, and shows that gradient descent recovers X under the assumption of restricted isometry with constant s c/(x3 Vrlog" n). where K is the condition number of X* and
is absolute constant.
The analysis that leads to Theorem 3 differs significantly from the proof of Theorem 1.1 in [9]. The proof of Theorem 1.1 in [19] involves an analysis of the trajectory of gradient descent, relating it to the population dynamics defined by the population risk E(A,)aI [U,, = U|U
X*1 1|
and identifying adaptive rank-r subspaces to which the iterates U, are approximately confined. On
the other hand, Theorem follows from Theorem and Theorem 2 which rely on a simple analysis of the evolution of the Bregman divergence, and employs arguments similar to the ones used in (27] to prove that RIP is sufficient to guarantee that nuclear norm minimization recovers X Further, our analysis applies both to the case of rectangular and positive semidefinite matrices, while the results in [9] only hold for the full-rank parametrization X UUT U E R2xn for which an extension to general rectangular matrices does not seem to be trivial see e.g. [16
21 29
39)
Sample complexity and condition number. The restricted isometry property assumption in Theorem 1.1 in requires a restricted isometry constant 5 S c/(x3 /ogg"" n) for an absolute constant c > O. which leads to sample complexity of (re log" n) if the sensing matrices A, 's belong to general class of random matrices
[27 It is conjectured in [19 that the dependence of 8 on the rank r and condition number к is not tight, and that 8 only needs to smaller than some absolute constant. On the other hand, Theorem 3 only requires 8 < 0.1, which is the same assumption that is sufficient to guarantee that nuclear norm minimization recovers low-rank matrices [27] and leads to a result for mirror sample complexity of O(n + n )r log(nn')) To the best of our knowledge. descent is the first recovery guarantee for an implicit regularization- based algorithm for (rectangular) matrix sensing that only requires the same assumptions nuclear norm minimization 27
Convergence speed and dependence on intialization size. The analysis along the trajectory of gradient descent in [19] allows to establish convergence speed guarantees and polynomial dependence of the estimation error U X I| on the initialization size a. On the other hand, we have no convergence speed guarantees for mirror descent (beyond the bounds on the empirical risk (7) and (10), and the final estimation error X X+ depends logarithmically on the parameters
and B, which can lead to an unpractically small value for and being required to reach some

---

desired accuracy E. Nonetheless, our result guarantees exact recovery of X' in the limit a, 8 - 0, which is setting often considered in the literature, e.g. [4
20 35
We remark that, beyond the aforementioned result on implicit regularization in matrix sensing 19] similar recovery results that include convergence speed guarantees and polynomial dependence on the initialization size have also been established for implicit regularization-basel algorithms in the context of sparse linear regression [3 and sparse phase retrieval 36 37.. However, these results all require a sample complexity that scales quadratically in the respective notions of sparsity, and we leave it to future work to investigate whether it is possible establish convergence guarantees that include a convergence speed analysis and depend polynomially on and when sample complexity that scales only linearly in the rank r of X* is assumed.
4.2 Matrix completion
In matrix completion, a subset of the entries of the matrix X* observed, and the corresponding sensing matrices A,'s do not satisfy the restricted isometry property. Instead, incoherence condition together with a sufficient number of randomly observed entries have been used to guarantee recovery for nuclear norm minimization (26) and gradient descent [22], for instance.
Definition (Coherence (6). Let U S R" be a linear subspace of dimension r and Py the orthogo- nal projection onto U. The coherence of U is defined as ((e,) denotes the canonical basis)
m(U)
n2
max I
Pueel
We have the following recovery guarantee for mirror descent under the same assumptions as in [26].
Theorem 4. Let X E pu be a rank-r matrix with (compact) singular value decomposition
X = UEVT, where U Ruxr, V R='x" and E E Rexr, Assume that:
A1 The row and column spaces of X* have coherences bounded by pa > 0.
A2 The matrix UVT has maximum entry bounded by μ1 /r/nn' in absolute value for some μ41 O.
Suppose that we observe m entries of X* with locations sampled uniformly at random. Then, if m 32cmax ( pi Jr(n + n') log" (2n') for some
the mirror descent algorithm described
in Theorem with B < 1.05en
[I* converges to a matrix X = limy-+00 X, that satisfies
n2
1 (128 log n'
(128cnn'
|X - -X
A I 66
+ (1+
(13)
log
X-II 3
9m
with probability at least 1 6 log(n' (nnemnn)n++nnn))) (n+ (n1)2-2 2VC, where Ag = (log( X' X-||| 1911//9)11111 -1
log(1.05m)
If. additionally, = n' and X* is positive semidefinite, then the mirror descent algorithm described in Theorem with < |X converges to positive semidefinite matrix X that satisfies
X X XX*1| (1+
1128cn loog n )²)
(14)
9m
where Aa =
[og[[] (1X1I1//))- 1)
log
To the best of our knowledge, there are no recovery guarantees in matrix completion for an unreg- ularized empirical risk minimization-basel algorithm that does not explicitly enforce the low-rank constraint. For instance, when X* [Rax is positive semidefinite, Theorem 2 in [22] establishes recovery guarantee for gradient descent with low-rank parametrization X UUT where U E Raxr, applied to the unregularized empirical risk with a sample requirement of order n log n.
5 Connection with gradient descent
In the vector-case, it been established that gradient descent with parametrization u V a first-order approximation to mirror descent equipped with the hypentropy mirror map 10 33 36
7

---

and general framework connecting mirror descent and reparametrized gradient descent was studied in [T. natural question is whether such connection also extends the matrix-case.
In the following, we consider matrix sensing with square symmetric sensing matrices A E IR i ,..., m. Consider the following exponentiated gradient algorithm given by
X = -U- V (VAX. te -
VienV((X.) + +
(15)
U 1+1
V 4+
2
2
When considering the full-rank parametrization X= U0 VVT, where U, V E R'*" gradient descent on the variables (U, ) a first-order approximation to the exponentiated gradient algorithm defined in (15), with the step size rescaled by a constant factor and the approximation being exact in the limit r O, Appendix [3.6 for details. The gradient descent algorithm considered in
B [1
19 20
can be obtained by initializing Vo = 0.
Proposition 5. Assume that the sensing matrices A;'s 's are symmetric and commute. Then:
1. Mirror descent equipped with the spectral entropy mirror map (5) and any positive definite initialization Xo which commutes with all A; 's (e.g, Xo = al for some a > 0) is equivalent to the exponentiated gradient algorithm defined in (15) with initialization Un- = Xu and Vo
2. Mirror descent equipped with the spectral hypentropy mirror map (4) with parameter 3 > 0
and inifialization Xo 0 is equivalent to the exponentiated gradient algorithm defined in 15
with initialization Un = Vo 3T..
As Corollary, we obtain a generalization of Theorem 1 in 14. Let [[T))=((UU])
Corollary 6. Assume that the sensing matrices A 's are symmetric and commute, and that there
exists X' E S*, satisfying f(X') 0. Then, the gradient flow defined by dU, ===-a -V((U)) and any initialization satisfying Ug al converges to a matrix Uxo minimizing
di
Σ log - -1 -
A A,
among all global minimizers of f, where {de denote the eigenvalues of the matrix U UT
This result generalizes Theorem in [14] in two ways: first, we obtain precise characterization of the quantity that is minimized for any initialization size a > 0, which indeed coincides with the nuclear norm in the limit a 0. Second, convergence a global minimizer is assumed in Theorem 1 in [4), which is non-trivial a-priori, since the optimization problem in U, is non-convex. On the other hand, we show convergence of mirror descent Theorem 2 which then carries over to gradient flow on the non-convex objective f via Proposition (when the A,'s are symmetric and commute).
Numerical simulations
In this section, present numerical simulations examining the dependence of the final estimates of mirror descent equipped with the spectral entropy (5) and of gradient descent with full-rank parametrization X UUT, U Ra**, the initialization size for random Gaussian sensing matrices A.....
We evaluate the nuclear norm | the reconstruction error X p. and 1 Pi pt), where pt a:/||X] i = 1, ......... n, denote the normalized singular values of X. Numerical simulations for matrix completion are provided in Appendix cland yield similar results for random Gaussian sensing matrices.
the effective rank (28) effrank(X) = exp( Ei=
Our experimental setup is as follows. We generate a rank-r positive semidefinite matrix by sampling random matrix U* guxr with i.i.d. (0, entries, setting X (*?U+) and normalizing |X = 1. We generate m symmetric sensing matrices A; = (B, + B,). where the entries of B, are i.idd. (0 1). We run mirror descent and gradient descent with initialization X, al and constant step sizes μ = 1 and μ = 0.25, respectively, for T = 5000 iterations, and vary the initialization size a from 10-1 to 10 10, For reference, we also include the ground truth X and the
estimate obtained from minimizing the nuclear norm, argmin ||||| X = 0, (XX 0}, using the

---

eifective core
reconntrratinn
docemt
iriiiaiizaiion
intiafization
inttalization
gread
goond bruh
errer
vadio
ground oust
gridert docert virro delcent
picer dacert
rirre desce
eáinor deseet
modear
Affectto
017
Intilication
Infiallattio size
Intialication size
Figure 1: Nuclear norm, effective rank 28 and reconstruction error against initialization size a for n 50 and r 5. Top row: m = 3nr measurements. Bottom row: m nr measurements.
cvxopt package. The experiments for Figure D were implemented in Python 3.9 and took around 10 minutes on machine with 1.1-GHz Intel Core i5 CPU and GB of RAM.
With m 3nr measurements (Figure top row), nuclear norm minimization coincides with X". In this case, our simulations show that the estimate of gradient descent closely tracks the estimate of mirror descent for all initialization sizes in terms of nuclear norm, effective rank [28] and reconstruction error, though the sensing matrices do not commute. When have m measurements (Figure bottom row), nuclear norm minimization does not recover the planted matrix X and our simulations show that gradient descent puts rank at the expense of a higher nuclear norm for initialization sizes smaller than 10-3, Since Theorem 2 guarantees that mirror descent minimizes the nuclear norm in the limit - regardless of the number of measurements, this is in line with the observations in [ 20), which suggest that notion of minimiziiiiz is involved in the implicit bias of gradient descent.
emphasis lowering the effective
7 Conclusion
In this paper, we analyzed discrete-time mirror descent for matrix sensing, equipped with the spectral hypentropy mirror map in the case of general rectangular matrices and equipped with the spectral entropy mirror map in the particular case of positive semidefinite matrices. We showed that mirror descent minimizes quantity that interpolates between the nuclear norm and Frobenius norm in the rectangular case, and is a linear combination of the nuclear norm and the negative von Neumann entropy in the positive semidefinite case. We used this result to show that mirror descent, first-order algorithm minimizing the unregularized empirical risk that does not explicitly enforce low-rankness of its iterates, can recover low-rank matrix X under the set of assumptions which is sufficient for nuclear norm minimization to recover X 26 27].
A downside of mirror descent compared to gradient descent with full-rank factorized parametrization, which is an alternative implicit regularization-ben based algorithm for matrix sensing. is its computational cost: the spectral hypentropy requires singular value decomposition in each iteration, while the spec- tral entropy requires computing a matrix exponential in each iteration, see Appendix A For general sensing matrices, the computational cost of mirror descent is of the same order that of gradient de- scent, since singular value decomposition takes O(n²n') operations and matrix exponentials can be computed in Onn²) operations, while evaluating the gradient V V m requires O (mnn') operations, and ner product (A,, X) can be computed in (1) operations in matrix completion, in which case the computational cost of gradient descent with full-rank factorized parametrization is dominated by the multiplication of two n X n matrices. When r & min(n, n'). neither implicit regularization- based approach achieves the computational efficiency of gradient descent with low-rank factorized parametrization X UVT, where U Raxr, V RR''xr see e.g. (2
- >n ((A,, X) y;) is typically required to recover X However, the in-
Previous results on implicit regularization-basee algorithms in matrix sensing 19] sparse linear regression [32 and sparse phase retrieval [36] 37 establish convergence speed guarantees and poly-

---

nomial dependence on the initialization size while sample complexity that scales quadratically in the respective notions of sparsity is required. On the other hand, our results for mirror descent in matrix sensing require a sample complexity that scales linearly in the rank of X but do not establish any convergence speed guarantees, and the bound on the estimation error depends logarith- mically on and B. We leave bridging this gap, i.e. establishing convergence speed guarantees with polynomial dependence on a and 3 while only assuming a linear sample complexity, to future work.
Acknowledgments and Disclosure of Funding
Fan Wu is supported by the EPSRC and MRC through the OxWaSP CDT programme (EP/L016710/1) Patrick Rebeschini was supported in part by the Alan Turing Institute under the EPSRC grant EP/N510129/1.
References
[1] E. Amid and M. K. Warmuth. Reparameterizing mirror descent as gradient descent. In Advances in Neural Information Processing Systems, pages 8430-8439, 2020.
[2] H. Andrews and C. Patterson. Singular value decomposition (SVD) image coding. IEEE Transactions on Communications, 24(4):425-432, 1976.
[3] S. Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pages 7411-7422, 2019.
[4] S. Azulay, E. Moroshko, M. S. Nacson, B. Woodworth, N. Srebro, A. Globerson, and D. Soudry. On the implicit bias of initialization shape: Beyond infinitesmial mirror descent. arXiv preprint arXiv:2102.0977
2021.
[5] J. F. Cai, E. J. Candès, and 7. Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4):1556-198) 2010.
[6] E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, (6):717-77,, 2009.
[7] Y. Chen and M. J. Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint 150. 2015.
[8] Y. Chi, Y. M. Lu, and Y. Chen. Non-convex optimization meets low-rank matrix factorization: overview. IEEE Transactions Signal Processing, 67(20):523-55263 2019.
[9] A. Eftekhari and K. Zygalakis. Implicit regularization in matrix sensing: Initialization rank matters. arXiv preprint arXiv:2008. 2021.
[10] U. Ghai, E. Hazan, and Y. Singer. Exponentiated gradient meets gradient descent. In Interna- tional Conference Algorithmic Learning Theory, volume 117, pages 386-407, 2020.
[11] G. Gidel. F. Bach, and S. Lacoste-Julien. Implicit regularization of discrete gradient dynamics in neural networks. Advances in Neural Information Processing Systems, pages 3196-3206, 2019.
[12] D. Gissin, S. Shalev-Shwartz, and A. Daniely. The implicit bias of depth: How incremental learning drives generalization. In International Conference on Learning Representations, 2020.
[13] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. In Proceedings of the 35th International Conference on Machine Learning, pages 1832-1841, 2018
[14] S. Gunasekar, E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pages 6151-6159, 2017.
[15] Jain, R. Meka, and Dhillon. Guaranteed rank minimization via singular value projection.
In Advances in Neural Information Processing Systems, pages 937-994 2010.
10

---

[16] C. Jin, S. M. Kakade, and P. Netrapalli. Provable efficient online matrix completion via non- convex stochastic gradient descent. Advances Neural Information Processing Systems, pages 4520-4528, 2016.
[17] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from few entries. IEEE Transactions on Information Theory. 56(6):2980-299) 29980, 2010.
[18] Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
[19] Y. Li, T. Ma, and H. Zhang. Algorithmic regularization in over-parametrized matrix sensing and neural networks with quadratic activation. In Conference on Learning Theory, pages 2 47, 2018.
[20] Z. Li, Luo, and K. Lyu. Towards resolving the implicit bias of gradient descent for matrix fac- torization: Greedy low-rank learning. In International Conference on Learning Representations, 2021.
[21] C. Ma, Y. Li. and Y. Chi. Beyond Procrustes: Balancing-free free gradient descent for asymmetric low-rank matrix sensing. arXiv preprint arXiv:2101.05113, 2021.
[22] C. Ma, K. Wang, Y. Chi, and Y. Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pages 3345-33544 2018.
[23] S. Ma, D. Goldfarb, and L. Chen. Fixed point and Bregman iterative methods for matrix rank minimization. Mathematical Programming, 128(1-2):321-2 2011.
[24] E. Moroshko, B. Woodworth, S. Gunasekar, J. D. Lee, N. Srebro, and D. Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. In Advances in Neural Information Processing Systems, pages
2020.
[25] N. Razin and N. Cohen. Implicit regularization deep learning may not be explainable by norms. In Advances in Neural Information Processing Systems, pages 21174-21187, 2020.
[26] B. Recht. A simpler approach matrix completion. Journal of Machine Learning Research, 22:4413-4330 2011.
[27] B. Recht, M. Fazel, and Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471-501, 2010.
(28) O. Roy and M. Vetterli. The effective rank: A measure of effective dimensionality. In 15th European Signal Processing Conference, pages 606-610, 2007.
[29] R. Sun and Z.-Q. Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory, 65(2):742-769, 2016.
[30] K.-C. Toh and S. Yun. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pucific Journal of Optimization, 6:615-640, 2010.
[31] S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht. Low-rank solutions of linear matrix equations via Procrustes flow. In Proceedings of The 33rd International Conference on Machine Learning, pages 964-973, 2016.
[32] T. Vaškevičius, V. Kanade, and P. Rebeschini. Implicit regularization for optimal sparse recovery. In Advances in Neural Information Processing Systems, pages 2968-2979, 2019.
[33] T. Vaškevičius, V. Kanade, and P. Rebeschini. The statistical complexity of cearly-stoppe mirror descent. In Advances in Neural Information Processing Systems, volume 33, pages 253-264, 2020.
[34] K. Q. Weinberger and L. K. Saul. Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision, 70(1):77-90, 2006.

---

[35] B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and
N. Srebro. Kemee and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673, 2020.
[36] F. Wu and P. Rebeschini. A continuous timemueuuuemmeeeeee mirror descent approach to sparse phase retrieval. Advances in Neural Information Processing Systems, pages 20192-20203, 2020.
[37] Wu and P. Rebeschini. Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent. arXiv preprint ar55::210,.03678, 2021.
[38] C. Yun, S. Krishman, and H. Mobahi. A unifying view on implicit bias in training linear neural networks. International Conference on Learning Representations, 2021.
[39] Q. Zheng and Lafferty. Convergence analysis for rectangular matrix completion using Murer-Monteiro factorization and gradient descent. arXiv preprint arXiv: 00000000,, 2016.
[40] Z. Zhou, P. Mertikopoulos, N. Bambos, S. P. Boyd, and P. W. Glynn. On the convergence of mirror descent beyond stochastic convex programming. SIAM Journal on Optimization, 30(1):687-716, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sections 4. and
(C) Did you discuss any potential negative societal impacts your work? [No] Our work
is of theoretical nature and does not present any foresceable societal consequences.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Sections 3
4 [
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen- tal material or hhtts:://// //github.bbbb.t.// com/ wwwuuuiirmmnt
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] We consider the results for single run to be more meaningful compared to the average obtained from multiple runs with error bars, since the estimates of mirror descent and gradient descent being close to each other for any individual run stronger statement than their means and standard deviations being close. This is analogous to X, Y ~ (O, 1). which have the same mean and standard deviation, but each relization of could differ significantly from Y.
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section and Appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vl3AQRH5Ops", "reviewer": "Reviewer_dunA", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths\n- 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. \n- Theorems 3 and 4 present recovery guarantees for the proposed mirror descent algorithm, the first of this kind in the framework of implicit regularization.\n\nWeaknesses\n- 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]. \n- 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.\n\nMinor comments \n\n- 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.\n- Typos: \n - line 105 : numerical\n- line 109 : large\n- line 146: identity\n-line 164: descent\n-line 345: regularization", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "qDuuo2OrrzW", "reviewer": "Reviewer_ZKpj", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n1) 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.\n\n2) 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.\n\nReference:\nEhsan Amid and Manfred K. Warmuth. \"Winnowing with Gradient Descent\". COLT, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "WjkPYw-MVXj", "reviewer": "Reviewer_sWYY", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Originality\n\nThere 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.\n\n# Quality\n\n- 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. \n\n- 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.\n\n# Clarity\n\nOverall, 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:\n- pg 1 line 33 “when then” -> “when the”, pg 3 line 105 “numercal” -> “numerical”, pg 3 line 109 “largeg” -> “large”\n\n# Significance\n\nThis 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "8diaieCu2Y", "reviewer": "Reviewer_oUMM", "summary": "This paper studies the implicit regularization of a particular algorithm, mirror descent, for matrix recovery problems. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.   \n\nI have a few questions that I would like to hear the author's responses. \n\n1. In theorem 1, does the stepsize eta depends on the parameter beta as well? \n\n2. 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?\n\n3. 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? \n\n4. 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A few limitations are discussed in the end. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)