Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting

Thank you for your questions about practicality; we addressed these in our meta-comment. We hope our response clarified the motivations and focus of our work.

In terms of how much additional work would be necessary for our work to become practical, it is hard to make such a prediction, but we discuss one potential avenue here. The current $\text{poly}(r)$ is quite large; we estimate it is $\geq 30$. However, this is primarily bottlenecked by the application of our iterative method in Appendix C, as carried out in Line 903. This step natively has a dependence of $r^7$, but incurs a further dependence on $\text{poly}(1/\gamma)$; right now, our techniques require taking $\gamma = 1/\text{poly}(r)$, where gamma is the fraction of dropped rows in each step. If we could modify our framework to allow for $\gamma = 1/r^{o(1)}$, then we expect the overall $\text{poly}(r)$ to just be the aforementioned $r^7$ (which could also potentially be improved). Prior matrix completion work in the fully random model by [Kelner, Li, Liu, Sidford, Tian ‘23] was indeed able to achieve $\gamma = 1/r^{o(1)}$, so this is a natural direction for future research.

The above would already reduce the $r$ dependence significantly and moreover, it is possible that in practice, we would not need to pay as many extra factors of $r$ as required by the theoretical analysis. For instance, some of the extra factors may not end up being necessary for most instances in practice. We hope that the general framework we propose, of designing reweighting steps with a certificate that guarantees progress, can be a useful paradigm for designing more robust algorithms, and that we can replace the most computationally expensive step in our algorithm, the flow-based solver, with a faster heuristic.

We will add a more thorough discussion of existing literature on matrix completion. However, we emphasize that the paper [1] referenced (and all other iterative matrix completion algorithms in the literature aside from [Cheng, Ge ‘18] which we discuss in depth) only work in the case of fully random matrix completion – in particular they heavily rely on the assumption that the entries are all observed with the same probability. Our algorithm crucially works in a more general semi-random model where the observations are not necessarily i.i.d.

Neither our paper nor [1] has implementations yet (in particular, [1] has no experimental evaluation). In terms of theoretical guarantees, compared to [1], we give improvements in a few notable aspects even in the fully random case. While [1] discusses how their alternating minimization steps are robust, they do not seem to give any guarantees when the observations are noisy – their main theorem is only stated when the observations are exact. Also, their sample complexity and runtime depend polynomially on the condition number of the matrix, whereas our dependence is logarithmic. On the other hand, [1] has better dependence on the rank $r$ and incoherence parameter $\mu$ (both papers are polynomial in these parameters).

We appreciate the feedback about self-containedness of statements, and will take a thorough pass in the revision in an effort to make theorems, etc. more self-contained.

We hope this discussion elevates our paper in your view; thanks for all your detailed feedback.

Thank you for your questions about practicality; we addressed these in our meta-comment. We hope our response clarified the motivations and focus of our work. We agree that to further develop this line of research, it is an important open direction to achieve simpler and more practical instantiations of our framework, which by itself likely requires new ideas.

Re: your question about our adversarial model, our model is the natural extension of the semi-random sparse recovery adversary [Kelner, Li, Liu, Sidford, Tian ‘23] to the matrix completion setting. The only additional generality the [KLLST23] model affords is the ability to mix observations to achieve RIP. This additional generality appears to have little meaning in the matrix completion case, as (1) there is no global “for all directions” type statement such as RIP to assume, and (2) the structure of observations being single entries is inherent to matrix completion, which makes mixing observations lose meaning. Re: manipulating the values of observed entries, note that we do allow for noise in our model (and give recovery guarantees parameterized by the noise size), which is exactly manipulating observed entries.

We would like to note that we believe our paper describes all the implementation details for its various algorithms, as well as full proofs of correctness. We apologize if these details were not sufficiently clear; we will take additional clarification efforts in a revision, and if you have specific parts you would like clarified, please let us know.

We hope this discussion elevates our paper in your view; thank you for your detailed feedback.

Thank you for your reviewing efforts. We appreciate that you found our insights interesting and our exposition clear.

Thank you for your encouraging review and kind comments. We appreciate that you found our paper well-written and its ideas of general interest.

The rank of the output as currently written can be quite large, we estimate the exponent in the $\text{poly}(r)$ as $\geq 30$. The losses stem from the fact that the iterate that is fed into the postprocessing step already has $r’ = \text{poly}(r)$ rank and then there are additional $\text{poly}(r’)$ losses in translating between $\ell_2$ and $\ell_{\infty}$ norms in the postprocessing. We remark that if our final error guarantee were in Frobenius norm instead of max-entry error, then we could simply do a top-$r$ PCA at the end and reduce our output to rank exactly r. We chose to write the error guarantee in terms of max-entry error so that it is compatible with the assumptions on the observation noise (note that doing a top-$r$ PCA does not necessarily preserve the max-entry error). We think the exploration of using Frobenius norm-based potentials within our framework is an exciting direction for follow-up work.

We agree with and appreciate the comments about fine-grained guarantees (e.g., $\ell_2$ vs. $\ell_{\infty}$, and dependencies on the number of revealed entries) being an important future research direction.

The main reason the current error depends on the largest entry of the noise is that the semi-random adversary could choose to reveal all of the entries where the noise is large, which effectively scales up the noise rate. We believe exploring the use of $\ell_2$-based certificates rather than $\ell_{\infty}$ could significantly improve our $r$ dependence (which currently uses several norm conversions, e.g., to make the Frobenius bound in Lemma 7 compatible with the entrywise guarantees of Lemma 13), and is important to better understand in the semi-random model.

The main difficulty with extending to an adaptive adversary is that it is no longer possible to split the samples into independent batches, e.g., we cannot assume that we have fresh randomness in each step of the iterative method. This makes the analysis significantly more challenging because the observations can depend on our current iterate. We mention that variants of sample splitting analyses caused major difficulties in previous works even in the fully random case, as discussed in Section 3 of [Recht, 2011], so there is precedent for this challenge. We will revise our phrasing in Lines 54-62 accordingly to be more clear; thank you for the comment.