Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing

Summary

This paper examines the role of gradient descent in inducing implicit regularization for tensor optimization, within the lifted matrix sensing framework. The authors show that with sufficiently small initialization, gradient descent applied to the lifted problem results in rank-1 tensors and critical points with escape directions. These findings show the significance of tensor parameterization for matrix sensing, combined with first-order methods, in achieving global optimality.

Strengths

- Seems well-written overall. - Has some useful insights, like "our findings indicate that when applying GD to the tensor optimization problem (3) an implicit bias can be detected with sufficiently small initialization points." - And also they show that, "...when initialized at a symmetric tensor, the entire GD trajectory remains symmetric, completing the requirements", which is interesting.

Weaknesses

- Needs more convincing or discussion that the theory can be useful for practical applications. I find the theory interesting, but unsure of the practicality. Of course, it's nice that they give an experiment on a two-layer neural network with quadratic activations, but I'm not sure quadratic activations have been used all that much practically. Also, the last "layer" of the neural network just sums the outputs of the "hidden" layer, which is not as general. I believe this is the biggest weakness of the paper. - Hyperparameters for the different optimizations algorithms used are not found. This makes it hard to believe that the authors made a good effort to optimize the unlifted problem via perhaps a hyperparameter search. - For Section 6.2, the experiment is under "low-sample" conditions, but this needs to be quantified and perhaps an experiment where there are "high-sample" (or at least non-"low-sample") conditions may be of interest just for completeness. - A minor point: While I did look over the proofs in the appendix, the number of pages of proof in the appendix is a bit long at 21 pages. It might help the paper to condense the proofs.

Questions

- Line 27-29: What are the practical applications of two-layer neural networks with quadratic activations? - Line 137: I'm assuming FOP stands for "first-order point", and this acronym should be explicitly clarified. - Line 232: "fist" to "first" - Line 278: "that wether" to "whether"

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

- The authors do not provide an explicit discussion of the limitations.

Summary

Studies the implicit regularization of gradient descent for a certain tensor optimization problem, obtained through the “lifted” matrix sensing framework. Lifting matrix sensing problems is a technique for transforming the original (non-convex) landscape into a new (still non-convex) landscape with favorable properties. In particular, spurious local minima are converted into strict saddle points. The current paper establishes that, under near-zero initialization, gradient descent over the lifted matrix sensing problem leads to approximate rank one tensors until a certain time step. Furthermore, it shows that one can extract a first-order point for the original matrix sensing problem from approximately rank one first-order points of the lifted problem. Along the way, derives a lifting framework over symmetric tensors for matrix sensing problems with a ground truth matrix of arbitrary rank. Experiments corroborate the theory by demonstrating that optimizing the lifted problem may lead to better reconstruction than optimizing the original problem.

Strengths

1. Establishes a novel implicit regularization of gradient descent for tensor optimization problems. In particular, as far as I am aware, this work is the first to show for the specific problem of (5) that gradient descent will lead to a trajectory that is approximately rank one until a certain time step. 2. Existing analyses of implicit regularization in tensor problems have focused on gradient flow (gradient descent with an infinitesimally small step size), while the current work supports the more realistic gradient descent with a finite step size. 3. The technical tools used, e.g. the v-eigenvalue definition, may be of use for future work on the implicit regularization in tensor problems. 4. The paper reads relatively well. Ample explanations and high-level intuitions are provided regarding the theoretical analysis.

Weaknesses

1. There seem to be gaps in the theory that are not adequately addressed (or mentioned explicitly). Specifically: - Theorem 1 applies for some k < 1. In principle, at least from the theorem statement, it seems that k can be close to one, in which case the tensor is not really approximately rank one. For Theorem 2, k needs to be upper bounded by a quantity depending on the target matrix. The matter of when we can expect this to hold is not treated. - Theorem 1 and 2 establish that the tensor will be approximately rank one until some time step, and that first-order points of tensors that are approximately rank one, but do not correspond to a global minimum, have an escape direction. Yet, it is not guaranteed that we will reach a critical point while the tensor is still approximately rank one. - In Theorem 1, it is not specified how small the initialization scale needs to be. Does the theory suggest a scale of practical size and not exponentially small in the problem parameters? - In Theorem 2, is the rank one escape direction in the same direction of \hat{x}? Otherwise the rank could increase upon escaping, in which case the fact that we can map rank one tensors to first-order points of the original problem may be of less use. Obtaining full characterizations for the dynamics of gradient descent in non-convex problems is challenging, and it is not out of the ordinary to have gaps in the theory. Yet, I firmly believe that such gaps should be explicitly discussed and perhaps reconciled via experiments (e.g. showing that indeed the tensor stays approximately rank one until convergence). &nbsp; 2. A large part of the motivation behind looking at the lifted problem (5) and analyzing the implicit regularization of gradient descent for it, is the possibility of achieving better reconstruction in matrix sensing problems. I find the empirical evidence provided unsatisfactory in establishing the importance of the lifted formulation. The matrix sensing experiments cover only a very specific perturbed matrix completion problem and matrix sensing problem with rank one measurements. Showing that using the lifted problem (5) is viable in more generic cases or real-world datasets can greatly boost the significance and interest of the results in my opinion. Furthermore, for the lifting technique to be practical, $l$ cannot be too large as the size of the tensor grows exponentially with it. It is not clear whether this is limiting for typical matrix sensing problems or not from the current evaluations. &nbsp; 3. Empirical support for Theorem 1, which establishes that the tensor will be approximately rank one until a certain time step, is lacking. The experiments only examine the resulting performance after extracting a rank one tensor from the last gradient descent iterate. However, they do not show whether the tensor is approximately rank one as the theory suggests, or it has grown in rank (i.e. the norm of the residual after reducing the rank one component is non-negligible). If it is the former, it strengthens the viability of the theory, while if the latter holds, then it is unclear whether the theory indeed explains the observed empirical phenomenon. I recommend reporting, e.g., the norm of the tensor after reducing from it the extracted rank one component or some other measure of how close to rank one the tensor is. Additional (more minor) comments: - In the empirical evaluation, success rate is too crude of a measure in my opinion, as it is possible that the difference in reconstruction error is not large while the difference in success rate is. I believe comparing (normalized) reconstruction errors will allow for a better comparison of the performance of the lifted and unlifted techniques. - I found the inner product notation (without any subindices) to be confusing. One would expect the output to be a scalar. - Escape direction from a critical point is not formally defined. - In Theorem 1, it is not specified what t_T stands for. - Experiments are for a custom version of gradient descent that does not quite align with the theory. I would recommend clarifying briefly in words (even if in an appendix) what are the modifications it introduces and why, rather than just referring to pseudo-code. - In line 124 it is claimed that the objective considered in this paper is more general than those studied in related works. However, it seems to me that the setting is simply different/incomparable rather than more general. For example, the analysis of [1] considers any differentiable (locally smooth) loss. [1] Razin, Noam, Asaf Maman, and Nadav Cohen. "Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks." International Conference on Machine Learning. PMLR, 2022.

Questions

1. In the numerical experiments, is there a reason for comparing success rates as opposed to normalized reconstruction errors? How was the threshold of 0.05 chosen? 2. Why not parameterize the tensor as a symmetric rank one matrix from the get go, as opposed to optimizing over the full tensor. The former is more efficient in terms of the number of parameters and guarantees that the trajectory stays rank one. Is it a matter of optimization, i.e. that a symmetric rank one parameterization may converge to spurious local minima/non-strict saddles?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

As detailed in the review above, I believe there is room for improvement in terms of explicitly addressing the limitations and gaps of the current theory.

Summary

This paper presents a new GD algorithm that is suitable for the problem of matrix sensing. Within this algorithm a 1-rank approximation of the corresponding tensor is made. A distinctive feature of this algorithm is that some points of local minima are turned into saddle points, which improves the convergence to the global optimum.

Strengths

- A new modification of the gradient descent method was invented and implemented, which gives an advantage in certain problems - This article shows the importance and application of concepts from tensor algebra to machine learning. - All the algorithms are described in detail in Appendix - All the proofs are given in Appendix, and all the necessary terms are neatly given in the text of the article and Appendix.

Weaknesses

- The article is overloaded with technical details and terms, many of which are only defined in appendix. This makes it difficult to understand the main idea of the article. Perhaps this style would be more suitable for people specializing in tensor algebra and matrix sensing problems. - Only few numerical experiments have demonstrated a strong advantage of the method. - Minor: line 156 possible typo, must be $2d$ instead of $d$

Questions

Have you tried testing the algorithm on more complex real-world problems?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

The theorems mention constraints on the operator $\mathcal A$, which appears in the formulation of the matrix sensing problem. Thus, the developed method is restricted to problems that can be reduced to the matrix sensing conception and those for which certain conditions are imposed. It seems difficult to say in advance (without numerical experiments) whether the algorithm will work on this particular problem.

Summary

Gradient descent induces implicit regularization for tensor optimization. Specifically, it has a bias towards approximately rank-1 solution in the lifted matrix sensing framework. In Theorem 1, the authors show that the ratio between the second v-eigenvalue and the first v-eigenvalue exponentially decays to 0 in terms of the number of iterations. In theorem 2, the authors show that any first-order solution of the lifted problem that is far away from the ground truth is a saddle point.

Strengths

The authors carried out complicated proof and show non-trivial results. The generalization of lifted problems from r=1 to general r is very interesting. Given that this is very theoretical, the presentation is good enough to capture the main proof strategy.

Weaknesses

There is still some confusion and I hope the authors can better explain them in the paper. 1) In Theorem 2, the authors show that if the approximation error is large, then GD can always find a direction to improve. However, it is not clear whether the lower bound is actually meaningful. For example, if $M^*$ is the identity matrix in the first $r$ dimension and $\hat{X}\hat{X}^T$ is the identity matrix in the next $r$ dimension. Then I would think $\hat{X}\hat{X}^T$ is not a good estimate for $M^*$ but the approximation error is 2r may not satisfy the lower bound $\frac{L_s}{\alpha_s}r $. Since the ratio $\frac{L_s}{\alpha_s}$ relates to the RIP condition and the authors have discussed how overparameterization can relax RIP constraints, I encourage authors to provide more discussions around the lower bound and possible connection to the RIP condition. 2) On line 262, the authors mentioned that "since increasing $l$ will decrease ratio $\lambda_2^v(w_t)/\lambda_1^v(w_t)$ provided that $\sigma_1(U)\geq 1$. I am not sure how strict this condition is and my guess is some simple tricks may make this condition always hold. 3) From Theorem 1, it looks like the rank 1 regularization always holds regardless of the value of $l$, and lifting may not be necessary. Theorem 2 requires a large and odd value of $l$ which is not clear to me why this condition is needed. Some explanation would be nice. 4) When $w_t$ is approximately rank-1, what does it implies about the rank of original estimate $\hat{X}$ for general r? It is not very clear to me.

Questions

line 232 typo: "fist" to "first"

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The main results are theoretical results.