Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting
Authors: Jonathan Kelner
Jerry Li
Allen Liu
Aaron Sidford
Kevin Tian
Venue: NeurIPS 2024 poster (2024)
Keywords: matrix completion
semi-random model
flow solver
short-flat decomposition
adaptive reweighting
Primary area: learning_theory
TL;DR: We give the first nearly-linear time algorithm for solving semi-random matrix completion to high accuracy and with noisy observations.

Abstract: We consider the well-studied problem of completing a rank-$r$, $\mu$-incoherent matrix $\mathbf{M} \in \mathbb{R}^{d \times d}$ from incomplete observations. We focus on this problem in the semi-random setting where each entry is independently revealed with probability at least $p = \frac{\textup{poly}(r, \mu, \log d)}{d}$. 
Whereas multiple nearly-linear time algorithms have been established in the more specialized fully-random setting where each entry is revealed with probablity exactly $p$, the only known nearly-linear time algorithm in the semi-random setting is due to [CG18], whose sample complexity has a polynomial dependence on the inverse accuracy and condition number and thus cannot achieve high-accuracy recovery. 
Our main result is the first high-accuracy nearly-linear time algorithm for solving semi-random matrix completion, and an extension to the noisy observation setting.
Our result builds upon the recent short-flat decomposition framework of [KLLST23a, KLLST23b] and leverages fast algorithms for flow problems on graphs to solve adaptive reweighting subproblems efficiently.

Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting
Jonathan A. Kelner*
Jerry Lit
Allen Liu
Aaron Sidford
Kevin Tian"
Abstract
We consider the well-studied problem of completing a rank-r, ju-incoherent matrix M Rdxd from incomplete observations. We focus on this problem in the semi- random setting where each entry is independently revealed with probability at least p poly(r.p,logd)) Whereas multiple nearly-lineat time algorithms have been established in the more specialized fully-randoo setting where each entry is revealed with probablity exactly p. the only known ncarly-lineat time algorithm in the semi-random setting is due to [17]. whose sample complexity has a polynomial dependence the inverse accuracy and condition number and thus cannot achieve high-accuracy recovery. Our main result the first high-accuracy nearly-linent linerr time algorithm for solving semi-random matrix completion, and extension to the noisy observation setting. Our result builds upon the recent short-flat decomposition framework of [42, 43] and leverages fast algorithms for flow problems on graphs to solve adaptive reweighting subproblems efficiently.
Introduction
How can ensure learning algorithms do not overfit generative assumptions their input data? Since worst-case statistical inference problems are often intractable (i.e., without distributional assumptions), develop efficient algorithms, we often introduce a generative model as a proxy for average-case, real-world behavior. However, if these algorithms are to be useful practically, we must ensure they do not depend too strongly on any artificial properties of the generative model. Ideally, they should require only what is statistically and algorithmically necessary, and no more.
In this paper, we consider this question in the context of matrix completion, one of the most fundamental and well-studied linear inverse problems. In matrix completion, the goal is to recover symmetric rank-r matrix M E Raxd where < d, given small (typically sublinear) number of entries revealed independently and at random. In seminal line of work [13, 11, 12, 61], it was shown that under natural structural assumptions on M. one can fully recover M given dr randomly revealed entries in polynomial time, via semidefinite programming (SDP). Subsequently, there has been extensive work attempting to improve upon statistical and computational guarantees for matrix completion. In an oversimplification of the literature (see Section 1.3 for more detailed and nuanced discussion), this has resulted in two categories of matrix completion algorithms.
SDP-based algorithms achieve the nearly-optimal sample complexity, but are based on solving SDPs, which requires time ((d8.5) even with state of the art solvers [39, 34).
First-order iterative methods require a slightly higher sample complexity, namely, they require pd revealed entries for observation probability lopo z. However,
MIT, kelnerOmit... edu.
1 Microsoff Research, verrl@microsoft
1 MIT, cliu568@mit edu.
$ Stanford University, sidford@@ttafordd.co
University of Texas at Austin, kj titinnecs. utexas. edu.
Our results also hold for asymmetrie, rectangular matrices. See the discussion the end of Appendix A.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

they use faster optimization primitives and can be implemented in time Ö(m poly(r, log d)). Throughout the introduction, we will somewhat informally refer to such algorithms as fast.'
Because matrix completion is particularly interesting study when the target rank is substantially smaller than the dimension d (as appear that fast algorithms are able to nearly match the statistical guarantees of the SDP-based methods, while offering substantially lower runtimes. In light of this, naïvely one might expect that first-order iterative methods ought to be always preferred over the alternative. However, has been noted that in many real-world situations, these first-order iterative methods actually fail to perform reliably, see e.g. [66. 70, 26, 68]. An oft-cited reason for this failure exactly the tendency for these sorts of methods to demonstrate the type of generative overfitting described above [66, 70, 4]. Indeed, in real-world applications, the distribution of revealed entries is usually very far from uniformly random [4], which can cause iterative methods that rely too heavily on this assumption to fail dramatically. This begs the following natural question:
cotmaaatonnthoorticallyy we require Z dr observations), it may
Can we design fast algorithmss for matrix completion that are robust to generative overfitting?
In light of this discussion, we consider a semi-random variant of matrix completion, introduced in [17]. Recall that in standard matrix completion, we assume every entry (i.j) E [d] x [d] is revealed independently with probability p. In the p-semi-random model (Definition 2), we only know p E (0, 1) such that every entry is revealed independently with an unknown probability P.j 2 p. Given that real-world data is unlikely to be generated exactly uniformly, it is reasonable to believe that the semi-random model is a more faithful model of matrix completion in practice.
In this model, the algorithm is given strictly more information than in the standard (uniform) matrix completion setup. This is because the semi-random model is equivalent to the setting where we are first given a standard matrix completion instance, and then additional (but potentially adversarially chosen) entries are revealed." 8 It is straightforward to show that the SDP-based approaches generalize to succeed the semi-random setting, since the adversary's revealed entries just translate to additional constraints in the convex program satisfied by the ground truth. However, as demonstrated in [17], Appendix A, previously known first-order iterative methods can fail to converge in this semi-random setting. We view this strong theoretical evidence that such algorithms exhibit large amounts of generative overfitting. We can now more concretely rephrase the previous question:
Can we design fast algorithms for semi-random matrix completion?
This paper focuses on the theoretical complexity of the problem; the relationship of the techniques in this work to efficient matrix completion in practice is an interesting direction for future research. Precisely, we seek to design an algorithm for semi-random matrix completion which works for the same (or qualitatively similar) p as in the standard setting, and which runs in time Ö(m poly(r, log d))? ? Here m denotes the total number of revealed entries, a proxy for the input size; note that in the semi-random setting. it could be that m >> pd?.
The main result of [17] is efficient algorithm for semi-random matrix completion, albeit with some important caveats, as we discuss shortly. Roughly speaking, for e E (0, 1). [17] gave an algorithm which, given observations of rank-r M with condition number n. from the p-semi- ranemi- model for p 1 (pooy((r, K. 4)), outputs M' so that ||M' M S ||M with high probability. Moreover, it rums in pearly-lineat time Ö(m- poly(r, })), where m is the number of revealed entries. While this is a promising first step towards matrix completion in the semi-random model, it leaves several important questions unanswered.
High-accuracy recovery. Both the sample complexity and runtime of the algorithm in [17] depend polynomially on e -1, In particular, the algorithm cannot recover the matrix M to -1= poly (d) levels of precision in nearly-linear time. Thus, even in the standard setting where we assume that the bit complexity of the entries of M are polynomially bounded, [17] cannot achieve exact
7 'eere, and throughout the paper, we use the notation Õ() = O(f 00) f) and similarly define O.
* "A clarified in Definition 2, it is important in this equivalence that the additionally revealed entries not adaptively chosen, i.c., do not depend on which random entries were observed. This manifests our analysis because an adaptive adversary causes significant difficulties with independent sample splitting (see Lemma 2). There is precedent from the literature on fully-random matrix completion that the inability to sample split causes analysis issues (see, e.g., Section 3 of [61]); extending an adaptive adversary is challenging open direction.

---

recovery of the matrix in nearly- linear time. Unfortunately, this dependence seems inherent to the techniques therein (see the discussion in Section 1.2).
Condition number dependence. Another important downside of the [17] algorithm's 's guarantee is its polynomial dependences on in both the sample complexity and runtime. No dependence anformation-thcoretiaaal theoretically, or by the SDP-based methods. This aspect also seems somewhat inherent the non-convex iterative method used in [17].
on k is required information-
Noise tolerance. Finally, the guarantees in [17] require that M is exactly low-rank, i.e. it does not generalize handle noise in observations. In practice, this is unlikely, and guarantees should ideally hold even when we only assume that the observed M is close to low-rank.
1.1 Our results
Our main result is a new fast algorithm for semi-random matrix completion that addresses all three of the aforementioned issues. Specifically, we show the following main result.
Theorem 1 (informal, see Theorem 2). Let M E Rdxd be symmetric, rank-r, ju-incoherent
matrix, let symmetric N E Raxd satisfy ||N S A, and let M M + N. Let E (0, 1). There is an algorithm that takes observations from M in the p-semi-random model for p d' where Q = poly(r, pr, log(())) and outputs M as a rank- Q factorization such that with high probability,
AM-M S (A (|M))
The algorithum runs in nearly-linear time O(mQ) where is the number of revealed entries.
Here, Il-llcc refers to the elementwise foo norm a matrix, and ||:ll= to the Frobenius norm. We pause to comment on Theorem 2. First, in the noiseless setting, i.e., when A = 0. our algorithm has polylogarithmic dependence on e- and thus achieves high-accuracy recovery in nearly-linear time. In particular, as long as the bit complexity of the underlying matrix is polynomially bounded, we nearly-linear time. Moreover, our rate has no dependence on the condition number k. In both of these aspects, our result qualitatively improves upon [17], while retaining
achieve exact recovery
nearly-linest runtime and (d poly(r)) sample complexity. We also remark that the incoherence assumption in Theorem (or a less standard variant thereof), which formally defined in Definition 1, is used in all low-rank matrix completion algorithms are aware of, as the problem is intractable without subspace regularity assumptions (see, e.g., discussion in [43]).
Finally, we observe that our guarantee applies to the noisy setting, i.e., A > 0. To our knowledge, this is the first such guarantce in the literature for semi-random matrix completion, even for SDP-based methods. We achieve guarantees in terms of the fx norm of the noise matrix N; moreover, the overhead is polynomial of only r log( ),, a preferable guarantee to the poly(d) overheads known to be achievable in the standard, fully random setting by semidefinite programming [11].
We do note that in the standard matrix completion setting, error guarantees are typically phrased in terms of the Frobenius norm of the noise N [11, 43]. However, in the semi-random setting, some measure of the "element-wii wisee" noise level is unavoidable, because the semi-random noise could be chosen only reveal unusually large entries of the noise matrix. We believe it is an interesting open question whether or not one can achieve somewhat more global measures of error such as the Frobenius norm of large entries in the revealed noise, which are more comparable to guarantees recently attained for semi-random sparse linear regression [42].
1.2 Our techniques
We achieve these results via a fundamentally different approach than the prior work of [17], detailed in Section 2. At (very) high level, [17] relies on finding a single reweighting of the revealed entries of M that is good in a global sense. This roughly corresponds to finding a mask of the revealed entries, so that the masked matrix is guaranteed to be a good spectral approximation of the ground truth matrix. Given such a mask, [17] then shows that non-convex optimization method will recover the true matrix, with high probability. While this is very natural approach, this also directly results in poly(?) dependence in the runtime and sample complexity of the algorithm. This because the quality of the spectral approximation directly goes into the final accuracy of their overall algorithm; ultimately, they need (1 + e) >multiplicative spectral approximation to the ground truth. However, known techniques for finding such a high-quality spectral approximation require poly(?) dependence in both sample complexity and runtime.
3

---

We instead devise an iterative method that is guaranteed to make progress, assuming that the iterate satisfies a local progress criterion. We then find a local reweighting of the matrix which allows us to find a step which satisfies this criterion. While this local progress criterion is much more involved to state, and this reweighting must now be done every iteration (rather than just once at the beginning of the algorithm), this framework has an important advantage over the global criterion used previously. Critically, now each step of our method need only seek a reweighting which achieves a constant factor of relative progress to the target matrix. Thus, rather than needing a (1 + +e e)multiplicative approximation at every step, we only need a constant multiplicative approximation to make progress. This is the main insight which allows to achieve polylogarithmic rates in :.
Our algorithm builds upon the short-flat decomposition-boe based approach to designing iterative methods for linear inverse problems introduced in [42], and specialized in [43] to matrix completion in the standard setting. However, there are significant technical challenges in adapting this framework to semi-random models. At high level, the matrix completion problem is not well-conditioned,
crucial step in the [43] algorithm is dropping rows and columns of a difference matrix (between an iterate and the target) which are estimated as too large. Random observations (held out via sample splitting) are then used in matrix concentration inequalities to estimate the difference matrix on the remaining indices, and dropped indices are later recovered.
Unfortunately, all of these steps crucially rely on independent sampling and hence break in the presence of comi-random noise. We instead take a fresh look at what certificates of progress are possible in the semi-random setting. Our key technical contribution, Algorithm 2, is a subroutine which makes bicriteria progress: either finds an adaptive reweighting which accurately estimates the difference on a large submatrix after denoising, or certifies that few rows and columns are responsible for much of the difference and hence can be dropped. To achieve our nearly-linea runtime, we crucially exploit graphical structure of feasible reweightings present in the randomly-reveate entries, and use flow-based optimization algorithms to solve our reweighting subproblem.
1.3 Related work
Here, we review related work on matrix completion and semi-random models. These lines of research are vast and we foeus on the research most relevant our setting. For a more comprehensive review, we refer the interested reader to surveys on these topics, e.g., [41, 60, 59, 63].
Matrix completion. Matrix completion was first introduced in [62] in the context of collaborative filtering, e-g., for the Netflix Prize [6]. Since then, it has found applications in various areas, such as signal processing [46, 64, 57], social network analysis [47], causal inference [4], and most recently, Al aligmment [1]. In a seminal line of work, [13, 11, 61. 12, 16] demonstrated that SDPs based on nuclear norm minimization can solve matrix completion with sublinear sample complexity, and in polynomial time. Another line of work focuses on first-order iterative methods for matrix completion, see e.g., [44, 31, 32, 33, 36, 74, 67, 18, 72, 30]. These works demonstrate that optimization frameworks, such as alternating minimization, can provably and efficiently recover the true matrix. Finally, yet another line of work seeks to understand the non-convex landscape of descent- methods for matrix completion [65, 21, 28, 40, 73, 40, 73, 71]. In terms of theoretical runtimes, the state of the art (dd is given in [43]. While some of the aforementioned papers have implementations, comprehensively evaluating the practical performance of all of these methods is interesting direction for future work. As noted in [17], none of these fast methods are known to succeed in the presence of semi-random noise.
Semi-random models. Semi-random models were first introduced in a pair of seminal papers [9, 24), in part as a means to test whether learning algorithms which succeed under random models generalize to more realistic generative modeling assumptions. Most early work semi-random models focused on understanding semi-random variants of various constraint satisfaction problems, see e.g. [25, 24, 45, 15, 48. 50]. More recently, they have also been studied in the context of learning theory, in the context of clustering problems [23, 53, 49, 14, 29, 51, 52, 55], sparse and overcomplete linear regression [37, 42], planted clique [54, 10], and more [27, 8].
Of particular interest to us is the recent line of work on developing fast learning algorithms in semi-random models [17, 42, 43, 27, 8]. The closest and most direct comparison to our work is the aforementioned [17], which we quantitatively improve upon in a number of ways. It is worth noting that the specific poly(r) R 6 dependence in the sample complexity of [17] is lower than in Theorem 1. We view our result as a promising proof-of-concept of the tractability of semi-random

---

matrix completion via fast algorithms: both our dependence and the dependence of [17] are somewhat large at the moment, limiting immediate practical deployment, but we believe that it is an interest direction for future research to tighten dependencies on problem parameters and seek more practical algorithms.
2 Technical overview
At a high level, our algorithm follows the paradigm in [42] for designing fast iterative algorithms that are robust to semi-random models, which used this framework for sparse linear regression. Broadly, the approach is to first find deterministic conditions which guarantee that step of the iterative method, which descends along a reweighted direction based on semi-random observations, makes progress. We then develop a custom nearly-linear time algorithm for computing such a reweighting. using optimization tools specialized to the regularity of graph-structured polytopes.
Short-flat decompositions for progress. We first discuss the verifiable conditions we impose to certify progress of our iterative method. Throughout this section, we let our current iterate be M e Rd and let the ground truth be M E Rdxdd assume both matrices have rank most r, and focus on the noiseless setting N = Odxd for simplicity. We also assume for normalization purposes
that | | 1, and our goal is to take a step M' <- M + so that
1
IIM D) M S 2
Our conditions are inspired by the approach in [43], which gives improved iterative algorithms for standard matrix completion (without remi-randon noise). Let p be the minimum observation probability, let f2 be the set of observed entries from M and let Q be the set of truly random observations, i.e., when each entry is revealed with probability exactly p (we can find a coupling so that f C f always). Inspired by a similar framework in the sparse recovery setting [42], the key certificate for guaranteeing progress of the form (1) in [43] that of short-flat decomposition. We say candidate step D has short-flat decomposition if we
write D S + F where 1 for small constant c: here we think of S as the "short" part and F as the "flat" part of the decomposition. If we further ensure that enough signal is captured, i.e., (D.M* - M) > 1 - c. then [42, 43] give a short argument based on Hölder's incquality that a step in D, combined with a low-rank projection for denoising, will imply (1).
|| and ||F]lop I cr-
Thus, it suffices to find a matrix that has these properties; for intuition, we would ideally like to take D = S = M M and F = Oaxd, which would complete the matrix in one shot. Naturally, however, we are limited by the fact that D should be supported on the observations Ω2 as otherwise we cannot make any guarantees on (D, M M). Naively, one would hope to simply take the empirical observations
= [M - M (which zeroes entries outside f?*), an unbiased estimator of M - M. and appeal to matrix concentration arguments to show existence of a short-flat decomposition. Unfortunately, this is not the case, as entries, rows, columns of M -M which are too large can arbitrarily hinder matrix concentration bounds, and [43] gives simple examples showing this dependence on the imbalance is unavoidable for uniform reweightings.
However, [43] made the important insight that when matrix concentration fails, it must be that - M-M
is overly concentrated on few heavy rows and columns, and hence dropping a few rows and columns significantly reduces ||M |I These rows and columns can later be recovered using the low-rank assumption, once enough progress has been made. The algorithm in [43] then works by repeatedly estimating heavy rows and columns, explicitly dropping them to form a set S S [d] of balanced indices, and then taking the step D = 1 [M- [e-n((xx.)) This necessity of dropping certain poorly-behave indices is crucial difference between the matrix completion setting and simpler stronger global regularity features such as the restricted isometry property (RIP).
inverse problems such as sparse linear regression [42], which possess
Certifying progress in semi-random models. In the semi-random matrix completion problem, we need several modifications the strategies of [42, 43], to handle the interplay between estimating heavy indices and making certifiable progress. Firstly, we cannot accurately estimate the &g norm of rows and columns of the true difference matrix M M* from observations, because the semi-random adversary can drastically distort our estimates. However, we show in Algorithm I that we can use the to norm of observed entries proxy for heaviness." 9 Specifically, after dropping rows and columns
This norm distortion is the main source of poly(r) losses in our guarantees compared to the [43] algorithm.
5

---

with the most observed large entries, we argue that all remaining rows and columns are well-balanced except on few sparse errors, which we exclude from our potential.
Next, even if appropriate rows and columns were dropped, we cannot use the empirical observations to construct our step, as semi-random observations are no longer unbiased and the fully-random indices Ω are unknown. Instead, we use S2" existentially to set up a convex program over reweightings w E RR, to search for a candidate step D := Einyen Wiy[M [M My Roughly, our convex program aims to find satisfying the following constraints (see Lemma 7 for a formal statement).
1. For all i E [d]. EeE((((()) wiy [M- M = =(5))
2. There exists F, E RRdxd with D = S + F. ||||: S 1, and |Fllop = Ogr 1).
3. For a sufficiently small constant c, (D, M M Eusen Wiy M M 21-1
Item 1 serves to ensure our step D is sufficiently spread out amongst its rows and columns, which serves two roles: it bounds how much progress is lost when excluding indices, and enforces crucial problem regularity for our reweighting optimization algorithm. On the other hand, Items 2 and 3 are the standard criteria for making iterative progress through the short-flat framework of [42, 43J. It is straightforward to see that the ideal candidate
p M M (( we mentioned earlier is feasible for these constraints, and we show in Lemma that finding any satisfying reweighting is enough to ensure progress (with some mild technical changes). It remains to discuss how to find a candidate D to ensure rapid convergence through the progress bound (1).
Flow-based adaptive reweighting. A key technical contribution of this work is a nearly-linear time algorithm finding a reweighting D(w)= == E(.)e W%y [M M that meets our progress criteria. Due to our focus on fast algorithms, we require this step to run in [[ poly(r)) time. Our strategy is to form a joint objective over w obeying Item I, and ||||| S 1, of the form
Fpog-an Aat (w, S) == - (D(w,, M M*) + C smax(D(w)) S). S).
Here, the parameter C' is used trade off the progress objective (D(w), M M*) (giving Item 3) and the flatness objective smax smax(D(w) (D(w) - S) (giving Item 2), where smax = log Tr (M) is a smooth upproximation to the operator norm. That is, letting Z == W S be the product space between w E RD satisfying Item and short matrices S E Raxd we show that finding (w, (W E Z with low suboptinality error in Fpmg-faa Ala is enough to make progress through Lemma
We optimize (2) by carefully applying a Frank- method due to [35]. While naive Frank- analysis requires global smoothness of the objective, this provably does not hold for our 1 prog--fat (at least, with a smoothness bound of ~ poly(r) required for nearly- time algorithms). However, we leverage that the analysis in [35] shows that weaker regularity conditions, namely bounds on the curvature constant, suffice for efficient convergence of an iterative method. Specifically, we use the structure of our constraint set W show that Foro--aat smooth in a restricted set of directions within W which implies suitable bounds on the curvature constant (see, e.g., Lemma 18) to remove a d factor from the naive smoothness bound. We also observe that W is exactly a rescaling of a bipartite matching polytope, so that we can use flow-hased graph algorithms, e.g., the approximate weighted matching algorithm of [22], to efficiently implement the linear optimization oracles over W required by Frank-Wolft methods. We then use techniques from numerical linear algebra and polynomial approximation to implement linear optimization oracles over S, completing optimization subroutine for finding adaptive reweightings.
One other technical hurdle arises implementing this framework for finding a reweighting: the existence of wt satisfying Items 1, 2, and 3 relies on having good estimate of the current distance ||M - MM- after excluding certain rows and columns. In general, we can only upper bound this quantity, but show that we can also of such a w* In this latter case, we show that must have been the case that a few rows and columns were significantly heavier than the rest, and we can run Algorithm to drop them. Our overall iterative method, Algorithm 2, makes bicriteria progress and either terminates with a "drop" step (when no feasible w" exists), or a "descent" step (when find good solution to (2)).
optimization subroutine for (2) to certify non-existence
Recovering dropped rows and columns. Finally, we briefly discuss how to post-process an estimate M that is close to M' on a large submatrix to recover dropped rows and columns. The high-level outline is similar to [43], where we aim to find "verified" set of rows and columns that

---

we completed well, and use the low-rank assumption to obtain accurate estimates to the remainder via regression. However, there are several key differences. The main difference is that in the semi-random model, we need to track errors in our estimate entrywise instead of in f2, since a semi-randomness could drastically distort the empirical l error by adversarially revealing entries. We rely on a structural result using tools from the theory on volumetric spanners [5, 7] (see Lemma 27) showing that large entrywise errors must be localized to a small submatrix. At this point, we set up loo regression problems to identify verified indices, solvable in nearly-linear time using recent advances in linear programming [69]. Importantly, the overhead in the error guarantee of this recovery step is only (poly(r)) (see Proposition 3), allowing us to achieve a recovery guarantee in Theorem that avoids poly(d) overheads in the presence of noise.
3 Preliminaries
We now formally set up preliminaries required for analyzing solution the semi-random matrix completion problem. First, we recall the standard definition of incoherence for subspaces.
Definition (Incoherence). We say dimension-r subspace V S Rd is p-incoherent if [IIvel S /Td for all E [d] (where is the ith standard basis vector), and M Rm is p-incoherent M has y-incoherent row and column spans.
We will work with symmetric matrices. We denote the space of d x d symmetric matrices by Saxd In Appendix A, we give a reduction from general matrices to symmetric matrices showing that suffices to work in the symmetric case, up constant factor loss in parameters. Next, we define the semi-random observation model.
Definition 2 (Semi-random model). For M E gdxd, we use (M) to denote oracle access to M in the p-semi-random model, where we call O% a p-semi-random oracle. Specifically, in one call to 0% with input M. for unknown observation probabilities {p.heldxxaa x[d] S [p, 1]. each i [d] x [d] is independently included in a set I with probability P.. The oracle Oµ then returns the set {[M]ee When an algorithm requires the ability to query (M) for various values of p (specified in the algorithm description), we list the input as (%.1((M)
Note that (M) and 1 (M) (M) inherit their definitions in [43] when p. p, for a fixed p E [0. 1]. p Now we can formally define the semi semi-random matrix completion problem we study.
Definition 3 (Semi-random matrix completion). In the semi-random matrix completion problem, R20. p E [0, 1], d E N, and r* [d], there is an unknown rank-r* ju-incoherent matrix M E Gáxd, For some N E gdxd satisfying [|N] S A, and M M* N, we receive the outpul of one call to (M), and wish to output an approximation to M
parameterized by μ,
Remark In Appendix A, we give a sample-splitting reduction which lets us use (M) to simulate & independent accesses to O% (M) for smaller values q S p.
We will also need a few technical definitions to explain the main ingredients in our algorithm.
Entropy and softmax. We let dxx := (M sixd Tr(M) = 1} denote the d x d spectraplex. We let H A dxd + R denote von Neumann (matrix) entropy, i.e., H (M) = (M, log M), and let H" ddxd + denote its convex conjugate, which we call matrix softmax, defined by H HMMM): == log Tr exp M. More generally, for 17 > O, we define
{
H (M) = n log Trexp
(3)
We recall the following standard facts about H;;
Fact 1 (158)). The function H defined in (3) satisfies the following for all 1) > O.
1. For all M E Sdxd, A1 & (M) < A (M) + log d, where > (M) is the maximum eigenvalue of M.
2. For all M E gaxd, (M)
exp M)
Trexp( M)
3. H. is swice-differene difceddifeerentibble and smoooh with respect the norm Il-log
7

---

To use H; to enforce operator norm bounds, we define the signed lift of matrix M E gaxd by
slift(M): ==
M
Odxd
E S2dx2d
Oaxd
-M)
Note that slift signs and lifts M that its maximum eigenvalue its operator norm.
Comparing matrices. We use the following comparison definition from [43].
Definition 4 (Closeness on a submatrix). We say M, M' E Rmxx are A-close on a 7-submatrix if there exist subsets A C [m]. B S [n] satisfying |A| 2 m min, n), B 2 min n.,, and
M - M' M' Ax S..
y = 0, we say M. M' are A-close. When M, M' are both symmetric, we require that B.
We note that in Definition 4, A, B are unknown; our analysis only uses this definition existentially.
4 Outline of proof of Theorem 1
In this section, overview the main components of the proof of Theorem which developed and proved in full in the appendix sections. Our final matrix completion algorithm, Algorithm 8, alternates between two main subroutines, Algorithm 3 (analyzed in the following Corollary 1) and Algorithm 7 (analyzed in the following Proposition 3). We prove Theorem 2, a formal version of Theorem by combining Corollary and Proposition 3 in Appendix E. We now explain and motivate each of these pieces in the context of our technical overview in Section 2.
The first main component of our final algorithm, Algorithm 8, takes input parameters and Yoot as well as an input matrix M gdxd satisfying M - Mr I A (i.c., M and the target matrix M A-close), where A is sufficiently larger than the noise level |N] Its goal is use semi-random
observations from M M + N to return another matrix M' E Sdxd such that M and M are A -cllose on Submmmriatrii (Definition 4). In other words, are willing give up on a "hu fraction of rows and columns to make an a factor progress on the remaining submatrix. To achieve this result, we first provide a helper claim Proposition an analysis of Algorithm 2 (DropOrDescent).
Proposition 1, Let M Şdxd be given as a rank-r factorization, let M E Sdxd d be rank-r*. and let U S [d]. Suppose know for "drop: "/sub E [0. 1). A > 0, that [[d] U ", and MUXU. MU f == r + r" and an appropriate polynomial,
A-close "isub- submaarix.. Let 8, E (0, 10) 8 K and suppose for
log(4) Tsubb
E
poly
%/ub S 360
(4)
Given one call to (M + N) |N S
SlanA
the following holds with probability 2
6.
20d
1. If Algorithm 2 returns Line 12, then M Mi are (1 288 Y/sub +
A-close on
Vüx -ubmatrixx and IU U'| S 40(7sub + 1/2 dog log
2. If Algorithmm returns on Line 16, then MUxU. MuxU are 10 A-close on a 2abb- submatrix, and M' given rank-(3r 2r*)) factorization.
The runtime of the algorithm is
o o poly
F Flog(?
:)
where m 2 d is the number of observed entries upon calling ON N).
Proposition is used to analyze one step of Algorithm 2, after we have already taken few iterations
and explicitly removed " rows and columns [d] \ U from consideration, so that our remaining submatrices on U x U are close Submattu. Our goal will ultimately to have Yaub, 7dop < 2 throughout the algorithm. Algorithm provides bicriteria guarantees: in the "drop" case of Item 1, slightly increases the "drop parameter, increases 7sub by an smaller amount (where the tradeoff is

---

given by a degree of freedom k), and makes a small amount of progress (decreasing the closeness by 1 -e)).. In the "descent" case of Item 2, we instead decrease the closeness by large ((poly(e)) factor, while doubling Tuub and roughly tripling the rank. By choosing the parameters appropriately, we show that iterating upon Proposition yields Corollary 1, proven Appendix B.
Corollary 1. Let M, E saxd be rank-r", and suppose || Toor (0, tt) Algorithm 3 uses one call to O + N), where for appropriate polynomials,
M S A. Let a 2 250 and
poly (b)( ao
A
|| S
d. d.poy(( log(#) (+o( p=
d
The
and computes rank-r* A -close Submatrx. The runtime of the algorithm is ma) -poly( 1 log( ()), where m is a the number of observed entries upon calling Og (M* + -N).
M', such that with probability 2 8, M' and M are
We now explain the key computational method we develop to implement Proposition 1. We will solve subproblem, defined in (5), to attempt find a reweighting which makes progress. The subproblem enforces the conditions on candidate weights wo mentioned in Section 2, and is formally stated below:
F Fprog-nal (2. S) =- ----(11 (Iz, + CH, (slift D -s)
(5)
where D(w)= W. D.D., v2 [ for all I, and denotes entrywise division.
EEI
The difference between (5) and our informal sketch in (2) is that we reparameterize x f- w o u where e is the squared observations of the difference matrix D, and I is the set of observations. We also introduce a tradeoff parameter 7) for controlling additive error bounds via Fact 1. Thus, the component (17. 2) = (w. w) captures the progress condition (Item 3), and the component H;; (slift
S)) captures the flatness condition (Item 2). We optimize (5) over ||S|| < + e, the set of short matrices, and x belonging to X' defined (22) which we observe is rescaling of bipartite matching polytope by parameter h (Fact 3). This polytope is used to enforce the spreadness condition (Item 1).
In the case we find a good solution to the subproblem, we can use the resulting solution take descent step and give the guarantee in Item of Proposition 3. Otherwise, we have certified that excluding few heavy rows and columns removed much of the progress that could be made (which we prove is the only way a good solution does not exist), and hence obtain the guarantee in Item 1. Our main guarantee for solving (5) a fast rate is the following, proven in Appendix C.
Let e E [0, C1 and E 1), and suppose [[]],] E [E, for all E I. There is an algorithu computing (2r, S), 6-approximate minimizer to (5) with probability 2 1 8, in time
Proposition 2.
o (I + +d) T2 poly (CkBu log
and T [ 1. and is given as a rank-r rank-r= 0 T) factorizationn
for R. 1
The last component in the proof of Theorem is Algorithm 7, "rounding" step where we take the output of Corollary 1, say M, which guaranteed to be close to M on large submatrix, and then postprocess it to matrix M that is guaranteed to be close to M* everywhere with some poly(r, μt log d)-factor loss in the closeness. As long as the progress made by Corollary is larger than this factor, we can simply alternate Corollary and the rounding step to still make constant-factor progress in each iteration. We prove the following result in Appendix D.
Proposition 3. Let M Saxd be rank-r* and y-incoherent, and let M - M* for N Sdxd with [N] < A for some A 2 0. Ler M E Sdxd be given as rank-r decomposition, with r 2 r". Further, for 7 E (0, 1) suppose M and M are dA-close on a submaatrix. Finally, assume
1
7 10 log(d))
Then for any 8 E (0, if 2 1 pol((uroog())) for an appropriate polynomial, Algorithm 7 uses one call to (M and with probability 2 1 8, outputs M 5axd such that
| s poly (ur log 8 )
M M
(6)
9

---

Also, M is given rank rank-poly(1r) log( g)) factorization. The algoritim runs in m pplly(urlogg)) time, where m is the number of observed entries upon calling Og (M).
Acknowledgments and Disclosure of Funding
AL was supported in part by an NSF GRFP and a Hertz Fellowship. AS was supported in part by a Microsoft Research Faculty Fellowship. NSF CAREER Grant 1955039, and a PayPal research award. JK was supported in part by NSF awards CCF-1955217, CCF-1565235, and DMS- DMS-2022448. Part of this work was conducted while visiting the Simons Institute for the Theory of Computing.
NSF Grant CCF-
References
[1] Prizes for matrix completion problems. https://ww, http:://wwwwwwggmmmm.... www.gnenttoootommmmmmmmmmmmm org/posts/ pptppeeeeeo........cccccaaaoaooo
2023.
[2] Amol Aggarwal and Josh Alman. Optimal-degres polynomial approximations for exponentials and gaussian kernel density estimation. In 37th Computational Complexity Conference, CCC 2022, volume 234 of L/Plcs, pages 22:1-22:22 Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022.
[3] Zeyuan Allen-Zhu and Lorenzo Orecchia. Nearly linear-time packing and covering LP solvers. Math. Program., 175(--3) 2019.
[4] Susan Athey, Mohsen Bayati, Nikolay Doudchenko, Guido Imbens, and Khashayar Khosravi. Matrix completion methods for causal panel data models. Journal of the American Statistical Association, 1 116(536)1716-1733) 2021.
[5] Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114,, 2008
[6] James Bennett and Stan Lanning. The netflix prize. 2007.
[7] Aditya Bhaskara, Sepideh Mahabadi, and Ali Vakilian. Tight bounds for volumetric spanners and applications. CoRR, abs/2310.00011 2023.
[8] Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, and Yuanyuan Yang. Dueling optimization with a monotone adversary. In International Conference on Algorithmic Learning Theory, volume 237 of Proceedings Machine Learning Research, pages 221-243. PMLR, 2024.
[9] Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. Journal of Algorithms, 19(2):204-2) 234,,, 1995.
[10] Rares-Darius Buhai, Pravesh K Kothari, and David Steurer. Algorithms approaching the threshold for semi-randon planted clique. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1918-1926, 2023.
[11] Emmanuel Candès and Yaniv Plan. Matrix completion with noise. Proc. IEEE, 98(6):255-936 2010.
[12] Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Commun. ACM, 55(6): (116))111:11 11-119, 2012.
[13] Emmanuel J Candès and Terence Tao. The power convex relaxation: Near-optimal matrix completion. IEEE Transactions Information Theory, 56(5):2053-2080, 2010.
[14] Yudong Chen, Ali Jalali, Sujay Sanghavi, and Huan Xu. Clustering partially observed graphs via convex optimization. The Journal of Machine Learning Research, (11))2213-2233 2014.
[15] Yudong Chen, Sujay Sanghavi, and Huan Xu. Clustering sparse graphs. arXiv preprint 1100v3121..3335, 2(5), 2012.
10

---

[16] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM journal on optimization, 30(4):3098-311 -321,, 2020.
[17] Yu Cheng and Rong Ge. Non-convex matrix completion against a semi-random adversary. In Conference On Learning Theory, pages 1362-1394. PMLR, 2018.
[18] Yeshwanth Cherapanamjeri, Kartik Gupta, and Prateek Jain. Nearly optimal robust matrix completion. In International Conference Machine Learning, pages 797-805. PMLR, 2017.
[19] Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost-linear time algorithms for markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Thheory of Computing, STOC 2017, pages 4 410-419, ACM, 2017.
[20] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of theorem of johnson and lindenstrauss. Random Struct. Algorithms, 22(1):60-655 2003.
[21] Christopher De Sa, Christopher Re, and Kunle Olukotun. Global convergence of stochastic gradient descent for some non-convex matrix problems. In International conference on machine learning, pages 2332-2341. PMLR, 2015.
[22] Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. J. ACM, 61(1):1:1-1:23, 2014.
[23] Micha Elsner and Warren Schudy. Bounding and comparing methods for correlation clustering beyond ilp. In Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing, pages 19-27. 2009.
[24] Uriel Feige and Joe Kilian. Heuristics for semirandom graph problems. Journal of Computer and System Sciences, 63(4):639 671, 2001.
[25] Uriel Feige and Robert Krauthgamer. Finding and certifying a large hidden clique in semiran- dom graph. Random Structures & Algorithms, 16(2):195-208, 2000.
[26] David Gamarnik and Sidhant Misra. A note alternating minimization algorithm for the matrix completion problem. IEEE Signal Processing Letters, 1340-13334--143 2016.
[27] Xing Gao and Yu Cheng. Robust matrix sensing in the semi-random model. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023.
[28] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has spurious local minimum. Advances in neural information processing systems, 29, 2016.
[29] Amir Globerson, Tim Roughgarden, David Sontag, and Cafer Yildirim. Tight error bounds for structured prediction. arXiv preprint 1409.5:40 2014.
[30] Yuzhou Gu, Zhao Song, Junze Yin, and Lichen Zhang. Low rank matrix completion via robust alternating minimization in nearly linear time. In The Twelfth International Conference on Learning Representations, ICLR 2024. OpenReview.nes 2024.
[31] Suriya Gunasekar, Ayan Acharya, Neeraj Gaur, and Joydeep Ghosh. Noisy matrix completion using alternating minimization. In Machine Learning and Knowledge Discovery Databases European Conference, ECML PKDD 2013, volume 8189 of Lecture Notes in Computer Science, pages 194-209. Springer, 2013.
[32] Moritz Hardt. Understanding alternating minimization for matrix completion. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 651-660. IEFE, 2014.
[33] Moritz Hardt and Mary Wootters. Fast matrix completion without the condition number. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, volume 35 of JMLR Workshop and Conference Proceedings, pages 638-678. JMLR.org, 2014.
11

---

[34] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang. Solving SDP faster: robust IPM framework and efficient implementation. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 233-244. IEER, 2022.
[35] Martin Jaggi. Revisiting frank-wolfe: Projection free sparse convex optimization. In Proceed- ings of the 30th International Conference on Machine Learning, ICMI. 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 427-435. JMLR.org, 2013.
[36] Prateek Jain and Praneeth Netrapalli. Fast exact matrix completion with finite samples. In Conference on Learning Theorr, pages 1007-1034. PMLR, 2015.
[37] Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sidford, and Kevin Tian. Structured semidefinite programming for recovering structured preconditioners. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023.
[38] Arun Jambulapati and Kevin Tian. Revisiting area convexity: Faster box-simplex games and spectrahedral generalizations. CoRR, fass23033.1627., 2023.
[39] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In 6 IEEE Annual Symposiun on Foundations of Computer Science, FOCS 2020, pages 900, 2020.
[40] Chi Jin, Sham M Kakade, and Praneeth Netrapalli. Provable efficient online matrix completion via non-convex stochastic gradient descent. Advances Neural Information Processing Systems, 29, 2016.
[41] Charles R Johnson. Matrix completion problems: a survey. In Matrix theory and applications, volume 40, pages 171-198, 1990.
[42] Jonathan Kelner, Jerry Li, Allen X Liu, Aaron Sidford, and Kevin Tian. Semi-random sparse recovery in nearly-linear time. In The Thirty Sixth Annual Conference on Learning Theory, pages 2352-2398. PMLR, 2023.
[43] Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Matrix completion in almost- verifiittii time, 2023.
[44] Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from noisy entries. In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009, pages 952-960. Curran Associates, Inc., 2009.
[45] Alexandra Kolla, Konstantin Makarychev, and Yury Makarychev. How to play unique games against semi-random adversary: Study of semi-random models of unique games. In 201 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 443-452, IEEE, 2011.
[46] Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215-245. 1995.
[47] Gunjan Mahindre, Anura P. Jayasumana, Kelum Gajamannage, and Randy Paffenroth. On sampling and recovery of topology of directed social networks a low-rank matrix completion based approach. In 2019 IEEE 44th Conference on Local Computer Networks (LCN), pages 324-331, 2019.
[48] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Approximation algorithms for semi-random partitioning problems. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 367-384, 2012.
[49] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Sorting noisy data with partial information. In Proceedings of the 4th conference on Innovations Theoretical Computer Science, pages 515-528, 2013.
12

---

[50] Konstantin Makarychev. Yury Makarychev, and Aravindan Vijayaraghavan. Constant factor approximation for balanced cut in the pie model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 41-49, 2014.
[51] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Correlation clus- tering with noisy partial information. In Conference on Learning Theory, pages 1321-1342.
PMLR, 2015.
[52] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Learning commu- nities in the presence of errors. In Conference on learning theory, pages 2258-1291. PMLR, 2016.
[53] Claire Mathieu and Warren Schudy. Correlation clustering with noisy input. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 712-728. SIAM, 2010.
[54] Theo McKenzie, Hermish Mehta, and Luca Trevisan. A new algorithm for the robust semi- random independent set problem. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 738-746. SIAM, 2020.
[55] Ankur Moitra, William Perry, and Alexander S Wein. How robust are reconstruction thresholds for community detection? In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 828-841, 2016.
[56] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Systems 2015,
pages 1396-1404, 2015.
[57] Nagarajan Natarajan and Inderjit S. Dhillon. Inductive matrix completion for predicting gene-disease associations. Bioinformatics, 30(12):60-66 68, 2014.
[58] Yurii Nesterov. Smoothing techmique and its applications in semidefinite optimization. Mathe- matical Programming, Series A, 110:245-221 259, 2007.
[59] Luong Trung Nguyen, Junhan Kim, and Byonghyo Shim. Low-rank matrix completion: A contemporary survey. IEEE Access, 7:94215-94237, 2019.
[60] Andy Ramlatchan, Mengyun Yang, Quan Liu, Min Li, Jianxin Wang, and Yaohang Li. A survey of matrix completion methods for recommendation systems. Big Data Mining and Analytics, 1(4):308-322 2018
[61] Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
[62] Jasson DM Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collabo- rative prediction. In Proceedings of the 22nd international conference on Machine learning, pages 713-719, 2005.
[63] Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithmss Cambridge University Press, 2021.
[64] Anthony Man-Cho So and Yinyu Ye. Theory of semidefinite programming for sensor network localization. Mathematical Programming, Series B, (109):367-384 2007.
[65] Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary? arXiv preprint 150.v:150, 2015.
[66] Ruoyu Sun. Matrix completion via noncomeee Algorithms and theory. PhD thesis, University of Minnesota, 2015.
[67] Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory, (2(1)):5355657) 2016.
13

---

[68] Wei Tu, Peng Liu, Jingyu Zhao. Yi Liu, Linglong Kong, Guodong Li, Bei Jiang, Guangjian Tian, and Hengshuai Yao. M-estimation low-rank matrix factorization: general framework. In 2019 IEEE international conference on data mining (ICDM), pages 568-577. IEEE, 2019.
[69] Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs nearly linear time, 2021.
[70] Bo Xin, Yizhou Wang, Wen Gao, and David Wipf. Exploring algorithmic limits matrix rank minimization under affine constraints. IEEE Transactions on Signal Processing, 64(19):4960- 4974, 2016.
[71] Jialun Zhang, Hong-Ming Chiu, and Richard Y Zhang. Accelerating sgd for highly ill- conditioned huge-scale online matrix completion. Advances Neural Information Processing Systems, 35:37549 1777449-776,222 2022.
[72] Shuai Zhang and Meng Wang. Correction of corrupted columns through fast robust hankel matrix completion. IEEE Transactions on Signal Processing, 67(10):2580-22 2594,, 2019.
[73] Xiao Zhang, Simon Du, and Quanquan Gu. Fast and sample efficient inductive matrix comple- tion via mulli-phase procrustes flow. In International Conference Machine Learning, pages 5756-5765. PMLR, 2018.
[74] Tuo Zhao, Zhaoran Wang, and Han Liu. A nonconvex optimization framework for low rank matrix estimation. Advances in Neural Information Processing Systems, 28, 2015.
14

---

A Additional preliminaries
In this section, we formalize some additional preliminaries and helpful notation which will be used in the remainder of the appendices.
General notation. For r E N we denote [n] := = (iEN n). We say a vector is s-sparse if it has $ nonzero entries. When S _ T and T'is is clear from context, we let S := S. The all-zeroes and all-ones vectors of dimension d are denoted O₂ and 4g. Applied to a vector, 1-I1p denotes the lp norm for p 2 1. Applied to matrix, I|l1l, denotes the l norm of the vector corresponding to the flattened matrix. We use (S) to denote the median of set S. For t R we let sign(t) 1 if t 2 0 and sign(t) = -1 otherwise. We let o denote the entrywise product of two vectors.
Matrices. Matrices are denoted in boldface. The number of nonzero entries of matrix M is denoted (n), and the set of indices corresponding to these nonzero entries, i.c., the support, denoted (M), We define Tmv (M) as the amount of time it takes to compute My for any vector V; note Tmv (M) rank-r factorization then Tmx (M) O(mm + n)r). We equip RTXx" with the inner product (A, B) := Tr(AT B), denote the
((nnz(M)) if M has explicit entries, and if M E Rmx x is given as
identity by La and the all-zero m X n matrix by 0mxn- The 1" row and jth column of a matrix M are respectively denoted M, and M.j. For a collection of matrices {Ai]eej E Ruxx with an associated operator A (clear from context), we denote A(x) = EiEN x;A,, for x E RR* We say M is s-row column sparse (RCS) if its rows and columns are s-sparse. For S S [m]. T S [n]], we let the submatrix of M E Rmx* indexed by S, T be denoted MsxT. When S is a singleton {i} for E [m]] we denote this M.,T and similarly define Ms., for j E [n].
The Frobenius, operator, and trace (nuclear) norms of matrix are denoted Il- Il-Ilap- and l1 respectively, corresponding the 2-norm, co-norm, and 1-norm of the singular values of the matrix. We denote the symmetric d x d matrices by gaxd and the positive semidefinite cone by soxd We say M E R has singular value decomposition (SVD) M UEVT T if M is rank-r, Σ R is diagonal, and U Rmxr, V E Rax" have orthonormal columns. The ordered singular values of M E R are denoted (M))is(mmm((mm))) where oi (M) is largest. Similarly we define the ordered eigenvalues of M e Sdxd by (M) For M E Sdxd with cigendecomposition UAUT, we define exp(M)= U exp(AAU" where the right-hand side, exp is applied entrywise on the diagonal. We also define log M for M sixd and [M] for M E Sdxd the functions are applied to the eigenvalues in the appropriate basis. Finally, we let span (A) denote the column span (or image) of a matrix A, and for subspace V C Rd, we let Il denote the orthogonal projection matrix onto V.
Index sets. For d E N, we let S(d) contain all symmetrized indices of the form:
(i, for E [d], or (i,,)), (i, for E id],i
We use (i,j)* as shorthand for the singleton {(i, i)} if j. and otherwise as shorthand for (i,,5) (i, i)}. When I is set of indices in [d] x [d). we let My be the d x d matrix which zeroes out all entries of M except those in 1. For a symmetrized index E S(d). we denote the scalar value of the entry by [M]. (note that this is well-defined even when & contains two indices due to symmetry). The zero-one matrix whose only nonzero entries are is denoted by E, so that M. = [M],E, for all e E S(d). For I C S(d) clear from context, we let E be the operator on w E RD which forms the associated d matrix whose indices on I agree with w and otherwise zero entrywise, i.e.,
E(w) = Σ W. E.
CEI
Optimization. For convex X R with X' C Rd, we let (z) denote the subgradient set at X. We let ||yll. sup| x: T denote the dual norm to norm ||-I|- When M is d x d linear operator we use the notation Miu, v] := (Mu, v). This becomes relevant when M a Hessian of matrix function (a linear operator on d x d matrices), so M(U, V] evaluates this operator on U, V.
Reduction to symmetric matrices. We briefly justify our focus on symmetric matrices in Defini- tion 3. We begin by recalling two facts.
15

---

Fact 2. Let m, E IN with m 2 n. There exists k E N such that kn E m). .
Lemma 1. Let m, n, N and let M |Rmxx be rank-r with SVD M UEVT. Suppose that both U == -pan U) and V == span (V) are y-incoherent. Then, letting M' E RRuxkn be defined as
M (M M
M M).
A times
and letting M' have SVD M' UE'WT, then W == span W) is p-incoherent.
Proof. is straightforward check that valid SVD is given by
E' =K=V W
V
V VT).
À times
Because incoherence invariant the choice of SVD, the conclusion holds.
Consider asymmetric variant of the problem in Definition 3, where M Rmxn for 2 is rank-r" and j--incoherent, and we have p-semi-random observation oracle access (defined analogously to Definition 2) to M Let k be the integer from Fact 2, and let M E Rmxkn be constructed as in Lemma by concatenating M times. The row and column spans of M are p-incoherent, by Lemma 1, Moreover, we can simulate p-semi-random observation oracle access to
O 0mxm M
M
E ((m+k))x(m+k))
Okn
in the symmetric sense of Definition 3, given asymmetric oracle access to M It straightforward to check that because M has dimensions within constant factor of each other, the incoherence parameter is only affected by a constant in this lifting process. For simplicity in the remainder of the paper, we focus on the case of symmetric matrices, i.e., the problem statement in Definition 3.
Sample splitting. Finally, we recall a convenient subsampling claim from [43] that extends to the semi-random model, which lets us use OF (M) to simulate access to Of (M) for smaller values q P p.
Lemma Let {PR]RE(K) C (0, 1) satisfy Pk: S Sps. S for all k E [K], and ler M Sdxd We can simulate sequential access to ps. (M*) ) all [K] with access Our (M*).
Proof. The claim is immediate from the observation that the proof of Lemma 1, [43] is monotone in p. In particular, the same subsampling process in [43] preserves monotonicity of observation probabilities and hence produces valid semi-random observation oracles.
B Semi-random partial matrix completion
In this section, we develop Algorithm 3, our main subroutine for partial matrix completion in the cami-random model (Definition 2). Algorithm 3 uses recursive calls to Algorithm 2, DropOrrescent, which implements single step of our partial completion method.
At high level, one application of DropOrDescent is parameterized by current number of dropped
rows Yhoo. a current number of excluded rows "sub. a subset of undropped rows = [d] D satisfying
[D] S d, and rank-r matrix M such that M xu is promised to be close target Mj x a Y -ubmattrxx (Definition 4). It then distinguishes between the following cases from semi-random, noisy observations of M* by solving testing problem via optimization.
1. In the first case, dropping additional fraction of rows and columns decreases the closeness parameter by a small amount, i.e. a small subset of rows or columns are responsible for nontrivial portion of the mass. We call this case the "drop" case.
16

---

2. In the second case, after removing few rows and columns, the remaining mass is still large. We show that in this case. by deleting particular subset of problematic rows or columns, we can use well-condittonednes properties of the remaining submatrix decrease A by a constant factor. We do by solving an optimization problem, which finds spread reweighting of observations with short-flat decomposition. We call this case the "descent" case.
We analyze the descent case in Appendix B.I, where we demonstrate sufficient conditions on proposed reweighted step which guarantee progress under submatrix closeness. The candidate steps we analyze in this section are all reweightings of truncated observations, which are found by solving an appropriate optimization problem (see (20)). We then analyze the drop case in Appendix B.2, where we show that either our current difference matrix has Frobenius norm which is unstable to dropping few rows and columns, or good solution exists which is compatible with our descent algorithm. We give an explicit dropping procedure for handling the former case in Appendix B.3. We finally put these cases together and give a win-win analysis of DropOrDescent in Appendix B.4.
B.1 Descent steps
In this section, give our progress analysis in the case where we can find sufficient signal in observations. Specifically, Lemma 7 gives sufficient conditions on a reweighted, truncated observation matrix such that can improve submatrix closeness parameter by constant factor.
For D gdxd, we first define a clipping operation which will be used to control our reweightings. We let clip,, (D) be the matrix which clips all entries to the range u, u). formally defined by
[clip,, (D) = med (-u, Dij. u)
We also will use the following claim which follows from straightforward casework. Lemma 3. Let u 2 0. |a| S u, and a' == med( - a + b, u). Then la' al s (b].
Proof. If a + bl < u the claim is obvious. Otherwise, if a' = it must be the case that 2 0. and 0 a' S b. Similarly, a'
we must have a' a 2 b.
We now introduce some additional notation. Let I c S(d) be a set of symmetrized indices under consideration (corresponding to observations). For E R and D gdxd clear from context, we let
D(w)=
w. D..
(8)
For parameter p, we define the set of "spread" reweightings of the observations Dz by
Wp = W E IRI max
Σ
WP DD} S
(9)
iEid
(E)
Further, we require the following result low-rank approximation. Lemma (Theorem (56]). Let 6,e E (0, 1), let M gaxd, and let q [d]. There is algorithm which returns Z E Rddx with orthonormal columns such that
Iz MZZ - -M (1
with probability 2 1 8, in time
o o Tay (M)
q log o
Ve
Moreover, we have for all i E (q). letting z; be the 8th column of Z,
2 M E [[1 - e) (M), (1 + e) (M))
Finally, we provide ways to bound the singular values of approximately low-rank matrix.
17

---

Lemma 5. Let M.N E Sáxd have eigendecomposittons M = UAU and N = VEV", where diag (A). Σ diag (o), and X, a R are nonincreasing order. Then. |M N 2
|| o l12--
Proof. Since | = | and [N| = = expanding the squares of both sides shows that it suffices to prove that (M, N) (),0), which follows from the von Neumann trace inequality. [
Lemma 6. LetE 1, ler M E gdxd be rank-f, and suppose |M- S||F S e S gaxd. Then for any 8 E N, we have of+s+1 S 3//2-
Proof. Let À E R be the set of eigenvalues of M nonincreasing order, and similarly let a E R be the nonincreasing eigenvalues of S. By assumption, A; for all 2 f + 1, and ||x o ll2 I by
Lemma 5. Thus, at most + eigenvalues of S can larger than 3/22. giving the conclusion. O
We are now ready to give our main progress guarantee in Lemma 7. Specifically, we show that reweighting of truncated observations which has enough signal and admits a short-flat decomposition is guaranteed to make significant progress, long as it is sufficiently spread in the sense of (9).
Lemma 7. Lete, E (0, 1.). f,u. 2 O, and T _ S S
[d] such that IU S1 S yd, IS T] yd, and 4. Suppose that for D,D Dr, N E Sdxd we have D D* N. for rank-f D with [D & |D I u, and [N]| S yl. Let
D = clip,,(D)
and for I S S(d) n (U x U), w E R 20' suppose the following conditions hold for S, F E &dxxd supported on In (U U) with =
1. w E for žंत recalling the definition (9).
2. (D, D(w)) 21 -
3. ||]|| S 1 c.
4. [FFloop S --73.
5. min,ez [[D],] 2 l.
Then, letting Rddx2 be the output of Lemma 4 with parameters & e M S, and
- 2f, we have with probability - 5 that
D ZZ SZZ
$ 10ct.
TXT F
Proof. As starting point, claim that
1Dix--S0 S V13e.
(10)
To this, expand show that
D - $1F < 2 3c 2 2DT STXT)
22+
DixT. (D(w) TXT
+2 D 1r
(1I)
DrwT, (D(w)
D - D
|(w)
52+ 5c
+2
TxT
Drxr; (D(mc)
22+7c 2
TxT
The first line used Item 3 and The third used Item 4 and that [DTxxIla S /F and the (vector) Hölder's inequality. The last line used |D $ u, the definition of D, and Lemma 3 to conclude
1Dsxslli 21r 1, and the second used the (matrix) Hölder's inequality.
D D
< NNxx $ Soe,
TxT 00
18

---

and also bounded [D(w)]la via Items and 5, which show
[D(w)lla (D. D(w)))
1
pd
max IEZ
[D].
e 27
Finally, since w is supported on U x U, applying 10 \ ( - 2yd, Item 1, and Item 2 yields
D Drxr.
[D(w)] TxT
2 (D. 4rpd 2 3c.
(12)
Then, (10) follows by combining (11) and (12). Next, applying Lemma using (10) shows that
13c f
22)+1(S) S
Therefore, assuming the algorithm in Lemma 4 succeeds, we have
6VE Vi
ZZ szz S (ZZ' SZZ S), where || llop S
:=
At this point, we can write D(w) = + (F F').
where by the triangle inequality
F F'llop T
VF
Since || < || I 1 + the remainder of the argument is identical to the proof of (10) with the worse flatness parameter, where we use that ||/ill| S | || and ||xx || S |||]]
B.2 Existence good solutions
In this section, define a stability condition (14) under which implies solution exists which satisfies the conditions in Lemma 7. We use this existence claim to certify progress in one of two ways in our final algorithm. In Lemma 11, show that under (14), there exists a reweighting (with high probability over the semi-random observations) which is compatible with Lemma 7's requirements. We then show Lemma 12 that in the absence of (14), one can increase the drop parameter to improve the submatrix closeness bound. We will analyze an explicit dropping procedure we use in this latter case Appendix B.3. We first require a helper guarantee from prior work on controlling entries of a low-rank matrix after dropping a few problematic rows and columns.
Lemma 8 (Lemma 6, [43]). Let A Gaxd be rank-i matrix with || || and let y [0, 1].
There is S' C [d] with S 2 (1 7)d, such that
VF
| S
(13)
yd
We also require a bound on the sampling error of random observations from a matrix with bounded entries, rows, and columns, which is an application of the matrix Bernstein inequality.
Lemma (Lemma 7, [43]). Let p, [0, 1. P, 2 0, and let A Sdxd satisfy | S p for all i [d], and [Aig] S T for all (i.5) [d] x [d] C (d) a random subset where each E S(d) is included with probability p, and ler Ä = Aq. Then with probability at least 1 8-
A
-
1p
4 max
P vp
log 8 ) log d
(0))
Finally, need guarantee the concentration of empirical estimates of squared & norms.
Lemma 10 (Lemma 3, [43]). Let p. 8, a E (0, 1), let u Rd have ||ollcc I r. and let ö E Rd have each ūn independently set to with probability p. and 0 otherwise. Then with probability 2 1 5,
|ا12 < max (a 1|u112
37 log 3
||01|2
op
19

---

We are now ready to give our main result on sufficient conditions for good solution to exist.
Lemma 11. Let 6,,,7,P E (0, to). and S CCC.
U S [d] such that IU V/S yd. Let
2V7
240F log( 6d)
20d U.
q p
33c2d
Suppose that for D,D N Sdxd, have D = D' + N. for rank-f D with [D xxs lF 1
and |N|] I 7t. Further, for D == (D), let 52" = {e S(d) n (U x U) [D] 2 f).
Finally, let 5' be the result of applying Lemma 8 with A Sxx
3. so [D s'xs oc S
and let T == S'> \ L where L is the indices of the [ rows of Ds with largest &o norms, so |S T S yd. Suppose
|DrxT]| 1 21
(14)
Letting 2 _ S(d) have each e E S(d) independently included with probability p. and w E (0, 1 have [w*]. p if and only if E (T T) nst the following conditions all hold with probability
> 8 over the randomness of D2 and St F E Egaxd supported on (T (T) D with D(w=)
F* + S
1. w² E for p 2nd recalling the definition (9).
2. (D, ((,D())) ((w)) 21
3. ||*||F S +
nc 4. | |lop 4F-72.
Proof. For notational convenience, let L* S(d) 2 be the set of indices i E S(d) with [D].] < f. We define our decomposition of D(w=) as follows, where we recall w" is supported on (T x 7) n
D(w=)= = D(TXT)NN- + D(w=) DiTXTIER.
Now, clearly ||N||= < d IN < 200 || < s < where we used that every entry of S* is smaller in magnitude than the corresponding entry in Dsxs (it is zeroed out if it does not belong (T x T) n and otherwise is clipped to smaller range). This establishes Item 3. The same logic shows that ||D II: S 1 + 200 Combined with (14) and the definition of
max ET
D
1
1
2
c e
(15)
y
10
5yd
since
<
DDs D ll S 10. and L consisted of the largest rows
of 5' by & norm. Therefore, applying Lemma 9 with A + -DTTxTinas T + u, and p² < 5 establishes Item 4 with probability 2 1 5 using the lower bound on p. We further have by (14) that
| || 2 30
De || 2
de 2 1
30
12
Therefore, Lemma 10 with set to the vectorized D D(TXT)naS, T u, and a E shows
| | I|= I|- (D, max (a (alpDextToo))
2 3u2 log (9)
ap
with probability > 21-4; again used our lower bound on p. Combining the above two displays establishes Item 2. Finally, to see Item I, fix a row i E T. We apply Lemma 10 once more with v set
to the vectorized [DerxTyna=]s la and a to obtain that with probability 2 1 3
3 [ ).1l < 2 where we used (15) and our lower bound p.
[Daxmnoo
6u log(?) < 2
< 2yd'
37d
20

---

We also provide helper lemma for making progress if (14) fails to hold.
Lemma 12. In the setting of Lemma 11, if (14) is false, [Dixrlle S 1
Proof. This follows from Lemma and the assumption on (14), which lets us bound
Dixxlll= - DrxT +
-D TxT IF
$
Drxr
+ +d|NN S - 200 - 1
36
B.3 Drop steps
In the previous Appendix B.2, we developed Lemmas 11 and 12, which together say that either there exists good solution compatible with the progress analysis in Lemma (if (14) holds), there an R y fraction of rows and columns which are responsible for an R fraction of the Frobenius norm of the difference matrix (if (14) does not hold). In this section, show in the latter scenario, there is a procedure which explicitly drops subset of rows and columns, such that on the remainder, slightly smaller submatrix makes an v e fraction of progress. Importantly, we can ensure that the submatrix parameter (i.e. in the sense of Definition 4) grows slowly using a tunable parameter, which lets us iterate drop steps without losing too many rows and columns.
We begin by giving a subroutine (Algorithm 1), analogous to Section 4.1 [43], which takes semi- cnrropriatelybbounde difference matrix and explicitly drops small
random observations from number of rows and columns, estimated from observations. We show that all remaining rows have few large entries with high probability. Our drop step simply applies this subroutine.
Algorithm 1: Sparsify
10.1 (D,,
Input: 0% [0.1] (D), U C [d], r 0, E (0, So +- U
Imax < 3og d +
for 0 < t max do
D. + Ogt (Dsxss)
for E St do ri, + Kij e St [il was observed, and [Delss /
S411 t- St \ RG where Rg St corresponds to the [nd] indices with largest Tia
end
return U < -Stmax
Lemma 13. Let D E gdxd, such that there is A C C [d] with |U\AI S 7d, [Daxalls S. Let 8 E N and p 2 800 log(d). Then with probability 2 1 8, Algorithm 1 returns U U with U UUI < 4yd d, and Di' has at most entries with magnitudes 2 t per row or column.
Proof. Let [0, 1]dxd be the true (symmetric) matrix of reveal probabilities of entries for calls OH, following Definition 2. Note that all entries of P are at least We define the potential
Σ P.j.
( [Di,,
We also denote the expected number of revealed large entries in each row and column as follows:
The Σ
Pij for all E S..
JES. |D
By standard Chernoff bound, with probability 2 1 - 8, for all 0 S < Imax and all i E St.
8 )
Ir,, rãcl S max T 50 log
(16)
21

---

Condition on this event in the rest of the proof. Due to our symmetric observation model (Definition 2). and since A has no entries 2 r in magnitude, any iteration, at least half of the contribution to i must be due to remaining rows in B, == Ss \ A, i.e. we have [B,] S ydd such that
4 2
Σ
iE B
Letting R denote the [yd] 2 [B,] indices in St with largest r7,0 we thus have from (16),
Σ rin RE
3
rhe 50ydlog d 3 p. -00y 3
d
Fia
4 R
g
E
Rg
Therefore, if t, 400yd log ( ) decrease &, by at least factor, so by our choice of mmxx we have fimaax1 S 1log I uped This shows that there are at most 7d remaining rows i E Stmax11 with r "ilmaxx-
2
Now, any remaining row E Staa-1 with at least entries with magnitude 2 has T f,lmax-- ps, and therefore will be one of the largest yd remaining rows by observed counts via (16). Hence, it will be dropped in the last iteration bmax claimed.
We conclude by showing that the leftover poorly- beeaae- rows and columns (i.e. those with any large entries) comprise a negligible fraction of the overall indices, using Lemma 8. This shows that by excluding these few indices from our maintained submatrix (after explicitly dropping indices via Algorithm 2), we make an & e fraction of the progress if the condition in Lemma 12 is met.
Lemma 14. Let ò, E, E (0, to) 8, 1. and S S U S [d] such that |U (SSS S -d. Suppose that for D, D* N E gdxd, we have D D N for rank-U D with | sxs
Ir and ||N S a Then, applying
and that there is subset T C S with [D flF S 1 and S \ T Algorithm I with inputs ON (0,1) (D), U, 5, and
<
ed g
v0
F
800 log(5)
7 7+ 10 0 p=
(17)
5d
returns a subset U" S U such that with probability 2 1 - 5, there exists subset S' S U with
NU' 40 ( v dlogd, d, | (++
Vo% d, and [ l1 S 11-5 8"
(18)
Proof. First, by Lemma there is subset A C S such that |S \ Al
S
10 3.
so that
V0
v0
Daxall S | + INN
6
10d
d
5d
Therefore, our application of Algorithm 1 with the parameters in (17) satisfies the hypotheses of
Lemma 13. Condition on the conclusion of Lemma 13 holding the rest of the proof (with probability
2 8), giving us the first bound in (18). Also, there are at most
FR. entries per row and column of PN
Dorxu with magnitude larger than 7 in (17), so there are at most entries per row and column of
D Du with magnitude larger than 7 5 27.
Next, if ||Dsxsllr S 1 5. the conclusion is obvious (taking S' + S S'U). Otherwise, for
C==-S' S,
1 D > (ID x - |
x (
1
- )
2)² -1--cp > e 3
2
By Lemma 8, there is subset S' S with
4d
ViOk
((SN))
D D's 11 5
(19)
4d
22

---

This set satisfies the second bound in (18), so it remains to prove the third, which follows from
Di DixxslF
|
lF
D Picnsixx'
2
1 2
Piinnsixss
F
2)
1 6 + 2 0 d. (27))
ed
ViOk
PR
4d
4
The third line used that there are at most ed rows in C, and each such row (restricted to S") has all entries bounded in magnitude by т, with the remainder bounded in (19).
but FM
B.4 Analysis of DropOrDescent and SRPartialCompletio
We now combine Lemma and Lemma 14 to give win-win analysis of progress step, DropOrDescent. This progress step either executes descent step (analyzed via Lemma 7), or drop step (analyzed via Lemma 14); of these cases. For the runtime analysis, we rely on Proposition 6, the main result of Appendix C, solve relevant optimization problem used by our algorithm, but all other parts of the proof celf-contained.
Lemmas and 12 demonstrate correctness of each
We provide pseudocode for the algorithm corresponding to Proposition in Algorithm 2.
Algorithm 2: DropOrDesseent(OP
[0.1] (M' + NN), M, U, Tdrop Ysub: A, r, 6, 0, K)
Input: 0%
[0.1] (M* + +N) where M gdxd is rank-r" and | I
CaaA 20d
S [d] with
[[d] \ U| Ydrop rank-r M gaxd such that MUxU. MixU A-close on a %uub Suub-aubb,
8, (0, 1,0,0K
0,
A r +
3 P1 < 2404 log( 201
P2 800FM logl 2d u 2v
+ f
d
20d
I + supp(ORr (M N)) { S(d) I[ +N N
MJ.l S ((A)N(UXU)
v, + A -2 (clip (M' + N M)]. for all i E
6 (w, S) + 12 approoximate minimizer to (20) with failure probability 5. computed using Proposition
output of Lemma 4 with M + D(w) S. ct 24 8
8 V2 < A-1, (= (D(w) -))
V (v, w) + CV22
if V. (1 12 then
U' + Sparsify(O 0.11 ( (M (M* +N -NM)),,U U,
vi ud
Tsab + 10 8 4
11
Return: ("Drop", U*)
13 end
14
else
output of Lemma with M S. 2 1 Return: ("Descent", M' < M + ZZ SZZ
15
16
end
Proposition 1, Let M E Sdxd be given as a rank-r factorization, let M E Sdxd be rank-r* and let U S [d]. Suppose know for "arop Ysub E [0. 1), A 0, that [[d] Ul s d, and MuxU, Mixu
A-close Nsab submatrix. Let 8, E (0, 1.) 0, k 1, and suppose for A = r + +r" and an appropriate polynomial,
Kf
(Ig(())
p
poly
Vuhh 360
(4)
CsubC
Given one call to (M + N) for |N
the following holds with probability > 216 8.
23

---

1. If Algorithm 2 returns on Line 12, then M Mir xt" are (1 (
Alosse on
288
Ysuu + - submatrix,, and IU U & 40(7/ub + 1/2 (d lo d. v8x
2. If Algorithm 2 returns on Line 16, then MUxU. MixU are 10c Alolos Yubb submatrix, and M' is given rank-(3r 2r*) factorization.
The runtime of the algorithm is
o (m
(llo(()) Yaub
m poly
where m 2 d. is the number of observed entries upon calling (M + N).
Proof. Throughout the proof, without loss we let A 1, since we can scale M by X. take the claimed step, and scale up by A (indeed, examination of Algorithm 2 shows it performs this scaling).
Further, let f == r + trrrr D M M, D = D + N, and fix
2/7
u. =
: 20d' = Y
Also, let D = clip,, (D), let Ω* = (1. E S(d) [D]1] S e) and let == S(d) \ 22 Note that
Lemma 2 shows we can simulate -p-smmi--radoon observation oracle access to D clip,, (D) (as required by Line 4) and the < 4 log(d) calls to pp-semi-randon observation oracle access to D (as required by Sparsify Line 11), given access Oz (M" + N), proving correctness of p in (4).
Let S. S(d) correspond to the output of Our (M N) in Line 4, after removing indices in L and outside U U, which couple to Ω S I, the result of calling Op, (M Nluxe) (i.e. P1
observation oracle where all probabilities are p1). after removing indices in L
We now describe our algorithm. Define W, as in (9), and for w R² define ((w) as (8). Consider the following optimization problem over W, x S, where = (S Saxd ||||| S +
F(w,S) = - (u, w) + CH, (slift (D(w)- - -))
min WES
(20)
VF
where E R² has v, D for all & EI, C
Y 1 = 24C' log(2d)
c approximate minimizer to F, and V, satisfying V - F(W,S) - 12- Pseudocode for computing such V with failure probability correctness and runtime of this step are analyzed at the end of this proof.
We compute (w, S), an 12
is provided in Line 9, and the
1. If V > -(1 - 1l ). we call Sparsify on (our semi-randon access to) the matrix D 12
ye 7 + Tsub + 10 f. p + p. and d $ We
M + M with parameters U, +-
then return the new row subset U' C U. We call this case the "drop" case.
2. Otherwise, update to M ZZ SZZT, where Z Rdx2# is the output of Lemma 4 with parameters å + S
2. M S, and q +- 2f. We call this case the "descent" case.
We first analyze the drop case. We claim that if V > -(1 16 ). it could not be the case that (14) held. To see this, suppose (14) held. Then, with probability
& (due to our lower bound (4)
p), Lemma 11 provides us (w=,, S,) E Wp x S satisfying
D(w²) = S F", (v, wn) 2 2: for ||S||| S + || S
Tsub 4
In fact, w is only supported on Ω, the fully random coordinates. By using Fact 1, conclude that
F v -
é /
+ (1F'1ll + log()2))
< (1 ") + CTsube
36
+ < -
2
VF
24
24

---

Therefore, any 12 approximate minimizer (w, S) to F will satisfy F(w, S) v -1 )g Finally, since we assumed our computed value V satisfies IV F(w, S) - 12 this contradicts V > -(1 - Le) as claimed. Hence, (14) indeed did not hold, so by Lemma 12 and our bounds in (4), the preconditions of Lemma 14 are met with +- 36 proving correctness of the "drop" case with the stated parameters.
Next, suppose we are in the descent case, meaning we have (w, E W. x S satisfying F(w, S) S -(1 - e). By nonnegativity the second summand the definition of F, this shows
(D,)(w)) (v, w) -6
Moreover, because (u, w² S dp 24 by the definition of Wp, we have
F(w. S)
|D(w)) -s s| < H (slift (D(w)-s)) <
(21)
C
where we used Fact in the first inequality. Lemma then yields correctness of the "descent" case.
We next bound the runtime, which the sum of three costs: the optimization solver, the cost of obtaining approximate value V, and the cost of Lemma 7 in the descent case. is straightforward to check that in the context of Proposition 6, which bounds the runtime of our optimization solver,
Ru = -0(-0)0 (flog(()) Suu
( ( log(d)
and T =
Yauub
Therefore, by our choices of C, m from before, the cost of Proposition 6 for failure probability is
o ((m++
((m
dr3 d log(d)
A log(d) 11.5 log
).
d
sub E8
8rsuub
Next, consider the cost of obtaining V ssatisfying IV- - FF,,,S) We can explicitly compute the term (u, w). and because 1/C/ log(2d) 21. suffices to obtain 21C 12/1/2 -additive approximation
to [ID(w) S Sllop by Fact 1. The guarantees of Proposition 6 give that [|((ww) Sllap p1/a (21)). Therefore, we may call Lemma 4 with q + L, e
2c (see
and + : in time which does 24
dominate the above, using the rank-O( (00 (222 (og(el)
factorization of given to us by Proposition Additionally, the runtime of Lemma 7, i.e. the cost of running Lemma 4 with constant and 2 does not dominate Proposition The claimed runtime follows by combining these bounds.
Finally, the failure probability comes from a union bound over Lemma 11, Lemma 14, the subroutine in Proposition 6, and our two calls Lemma 4, once for the descent step and once compute the value V. We set each of the failure probabilities of these five randomized steps to g.
By iterating on Proposition
provide our full partial completion method, Algorithm 3.
Corollary 1, Lei M,M şaxd be rank-r*, and suppose ||M M' S A. Let a 2 250 and 5, Noor (0, 1.) Algorithm 3 uses one call to O + N), where for appropriate polynomials,
poly log(()) (1)
||N]|co S
d poly The ()) a+to(1) p
d
and computes rank-r* (l) M, such that with probability 2 1 - 8, M' and M' are A -close on Submatib The runtime of the algorithm is m) poly r" log( ()). where m is the number of observed entries upon calling Oat (M* -N).
Proof. We claim that throughout the course Algorithm 3, the preconditions of Proposition are always met, i.e. 7ub is always an upper bound on the number of excluded rows U \ S, Vrro is always an upper bound on the number of dropped rows [d] \ U, and M always has rank r* To show correctness of the rank bound, the rank of our iterate only increases drop steps, where Proposition ensures r + y at most triples, so f - r (after the update on Line 11) remains a correct bound on r throughout the algorithm. Also, f < fro throughout, since there are R descent steps.
25

---

Algorithm 3: www.artialComplltiiionnio/o (M' + N), M, A, r" a, Yoa. 6)
Input: 0% [0 (M* + N) where M gaxd rank-r* M E Sdxd such that |M - 1 s A.
250, Ttor 8 E (0, T
Namp f- Neescent 0, R e + K 288yloga
Fux f- (2r*) 3R
f 2r", < [d], "Memp 10 RR log(d) 7suh
Tump
2 2-R R Ydrop +-
160RK log(d)
0 25600F (RK lug(d))²
1G R 4
The
while Narop RK and Neeseent do if DrroOOreeceet((0) (O (0.1] (M* N), M, U, 7dmpp Ysub; A, F r*, TKK MK- 0,K)
("Drop", ""rop",U" U²) then
U 4- U", "drop Vdrop + end else
Jue 2RK
A c exp(
Narop
Narop + 1
288
10 ("Descent", M'
5 DropOrDescent (0.1) (M' + +N), M,,,, U, Ydrop Ysubs A, r", R(K+1] C,K+ii,c,,,.. C,
3f, Tiub Vishh, M M', A 10 A, Neescem +- Ndesenn +
end
13 end
Return: M
We next prove correctness of the Ysub parameter throughout the algorithm. By Proposition 1, this parameter doubles each time Algorithm 2 runs descent step, which is correctly handled by Line 11. Moreover, the only other time Ysuh increases by 4_ each time Algorithm runs a drop step, via the first part of Proposition 1. Note that the algorithm terminates once RK drop steps or R descent steps have run, and by our choices of 0, K, we have
4
Temp
RKK- 160RK log(d)
2
VOk
which our initial setting of Yab in Line 3. Therefore, since the worst-case growth of the "yubb parameter over RK drop steps and R descent steps is if we encounter all of the drop steps first (and then repeatedly double It times), the value of Tsub is correct throughout the algorithm.
Next, we show that the "drop parameter remains correct throughout the algorithm. Note that the Tisub The
"heup parameter is never larger than 160RK log(d) S 160KK TeokKloggal log(dj in each drop step, by Proposition and our choice of is most
Therefore, the number of dropped rows
Piat 0
log d s (-2im That
+ That 4RK
Hha 2RK
40
160RK log d
4RK
Therefore the update to "drop in Line 7 is correct. We have also shown that over the course of the "ne
algorithm, never drop exclude more than 160RK log(d) we verify the second condition in (4) holds with the largest value of Tsubi
Ioed < "had rows in total. Additionally,
Them
160RK log(d) S 368
RKK) _1 factor progress on the closeness parameter A. Similarly, after R descent steps, since 10c < ct by our condition > 250, we have made
Finally, after RK drop steps Proposition shows that we have made an exp(- 253
factor progress well. The failure probability comes from union bounding over the at most R(K K a 1) calls to DropOrDescent.
For the runtime bound, by observation all of the parameters f, % c= in Proposition are bounded by a polynomial in r* (11( throughout the algorithm. The correctness of the lower bound on p and the upper bound on ||]]] similarly follow from Proposition 1.
D
26

---

C Computing adaptive reweightings
In this section, we develop an optimization subroutine for solving the subproblems (20) arising in partial matrix completion method. We use approximate Moole framework reduce our optimization to a sequence of linear optimization problems over our constraint set, which we characterize as matching polytope over bipartite graph. We show that for the vector block of our variable, we can cast these linear optimization problems as computing maximum weight bipartite matchings, explained in Appendix C.4. To efficiently implement the matrix block steps, we apply standard tools from the numerical linear algebra and approximation theory literature in Appendix C.3. We now define the problem study in self-contained way.
Throughout this section, we fix a subset
C S(d) and parameters is E RRso e E (0, 1), and define:
k
X' = I E R
max (E(d)
Σ
I2 S
d
(22)
(i)))
S = {S E gaxd gdxd
||||| S 1+ X
In other words, S is the set of "short" (Frohenius-norm bounded) matrices. Further, if x E X' is viewed as symmetric d x d matrix, the constraints on A' enforce that x has bounded row and column sums, Clearly z X = ||=|| S k, so is a subset of an & ball of radius However, we can more specifically capture X as scaled bipartite matching polytope.
Fact 3. Let I C S(d) be identified with d d bipartite graph G (LL R,,,,,, where for (i.5) E [d] x [d], we place an edge from the tt vertex in L (denoted u,) to the jth vertex in V (denoted 0z) if and only if (1, E S(d). Let M be the bipartite matching polytope of G. i.e.
M:= f FER
max R.EL
E
f(N..s)) $
(23)
Then _ = for X in (22), where we map coordinates in I to edges in E in the canonical way.
By the characterization in Fact 3, we efficiently implement iterations our Frank-Wolfe method by calling approximate maximum weight matching algorithm by [22]. We also use the structure of the matching polytope to prove a key regularity property on our objective in Appendix C.2. We finally require the definition of bounded submatrix, whose entries lic in given range.
Definition 5 (Bounded submatrix). Let D gaxd and I C S(d). We say that (D,I) is an (f, u)-bounded submatrix if for all E I, [D],] E u.,
When D and I are clear from context, let 'D be the operator on RI such that
D(w)= = Σ D,
(24)
IEI
With these definitions in hand, our goal in this section is to optimize the following jointly convex function over (x. S) E Z, for an (f, u) bounded submatrix (D, I) and parameters C, E Ryo, named F ftr to denote its decomposition into progress and (approximate) flatness components:
F Ap alan (z, S) (Lz,z) CHI, (slift (D (D()) -s)=
(25)
where v, = D for all & I, and denotes entrywise division.
Note that (25) is exactly the problem in (20), up to reparameterizing to think of the parameter settings for (25) in the context (20), e.g., R S.n t u R f f
o It may be helpful
d k R3 7, where and 7 are the rank and closeness parameter of current iterate.
C.1 Approach based on the Frank-Wolfe method
To efficiently minimize f = Fpmg-ful (defined in (25)) over (defined in (22)) we apply a variant of Frank-Wai Wolfe or conditional gradient methods due to [35]. This method essentially reduces the
27

---

problem to approximately solving minzez (Vg(g), 2) for different values of q E Z. The algorithm given below as Algorithm 4. 10 Below we define the curvature constant, the key quantity which bounds the convergence of the method, as well as the main theorem from [35] which we use.
Algorithm 4: ApproxFrankWoofie(,,D,, ( (Algorithm [35] restated)
Input: Differentiable. convex f IR" + R and compact, convex D C Rd such that the curvature
constant of with respect D is Cy, iteration count 2 1 and approximation tolerance ó Z
2 Compute arbitrary 200) E for t O...., do
700
2
t+2
Compute g()) D such that (VI(=(")), mingeD (VI(=!0), 8) + 6 ((++1) - - )2)) (2 + (())((()
7 end
return (7)
Definition 6 (Curvature constant (restated from [35])). The curvature constant C5.D of convex and differentiable f Rd - IR with respect to compact domain C Rd
2 (..nE,,ye(0.l.... +2 20) 72 (f(2)) f(2o) - 2, -0))
CDD: =
sup
Proposition (Approximate Trank-Wolfe Theorem of [35] restated and specialized), Let f Rd R be convex and differentiable. let D S Rd be compact and convex, and let x² argmingepl (2). For any K 2 1 and ê 2 0, z ApproxFrankWolfe(J: DD, 2,T, (Algorithm 4) satisfies
- ((()))(()")) 2(1 + 10
T
To facilitate applying Proposition to efficiently minimize Forog-far (25) over (22) we provide two general lemmas. The first is Lemma 15 below, which implies that implement Line 5 of Algorithm suffices to compute approximate gradients and and then approximately solve constrained linear optimization problems for these approximate gradients.
Lemma 15 (Gradient approximation), For compact D Rd, 9.9 Rd, and A M 2 0 suppose that
(g g, 8) < A and (g. s)
s M for all E D
If (g. 8) s (1 ai) min (g, s) + A for & and a E [0, 1] then
(g. 8) < min (g. 8) + aM 3A. ZED
Proof. For s* E argmin (g, 8) the assumptions imply that s) = (g. 8) + (0 s) $ (1 + +A+A.
The result then follows
(1 a)) (Ú, = (1 - a)) (g, + - a) (g g,8 S (g.8") + a. A.
The second lemma is the following straightforward upper bound on the curvature constant (that perhaps related to the relationship smoothness given in Lemma 7 of [35]). It shows that to upper bound the curvature constant suffices to upper bound 42 (=) wu, w| for all w, z E
Lemma 16 (Curvature bound). For convex, wiice-differentiable Rdd - R and compact DD C Rd if (=) w] < M for all w, E then the curvature constant f with respect to D is at most 2MM.
We perform minor changes to the names of the variables, choice of offsets, etc. to facilitate and simplify the of [35] to obtain results.
28

---

Proof. Let 2u. 21 2 and y E [0, 1] and define 2, := 20 7(1 20) for all 7 [0, 1]. Note that
-20 L' ( (VI(z), - =0) dt
- - 20) = - (Vf((z), - -
= %/' (V[(=)) V/(z0), 20) dl.
=
Additionally,
(V)(=) V/(20), -20) / {(x)((z 20,21 20|da
sup [==([= 20, 20)
EE
Now, since convex, V f(x) is positive semidefinite for x E D and so
f()]] 20, 21 zo] s fV) 31] +V2 Hol S 2M.
Combining these bounds yields the desired bound of
f(2)) - (Vf(()))())))))))))))))))()))))) - 20) S / 2Mtdt = My².
In the following Appendix C.2 we bound the curvature constant of the particular f prog flat defined in (24) over 2 and provide additional regularity bounds on this f over Z. Then in Appendices C.3 and C.4, we discuss the implementation
single step of Algorithm 5 (specifically, Line by satisfying the conditions needed to apply Lemma 15). To fix some notation, we let 2, == (Iz, S,) be the 4thh iterate of Algorithm 5 (z(1) in the code). We also let
(tslift (D (#) - -s.)
exp
Y,
Trexp slift (D ( (z:) S.)
be the gradient of (slif( S)) before applying the chain rule, see Fact 1. Because of the block-separable structure of slift, we have that
L Odxd
Odxd R²
Y,
Tr(L,) Tr(R,)
(26)
where L, == exp
s.)) R = exp
1 (s.
-D -D
())
23
For notational simplicity, we finally define
B, = L, - R,, T- Tr(L,) + Tr(R,).
We observe that by definition of the objective in (25), we have
C T, B., for all I, Vsf(z)) - B.. T.
C
V [x,() =
Finally, St := (he, H,) denotes the blocks of the approximate gradient computed in iteration and Vt : (w,, We) denotes the blocks of the approximate linear objective optimizer in iteration as suffice for applying Lemma 15. Throughout Appendices C.3 and C.4, we fix a single iteration and drop / from all subscripts, to decrease notational clutter.
C.2 Curvature constants and regularity
Here we bound the curvature constant of Fprog-tlat as defined in (25) over Z defined in (22). To do so, we first provide a bound, Lemma 17, on the operator norm of D(x) defined in (24), for X. The proof follows from previously established fact that the operator norm of any matrix (even if rectangular) upper bounded by the maximum norm of any rows or columns (see egg. Lemma B.4, [19]); however, we directly give self-contained proof for convenience.
29

---

ku Lemma 17. For all x E X' (defined in (22)), we have [DD S
d for DD as defined in (24).
Proof. For all 2 E RR, the Schwarz inequality and the fact that D(x)) is symmetric imply
$
D(z)2
Σ
[D(x))ls
222
Σ 2
p(ollll))
Σ 2]
[ID())la)
1.EE|d
WEll
Σ
2
[D(x)le)
iE|d
JE[d]
Additionally, for all i [d]
since I) is an (l).u)-buuddd submatrix and X.
[D(x)les S ku d
Σ
[P(x)ly)]
Σ
jEld
(i.))t=
Combining shows that |a D(x)=l I
ku
d' || for all Rd and yields the result D(x) is
symmetric.
Lemma 17 improves upon the trivial bound on [1 op for x with ||>=|| k. Note that if x has k on the index corresponding to the largest entry of Dz. then [1 Mlop 2 ku, which substantially larger than J. bound given in Lemma 17. The improved bound for x E X' that we show in Lemma 17 is key to obtaining bounds on the curvature constant of Fpog-Bu fla over 2 which are sufficient for obtaining our desired runtimes (i.e., scaling polynomially only in r", not d). We provide the curvature bound as well as different bounds on the regularity of Prog-fla over 2 below.
ku
Lemma 18. For all 2, 2 E with 2 = (x, S) for x E X and S E S as defined in (22) and for F Frrog.na naa defined in (25).
KVxf(x'), < C ku
C ((2
ku
+ k. (Vsf(22), < 2C, and f(())1))
2
2
(27)
Rd
77 (
Consequently, Cpoane.2 S 20
2 +
ku Pd
Proof. Let 2 Z be arbitrary. Let A be the linear operator such that A S) slift (D (3) -). Let G be the gradient of H; at Az' and let H be the Hessian of H, at Az'. Note that the chain rule, Fact 1, and that the trace and operator norm are dual imply that, for (x,
(V 21 (1z, + C A |- + + | S k CIIA:
C - 1=
= A²) <
1
However, for any (I = XxS.
stlift (D (3) s))| - D (
+1+ + < ku E2d
+ 2,
(28)
op
where the first inequality used the triangle inequality and that the operator norm is bounded by the Frobenius norm, and the second used the range of that E (0, 1), and Lemma 17. Combining these
inequalities yields V f22) 2] < (2 + ku) Applying the same argument with S = 0 and x
0 yields (VxI(=²), . < C 2. + k and (Vs((z'), Sy < 2C. Finally, CF Crpaaan: < 20 (2 + ku
P7
follows from Lemma 16.
30

---

C.3 Matrix step implementation
In this section, we discuss how to approximate the S block of prog-na(()) == prog- (x, S) within the error allowed by Line 5 and Lemma 15, where (as discussed earlier) we denote approximation by
C [B, for T = Tr(L) + TR(), B B T
H Vsf(x, =
following notation in (26). We then give implementation details for computing
W R min (H,
MES
within the error threshold required by Line 5. Our approximately-optimal step matrix W will have the convenient property of coming with explicit low-rank representation, facilitating faster imple- mentation of future iterations of our subproblem solver. We will give approximation guarantees in mixed aultipiccative-addiive format, whose conversion additive error is facilitated by Lemma 15.
The main result of this section is the following.
Lemma 19 (S step). There is an algoritium which takes as input I E X, S E S given as a rank-r factorization, R Z (D(()
llop A [0, C). and a, 8 (0, and computes W 8
rank-q factoriattin satisfying
H) S (1 a jargmin es (W", +
(29)
for H E Saxd with |H V Prog--na (2, S), S for all S' E S,
(30)
with probability 2 1 5. Moreover, y = 0 (2) and the algorithm runs in time
o ( + dr) R log
C
C
d 8
log
A
a
A
Approximating the gradient. We begin by bounding the complexity of matrix-vector access to matrix B x B B L- R. with a given tolerance for approximation error. Ultimately we will use the approximate gradient
C T
H
B
(31)
implement the update S our algorithm. Our access is based on standard polynomial approximation to the exponential which is well-known in the literature.
Lemma 20 ([2)). For a 2 0 and R 2 0, there is polynomial of degree O(R log 2) such that [ex((x) p(z) I a exp(x) for all [[-R, R).
Applying Lemma twice directly yields our approximation B.
Corollary Let x E X, satisfy || (D( S) S R. and let A 2 0. There a matrix B such that, for L == cxp(( (D( ( S)) and R == exp() 2 (S D))))), and defining
T Tr(L) + TrR), B L R.
we have | 1lr S (1
8C YT, as well as
C C B (G-BBS) Aor all all S' e S, Tm (B) =0 ((Z)+
+ml++Tm Tmn (mm(s))) By log C A
Proof. It suffices to provide matrices Σ, R such that
Tax (L) + Tan ( o (LI) Tmv(()) RR log C
< 80
Tr(L),
R R < 8C
Tr(R)..
31

---

Indeed, letting B : R. the bound on Tax (B) is then immediate, and by Hölder's 's inequality (with |S lp || | 2) and the triangle inequality, we also have the desired
B B.
(
T B B-
2C
2C
R-RR
by the definition of T = Tr(L) + Tr(R). We only discuss L, as the case of R is symmetric. We A
let L (D(()) S)). where is the polynomial from Lemma 20 with Tan (L) follows from the degree of p, and the fact that Tan (D( O(IZ). Moreover, letting {Aibeed - [[-R, R be the eigenvalues of 1 (D())) S), we indeed have
sc The bound
L L
Σ
((A))) - exp( S
exp(A.) = SC Tr(L).
8C
iE|d]
VEld
Finally, the claim
|B S (1
+
A YT follows from the triangle inequality. SC
Approximating the S step. We now build upon the access afforded by Corollary 2 to compute
W, our approximate solution minMes (H, M), where Specifically, we use the following standard tool with Lemma 4 to provide our approximate linear optimization implementation over S for any matrix supporting vector multiplication access.
ç B our gradient approximation.
Lemma 21. Let o, E (0,1) and M E 5dxd There is an algorithm which returns E [(1
a) M F (1 + a) [[M]]]] with probability 2 11- 5 in time ( (M)a log d)
Proof. Let Q E IRexd with independently uniform random unit vector rows Rd scaled down by VE for appropriately large k: O(a log 4). By the Liinsoon-inddnstraauss lemma of [20], with probability 2 6, we have for all i [d] that
[MQ 11:112 E (1 a) |M, 11..0.0
12 (1 + a) || 11]
Therefore, summing for all i E [d] proves that Tr(QM = F' satisfies the desired bound. We can compute MQ explicitly in time k (M), and computing the Frobenius norm of MQ E Rdxk does not dominate the stated running time.
Lemma 22. Let ar (0,1), 2 let H E 5dxd have H S T. and let W
argminwes' (W, H). There is an algorithm which with probability 2 returns W ZRZ satisfying R E S9x9 and E Sdxq, with
22 A²
(W, H. < a) (W' H + q
O
(32)
in time
o 0 Tmv H)
1
T2
d
+
log
a
A
Proof. Note that in closed form, we have W -1 + c) H and the optimal objective value is (W*, H) H||p. We first compute F using Lemma 21 such that
|
H F S F
|
within the allotted time and failure probability 1. Then, letting W <- --(1+ +) S, we have
H F
(W', H) (W' H)
HI+
H < ( H)
(33)
2
2 1, 1. and failure probability & We output R == Z W'z and Z, which can be computed within the allotted time. The result follows by combining (33) with
Next, let W + ZZ W'ZZ where Z is the result of Lemma 4 with
37 S
(W, H) (W' H
W
W
H
g ( A.
Here, we used that ['|
IF < implies <
9, 2AT
singular values of W' are larger than 2r 32
32

---

We make one slight extension to Lemma 22 under implicit access to H.
Corollary 3. In the setting of Lemma 22, suppose H = 1 for an unknown constant A. There is an algorithm which returns W ZRZ' with R E S4x9 and Z E Saxq satisfying the guarantee in (32) with probability 2 1 time
o ( (B)
d log
8 )
a² +
A
Proof. We follow the steps of Lemma 22 exactly, except we instead let W +- - F7
B where F
satisfies |[B]|F S F" S (1 + g |B[[. again with probability 2 1 z using Lemma 21. Because the computation in Lemma 21 scale-invariant, the distribution of W remains unchanged from Lemma 22, and all remaining steps are the same as before.
We combine the developments of this section to prove Lemma 19.
Proof of Lemma 19. We define H = B in (31) (using B defined in Corollary 2), and take the step given by Lemma 22 and Corollary 3. Recall from Corollary 2 that || I (1 se) 2C, so we can set t = 2C' in Lemma 22. Moreover, in the context of Corollary 3,
Tm B =
( ((1Z)) ((Z) (IZ)+ dr). RV log A
C
The runtime bound then follows from Corollary 3. Finally, the rank bound follows from (32).
C.4 Vector step implementation
In this section, analogously Appendix C.3, we discuss how to approximate the X block of V f=) with a vector h, and give implementation details for computing
min (h, v).
vEX
We crucially use the characterization in Fact 3, which implies this is weighted matching problem.
The main result of this section is the following.
Lemma 23 (X' step). There is an algorithm which takes as input x E X, S E S given as a rank-r factorization, z 11 (D(() S)op A E [0, C), and a, E (0, 1), and computes y E X satisfying
h) < (1 - a Jargmin er for h E RT with (h - V 2 prog- (x, S),z)) for all x' X,
(34)
(35)
with probability 2 1 - 5. The algorithm runs in time
o ((12 (1Z (r) dr). C2 log 1.5
log
RdkC 4
I
log 1 )
2
Approximating the gradient. Recall that (xf = C (B,E,) for all & E I, where again B L- RR and 7 Tr(L) Tr(R) in Appendix C.3. To produce our approximation h V (x, S), we use the following helper guarantee.
Lemma 24 (Lemma 20, [38]). Let e, E (0, {Athem E Sdxd R 2 log J. and let M gaxd satisfy ||M]| S R. There an algorithm which computes (Vi)ken)) S such that for all
i E [n].
IV: (Ai, exp(M)) <(IAs), exp(MM) + + +
with probability 2 1 - in time
MRlog' 1.5/
Rad dee"
log nd B
Tan (M)
Σ
Tan (Ai)
22
2
(E(xz)
33

---

With Lemma 24 established, our gradient approximation follows straightforwardly.
Corollary 4. Let x E X, S satisfy (D(()
S) R, and let A and 8 (0, 1). We
can compute h E IR in time
o (( (1Z]+ (Inn+Tn((S))
v RR log
RdkkC
2
such that with probability 11-10-10 6, 6,
(1h Vn. (I, S A for all x' E X.
Proof. Define T as in Corollary 2 throughout the proof. We let h E R² satisfy hy = -11 C(V-U.) for all L I, for V.U R² be defined, which we can compute within the allotted time. Since ||a' 1 I k for all E X, it suffices to show that || V= S) I 2
T
To this end, throughout this proof let M == (D( - S), and define
V (exp(M), E,), U. (exp(-NM) M), E.), for all & I.
By our choice of h, we have
C (IV. | V V S)1, V
+ -U,
We take (Vihez to be the approximations given by Lemma 24 with the set of matrices {E, hez and M. 2. and e' +- T we define {U. identically, except we apply Lemma 24 with -M instead of M. Note that these approximations yield
C' ((V. ((V.-V,7 1 U,1) S -
- (c+ (CT())(((E.)) (Trexp(M) Trexp(-M)) T
A
s 20(e+ S
desired. The first inequality used the guarantee in Lemma 24 with Hölder's inequality, and the second used the definition of = Tr) + Trexp(-M) and Tr( = 2. Finally, the runtime follows directly from the bound in Lemma 24.
Approximating the x step. Given our estimate from Corollary 4, our approximate linear opti- mization oracle follows from known result on approximating maximum weighted matchings.
Proposition 5 (Theorem 3.12, [22]). Let G ( R. E) be bipartite graph, let RR be set of weights, and let m := [E]. There is an algorithm which computes f E .,, defined in (23), such that (w, f) < (1 a) minf-eM (w,, f*),, ) in time O m log L.
We remark that Proposition 5 is stated in [3] for maximization linear objectives in nonnegative weight vectors w, i.e. maximum weight matchings. However, it is straightforward implies the same result for minimization of linear objectives in arbitrary cost vectors w E R by first dropping any positive coordinates (which only increase the objective (w,, 2) when is coordinatewise nonnegative), and then negating the result [22]. Because our access to our cost vector of interest is implicit, make simple observation which extends Proposition 5.
that this
Corollary 5. the setting of Proposition 5, let E R20 and suppose w = 1 0 for an unknown constant A > O, and an explicit vector E RR", The guarantees of Proposition 5 hold true for inputs (w, M) if run on imputs (v, G, C M)) instead.
Proof. This follows directly from scale-invariance of the guarantees in Proposition 5.
We now use these developments to give a short proof of Lemma 23.
Proof of Lemma 23. We define h, - + C(V. C(V-U..) entrywise (using notation in Corollary 4), and take the step given by Proposition 5 and Corollary 5. The runtime follows immediately from these results.
D
34

---

C,5 Runtime analysis for subproblem solver
In this section, we put together the pieces and provide a runtime bound for approximately solving (25). We first provide Lemma 25 which provides the bounds for implementing Line 5 for 2 and then use this to provide the main result for approximately solving, (25), Proposition 6.
Lemma 25. There is an algorithm that for input
S) E X x S where S is given as rank-r factorization, R Z (D(() o) A E [0, and 8 (0, 1) outpuis & Z with
(y, W) E EX x where W is output as a rank O (( factorization such that with probability 8.
(V prog Mal (2 (2), 2) S min FF prog aaog-nalee (z, S),
2'EZ
time
o
( (Z)) ( ((ZI+dr) dr)
(RC 2
C
log C
d 3
Rhe C2 log!.
1.3
Rdkk 53
Cku
Cku APd
log
[Z]
k
log
2
APdd
Proof. Applying Lemma 19 and Lemma 23 yields that for any as, ax as.ax
E (0, 1] and á E [0,c]
(which we set later) we can obtain with probability 2 1 (by a union bound) W as rank-y factorization for q 0 C* and H E gaxd satisfying (Lemma 19)
Az
(H. W) & (1 as) min S'ES
SH + A and [H - V. prog fla (z, 2)) A for all e e,
and y E X and h E Rº satisfying (Lemma 23)
(h.v) S (1 ax) min (h, and 1(h- Vx F prog (2, S),2") S Å for all x' e X, x'EX
in time
o (IZ)+ dr)
log (Rylog
RV
C A
C
log
d
v C "og"
1.5
RdkC 64
I
log
2
2
ax
0x
Conditioning on these events and applying Lemma 15 and Lemma 18 yields that (VslFrog-tarzz,, S), w) min (V (VsFprog-taee: (x, x²) as 2C' + 3Δ.
and
(atz
ku pdd +k 33.
Xvx x F Prog- (Ir, S).9) S min (Vx x Fargg-na (x S), + ax S'ES
Picking as 80 ax min( $
(Ic +
Cku 1} and À 24
then yields the result.
Edd
We now prove a more quantitative variant of Proposition 2.
Proposition 6. Let c E [0. C1 and 8 E 1), and suppose [D], E [t, for all E I. There is an
algorithm computing (x. S), an c-approximate minimizer to (5) with probability 2 2 8, in time
o T
C²T (
[
2 .))
C² R 2
log
C
log
dT
+
v R k2 2 log
1.5 R.,dKC
bc
22
CnRu log
Cnn
+0 T
for Roy := 12 +
ku Pd
and T [C'n 1, and S is given as rank-r = O T) factoriattion.
Proof. Throughout the proof let f := Fprog-tat for simplicity. Our algorithm computes (T) 2CvR22 ApproxFrankWVoff((f. Z,T, Cy.2" (Algorithm 4), where note that Cy.2 need not necessarily be computed. By Lemma 18 we know that Cy.2 < RCn and consequently Proposition 4 implies that so long as each iteration of Algorithm is implemented to the desired accuracy.
2C,,z RC <
80 R
f(x(1))
T+2
T+2
+
35

---

(Cr 4). This
To implement the method we apply Lemma 25 with (A, 8) in the lemma set to suffices to have the desired output with the desired probability by union bound.
It remains to bound the computational cost of this algorithm and the rank of the output. Note that T ()( and R. 2 (D=()) - S') for all (a', (') E X x S (by Lemma 17, see e.g.. (28)). Additionally, if we initialize the method with (Da, Odxa) then component of each computed (()) O ( and that each S component of each z04) can be maintained
OnR
that the rank of the S
rank O(t - factorization. The computational cost is then dominated by the cost of each iteration which, by Lemma 25 is bounded as claimed after adjusting by T.
D Postprocessing
In this section, we give the second main component of our overall matrix completion algorithm in Algorithm 7. This piece takes input two matrices M, M E Sdxd which close on submatrix (where we only have noisy semi-random observations from M*). It then performs a sequence of postprocessing steps to produce a matrix M such that M is close to M* on the full matrix, as measured in the foo norm. For the first step of Algorithm we simply reuse our earlier subroutine Sparsify (Algorithm I), whose guarantees we recall here for convenience.
Lemma 13. Let D Sdxd, such that there is A U S [d] with |U S yd, |Daxalls ST. T. Lets E N and p 2 800 log(g) (g). Then with probability 2 1 6, Algorithmm I returns U S U with JU U S 4ryd log d, and Du' xt' has at most entries with magnitudes 2 T per row or column.
In Appendix D.1, we prove structural fact about bounded spanning subsets of low-rank matrices. We use this to analyze our fixing step in Appendices D.2 and D.3, where we use regression problems on a subset of columns passing an appropriate test to complete the matrix.
D.1 Localizing errors via spanning subsets
Before giving our next postprocessing steps, we prove structural property. which can be stated concisely the language of volumetric spanners [5]. Following definitions [7], Lemma 26 shows any n-sized set in Rd admits 2d-approximate f--volumetric spanner of size d + 1.
Lemma 26. Given {Us)eein) C. Rd. there exists S [n] with |S| s d such that for all E [n].
Σ azyj
JES
with coefficients satisfying Ejes lay1 S 2d.
Proof. Consider the largest volume simplex among the [ri)eedd say given by (u) without loss of generality, We claim all the other vectors are contained in the simplex with d + +1 vertices,
Σ vy du;, for all E [d + 1]. jE(++1]
To see this, fix [d + 1], and let the (d 1) dimenssooaal plane spanned by the other points be P. If any other vy lies outside the two planes parallel to P at equal distances, such that one
contains vi, then including "j would produce larger-volume simplex. Taking the intersections of the halfspaces defined by these planes produces the simplex described above. From this, we have the desired property by convexity of the & norm, applied to the coefficients defining this simplex. D
Using Lemma 26, we obtain the following corollary on boundedness of large index subsets.
Lemma 27. Let D E gaxd be rank-r, and assume each row of has at most entries with magnitude r. There exists S C [d] with [d] S (r + 1)s such that [[[]| solss:lles loo. [[[]]ss]] l| 2rt.
Proof. Let T be an SVD of D, and let {ulieea E R" be the rows of U. By Lemma 26, we can find a subset T such that all rows E [d] can be written as
U4 Σ ajuy, with Σ
lasl 2r.
OET
JET
36

---

This also implies every row of D can be written as linear combination of the row vectors j:jheer such that the & norm of the linear combination coefficients
most 2r. Now, let [d] R. where R consists of all indices i E [d] such that [D] jul 2 for some E T, by assumption, |R S (r 11+ giving the size bound. Take some row D; for E [d], and let D.s be the restriction of this row to columns in S. By applying the given linear combination to the rows (D,,s) all entrywise at most 7 in magnitude, the triangle incquality shows Ds,ssloo I 2rt as claimed.
D.2 Testing columns
In this section, we present the second step of our postprocessing algorithm, where we design a test to identify columns with no large errors. This step our structural claim in Lemma 27.
Algorithm 5: (,,
Input: M Raxd j e [d] Φ 2 2.9.8 (0,1)
fmax < [10 31
c c+0
for E [[max] do [d] by including each element independently with probability q if' miniere |M.r -Myl + ø |olloc S 26 then c f- c+
Sample T
7 eend
8 if' c tmax then Return: true
else Return: false
To analyze Algorithm 5, we need the following basic claims which are standard in the literature.
Lemma 28. Let rank-r M Raxk be y-incoherent with k, and let span(MM. Then for all i [d]. [ S 7 1/2 ||=|||-
Proof. Let E Rdxr an orthonormal basis for (M) with rows {ur Jejde so that x Uv with ||=||, ||u||2- The conclusion follows from
|2s| (u,, v)) s ||ulll ||0|12 S V
Pr d |1:1|2-
Lemma 29, Let V C Rd be p-incoherent subspace of dimension and let By E Rdxr be
orthonormal basis for V. Let S C [d] have |S| (1 3pr dd. Then the following properties hold.
For any V, ||ulll2 2 V |1ll2
spans (yyls..)ss). as a subspace of R(S), 3pp-incoherent
Proof. Let A [B Byls: Eies b,b, where (beleetd) are of By. By the definition of incoherence, we have that [[, Allop S Tr(I, - A) = Eiedgys Tr(b.b]) < 3. so that
1 A > I.
3
The lower bound then yields the first statement. Now, the matrix M = [Bv]s:A has orthonormal columns, and the same span as Bv:s:: Furthermore, by incoherence and the fact that A 21 all of the rows i E S of M have
3 B Bv S V
3ur
|M 11
2d
Finally, |S| 2
24 3 (since μ 2 1). Combining these claims proves the second statement.
37

---

We also include the following application of the matrix Bernstein inequality from [43].
Lemma 30 (Lemma 12, [43]). Let E (0,1) 1) and let V C Rd be y-incoherent subspace of
dimension r. Let By be an orthononormal basis for V, with rows (beli C RR. Let S S [d]
have [S] (1 3pr)d )d. Let T S include each element independently with probability p 2
100pr log (2r) Then with probability 2 1-
P 3 Σ
b,b 2
FET
Now, we are ready to analyze our testing algorithm and prove that it has the desired behavior.
Lemma 31. Let M E Sáxd be rank-r" and y-incoherent, and let M E Sdxd be rank-r for r 2 r". For O, assume M - M has at most entries with magnitudes
in each row. Then with probability - 6, if we run Algorithm 5 with parameters q, & and j E [d] such that
1000
log (0).95 20psr** Φ v /qdr'T
92
d
Algorithm 5 has the following behavior
1f - M,yloo S 4r /ur", Algorithm returns true.
. If | - M2 2 10rgdurr Algorithum returns false.
Proof. Let the SVD of M be M = UUE)(U+) We consider the two claims separately.
True case. Suppose that M M,lxx I 4r We will prove that each run of the inner loop of the algorithm succeeds with probability 2 r. By using Lemma 27 with D < M M, and 33m²
applying our upper and lower bounds on there exists S C [d] with |S| 2 (1 1 ) such that for all i S. ||M; M S 4r*T. Next, by Lemma 30 and incoherence of M*, with probability TO
(Vims) T Virns = -I.
This means there exists v E RTSS with ||l||2 S v also means Mirns" My. We thus have for this vector v.
Aur
2nd such that (Virns) Tu = (Vij) T, which
M - Myyla +
|M M + M. Myllso ||ll T ||l||
4. Tur & ||/|
(36)
$ 4r ||u||2 v [T] + 6r Vur s 20rT S 26.
where we used that with probability : [T| S 2qd. By a union bound, each independent test thus increments e with probability 5 over the randomness of T, so a Chernoff bound gives the claim.
False case. Next, suppose that |M M2 /lce 2 10rqdur*, and again consider single run of the algorithm. Let io E [d] be the entry such that |M M 2 10rqdur". First, with probability at least TO over the randomness of the inner loop, for all j' T.
M
M S
(37)
because by assumption, there are at most indices j' where [M:..r - M...''l 2 r. Since qs S 20 there is at least o/ probability that none of these indices selected in T by a Chernoff bound. As
before, with probability TO there is a vector e with ||o||2 S v 2nd such that M = My.- Also,
9.
Jur
again, with probability
9 we have [T] < 2qd. Now let R C [d] be the set of rows i such that
10
M M M.
M M
ST.
38

---

By assumption, each row in T U {j} can only remove indices from R, so
[|| 2 d s( [T] + 1) 2 d - 2qsd z (1
1
d.
10ur
Consider any solution e' to the problem in Line 6 which increments For v' to be feasible, must have || I 2, so ||''ll S T Further,
|M d' M2ylo 2v
(38)
Hence, for all E R.
[ (0- S M Mij (MM), [M ) + [ o' -Ma
(39)
T 0 r 2r qd & 3rgdvr
In the first line, we used that M = Mr by definition. Also, note that M7 - D') in the span of M so by Lemma 29, the fact that [ 2 (1 Tüprr )d, and (39),
V 3
M - 1/)1 S
M Rx 1')1 S Argdvrrd.
Therefore, by incoherence of M Lemma 28 implies that for all i e [d].
[M* krr (v o') S 4rqdur".
(40)
However, consider the index in defined at the beginning of this case. Similarly (39).
M Miel S [M] i of Mioj + | (o.T [M') o/ [M' (e n')
< 2d/ + 2 + 4rqdjur" < 10rqdjrr",
where we used (37), (38), (40), and [T] < 2qd. This contradicts the assumption that
M Mijl 10rgdur*.
We conclude that the problem on Line fails to increment e with probability 2 3 by union bound. Since we repeat the loop 10 (ogo(} ( times, with probability the test will reject, as claimed. O
Remark 2. From observation, the proof of Lemma 31 continues to hold the problem Line 6 is solved up to accuracy 0.1 That is, the true case actually proves a stronger bound of 1.96 in (36), so it would continue pass for any error I 0.1 Similarly, even if assumed the vector in the false case achieved a value of S 2.16 (instead of 2②), we would still have a contradiction.
Finally, we include claim from prior work which bounds the complexity of implementing Line 6.
Lemma 32. Following notation in Lemma 31, for any E (0, 1), assuming O u²² optimization problem on Line 6 can be solved to accuracy 0. 0.1ø with probability 2 6, in time
d log( log(()), the
o (d poly (r* log
Proof. For shorthand let M M. IT, and M, in this proof, and assume that k S 2qd, which occurs with probability 2 1 S. We create linear program,
min ZER Az
where x: T - (u a 3) for a. 8 E R and e E Rd We encode the constraints ||Me ull S a.
||u|l S B using 2d + 2k linear constraints on æ. Finally, we make the objective cT = a + 68. The conclusion follows by applying the solver of [69], Theorem 1, with failure probability 5. since A Our lo)( and we have a O(d + k) x ((k) constraint matrix.
39

---

Algorithm 6: Fi (M) M, T, 7,,00000 0,
Input: Og (M), M E guxd, T S [d], ø 2 0, g. E (0,1)
Sample B T by including each element independently with probability
G 0
4 for b E B do
5 if Te. b, 0, 10d
then G + GU
end
for
j [d] do Sj indices in [d] of observed entries in our call Of (M)
0j f ar / || + |Mssxxu ,s
end
11 vertical concatenation of {0] be(
12
return M M.GV
D.3 Fixing columns via regression
We now complete our postprocessing algorithm. Given estimate M that is entrywise close to M except for small number of potentially large errors in each row and column, we first run Algorithm identify of columns containing no large errors. We then set up regression problems to fix the rest of the matrix (which may initially contain large errors on some entries).
Lemma 33. Let M E Saxd be rank-r" and j--incoherent, and let M = M + N for N E Saxd with || S Let M Saxd be rank-r for r*. For s, T assume [M M has at most 8 entries larger than T in each row and column. Assume
100μr
d
[T|
10pr d
log
20pr2''
d
Then with probability 1 8. if we run Algorithm with parameters q, ó such that
1000
d
log
q
VqdrT,
d
20psr'
then the output satisfies
M
M
10 q (1r))3
Proof. First, by Lemma 27 and applying our upper and lower bounds on q. there a subset T C T with [T'] 2 (1 3 )d such that for all E T', | My S 4rr. Next, by Lemma 31, with 10. we have BOT' S G. Thus, by applying Lemma 30 with S < T' and p <- g, we
probability 1 5
have that with 1 5 My M Also, by Lemma 31, we have with probability 10
10 probability, for any j [d], there is vector u with ||ur||2 S v /pr such that 2qd
5 that
| M.al 10rqdpr.
Now fix a [d] and consider the execution of the loop in Lines 7 to 10 for this index j. Consider My as candidate solution to the optimization problem. We have
Φ Φ gdd 11 + Ms, xau; Ms,3
22 /d T
M Mssxauj
M M2
Mr Ms33
< 2 Vddur 1 + GG| |ull 10rgdur +
100rgd(ur)__,
where we use that with probability, |G| < 2qd. Thus, the solution uy in Line 9 must have
To
[Ms Ms
< 100rgd(ur))-5 Iluslls, s 1.0 Vr.
(41)
40

---

This implies that
Mrs X - M
< Ma Mg,x xX +
Ms - Msys
Mays - MSyJ
< |G] 111y| 10rgdur 1007gd(ur)
- 2500 (pr))....
Next, recall that span(M') is y-incoherent. ( span with rows {b, held- tains subset 5 such that [sy] s 2pd and
Let B E Rdxr have orthonormal columns with By Lemma 30, with probability 10.2. Sj con-
|
Σ TES;
b,b,
=
P I -
I,-
2
4d
Thus, for vectors E span(M*),, ||=||2 S again,
|= 1l.
Using p-incoherennc of span (M*)
1591
MM - M -
M Miile V
pr
4ur
M M33.
|S/1
Misrauu M33.s
V4ur
s of (ur))²,,
where the first line used Lemma 28. Finally, recall from (41) that for ey to be an optimal solution, we must have ||oyll & 100 Vr. Since |G| s 2qd, we have the desired bound for column j E [d]:
| M 1o < [|. Mo loo + || -Myll
|G| ||5 |M. M. (0
df (
Union bounding all of the failure probabilities then completes the proof.
Remark 3. Similarly to Remark 2, note that the proof of Lemma 33 is tolerant to error of rqd(ur)1.5 1.3 for the problem Line 9, because this implies (41) holds up to negligible constant factor, which does not affect correctness of the rest of the proof. Line 9 can again be solved this accuracy in time ((d poly(ur log( ))), with failure probability 8, as described in Lemma 32.
Finally, we put everything together and give our full postprocessing procedure.
Propasition 3. Let M E Sdxd be rank-r* and u-incoherent, and let M M + N for N E Sdxd with [N] xc I A for some A 2 Let Le E Sdxd be given as rank-r decomposition, with r 2 r*. Further, for 7 E (0, suppose M and M are d'-close on s-sumaatrix. Finally, assume
S
10 10tproow log(d)
ifp 2 poly(ur ()) for an appropriate polynomial, Algorithm 7 uses Then for any 8 E (0,1) one call to (M and with probability 2 1 8, outputs M Saxd such that
M M S poly (ur log ( )1))a
(6)
Also, M is given rank- lank-poly(pr) (og())) factorization. The algorithm runs in (ol log( ()) time, where m is the number of observed entries upon calling (M))
41

---

Proof. Let r = 1000Apr log d. By applying Lemma 6, [43], and the assumed bound on there
A' C [d] with [d] A S 300pr log
such that
M [M-MM M M
[M
M Maxaal + S..
Now run Algorithm with
p p 10 log 8 20 log d
d
These satisfy the conditions in Lemma 13, so with probability 10 we obtain S [d] with |S] d(1 30 ). and [M- Mlsxs has entries with magnitude larger than in each or column, implying M Ms has I s entries with magnitude larger than 27 per row or column.
Next, we run Algorithm 6 on the submatrix with rows indexed by S, i.e. we use the observations from Ms: and input Ms:. The subset that is input to Algorithm 6 will be T S, and we 3000 log( ( Note that we have q S - Also by construction, |S| 2 d(1 300 and by Lemma 29, M is 3/1-incoherent. Thus, Lemma 33 yields, with probability 1 To M such that
q
M M'ss: S (f (4r) log? A.
Finally, we transpose the matrix and then run Algorithm 6 again to complete the whole matrix, i.e. with inputs M M and T <- S. Overall, compute rank-poly(1r) log( ( M such that
M M M
S poly (pr log )
A.
Finally, by convexity of norms, symmetrize M (M M and this will only improve the bound. Combining over all the subroutines, the sample complexity and runtime are as claimed, by appropriately applying the linear program solvers described in Lemma 32 and Remark 3. D
We provide pseudocode for the procedure in Proposition Algorithm 7.
Algorithm 7: Postprocess((Pr.. (0.1j (M), (M) M, y, r, ,,,)),
Input:
%%.1 (M) where M M + N E Saxd where M is rank-r" and pu-incoherent and ||]] A. M Saxd given as rank-r factorization such that M. M are -A-close on y-submatrix, (0, 1)
2 S < Sparsify(O 00,1] [M- - M), 10000p0r00 pr 1.5 log d, 300pr log
10 2P, (
5
10
3 p f 100μr log( (4) f 3000ar log(? ( ) 10004 1.5 log
d
M Fix (Ms: (ss). M Ms. S, v VqdrT, 4 10 rank(MV)
log( ()) T+ (0)) (g)A M Fi (M), M S,, Vgdrr, ))
100μer log( ()), q 3000pr
p
Return: ] [M++ M
E Semi-random matrix completion
In this section, finally combine the two main components of algorithm, Algorithm 3 and Algorithm 7, to give our final result, Theorem We begin with a preprocessing step to estimate an initial distance bound, which follows straightforwardly from analogous result in [43].
Lemma 34. There is algorithm, EstimateFrobNorm, which takes imput Og (M) and parameters A and 8 (0, 1) where M M' N where M gaxd is rank-r" and p-incoherent and
42

---

N S A and 2 120pr" log(d/o), EstimateFrobNorm runs in time (m)) where m is the number d
of obseerved entries and outputs an estimate & R such that with probability
|M F S V 10d [I A).
Proof. Let 92 C [d] x [d] be the set of observed entries. Our estimator for V will be
2d Σ (M,l + + (A,))n
Now we analyze this estimator. For each row i E [d]. by Lemma 30, with probability least if we let S; be the set of observed entries in row i,
(M,
(M jEId
JES;
Summing over all rows, we have by the triangle inequality [My] S MyJ + A that
v ž dp M 1
|M
which proves side of the claim. To prove the other direction, by the triangle inequality,
V S v2d
[ F dه) I 10d 10d([ A).
Now, we present the full algorithm for semi-random matrix completion.
Algorithm 8: SRCompletion((",, 00.1) (M,, A,r",
Input:
0f [0 (M) where M M + N E gaxd where M is rank-r" and p-incoherent and [N| A. 8 E 10,
2 M Odxd
200pr" ldg(8/8)
Po
D <- EstimateFrobNorm(000 Ozt (M), 2: A)
P poly (r*,
M4 log (#2)
Q poly(P)
7 p f
A 8 K + [log D1
9 while D 2 AdQ do
(M M SRPartialCompletion (0%.1) (M* + N), M, D"," 10 OK
10
M + Postprocess (Or (M* + N), M, 10 ap: po(l), r-, u1 4K
11
M PCA,. (M)
13
D + 0.1D
14
end
Return: M
Remark 4. In Line 12 of Algorithm 8, PCA,, (.) denotes computing the top-r* PCA of a matrix. We ensure that the input M rank = poly(r* jr,, log( (D) matrix given as low-rank factorization, and then this step can be implemented in time d (rly(r).
Now prove main theorem.
Theorem M Sd'x be rank-r" and p-incoherent, N E Sdxd have [N]] SA and let 8 E (0, 1). Let Q poly(r*,, lo,
di d lle for sufficiently large polynomial. Algorithm 8 can
6A
43

---

be implemented with one call to (M + N) for q and outputs M E Sdxd with rank at most Q (represented in terms of its low-rank factorization) such that with probability 2
M M-M M SQa.
The algorithm runs in time ((mQ) where m is the total number of observed entries.
Proof. We inductively verify the conditions of Corollary are satisfied whenever SRPartialCompletion is called and the conditions of Proposition are satisfied whenever Postprocess is called. The base case for SRPartialCompletion is clear from the guarantees of Lemma 34. Now assuming that the hypotheses of Corollary are satisfied when SRPartialComplltion called, we know the output M has rank I r* po(1) and is 2 l-close to M on a 10 submatrix.
a Now this implies that the hypotheses Proposition are satisfied when we call Postprocess and thus we get that
M M
$ pol) D dP
D 100d
Since M is rank-r*, we have
[M - Mr S PCA, (M) - M S O.1D.
This now implies that the hypotheses Corollary are satisfied the beginning of the next iteration (unless D < AdQ in which case the loop ends). By the way we set K, the loop ends in at most K iterations and thus the overall failure probability is at most 8. As long as none of the subroutines fails, the above argument implies the output must satisfy
M
M
SQQ
and that M has rank most Q. Note that by Lemma 2, we can simulate all of the observations used the algorithm with a single sample Orr (M* + N) with reveal probability
poly (r* H4, log
ddIM LE) 6A
The overall runtime guarantee follows by combining the runtime guarantees of Corollary 1, Proposi- tion 3, and the PCA step (see Remark 4).
44

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: As stated in the abstract and introduction, this is a theory paper where we give new algorithm for semi-random matrix completion and prove that it achieves improved guarantees in terms of runtime, accuracy and noise tolerance.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the modeling assumptions and acknowledge that since this is theory paper, the modeling assumptions and runtimes of the algorithms may not be practical yet (as mentioned in Section 1.3), but hope that the insights are useful and may have practical implications in the future.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
45

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper (and supplementary material) includes complete proofs of all of the claims.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
46

---

(a) If the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which authors are welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr hobpll/c/uuddss/dddssttssssssoop
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.co. cct wwtpcccppppppcct.ccc.ccccccccclt weeiii/ggiies//eee
/tteg/gggddeeeoeeuuumbiii htth://ooeeSbbmeeeeeee wwtsSSuumiiiioo. www.nsoollleeeeeeeeooeooeoeeoeee for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
47

---

The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
48

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httprppsss.pppp..cc/cccceeiiiiia
Question:
Answer: [Yes]
Justification:
We read the ethics guidelines and believe we meet them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Our paper is about theoretical results and therefore substantial societal impact would likely come only with further research and work. However, we do discuss how our paper is motivated by algorithms more robust and less sensitive to distributional assumptions. In this sense, our paper seems to be providing potential helpful tool; positive negative societal impacts of this tool would likely come from future work applying our result.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: The paper does not release data models.
49

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
50

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
51


Reviews:
[{"review_id": "ojnl3mqHrL", "reviewer": "Reviewer_kK6Q", "summary": "In this paper, the authors study semirandom matrix completion. In their models, entry $ij$ of a $\\mu$-incoherent, symmetric ground truth rank-$r$ matrix $M^{\\star} \\in \\mathbb{R}^{d \\times d}$ are revealed independently with probability $p_{ij}$, where $1 \\ge p_{ij} \\ge p$ for some parameter $p$ that is a function of $r$ and $d$. The assumption that $M^{\\star}$ is symmetric is not important, as we can reduce the asymmetric setting to the symmetric one with minimal overhead.\n\nAn important feature of this model is that the entry reveal probabilities are allowed to vary. This contrasts against standard assumptions in the matrix completion literature which typically stipulate that the entries are revealed i.i.d with probability $p$. Although revealing more entries of the matrix may seem to help the learning algorithm learn the underlying matrix, many algorithms fail under this helpful adversary. This is evidence that these algorithms have overfit to a statistical assumption implicit in the problem statement.\n\nA prior work [CG18] studied this problem and gave some recovery guarantees based on a global reweighting scheme for the matrix, but this algorithm has certain undesirable properties -- it is not a high-accuracy algorithm, it is not robust to outliers, and it has a dependence on the conditioning of the matrix. The present work addresses all of these issues and gives a nearly linear time algorithm that achieves an $\\ell_{\\infty}$ recovery guarantee.\n\nThe main technical contribution builds off of a prior work concerning semirandom sparse recovery [KLLST23]. In particular, the algorithm tries to find a progress direction in each step that can be written as the sum of a \"short\" matrix (one that has small Frobenius norm) and a \"flat\" matrix (one that has low spectral norm). This is chosen by a combination of dropping heavy rows/columns of $M$ that witness a large  Frobenius error in the current iteration along with a fast reweighting algorithm that finds a candidate descent direction that admits the short-flat decomposition. The fast reweighting algorithm itself is a Frank-Wolfe type algorithm over a set of valid reweightings and short matrices. The runtime arising from this subproblem follows from observing that the set of valid reweightings is in fact a rescaled bipartite matching polytope, which means fast matching algorithms can be called as a black box, and implementing a separate algorithm to optimizer linear functions over the set of short matrices.\n\n* [CG18] Non-Convex Matrix Completion Against a Semi-Random Adversary (https://arxiv.org/abs/1803.10846)\n\n* [KLLST23] Semi-Random Sparse Recovery in Nearly-Linear Time (https://arxiv.org/abs/2203.04002)", "questions": "What are the challenges, if any, to extending the results to an adaptive adversary? For example, consider an adversary that perhaps samples several entries of $M$ with probability $p$, then upon seeing the sampled entries, reveals an extra arbitrary set of their choice? I ask these because it seems suggested that the algorithm you presented actually does work in such a settings (lines 54-62), but I don't see something in Definition 2 to this effect.", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper constitutes an important step towards understanding algorithms that don't implicitly overfit to statistical assumptions present in the model. In practice, one probably shouldn't assume that entries are revealed i.i.d with distribution Bernoulli(p). The model studied in this paper (Definition 2) is much more realistic than the i.i.d random entry model.\n\nFurthermore, the improvements in this work over the previous state of the art, [CG18], are quite strong. In particular, the authors get a condition-free, high-accuracy recovery guarantee in $\\ell_{\\infty}$. Furthermore, the algorithm runs in nearly linear time in the number of revealed entries.\n\nThe paper is very well written and the main ideas are clearly presented. The algorithmic ideas will be very interesting to anyone in the algorithmic statistics and convex optimization communities.", "weaknesses": "The rank of the matrix that's output can be $poly(r)$ than the ground truth. Since this paper seems mostly concerned with $r \\ll d$ and independent of $d$, this is morally not a big deal. Also, what is the polynomial? I did some very cursory searching but didn't find it explicitly written down (all I see is that it's bigger than $r^6$).\n\nThe error depends on the largest entry of the noise -- this might be a bit pessimistic (e.g. if the noise matrix has just one nonzero entry, but the corresponding index isn't revealed to the learner, then this shouldn't affect anything). The authors explicitly mention getting a more \"optimistic\" dependence on the noise as an interesting open direction for future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review and kind comments. We appreciate that you found our paper well-written and its ideas of general interest.\n\nThe 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.\n\nWe 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. \n\nThe 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. \n\nThe 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.", "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": "", "extra_scores": {}}, {"review_id": "IPtOzaGkzl", "reviewer": "Reviewer_orB2", "summary": "This paper consider semi-random matrix completion via flow-based adaptive reweighting. \nThe main result is the first high-accuracy nearly-linear time algorithm for solving semi-random matrix completion, and an extension to the  noisy observation setting.\n\nI am not familiar with the area of matrix completion.", "questions": "NO", "limitations": "NO", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "No", "weaknesses": "NO", "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": "", "extra_scores": {}}, {"review_id": "DTFHDCzhyG", "reviewer": "Reviewer_JbFK", "summary": "This paper considers the semi-random matrix completion problem. Given an unknown rank-r matrix M, each entry of the matrix Is observed independently with a probability  p_{ij} at least p.  The goal is to find a matrix close the matrix M. \n\nThe sap-based algorithm can achieve the nearly-optimal sample complexity, but is not fast compared to iterative method. The previous work shows an iterative method which has a sample complexity and runtime has a polynomial dependence on epsilon.\n\nThis paper provides a fast iterative method that achieves the sample complexity and runtime with polylogrithmic dependence on the accuracy epsilon. It has no dependence on the condition number and can also handle noise in observations.", "questions": "-", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 This paper provides a clear motivation to consider the semi-random matrix completion problem and clearly explains the limitations of previous methods. \n2 This paper provides an interesting fast iterative method for this problem and shows that it achieves improved sample complexity and runtime.\n3 This paper utilizes the techniques by Kelner, Li, Liu, Sidford, and Tian and make interesting modifications based on new sights on this semi-random problem.", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your reviewing efforts. We appreciate that you found our insights interesting and our exposition clear.", "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": "", "extra_scores": {}}, {"review_id": "lnFcXQORST", "reviewer": "Reviewer_cp6D", "summary": "This paper proposes an algorithm that is able to achieve high-accuracy in semi-random matrix completion with nearly linear time.  The key innovation lies in using a flow-based adaptive reweighting scheme to mitigate the bias introduced by the adversary. This technique effectively identifies and downweights the potentially misleading entries, allowing for accurate recovery of the underlying low-rank matrix. The authors provide theoretical guarantees for their algorithm, demonstrating its ability to achieve near-optimal sample complexity.", "questions": "Could you provide more details on the practical implementation of your algorithm? Specifically, how does it handle very large datasets in terms of memory usage and computational overhead?", "limitations": "See weakness", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a unique flow-based reweighting strategy specifically designed to handle the challenges posed by the semi-random adversary. This approach effectively leverages the underlying structure of the problem to identify and mitigate the adversary's influence.\n2. The theoretical analysis demonstrates that the proposed algorithm achieves near-optimal sample complexity, meaning it requires a near-minimal number of observed entries to accurately recover the underlying matrix. \n3. The flow-based reweighting scheme is flexible and can be adapted to different variations of the semi-random model with considerations of the noise. This adaptability makes the approach potentially applicable to a wider range of practical scenarios.\n4. The paper provides a clear presentation of the problem, the proposed algorithm, and its theoretical analysis. The technical details are presented rigorously, making the contributions easy to understand and evaluate.", "weaknesses": "1. While it outlines the general approach, it lacks concrete pseudocode or even finished code, making it difficult for readers to fully grasp the implementation details. \n2. Unlike the work of Kelner et al 2022, the paper only considers a specific type of semi-random adversary. Exploring how the method performs against different adversarial models, including more powerful adversaries that can manipulate the values of the observed entries, would strengthen the contributions.\n3. The paper's claim of near-linear time complexity is not sufficiently substantiated and demonstrated in empirical setting. The authors does not provide a detailed analysis of the polynomial factors involved in the runtime. This makes it difficult to compare its efficiency to existing methods with the similar magnitude. Furthermore, the absence of empirical validation leaves it unclear how much practical improvement the algorithm actually achieves in real-world settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\nRe: 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.\n\nWe 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.\n\nWe hope this discussion elevates our paper in your view; thank you for your detailed feedback.", "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": "", "extra_scores": {}}, {"review_id": "kffVBEfcEY", "reviewer": "Reviewer_RnDV", "summary": "This paper presents a new algorithm for matrix completion in the semi-random setting, where each entry is revealed independently with a probability at least $p = \\frac{\\mathrm{poly}(r, \\mu, \\log d)}{d}$. The paper provides a promising approach for designing fast matrix completion algorithms that are robust to semi-random sampling, which is argued to be a more realistic model than uniform sampling in practice. The insights may enable future work on more practical algorithms for semi-random matrix completion.", "questions": "1. One of the main motivations of this paper is to consider the matrix completion problem under the semi-random setting, which is a more realistic setting than uniformly random. Meanwhile, the paper mentions, “both our dependence and the dependence of [16] are somewhat large at the moment, limiting immediate practical deployment”. I understand the difficulties of making theoretical breakthroughs, but since this paper is motivated by the practical setting, I want to ask, how much work is still needed before the practical deployment.\n\n2. A minor comment: Each definition, theorem, and proposition should be more self-contained. There are some notations in these blocks that should be more explicitly defined.", "limitations": "As mentioned by the authors, the main limitation is “the modeling assumptions and runtimes of the algorithms may not be practical yet”. Other than that, I do not find obvious limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides the first high-accuracy and noise-tolerant nearly-linear time algorithm for matrix completion in the semi-random setting, improving upon previous work in terms of accuracy, condition number dependence, and noise handling. \n\n2. The iterative method based on local reweighting and adaptive subproblems is a novel approach that enables the improved guarantees. Using flow algorithms for the reweighting subproblems is a key technical innovation. \n\n3. The polylogarithmic dependence on the target accuracy $\\epsilon$ and lack of dependence on condition number are significant improvements over previous nearly-linear time algorithms.", "weaknesses": "1. While the paper provides a promising theoretical foundation, the polynomial factors in the sample complexity and runtime may still be too high for immediate practical deployment, as acknowledged by the authors. Further work may be needed to obtain more practical parameter dependencies. \n\n2. This paper does not sufficiently discuss how it fits into the broader field of matrix completion algorithms with practical implementation. For example, [1] considers the matrix completion problem via robust alternating minimization, which can tolerate errors caused by approximate updates. Both papers consider the practical implementation of the matrix completion algorithm. What are some similarities and differences between these two (or some other related) matrix completion papers? \n\n3. The paper focuses on the theoretical algorithm and analysis but does not include empirical evaluation of real-world datasets. Experimental validation of the robustness and efficiency benefits would strengthen the claims.\n\n[1] Yuzhou Gu, Zhao Song, Junze Yin, and Lichen Zhang. “Low rank matrix completion via robust alternating minimization in nearly linear time.” ICLR 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n\nIn 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.\n \nThe 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.\n\nWe 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.\n\nNeither 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).  \n\nWe 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.\n\nWe hope this discussion elevates our paper in your view; thanks for all your detailed feedback.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all of the reviewers for their reviewing efforts and feedback.

Several reviewers, e.g., cp6D and RnDV, asked us to address our method’s practicality. We acknowledge that our work’s primary contribution is theoretical. However, we note that previous practical matrix completion algorithms (e.g., alternating minimization and other gradient methods) both (1) encountered conceptual barriers towards generalizing to the semi-random model (due to their reliance on independent observation probabilities), and (2) often failed to work reliably on practical instances, as referenced in Lines 42-45. We believe the fact that our new, near-linear time, approach provably succeeds in this challenging model is an exciting and promising proof-of-concept that could facilitate future empirical research. We emphasize that no previous algorithm achieved a comparable result to Theorem 1.

We acknowledge that we have not implemented our algorithm yet, and that there are several natural avenues for significantly improving its complexity, which could make it more practical. We view our work as an important first step towards developing practical algorithms for matrix completion that are robust to these types of real-world noise, and we believe that our work could enable future research in this important direction.

Meta-review: This paper presents the first high-accuracy nearly-linear time algorithm for solving semi-random matrix completion. The majority of reviewers agree that the semi-random setting is more realistic than the fully-random setting and thus this paper is well-motivated. Though there are concerns about practicality, the general consensus seems to appreciate the depth of the theoretical contributions of the paper.

To ensure the work has a stronger impact, I would encourage the authors incorporate the initial reviewer feedback, e.g., suggestions about self-contained nature of theorem/lemma statements to improve the overall clarity/presentation.
Decision: Accept (poster)