Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting

Authors: jonathan a kelner
jerry  li
allen  liu
aaron  sidford
kevin  tian
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:47:11

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

Main paper: 
 introduction: 
 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.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 ∈ R d×d where r ≪ d, 6 given a small (typically sublinear) number of entries revealed independently and at random. In a seminal line of work [13, 11, 12, 61] , it was shown that under natural structural assumptions on M, one can fully recover M given ≈ dr randomly revealed entries in polynomial time, via semidefinite programming (SDP). Subsequently, there has been extensive work attempting to improve upon statistical and computational guarantees for matrix completion. In an oversimplification of the literature (see Section 1.3 for a more detailed and nuanced discussion), this has resulted in two categories of matrix completion algorithms.• SDP-based algorithms achieve the nearly-optimal sample complexity, but are based on solving SDPs, which requires time Ω(d 3.5 ) even with state of the art solvers [39, 34] .• First-order iterative methods require a slightly higher sample complexity, namely, they require m ≈ pd 2 revealed entries for an observation probability p = Ω(poly(r, log d)) • 1 d . However,The main result of [17] is an efficient algorithm for semi-random matrix completion, albeit with some important caveats, as we discuss shortly. Roughly speaking, for ϵ ∈ (0, 1), [17] gave an algorithm which, given observations of rank-r M with condition number κ from the p-semi-random model for p = 1 d • O(poly(r, κ, 1 ϵ )), outputs M ′ so that ∥M ′ -M∥ 2 F ≤ ϵ∥M∥ 2 F with high probability. Moreover, it runs in nearly-linear time O(m • poly(r, κ, 1 ϵ )), where m is the number of revealed entries. While this is a promising first step towards matrix completion in the semi-random model, it leaves several important questions unanswered.• High-accuracy recovery. Both the sample complexity and runtime of the algorithm in [17] depend polynomially on ϵ -1 . In particular, the algorithm cannot recover the matrix M to ϵ -1 = poly(d) levels of precision in nearly-linear time. Thus, even in the standard setting where we assume that the bit complexity of the entries of M are polynomially bounded, [17] cannot achieve exact 7 Here, and throughout the paper, we use the notation O(f ) := O(f log O(1) f ) and similarly define Ω. 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 Lemma 2) . There is precedent from the literature on fully-random matrix completion that the inability to sample split causes analysis issues (see, e.g., Section 3 of [61] ); extending 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).• Condition number dependence. Another important downside of the [17] algorithm's guarantee is its polynomial dependences on κ in both the sample complexity and runtime. No dependence on κ is required information-theoretically, or by the SDP-based methods. This aspect also seems somewhat inherent to the non-convex iterative method used in [17] .• Noise tolerance. Finally, the guarantees in [17] 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.Our main result is a new fast algorithm for semi-random matrix completion that addresses all three of the aforementioned issues. Specifically, we show the following main result.Theorem 1 (informal, see Theorem 2) . Let M ⋆ ∈ R d×d be a symmetric, rank-r, µ-incoherent matrix, let symmetric N ∈ R d×d satisfy ∥N∥ ∞ ≤ ∆, and let M = M ⋆ + N. Let ϵ ∈ (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, µ, log( d ϵ )), and outputs M as a rank-Q factorization such that with high probability,∥M -M ⋆ ∥ ∞ ≤ Q (∆ + ϵ ∥M ⋆ ∥ ∞ ) .The algorithm runs in nearly-linear time O(mQ) where m is the number of revealed entries.Here, ∥•∥ ∞ refers to the elementwise ℓ ∞ norm of a matrix, and ∥•∥ F refers to the Frobenius norm. We pause to comment on Theorem 2. First, in the noiseless setting, i.e., when ∆ = 0, our algorithm has a polylogarithmic dependence on ϵ -1 , and thus achieves high-accuracy recovery in nearly-linear time.In particular, as long as the bit complexity of the underlying matrix is polynomially bounded, we achieve exact recovery in nearly-linear time. Moreover, our rate has no dependence on the condition number κ. In both of these aspects, our result qualitatively improves upon [17] , while retaining a nearly-linear runtime and O(d • 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 [43] ).Finally, we observe that our guarantee applies to the noisy setting, i.e., ∆ > 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 ℓ ∞ norm of the noise matrix N; moreover, the overhead is a polynomial of only r log( d ϵ ), a preferable guarantee to the poly(d) overheads known to be achievable in the standard, fully random setting by semidefinite programming [11] .We do note that in the standard matrix completion setting, error guarantees are typically phrased in terms of the Frobenius norm of the noise N [11, 43] . However, in the semi-random setting, some measure of the "element-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 [42] .We achieve these results via a fundamentally different approach than the prior work of [17] , detailed in Section 2. At a (very) high level, [17] relies on finding a single reweighting of the revealed entries of M that is good in a global sense. This roughly corresponds to finding a mask of the revealed entries, so that the masked matrix is guaranteed to be a good spectral approximation of the ground truth matrix. Given such a mask, [17] then shows that 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 ϵ ) 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 + ϵ)-multiplicative spectral approximation to the ground truth. However, all known techniques for finding such a high-quality spectral approximation require a poly( 1 ϵ ) dependence in both sample complexity and runtime.We instead devise an iterative method that is guaranteed to make progress, assuming that the iterate satisfies a local progress criterion. We then find a local reweighting of the matrix which allows us to find a step which satisfies this criterion. While this local progress criterion is much more involved to state, and this reweighting must now be done every iteration (rather than just once at the beginning of the algorithm), this framework has an important advantage over the global criterion used previously.Critically, now each step of our method need only seek a reweighting which achieves a constant factor of relative progress to the target matrix. Thus, rather than needing a (1 + ϵ)-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 ϵ . Our algorithm builds upon the short-flat decomposition-based approach to designing iterative methods for linear inverse problems introduced in [42] , and specialized in [43] to matrix completion in the standard setting. However, there are significant technical challenges in adapting this framework to semi-random models. At a high level, the matrix completion problem is not well-conditioned, so a crucial step in the [43] algorithm is dropping rows and columns of a difference matrix (between an iterate and the target) which are estimated as too large. Random observations (held out via sample splitting) are then used in matrix concentration inequalities to estimate the difference matrix on the remaining indices, and dropped indices are later recovered.Unfortunately, all of these steps crucially rely on independent sampling and hence break in the presence of 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.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., [41, 60, 59, 63] . [62] in the context of collaborative filtering, e.g., for the Netflix Prize [6] . Since then, it has found applications in various areas, such as signal processing [46, 64, 57] , social network analysis [47] , causal inference [4] , and most recently, AI alignment [1] . In a seminal line of work, [13, 11, 61, 12, 16] demonstrated that SDPs based on nuclear norm minimization can solve matrix completion with sublinear sample complexity, and in polynomial time. Another line of work focuses on first-order iterative methods for matrix completion, see e.g., [44, 31, 32, 33, 36, 74, 67, 18, 72, 30] . These works demonstrate that optimization frameworks, such as alternating minimization, can provably and efficiently recover the true matrix. Finally, yet another line of work seeks to understand the non-convex landscape of descent-based methods for matrix completion [65, 21, 28, 40, 73, 40, 73, 71] . In terms of theoretical runtimes, the state of the art O(dr 3+o (1) ), is given in [43] . 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 [17] , none of these fast methods are known to succeed in the presence of semi-random noise.Semi-random models. Semi-random models were first introduced in a pair of seminal papers [9, 24] , in part as a means to test whether learning algorithms which succeed under random models generalize to more realistic generative modeling assumptions. Most early work on semi-random models focused on understanding semi-random variants of various constraint satisfaction problems, see e.g. [25, 24, 45, 15, 48, 50] . More recently, they have also been studied in the context of learning theory, in the context of clustering problems [23, 53, 49, 14, 29, 51, 52, 55] , sparse and overcomplete linear regression [37, 42] , planted clique [54, 10] , and more [27, 8] .Of particular interest to us is the recent line of work on developing fast learning algorithms in semi-random models [17, 42, 43, 27, 8] . The closest and most direct comparison to our work is the aforementioned [17] , which we quantitatively improve upon in a number of ways. It is worth noting that the specific poly(r) ≈ r 6 dependence in the sample complexity of [17] is lower than in Theorem 1. We view our result as a promising proof-of-concept of the tractability of semi-random matrix completion via fast algorithms; both our dependence and the dependence of [17] are somewhat large at the moment, limiting immediate practical deployment, but we believe that it is an interest direction for future research to tighten dependencies on problem parameters and seek more practical algorithms.i ∈ [d], j∈[d]|(i,j)∈Ω w ij [M -M ⋆ ] 2 ij = O( 1 d ).2. There exists S, F ∈ R d×d with D = S + F, ∥S∥ F ≤ 1, and ∥F∥ op = O(r -1 2 ).3. For a sufficiently small constant c, ⟨D, M -M ⋆ ⟩ = (i,j)∈Ω w ij [M -M ⋆ ] 2 ij ≥ 1 -c.Item 1 serves to ensure our step D is sufficiently spread out amongst its rows and columns, which serves two roles: it bounds how much progress is lost when excluding indices, and enforces crucial problem regularity for our reweighting optimization algorithm. On the other hand, Items 2 and 3 are the standard criteria for making iterative progress through the short-flat framework of [42, 43] . It is straightforward to see that the ideal candidate1 p [M -M ⋆ ] Ω ⋆ ∩(S×S)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).A key technical contribution of this work is a nearly-linear time algorithm finding a reweighting D(w) := (i,j)∈Ω w ij [M -M ⋆ ] ij that meets our progress criteria. Due to our focus on fast algorithms, we require this step to run in O(|Ω| • poly(r)) time. Our strategy is to form a joint objective over w obeying Item 1, and ∥S∥ F ≤ 1, of the formEQUATIONHere, the parameter C is used to trade off the progress objective ⟨D(w), M -M ⋆ ⟩ (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 × S be the product space between w ∈ R Ω satisfying Item 1 and short matrices S ∈ R d×d , we show that finding (w, S) ∈ Z with low suboptimality error in F prog-flat is enough to make progress through Lemma 7.We optimize (2) by carefully applying a Frank-Wolfe method due to [35] . While naï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 ≈ poly(r) required for nearly-linear time algorithms). However, we leverage that the analysis in [35] shows that weaker regularity conditions, namely bounds on the curvature constant, suffice for efficient convergence of an iterative method. Specifically, we use the structure of our constraint set W 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., Lemma 18) to remove a d factor from the naï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 [22] , 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.One other technical hurdle arises in implementing this framework for finding a reweighting: the existence of w ⋆ satisfying Items 1, 2, and 3 relies on having a good estimate of the current distance ∥M -M ⋆ ∥ 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 ⋆ . 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 ⋆ exists), or a "descent" step (when we find a good solution to (2)).Recovering dropped rows and columns. Finally, we briefly discuss how to post-process an estimate M that is close to M ⋆ on a large submatrix to recover dropped rows and columns. The high-level outline is similar to [43] , where we aim to find 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 ℓ 2 , since a semi-randomness could drastically distort the empirical ℓ 2 error by adversarially revealing entries. We rely on a structural result using tools from the theory on volumetric spanners [5, 7] (see Lemma 27) showing that large entrywise errors must be localized to a small submatrix. At this point, we set up ℓ ∞ regression problems to identify verified indices, solvable in nearly-linear time using recent advances in linear programming [69] . Importantly, the overhead in the error guarantee of this recovery step is only 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.12 ), we call Sparsify on (our semi-random access to) the matrixD = M ⋆ + N -M with parameters U , τ ← √ θ5d , γ ← γ sub + 10 r θ , p ← p, and δ ← δ 5 . We then return the new row subset U ′ ⊆ U . We call this case the "drop" case.2. Otherwise, we update to M + ZZ ⊤ SZZ ⊤ , where Z ∈ R d×2r is the output of Lemma 4 with parameters δ ← δ 5 , ϵ ← 1 2 , M ← S, and q ← 2r. We call this case the "descent" case. We first analyze the drop case. We claim that if V > -(1 -11ϵ 12 ), it could not be the case that ( 14) held. To see this, suppose (14) held. Then, with probability ≥ 1 -δ 5 (due to our lower bound (4) on p), Lemma 11 provides us (w ⋆ , S ⋆ ) ∈ W ρ × S satisfyingD(w ⋆ ) = S ⋆ + F ⋆ , ⟨v, w ⋆ ⟩ ≥ 1 - ϵ 2 , for ∥S ⋆ ∥ F ≤ 1 + ϵ, ∥F ⋆ ∥ op ≤ γ sub ϵ 4 √ r .In fact, w ⋆ is only supported on Ω, the fully random coordinates. By using Fact 1, we conclude thatF (w ⋆ , S ⋆ ) ≤ -1 - ϵ 2 + C ∥F ⋆ ∥ op + η log(2d) ≤ -1 - ϵ 2 + Cγ sub ϵ √ r + ϵ 24 ≤ -1 - 3ϵ 4 .Therefore, any ϵ 12 -approximate minimizer (w, S) to F will satisfy F (w, S) ≤ -(1 -5ϵ 6 ). Finally, since we assumed our computed value V satisfies |V -F (w, S)| ≤ ϵ 12 , this contradicts V > -(1 -11ϵ 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 ϵ ← ϵ 36 , proving correctness of the "drop" case with the stated parameters.Next, suppose we are in the descent case, meaning we have (w, S) ∈ W ρ × S satisfying F (w, S) ≤ -(1 -ϵ). By nonnegativity of the second summand in the definition of F , this showsD, D(w) = ⟨v, w⟩ ≥ 1 -ϵ.Moreover, because ⟨v, w⟩ ≤ dρ = ϵ 2γ by the definition of W ρ , we haveEQUATIONwhere we used Fact 1 in the first inequality. Lemma 7 then yields correctness of the "descent" case.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,k = ϵ 2γ sub , R η = O r log(d) γ 3 sub ϵ 2 , and T = O r2 log(d) γ 6 sub ϵ 4 .Therefore, by our choices of C, η from before, the cost of Proposition 6 for δ 5 failure probability isO m + dr 3 log(d) γ 8 sub ϵ 6 • r4 log(d) γ 11.5 sub ϵ 8 log 1.5 d δγ sub .Next, consider the cost of obtaining V satisfying |V -F (w, S)|. We can explicitly compute the term ⟨v, w⟩, and because ηC log(2d) ≤ ϵ 24 , it suffices to obtain an ϵ 24C = ϵγsub 12r 1/2 -additive approximation to ∥ D(w) -S∥ op by Fact 1. The guarantees of Proposition 6 give that ∥ D(w) -S∥ op ≤ 2ϵ r1/2 (see (21) ). Therefore, we may call Lemma 4 with q ← 1, ϵ ← γsub 24 , and δ ← δ 6 , in time which does dominate the above, using the rank-O( r2.5 log(d) γ 6 sub ϵ 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 ϵ and q = 2r, does not dominate Proposition 6. The claimed runtime follows by combining these bounds.Finally, the failure probability comes from a union bound over Lemma 11, Lemma 14, the subroutine in Proposition 6, and our two calls 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 δ 5 .By iterating on Proposition 1, we provide our full partial completion method, Algorithm 3.Corollary 1. Let M, M ⋆ ∈ S d×d be rank-r ⋆ , and suppose ∥M -M ⋆ ∥ F ≤ ∆. Let α ≥ 250 and δ, γ tot ∈ (0, 1 10 ). Algorithm 3 uses one call to O sr p (M ⋆ + N), where for appropriate polynomials,∥N∥ ∞ ≤ ∆ d • poly( r ⋆ γtot log( d δ )) • α 1+o(1) , p = poly( r ⋆ γtot log( d δ )) • α o(1) d ,and computes a rank-r ⋆ • α o(1) -matrix M ′ , such that with probability ≥ 1 -δ, M ′ and M ⋆ are ∆ α -close on a γ tot -submatrix. The runtime of the algorithm is mα o (1) • poly( r ⋆ γtot log( d δ )), where m is the number of observed entries upon calling O sr p (M ⋆ + N).Proof. We claim that throughout the course of Algorithm 3, the preconditions of Proposition 1 are always met, i.e. γ sub is always an upper bound on the number of excluded rows U \ S, γ drop is always an upper bound on the number of dropped rows [d] \ U , and M always has rank r -r ⋆ . To show correctness of the rank bound, the rank r of our iterate only increases on drop steps, where Proposition 1 ensures r + r ⋆ at most triples, so r -r ⋆ (after the update on Line 11) remains a correct bound on r throughout the algorithm. Also, r ≤ rtot throughout, since there are ≤ R descent steps.Algorithm 3: SRPartialCompletion(O sr [0,1] (M ⋆ + N), M, ∆, r ⋆ , α, γ tot , δ) Input: O sr [0,1] (M ⋆ + N) where M ⋆ ∈ S d×d , rank-r ⋆ M ∈ S d×d such that ∥M -M ⋆ ∥ F ≤ ∆, α ≥ 250, γ tot , δ ∈ (0, 1 10 ) N drop ← 0, N descent ← 0, R ← √ log α, ϵ ← exp(-8 √ log α), K ← 288 √ log α ϵ , rtot ← (2r ⋆ ) • 3 R r ← 2r ⋆ , U ← [d], γ temp ← ϵγ 2 tot 10 6 rtotRK log(d) , γ sub ← γtemp 160RK log(d) • 2 -R , γ drop ← 0 θ ← 25600rtot(RK log(d)) 2 γ 2 tot , κ ← 16γ 2 tot R 2 K 2 4 R rtotγ 2 temp while N drop < RK and N descent < R do if DropOrDescent(O sr [0,1] (M ⋆ + N), M, U, γ drop , γ sub , ∆, r -r ⋆ , r ⋆ , δ R(K+1) , ϵ, θ, κ) = ("Drop", U ′ ) then U ← U ′ , γ drop ← γ drop + γtot 2RK , ∆ ← exp(-ϵ 288 )∆, N drop ← N drop + 1 end else ("Descent", M ′ ) ← DropOrDescent(O sr [0,1] (M ⋆ + N), M, U, γ drop , γ sub , ∆, r -r ⋆ , r ⋆ , δ R(K+1) , ϵ, θ, κ) r ← 3r, γ sub ← 2γ sub , M ← M ′ , ∆ ← 10ϵ 1 4 ∆, N descent ← N descent + 1 end end Return: MWe next prove correctness of the γ 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 γ sub increases is by 4 √ θκ 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 θ, κ, we have4 √ θκ • RK ≤ γ temp 160RK log(d) • 2 -R ,which is our initial setting of γ sub in Line 3. Therefore, since the worst-case growth of the γ 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 γ sub is correct throughout the algorithm.Next, we show that the γ drop parameter remains correct throughout the algorithm. Note that the γ sub parameter is never larger thanγtemp 160RK log(d) ≤ γtot 160RK log(d) .Therefore, the number of dropped rows in each drop step, by Proposition 1 and our choice of θ, is at most40 γ tot 160RK log d + rtot θ d log d ≤ γ tot 4RK + γ tot 4RK • d = γ tot d 2RK .Therefore the update to γ drop in Line 7 is correct. We have also shown that over the course of the algorithm, we never drop or exclude more than γtotd 160RK log(d) + γtotd 2 ≤ γ tot d rows in total. Additionally, we verify the second condition in (4) holds with the largest value of γ sub :γ temp 160RK log(d) ≤ ϵ 36θ .Finally, after RK drop steps Proposition 1 shows that we have made an exp(-ϵ 288 • RK) = 1 α factor progress on the closeness parameter ∆. Similarly, after R descent steps, since 10ϵ α factor progress as well. The failure probability comes from union bounding over the at most R(K + 1) calls to DropOrDescent.For the runtime bound, by observation all of the parameters r, γ -1 sub , ϵ -1 in Proposition 1 are bounded by a polynomial in r ⋆ • α o (1) throughout the algorithm. The correctness of the lower bound on p and the upper bound on ∥N∥ ∞ similarly follow from Proposition 1.In this section, we develop an optimization subroutine for solving the subproblems (20) 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.Throughout this section, we fix a subset I ⊂ S(d) and parameters k ∈ R >0 , ϵ ∈ (0, 1), and define:EQUATIONIn other words, S is the set of "short" (Frobenius-norm bounded) matrices. Further, if x ∈ X is viewed as a symmetric d × d matrix, the constraints on X enforce that x has bounded row and column sums. Clearly x ∈ X =⇒ ∥x∥ 1 ≤ k, so X is a subset of an ℓ 1 ball of radius k. However, we can more specifically capture X as a scaled bipartite matching polytope. (i, j) ∈ [d] × [d],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) ♯ ∈ S(d). Let M be the bipartite matching polytope of G, i.e.EQUATION)Then d k X = M for X in (22) , where we map coordinates in I to edges in E in the canonical way. By the characterization in Fact 3, we efficiently implement iterations of our Frank-Wolfe method by calling an approximate maximum weight matching algorithm by [22] . We also use the structure of the matching polytope to prove a key regularity property on our objective in Appendix C.2. We finally require the definition of a bounded submatrix, whose entries lie in a given range. With these definitions in hand, our goal in this section is to optimize the following jointly convex function over (x, S) ∈ Z, for an (ℓ, u)-bounded submatrix (D, I) and parameters C, η ∈ R >0 , named F prog-flat to denote its decomposition into progress and (approximate) flatness components:F prog-flat (x, S) := -⟨1 I , x⟩ + CH * η slift D x v -S ,where v ι = [D] 2 ι for all ι ∈ I, andEQUATION)Note that ( 25) is exactly the problem in (20) , up to reparameterizing x ← w • v. It may be helpful to think of the parameter settings for (25) in the context (20) , e.g.,C ≈ √ r γ , η ≈ 1 C , u ≈ √ r d , ℓ ≈ 1 d , k ≈ 1 γ, where r and γ are the rank and closeness parameter of a current iterate.To efficiently minimize f = F prog-flat (defined in (25) ) over Z (defined in ( 22)) we apply a variant of Frank-Wolfe or conditional gradient methods due to [35] . This method essentially reduces the problem to approximately solving min z∈Z ⟨∇f (q), z⟩ for different values of q ∈ Z. The algorithm is given below as Algorithm 4. 10 Below we define the curvature constant, the key quantity which bounds the convergence of the method, as well as the main theorem from [35] which we use. EQUATIONz (t+1) ← (1 -γ (t) )z (t) + γ (t) s (t) end return z (T )Definition 6 (Curvature constant (restated from [35] )). The curvature constant C f,D of convex and differentiable f :R d → R with respect to compact domain D ⊆ R d is C f,D := sup z0,z1∈D,γ∈[0,1],zγ =z0+γ(z1-z0) 2 γ 2 (f (z γ ) -f (z 0 ) -⟨∇f (z 0 ), z γ -z 0 ⟩) .Proposition 4 (Approximate Frank-Wolfe, Theorem 1 of [35] restated and specialized). Let f : R d → R be convex and differentiable, let D ⊆ R d be compact and convex, and let z ⋆ ∈ argmin z∈D f (z).For any K ≥ 1 and δ ≥ 0,z (T ) = ApproxFrankWolfe(f, D, T, δ) (Algorithm 4) satisfies f (z (T ) ) -f (z ⋆ ) ≤ 2(1 + δ)C f,D T + 2 .To facilitate applying Proposition 4 to efficiently minimize F prog-flat (25) over Z (22) 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.Lemma 15 (Gradient approximation). For compact Proof. For s ⋆ ∈ argmin s∈D ⟨g, s⟩ the assumptions imply thatD ⊆ R d , g, ĝ ∈ R d ,⟨g, s⟩ = ⟨ĝ, s⟩ + ⟨ĝ -g, s⟩ ≤ (1 -α) ⟨ĝ, s ⋆ ⟩ + ∆ + ∆.The result then follows as(1 -α) ⟨ĝ, s ⋆ ⟩ = (1 -α) ⟨g, s ⋆ ⟩ + (1 -α) ⟨g -ĝ, s ⋆ ⟩ ≤ ⟨g, s ⋆ ⟩ + αM + ∆ .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 [35] ). It shows that to upper bound the curvature constant it suffices to upper bound ∇ 2 f (z)[w, w] for all w, z ∈ D.Lemma 16 (Curvature bound). For convex, twice-differentiable f :R d → R and compact D ⊆ R d if ∇ 2 f (z)[w, w]≤ M for all w, z ∈ D then the curvature constant f with respect to D is at most 2M .Proof. Let z 0 , z 1 ∈ Z and γ ∈ [0, 1] and definez γ := z 0 + γ(z 1 -z 0 ) for all γ ∈ [0, 1]. Note that f (z γ ) -f (z 0 ) -⟨∇f (z 0 ), z γ -z 0 ⟩ = -γ ⟨∇f (z 0 ), z 1 -z 0 ⟩ + γ 0 ⟨∇f (z t ), z 1 -z 0 ⟩ dt = γ 0 ⟨∇f (z t ) -∇f (z 0 ), z 1 -z 0 ⟩ dt . Additionally, ⟨∇f (z t ) -∇f (z 0 ), z 1 -z 0 ⟩ = t 0 ∇ 2 f (z α )[z 1 -z 0 , z 1 -z 0 ]dα ≤ t • sup z∈D ∇ 2 f (z)[z 1 -z 0 , z 1 -z 0 ] . Now, since f is convex, ∇ 2 f (x)is positive semidefinite for all x ∈ D and so∇ 2 f (z)[z 1 -z 0 , z 1 -z 0 ] ≤ 2∇ 2 f (z)[z 1 , z 1 ] + 2∇ 2 f (z)[z 0 , z 0 ] ≤ 2M .Combining these bounds yields the desired bound off (z γ ) -f (z 0 ) -⟨∇f (z 0 ), z γ -z 0 ⟩ ≤ γ 0 2M tdt = M γ 2 .In the following Appendix C.2 we bound the curvature constant of the particular f = F prog-flat defined in ( 24) 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 letY t := exp 1 η slift D xt v -S t Tr exp 1 η slift D xt v -S tbe the gradient of H * η (slift(D( x v ) -S)) before applying the chain rule, see Fact 1. Because of the block-separable structure of slift, we have thatY t = 1 Tr(L t ) + Tr(R t ) L t 0 d×d 0 d×d R t ,whereEQUATIONFor notational simplicity, we finally defineB t := L t -R t , T t := Tr(L t ) + Tr(R t ).We observe that by definition of the objective in (25), we have[∇ x f (z t )] ι = -1 + C T t ⟨B t , E ι ⟩ for all ι ∈ I, ∇ S f (z t ) = C T t B t .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.Here we bound the curvature constant of F prog-flat as defined in (25) over Z defined in (22) . To do so, we first provide a bound, Lemma 17, on the operator norm of D(x) defined in (24) , for x ∈ 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 ℓ 1 norm of any its rows or columns (see e.g., Lemma B.4, [19] ); however, we directly give a self-contained proof for convenience.Lemma 17. For all x ∈ X (defined in ( 22)), we have ∥D(x)∥ op ≤ ku d for D as defined in (24) .Proof. For all z ∈ R d , the Cauchy-Schwarz inequality and the fact that D(x) is symmetric implyz ⊤ D(x)z = i,j∈[d] [D(x)] ij z i z j ≤   i,j∈[d] z 2 i [D(x)] ij   1 2   i,j∈[d] z 2 j [D(x)] ij   1 2 = i∈[d] z 2 i j∈[d] [D(x)] ij .Additionally, for all i ∈ [d] since (D, I) is an (ℓ, u)-bounded submatrix and x ∈ X ,j∈[d] [D(x)] ij | = j∈[d]|ι=(i,j) ♯ ∈I [D(x)] ij ≤ ku d .Combining shows that |z ⊤ D(x)z| ≤ ku d ∥z∥ 2 2 for all z ∈ R d and yields the result as D(x) is symmetric.Lemma 17 improves upon the trivial bound on ∥D(x)∥ op for x with ∥x∥ 1 ≤ k. Note that if x has k on the index corresponding to the largest entry of D I , then ∥D(x)∥ op ≥ ku, which is substantially larger than ku d bound given in Lemma 17. The improved bound for x ∈ 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 ⋆ , 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 ′ ∈ Z with z = (x, S) for x ∈ X and S ∈ S as defined in (22) and for f = F prog-flat defined in (25) ,EQUATIONConsequently,C Fprog-flat,Z ≤ 2C η 2 + ku ℓ 2 d 2 .Proof. Let z, z ′ ∈ 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 * η at Az ′ and let H be the Hessian of H * η at Az ′ . Note that the chain rule, Fact 1, and that the trace and operator norm are dual imply that, for z = (x, S),|⟨∇f (z ′ ), z⟩| = |-⟨1 I , x⟩ + C ⟨G, Az⟩| ≤ ∥x∥ 1 + C ∥G∥ tr ∥Az∥ op ≤ k + C ∥Az∥ op , ∇ 2 f (z ′ )[z, z] = CH[Az, Az] ≤ C η ∥Az∥ 2 op .However, for any (x, S) ∈ Z = X × S,EQUATIONwhere 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 ϵ ∈ (0, 1), and Lemma 17. Combining these inequalities yields∇ 2 f (z ′ )[z, z] ≤ C η 2 + ku ℓ 2 d 2 .Applying the same argument with S = 0 and x =0 yields |⟨∇ X f (z ′ ), x⟩| ≤ C ku ℓ 2 d + k and |⟨∇ S f (z ′ ), S⟩| ≤ 2C. Finally, C Fprog-flat,Z ≤ 2C η 2 + ku ℓ 2 d 2follows from Lemma 16.In this section, we discuss how to approximate the S block of ∇F prog-flat (z) := ∇F prog-flat (x, S) within the error allowed by Line 5 and Lemma 15, where (as discussed earlier) we denote our approximation byH ≈ ∇ S f (x, S) = C T B, for T = Tr(L) + Tr(R), B = L -R,following notation in (26) . We then give implementation details for computingW ≈ min M∈S ⟨H, M⟩ ,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.The main result of this section is the following.There is an algorithm which takes as input x ∈ X , S ∈ S given as a rank-r factorization,R ≥ ∥ 1 η (D( x v ) -S)∥ op , ∆ ∈ [0, C],and α, δ ∈ (0, 1), and computes W ∈ S as a rank-q factorization satisfyingEQUATIONforEQUATIONwith probability ≥ 1 -δ. Moreover, q = O( C 2 ∆ 2 ), and the algorithm runs in timeO (|I| + dr) • R log C ∆ • 1 α 2 + C 2 ∆ 2 log d δ .Approximating the gradient. We begin by bounding the complexity of matrix-vector access to a matrix B ≈ B -L -R, with a given tolerance for approximation error. Ultimately we will use the approximate gradientEQUATIONto 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.). For α ≥ 0 and R ≥ 0, there is a polynomial p of degreeO(R log 1 α ) such that | exp(x) -p(x)| ≤ α exp(x) for all x ∈ [-R, R].Applying Lemma 20 twice directly yields our approximation B.Corollary 2. Let x ∈ X , S ∈ S satisfy ∥ 1 η (D( x v ) -S)∥ op ≤ R, and let ∆ ≥ 0. There is a matrix B such that, for L := exp( 1 η (D( x v ) -S)) and R := exp( 1 η (S -D( x v ))), and definingT := Tr(L) + Tr(R), B := L -R, we have ∥ B∥ tr ≤ (1 + ∆ 8C )T , as well as C T B -B, S ′ ≤ ∆ for all S ′ ∈ S, T mv ( B) = O (|I| + T mv (S)) • R log C ∆ .Proof. It suffices to provide matrices L, R such thatT mv ( L) + T mv ( R) = O (|I| + T mv (S)) • R log C ∆ , L -L tr ≤ ∆ 8C Tr(L), R -R tr ≤ ∆ 8C Tr(R).Indeed, letting B := L -R, the bound on T mv ( B) is then immediate, and by Hölder's inequality (with ∥S ′ ∥ op ≤ ∥S ′ ∥ F ≤ 2) and the triangle inequality, we also have the desiredC T B -B, S ′ ≤ 2C T B -B tr ≤ 2C T L -L tr + R -R tr ≤ ∆,by the definition of T = Tr(L) + Tr(R). We only discuss L, as the case of R is symmetric. We letL = p( 1 η (D( x v ) -S)), where p is the polynomial from Lemma 20 with α ← ∆ 8C . The bound on T mv ( L) follows from the degree of p, and the fact thatT mv (D( x v )) = O(|I|). Moreover, letting {λ i } i∈[d] ⊆ [-R, R] be the eigenvalues of 1 η (D( x v ) -S), we indeed have L -L tr = i∈[d] |p(λ i ) -exp(λ i )| ≤ ∆ 8C i∈[d] exp(λ i ) = ∆ 8C Tr(L).Finally, the claim ∥ B∥ tr ≤ (1 + ∆ 8C )T follows from the triangle inequality.Approximating the S step. We now build upon the access afforded by Corollary 2 to compute W, our approximate solution to min M∈S ⟨H, M⟩, 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.Lemma 21. Let α, δ ∈ (0, 1) and M ∈ S d×d . There is an algorithm which returnsF ∈ [(1 - α) ∥M∥ F , (1 + α) ∥M∥ F ] with probability ≥ 1 -δ in time O(T mv (M)α -2 log d δ ).Proof. Let Q ∈ R k×d with independently uniform random unit vector rows in R d scaled down by1 √ k for appropriately large k = Θ(α -2 log d δ ). By the Johnson-Lindenstrauss lemma of [20] , with probability ≥ 1 -δ, we have for all i ∈ [d] that[MQ ⊤ ] i: 2 2 ∈ (1 -α) ∥M i: ∥ 2 2 , (1 + α) ∥M i: ∥ 2 2 .Therefore, summing for all i ∈ [d] proves that Tr(QM 2 Q ⊤ ) = F satisfies the desired bound. We can compute MQ ⊤ explicitly in time k • T mv (M), and computing the Frobenius norm of MQ ⊤ ∈ R d×k does not dominate the stated running time.Lemma 22. Let α, δ ∈ (0, 1), ∆ ≥ 0, let H ∈ S d×d have ∥H∥ tr ≤ τ , and let W ⋆ := argmin W∈S ⟨W, H⟩. There is an algorithm which with probability ≥ 1 -δ returns W = ZRZ ⊤ satisfying R ∈ S q×q and Z ∈ S d×q , withEQUATIONin timeO T mv (H) • 1 α 2 + τ 2 ∆ 2 log d δ .Proof. Note that in closed form, we have W ⋆ = -(1 + ϵ) H ∥H∥F , and the optimal objective value is ⟨W ⋆ , H⟩ = -∥H∥ F . We first compute F using Lemma 21 such that∥H∥ F ≤ F ≤ 1 + α 8 ∥H∥ F ,within the allotted time and failure probability δ 2 . Then, lettingEQUATIONNext, let W ← ZZ ⊤ W ′ ZZ ⊤ where Z is the result of Lemma 4 with q ← ⌈ 9τ 2 2∆ 2 ⌉, ϵ ← 1 2 , and failure probability δ 2 . We output R := Z ⊤ W ′ Z and Z, which can be computed within the allotted time. The result follows by combining (33) with⟨W, H⟩ -⟨W ′ , H⟩ ≤ ∥W ′ -W∥ op ∥H∥ tr ≤ 3τ 2 σ q+1 (W ′ ) ≤ ∆.Here, we used that ∥W ′ ∥ F ≤ 2 implies ≤ 9τ 2 2∆ 2 singular values of W ′ are larger than 2τ 3∆ .We make one slight extension to Lemma 22 under implicit access to H.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 ⊤ with R ∈ S q×q and Z ∈ S d×q satisfying the guarantee in (32) with probability ≥ 1 -δ in timeO T mv ( B) • 1 α 2 + τ 2 ∆ 2 log d δ .Proof. We follow the steps of Lemma 22 exactly, except we instead letW ′ ← -(1 + ϵ) B F ′ where F ′ satisfies ∥ B∥ F ≤ F ′ ≤ (1 + α 8 )∥ B∥ F , again with probability ≥ 1 -δ 2 , using Lemma 21. Because the computation in Lemma 21 is scale-invariant, the distribution of W ′ remains unchanged from Lemma 22, and all remaining steps are the same as before.We combine the developments of this section to prove Lemma 19.Proof of Lemma 19. We define H = 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 ∥H∥ op ≤ (1 + ∆ 8C )C ≤ 2C, so we can set τ = 2C in Lemma 22. Moreover, in the context of Corollary 3,T mv ( B) = O (|I| + dr) • R log C ∆The runtime bound then follows from Corollary 3. Finally, the rank bound q follows from (32).In this section, analogously to Appendix C.3, we discuss how to approximate the X block of ∇f (z) with a vector h, and give implementation details for computing w ≈ min v∈X ⟨h, v⟩ .We crucially use the characterization in Fact 3, which implies this is a weighted matching problem.The main result of this section is the following.There is an algorithm which takes as input x ∈ X , S ∈ S given as a rank-r factorization, R ≥ ∥ 1 η (D( x v ) -S)∥ op , ∆ ∈ [0, C], and α, δ ∈ (0, 1), and computes y ∈ X satisfying ⟨y, h⟩ ≤ (1 -α)argmin y ⋆ ∈X ⟨y ⋆ , h⟩ ,EQUATIONwith probability ≥ 1 -δ. The algorithm runs in timeO (|I| + dr) • √ Rk 2 C 2 log 1.5 ( RdkC δ∆ ) ∆ 2 + |I| α log 1 α .Approximating the gradient. Recall that [∇ x f (x, S)] ι = -1 + C T ⟨B, E ι ⟩ for all ι ∈ I, where again B = L -R and T = Tr(L) + Tr(R) as in Appendix C.3. To produce our approximation h ≈ ∇ x f (x, S), we use the following helper guarantee.Lemma 24 (Lemma 20, [38] ). Let ϵ, ϵ ′ , δ ∈ (0, 1), {A i } i∈[n] ∈ S d×d , R ≥ log 1 ϵ ′ , and let M ∈ S d×d satisfy ∥M∥ op ≤ R. There is an algorithm which computes{V i } i∈[n] ⊆ R such that for all i ∈ [n], |V i -⟨A i , exp(M)⟩ | ≤ ϵ ⟨|A i |, exp(M)⟩ + ϵ ′ Tr(|A i |)Tr exp(M) with probability ≥ 1 -δ in time O   T mv (M) • √ R log 1.5 ( Rnd δϵϵ ′ ) ϵ 2 +   i∈[n] T mv (A i )   • log nd δ ϵ 2   .With Lemma 24 established, our gradient approximation follows straightforwardly, Corollary 4. Let x ∈ X , S ∈ S satisfy ∥ 1 η (D( x v ) -S)∥ op ≤ R, and let ∆ ≥ 0 and δ ∈ (0, 1). We can compute h ∈ R I in timeO (|I| + T mv (S)) • √ Rk 2 C 2 log 1.5 ( RdkC δ∆ ) ∆ 2 ,such that with probability ≥ 1 -δ,| ⟨h -∇ x f (x, S), x ′ ⟩ | ≤ ∆ for all x ′ ∈ X .Proof. Define T as in Corollary 2 throughout the proof. We let h ∈ R I satisfy h I = -1 + C(Vι-Uι) T for all ι ∈ I, for V, U ∈ R I to be defined, which we can compute within the allotted time. Since ∥x ′ ∥ 1 ≤ k for all x ′ ∈ X , it suffices to show that ∥h -∇ x f (x, S)∥ ∞ ≤ ∆ 2k . To this end, throughout this proof let M := 1 η (D( x v ) -S), and define M ), E ι ⟩ , for all ι ∈ I. By our choice of h ι , we haveV ⋆ ι := ⟨exp(M), E ι ⟩ , U ⋆ ι := ⟨exp(-|[h -∇ x f (x, S)] ι | = C T (|V ι -V ⋆ ι | + |U ι -U ⋆ ι |) .We take {V ι } ι∈I to be the approximations given by Lemma 24 with the set of matrices {E ι } ι∈I and M, δ ← δ 2 , and ϵ, ϵ ′ ← ∆ 4kC ; we define {U ι } ι∈I identically, except we apply Lemma 24 with -M instead of M. Note that these approximations yieldC T (|V ι -V ⋆ ι | + |U ι -U ⋆ ι |) ≤ C T (ϵ + ϵ ′ )Tr(|E ι |) (Tr exp(M) + Tr exp(-M)) ≤ 2C(ϵ + ϵ ′ ) ≤ ∆ k ,as desired. The first inequality used the guarantee in Lemma 24 with Hölder's inequality, and the second used the definition of T = Tr exp(M) + Tr exp(-M) and Tr(|E ι |) = 2. Finally, the runtime follows directly from the bound in Lemma 24.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.Proposition 5 (Theorem 3.12, [22] ). Let G = (L ∪ R, E) be a bipartite graph, let w ∈ R E be a set of weights, and let m := |E|. There is an algorithm which computes f ∈ M, defined in (23) , such that ⟨w, f ⟩ ≤ (1 -α) min f ⋆ ∈M ⟨w, f ⋆ ⟩, in time O( m α log 1 α ). We remark that Proposition 5 is stated in [3] 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 ∈ R E , by first dropping any positive coordinates (which can only increase the objective ⟨w, x⟩ when x is coordinatewise nonnegative), and then negating the result of [22] . 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.We now use these developments to give a short proof of Lemma 23.Proof of Lemma 23. We define h ι = -1 + C(Vι-Uι) 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.In this section, we put together the pieces and provide a runtime bound for approximately solving (25) . We first provide Lemma 25 which provides the bounds for implementing Line 5 for 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) ∈ X × S where S is given as a rank-r factorization, R ≥ ∥ 1 η (D( x v ) -S)∥ op , ∆ ∈ [0, C], and δ ∈ (0, 1) outputs ẑ ∈ Z with ẑ = (y, W) ∈ X × S where W is output as a rank O( C 2 ∆ 2 ) factorization such that with probability ≥ 1 -δ, ⟨∇F prog-flat (z), ẑ⟩ ≤ minz ′ ∈Z ⟨∇ S F prog-flat (x, S), z ′ ⟩ + ∆ in time O (|I| + dr) • R C 2 ∆ 2 log C ∆ log d δ + √ Rk 2 C 2 log 1.5 ( RdkC δ ∆ ) ∆ 2 + |I| k + Cku ∆ℓ 2 d log Cku ∆ℓ 2 d .Proof. Applying Lemma 19 and Lemma 23 yields that for any α S , α X ∈ (0, 1] and ∆ ∈ [0, C] (which we set later) we can obtain with probability ≥ 1 -δ (by a union bound) W ∈ S as a rank-q factorization for q = O( C 2 ∆2 ) and H ∈ S d×d satisfying (Lemma 19) ⟨H, W⟩ ≤ (1 -α S ) min S ′ ∈S ⟨H, S ′ ⟩ + ∆ and |⟨H -∇ S F prog-flat (x, S), z ′ ⟩| ≤ ∆ for all S ′ ∈ S , and y ∈ X and h ∈ R I satisfying (Lemma 23)⟨h, y⟩ ≤ (1 -α X ) min x ′ ∈X ⟨h, x ′ ⟩ and |⟨h -∇ X F prog-flat (x, S), x ′ ⟩| ≤ ∆ for all x ′ ∈ X , in time O (|I| + dr) R log C ∆ • 1 α 2 S + C 2 ∆2 log d δ + √ Rk 2 C 2 log 1.5 ( RdkC δ ∆ ) ∆2 + |I| α X log 1 α X .Conditioning on these events and applying Lemma 15 and Lemma 18 yields that ⟨∇ S F prog-flat (x, S), W⟩ ≤ minx ′ ∈X ⟨∇ S F prog-flat (x, S), x ′ ⟩ + α S • 2C + 3 ∆ .and ⟨∇ X F prog-flat (x, S), y⟩ ≤ minS ′ ∈S ⟨∇ X F prog-flat (x, S), S ′ ⟩ + α X • C ku ℓ 2 d + k + 3 ∆ . Picking α S = ∆ 8C , α X = min{ ∆ 8 • (k + Cku ℓ 2 d ) -1, 1} and ∆ = ∆ 24 then yields the result.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,O T |I| + C 2 T ϵ 2 • d • R η C 2 ϵ 2 log C ϵ log dT δ + R η k 2 C 2 log 1.5 ( RηdkC δϵ ) ϵ 2 +O T |I| • CηR η ϵ log CηR η ϵ , for R η := η -1 (2k + ku ℓ 2 d ) and T = ⌈2CηR 2 η C f,Z ) (Algorithm 4), where we note that C f,Z need not necessarily be computed. By Lemma 18 we know that C f,Z ≤ 2CηR 2 η and consequently Proposition 4 implies that so long as each iteration of Algorithm 4 is implemented to the desired accuracy,f (z (T ) ) -f (z ⋆ ) ≤ 2C f,Z T + 2 + 4CηR 2 η T + 2 ≤ 8CηR 2 η T + 2 ≤ ϵ .To implement the method we apply Lemma 25 with (∆, δ) in the lemma set to (CηR 2 η T +2 , δ T ). This suffices to have the desired output with the desired probability by union bound.It remains to bound the computational cost of this algorithm and the rank of the output. Note thatCηR 2 η T = Ω(ϵ -1 ) and R η ≥ ∥ 1 η (D( x ′ v ) -S ′ )∥ op for all (x ′ , S ′ ) ∈ X × S (by Lemma 17, see e.g., (28) ). Additionally, if we initialize the method with (0 d , 0 d×d ) then we see that the rank of the S component of each computed s (t) is O( C 2 ϵ 2 ) and that each S component of each z (t) can be maintained as a rank O(t • C 2 ϵ 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 .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 ⋆ ∈ S d×d which are close on a submatrix (where we only have noisy semi-random observations from M ⋆ ). It then performs a sequence of postprocessing steps to produce a matrix M such that M is close to M ⋆ on the full matrix, as measured in the ℓ ∞ 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.Before giving our next postprocessing steps, we prove a structural property, which can be stated concisely in the language of volumetric spanners [5] . Following definitions in [7] , Lemma 26 shows any n-sized set in R d admits a 2d-approximate ℓ 1 -volumetric spanner of size d + 1. To see this, fix i ∈ [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 ℓ 1 norm, applied to the coefficients defining this simplex.Using Lemma 26, we obtain the following corollary on boundedness of large index subsets. Lemma 27. Let D ∈ S d×d be rank-r, and assume each row of D has at most s entries with magnitude ≥ τ . There exists S ⊆[d] with |[d] \ S| ≤ (r + 1)s such that ∥[D] S: ∥ ∞ , ∥[D] :S ∥ ∞ ≤ 2rτ .Proof. Let UΣU ⊤ be an SVD of D, and let {u i } i∈[d] ∈ R r be the rows of U. By Lemma 26, we can find a subset T such that all rows i ∈ [d] can be written asu i = j∈T a j u j , with j∈T |a j | ≤ 2r.We also include the following application of the matrix Bernstein inequality from [43] .Lemma 30 (Lemma 12, [43] ). Let δ ∈ (0, 1) and let V ⊆ R d be a µ-incoherent subspace of dimension r. Let B V be an orthononormal basis for V , with rows {bi } i∈[d] ⊂ R r . Let S ⊆ [d] have |S| ≥ (1 -1 3µr )d. Let T ⊆ S include each element independently with probability p ≥ 100µr d log 2r δ . Then with probability ≥ 1 -δ, p 2 I r ⪯ i∈T b i b ⊤ i ⪯ 2pI r .Now, we are ready to analyze our testing algorithm and prove that it has the desired behavior.Lemma 31. Let M ⋆ ∈ S d×d be rank-r ⋆ and µ-incoherent, and let M ∈ S d×d be rank-r for r ≥ r ⋆ . For s, τ > 0, assume M -M ⋆ has at most s entries with magnitudes ≥ τ in each row. Then with probability 1 -δ, if we run Algorithm 5 with parameters q, ϕ and j ∈[d] such that q ≥ 1000µr ⋆ d log d δ , q ≤ 1 20µsr ⋆ , ϕ = qdr ⋆ τ,Algorithm 5 has the following behavior.• If ∥M ⋆ :j -M :j ∥ ∞ ≤ 4r ⋆ τ √ µr ⋆ , Algorithm 5 returns true. • If ∥M ⋆ :j -M :j ∥ ∞ ≥ 10τ qdµr ⋆ , Algorithm 5 returns false. Proof. Let the SVD of M ⋆ be M ⋆ = U ⋆ Σ ⋆ (U ⋆ ) ⊤ .We consider the two claims separately.True case. Suppose that ∥M ⋆ :j -M :j ∥ ∞ ≤ 4r ⋆ τ √ µr ⋆ . We will prove that each run of the inner loop of the algorithm succeeds with probability ≥ 4 5 . By using Lemma 27 with D ← M ⋆ -M, and applying our upper and lower bounds on q, there exists S ⊆ [d] with |S| ≥ (1 -1 3µr ⋆ )d such that for all i ∈ S, ∥M ⋆ :i -M :i ∥ ∞ ≤ 4r ⋆ τ . Next, by Lemma 30 and incoherence of M ⋆ , with probability 9 10 ,(V ⋆ :T ∩S ) ⊤ V ⋆ :T ∩S ⪰ 2 3 qI r .This means there exists v ∈ R T ∩S with ∥v∥ 2 ≤ 3µr ⋆ 2qd , such that (V ⋆ :T ∩S ) ⊤ v = (V ⋆ :j ) ⊤ , which also means M ⋆ :T ∩S v = M ⋆ :j . We thus have for this vector v,EQUATIONwhere we used that with probability 9 10 , |T | ≤ 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 ∥M ⋆ :j -M :j ∥ ∞ ≥ 10τ qdµr ⋆ , and again consider a single run of the algorithm. Let i 0 ∈ [d] be the entry such that |M ⋆ i0j -M i0j | ≥ 10τ qdµr ⋆ . First, with probability at least 9 10 over the randomness of the inner loop, for all j ′ ∈ T ,EQUATIONbecause by assumption, there are at most s indices j ′ where |M ⋆ i0,j ′ -M i0,j ′ | ≥ τ . Since qs ≤ 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 ∥v∥ 2 ≤ 3µr ⋆ 2qd such that M ⋆ :T v = M ⋆ :j . Also, again, with probability 9 10 , we have |T | < 2qd. Now let R ⊆ [d] be the set of rows i such that[M ⋆ ] i,T ∪{j} -[M] i,T ∪{j} ∞ ≤ τ .Algorithm 6: Fix(O sr p ( M), M, T, ϕ, q, δ)Input: O sr p ( M), M ∈ S d×d , T ⊆ [d], ϕ ≥ 0, q, δ ∈ (0, 1) Sample B ⊆ T by including each element independently with probability q G ← ∅ for b ∈ B do if Test(M :T , b, ϕ, q, δ 10d 2 ) then G ← G ∪ {b} end for j ∈ [d] do S j ← indices in [d] of observed entries in our call to O sr p ( M) v j ← argmin v∈R |G| ϕ √ qd ∥v∥ ∞ + ∥M Sj ×G v -M Sj ,j ∥ ∞ end V ← vertical concatenation of {v ⊤ j } j∈[d] return M = M :G V ⊤ D.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]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.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
technical overview: 
 At a high level, our algorithm follows the paradigm in [42] for designing fast iterative algorithms that are robust to semi-random models, which used this framework for sparse linear regression. Broadly, the approach is to first find deterministic conditions which guarantee that 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.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 ∈ R d×d and let the ground truth be M ⋆ ∈ R d×d , assume both matrices have rank at most r, and focus on the noiseless setting N = 0 d×d for simplicity. We also assume for normalization purposes that ∥M -M ⋆ ∥ F = 1, and our goal is to take a step M ′ ← M + D so thatEQUATION)Our conditions are inspired by the approach in [43] , which gives improved iterative algorithms for standard matrix completion (without semi-random noise). Let p be the minimum observation probability, let Ω be the set of observed entries from M ⋆ , and let Ω ⋆ 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 Ω ⋆ ⊆ Ω always). Inspired by a similar framework in the sparse recovery setting [42] , the key certificate for guaranteeing progress of the form (1) in [43] 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 ∥S∥ F ≤ 1 and ∥F∥ op ≤ 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., ⟨D, M ⋆ -M⟩ ≥ 1 -c, then [42, 43] give a short argument based on Hölder's inequality that a step in D, combined with a low-rank projection for denoising, will imply (1) . Thus, it suffices to find a matrix D that has these properties; for intuition, we would ideally like to take D = S = M ⋆ -M and F = 0 d×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 Ω, as otherwise we cannot make any guarantees on ⟨D, M ⋆ -M⟩. Naïvely, one would hope to simply take the empirical observations D = 1 p [M -M ⋆ ] Ω ⋆ (which zeroes entries outside Ω ⋆ ), an unbiased estimator of M ⋆ -M, and appeal to matrix concentration arguments to show existence of a short-flat decomposition. Unfortunately, this is not the case, as entries, rows, or columns of M ⋆ -M which are too large can arbitrarily hinder matrix concentration bounds, and [43] gives simple examples showing this dependence on the imbalance is unavoidable for uniform reweightings.However, [43] made the important insight that when matrix concentration fails, it must be that M -M ⋆ is overly concentrated on a few heavy rows and columns, and hence dropping a few rows and columns significantly reduces ∥M -M ⋆ ∥ F . These rows and columns can later be recovered using the low-rank assumption, once enough progress has been made. The algorithm in [43] then works by repeatedly estimating heavy rows and columns, explicitly dropping them to form a set S ⊆ [d] of balanced indices, and then taking the stepD = 1 p [M -M ⋆ ] Ω ⋆ ∩(S×S). 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 [42] , which possess stronger global regularity features such as the restricted isometry property (RIP).Certifying progress in semi-random models. In the semi-random matrix completion problem, we need several modifications to the strategies of [42, 43] , to handle the interplay between estimating heavy indices and making certifiable progress. Firstly, we cannot accurately estimate the ℓ 2 norm of rows and columns of the true difference matrix M -M ⋆ from observations, because the semi-random adversary can drastically distort our estimates. However, we show in Algorithm 1 that we can use the ℓ ∞ norm of observed entries as a proxy for heaviness. 9 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.Next, even if appropriate rows and columns were dropped, we cannot use the empirical observations to construct our step, as semi-random observations are no longer unbiased and the fully-random indices Ω ⋆ are unknown. Instead, we use Ω ⋆ existentially to set up a convex program over reweightings w ∈ R Ω , to search for a candidate step D :=(i,j)∈Ω w ij [M -M ⋆ ] ij .Roughly, our convex program aims to find w satisfying the following constraints (see Lemma 7 for a formal statement).M ∈ S d×d , ∇H * η (M) = exp( 1 η M) Tr exp( 1 η M) . 3. H *η is twice-differentiable and 1 η -smooth with respect to the norm ∥•∥ op .To use H * η to enforce operator norm bounds, we define the signed lift of a matrix M ∈ S d×d by slift(M) := M 0 d×d 0 d×d -M ∈ S 2d×2d .Note that slift signs and lifts M so that its maximum eigenvalue is its operator norm.Comparing matrices. We use the following comparison definition from [43] .Definition 4 (Closeness on a submatrix). We say M, M ′ ∈ R m×n are ∆-close on a γ-submatrix if there exist subsetsA ⊆ [m], B ⊆ [n] satisfying |A| ≥ m -γ min(m, n), |B| ≥ n -γ min(m, n), and [M -M ′ ] A×B F ≤ ∆.If γ = 0, we say M, M ′ are ∆-close. When M, M ′ are both symmetric, we require that A = B.We note that in Definition 4, A, B are unknown; our analysis only uses this definition existentially.4 Outline of proof of Theorem 1In 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.The first main component of our final algorithm, Algorithm 8, takes as input parameters α and γ tot , as well as an input matrix M ∈ S d×d satisfying ∥M -M ⋆ ∥ F ≤ ∆ (i.e., M and the target matrix M ⋆ are ∆-close), where ∆ is sufficiently larger than the noise level ∥N∥ ∞ . Its goal is to use semi-random observations from M = M ⋆ + N to return another matrix M ′ ∈ S d×d such that M and M are ∆ α -close on a γ tot -submatrix (Definition 4). In other words, we are willing to give up on a γ tot fraction of rows and columns to make an α 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). ), θ, κ ≥ 1, and suppose for r := r + r ⋆ and an appropriate polynomial,EQUATIONGiven one call to O sr p (M ⋆ + N) for ∥N∥ ∞ ≤ ϵγsub∆ 20d , the following holds with probability ≥ 1 -δ.1. If Algorithm 2 returns on Line 12, then M U ′ ×U ′ , M ⋆ U ′ ×U ′ are (1 -ϵ 288 )∆-close on a γ sub + 4 √ θκ -submatrix, and |U \ U ′ | ≤ 40(γ sub + ( r θ ) 1/2 )d log d.M ′ U ×U , M ⋆ U ×U are 10ϵ 1 4∆-close on a 2γ subsubmatrix, and M ′ is given as a rank-(3r + 2r ⋆ ) factorization.O m • poly r log( d δ ) γ sub ϵ ,where m ≥ d is the number of observed entries upon calling O sr p (M ⋆ + N). Proposition 1 is used to analyze one step of Algorithm 2, after we have already taken a few iterations and explicitly removed γ drop d rows and columns [d] \ U from consideration, so that our remaining submatrices on U × U are close on a γ sub -submatrix. Our goal will ultimately to have γ sub , γ drop ≤ γtot 2 throughout the algorithm. Algorithm 2 provides bicriteria guarantees: in the "drop" case of Item 1, it slightly increases the γ drop parameter, increases γ sub by an even smaller amount (where the tradeoff is given by a degree of freedom κ), and makes a small amount of progress (decreasing the closeness by 1 -O(ϵ)). In the "descent" case of Item 2, we instead decrease the closeness by a large O(poly(ϵ)) factor, while doubling γ 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.Corollary 1. Let M, M ⋆ ∈ S d×d be rank-r ⋆ , and suppose ∥M -M ⋆ ∥ F ≤ ∆. Let α ≥ 250 and δ, γ tot ∈ (0, 1 10 ). Algorithm 3 uses one call to O sr p (M ⋆ + N), where for appropriate polynomials,∥N∥ ∞ ≤ ∆ d • poly( r ⋆ γtot log( d δ )) • α 1+o(1) , p = poly( r ⋆ γtot log( d δ )) • α o(1) d ,and computes a rank-r ⋆ • α o(1) -matrix M ′ , such that with probability ≥ 1 -δ, M ′ and M ⋆ are ∆ α -close on a γ tot -submatrix. The runtime of the algorithm is mα o (1) • poly( r ⋆ γtot log( d δ )), where m is the number of observed entries upon calling O sr p (M ⋆ + N). We now explain the key computational method we develop to implement Proposition 1. We will solve a subproblem, defined in (5) , 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:F prog-flat (x, S) := -⟨1 I , x⟩ + CH * η slift D x v -S ,whereD(w) := ι∈I w ι D ι , v ι = [D] 2ι for all ι ∈ I, andEQUATION)The difference between (5) and our informal sketch in ( 2) is that we reparameterize x ← w • 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 η for controlling additive error bounds via Fact 1. Thus, the component ⟨1 I , x⟩ = ⟨v, w⟩ captures the progress condition (Item 3), and the component H * η (slift(D( x v ) -S)) captures the flatness condition (Item 2). We optimize (5) over ∥S∥ F ≤ 1 + ϵ, the set of short matrices, and x belonging to X defined in (22) 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).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 ϵ ∈ [0, C] and δ ∈ (0, 1), and suppose|[D] ι | ∈ [ℓ, u] for all ι ∈ I.There is an algorithm computing (x, S), an ϵ-approximate minimizer to (5) with probability ≥ 1 -δ, in timeO (|I| + d) T 2 • poly CkR η ϵ log d δ for R η := η -1 (2k + ku ℓ 2 d ) and T = ⌈ 8CηR 2 η ϵ⌉, and S is given as a rank-r = O( C 2 ϵ 2 • 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 ⋆ on a large submatrix, and then postprocess it to a matrix M that is guaranteed to be close to M ⋆ everywhere with some poly(r, µ, log d)-factor loss in the closeness. As long as the progress α 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 ⋆ ∈ S d×d be rank-r ⋆ and µ-incoherent, and let M = M ⋆ + N for N ∈ S d×d with ∥N∥ ∞ ≤ ∆ for some ∆ ≥ 0. Let M ∈ S d×d be given as a rank-r decomposition, with r ≥ r ⋆ . Further, for γ ∈ (0, 1) suppose M and M ⋆ are d∆-close on a γ-submatrix. Finally, assume γ ≤ 1 10 4 µr log (d) .Then for any δ ∈ (0, 1)if p ≥ 1 d • poly(µr log( d δ )) for an appropriate polynomial, Algorithm 7 uses one call to O p ( M) and with probability ≥ 1 -δ, outputs M ∈ S d×d such thatEQUATIONAlso, M is given as a rank-poly(µr log( d δ )) factorization. The algorithm runs in m • poly(µr log( d δ )) time, where m is the number of observed entries upon calling O sr p ( M).In this section, we formalize some additional preliminaries and helpful notation which will be used in the remainder of the appendices.For n ∈ N we denote [n] := {i ∈ N | i ≤ n}. We say a vector is s-sparse if it has ≤ s nonzero entries. When S ⊆ 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, ∥•∥ p denotes the ℓ p norm for p ≥ 1. Applied to a matrix, ∥•∥ p denotes the ℓ p norm of the vector corresponding to the flattened matrix. We use med(S) to denote the median of a set S. For t ∈ R we let sign(t) = 1 if t ≥ 0 and sign(t) = -1 otherwise. We let • denote the entrywise product of two vectors.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; noteT mv (M) = O(nnz(M)) if M has explicit entries, and if M ∈ R m×n is given as a rank-r factorization then T mv (M) = O((m + n)r).We equip R m×n with the inner product ⟨A, B⟩ := Tr(A ⊤ B), denote the d × d identity by I d , and the all-zero m × n matrix by 0 m×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{A i } i∈[k] ∈ R m×n with an associated operator A (clear from context), we denote A(x) := i∈[k] x i A i for x ∈ R k .We say M is s-row column sparse (RCS) if its rows and columns are s-sparse.For S ⊆ [m], T ⊆ [n],we let the submatrix of M ∈ R m×n indexed by S, T be denotedM S×T . When S is a singleton {i} for i ∈ [m],we denote this M i,T and similarly define M S,j for j ∈ [n].The Frobenius, operator, and trace (nuclear) norms of a matrix are denoted ∥•∥ F , ∥•∥ op , and ∥•∥ tr respectively, corresponding to the 2-norm, ∞-norm, and 1-norm of the singular values of the matrix. We denote the symmetric d × d matrices by S d×d and the positive semidefinite cone by S d×d ⪰0 . We say M ∈ R m×n has singular value decomposition (SVD)M = UΣV ⊤ if M is rank-r, Σ ∈ R r×r is diagonal, and U ∈ R m×r , V ∈ R n×r have orthonormal columns. The ordered singular values of M ∈ R m×n are denoted {σ i (M)} i∈[min(m,n)]where σ 1 (M) is largest. Similarly we define the ordered eigenvalues of M ∈ S d×d by {λ i (M)} i∈ [d] . For M ∈ S d×d with eigendecomposition UΛU ⊤ , we define exp(M) := U exp(Λ)U ⊤ where on the right-hand side, exp is applied entrywise on the diagonal. We also define log M for M ∈ S d×d ⪰0 and |M| for M ∈ S d×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 ⊂ R d , we let Π V denote the orthogonal projection matrix onto V . Index sets. For d ∈ N, we let S(d) contain all symmetrized indices of the form:{(i, i)} for i ∈ [d], or {(i, j), (j, i)} for i, j ∈ [d], i ̸ = j.We use (i, j) ♯ as shorthand for the singleton {(i, i)} if i = j, and otherwise as shorthand for{(i, j), (j, i)}. When I is a set of indices in [d] × [d],we let M I be the d × d matrix which zeroes out all entries of M except those in ι. For a symmetrized index ι ∈ S(d), we denote the scalar value of the ι entry by [M] ι (note that this is well-defined even when ι contains two indices due to symmetry). The zero-one matrix whose only nonzero entries are ι is denoted by E ι , so that Optimization. For convex f : X → R with X ⊆ R d , we let ∂f (x) denote the subgradient set at x ∈ X . We let ∥y∥ * := sup ∥x∥≤1 x ⊤ y denote the dual norm to a norm ∥•∥. When M is a d × d linear operator we use the notation M[u, v] := ⟨Mu, v⟩. This becomes relevant when M is a Hessian of a matrix function (a linear operator on d × d matrices), so M[U, V] evaluates this operator on U, V.M ι = [M] ι E ι for all ι ∈ S(d).Reduction to symmetric matrices. We briefly justify our focus on symmetric matrices in Definition 3. We begin by recalling two facts.Fact 2. Let m, n ∈ N with m ≥ n. There exists k ∈ N such that kn ∈ [ m 2 , m]. Lemma 1.Let m, n, k ∈ N and let M ∈ R m×n be rank-r with SVD M = UΣV ⊤ . Suppose that both U := span(U) and V := span(V) are µ-incoherent. Then, letting M ′ ∈ R m×kn be defined asM ′ := (M M . . . M M) k times , and letting M ′ have SVD M ′ = UΣ ′ W ⊤ , then W := span(W) is µ-incoherent.Proof. It is straightforward to check that a valid SVD is given byΣ ′ = √ kΣ, W ⊤ = 1 √ k V ⊤ V ⊤ . . . V ⊤ V ⊤ k times .Because incoherence is invariant to the choice of SVD, the conclusion holds.Consider an asymmetric variant of the problem in Definition 3, where M ⋆ ∈ R m×n for m ≥ n is rank-r ⋆ and µ-incoherent, and we have p-semi-random observation oracle access (defined analogously to Definition 2) to M ⋆ . Let k be the integer from Fact 2, and let M ⋆ ∈ R m×kn be constructed as in Lemma 1 by concatenating M ⋆ k times. The row and column spans of M ⋆ are µ-incoherent, by Lemma 1. Moreover, we can simulate p-semi-random observation oracle access to  0 m×m M ⋆ M ⋆ ⊤ 0 kn×kn   ∈ S (m+kn)×(m+kn)in the symmetric sense of Definition 3, given asymmetric oracle access to M ⋆ . It is straightforward to check that because M ⋆ 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.Sample splitting. Finally, we recall a convenient subsampling claim from [43] 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 ≤ p.Lemma 2. Let {p k } k∈[K] ⊂ (0, 1) satisfy p k ≤ p ≤ 1 K for all k ∈ [K], and let M ⋆ ∈ S d×d . We can simulate sequential access toO sr p k (M ⋆ ) for all k ∈ [K] with access to O sr Kp (M ⋆ ).Proof. The claim is immediate from the observation that the proof of Lemma 1, [43] is monotone in p. In particular, the same subsampling process in [43] preserves monotonicity of observation probabilities and hence produces valid semi-random observation oracles.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.At a high level, one application of DropOrDescent is parameterized by a current number of dropped rows γ drop , a current number of excluded rows γ sub , a subset of undropped rows U = [d]\D satisfying |D| ≤ γ drop d, and a rank-r matrix M such that M U ×U is promised to be close to our target M ⋆ U ×U on a γ sub -submatrix (Definition 4). It then distinguishes between the following cases from semi-random, noisy observations of M ⋆ , by solving a testing problem via optimization.1. In the first case, dropping an additional γ fraction of rows and columns decreases the closeness parameter ∆ by a small amount, i.e. a small subset of rows or columns are responsible for a nontrivial portion of the mass. We call this case the "drop" case.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 ∆ 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.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 (20) ). We then analyze the drop case in Appendix B.2, where we show that either our current difference matrix has Frobenius norm which is unstable to dropping few rows and columns, or 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.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.For D ∈ S d×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 byEQUATIONWe also will use the following claim which follows from straightforward casework.Lemma 3. Let u ≥ 0, |a| ≤ u, and a ′ := med(-u, a + b, u). Then |a ′ -a| ≤ |b|.Proof. If |a + b| ≤ u the claim is obvious. Otherwise, if a ′ = u it must be the case that b ≥ 0, and0 ≤ a ′ -a ≤ b. Similarly, if a ′ = -u we must have 0 ≥ a ′ -a ≥ -b.We now introduce some additional notation. Let I ⊂ S(d) be a set of symmetrized indices under consideration (corresponding to observations). For w ∈ R I and D ∈ S d×d clear from context, we letEQUATIONFor a parameter ρ, we define the set of "spread" reweightings of the observations D I byEQUATIONFurther, we require the following result on low-rank approximation.Lemma 4 (Theorem 1, [56] ). Let δ, ϵ ∈ (0, 1), let M ∈ S d×d , and let q ∈ [d]. There is an algorithm which returns Z ∈ R d×q with orthonormal columns such thatZZ ⊤ MZZ ⊤ -M op ≤ (1 + ϵ)σ q+1 (M) with probability ≥ 1 -δ, in time O T mv (M) • q log d δ √ ϵ .Moreover, we have for all i ∈ [q], letting z i be the i th column of Z,z ⊤ i M 2 z i ∈ [(1 -ϵ) σ i (M) , (1 + ϵ) σ i (M)] .Finally, we provide ways to bound the singular values of an approximately low-rank matrix. Proof. Let λ ∈ R d be the set of eigenvalues of M in nonincreasing order, and similarly let σ ∈ R d be the nonincreasing eigenvalues of S. By assumption, λ i = 0 for all i ≥ r + 1, and ∥λ -σ∥ 2 ≤ ϵ by Lemma 5. Thus, at most r + s eigenvalues of S can be larger than ϵ s 1/2 , giving the conclusion.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 ( 9).Lemma 7. Let ϵ, γ ∈ (0, 1 10 ), ℓ, u ≥ 0, andT ⊆ S ⊆ U ⊆ [d] such that |U \ S| ≤ γd, |S \ T | ≤ γd, and ℓ ≤ ϵ d . Suppose that for D, D ⋆ , N ∈ S d×d , we have D = D ⋆ + N, for rank-r D ⋆ with ∥D ⋆ S×S ∥ F ≤ 1, ∥D ⋆ T ×T ∥ ∞ ≤ u, and ∥N∥ ∞ ≤ γℓ. Let D := clip u (D),and forI ⊆ S(d) ∩ (U × U ), w ∈ R I ≥0 , suppose the following conditions hold for S, F ∈ S d×d supported on I ∩ (U × U ) with D(w) = F + S. 1. w ∈ W ρ for ρ = ϵ2γd , recalling the definition (9).2. ⟨ D, D(w)⟩ ≥ 1 -ϵ. 3. ∥S∥ F ≤ 1 + ϵ. 4. ∥F∥ op ≤ ϵ r1/2 . 5. min ι∈I |[ D] ι | ≥ ℓ.Then, letting Z ∈ R d×2r be the output of Lemma 4 with parameters δ ∈ (0, 1), ϵ ← 1 2 , M ← S, and q ← 2r, we have with probability ≥ 1 -δ thatD ⋆ -ZZ ⊤ SZZ ⊤ T ×T F ≤ 10ϵ 1 4 .Proof. As a starting point, we claim thatEQUATIONTo see this, we expand to show thatEQUATION)The first line used Item 3 and ∥D ⋆ S×S ∥ F ≤ 1, and the second used the (matrix) Hölder's inequality. The third used Item 4 and that ∥ D T ×T ∥ tr ≤ √ r∥ D T ×T ∥ F , and the (vector) Hölder's inequality. The last line used ∥D ⋆ T ×T ∥ ∞ ≤ u, the definition of D, and Lemma 3 to concludeD ⋆ -D T ×T ∞ ≤ ∥N T ×T ∥ ∞ ≤ γℓ,and also bounded ∥ D(w)∥ 1 via Items 1 and 5, which show∥ D(w)∥ 1 ≤ D, D(w) •   max ι∈I 1 [ D] ι   ≤ ρd ℓ = ϵ 2γℓ .Finally, since w is supported on U × U , applying |U \ T | ≤ 2γd, Item 1, and Item 2 yieldsEQUATIONThen, (10) follows by combining (11) and (12) . Next, applying Lemma 6 using (10) shows that σ 2r+1 (S) ≤ 13ϵ r . Therefore, assuming the algorithm in Lemma 4 succeeds, we haveZZ ⊤ SZZ ⊤ :=S ′ = S + ZZ ⊤ SZZ ⊤ -S :=F ′ , where ∥F ′ ∥ op ≤ 6 √ ϵ √ r .At this point, we can write D(w) = S ′ + (F + F ′ ), where by the triangle inequality∥F + F ′ ∥ op ≤ 7 √ ϵ • 1 √ r . Since ∥S ′ ∥ F ≤ ∥S∥ F ≤ 1 + ϵ,the remainder of the argument is identical to the proof of (10) with the worse flatness parameter, where we use that∥S ′ T ×T ∥ F ≤ ∥S ′ ∥ F and ∥S T ×T ∥ F ≤ ∥S∥ F .In this section, we define a stability condition (14) 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 (14) , 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 ( 14), one can increase the drop parameter to improve the submatrix closeness bound. We will analyze an explicit dropping procedure we use in this latter case 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.Lemma 8 (Lemma 6, [43] ). Let A ∈ S d×d be a rank-r matrix with ∥A∥ F ≤ 1, and let γ ∈ [0, 1].There isEQUATIONWe also require a bound on the sampling error of random observations from a matrix with bounded entries, rows, and columns, which is an application of the matrix Bernstein inequality.Lemma 9 (Lemma 7, [43] ). Let p, δ ∈ [0, 1 2 ], ρ, τ ≥ 0, and let A ∈ S d×d satisfy∥A i: ∥ 2 ≤ ρ for all i ∈ [d], and |A ij | ≤ τ for all (i, j) ∈ [d] × [d].Let Ω ⊆ S(d) be a random subset where each ι ∈ S(d) is included in Ω with probability p, and let A := 1 p A Ω . Then with probability at least 1 -δ,A -A op ≤ 4 max ρ √ p log d δ , τ p log d δ .Finally, we need a guarantee on the concentration of empirical estimates of squared ℓ 2 norms.Lemma 10 (Lemma 3, [43] ). Let p, δ, α ∈ (0, 1), let v ∈ R d have ∥v∥ ∞ ≤ τ , and let ṽ ∈ R d have each ṽi independently set to v i with probability p, and 0 otherwise. Then with probability ≥ 1 -δ,∥v∥ 2 2 - 1 p ∥ṽ∥ 2 2 ≤ max α ∥v∥ 2 2 , 3τ 2 log 2 δ αp .We are now ready to give our main result on sufficient conditions for a good solution to exist.Lemma 11. Let δ, ϵ, γ, p ∈ (0, 1 10 ), andS ⊆ U ⊆ [d] such that |U \ S| ≤ γd. Let ℓ := ϵ 20d , u := 2 √ r γd , p ≥ 240r log( 6d δ ) γ 3 ϵ 2 d .Suppose that for D, D ⋆ , N ∈ S d×d , we haveD = D ⋆ + N, for rank-r D ⋆ with ∥D ⋆ S×S ∥ F ≤ 1 and ∥N∥ ∞ ≤ γℓ. Further, for D := clip u (D), let Ω ⋆ := {ι ∈ S(d) ∩ (U × U ) | |[ D] ι | ≥ ℓ}.Finally, let S ′ be the result of applying Lemma 8 with A ← D ⋆ S×S , γ ← γ 2 , so ∥D ⋆ S ′ ×S ′ ∥ ∞ ≤ u, and let T := S ′ \ L where L is the indices of the ⌊ γd 2 ⌋ rows of D S ′ ×S ′ with largest ℓ 2 norms, soEQUATION)Letting Ω ⊆ S(d) have each ι ∈ S(d) independently included with probability p, andw ⋆ ∈ {0, 1 p } Ω have [w ⋆ ] ι = 1p if and only if ι ∈ (T × T ) ∩ Ω ⋆ , the following conditions all hold with probability ≥ 1 -δ over the randomness of Ω, and S ⋆ ,F ⋆ ∈ S d×d supported on (T ∩ T ) ∩ Ω ⋆ with D(w ⋆ ) = F ⋆ + S ⋆ . 1. w ⋆ ∈ W ρ for ρ = ϵ2γd , recalling the definition (9).⋆ ) ≥ 1 -ϵ 2 .3.∥S ⋆ ∥ F ≤ 1 + ϵ. 4. ∥F ⋆ ∥ op ≤ γϵ 4r 1/2 .Proof. For notational convenience, letL ⋆ := S(d)\Ω ⋆ be the set of indices ι ∈ S(d) with |[ D] ι | < ℓ.We define our decomposition of D(w ⋆ ) as follows, where we recall w ⋆ is supported on (T × T ) ∩ Ω ⋆ :D(w ⋆ ) := D (T ×T )∩Ω ⋆ :=S ⋆ + D(w ⋆ ) -D (T ×T )∩Ω ⋆ :=F ⋆ . Now, clearly ∥N∥ F ≤ d ∥N∥ ∞ ≤ ϵ 200 , so ∥S ⋆ ∥ F ≤ ∥D S×S ∥ F ≤ 1 + ϵ 200where we used that every entry of S ⋆ is smaller in magnitude than the corresponding entry in D S×S (it is zeroed out if it does not belong to (T × T ) ∩ Ω ⋆ , and otherwise is clipped to a smaller range). This establishes Item 3. The same logic shows that ∥ D S ′ ×S ′ ∥ F ≤ 1 + ϵ 200 . Combined with (14) and the definition of T ,EQUATION)since i∈L ∥[ D T ×T ] i: ∥ 2 2 ≤ ∥ D S ′ ×S ′ ∥ 2 F -∥ D T ×T ∥ 2 F ≤ ϵ 10, and L consisted of the largest rows of S ′ by ℓ 2 norm. Therefore, applying Lemma 9 with A ← D (T ×T )∩Ω ⋆ , τ ← u, and ρ 2 ← ϵ 5γd establishes Item 4 with probability ≥ 1 -δ 3 using the lower bound on p. We further have by (14) thatD (T ×T )∩Ω ⋆ F ≥ 1 - ϵ 30 -D L ⋆ F ≥ 1 - ϵ 30 -dℓ ≥ 1 - ϵ 12 .Therefore, Lemma 10 with v set to the vectorized D (T ×T )∩Ω ⋆ , τ ← u, and α ← ϵ 5 showsEQUATIONwith probability ≥ 1 -δ 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 ∈ T . We apply Lemma 10 once more with v set to the vectorized [ D (T ×T )∩Ω ⋆ ] i: and α = 1 2 to obtain that with probability ≥ 1 -δ 3 ,i:2 2 ≤ 3 2 D (T ×T )∩Ω ⋆ i: 2 2 + 6u 2 log( 6 δ ) p ≤ 2 • ϵ 5γd ≤ ϵ 2γd ,where we used (15) and our lower bound on p.We also provide a helper lemma for making progress if ( 14) fails to hold.Lemma 12. In the setting of Lemma 11, if(14) is false, ∥D ⋆ T ×T ∥ F ≤ 1 -ϵ 36 .Proof. This follows from Lemma 3 and the assumption on (14) , which lets us boundD ⋆ T ×T F ≤ D T ×T F + D ⋆ -D T ×T F ≤ D T ×T F + d ∥N∥ ∞ ≤ 1 - ϵ 30 + ϵ 200 ≤ 1 - ϵ 36 .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 ( 14) holds), or there are an ≈ γ fraction of rows and columns which are responsible for an ≈ ϵ fraction of the Frobenius norm of the difference matrix (if (14) 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 ≈ ϵ fraction of progress. Importantly, we can ensure that the submatrix parameter (i.e. γ in the sense of Definition 4) grows slowly using a tunable parameter, which lets us iterate drop steps without losing too many rows and columns.We begin by giving a subroutine (Algorithm 1), analogous to Section 4.1 of [43] , 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.Algorithm 1: Proof. Let P ∈ [0, 1] d×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 potentialSparsify(O sr [0,1] (D), U, τ, γ, p, δ) Input: O sr [0,1] (D), U ⊆ [d], τ ≥ 0, γ, p, δ ∈ (0, 1) S 0 ← U t max ← ⌈3 log d⌉ + 1 for 0 ≤ t <Φ t := (i,j)∈St×St |[D ⋆ t ] ij |≥τ P ij .We also denote the expected number of revealed large entries in each row and column as follows:r ⋆ i,t := j∈St |[D ⋆ t ]ij |≥τ P ij for all i ∈ S t .By a standard Chernoff bound, with probability ≥ 1 -δ, for all 0 ≤ t < t max and all i ∈ S t ,EQUATION)Condition on this event in the rest of the proof. Due to our symmetric observation model (Definition 2), and since A × A has no entries ≥ τ in magnitude, in any iteration, at least half of the contribution to Φ t must be due to remaining rows in B t := S t \ A, i.e. we have|B t | ≤ γd such that i∈Bt r ⋆ i,t ≥ Φ t 2 .Letting R ⋆ i,t denote the ⌊γd⌋ ≥ |B t | indices in S t with largest r ⋆ i,t , we thus have from (16) ,i∈Rt r i,t ≥ i∈R ⋆ t r i,t ≥ 3 4 i∈R ⋆ t r ⋆ i,t -50γd log d δ ≥ 3 8 Φ t -50γd log d δ .Therefore, if Φ t ≥ 400γd log( d δ ), we decrease Φ t by at least a 1 4 factor, so by our choice of t max , we have Φ tmax-1 ≤ 400γd(log d δ ) ≤ γpsd 2 . This shows that there are at most γd remaining rows i ∈ S tmax-1 with r ⋆ i,tmax-1 ≥ ps 2 . Now, any remaining row i ∈ S tmax-1 with at least s entries with magnitude ≥ τ has r ⋆ i,tmax-1 ≥ ps, and therefore will be one of the largest γd remaining rows by observed counts via (16) . Hence, it will be dropped in the last iteration t max as claimed.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 ≈ ϵ fraction of the progress if the condition in Lemma 12 is met. Lemma 14. Let δ, ϵ, γ, p ∈ (0, 1 10 ), θ, κ ≥ 1, andEQUATIONEQUATIONreturns a subset U ′ ⊆ U such that with probability ≥ 1 -δ, there exists a subset S ′ ⊆ U ′ withEQUATIONProof. First, by Lemma 8, there is a subset A ⊆ S such that |S \ A| ≤ 10 r θ , so that∥D A×A ∥ ∞ ≤ D ⋆ A×A ∞ + ∥N∥ ∞ ≤ √ θ 10d + ϵ d ≤ √ θ 5d .Therefore, our application of Algorithm 1 with the parameters in (17) satisfies the hypotheses of Lemma 13. Condition on the conclusion of Lemma 13 holding in the rest of the proof (with probability ≥ 1 -δ), giving us the first bound in (18) . Also, there are at most d rκ entries per row and column of D U ′ ×U ′ with magnitude larger than τ in (17) , so there are at most d rκ entries per row and column ofD ⋆ U ′ ×U ′ with magnitude larger than τ + ϵ d ≤ 2τ . Next, if ∥D ⋆ S×S ∥ F ≤ 1 -ϵ 3 , the conclusion is obvious (taking S ′ ← S ∩ U ′ ). Otherwise, for C := S \ T , D ⋆ C×S 2 F ≥ 1 2 D ⋆ S×S 2 F -D ⋆ T ×T 2 F ≥ 1 2 1 - ϵ 3 2 -(1 -ϵ) 2 ≥ ϵ 2 .By Lemma 8, there is a subsetEQUATION)This set satisfies the second bound in (18) , so it remains to prove the third, which follows fromD ⋆ S ′ ×S ′ 2 F ≤ D ⋆ S×S 2 F - D ⋆ C×S 2 F -D ⋆ (C∩S ′ )×S ′ 2 F ≤ 1 - ϵ 2 + D ⋆ (C∩S ′ )×S ′ 2 F ≤ 1 - ϵ 2 + ϵd θ •   d • (2τ ) 2 + d rκ • √ rθκ 4d 2   ≤ 1 - ϵ 4 .The third line used that there are at most ϵd θ rows in C, and each such row (restricted to S ′ ) has all but d rκ entries bounded in magnitude by τ , with the remainder bounded as in (19) .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 Lemma 7), 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.We provide pseudocode for the algorithm corresponding to Proposition 1 in Algorithm 2.Algorithm 2: DropOrDescent(O sr [0,1] (M ⋆ + N), M, U, γ drop , γ sub , ∆, r, r ⋆ , δ, ϵ, θ, κ) Input: O sr [0,1] (M ⋆ + N) where M ⋆ ∈ S d×d is rank-r ⋆ and ∥N∥ ∞ ≤ ϵγsub∆ 20d , U ⊆ [d] with |[d] \ U | ≤ γ drop , rank-r M ∈ S d×d such that M U ×U , M ⋆ U ×U are ∆-close on a γ sub -submatrix, δ, ϵ ∈ (0, 1 10 ), θ, κ ≥ 1 r ← r + r ⋆ p 1 ← 240r log( 30d δ ) γ 3 sub ϵ 2 d , p 2 ← 800rκ log( 5d δ ) d , u ← 2 √ r γsubd , ℓ ← ϵ 20d I ← supp(O sr p1 (M ⋆ + N)) \ {ι ∈ S(d) | |[M ⋆ + N -M] ι | ≤ ℓ∆} ∩ (U × U ) v ι ← ∆ -2 • [clip u∆ (M ⋆ + N -M)] 2ι for all ι ∈ I (w, S) ← ϵ 12 -approximate minimizer to (20) with failure probability δ 5 , computed using Proposition 6EQUATIONReturn: ("Descent", M ′ ← M + ZZ ⊤ SZZ ⊤ ) end Proposition 1. Let M ∈ S d×d be given as a rank-r factorization, let M ⋆ ∈ S d×d be rank-r ⋆ , and let U ⊆EQUATION), θ, κ ≥ 1, and suppose for r := r + r ⋆ and an appropriate polynomial,EQUATIONGiven one call to O sr p (M ⋆ + N) for ∥N∥ ∞ ≤ ϵγsub∆ 20d , the following holds with probability ≥ 1 -δ. O m • poly r log( d δ ) γ sub ϵ ,where m ≥ d is the number of observed entries upon calling O sr p (M ⋆ + N).Proof. Throughout the proof, without loss we let ∆ = 1, since we can scale M by 1 ∆ , take the claimed step, and scale up by ∆ (indeed, examination of Algorithm 2 shows it performs this scaling). We now describe our algorithm. Define W ρ as in (9) , and for w ∈ R I , define D(w) as in (8) .We compute (w, S), an ϵ 12 -approximate minimizer to F , and V , satisfying |V -F (w, S)| ≤ ϵ 12 . Pseudocode for computing such a V with failure probability 1 -δ 5 is provided in Line 9, and the correctness and runtime of this step are analyzed at the end of this proof.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discuss the modeling assumptions and acknowledge that since this is 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.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• 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.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• 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.• The full details can be provided either with the code, in appendix, or as supplemental material. 
preliminaries: 
 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.Definition 1 (Incoherence). We say a dimension-r subspaceV ⊆ R d is µ-incoherent if ∥Π V e i ∥ 2 ≤ µr d for all i ∈ [d](where e i is the ith standard basis vector), and M ∈ R m×n is µ-incoherent if M has µ-incoherent row and column spans.We will work with symmetric matrices. We denote the space of d × d symmetric matrices by S d×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. (M) inherit their definitions in [43] when all p ι = p, for a fixed p ∈ [0, 1]. Now we can formally define the semi-random matrix completion problem we study.Definition 3 (Semi-random matrix completion). In the semi-random matrix completion problem, parameterized by µ, ∆ ∈ R ≥0 , p ∈ [0, 1], d ∈ N, and r ⋆ ∈ [d], there is an unknown rank-r ⋆ µ-incoherent matrix M ⋆ ∈ S d×d . For some N ∈ S d×d satisfying ∥N∥ ∞ ≤ ∆, and M := M ⋆ + N, we receive the output of one call to O sr p (M), and wish to output an approximation to M ⋆ . Remark 1. In Appendix A, we give a sample-splitting reduction which lets us use O sr p (M) to simulate ≈ p q independent accesses to O sr q (M) for smaller values q ≤ p. We will also need a few technical definitions to explain the main ingredients in our algorithm. We recall the following standard facts about H * η . Fact 1 ( [58] ). The function H * η defined in (3) satisfies the following for all η > 0. 1. For all M ∈ S d×d , λ 1 (M) ≤ H * η (M) ≤ λ 1 (M) + η log d, where λ 1 (M) is the maximum eigenvalue of M.We now complete our postprocessing algorithm. Given an estimate M that is entrywise close to M ⋆ , 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).Lemma 33. Let M ⋆ ∈ S d×d be rank-r ⋆ and µ-incoherent, and let M = M ⋆ + N for N ∈ S d×d with ∥N∥ ∞ ≤ τ . Let M ∈ S d×d be rank-r for r ≥ r ⋆ . For s, τ > 0, assume [M -M ⋆ ] :T has at most s entries larger than τ in each row and column. Assumes ≤ d 20µr 2 , |T | ≥ 1 - 1 10µr d, p ≥ 100µr d log d δ .Then with probability 1 -δ, if we run Algorithm 6 with parameters q, ϕ such thatq ≥ 1000µr d log d δ , q ≤ 1 20µsr , ϕ = qdrτ, then the output satisfies M -M ⋆ ∞ ≤ 10 4 q 2 d 2 (µr) 3 τ.Proof. First, by Lemma 27 and applying our upper and lower bounds on q, there is a subset T ′ ⊆ T with |T ′ | ≥ (1 -1 3µr )d such that for all j ∈ T ′ , ∥M :j -M ⋆ :j ∥ ∞ ≤ 4rτ . Next, by Lemma 31, with probability 1 -δ 10 , we have B ∩ T ′ ⊆ G. Thus, by applying Lemma 30 with S ← T ′ and p ← q, we have that with 1 -δ 10 probability, for any j ∈ [d], there is a vector u j with ∥u j ∥ 2 ≤ 3µr 2qd such that M ⋆ :G u j = M ⋆ :j . Also, by Lemma 31, we have with probability 1 -δ 10 that ∥M ⋆ :G -M :G ∥ ∞ ≤ 10τ qdµr. Now fix a j ∈ [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ϕ qd ∥u j ∥ ∞ + M Sj ×G u j -M Sj ,j ∞ ≤ 2 qdµr 1.5 τ + M Sj ×G u j -M ⋆ Sj ×G u j ∞ + M ⋆ Sj ,j -M Sj ,j ∞ ≤ 2 qdµr 1.5 τ + |G| ∥u j ∥ 2 10τ qdµr + τ ≤ 100τ qd(µr) 1.5 ,where we use that with 1 -δ 10 probability, |G| ≤ 2qd. Thus, the solution v j in Line 9 must haveEQUATIONThis implies thatM ⋆ Sj ×G v j -M ⋆ Sj ,j ∞ ≤ M ⋆ Sj ×G v j -M Sj ×G v j ∞ + M Sj ×G v j -M Sj ,j ∞ + M Sj ,j -M ⋆ Sj ,j ∞ ≤ |G| ∥v j ∥ ∞ 10τ qdµr + 100τ qd(µr) 1.5 + τ ≤ 2500q 2 d 2 (µr) 2.5 τ.Next, recall that span(M ⋆ ) is µ-incoherent. Let B ∈ R d×r have orthonormal columns with span(B) = span(M ⋆ ), with rows {b i } i∈ [d] . By Lemma 30, with probability 1 -δ 10d 2 , S j contains a subset S ′ j such that |S ′ j | ≤ 2pd andi∈S ′ j b i b ⊤ i ⪰ p 2 I r ⪰ |S ′ j | 4d I r .Thus, for all vectors z ∈ span(M ⋆ ),∥z∥ 2 ≤ 4d |S ′ j | ∥z S ′ j : ∥ 2 . Using µ-incoherence of span(M ⋆ ) again, M ⋆ :G v j -M ⋆ :j ∞ ≤ M ⋆ :G v j -M ⋆ :j 2 µr d ≤ M ⋆ S ′ j :G v j -M ⋆ S ′ j :j 2 4µr |S ′ j | ≤ M ⋆ S ′ j :G v j -M ⋆ S ′ j :j ∞ 4µr ≤ 5000q 2 d 2 (µr) 3 τ,where the first line used Lemma 28. Finally, recall from ( 41) that for v j to be an optimal solution, we must have ∥v j ∥ ∞ ≤ 100µ 1.5 √ r. Since |G| ≤ 2qd, we have the desired bound for column j ∈ [d]:M :G v j -M ⋆ :j ∞ ≤ ∥M :G v j -M ⋆ :G v j ∥ ∞ + M ⋆ :G v j -M ⋆ :j ∞ ≤ |G| ∥v j ∥ ∞ ∥M :G -M ⋆ :G ∥ ∞ + 5000q 2 d 2 (µr) 3 τ ≤ 10 4 q 2 d 2 (µr) 3 τ.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 τ qd(µ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 • poly(µr log( d δ ))), with failure probability δ, as described in Lemma 32. Finally, we put everything together and give our full postprocessing procedure. Proposition 3. Let M ⋆ ∈ S d×d be rank-r ⋆ and µ-incoherent, and let M = M ⋆ + N for N ∈ S d×d with ∥N∥ ∞ ≤ ∆ for some ∆ ≥ 0. Let M ∈ S d×d be given as a rank-r decomposition, with r ≥ r ⋆ . Further, for γ ∈ (0, 1) suppose M and M ⋆ are d∆-close on a γ-submatrix. Finally, assume γ ≤ 1 10 4 µr log (d) .Then for any δ ∈ (0, 1) if p ≥ 1 d • poly(µr log( d δ )) for an appropriate polynomial, Algorithm 7 uses one call to O p ( M) and with probability ≥ 1 -δ, outputs M ∈ S d×d such thatEQUATIONAlso, M is given as a rank-poly(µr log( d δ )) factorization. The algorithm runs in m • poly(µr log( d δ )) time, where m is the number of observed entries upon calling O sr p ( M).be implemented with one call to O sr p (M ⋆ + N) for p = Q d and outputs M ∈ S d×d with rank at most Q (represented in terms of its low-rank factorization) such that with probability ≥ 1 -δ,M -M ∞ ≤ Q∆ .The algorithm runs in time O(mQ) where m is the total number of observed entries.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 ≤ r ⋆ • P o (1) and is D α -close to M ⋆ on a 1 10 6 µP 2 submatrix. Now this implies that the hypotheses of Proposition 3 are satisfied when we call Postprocess and thus we get thatM -M ⋆ ∞ ≤ poly(r ⋆ )P o(1) D dP ≤ D 100d.Since M ⋆ is rank-r ⋆ , we have∥ M -M ⋆ ∥ F ≤ 2∥PCA r ⋆ ( M) -M ⋆ ∥ F ≤ 0.1D .This now implies that the hypotheses of Corollary 1 are satisfied at the beginning of the next iteration (unless D ≤ ∆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 δ. As long as none of the subroutines fails, the above argument implies the output must satisfyM -M ⋆ ∞ ≤ ∆Qand 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 ⋆ + N) with reveal probability p ≥ poly r ⋆ , µ, logd∥M ⋆ ∥ F δ∆ d .The overall runtime guarantee follows by combining the runtime guarantees of Corollary 1, Proposition 3, and the PCA step (see Remark 4).NeurIPS Paper Checklist 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA]Justification: The paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• 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.• 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).• 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. 
experiments compute resources: 
 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?Answer: [NA]Justification: The paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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.• 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. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.This norm distortion is the main source of poly(r) losses in our guarantees compared to the[43] algorithm.We perform minor changes to the names of the variables, choice of offsets, etc. to facilitate and simplify the use of[35] to obtain our results. 
 
 Appendix:  


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

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

Reviews: review: paper_summary: paper_summary: In this paper, the authors study semirandom matrix completion. In their models, entry $ij$ of a $\mu$-incoherent, symmetric ground truth rank-$r$ matrix $M^{\star} \in \mathbb{R}^{d \times d}$ are revealed independently with probability $p_{ij}$, where $1 \ge p_{ij} \ge p$ for some parameter $p$ that is a function of $r$ and $d$. The assumption that $M^{\star}$ is symmetric is not important, as we can reduce the asymmetric setting to the symmetric one with minimal overhead.

An important feature of this model is that the entry reveal probabilities are allowed to vary. This contrasts against standard assumptions in the matrix completion literature which typically stipulate that the entries are revealed i.i.d with probability $p$. Although revealing more entries of the matrix may seem to help the learning algorithm learn the underlying matrix, many algorithms fail under this helpful adversary. This is evidence that these algorithms have overfit to a statistical assumption implicit in the problem statement.

A prior work [CG18] studied this problem and gave some recovery guarantees based on a global reweighting scheme for the matrix, but this algorithm has certain undesirable properties -- it is not a high-accuracy algorithm, it is not robust to outliers, and it has a dependence on the conditioning of the matrix. The present work addresses all of these issues and gives a nearly linear time algorithm that achieves an $\ell_{\infty}$ recovery guarantee.

The main technical contribution builds off of a prior work concerning semirandom sparse recovery [KLLST23]. In particular, the algorithm tries to find a progress direction in each step that can be written as the sum of a "short" matrix (one that has small Frobenius norm) and a "flat" matrix (one that has low spectral norm). This is chosen by a combination of dropping heavy rows/columns of $M$ that witness a large  Frobenius error in the current iteration along with a fast reweighting algorithm that finds a candidate descent direction that admits the short-flat decomposition. The fast reweighting algorithm itself is a Frank-Wolfe type algorithm over a set of valid reweightings and short matrices. The runtime arising from this subproblem follows from observing that the set of valid reweightings is in fact a rescaled bipartite matching polytope, which means fast matching algorithms can be called as a black box, and implementing a separate algorithm to optimizer linear functions over the set of short matrices.

* [CG18] Non-Convex Matrix Completion Against a Semi-Random Adversary (https://arxiv.org/abs/1803.10846)

* [KLLST23] Semi-Random Sparse Recovery in Nearly-Linear Time (https://arxiv.org/abs/2203.04002)
strength_weakness: strength_weakness: The rank of the matrix that's output can be $poly(r)$ than the ground truth. Since this paper seems mostly concerned with $r \ll d$ and independent of $d$, this is morally not a big deal. Also, what is the polynomial? I did some very cursory searching but didn't find it explicitly written down (all I see is that it's bigger than $r^6$).

The error depends on the largest entry of the noise -- this might be a bit pessimistic (e.g. if the noise matrix has just one nonzero entry, but the corresponding index isn't revealed to the learner, then this shouldn't affect anything). The authors explicitly mention getting a more "optimistic" dependence on the noise as an interesting open direction for future work.
questions: questions: What are the challenges, if any, to extending the results to an adaptive adversary? For example, consider an adversary that perhaps samples several entries of $M$ with probability $p$, then upon seeing the sampled entries, reveals an extra arbitrary set of their choice? I ask these because it seems suggested that the algorithm you presented actually does work in such a settings (lines 54-62), but I don't see something in Definition 2 to this effect.
limitations: limitations: Yes
paper_summary: paper_summary: This paper consider semi-random matrix completion via flow-based adaptive reweighting. 
The 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.

I am not familiar with the area of matrix completion.
strength_weakness: strength_weakness: NO
questions: questions: NO
limitations: limitations: NO
paper_summary: paper_summary: This paper considers the semi-random matrix completion problem. Given an unknown rank-r matrix M, each entry of the matrix Is observed independently with a probability  p_{ij} at least p.  The goal is to find a matrix close the matrix M. 

The sap-based algorithm can achieve the nearly-optimal sample complexity, but is not fast compared to iterative method. The previous work shows an iterative method which has a sample complexity and runtime has a polynomial dependence on epsilon.

This paper provides a fast iterative method that achieves the sample complexity and runtime with polylogrithmic dependence on the accuracy epsilon. It has no dependence on the condition number and can also handle noise in observations.
strength_weakness: strength_weakness: -
questions: questions: -
limitations: limitations: Yes.
paper_summary: paper_summary: This paper proposes an algorithm that is able to achieve high-accuracy in semi-random matrix completion with nearly linear time.  The key innovation lies in using a flow-based adaptive reweighting scheme to mitigate the bias introduced by the adversary. This technique effectively identifies and downweights the potentially misleading entries, allowing for accurate recovery of the underlying low-rank matrix. The authors provide theoretical guarantees for their algorithm, demonstrating its ability to achieve near-optimal sample complexity.
strength_weakness: strength_weakness: 1. While it outlines the general approach, it lacks concrete pseudocode or even finished code, making it difficult for readers to fully grasp the implementation details. 
2. Unlike the work of Kelner et al 2022, the paper only considers a specific type of semi-random adversary. Exploring how the method performs against different adversarial models, including more powerful adversaries that can manipulate the values of the observed entries, would strengthen the contributions.
3. The paper's claim of near-linear time complexity is not sufficiently substantiated and demonstrated in empirical setting. The authors does not provide a detailed analysis of the polynomial factors involved in the runtime. This makes it difficult to compare its efficiency to existing methods with the similar magnitude. Furthermore, the absence of empirical validation leaves it unclear how much practical improvement the algorithm actually achieves in real-world settings.
questions: questions: Could you provide more details on the practical implementation of your algorithm? Specifically, how does it handle very large datasets in terms of memory usage and computational overhead?
limitations: limitations: See weakness
paper_summary: paper_summary: This paper presents a new algorithm for matrix completion in the semi-random setting, where each entry is revealed independently with a probability at least $p = \frac{\mathrm{poly}(r, \mu, \log d)}{d}$. The paper provides a promising approach for designing fast matrix completion algorithms that are robust to semi-random sampling, which is argued to be a more realistic model than uniform sampling in practice. The insights may enable future work on more practical algorithms for semi-random matrix completion.
strength_weakness: strength_weakness: 1. While the paper provides a promising theoretical foundation, the polynomial factors in the sample complexity and runtime may still be too high for immediate practical deployment, as acknowledged by the authors. Further work may be needed to obtain more practical parameter dependencies. 

2. This paper does not sufficiently discuss how it fits into the broader field of matrix completion algorithms with practical implementation. For example, [1] considers the matrix completion problem via robust alternating minimization, which can tolerate errors caused by approximate updates. Both papers consider the practical implementation of the matrix completion algorithm. What are some similarities and differences between these two (or some other related) matrix completion papers? 

3. The paper focuses on the theoretical algorithm and analysis but does not include empirical evaluation of real-world datasets. Experimental validation of the robustness and efficiency benefits would strengthen the claims.

[1] Yuzhou Gu, Zhao Song, Junze Yin, and Lichen Zhang. “Low rank matrix completion via robust alternating minimization in nearly linear time.” ICLR 2024.
questions: questions: 1. One of the main motivations of this paper is to consider the matrix completion problem under the semi-random setting, which is a more realistic setting than uniformly random. Meanwhile, the paper mentions, “both our dependence and the dependence of [16] are somewhat large at the moment, limiting immediate practical deployment”. I understand the difficulties of making theoretical breakthroughs, but since this paper is motivated by the practical setting, I want to ask, how much work is still needed before the practical deployment.

2. A minor comment: Each definition, theorem, and proposition should be more self-contained. There are some notations in these blocks that should be more explicitly defined.
limitations: limitations: As mentioned by the authors, the main limitation is “the modeling assumptions and runtimes of the algorithms may not be practical yet”. Other than that, I do not find obvious limitations.

Comments: title: response to author response to review
comment: Your response clearly addressed my concerns. Thank you so much. I believe the paper has included sufficient details for the algorithm to be implemented.
Thank you very much for your detailed response. I have updated my score.
Thanks so much for the detailed response :)