<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting</title></titleStmt>
			<publicationStmt>
				<publisher>NeurIPS 2024 https://openreview.net/forum?id=XZp1uP0hh2</publisher>
				<date>11/06/2024</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10631093</idno>
					<idno type="doi"></idno>
					
					<author>Jonathan Kelner</author><author>J Li</author><author>Allen Liu</author><author>Aaron Sidford</author><author>Kevin Tian</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[We consider the well-studied problem of completing a rank-, -incoherent matrix  from incomplete observations. We focus on this problem in the semi-random setting where each entry is independently revealed with probability at least  . Whereas multiple nearly-linear time algorithms have been established in the more specialized fully-random setting where each entry is revealed with probablity exactly , 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]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>How can we ensure learning algorithms do not overfit to generative assumptions on their input data? Since worst-case statistical inference problems are often intractable (i.e., without distributional assumptions), to 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.</p><p>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 a symmetric rank-r matrix M &#8712; R d&#215;d where r &#8810; d, 6 given a small (typically sublinear) number of entries revealed independently and at random. In a seminal line of work <ref type="bibr">[13,</ref><ref type="bibr">11,</ref><ref type="bibr">12,</ref><ref type="bibr">61]</ref>, it was shown that under natural structural assumptions on M, one can fully recover M given &#8776; 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 a more detailed and nuanced discussion), this has resulted in two categories of matrix completion algorithms.</p><p>&#8226; SDP-based algorithms achieve the nearly-optimal sample complexity, but are based on solving SDPs, which requires time &#8486;(d 3.5 ) even with state of the art solvers <ref type="bibr">[39,</ref><ref type="bibr">34]</ref>.</p><p>&#8226; First-order iterative methods require a slightly higher sample complexity, namely, they require m &#8776; pd 2 revealed entries for an observation probability p = &#8486;(poly(r, log d)) &#8226; 1 d . However,</p><p>The main result of <ref type="bibr">[17]</ref> is an efficient algorithm for semi-random matrix completion, albeit with some important caveats, as we discuss shortly. Roughly speaking, for &#1013; &#8712; (0, 1), <ref type="bibr">[17]</ref> gave an algorithm which, given observations of rank-r M with condition number &#954; from the p-semi-random model for p = 1 d &#8226; O(poly(r, &#954;, 1 &#1013; )), outputs M &#8242; so that &#8741;M &#8242; -M&#8741; 2 F &#8804; &#1013;&#8741;M&#8741; 2 F with high probability. Moreover, it runs in nearly-linear time O(m &#8226; poly(r, &#954;, 1 &#1013; )), 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.</p><p>&#8226; High-accuracy recovery. Both the sample complexity and runtime of the algorithm in <ref type="bibr">[17]</ref> depend polynomially on &#1013; -1 . In particular, the algorithm cannot recover the matrix M to &#1013; -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, <ref type="bibr">[17]</ref> cannot achieve exact 7 Here, and throughout the paper, we use the notation O(f ) := O(f log O(1) f ) and similarly define &#8486;. 8 As clarified in Definition 2, it is important in this equivalence that the additionally revealed entries are not adaptively chosen, i.e., do not depend on which random entries were observed. This manifests in our analysis because an adaptive adversary causes significant difficulties with independent sample splitting (see <ref type="bibr">Lemma 2)</ref>. 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 <ref type="bibr">[61]</ref>); extending to an adaptive adversary is a 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).</p><p>&#8226; Condition number dependence. Another important downside of the <ref type="bibr">[17]</ref> algorithm's guarantee is its polynomial dependences on &#954; in both the sample complexity and runtime. No dependence on &#954; is required information-theoretically, or by the SDP-based methods. This aspect also seems somewhat inherent to the non-convex iterative method used in <ref type="bibr">[17]</ref>.</p><p>&#8226; Noise tolerance. Finally, the guarantees in <ref type="bibr">[17]</ref> require that M is exactly low-rank, i.e. it does not generalize to 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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.1">Our results</head><p>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.</p><p>Theorem 1 (informal, see <ref type="bibr">Theorem 2)</ref>. Let M &#8902; &#8712; R d&#215;d be a symmetric, rank-r, &#181;-incoherent matrix, let symmetric N &#8712; R d&#215;d satisfy &#8741;N&#8741; &#8734; &#8804; &#8710;, and let M = M &#8902; + N. Let &#1013; &#8712; (0, 1). There is an algorithm that takes observations from M in the p-semi-random model for p = Q d , where Q = poly(r, &#181;, log( d &#1013; )), and outputs M as a rank-Q factorization such that with high probability,</p><p>The algorithm runs in nearly-linear time O(mQ) where m is the number of revealed entries.</p><p>Here, &#8741;&#8226;&#8741; &#8734; refers to the elementwise &#8467; &#8734; norm of a matrix, and &#8741;&#8226;&#8741; F refers to the Frobenius norm. We pause to comment on Theorem 2. First, in the noiseless setting, i.e., when &#8710; = 0, our algorithm has a polylogarithmic dependence on &#1013; -1 , and thus achieves high-accuracy recovery in nearly-linear time.</p><p>In particular, as long as the bit complexity of the underlying matrix is polynomially bounded, we achieve exact recovery in nearly-linear time. Moreover, our rate has no dependence on the condition number &#954;. In both of these aspects, our result qualitatively improves upon <ref type="bibr">[17]</ref>, while retaining a nearly-linear runtime and O(d &#8226; poly(r)) sample complexity. We also remark that the incoherence assumption in Theorem 2 (or a less standard variant thereof), which is formally defined in Definition 1, is used in all low-rank matrix completion algorithms we are aware of, as the problem is intractable without subspace regularity assumptions (see, e.g., discussion in <ref type="bibr">[43]</ref>).</p><p>Finally, we observe that our guarantee applies to the noisy setting, i.e., &#8710; &gt; 0. To our knowledge, this is the first such guarantee in the literature for semi-random matrix completion, even for SDP-based methods. We achieve guarantees in terms of the &#8467; &#8734; norm of the noise matrix N; moreover, the overhead is a polynomial of only r log( d &#1013; ), a preferable guarantee to the poly(d) overheads known to be achievable in the standard, fully random setting by semidefinite programming <ref type="bibr">[11]</ref>.</p><p>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 <ref type="bibr">[11,</ref><ref type="bibr">43]</ref>. However, in the semi-random setting, some measure of the "element-wise" noise level is unavoidable, because the semi-random noise could be chosen to 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 <ref type="bibr">[42]</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.2">Our techniques</head><p>We achieve these results via a fundamentally different approach than the prior work of <ref type="bibr">[17]</ref>, detailed in Section 2. At a (very) high level, <ref type="bibr">[17]</ref> 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, <ref type="bibr">[17]</ref> then shows that a non-convex optimization method will recover the true matrix, with high probability. While this is a very natural approach, this also directly results in a poly( 1 &#1013; ) dependence in the runtime and sample complexity of the algorithm. This is because the quality of the spectral approximation directly goes into the final accuracy of their overall algorithm; ultimately, they need a (1 + &#1013;)-multiplicative spectral approximation to the ground truth. However, all known techniques for finding such a high-quality spectral approximation require a poly( 1 &#1013; ) dependence in both sample complexity and runtime.</p><p>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.</p><p>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 + &#1013;)-multiplicative approximation at every step, we only need a constant multiplicative approximation to make progress. This is the main insight which allows us to achieve polylogarithmic rates in 1 &#1013; . Our algorithm builds upon the short-flat decomposition-based approach to designing iterative methods for linear inverse problems introduced in <ref type="bibr">[42]</ref>, and specialized in <ref type="bibr">[43]</ref> to matrix completion in the standard setting. However, there are significant technical challenges in adapting this framework to semi-random models. At a high level, the matrix completion problem is not well-conditioned, so a crucial step in the <ref type="bibr">[43]</ref> 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.</p><p>Unfortunately, all of these steps crucially rely on independent sampling and hence break in the presence of semi-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: it either finds an adaptive reweighting which accurately estimates the difference on a large submatrix after denoising, or certifies that a few rows and columns are responsible for much of the difference and hence can be dropped. To achieve our nearly-linear runtime, we crucially exploit graphical structure of feasible reweightings present in the randomly-revealed entries, and use flow-based optimization algorithms to solve our reweighting subproblem.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.3">Related work</head><p>Here, we review related work on matrix completion and semi-random models. These lines of research are vast and we focus on the research most relevant to our setting. For a more comprehensive review, we refer the interested reader to surveys on these topics, e.g., <ref type="bibr">[41,</ref><ref type="bibr">60,</ref><ref type="bibr">59,</ref><ref type="bibr">63]</ref>. <ref type="bibr">[62]</ref> in the context of collaborative filtering, e.g., for the Netflix Prize <ref type="bibr">[6]</ref>. Since then, it has found applications in various areas, such as signal processing <ref type="bibr">[46,</ref><ref type="bibr">64,</ref><ref type="bibr">57]</ref>, social network analysis <ref type="bibr">[47]</ref>, causal inference <ref type="bibr">[4]</ref>, and most recently, AI alignment <ref type="bibr">[1]</ref>. In a seminal line of work, <ref type="bibr">[13,</ref><ref type="bibr">11,</ref><ref type="bibr">61,</ref><ref type="bibr">12,</ref><ref type="bibr">16]</ref> 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., <ref type="bibr">[44,</ref><ref type="bibr">31,</ref><ref type="bibr">32,</ref><ref type="bibr">33,</ref><ref type="bibr">36,</ref><ref type="bibr">74,</ref><ref type="bibr">67,</ref><ref type="bibr">18,</ref><ref type="bibr">72,</ref><ref type="bibr">30]</ref>. 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-based methods for matrix completion <ref type="bibr">[65,</ref><ref type="bibr">21,</ref><ref type="bibr">28,</ref><ref type="bibr">40,</ref><ref type="bibr">73,</ref><ref type="bibr">40,</ref><ref type="bibr">73,</ref><ref type="bibr">71]</ref>. In terms of theoretical runtimes, the state of the art O(dr 3+o (1) ), is given in <ref type="bibr">[43]</ref>. While some of the aforementioned papers have implementations, comprehensively evaluating the practical performance of all of these methods is an interesting direction for future work. As noted in <ref type="bibr">[17]</ref>, none of these fast methods are known to succeed in the presence of semi-random noise.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Matrix completion. Matrix completion was first introduced in</head><p>Semi-random models. Semi-random models were first introduced in a pair of seminal papers <ref type="bibr">[9,</ref><ref type="bibr">24]</ref>, 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 on semi-random models focused on understanding semi-random variants of various constraint satisfaction problems, see e.g. <ref type="bibr">[25,</ref><ref type="bibr">24,</ref><ref type="bibr">45,</ref><ref type="bibr">15,</ref><ref type="bibr">48,</ref><ref type="bibr">50]</ref>. More recently, they have also been studied in the context of learning theory, in the context of clustering problems <ref type="bibr">[23,</ref><ref type="bibr">53,</ref><ref type="bibr">49,</ref><ref type="bibr">14,</ref><ref type="bibr">29,</ref><ref type="bibr">51,</ref><ref type="bibr">52,</ref><ref type="bibr">55]</ref>, sparse and overcomplete linear regression <ref type="bibr">[37,</ref><ref type="bibr">42]</ref>, planted clique <ref type="bibr">[54,</ref><ref type="bibr">10]</ref>, and more <ref type="bibr">[27,</ref><ref type="bibr">8]</ref>.</p><p>Of particular interest to us is the recent line of work on developing fast learning algorithms in semi-random models <ref type="bibr">[17,</ref><ref type="bibr">42,</ref><ref type="bibr">43,</ref><ref type="bibr">27,</ref><ref type="bibr">8]</ref>. The closest and most direct comparison to our work is the aforementioned <ref type="bibr">[17]</ref>, which we quantitatively improve upon in a number of ways. It is worth noting that the specific poly(r) &#8776; r 6 dependence in the sample complexity of <ref type="bibr">[17]</ref> 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 <ref type="bibr">[17]</ref> 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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Technical overview</head><p>At a high level, our algorithm follows the paradigm in <ref type="bibr">[42]</ref> 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 a 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.</p><p>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 &#8712; R d&#215;d and let the ground truth be M &#8902; &#8712; R d&#215;d , assume both matrices have rank at most r, and focus on the noiseless setting N = 0 d&#215;d for simplicity. We also assume for normalization purposes that &#8741;M -M &#8902; &#8741; F = 1, and our goal is to take a step M &#8242; &#8592; M + D so that</p><p>Our conditions are inspired by the approach in <ref type="bibr">[43]</ref>, which gives improved iterative algorithms for standard matrix completion (without semi-random noise). Let p be the minimum observation probability, let &#8486; be the set of observed entries from M &#8902; , and let &#8486; &#8902; 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 &#8486; &#8902; &#8838; &#8486; always). Inspired by a similar framework in the sparse recovery setting <ref type="bibr">[42]</ref>, the key certificate for guaranteeing progress of the form (1) in <ref type="bibr">[43]</ref> is that of a short-flat decomposition. We say a candidate step D has a short-flat decomposition if we can write D = S + F where &#8741;S&#8741; F &#8804; 1 and &#8741;F&#8741; op &#8804; cr -1 2 for a small constant c: here we think of S as the "short" part and F as the "flat" part of the decomposition. If we can further ensure that enough signal is captured, i.e., &#10216;D, M &#8902; -M&#10217; &#8805; 1 -c, then <ref type="bibr">[42,</ref><ref type="bibr">43]</ref> give a short argument based on H&#246;lder's inequality that a step in D, combined with a low-rank projection for denoising, will imply <ref type="bibr">(1)</ref>. Thus, it suffices to find a matrix D that has these properties; for intuition, we would ideally like to take D = S = M &#8902; -M and F = 0 d&#215;d , which would complete the matrix in one shot. Naturally, however, we are limited by the fact that D should be supported on the observations &#8486;, as otherwise we cannot make any guarantees on &#10216;D, M &#8902; -M&#10217;. Na&#239;vely, one would hope to simply take the empirical observations D = 1 p [M -M &#8902; ] &#8486; &#8902; (which zeroes entries outside &#8486; &#8902; ), an unbiased estimator of M &#8902; -M, and appeal to matrix concentration arguments to show existence of a short-flat decomposition. Unfortunately, this is not the case, as entries, rows, or columns of M &#8902; -M which are too large can arbitrarily hinder matrix concentration bounds, and <ref type="bibr">[43]</ref> gives simple examples showing this dependence on the imbalance is unavoidable for uniform reweightings.</p><p>However, <ref type="bibr">[43]</ref> made the important insight that when matrix concentration fails, it must be that M -M &#8902; is overly concentrated on a few heavy rows and columns, and hence dropping a few rows and columns significantly reduces &#8741;M -M &#8902; &#8741; F . These rows and columns can later be recovered using the low-rank assumption, once enough progress has been made. The algorithm in <ref type="bibr">[43]</ref> then works by repeatedly estimating heavy rows and columns, explicitly dropping them to form a set S &#8838; [d] of balanced indices, and then taking the step</p><p>. This necessity of dropping certain poorly-behaved indices is a crucial difference between the matrix completion setting and simpler semi-random inverse problems such as sparse linear regression <ref type="bibr">[42]</ref>, which possess stronger global regularity features such as the restricted isometry property (RIP).</p><p>Certifying progress in semi-random models. In the semi-random matrix completion problem, we need several modifications to the strategies of <ref type="bibr">[42,</ref><ref type="bibr">43]</ref>, to handle the interplay between estimating heavy indices and making certifiable progress. Firstly, we cannot accurately estimate the &#8467; 2 norm of rows and columns of the true difference matrix M -M &#8902; from observations, because the semi-random adversary can drastically distort our estimates. However, we show in Algorithm 1 that we can use the &#8467; &#8734; norm of observed entries as a proxy for heaviness. <ref type="foot">9</ref> Specifically, after dropping rows and columns 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.</p><p>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 &#8486; &#8902; are unknown. Instead, we use &#8486; &#8902; existentially to set up a convex program over reweightings w &#8712; R &#8486; , to search for a candidate step D :=</p><p>Roughly, our convex program aims to find w satisfying the following constraints (see Lemma 7 for a formal statement).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">For all</head><p>2. There exists S, F &#8712; R d&#215;d with D = S + F, &#8741;S&#8741; F &#8804; 1, and &#8741;F&#8741; op = O(r -1 2 ).</p><p>3. For a sufficiently small constant c, &#10216;D, M -</p><p>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 <ref type="bibr">[42,</ref><ref type="bibr">43]</ref>. It is straightforward to see that the ideal candidate</p><p>we mentioned earlier is feasible for these constraints, and we show in Lemma 7 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).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Flow-based adaptive reweighting.</head><p>A key technical contribution of this work is a nearly-linear time algorithm finding a reweighting D(w) := (i,j)&#8712;&#8486; w ij [M -M &#8902; ] ij that meets our progress criteria. Due to our focus on fast algorithms, we require this step to run in O(|&#8486;| &#8226; poly(r)) time. Our strategy is to form a joint objective over w obeying Item 1, and &#8741;S&#8741; F &#8804; 1, of the form</p><p>Here, the parameter C is used to trade off the progress objective &#10216;D(w), M -M &#8902; &#10217; (giving Item 3) and the flatness objective smax(D(w) -S) (giving Item 2), where smax(M) = log Tr exp(M) is a smooth approximation to the operator norm. That is, letting Z := W &#215; S be the product space between w &#8712; R &#8486; satisfying Item 1 and short matrices S &#8712; R d&#215;d , we show that finding (w, S) &#8712; Z with low suboptimality error in F prog-flat is enough to make progress through Lemma 7.</p><p>We optimize (2) by carefully applying a Frank-Wolfe method due to <ref type="bibr">[35]</ref>. While na&#239;ve Frank-Wolfe analysis requires global smoothness of the objective, this provably does not hold for our F prog-flat (at least, with a smoothness bound of &#8776; poly(r) required for nearly-linear time algorithms). However, we leverage that the analysis in <ref type="bibr">[35]</ref> 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 to show that F prog-flat is smooth in a restricted set of directions within W which implies suitable bounds on the curvature constant (see, e.g., <ref type="bibr">Lemma 18)</ref> to remove a d factor from the na&#239;ve smoothness bound. We also observe that W is exactly a rescaling of a bipartite matching polytope, so that we can use flow-based graph algorithms, e.g., the approximate weighted matching algorithm of <ref type="bibr">[22]</ref>, to efficiently implement the linear optimization oracles over W required by Frank-Wolfe methods. We then use techniques from numerical linear algebra and polynomial approximation to implement linear optimization oracles over S, completing our optimization subroutine for finding adaptive reweightings.</p><p>One other technical hurdle arises in implementing this framework for finding a reweighting: the existence of w &#8902; satisfying Items 1, 2, and 3 relies on having a good estimate of the current distance &#8741;M -M &#8902; &#8741; F , after excluding certain rows and columns. In general, we can only upper bound this quantity, but we show that we can also use our optimization subroutine for (2) to certify non-existence of such a w &#8902; . In this latter case, we show that it must have been the case that a few rows and columns were significantly heavier than the rest, and we can run Algorithm 1 to drop them. Our overall iterative method, Algorithm 2, makes bicriteria progress and either terminates with a "drop" step (when no feasible w &#8902; exists), or a "descent" step (when we find a good solution to (2)).</p><p>Recovering dropped rows and columns. Finally, we briefly discuss how to post-process an estimate M that is close to M &#8902; on a large submatrix to recover dropped rows and columns. The high-level outline is similar to <ref type="bibr">[43]</ref>, where we aim to find a "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 &#8467; 2 , since a semi-randomness could drastically distort the empirical &#8467; 2 error by adversarially revealing entries. We rely on a structural result using tools from the theory on volumetric spanners <ref type="bibr">[5,</ref><ref type="bibr">7]</ref> (see <ref type="bibr">Lemma 27)</ref> showing that large entrywise errors must be localized to a small submatrix. At this point, we set up &#8467; &#8734; regression problems to identify verified indices, solvable in nearly-linear time using recent advances in linear programming <ref type="bibr">[69]</ref>. Importantly, the overhead in the error guarantee of this recovery step is only O(poly(r)) (see Proposition 3), allowing us to achieve a recovery guarantee in Theorem 1 that avoids poly(d) overheads in the presence of noise.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Preliminaries</head><p>We now formally set up preliminaries required for analyzing our solution to the semi-random matrix completion problem. First, we recall the standard definition of incoherence for subspaces.</p><p>Definition 1 (Incoherence). We say a dimension-r subspace</p><p>(where e i is the ith standard basis vector), and M &#8712; R m&#215;n is &#181;-incoherent if M has &#181;-incoherent row and column spans.</p><p>We will work with symmetric matrices. We denote the space of d &#215; d symmetric matrices by S d&#215;d . In Appendix A, we give a reduction from general matrices to symmetric matrices showing that it suffices to work in the symmetric case, up to constant factor loss in parameters. Next, we define the semi-random observation model.</p><p>Definition 2 (Semi-random model). For M &#8712; S d&#215;d , we use O sr p (M) to denote oracle access to M in the p-semi-random model, where we call O sr p a p-semi-random oracle. Specifically, in one call to O sr p with input M, for unknown observation probabilities {p &#953; } &#953;&#8712;[d]&#215;[d] &#8838; [p, 1], each &#953; &#8712; [d] &#215; [d] is independently included in a set I with probability p &#953; . The oracle O sr p then returns the set {[M] &#953; } &#953;&#8712;I . When an algorithm requires the ability to query O sr p (M) for various values of p (specified in the algorithm description), we list the input as O sr [0,1] (M). Note that O sr p (M) and O sr [0,1]</p><p>(M) inherit their definitions in <ref type="bibr">[43]</ref> when all p &#953; = p, for a fixed p &#8712; [0, 1]. Now we can formally define the semi-random matrix completion problem we study.</p><p>Definition 3 (Semi-random matrix completion). In the semi-random matrix completion problem, parameterized by &#181;, &#8710; &#8712; R &#8805;0 , p &#8712; [0, 1], d &#8712; N, and r &#8902; &#8712; [d], there is an unknown rank-r &#8902; &#181;-incoherent matrix M &#8902; &#8712; S d&#215;d . For some N &#8712; S d&#215;d satisfying &#8741;N&#8741; &#8734; &#8804; &#8710;, and M := M &#8902; + N, we receive the output of one call to O sr p (M), and wish to output an approximation to M &#8902; . Remark 1. In Appendix A, we give a sample-splitting reduction which lets us use O sr p (M) to simulate &#8776; p q independent accesses to O sr q (M) for smaller values q &#8804; p. We will also need a few technical definitions to explain the main ingredients in our algorithm. </p><p>We recall the following standard facts about H * &#951; . Fact 1 ( <ref type="bibr">[58]</ref>). The function H * &#951; defined in (3) satisfies the following for all &#951; &gt; 0. 1. For all M &#8712; S d&#215;d , &#955; 1 (M) &#8804; H * &#951; (M) &#8804; &#955; 1 (M) + &#951; log d, where &#955; 1 (M) is the maximum eigenvalue of M.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">For all</head><p>&#951; is twice-differentiable and 1 &#951; -smooth with respect to the norm &#8741;&#8226;&#8741; op .</p><p>To use H * &#951; to enforce operator norm bounds, we define the signed lift of a matrix M &#8712; S d&#215;d by slift(M) := M 0 d&#215;d 0 d&#215;d -M &#8712; S 2d&#215;2d .</p><p>Note that slift signs and lifts M so that its maximum eigenvalue is its operator norm.</p><p>Comparing matrices. We use the following comparison definition from <ref type="bibr">[43]</ref>.</p><p>Definition 4 (Closeness on a submatrix). We say M, M &#8242; &#8712; R m&#215;n are &#8710;-close on a &#947;-submatrix if there exist subsets</p><p>If &#947; = 0, we say M, M &#8242; are &#8710;-close. When M, M &#8242; are both symmetric, we require that A = B.</p><p>We note that in Definition 4, A, B are unknown; our analysis only uses this definition existentially.</p><p>4 Outline of proof of Theorem 1</p><p>In this section, we overview the main components of the proof of Theorem 1, which are 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 1, by combining Corollary 1 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.</p><p>The first main component of our final algorithm, Algorithm 8, takes as input parameters &#945; and &#947; tot , as well as an input matrix M &#8712; S d&#215;d satisfying &#8741;M -M &#8902; &#8741; F &#8804; &#8710; (i.e., M and the target matrix M &#8902; are &#8710;-close), where &#8710; is sufficiently larger than the noise level &#8741;N&#8741; &#8734; . Its goal is to use semi-random observations from M = M &#8902; + N to return another matrix M &#8242; &#8712; S d&#215;d such that M and M are &#8710; &#945; -close on a &#947; tot -submatrix (Definition 4). In other words, we are willing to give up on a &#947; tot fraction of rows and columns to make an &#945; factor progress on the remaining submatrix. To achieve this result, we first provide a helper claim in Proposition 1, an analysis of Algorithm 2 (DropOrDescent). ), &#952;, &#954; &#8805; 1, and suppose for r := r + r &#8902; and an appropriate polynomial,</p><p>Given one call to O sr p (M &#8902; + N) for &#8741;N&#8741; &#8734; &#8804; &#1013;&#947;sub&#8710; 20d , the following holds with probability &#8805; 1 -&#948;.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">If Algorithm 2 returns on Line 16, then</head><p>&#8710;-close on a 2&#947; subsubmatrix, and M &#8242; is given as a rank-(3r + 2r &#8902; ) factorization.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>The runtime of the algorithm is</head><p>where m &#8805; d is the number of observed entries upon calling O sr p (M &#8902; + N). Proposition 1 is used to analyze one step of Algorithm 2, after we have already taken a few iterations and explicitly removed &#947; drop d rows and columns [d] \ U from consideration, so that our remaining submatrices on U &#215; U are close on a &#947; sub -submatrix. Our goal will ultimately to have &#947; sub , &#947; drop &#8804; &#947;tot 2 throughout the algorithm. Algorithm 2 provides bicriteria guarantees: in the "drop" case of Item 1, it slightly increases the &#947; drop parameter, increases &#947; sub by an even smaller amount (where the tradeoff is given by a degree of freedom &#954;), and makes a small amount of progress (decreasing the closeness by 1 -O(&#1013;)). In the "descent" case of Item 2, we instead decrease the closeness by a large O(poly(&#1013;)) factor, while doubling &#947; sub and roughly tripling the rank. By choosing the parameters appropriately, we show that iterating upon Proposition 1 yields Corollary 1, proven in Appendix B.</p><p>Corollary 1. Let M, M &#8902; &#8712; S d&#215;d be rank-r &#8902; , and suppose &#8741;M -M &#8902; &#8741; F &#8804; &#8710;. Let &#945; &#8805; 250 and &#948;, &#947; tot &#8712; (0, 1  10 ). Algorithm 3 uses one call to O sr p (M &#8902; + N), where for appropriate polynomials,</p><p>and computes a rank-r &#8902; &#8226; &#945; o(1) -matrix M &#8242; , such that with probability &#8805; 1 -&#948;, M &#8242; and M &#8902; are &#8710; &#945; -close on a &#947; tot -submatrix. The runtime of the algorithm is m&#945; o (1) &#8226; poly( r &#8902; &#947;tot log( d &#948; )), where m is the number of observed entries upon calling O sr p (M &#8902; + N). We now explain the key computational method we develop to implement Proposition 1. We will solve a subproblem, defined in <ref type="bibr">(5)</ref>, to attempt to find a reweighting which makes progress. The subproblem enforces the conditions on candidate weights w mentioned in Section 2, and is formally stated below:</p><p>where</p><p>&#953; for all &#953; &#8712; I, and</p><p>The difference between (5) and our informal sketch in ( <ref type="formula">2</ref>) is that we reparameterize x &#8592; w &#8226; v where v is the squared observations of the difference matrix D, and I is the set of observations. We also introduce a tradeoff parameter &#951; for controlling additive error bounds via Fact 1. Thus, the component &#10216;1 I , x&#10217; = &#10216;v, w&#10217; captures the progress condition (Item 3), and the component H * &#951; (slift(D( x v ) -S)) captures the flatness condition (Item 2). We optimize (5) over &#8741;S&#8741; F &#8804; 1 + &#1013;, the set of short matrices, and x belonging to X defined in <ref type="bibr">(22)</ref> which we observe is a rescaling of a bipartite matching polytope by a parameter k (Fact 3). This polytope is used to enforce the spreadness condition (Item 1).</p><p>In the case we find a good solution to the subproblem, we can use the resulting solution to take a descent step and give the guarantee in Item 2 of Proposition 3. Otherwise, we have certified that excluding a 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) at a fast rate is the following, proven in Appendix C. Proposition 2. Let &#1013; &#8712; [0, C] and &#948; &#8712; (0, 1), and suppose</p><p>There is an algorithm computing (x, S), an &#1013;-approximate minimizer to (5) with probability &#8805; 1 -&#948;, in time</p><p>&#8969;, and S is given as a rank-r = O( C 2 &#1013; 2 &#8226; T ) factorization. The last component in the proof of Theorem 1 is Algorithm 7, a "rounding" step where we take the output of Corollary 1, say M, which is guaranteed to be close to M &#8902; on a large submatrix, and then postprocess it to a matrix M that is guaranteed to be close to M &#8902; everywhere with some poly(r, &#181;, log d)-factor loss in the closeness. As long as the progress &#945; made by Corollary 1 is larger than this factor, we can simply alternate Corollary 1 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 &#8902; &#8712; S d&#215;d be rank-r &#8902; and &#181;-incoherent, and let M = M &#8902; + N for N &#8712; S d&#215;d with &#8741;N&#8741; &#8734; &#8804; &#8710; for some &#8710; &#8805; 0. Let M &#8712; S d&#215;d be given as a rank-r decomposition, with r &#8805; r &#8902; . Further, for &#947; &#8712; (0, 1) suppose M and M &#8902; are d&#8710;-close on a &#947;-submatrix. Finally, assume &#947; &#8804; 1 10 4 &#181;r log <ref type="bibr">(d)</ref> .</p><p>Then for any &#948; &#8712; (0, 1)</p><p>) for an appropriate polynomial, Algorithm 7 uses one call to O p ( M) and with probability &#8805; 1 -&#948;, outputs M &#8712; S d&#215;d such that</p><p>Also, M is given as a rank-poly(&#181;r log( d &#948; )) factorization. The algorithm runs in m &#8226; poly(&#181;r log( d &#948; )) time, where m is the number of observed entries upon calling O sr p ( M).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A Additional preliminaries</head><p>In this section, we formalize some additional preliminaries and helpful notation which will be used in the remainder of the appendices.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>General notation.</head><p>For n &#8712; N we denote [n] := {i &#8712; N | i &#8804; n}. We say a vector is s-sparse if it has &#8804; s nonzero entries. When S &#8838; T and T is clear from context, we let S c := T \S. The all-zeroes and all-ones vectors of dimension d are denoted 0 d and 1 d . Applied to a vector, &#8741;&#8226;&#8741; p denotes the &#8467; p norm for p &#8805; 1. Applied to a matrix, &#8741;&#8226;&#8741; p denotes the &#8467; p norm of the vector corresponding to the flattened matrix. We use med(S) to denote the median of a set S. For t &#8712; R we let sign(t) = 1 if t &#8805; 0 and sign(t) = -1 otherwise. We let &#8226; denote the entrywise product of two vectors.</p><p>Matrices. Matrices are denoted in boldface. The number of nonzero entries of a matrix M is denoted nnz(M), and the set of indices corresponding to these nonzero entries, i.e., the support, is denoted supp(M). We define T mv (M) as the amount of time it takes to compute Mv for any vector v; note</p><p>We equip R m&#215;n with the inner product &#10216;A, B&#10217; := Tr(A &#8868; B), denote the d &#215; d identity by I d , and the all-zero m &#215; n matrix by 0 m&#215;n . The i th row and j th column of a matrix M are respectively denoted M i: and M :j . For a collection of matrices</p><p>We say M is s-row column sparse (RCS) if its rows and columns are s-sparse.</p><p>we let the submatrix of M &#8712; R m&#215;n indexed by S, T be denoted</p><p>we denote this M i,T and similarly define M S,j for j &#8712; [n].</p><p>The Frobenius, operator, and trace (nuclear) norms of a matrix are denoted &#8741;&#8226;&#8741; F , &#8741;&#8226;&#8741; op , and &#8741;&#8226;&#8741; tr respectively, corresponding to the 2-norm, &#8734;-norm, and 1-norm of the singular values of the matrix. We denote the symmetric d &#215; d matrices by S d&#215;d and the positive semidefinite cone by S d&#215;d &#10928;0 . We say M &#8712; R m&#215;n has singular value decomposition (SVD)</p><p>where &#963; 1 (M) is largest. Similarly we define the ordered eigenvalues of M &#8712; S d&#215;d by {&#955; i (M)} i&#8712; <ref type="bibr">[d]</ref> . For M &#8712; S d&#215;d with eigendecomposition U&#923;U &#8868; , we define exp(M) := U exp(&#923;)U &#8868; where on the right-hand side, exp is applied entrywise on the diagonal. We also define log M for M &#8712; S d&#215;d &#10928;0 and |M| for M &#8712; S d&#215;d so 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 a subspace V &#8834; R d , we let &#928; V denote the orthogonal projection matrix onto V . Index sets. For d &#8712; N, we let S(d) contain all symmetrized indices of the form:</p><p>We use (i, j) &#9839; as shorthand for the singleton {(i, i)} if i = j, and otherwise as shorthand for</p><p>we let M I be the d &#215; d matrix which zeroes out all entries of M except those in &#953;. For a symmetrized index &#953; &#8712; S(d), we denote the scalar value of the &#953; entry by [M] &#953; (note that this is well-defined even when &#953; contains two indices due to symmetry). The zero-one matrix whose only nonzero entries are &#953; is denoted by E &#953; , so that Optimization. For convex f : X &#8594; R with X &#8838; R d , we let &#8706;f (x) denote the subgradient set at x &#8712; X . We let &#8741;y&#8741; * := sup &#8741;x&#8741;&#8804;1 x &#8868; y denote the dual norm to a norm &#8741;&#8226;&#8741;. When M is a d &#215; d linear operator we use the notation M[u, v] := &#10216;Mu, v&#10217;. This becomes relevant when M is a Hessian of a matrix function (a linear operator on d &#215; d matrices), so M[U, V] evaluates this operator on U, V.</p><p>Reduction to symmetric matrices. We briefly justify our focus on symmetric matrices in Definition 3. We begin by recalling two facts.</p><p>Let m, n, k &#8712; N and let M &#8712; R m&#215;n be rank-r with SVD M = U&#931;V &#8868; . Suppose that both U := span(U) and V := span(V) are &#181;-incoherent. Then, letting M &#8242; &#8712; R m&#215;kn be defined as</p><p>Proof. It is straightforward to check that a valid SVD is given by</p><p>Because incoherence is invariant to the choice of SVD, the conclusion holds.</p><p>Consider an asymmetric variant of the problem in Definition 3, where M &#8902; &#8712; R m&#215;n for m &#8805; n is rank-r &#8902; and &#181;-incoherent, and we have p-semi-random observation oracle access (defined analogously to Definition 2) to M &#8902; . Let k be the integer from Fact 2, and let M &#8902; &#8712; R m&#215;kn be constructed as in Lemma 1 by concatenating M &#8902; k times. The row and column spans of M &#8902; are &#181;-incoherent, by Lemma 1. Moreover, we can simulate p-semi-random observation oracle access to</p><p>in the symmetric sense of Definition 3, given asymmetric oracle access to M &#8902; . It is straightforward to check that because M &#8902; has dimensions within a 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.</p><p>Sample splitting. Finally, we recall a convenient subsampling claim from <ref type="bibr">[43]</ref> that extends to the semi-random model, which lets us use O sr p (M) to simulate access to O sr q (M) for smaller values q &#8804; p.</p><p>, and let M &#8902; &#8712; S d&#215;d . We can simulate sequential access to</p><p>Proof. The claim is immediate from the observation that the proof of Lemma 1, <ref type="bibr">[43]</ref> is monotone in p. In particular, the same subsampling process in <ref type="bibr">[43]</ref> preserves monotonicity of observation probabilities and hence produces valid semi-random observation oracles.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B Semi-random partial matrix completion</head><p>In this section, we develop Algorithm 3, our main subroutine for partial matrix completion in the semi-random model (Definition 2). Algorithm 3 uses recursive calls to Algorithm 2, DropOrDescent, which implements a single step of our partial completion method.</p><p>At a high level, one application of DropOrDescent is parameterized by a current number of dropped rows &#947; drop , a current number of excluded rows &#947; sub , a subset of undropped rows U = [d]\D satisfying |D| &#8804; &#947; drop d, and a rank-r matrix M such that M U &#215;U is promised to be close to our target M &#8902; U &#215;U on a &#947; sub -submatrix (Definition 4). It then distinguishes between the following cases from semi-random, noisy observations of M &#8902; , by solving a testing problem via optimization.</p><p>1. In the first case, dropping an additional &#947; fraction of rows and columns decreases the closeness parameter &#8710; by a small amount, i.e. a small subset of rows or columns are responsible for a nontrivial portion of the mass. We call this case the "drop" case.</p><p>2. In the second case, after removing a few rows and columns, the remaining mass is still large. We show that in this case, by deleting a particular subset of problematic rows or columns, we can use well-conditionedness properties of the remaining submatrix to decrease &#8710; by a constant factor. We do so by solving an optimization problem, which finds a spread reweighting of observations with a short-flat decomposition. We call this case the "descent" case.</p><p>We analyze the descent case in Appendix B.1, where we demonstrate sufficient conditions on a 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 <ref type="bibr">(20)</ref>). 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 a 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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B.1 Descent steps</head><p>In this section, we give our progress analysis in the case where we can find sufficient signal in our observations. Specifically, Lemma 7 gives sufficient conditions on a reweighted, truncated observation matrix such that we can improve our submatrix closeness parameter by a constant factor.</p><p>For D &#8712; S d&#215;d , we first define a clipping operation which will be used to control our reweightings. We let clip u (D) be the matrix which clips all entries to the range [-u, u], formally defined by</p><p>We also will use the following claim which follows from straightforward casework.</p><p>Lemma 3. Let u &#8805; 0, |a| &#8804; u, and a &#8242; := med(-u, a + b, u). Then |a &#8242; -a| &#8804; |b|.</p><p>Proof. If |a + b| &#8804; u the claim is obvious. Otherwise, if a &#8242; = u it must be the case that b &#8805; 0, and</p><p>We now introduce some additional notation. Let I &#8834; S(d) be a set of symmetrized indices under consideration (corresponding to observations). For w &#8712; R I and D &#8712; S d&#215;d clear from context, we let</p><p>For a parameter &#961;, we define the set of "spread" reweightings of the observations D I by</p><p>Further, we require the following result on low-rank approximation.</p><p>Lemma 4 (Theorem 1, <ref type="bibr">[56]</ref>). Let &#948;, &#1013; &#8712; (0, 1), let M &#8712; S d&#215;d , and let q &#8712; [d]. There is an algorithm which returns Z &#8712; R d&#215;q with orthonormal columns such that</p><p>Moreover, we have for all i &#8712; [q], letting z i be the i th column of Z,</p><p>Finally, we provide ways to bound the singular values of an approximately low-rank matrix. Proof. Let &#955; &#8712; R d be the set of eigenvalues of M in nonincreasing order, and similarly let &#963; &#8712; R d be the nonincreasing eigenvalues of S. By assumption, &#955; i = 0 for all i &#8805; r + 1, and &#8741;&#955; -&#963;&#8741; 2 &#8804; &#1013; by Lemma 5. Thus, at most r + s eigenvalues of S can be larger than &#1013; s 1/2 , giving the conclusion.</p><p>We are now ready to give our main progress guarantee in Lemma 7. Specifically, we show that a reweighting of truncated observations which has enough signal and admits a short-flat decomposition is guaranteed to make significant progress, as long as it is sufficiently spread in the sense of ( <ref type="formula">9</ref>).</p><p>Lemma 7. Let &#1013;, &#947; &#8712; (0, 1  10 ), &#8467;, u &#8805; 0, and</p><p>and for</p><p>2&#947;d , recalling the definition (9).</p><p>Then, letting Z &#8712; R d&#215;2r be the output of Lemma 4 with parameters &#948; &#8712; (0, 1), &#1013; &#8592; 1 2 , M &#8592; S, and q &#8592; 2r, we have with probability &#8805; 1 -&#948; that</p><p>Proof. As a starting point, we claim that</p><p>To see this, we expand to show that</p><p>The first line used Item 3 and &#8741;D &#8902; S&#215;S &#8741; F &#8804; 1, and the second used the (matrix) H&#246;lder's inequality. The third used Item 4 and that &#8741; D T &#215;T &#8741; tr &#8804; &#8730; r&#8741; D T &#215;T &#8741; F , and the (vector) H&#246;lder's inequality. The last line used &#8741;D &#8902; T &#215;T &#8741; &#8734; &#8804; u, the definition of D, and Lemma 3 to conclude</p><p>and also bounded &#8741; D(w)&#8741; 1 via Items 1 and 5, which show</p><p>Finally, since w is supported on U &#215; U , applying |U \ T | &#8804; 2&#947;d, Item 1, and Item 2 yields</p><p>Then, <ref type="bibr">(10)</ref> follows by combining <ref type="bibr">(11)</ref> and <ref type="bibr">(12)</ref>. Next, applying Lemma 6 using <ref type="bibr">(10)</ref> shows that &#963; 2r+1 (S) &#8804; 13&#1013; r . Therefore, assuming the algorithm in Lemma 4 succeeds, we have</p><p>At this point, we can write D(w) = S &#8242; + (F + F &#8242; ), where by the triangle inequality</p><p>the remainder of the argument is identical to the proof of <ref type="bibr">(10)</ref> with the worse flatness parameter, where we use that</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B.2 Existence of good solutions</head><p>In this section, we define a stability condition <ref type="bibr">(14)</ref> under which implies a 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, we show that under <ref type="bibr">(14)</ref>, there exists a reweighting (with high probability over the semi-random observations) which is compatible with Lemma 7's requirements. We then show in Lemma 12 that in the absence of ( <ref type="formula">14</ref>), 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 in 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.</p><p>Lemma 8 (Lemma 6, <ref type="bibr">[43]</ref>). Let A &#8712; S d&#215;d be a rank-r matrix with &#8741;A&#8741; F &#8804; 1, and let &#947; &#8712; [0, 1].</p><p>There is</p><p>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.</p><p>Lemma 9 (Lemma 7, <ref type="bibr">[43]</ref>). Let p, &#948; &#8712; [0, 1  2 ], &#961;, &#964; &#8805; 0, and let A &#8712; S d&#215;d satisfy</p><p>Let &#8486; &#8838; S(d) be a random subset where each &#953; &#8712; S(d) is included in &#8486; with probability p, and let A := 1 p A &#8486; . Then with probability at least 1 -&#948;,</p><p>Finally, we need a guarantee on the concentration of empirical estimates of squared &#8467; 2 norms.</p><p>Lemma 10 (Lemma 3, <ref type="bibr">[43]</ref>). Let p, &#948;, &#945; &#8712; (0, 1), let v &#8712; R d have &#8741;v&#8741; &#8734; &#8804; &#964; , and let &#7805; &#8712; R d have each &#7805;i independently set to v i with probability p, and 0 otherwise. Then with probability &#8805; 1 -&#948;,</p><p>We are now ready to give our main result on sufficient conditions for a good solution to exist.</p><p>Lemma 11. Let &#948;, &#1013;, &#947;, p &#8712; (0, 1  10 ), and</p><p>Suppose that for D, D &#8902; , N &#8712; S d&#215;d , we have</p><p>Finally, let S &#8242; be the result of applying Lemma 8 with A &#8592; D &#8902; S&#215;S , &#947; &#8592; &#947; 2 , so &#8741;D &#8902; S &#8242; &#215;S &#8242; &#8741; &#8734; &#8804; u, and let T := S &#8242; \ L where L is the indices of the &#8970; &#947;d 2 &#8971; rows of D S &#8242; &#215;S &#8242; with largest &#8467; 2 norms, so</p><p>Letting &#8486; &#8838; S(d) have each &#953; &#8712; S(d) independently included with probability p, and</p><p>p if and only if &#953; &#8712; (T &#215; T ) &#8745; &#8486; &#8902; , the following conditions all hold with probability &#8805; 1 -&#948; over the randomness of &#8486;, and S &#8902; ,</p><p>2&#947;d , recalling the definition (9).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">D, D(w</head><p>3.</p><p>Proof. For notational convenience, let</p><p>We define our decomposition of D(w &#8902; ) as follows, where we recall w &#8902; is supported on (T &#215; T ) &#8745; &#8486; &#8902; :</p><p>where we used that every entry of S &#8902; is smaller in magnitude than the corresponding entry in D S&#215;S (it is zeroed out if it does not belong to (T &#215; T ) &#8745; &#8486; &#8902; , and otherwise is clipped to a smaller range). This establishes Item 3. The same logic shows that &#8741; D S &#8242; &#215;S &#8242; &#8741; F &#8804; 1 + &#1013; 200 . Combined with <ref type="bibr">(14)</ref> and the definition of T ,</p><p>, and L consisted of the largest rows of S &#8242; by &#8467; 2 norm. Therefore, applying Lemma 9 with A &#8592; D (T &#215;T )&#8745;&#8486; &#8902; , &#964; &#8592; u, and &#961; 2 &#8592; &#1013; 5&#947;d establishes Item 4 with probability &#8805; 1 -&#948; 3 using the lower bound on p. We further have by <ref type="bibr">(14)</ref> that</p><p>Therefore, Lemma 10 with v set to the vectorized D (T &#215;T )&#8745;&#8486; &#8902; , &#964; &#8592; u, and &#945; &#8592; &#1013; 5 shows</p><p>with probability &#8805; 1 -&#948; 3 ; we again used our lower bound on p. Combining the above two displays establishes Item 2. Finally, to see Item 1, fix a row i &#8712; T . We apply Lemma 10 once more with v set to the vectorized [ D (T &#215;T )&#8745;&#8486; &#8902; ] i: and &#945; = 1  2 to obtain that with probability &#8805; 1 -&#948; 3 ,</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>D(w &#8902; )</head><p>i:</p><p>where we used <ref type="bibr">(15)</ref> and our lower bound on p.</p><p>We also provide a helper lemma for making progress if ( <ref type="formula">14</ref>) fails to hold.</p><p>Lemma 12. In the setting of Lemma 11, if</p><p>Proof. This follows from Lemma 3 and the assumption on <ref type="bibr">(14)</ref>, which lets us bound</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B.3 Drop steps</head><p>In the previous Appendix B.2, we developed Lemmas 11 and 12, which together say that either there exists a good solution compatible with the progress analysis in Lemma 7 (if ( <ref type="formula">14</ref>) holds), or there are an &#8776; &#947; fraction of rows and columns which are responsible for an &#8776; &#1013; fraction of the Frobenius norm of the difference matrix (if <ref type="bibr">(14)</ref> does not hold). In this section, we show in the latter scenario, there is a procedure which explicitly drops a subset of rows and columns, such that on the remainder, a slightly smaller submatrix makes an &#8776; &#1013; fraction of progress. Importantly, we can ensure that the submatrix parameter (i.e. &#947; 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.</p><p>We begin by giving a subroutine (Algorithm 1), analogous to Section 4.1 of <ref type="bibr">[43]</ref>, which takes semirandom observations from an appropriately-bounded difference matrix and explicitly drops a small 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.</p><p>Algorithm 1:</p><p>t max do D t &#8592; O sr p (D St&#215;St ) for i &#8712; S t do r i,t &#8592; |{j &#8712; S t | [D t ] ij was observed, and |[D t ] ij | &#8805; &#964; }| S t+1 &#8592; S t \ R t where R t &#8834; S t corresponds to the &#8970;&#947;d&#8971; indices i with largest r i,t end return U &#8242; &#8592; S tmax Proof. Let P &#8712; [0, 1] d&#215;d be the true (symmetric) matrix of reveal probabilities of entries for calls to O sr p , following Definition 2. Note that all entries of P are at least p. We define the potential</p><p>We also denote the expected number of revealed large entries in each row and column as follows:</p><p>By a standard Chernoff bound, with probability &#8805; 1 -&#948;, for all 0 &#8804; t &lt; t max and all i &#8712; S t ,</p><p>Condition on this event in the rest of the proof. Due to our symmetric observation model (Definition 2), and since A &#215; A has no entries &#8805; &#964; in magnitude, in any iteration, at least half of the contribution to &#934; t must be due to remaining rows in B t := S t \ A, i.e. we have</p><p>Letting R &#8902; i,t denote the &#8970;&#947;d&#8971; &#8805; |B t | indices in S t with largest r &#8902; i,t , we thus have from <ref type="bibr">(16)</ref>,</p><p>Therefore, if &#934; t &#8805; 400&#947;d log( d &#948; ), we decrease &#934; t by at least a 1 4 factor, so by our choice of t max , we have &#934; tmax-1 &#8804; 400&#947;d(log d &#948; ) &#8804; &#947;psd 2 . This shows that there are at most &#947;d remaining rows i &#8712; S tmax-1 with r &#8902; i,tmax-1 &#8805; ps 2 . Now, any remaining row i &#8712; S tmax-1 with at least s entries with magnitude &#8805; &#964; has r &#8902; i,tmax-1 &#8805; ps, and therefore will be one of the largest &#947;d remaining rows by observed counts via <ref type="bibr">(16)</ref>. Hence, it will be dropped in the last iteration t max as claimed.</p><p>We conclude by showing that the leftover poorly-behaved 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 &#8776; &#1013; fraction of the progress if the condition in Lemma 12 is met. Lemma 14. Let &#948;, &#1013;, &#947;, p &#8712; (0, 1  10 ), &#952;, &#954; &#8805; 1, and</p><p>returns a subset U &#8242; &#8838; U such that with probability &#8805; 1 -&#948;, there exists a subset S &#8242; &#8838; U &#8242; with</p><p>Proof. First, by Lemma 8, there is a subset A &#8838; S such that |S \ A| &#8804; 10 r &#952; , so that</p><p>Therefore, our application of Algorithm 1 with the parameters in <ref type="bibr">(17)</ref> satisfies the hypotheses of Lemma 13. Condition on the conclusion of Lemma 13 holding in the rest of the proof (with probability &#8805; 1 -&#948;), giving us the first bound in <ref type="bibr">(18)</ref>. Also, there are at most d r&#954; entries per row and column of D U &#8242; &#215;U &#8242; with magnitude larger than &#964; in <ref type="bibr">(17)</ref>, so there are at most d r&#954; entries per row and column of</p><p>By Lemma 8, there is a subset</p><p>This set satisfies the second bound in <ref type="bibr">(18)</ref>, so it remains to prove the third, which follows from</p><p>The third line used that there are at most &#1013;d &#952; rows in C, and each such row (restricted to S &#8242; ) has all but d r&#954; entries bounded in magnitude by &#964; , with the remainder bounded as in <ref type="bibr">(19)</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B.4 Analysis of DropOrDescent and SRPartialCompletion</head><p>We now combine Lemma 7 and Lemma 14 to give a win-win analysis of a progress step, DropOrDescent. This progress step either executes a descent step (analyzed via <ref type="bibr">Lemma 7)</ref>, or a drop step (analyzed via Lemma 14); we use Lemmas 11 and 12 to demonstrate correctness of each of these cases. For the runtime analysis, we rely on Proposition 6, the main result of Appendix C, to solve a relevant optimization problem used by our algorithm, but all other parts of the proof are self-contained.</p><p>We provide pseudocode for the algorithm corresponding to Proposition 1 in Algorithm 2.</p><p>&#953; for all &#953; &#8712; I (w, S) &#8592; &#1013; 12 -approximate minimizer to <ref type="bibr">(20)</ref> with failure probability &#948; 5 , computed using Proposition 6</p><p>Return: ("Descent", M &#8242; &#8592; M + ZZ &#8868; SZZ &#8868; ) end Proposition 1. Let M &#8712; S d&#215;d be given as a rank-r factorization, let M &#8902; &#8712; S d&#215;d be rank-r &#8902; , and let U &#8838;</p><p>), &#952;, &#954; &#8805; 1, and suppose for r := r + r &#8902; and an appropriate polynomial,</p><p>Given one call to O sr p (M &#8902; + N) for &#8741;N&#8741; &#8734; &#8804; &#1013;&#947;sub&#8710; 20d , the following holds with probability &#8805; 1 -&#948;.</p><p>1. If Algorithm 2 returns on Line 12, then M U &#8242; &#215;U &#8242; , M &#8902; U &#8242; &#215;U &#8242; are (1 -&#1013; 288 )&#8710;-close on a &#947; sub + 4 &#8730; &#952;&#954; -submatrix, and |U \ U &#8242; | &#8804; 40(&#947; sub + ( r &#952; ) 1/2 )d log d. 2. If Algorithm 2 returns on Line 16, then M &#8242; U &#215;U , M &#8902; U &#215;U are 10&#1013; 1 4 &#8710;-close on a 2&#947; subsubmatrix, and M &#8242; is given as a rank-(3r + 2r &#8902; ) factorization. The runtime of the algorithm is</p><p>where m &#8805; d is the number of observed entries upon calling O sr p (M &#8902; + N).</p><p>Proof. Throughout the proof, without loss we let &#8710; = 1, since we can scale M by 1 &#8710; , take the claimed step, and scale up by &#8710; (indeed, examination of Algorithm 2 shows it performs this scaling). We now describe our algorithm. Define W &#961; as in <ref type="bibr">(9)</ref>, and for w &#8712; R I , define D(w) as in <ref type="bibr">(8)</ref> </p><note type="other">.</note><p>We compute (w, S), an &#1013; 12 -approximate minimizer to F , and V , satisfying |V -F (w, S)| &#8804; &#1013; 12 . Pseudocode for computing such a V with failure probability 1 -&#948; 5 is provided in Line 9, and the correctness and runtime of this step are analyzed at the end of this proof.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">If V &gt; -(1 -11&#1013;</head><p>12 ), we call Sparsify on (our semi-random access to) the matrix</p><p>5d , &#947; &#8592; &#947; sub + 10 r &#952; , p &#8592; p, and &#948; &#8592; &#948; 5 . We then return the new row subset U &#8242; &#8838; U . We call this case the "drop" case.</p><p>2. Otherwise, we update to M + ZZ &#8868; SZZ &#8868; , where Z &#8712; R d&#215;2r is the output of <ref type="bibr">Lemma 4</ref> with parameters &#948; &#8592; &#948; 5 , &#1013; &#8592; 1 2 , M &#8592; S, and q &#8592; 2r. We call this case the "descent" case. We first analyze the drop case. We claim that if V &gt; -(1 -11&#1013; 12 ), it could not be the case that ( <ref type="formula">14</ref>) held. To see this, suppose (14) held. Then, with probability &#8805; 1 -&#948; 5 (due to our lower bound (4) on p), Lemma 11 provides us (w &#8902; , S &#8902; ) &#8712; W &#961; &#215; S satisfying</p><p>In fact, w &#8902; is only supported on &#8486;, the fully random coordinates. By using Fact 1, we conclude that</p><p>Therefore, any &#1013; 12 -approximate minimizer (w, S) to F will satisfy F (w, S) &#8804; -(1 -5&#1013; 6 ). Finally, since we assumed our computed value V satisfies |V -F (w, S)| &#8804; &#1013; 12 , this contradicts V &gt; -(1 -11&#1013; 12 ) 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 &#1013; &#8592; &#1013; 36 , proving correctness of the "drop" case with the stated parameters.</p><p>Next, suppose we are in the descent case, meaning we have (w, S) &#8712; W &#961; &#215; S satisfying F (w, S) &#8804; -(1 -&#1013;). By nonnegativity of the second summand in the definition of F , this shows</p><p>Moreover, because &#10216;v, w&#10217; &#8804; d&#961; = &#1013; 2&#947; by the definition of W &#961; , we have</p><p>where we used Fact 1 in the first inequality. Lemma 7 then yields correctness of the "descent" case.</p><p>We next bound the runtime, which is the sum of three costs: the optimization solver, the cost of obtaining an approximate value V , and the cost of Lemma 7 in the descent case. It is straightforward to check that in the context of Proposition 6, which bounds the runtime of our optimization solver,</p><p>Therefore, by our choices of C, &#951; from before, the cost of Proposition 6 for &#948; 5 failure probability is</p><p>Next, consider the cost of obtaining V satisfying |V -F (w, S)|. We can explicitly compute the term &#10216;v, w&#10217;, and because &#951;C log(2d) &#8804; &#1013; 24 , it suffices to obtain an &#1013; 24C = &#1013;&#947;sub 12r 1/2 -additive approximation to &#8741; D(w) -S&#8741; op by Fact 1. The guarantees of Proposition 6 give that &#8741; D(w) -S&#8741; op &#8804; 2&#1013; r1/2 (see <ref type="bibr">(21)</ref>). Therefore, we may call Lemma 4 with q &#8592; 1, &#1013; &#8592; &#947;sub 24 , and &#948; &#8592; &#948; 6 , in time which does dominate the above, using the rank-O( r2.5 log(d) &#947; 6 sub &#1013; 5 ) factorization of S given to us by Proposition 6. Additionally, the runtime of Lemma 7, i.e. the cost of running Lemma 4 with constant &#1013; and q = 2r, does not dominate Proposition 6. The claimed runtime follows by combining these bounds.</p><p>Finally, the failure probability comes from a union bound over Lemma 11, Lemma 14, the subroutine in Proposition 6, and our two calls to Lemma 4, once for the descent step and once to compute the value V . We set each of the failure probabilities of these five randomized steps to &#948; 5 .</p><p>By iterating on Proposition 1, we provide our full partial completion method, Algorithm 3.</p><p>Corollary 1. Let M, M &#8902; &#8712; S d&#215;d be rank-r &#8902; , and suppose &#8741;M -M &#8902; &#8741; F &#8804; &#8710;. Let &#945; &#8805; 250 and &#948;, &#947; tot &#8712; (0, 1  10 ). Algorithm 3 uses one call to O sr p (M &#8902; + N), where for appropriate polynomials,</p><p>and computes a rank-r &#8902; &#8226; &#945; o(1) -matrix M &#8242; , such that with probability &#8805; 1 -&#948;, M &#8242; and M &#8902; are &#8710; &#945; -close on a &#947; tot -submatrix. The runtime of the algorithm is m&#945; o (1) &#8226; poly( r &#8902; &#947;tot log( d &#948; )), where m is the number of observed entries upon calling O sr p (M &#8902; + N).</p><p>Proof. We claim that throughout the course of Algorithm 3, the preconditions of Proposition 1 are always met, i.e. &#947; sub is always an upper bound on the number of excluded rows U \ S, &#947; drop is always an upper bound on the number of dropped rows [d] \ U , and M always has rank r -r &#8902; . To show correctness of the rank bound, the rank r of our iterate only increases on drop steps, where Proposition 1 ensures r + r &#8902; at most triples, so r -r &#8902; (after the update on Line 11) remains a correct bound on r throughout the algorithm. Also, r &#8804; rtot throughout, since there are &#8804; R descent steps.</p><p>We next prove correctness of the &#947; sub parameter throughout the algorithm. By Proposition 1, this parameter doubles each time Algorithm 2 runs a descent step, which is correctly handled by Line 11. Moreover, the only other time &#947; sub increases is by 4   &#8730; &#952;&#954; each time Algorithm 2 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 &#952;, &#954;, we have</p><p>which is our initial setting of &#947; sub in Line 3. Therefore, since the worst-case growth of the &#947; sub parameter over RK drop steps and R descent steps is if we encounter all of the drop steps first (and then repeatedly double R times), the value of &#947; sub is correct throughout the algorithm.</p><p>Next, we show that the &#947; drop parameter remains correct throughout the algorithm. Note that the &#947; sub parameter is never larger than</p><p>Therefore, the number of dropped rows in each drop step, by Proposition 1 and our choice of &#952;, is at most</p><p>Therefore the update to &#947; drop in Line 7 is correct. We have also shown that over the course of the algorithm, we never drop or exclude more than &#947;totd 160RK log(d) + &#947;totd 2 &#8804; &#947; tot d rows in total. Additionally, we verify the second condition in (4) holds with the largest value of &#947; sub :</p><p>Finally, after RK drop steps Proposition 1 shows that we have made an exp(-&#1013; 288 &#8226; RK) = 1 &#945; factor progress on the closeness parameter &#8710;. Similarly, after R descent steps, since 10&#1013; &#945; factor progress as well. The failure probability comes from union bounding over the at most R(K + 1) calls to DropOrDescent.</p><p>For the runtime bound, by observation all of the parameters r, &#947; -1 sub , &#1013; -1 in Proposition 1 are bounded by a polynomial in r &#8902; &#8226; &#945; o (1) throughout the algorithm. The correctness of the lower bound on p and the upper bound on &#8741;N&#8741; &#8734; similarly follow from Proposition 1.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C Computing adaptive reweightings</head><p>In this section, we develop an optimization subroutine for solving the subproblems <ref type="bibr">(20)</ref> arising in our partial matrix completion method. We use an approximate Frank-Wolfe framework to reduce our optimization to a sequence of linear optimization problems over our constraint set, which we characterize as a matching polytope over a 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, as 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 we study in a self-contained way.</p><p>Throughout this section, we fix a subset I &#8834; S(d) and parameters k &#8712; R &gt;0 , &#1013; &#8712; (0, 1), and define:</p><p>In other words, S is the set of "short" (Frobenius-norm bounded) matrices. Further, if x &#8712; X is viewed as a symmetric d &#215; d matrix, the constraints on X enforce that x has bounded row and column sums. Clearly x &#8712; X =&#8658; &#8741;x&#8741; 1 &#8804; k, so X is a subset of an &#8467; 1 ball of radius k. However, we can more specifically capture X as a scaled bipartite matching polytope. </p><p>we place an edge from the i th vertex in L (denoted u i ) to the j th vertex in V (denoted v j ) if and only if (i, j) &#9839; &#8712; S(d). Let M be the bipartite matching polytope of G, i.e.</p><p>Then d k X = M for X in <ref type="bibr">(22)</ref>, where we map coordinates in I to edges in E in the canonical way. By the characterization in Fact 3, we efficiently implement iterations of our Frank-Wolfe method by calling an approximate maximum weight matching algorithm by <ref type="bibr">[22]</ref>. 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 a bounded submatrix, whose entries lie in a given range. </p><p>With these definitions in hand, our goal in this section is to optimize the following jointly convex function over (x, S) &#8712; Z, for an (&#8467;, u)-bounded submatrix (D, I) and parameters C, &#951; &#8712; R &gt;0 , named F prog-flat to denote its decomposition into progress and (approximate) flatness components:</p><p>where v &#953; = [D] 2 &#953; for all &#953; &#8712; I, and</p><p>Note that ( <ref type="formula">25</ref>) is exactly the problem in <ref type="bibr">(20)</ref>, up to reparameterizing x &#8592; w &#8226; v. It may be helpful to think of the parameter settings for <ref type="bibr">(25)</ref> in the context <ref type="bibr">(20)</ref>, e.g.,</p><p>, where r and &#947; are the rank and closeness parameter of a current iterate.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.1 Approach based on the Frank-Wolfe method</head><p>To efficiently minimize f = F prog-flat (defined in <ref type="bibr">(25)</ref>) over Z (defined in ( <ref type="formula">22</ref>)) we apply a variant of Frank-Wolfe or conditional gradient methods due to <ref type="bibr">[35]</ref>. This method essentially reduces the problem to approximately solving min z&#8712;Z &#10216;&#8711;f (q), z&#10217; for different values of q &#8712; Z. The algorithm is given below as Algorithm 4. <ref type="foot">10</ref> Below we define the curvature constant, the key quantity which bounds the convergence of the method, as well as the main theorem from <ref type="bibr">[35]</ref> which we use. </p><p>Definition 6 (Curvature constant (restated from <ref type="bibr">[35]</ref>)). The curvature constant C f,D of convex and differentiable f :</p><p>Proposition 4 (Approximate Frank-Wolfe, Theorem 1 of <ref type="bibr">[35]</ref> restated and specialized). Let f : R d &#8594; R be convex and differentiable, let D &#8838; R d be compact and convex, and let z &#8902; &#8712; argmin z&#8712;D f (z).</p><p>For any K &#8805; 1 and &#948; &#8805; 0,</p><p>To facilitate applying Proposition 4 to efficiently minimize F prog-flat <ref type="bibr">(25)</ref> over Z <ref type="bibr">(22)</ref> we provide two general lemmas. The first is Lemma 15 below, which implies that to implement Line 5 of Algorithm 4 it suffices to compute approximate gradients and and then approximately solve constrained linear optimization problems for these approximate gradients.</p><p>Lemma 15 (Gradient approximation). For compact Proof. For s &#8902; &#8712; argmin s&#8712;D &#10216;g, s&#10217; the assumptions imply that</p><p>The result then follows as</p><p>The second lemma is the following straightforward upper bound on the curvature constant (that is perhaps related to the relationship to smoothness given in Lemma 7 of <ref type="bibr">[35]</ref>). It shows that to upper bound the curvature constant it suffices to upper bound &#8711; 2 f (z)[w, w] for all w, z &#8712; D.</p><p>Lemma 16 (Curvature bound). For convex, twice-differentiable f :</p><p>&#8804; M for all w, z &#8712; D then the curvature constant f with respect to D is at most 2M .</p><p>Proof. Let z 0 , z 1 &#8712; Z and &#947; &#8712; [0, 1] and define</p><p>is positive semidefinite for all x &#8712; D and so</p><p>Combining these bounds yields the desired bound of</p><p>In the following Appendix C.2 we bound the curvature constant of the particular f = F prog-flat defined in ( <ref type="formula">24</ref>) over Z and provide additional regularity bounds on this f over Z. Then in Appendices C.3 and C.4, we discuss the implementation of a single step of Algorithm 5 (specifically, Line 5 by satisfying the conditions needed to apply Lemma 15). To fix some notation, we let z t := (x t , S t ) be the t th iterate of Algorithm 5 (z (t) in the code). We also let</p><p>be the gradient of H * &#951; (slift(D( x v ) -S)) before applying the chain rule, see Fact 1. Because of the block-separable structure of slift, we have that</p><p>where</p><p>For notational simplicity, we finally define</p><p>We observe that by definition of the objective in ( <ref type="formula">25</ref>), we have</p><p>Finally, g t := (h t , H t ) denotes the blocks of the approximate gradient computed in iteration t and v t := (w t , W t ) denotes the blocks of the approximate linear objective optimizer in iteration t, as suffice for applying Lemma 15. Throughout Appendices C.3 and C.4, we fix a single iteration t and drop t from all subscripts, to decrease notational clutter.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.2 Curvature constants and regularity</head><p>Here we bound the curvature constant of F prog-flat as defined in <ref type="bibr">(25)</ref> over Z defined in <ref type="bibr">(22)</ref>. To do so, we first provide a bound, Lemma 17, on the operator norm of D(x) defined in <ref type="bibr">(24)</ref>, for x &#8712; X . The proof follows from a previously established fact that the operator norm of any matrix (even if rectangular) is upper bounded by the maximum &#8467; 1 norm of any its rows or columns (see e.g., Lemma B.4, <ref type="bibr">[19]</ref>); however, we directly give a self-contained proof for convenience.</p><p>Lemma 17. For all x &#8712; X (defined in ( <ref type="formula">22</ref>)), we have &#8741;D(x)&#8741; op &#8804; ku d for D as defined in <ref type="bibr">(24)</ref>.</p><p>Proof. For all z &#8712; R d , the Cauchy-Schwarz inequality and the fact that D(x) is symmetric imply</p><p>Additionally, for all i &#8712; [d] since (D, I) is an (&#8467;, u)-bounded submatrix and x &#8712; X ,</p><p>Combining shows that |z &#8868; D(x)z| &#8804; ku d &#8741;z&#8741; 2 2 for all z &#8712; R d and yields the result as D(x) is symmetric.</p><p>Lemma 17 improves upon the trivial bound on &#8741;D(x)&#8741; op for x with &#8741;x&#8741; 1 &#8804; k. Note that if x has k on the index corresponding to the largest entry of D I , then &#8741;D(x)&#8741; op &#8805; ku, which is substantially larger than ku d bound given in Lemma 17. The improved bound for x &#8712; X that we show in Lemma 17 is key to obtaining bounds on the curvature constant of F prog-flat over Z which are sufficient for obtaining our desired runtimes (i.e., scaling polynomially only in r &#8902; , not d). We provide the curvature bound as well as different bounds on the regularity of F prog-flat over Z below. Lemma 18. For all z, z &#8242; &#8712; Z with z = (x, S) for x &#8712; X and S &#8712; S as defined in <ref type="bibr">(22)</ref> and for f = F prog-flat defined in <ref type="bibr">(25)</ref>,</p><p>Consequently,</p><p>Proof. Let z, z &#8242; &#8712; Z be arbitrary. Let A be the linear operator such that A(x, S) = slift D x v -S . Let G be the gradient of H * &#951; at Az &#8242; and let H be the Hessian of H * &#951; at Az &#8242; . Note that the chain rule, Fact 1, and that the trace and operator norm are dual imply that, for z = (x, S),</p><p>However, for any (x, S) &#8712; Z = X &#215; S,</p><p>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 v, that &#1013; &#8712; (0, 1), and Lemma 17. Combining these inequalities yields</p><p>Applying the same argument with S = 0 and x =</p><p>follows from Lemma 16.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.3 Matrix step implementation</head><p>In this section, we discuss how to approximate the S block of &#8711;F prog-flat (z) := &#8711;F prog-flat (x, S) within the error allowed by Line 5 and Lemma 15, where (as discussed earlier) we denote our approximation by</p><p>following notation in <ref type="bibr">(26)</ref>. We then give implementation details for computing</p><p>within the error threshold required by Line 5. Our approximately-optimal step matrix W will have the convenient property of coming with an explicit low-rank representation, facilitating faster implementation of future iterations of our subproblem solver. We will give approximation guarantees in a mixed multiplicative-additive format, whose conversion to additive error is facilitated by Lemma 15.</p><p>The main result of this section is the following.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Lemma 19 (S step).</head><p>There is an algorithm which takes as input x &#8712; X , S &#8712; S given as a rank-r factorization,</p><p>and &#945;, &#948; &#8712; (0, 1), and computes W &#8712; S as a rank-q factorization satisfying</p><p>for</p><p>with probability &#8805; 1 -&#948;. Moreover, q = O( C 2 &#8710; 2 ), and the algorithm runs in time</p><p>Approximating the gradient. We begin by bounding the complexity of matrix-vector access to a matrix B &#8776; B -L -R, with a given tolerance for approximation error. Ultimately we will use the approximate gradient</p><p>to implement the update to S in our algorithm. Our access is based on a standard polynomial approximation to the exponential which is well-known in the literature.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Lemma 20 ([2]</head><p>). For &#945; &#8805; 0 and R &#8805; 0, there is a polynomial p of degree</p><p>Applying Lemma 20 twice directly yields our approximation B.</p><p>)), and defining</p><p>Proof. It suffices to provide matrices L, R such that</p><p>Indeed, letting B := L -R, the bound on T mv ( B) is then immediate, and by H&#246;lder's inequality (with &#8741;S &#8242; &#8741; op &#8804; &#8741;S &#8242; &#8741; F &#8804; 2) and the triangle inequality, we also have the desired</p><p>by the definition of T = Tr(L) + Tr(R). We only discuss L, as the case of R is symmetric. We let</p><p>, where p is the polynomial from Lemma 20 with &#945; &#8592; &#8710; 8C . The bound on T mv ( L) follows from the degree of p, and the fact that</p><p>Finally, the claim &#8741; B&#8741; tr &#8804; (1 + &#8710; 8C )T follows from the triangle inequality.</p><p>Approximating the S step. We now build upon the access afforded by Corollary 2 to compute W, our approximate solution to min M&#8712;S &#10216;H, M&#10217;, where H := C T B is our gradient approximation. 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.</p><p>Lemma 21. Let &#945;, &#948; &#8712; (0, 1) and M &#8712; S d&#215;d . There is an algorithm which returns</p><p>Proof. Let Q &#8712; R k&#215;d with independently uniform random unit vector rows in R d scaled down by</p><p>. By the Johnson-Lindenstrauss lemma of <ref type="bibr">[20]</ref>, with probability &#8805; 1 -&#948;, we have for all i &#8712; [d] that</p><p>Therefore, summing for all i &#8712; [d] proves that Tr(QM 2 Q &#8868; ) = F satisfies the desired bound. We can compute MQ &#8868; explicitly in time k &#8226; T mv (M), and computing the Frobenius norm of MQ &#8868; &#8712; R d&#215;k does not dominate the stated running time.</p><p>Lemma 22. Let &#945;, &#948; &#8712; (0, 1), &#8710; &#8805; 0, let H &#8712; S d&#215;d have &#8741;H&#8741; tr &#8804; &#964; , and let W &#8902; := argmin W&#8712;S &#10216;W, H&#10217;. There is an algorithm which with probability &#8805; 1 -&#948; returns W = ZRZ &#8868; satisfying R &#8712; S q&#215;q and Z &#8712; S d&#215;q , with</p><p>in time</p><p>Proof. Note that in closed form, we have W &#8902; = -(1 + &#1013;) H &#8741;H&#8741;F , and the optimal objective value is &#10216;W &#8902; , H&#10217; = -&#8741;H&#8741; F . We first compute F using Lemma 21 such that</p><p>within the allotted time and failure probability &#948; 2 . Then, letting</p><p>Next, let W &#8592; ZZ &#8868; W &#8242; ZZ &#8868; where Z is the result of Lemma 4 with q &#8592; &#8968; 9&#964; 2 2&#8710; 2 &#8969;, &#1013; &#8592; 1 2 , and failure probability &#948; 2 . We output R := Z &#8868; W &#8242; Z and Z, which can be computed within the allotted time. The result follows by combining <ref type="bibr">(33)</ref> with</p><p>Here, we used that &#8741;W &#8242; &#8741; F &#8804; 2 implies &#8804; 9&#964; 2 2&#8710; 2 singular values of W &#8242; are larger than 2&#964; 3&#8710; .</p><p>We make one slight extension to Lemma 22 under implicit access to H.</p><p>Corollary 3. In the setting of Lemma 22, suppose H = 1 A B for an unknown constant A. There is an algorithm which returns W = ZRZ &#8868; with R &#8712; S q&#215;q and Z &#8712; S d&#215;q satisfying the guarantee in <ref type="bibr">(32)</ref> </p><p>Proof. We follow the steps of Lemma 22 exactly, except we instead let</p><p>&#8741; B&#8741; F , again with probability &#8805; 1 -&#948; 2 , using Lemma 21. Because the computation in Lemma 21 is scale-invariant, the distribution of W &#8242; remains unchanged from Lemma 22, and all remaining steps are the same as before.</p><p>We combine the developments of this section to prove Lemma 19.</p><p>Proof of Lemma 19. We define H = C T B as in (31) (using B defined in Corollary 2), and take the step given by Lemma 22 and Corollary 3. Recall from Corollary 2 that &#8741;H&#8741; op &#8804; (1 + &#8710; 8C )C &#8804; 2C, so we can set &#964; = 2C in Lemma 22. Moreover, in the context of Corollary 3,</p><p>The runtime bound then follows from Corollary 3. Finally, the rank bound q follows from (32).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.4 Vector step implementation</head><p>In this section, analogously to Appendix C.3, we discuss how to approximate the X block of &#8711;f (z) with a vector h, and give implementation details for computing w &#8776; min v&#8712;X &#10216;h, v&#10217; .</p><p>We crucially use the characterization in Fact 3, which implies this is a weighted matching problem.</p><p>The main result of this section is the following.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Lemma 23 (X step).</head><p>There is an algorithm which takes as input x &#8712; X , S &#8712; S given as a rank-r factorization,</p><p>and &#945;, &#948; &#8712; (0, 1), and computes y &#8712; X satisfying &#10216;y, h&#10217; &#8804; (1 -&#945;)argmin y &#8902; &#8712;X &#10216;y &#8902; , h&#10217; ,</p><p>with probability &#8805; 1 -&#948;. The algorithm runs in time</p><p>Approximating the gradient. Recall that [&#8711; x f (x, S)] &#953; = -1 + C T &#10216;B, E &#953; &#10217; for all &#953; &#8712; I, where again B = L -R and T = Tr(L) + Tr(R) as in Appendix C.3. To produce our approximation h &#8776; &#8711; x f (x, S), we use the following helper guarantee.</p><p>Lemma 24 (Lemma 20, <ref type="bibr">[38]</ref>). Let &#1013;, &#1013; &#8242; , &#948; &#8712; (0, 1), {A i } i&#8712;[n] &#8712; S d&#215;d , R &#8805; log 1 &#1013; &#8242; , and let M &#8712; S d&#215;d satisfy &#8741;M&#8741; op &#8804; R. There is an algorithm which computes</p><p>With Lemma 24 established, our gradient approximation follows straightforwardly, Corollary 4. Let x &#8712; X , S &#8712; S satisfy &#8741; 1 &#951; (D( x v ) -S)&#8741; op &#8804; R, and let &#8710; &#8805; 0 and &#948; &#8712; (0, 1). We can compute h &#8712; R I in time</p><p>such that with probability &#8805; 1 -&#948;,</p><p>Proof. Define T as in Corollary 2 throughout the proof. We let h &#8712; R I satisfy h I = -1 + C(V&#953;-U&#953;) T for all &#953; &#8712; I, for V, U &#8712; R I to be defined, which we can compute within the allotted time. Since &#8741;x &#8242; &#8741; 1 &#8804; k for all x &#8242; &#8712; X , it suffices to show that &#8741;h -&#8711; x f (x, S)&#8741; &#8734; &#8804; &#8710; 2k . To this end, throughout this proof let M := 1 &#951; (D( x v ) -S), and define <ref type="figure">M</ref>), E &#953; &#10217; , for all &#953; &#8712; I. By our choice of h &#953; , we have</p><p>We take {V &#953; } &#953;&#8712;I to be the approximations given by Lemma 24 with the set of matrices {E &#953; } &#953;&#8712;I and M, &#948; &#8592; &#948; 2 , and &#1013;, &#1013; &#8242; &#8592; &#8710; 4kC ; we define {U &#953; } &#953;&#8712;I identically, except we apply Lemma 24 with -M instead of M. Note that these approximations yield</p><p>as desired. The first inequality used the guarantee in Lemma 24 with H&#246;lder's inequality, and the second used the definition of T = Tr exp(M) + Tr exp(-M) and Tr(|E &#953; |) = 2. Finally, the runtime follows directly from the bound in Lemma 24.</p><p>Approximating the x step. Given our estimate h from Corollary 4, our approximate linear optimization oracle follows from a known result on approximating maximum weighted matchings.</p><p>Proposition 5 (Theorem 3.12, <ref type="bibr">[22]</ref>). Let G = (L &#8746; R, E) be a bipartite graph, let w &#8712; R E be a set of weights, and let m := |E|. There is an algorithm which computes f &#8712; M, defined in <ref type="bibr">(23)</ref>, such that &#10216;w, f &#10217; &#8804; (1 -&#945;) min f &#8902; &#8712;M &#10216;w, f &#8902; &#10217;, in time O( m &#945; log 1 &#945; ). We remark that Proposition 5 is stated in <ref type="bibr">[3]</ref> for maximization of linear objectives in nonnegative weight vectors w, i.e. maximum weight matchings. However, it is straightforward to see that this implies the same result for minimization of linear objectives in arbitrary cost vectors w &#8712; R E , by first dropping any positive coordinates (which can only increase the objective &#10216;w, x&#10217; when x is coordinatewise nonnegative), and then negating the result of <ref type="bibr">[22]</ref>. Because our access to our cost vector w of interest is implicit, we make a simple observation which extends Proposition 5. Proof. This follows directly from scale-invariance of the guarantees in Proposition 5.</p><p>We now use these developments to give a short proof of Lemma 23.</p><p>Proof of Lemma 23. We define h &#953; = -1 + C(V&#953;-U&#953;) T entrywise (using notation in Corollary 4), and take the step given by Proposition 5 and Corollary 5. The runtime follows immediately from these results.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C.5 Runtime analysis for subproblem solver</head><p>In this section, we put together the pieces and provide a runtime bound for approximately solving <ref type="bibr">(25)</ref>. We first provide Lemma 25 which provides the bounds for implementing Line 5 for Z and then use this to provide the main result for approximately solving, (25), Proposition 6. Lemma 25. There is an algorithm that for input z = (x, S) &#8712; X &#215; S where S is given as a rank-r factorization, R &#8805; &#8741; 1 &#951; (D( x v ) -S)&#8741; op , &#8710; &#8712; [0, C], and &#948; &#8712; (0, 1) outputs &#7825; &#8712; Z with &#7825; = (y, W) &#8712; X &#215; S where W is output as a rank O( C 2 &#8710; 2 ) factorization such that with probability &#8805; 1 -&#948;, &#10216;&#8711;F prog-flat (z), &#7825;&#10217; &#8804; min</p><p>Proof. Applying Lemma 19 and Lemma 23 yields that for any &#945; S , &#945; X &#8712; (0, 1] and &#8710; &#8712; [0, C] (which we set later) we can obtain with probability &#8805; 1 -&#948; (by a union bound) W &#8712; S as a rank-q factorization for q = O( C 2 &#8710;2 ) and H &#8712; S d&#215;d satisfying (Lemma 19) &#10216;H, W&#10217; &#8804; (1 -&#945; S ) min S &#8242; &#8712;S &#10216;H, S &#8242; &#10217; + &#8710; and |&#10216;H -&#8711; S F prog-flat (x, S), z &#8242; &#10217;| &#8804; &#8710; for all S &#8242; &#8712; S , and y &#8712; X and h &#8712; R I satisfying (Lemma 23)</p><p>Conditioning on these events and applying Lemma 15 and Lemma 18 yields that &#10216;&#8711; S F prog-flat (x, S), W&#10217; &#8804; min</p><p>and &#10216;&#8711; X F prog-flat (x, S), y&#10217; &#8804; min</p><p>, 1} and &#8710; = &#8710; 24 then yields the result.</p><p>We now prove a more quantitative variant of Proposition 2.  Proof. Throughout the proof let f := F prog-flat for simplicity. Our algorithm computes z (T ) = ApproxFrankWolfe(f, Z, T,</p><p>), where we note that C f,Z need not necessarily be computed. By Lemma 18 we know that C f,Z &#8804; 2C&#951;R 2 &#951; and consequently Proposition 4 implies that so long as each iteration of Algorithm 4 is implemented to the desired accuracy,</p><p>To implement the method we apply Lemma 25 with (&#8710;, &#948;) in the lemma set to (</p><p>. This suffices to have the desired output with the desired probability by union bound.</p><p>It remains to bound the computational cost of this algorithm and the rank of the output. Note that</p><p>&#8741; op for all (x &#8242; , S &#8242; ) &#8712; X &#215; S (by Lemma 17, see e.g., <ref type="bibr">(28)</ref>). Additionally, if we initialize the method with (0 d , 0 d&#215;d ) then we see that the rank of the S component of each computed s (t) is O( C 2 &#1013; 2 ) and that each S component of each z (t) can be maintained as a rank O(t &#8226; C 2 &#1013; 2 ) 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 .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>D Postprocessing</head><p>In this section, we give the second main component of our overall matrix completion algorithm in Algorithm 7. This piece takes as input two matrices M, M &#8902; &#8712; S d&#215;d which are close on a submatrix (where we only have noisy semi-random observations from M &#8902; ). It then performs a sequence of postprocessing steps to produce a matrix M such that M is close to M &#8902; on the full matrix, as measured in the &#8467; &#8734; norm. For the first step of Algorithm 7, we simply reuse our earlier subroutine Sparsify (Algorithm 1), whose guarantees we recall here for convenience. In Appendix D.1, we prove a 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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>D.1 Localizing errors via spanning subsets</head><p>Before giving our next postprocessing steps, we prove a structural property, which can be stated concisely in the language of volumetric spanners <ref type="bibr">[5]</ref>. Following definitions in <ref type="bibr">[7]</ref>, Lemma 26 shows any n-sized set in R d admits a 2d-approximate &#8467; 1 -volumetric spanner of size d + 1. To see this, fix i &#8712; [d + 1], and let the (d -1)-dimensional plane spanned by the other d points be P . If any other v j lies outside the two planes parallel to P at equal distances, such that one contains v i , then including v j would produce a 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 &#8467; 1 norm, applied to the coefficients defining this simplex.</p><p>Using Lemma 26, we obtain the following corollary on boundedness of large index subsets. This also implies every row of D can be written as a linear combination of the row vectors {D j: } j&#8712;T , such that the &#8467; 1 norm of the linear combination coefficients is at most 2r. Now, let S = [d] \ R, where R consists of all indices i &#8712; [d] such that |[D] ji | &#8805; &#964; for some j &#8712; T ; by assumption, |R| &#8804; (r + 1)s, giving the size bound. Take some row D i: for i &#8712; [d], and let D i,S be the restriction of this row to columns in S. By applying the given linear combination to the rows {D j,S } j&#8712;T , all entrywise at most &#964; in magnitude, the triangle inequality shows &#8741;D i,S &#8741; &#8734; &#8804; 2r&#964; as claimed.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>D.2 Testing columns</head><p>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 uses our structural claim in Lemma 27.</p><p>Algorithm 5: Test(M, j, &#981;, q, &#948;) </p><p>Proof. Let U &#8712; R d&#215;r be an orthonormal basis for span(M) with rows {u i } i&#8712;[d] , so that x = Uv with &#8741;x&#8741; 2 = &#8741;v&#8741; 2 . The conclusion follows from</p><p>Lemma 29. Let V &#8838; R d be a &#181;-incoherent subspace of dimension r, and let B V &#8712; R d&#215;r be an orthonormal basis for V . Let S &#8838; [d] have |S| &#8805; (1 -1 3&#181;r )d. Then the following properties hold.</p><p>The lower bound then yields the first statement. Now, the matrix M := [B V ] S: A -1 2 has orthonormal columns, and the same span as [B V ] S: . Furthermore, by incoherence and the fact that A &#10928; 2 3 I r , all of the rows i &#8712; S of M have</p><p>Finally, |S| &#8805; 2d 3 (since &#181; &#8805; 1). Combining these claims proves the second statement.</p><p>We also include the following application of the matrix Bernstein inequality from <ref type="bibr">[43]</ref>.</p><p>Lemma 30 (Lemma 12, <ref type="bibr">[43]</ref>). Let &#948; &#8712; (0, 1) and let V &#8838; R d be a &#181;-incoherent subspace of dimension r. Let B V be an orthononormal basis for V , with rows</p><p>Now, we are ready to analyze our testing algorithm and prove that it has the desired behavior.</p><p>Lemma 31. Let M &#8902; &#8712; S d&#215;d be rank-r &#8902; and &#181;-incoherent, and let M &#8712; S d&#215;d be rank-r for r &#8805; r &#8902; . For s, &#964; &gt; 0, assume M -M &#8902; has at most s entries with magnitudes &#8805; &#964; in each row. Then with probability 1 -&#948;, if we run Algorithm 5 with parameters q, &#981; and j &#8712;</p><p>Algorithm 5 has the following behavior.</p><p>We consider the two claims separately.</p><p>True case. Suppose that &#8741;M &#8902; :j -M :j &#8741; &#8734; &#8804; 4r &#8902; &#964; &#8730; &#181;r &#8902; . We will prove that each run of the inner loop of the algorithm succeeds with probability &#8805; 4  5 . By using Lemma 27 with D &#8592; M &#8902; -M, and applying our upper and lower bounds on q, there exists S &#8838; [d] with |S| &#8805; (1 -1 3&#181;r &#8902; )d such that for all i &#8712; S, &#8741;M &#8902; :i -M :i &#8741; &#8734; &#8804; 4r &#8902; &#964; . Next, by Lemma 30 and incoherence of M &#8902; , with probability 9  10 ,</p><p>This means there exists v &#8712; R T &#8745;S with &#8741;v&#8741; 2 &#8804; 3&#181;r &#8902; 2qd , such that (V &#8902; :T &#8745;S ) &#8868; v = (V &#8902; :j ) &#8868; , which also means M &#8902; :T &#8745;S v = M &#8902; :j . We thus have for this vector v,</p><p>where we used that with probability 9 10 , |T | &#8804; 2qd. By a union bound, each independent test thus increments c with probability 4  5 over the randomness of T , so a Chernoff bound gives the claim. False case. Next, suppose that &#8741;M &#8902; :j -M :j &#8741; &#8734; &#8805; 10&#964; qd&#181;r &#8902; , and again consider a single run of the algorithm. Let i 0 &#8712; [d] be the entry such that |M &#8902; i0j -M i0j | &#8805; 10&#964; qd&#181;r &#8902; . First, with probability at least 9  10 over the randomness of the inner loop, for all j &#8242; &#8712; T ,</p><p>because by assumption, there are at most s indices j &#8242; where |M &#8902; i0,j &#8242; -M i0,j &#8242; | &#8805; &#964; . Since qs &#8804; 1 20 , there is at least a 9  10 probability that none of these indices is selected in T by a Chernoff bound. As before, with probability 9  10 , there is a vector v with &#8741;v&#8741; 2 &#8804; 3&#181;r &#8902; 2qd such that M &#8902; :T v = M &#8902; :j . Also, again, with probability 9  10 , we have |T | &lt; 2qd. Now let R &#8838; [d] be the set of rows i such that</p><p>Algorithm 6: Fix(O sr p ( M), M, T, &#981;, q, &#948;)</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Fixing columns via regression</head><p>We now complete our postprocessing algorithm. Given an estimate M that is entrywise close to M &#8902; , except for a small number of potentially large errors in each row and column, we first run Algorithm 5 to identify a set 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).</p><p>Lemma 33. Let M &#8902; &#8712; S d&#215;d be rank-r &#8902; and &#181;-incoherent, and let M = M &#8902; + N for N &#8712; S d&#215;d with &#8741;N&#8741; &#8734; &#8804; &#964; . Let M &#8712; S d&#215;d be rank-r for r &#8805; r &#8902; . For s, &#964; &gt; 0, assume [M -M &#8902; ] :T has at most s entries larger than &#964; in each row and column. Assume</p><p>Then with probability 1 -&#948;, if we run Algorithm 6 with parameters q, &#981; such that</p><p>Proof. First, by Lemma 27 and applying our upper and lower bounds on q, there is a subset T &#8242; &#8838; T with |T &#8242; | &#8805; (1 -1 3&#181;r )d such that for all j &#8712; T &#8242; , &#8741;M :j -M &#8902; :j &#8741; &#8734; &#8804; 4r&#964; . Next, by Lemma 31, with probability 1 -&#948; 10 , we have B &#8745; T &#8242; &#8838; G. Thus, by applying Lemma 30 with S &#8592; T &#8242; and p &#8592; q, we have that with 1 -&#948; 10 probability, for any j &#8712; [d], there is a vector u j with &#8741;u j &#8741; 2 &#8804; 3&#181;r 2qd such that M &#8902; :G u j = M &#8902; :j . Also, by Lemma 31, we have with probability 1 -&#948; 10 that &#8741;M &#8902; :G -M :G &#8741; &#8734; &#8804; 10&#964; qd&#181;r. Now fix a j &#8712; [d] and consider the execution of the loop in Lines 7 to 10 for this index j. Consider u j as a candidate solution to the optimization problem. We have</p><p>where we use that with 1 -&#948; 10 probability, |G| &#8804; 2qd. Thus, the solution v j in Line 9 must have</p><p>This implies that</p><p>Next, recall that span(M &#8902; ) is &#181;-incoherent. Let B &#8712; R d&#215;r have orthonormal columns with span(B) = span(M &#8902; ), with rows {b i } i&#8712; <ref type="bibr">[d]</ref> . By Lemma 30, with probability 1 -&#948; 10d 2 , S j contains a subset S &#8242; j such that |S &#8242; j | &#8804; 2pd and</p><p>Thus, for all vectors z &#8712; span(M &#8902; ),</p><p>where the first line used Lemma 28. Finally, recall from ( <ref type="formula">41</ref>) that for v j to be an optimal solution, we must have &#8741;v j &#8741; &#8734; &#8804; 100&#181; 1.5 &#8730; r. Since |G| &#8804; 2qd, we have the desired bound for column j &#8712; [d]:</p><p>Union bounding all of the failure probabilities then completes the proof. Remark 3. Similarly to Remark 2, we note that the proof of Lemma 33 is tolerant to an error of &#964; qd(&#181;r) 1.5 for the problem in Line 9, because this implies (41) holds up to a negligible constant factor, which does not affect correctness of the rest of the proof. Line 9 can again be solved to this accuracy in time O(d &#8226; poly(&#181;r log( d &#948; ))), with failure probability &#948;, as described in Lemma 32. Finally, we put everything together and give our full postprocessing procedure. Proposition 3. Let M &#8902; &#8712; S d&#215;d be rank-r &#8902; and &#181;-incoherent, and let M = M &#8902; + N for N &#8712; S d&#215;d with &#8741;N&#8741; &#8734; &#8804; &#8710; for some &#8710; &#8805; 0. Let M &#8712; S d&#215;d be given as a rank-r decomposition, with r &#8805; r &#8902; . Further, for &#947; &#8712; (0, 1) suppose M and M &#8902; are d&#8710;-close on a &#947;-submatrix. Finally, assume &#947; &#8804; 1 10 4 &#181;r log <ref type="bibr">(d)</ref> .</p><p>Then for any &#948; &#8712; (0, 1) if p &#8805;  The algorithm runs in time O(mQ) where m is the total number of observed entries.</p><p>Proof. We inductively verify the conditions of Corollary 1 are satisfied whenever SRPartialCompletion is called and the conditions of Proposition 3 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 1 are satisfied when SRPartialCompletion is called, we know the output M has rank r &#8804; r &#8902; &#8226; P o (1) and is D &#945; -close to M &#8902; on a 1 10 6 &#181;P 2 submatrix. Now this implies that the hypotheses of Proposition 3 are satisfied when we call Postprocess and thus we get that</p><p>.</p><p>Since M &#8902; is rank-r &#8902; , we have</p><p>This now implies that the hypotheses of Corollary 1 are satisfied at the beginning of the next iteration (unless D &#8804; &#8710;dQ 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 &#948;. As long as none of the subroutines fails, the above argument implies the output must satisfy</p><p>and that M has rank at most Q. Note that by Lemma 2, we can simulate all of the observations used in the algorithm with a single sample O sr p (M &#8902; + N) with reveal probability p &#8805; poly r &#8902; , &#181;, log</p><p>The overall runtime guarantee follows by combining the runtime guarantees of Corollary 1, Proposition 3, and the PCA step (see Remark 4).</p><p>NeurIPS Paper Checklist</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">Claims</head><p>Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?</p><p>Answer: [Yes]</p><p>Justification: As stated in the abstract and introduction, this is a theory paper where we give a new algorithm for semi-random matrix completion and prove that it achieves improved guarantees in terms of runtime, accuracy and noise tolerance.</p><p>Guidelines:</p><p>&#8226; The answer NA means that the abstract and introduction do not include the claims made in the paper.</p><p>&#8226; 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.</p><p>&#8226; The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.</p><p>&#8226; It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Limitations</head><p>Question: Does the paper discuss the limitations of the work performed by the authors?</p><p>Answer: [Yes] Justification: We discuss the modeling assumptions and acknowledge that since this is a 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.</p><p>Guidelines:</p><p>&#8226; 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.</p><p>&#8226; The authors are encouraged to create a separate "Limitations" section in their paper.</p><p>&#8226; 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 on how these assumptions might be violated in practice and what the implications would be.</p><p>&#8226; The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.</p><p>&#8226; The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.</p><p>&#8226; The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.</p><p>&#8226; If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.</p><p>&#8226; The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.</p><p>&#8226; The full details can be provided either with the code, in appendix, or as supplemental material.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="7.">Experiment Statistical Significance</head><p>Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?</p><p>Answer: [NA]</p><p>Justification: The paper does not include experiments.</p><p>Guidelines:</p><p>&#8226; The answer NA means that the paper does not include experiments.</p><p>&#8226; The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.</p><p>&#8226; 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).</p><p>&#8226; The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)</p><p>&#8226; The assumptions made should be given (e.g., Normally distributed errors).</p><p>&#8226; It should be clear whether the error bar is the standard deviation or the standard error of the mean.</p><p>&#8226; It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.</p><p>&#8226; For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).</p><p>&#8226; If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="8.">Experiments Compute Resources</head><p>Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?</p><p>Answer: [NA]</p><p>Justification: The paper does not include experiments.</p><p>Guidelines:</p><p>&#8226; The answer NA means that the paper does not include experiments.</p><p>&#8226; The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.</p><p>&#8226; The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.</p><p>&#8226; 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 make it into the paper).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="9.">Code Of Ethics</head><p>&#8226; At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="14.">Crowdsourcing and Research with Human Subjects</head><p>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 as details about compensation (if any)?</p><p>Answer: [NA]</p><p>Justification: The paper does not involve crowdsourcing nor research with human subjects.</p><p>Guidelines:</p><p>&#8226; The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.</p><p>&#8226; Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.</p><p>&#8226; According to 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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="15.">Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects</head><p>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?</p><p>Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects.</p><p>Guidelines:</p><p>&#8226; The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.</p><p>&#8226; Depending on 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.</p><p>&#8226; 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.</p><p>&#8226; For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="9" xml:id="foot_0"><p>This norm distortion is the main source of poly(r) losses in our guarantees compared to the<ref type="bibr">[43]</ref> algorithm.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="10" xml:id="foot_1"><p>We perform minor changes to the names of the variables, choice of offsets, etc. to facilitate and simplify the use of<ref type="bibr">[35]</ref> to obtain our results.</p></note>
		</body>
		</text>
</TEI>
