Recovering structured mathematical objects from partial measurements is a fundamental task in machine learning and statistical inference. One important example, which has been a mainstay of modern research in machine learning and high-dimensional statistics, is matrix completion. Here, we receive n entries from an unknown d × d matrix, and the goal is to complete the remaining entries when n is as small is possible.
The key structural assumption that enables recovery when n ≪ d 2 is that the underlying matrix is low-rank. A celebrated line of research on matrix completion (Srebro and Shraibman, 2005;Candès and Recht, 2009;Candès and Tao, 2010;Keshavan et al., 2010;Gross, 2011;Recht, 2011) has culminated in the following guarantee: to exactly recover an incoherent rank-r matrix, n = Õ(rd) uniformly sampled entries suffice.
While low-rank matrix completion has seen successful application across many problem domains (most famously in the context of the Netflix Problem), for many tasks it is natural to consider not just pairwise interactions but higher-order interactions, leading to the problem of tensor completion. Tensor completion poses significant computational hurdles compared to the matrix case, but in an impressive recent work, Potechin and Steurer (2017) provide an efficient algorithm based on the sum-of-squares hierarchy that exactly recovers a d × d × d tensor of rank-r with incoherent and orthogonal components from Õ(rd 3 2 ) measurements. While this undershoots the optimal statistical rate of Õ(rd), there is evidence that this is optimal amongst polynomial time algorithms under certain average-case hardness assumptions (Barak and Moitra, 2016).
In real-world applications, the assumption that the underlying tensor is truly low-rank may be too strong, and model misspecification is unavoidable. This is the main thrust of agnostic learning (Haussler, 1992;Kearns et al., 1994) which, rather than attempting to recover an unknown model in some class, attempts to predict as well as the best model. The aim of this paper is to develop guarantees for agnostic tensor completion: predicting as well as the best low rank tensor, even when exact recovery is impossible.
We work in the following agnostic tensor regression model, which captures tensor completion as a special case: we receive examples (X 1 , Y 1 , ), . . . , (X n , Y n ) i.i.d. from an unknown distribution D, where each instance X t is a d × d × d tensor and Y t is a real-valued response. Letting ⟨⋅, ⋅⟩ denote the usual inner product, we measure predictive performance of a given d × d × d tensor T via its square loss risk L D (T ) = E (X,Y )∼D (⟨T, X⟩ -Y ) 2 . Our goal is to use the samples to produce a predictor Tn that enjoy low excess risk:
L D ( Tn )inf
where the bound ε(n, r, d) converges to zero as n → ∞. When the observations X are uniformly distributed indicators (i.e. X = e i ⊗ e j ⊗ e k , where (i, j, k) is uniform) this recovers the usual measurement model for tensor completion. If the model is well-specified in the sense that Y = ⟨X, T ⋆ ⟩ + ξ, where T ⋆ is a low-rank tensor and E[ξ X] = 0, then low excess risk implies approximate recovery of T ⋆ . In general, the guarantee ( 1) is interesting because it implies non-trivial predictive performance even in the presence of severe model misspecification.
In the matrix case, agnostic excess risk guarantees of the type in (1) were characterized by Koltchinskii et al. (2011). There it was shown that to compete with the best rank-r matrix with bounded entries, empirical risk minimization with nuclear norm penalization obtains a fast rate of the form ε(n, r, d) = O(rd log d n), and also showed that this is optimal. 1 The nomenclature fast rate is intended to contrast the 1 n dependency on n with slow rates, which have a 1 √ n dependency on n, and which are typically much simpler to obtain (see Gaiffas and Lecué (2011) for slow rates in the matrix setting).
The results of Koltchinskii et al. (2011) leverage strong understanding of the (matrix) nuclear norm, namely matrix concentration and decomposability/subgradient properties. In this paper, we tackle the following questions:
• Can we give similar guarantees for agnostic tensor completion?
• Can we obtain fast rates while at the same time relaxing the strong statistical assumptions (low rank observations, incoherence) needed for exact recovery?
• What are the best rates we can obtain subject to employing a polynomial-time algorithm?
Our main result is to give the first polynomial time algorithm with a fast O(1 n)-type rate for agnostic completion of third order tensors that improves over the rate obtained by the natural reduction to matrix completion. Our main theorem gives excess risk bounds relative to low-rank orthogonal tensors, i.e. tensors of the form
where u i 2 = v i 2 = w i 2 = 1 and {u i } are orthogonal, as are {v i } and {w i }. The result is as follows.
Theorem 1 (informal). There is a convex set of d× d× d tensors T derived from a sum-of-squares relaxation of the tensor nuclear norm, for which the empirical risk minimizer Tn ∶= arg min T ∈T 1 n ∑ n t=1 (⟨T, X t ⟩ -Y t )foot_1 can be computed in polynomial time, and guarantees that with probability at least 1o(1), L D ( Tn )inf
(3)
The guarantee applies to both random indicator measurements (tensor completion) and gaussian measurements (tensor compressed sensing).
The full version of the theorem is stated in Section 3. The result be thought of as a generalization of the agnostic matrix completion results of Koltchinskii et al. (2011) to higher-order tensors. We also achieve a more general exact oracle inequality that trades off approximation and estimation error. This takes the form
where r(T ) denotes the rank of T . 2
Algorithm. Our algorithm is based on the sum-of-squares (SoS) hierarchy of convex relaxations (Shor, 1987;Parrilo, 2000;Lasserre, 2001), applied to the tensor nuclear norm. For k ∈ N, the sum-of-squares hierarchy defines a sequence of outer convex relaxations ⋅ nuc k that give an increasingly tight approximation to the (hard to approximate (Hillar and Lim, 2013)) tensor nuclear norm ⋅ nuc as k is increased. The SoS nuclear norm was previously used in the work of Barak and Moitra (2016), who gave O(1 √ n) rates for tensor completion in the agnostic model with absolute loss. Their main contribution was to show how certain spectral bounds arising in 3-SAT refutation (Coja-Oghlan et al., 2004) bound the Rademacher complexity for the unit ball of the degree-six SoS nuclear norm, thereby controlling the usual empirical process via uniform convergence. Our guarantees are based on empirical risk minimization over the (scaled) ball in this norm, specifically the degree-six relaxation ⋅ nuc 6 , and our analysis builds on their Rademacher complexity bounds.
Restricted eigenvalue and subgradient lemmas. While the O(1 √ n)-type rates provided in Barak and Moitra (2016) are optimal (in terms of n dependence) for generic Lipschitz losses, it is not immediately obvious whether their result can be used to provide O(1 n)-type fast rates for strongly convex losses like the square loss. It has long been recognized that to obtain fast rates for prediction with strongly convex losses, more refined control of the empirical process is necessary. In particular, it is well-known that local Rademacher complexities and related fixed point complexities characterize the rates for empirical risk minimization in a data-dependent fashion. To bound such localized complexities under convex relaxations, the typical approach is to establish a restricted eigenvalue property for the empirical design matrix (Negahban et al., 2012;Bartlett et al., 2012;Lecué andMendelson, 2017, 2018). Establishing such guarantees for regularizers such as the ℓ 1 norm, nuclear norm, and so on is usually done by appealing to properties of the subgradient of the norm and proving that the norm (approximately) decomposes across certain subspaces (Negahban et al., 2012). The main tool we establish here, which allows us to unlock the full power of localized complexities and establish rates fast rates, is a new guarantee of this type for the SoS nuclear norm. Informally, we show: Theorem 2 (informal). Let T ⋆ be a fixed orthogonal tensor, and let T = {T ∶ T nuc 6 ≤ T ⋆ nuc 6 }. Then:
This theorem is a consequence of a more general result we prove in Section 2, which gives a characterization of the subgradient of ⋅ nuc 4 at any orthogonal tensor. The basic idea is to show that a characterization for the subgradient of the tensor nuclear norm given in Yuan and Zhang (2016) can be captured in the sumof-squares proof system. The final result (Theorem 4) is fairly user-friendly, and packages the complexity of SoS into a self-contained statement about geometric properties of the norm ⋅ nuc 4 . We hope that this will find use in other applications. As one concrete example, in Section 3 we show how the subgradient characterization can also be used to give agnostic fast rates for the problem of low-rank tensor sensing with gaussian measurements. Here we also obtain Õ(r 2 d 3 2 n)-type fast rates.
Lower bounds. Lastly, we prove that our results can't be strengthened significantly while still obtaining computationally efficient algorithms. It is straightforward to show that there is an inefficient predictor that obtains O(rd n) excess risk, whereas the dimension scaling in Theorem 1 is O(d 3 2 ). This scaling is shared by the other results based on the SoS nuclear norm (Barak and Moitra, 2016;Potechin and Steurer, 2017), and Barak and Moitra (2016) show that finding relaxations for which the Rademacher complexity grows as o(d 3 2 ) is at least as hard as refuting random instances of 3-XOR. In Section 4 we give a computational lower bound for agnostic learning that shows that obtaining square loss excess risk scaling as o(d 3 2 ) is at least as hard as a certain distinguishing problem for random 3-XOR, sometimes called learning sparse parities with noise.
Early algorithms for computationally efficient tensor completion relied on unfolding: reshaping the tensor into a matrix and applying a matrix completion algorithm (Tomioka et al., 2011;Tomioka and Suzuki, 2013;Romera-Paredes and Pontil, 2013;Mu et al., 2014;Jain and Oh, 2014). This approach yields suboptimal results for third-order tensors and other odd-order tensors. For example, for a third-order tensor in (R d ) ⊗3 , the most "balanced" unfolding of the tensor is a d × d 2 matrix, and so directly reducing to an algorithm for agnostic matrix completion (e.g. Koltchinskii et al. (2011)) would yield suboptimal O(d 2 )-type sample complexity.
Recent results of Montanari and Sun (2016), Potechin andSteurer (2017), andXia et al. (2017) all give sub-O(d 2 ) type rates, but apply only to noiseless or well-specified models, and do not obviously extend to the agnostic setting. Potechin and Steurer (2017) give exact completion in the noiseless case after Õ(rd 3 2 ) entries are observed. Montanari and Sun (2016) show that a refined spectral approach based on unfolding can obtain sub-O(d 2 ) rates for prediction error in the noiseless setting, but they obtain a rate of O(1 n 2 3 ) that falls short of the O(1 n)-type rate we provide. Finally, Xia et al. (2017) recently showed that an algorithm based on power iteration provides O(d n)-type rates once n = Ω(d 3 2 ), but their result only applies to well-specified models, and it seems unlikely that this algorithmic approach succeeds in the fully agnostic setting.
Our results build on the seminal work of Barak and Moitra (2016) and Potechin and Steurer (2017), both of which use sum-of-squares to give O(d 3 2 )-type guarantees that improve on unfolding. The former was the first paper to study the agnostic setting, and gave slow excess risk guarantees for the absolute loss (i.e., rates growing as 1 √ n ). Technically, our results build on their Rademacher complexity bounds for the SoS norms (Barak and Moitra, 2016), as well as spectral bounds from Hopkins et al. (2015). Obtaining fast rates, however, requires developing new technical tools and necessitates that we control the subgradient of the SoS norms. Our analysis here builds on ideas used to construct dual certificates for tensor completion in Potechin and Steurer (2017).
Lastly, we mention that various recent works have begun to explore that power of SoS in other agnostic learning settings. Notably, Klivans et al. (2018) provide square loss risk bounds for SoS algorithms for robust regression. To the best of our knowledge our work is the first to provide fast rates for SoS algorithms in any agnostic setting.
We let ⋅ p denote the ℓ p norm, i.e. if x ∈ R d is a vector then x p = ∑ d i=1 x i p 1 p . For a matrix A we let A op denote the operator norm/spectral norm and let A nuc denote the nuclear norm. For matrices or tensors we let ⋅ F denote the element-wise ℓ 2 norm. For any norm ⋅ we let ⋅ ⋆ denote the dual.
We use Õ to suppress factors logarithmic in d, r, and 1 δ, where δ is the failure probability.
Tensor notation. The outer product between two vectors u ∈ R d 1 and v ∈ R d 2 is denoted u ⊗ v, and belongs to the space R d 1 ⊗ R d 2 . For a given vector u, we write u ⊗k = u ⊗ ⋯ ⊗ u (k times), and likewise define (R d ) ⊗k = R d ⊗ ⋯⊗ R d . This paper develops algorithms for completion of 3-tensors in (R d ) ⊗3 , which we frequently identify with elements of R d × R d × R d . In more detail, for a tensor T ∈ (R d ) ⊗3 , we let T i,j,k be such that T = ∑ i,j,k T i,j,k ⋅ e i ⊗ e j ⊗ e k . For a pair of matrices A, B, we let A ⊗ B denote the Kronecker product, which obeys the relation
Whenever T is an orthogonal tensor of the form (2), we let r(T ) denote the rank.
2 Subgradient of the sum-of-squares nuclear norm 2.1 Tensor nuclear norm and sum-of-squares relaxation
In the classical results on matrix completion (Candès and Recht, 2009;Candès and Tao, 2010;Recht, 2011;Koltchinskii et al., 2011), a central object is the nuclear norm, which arises as a convex relaxation of the rank. A natural candidate to develop efficient algorithms for tensor completion is the tensor nuclear norm (e.g. Hillar and Lim (2013); Friedland and Lim (2018)), which may be defined via
and whose dual is the injective tensor norm X inj = sup x 2 = y 2 = z 2 =1 ⟨X, x ⊗ y ⊗ z⟩. Unfortunately, the optimization problem here-maximizing a degree-three polynomial over the sphere-is intractable in general.
The approach we take, following Barak and Moitra (2016) and Potechin and Steurer (2017), is to employ the sum-of-squares hierarchy of convex relaxations (Shor, 1987;Parrilo, 2000;Lasserre, 2001) which provides an increasingly tight sequence of relaxations of the optimization problem in (4). To describe the relaxations, we require the notion of a pseudodistribution. Definition 1 (Pseudodistribution (Barak and Steurer (2016))). Let µ ∶ R d → R be a finitely supported function and let Ẽµ f = ∑ x∈supp(µ) µ(x)f (x). µ is said to be a degree-k pseudodistribution if Ẽµ 1 = 1 and Ẽµ f 2 ≥ 0 for all polynomials f of degree at most k 2.
Given a degree-s pseudodistribution µ and sytem of polynomial inequalities A = {f 1 ≥ 0, . . . , f m ≥ 0} ∪ {g 1 = 0, . . . , g m ′ = 0}, we write µ ⊧ A if for all S ⊆ [m] and all sum-of-squares polynomials h such that
and Ẽµ [g i q] = 0 for all i ∈ [m ′ ] and all polynomials q such that deg(g i q) ≤ ℓ.
With the pseudodistribution formalism, we define the degree-k SoS injective norm as follows:foot_2
The degree-k SoS nuclear norm is simply defined as the dual:
and then
The SoS nuclear norm and injective norm can be evaluated in d O(k) time (Grötschel et al., 1981;Barak and Steurer, 2016). Moreover, the norms obey the ordering T nuc ≥ . . . ≥ T nuc k ≥ . . . ≥ T nuc 2 ≥ T F , and likewise
Our algorithms are based on empirical risk minimization with SoS nuclear norm constraints, i.e., algorithms that minimize the empirical loss over the set T = T ∈ (R d ) ⊗3 T nuc k ≤ τ for appropriate choice of τ and k. The technical challenge to analyzing this type of relaxation is that even if measurements are realized by a rank-r tensor, there is nothing that guarantees a-priori that the tensor Tn output by the algorithm is itself low rank. Letting T be a rank-r orthogonal tensor, our main technical result here shows that if τ = T nuc k , then for all elements of T ′ ∈ T , the error ∆ = T ′ -T is "approximately low rank" in a sense that suffices to guarantee good generalization performance. Theorem 3 (Formal version of Theorem 2). Let k ≥ 4. Let T ∈ (R d ) ⊗3 be an orthogonal rank-r tensor, and let T ′ ∈ (R d ) ⊗3 be an arbitrary tensor with
In the analysis of nuclear norm regularization for matrix completion-and more broadly, throughout highdimensional statistics-the key tool used to establish guarantees along the lines of ( 9) is a characterization for the subgradient for the nuclear norm, and the related notion of decomposability (Negahban et al., 2012;Negahban and Wainwright, 2012). It is known clasically (Watson, 1992) that for any matrix W with singular value decomposition W = U ΣV ⊺ ,
Our approach in the remainder of this section is to establish a similar result for the subgradient of the SoS nuclear norm ⋅ nuc k at any orthogonal tensor T . From here Theorem 3 will quickly follow.
As a first step, we need to define certain subspaces and projection operators associated with T .
Subspaces For the remainder of the section we let T be a rank-r orthogonal tensor as in (2). Define U = span{u i }, V = span{v i }, and W = span{w i }, and note that each subspace has dimension at most r.
orthogonal projections onto these subspaces and P U ⊥ , P V ⊥ and P W ⊥ be the projections onto the respective orthogonal complements. We define projection operators from (R d ) ⊗3 to (R d ) ⊗3 for all 2 3 combinations of subspaces:foot_4
Lastly, we define two subspaces that play a central role in our analysis:
One can verify via multilinearity that
, and that any tensor in the range of Q T ∥ spans at most r dimensions along at least two modes. We can now state our main theorem for the subgradient.
Theorem 4 (Subgradient of SoS nuclear norm). Let k ≥ 4, and let T = ∑ r i=1 λ i ⋅u i ⊗v i ⊗w i be an orthogonal rank-r tensor. Define
, and for all
In other words, Theorem 4 states that
which we may view as a generalization of the matrix subgradient characterization (10). Yuan and Zhang (2016) proved a similar result for the (exact) tensor nuclear norm. Our proof of Theorem 4 shows that the essence of their proof can be captured by a low-degree sum-of-squares proof. It builds on the approach introduced in Potechin and Steurer (2017) to provide dual certificates for exact tensor completion.
With the subgradient lemma in hand, the path to the "approximately low rank" result of Theorem 3 is clear. Suppose that T ′ nuc k+2 ≤ T nuc k+2 , and let ∆ = T ′ -T . By appropriately choosing the dual tensor X in (13), we can show that
which is a consequence of the earlier remark that all the projections used to define Q T ∥ in ( 12) project into r dimensions along at least two modes. This full argument is in Appendix B.
We now state our main learning results, which use the SoS nuclear norm to give efficient algorithms with fast rates for agnostic tensor completion and tensor sensing. For both results we receive observations
the goal is to obtain low square loss excess risk in the sense of equation ( 1). We let Ên denote the empirical expectation, which is uniform over the examples {(X t , Y t )} n t=1 .
In the tensor completion model we take observations X t to be of the form X t = e it ⊗ e jt ⊗ e kt , where
is selected uniformly at random. 6 In the noiseless or well-specified setting, this corresponds to observing a single entry of an unknown tensor, but we make no assumption on the responses Y t other than boundedness. The main theorem is as follows.
Theorem 5 (Formal version of Theorem 1). Let τ > 0 be fixed. Suppose that Y ≤ R almost surely, and let Tn be the empirical risk minimizer over the tensor class
Let us spend a moment interpreting the theorem. First, let T ⋆ = arg min T ∶rank-r L D (T ). Then, by setting τ = T ⋆ nuc 6 , we are guaranteed that with probability at least 1δ,
More generally, (15) implies an exact oracle inequality (Koltchinskii et al., 2011;Gaiffas and Lecué, 2011): With probability at least 1δ, we have
Let us compare the result in detail with Barak and Moitra (2016), which is the only other polynomial time agnostic tensor completion result with sub-O(d 2 ) sample complexity. For general noise distributions, their analysis gives an excess risk bound that scales as Õ
. The bound in (15) matches this dependence on all the parameters, but is squared, and is thus always tighter. The result has excess risk against arbitrary tensors, however, while our bound requires orthogonality of the benchmark. We do not know whether this restriction can be removed.
Interestingly, while Barak and Moitra (2016) give excess risk bounds against incoherent tensors, we do not require incoherence. This is because we control the complexity of the benchmark through the ℓ ∞ norm of the entries rather than through the Frobenius norm; this parallels the situation in the matrix setting (Koltchinskii et al., 2011;Gaiffas and Lecué, 2011). Applying the spectral bounds of Barak and Moitra (2016) without incoherence requires slightly tightening the analysis.
Lastly, we remark that the guarantee ( 16) requires setting the parameter τ based on the norm of the unknown benchmark T ⋆ . It is likely that this can be relaxed by appealing to penalized empirical risk minimization rather than empirical risk minimization as in Koltchinskii et al. (2011), but we leave this for future work.
In this setting we give agnostic learning guarantees for a setting we call tensor sensing, which generalizes the matrix compressed sensing setup studied in Negahban and Wainwright (2011). We assume that observations X ∈ (R d ) ⊗3 have independent entries from N (0 ; 1) and-as in the tensor completion setting-allow Y ∈ R to be arbitrary. For each tensor T , define R(T ) to be the smallest almost-sure bound on ⟨T, X⟩ -Y . As in the tensor completion setup, the main result is a fast rate with Õ r 2 d 3 2 n -type scaling.
Theorem 6. Let τ > 0 be fixed, and let Tn be the empirical risk minimizer over the tensor class
for all orthogonal tensors T ⋆ ∈ (R d ) ⊗3 for which n = Ω(r 2 (T ⋆ )d 3 2 log 1 2 d + log(1 δ)) and T ⋆ nuc 6 = τ . Overview of analysis We now sketch how the subgradient theorem can be combined with empirical process arguments to prove Theorem 5 and Theorem 6. We follow a generic recipe given in Appendix C.1specifically, Theorem 8-which shows that to control the generalization error of empirical risk minimization, it suffices to bound a certain "offset" or "shifted" empirical process. For any fixed benchmark T ⋆ , the excess risk relative to T ⋆ is bounded as
The offset process on the right-hand side was used to obtain high-probability fast rates for misspecified models by Liang et al. (2015), and its analysis is closely related to that of Lecué and Mendelson (2013); Mendelson (2014). To bound the process, it suffices to establish a type of lower isometry/restricted eigenvalue property, which we state here for the case of tensor regression: let X n ∶ (R d ) ⊗3 → R n be the data operator, which maps any tensor T to the sequence ⟨T, X 1 ⟩, . . . , ⟨T, X n ⟩, and let Σ = E X [XX ⊺ ] ∈ R d 3 ×d 3 be the covariance matrix for the vectorized measurements. Then it suffices to show that with high probability, the following restricted eigenvalue bound holds:
where c > 1 √ 2 is a sufficiently large constant.
Our starting point to establish the guarantee is to borrow a bound from Hopkins et al. ( 2015), which states that E X ĩ nj 4 = O(d 3 4 log 1 4 d) under gaussian measurements, and suffices to bound the Rademacher complexity of our tensor class. Using this bound in conjunction with standard gaussian concentration arguments and the "peeling" method (e.g. (Negahban and Wainwright, 2011)), we prove Theorem 10, which states that with high probability,
Combined with Theorem 3, which asserts that all
To establish the analogous bound in the tensor completion model we use the SoS Rademacher bound from Barak and Moitra (2016), but utilize somewhat different concentration arguments. Indeed, due to the sparse nature of the measurement distribution one cannot hope to exactly establish the restricted eigenvalue property for X n , and must instead show that it holds up to a small additive error.
In the rank-one case, the excess risk bound of Theorem 5 scales as Õ(d 3 2 n), while the excess risk attained by the natural inefficient algorithm scales as Õ(d n). It is natural to ask whether this O(d 1 2 ) gap can be improved or whether it poses a fundamental barrier. In the slow rate regime, Barak and Moitra (2016) gave a computational lower bound showing that finding efficiently computable classes of tensors for which the Rademacher complexity grows as o( d 3 2 n) is at least as hard as refuting random instances of 3-XOR with o(d 3 2 ) clauses. In this section we show that this computational hardness is also present in the fast rate regime: Under plausible average-case hardness assumptions, no polynomial time algorithm can obtain a fast rate for square loss scaling as O(d 3 2-ε n) for any ε > 0.
Our improper learning lower bound applies to any algorithm that obtains low excess risk in the sense of (15), and states that under conjectured hardness of a certain distinguishing problem for 3-XOR it is not possible to improve the O(d 3 2 ) dependence on dimension.
We reduce from the 3-XOR problem over variables x ∈ {±1} d . A 3-XOR instance consists of a sequence of m clauses of the form
where z ijk ∈ {±1} is a target. We consider two families of instances:
• Planted. Fix an arbitrary assignment a ∈ {±1} d . Select m triples (i, j, k) uniformly at random with replacement.foot_6 For each such triple (i, j, k), include a clause
with probability η.
Note, we sample the value z i,j,k for a triple (i, j, k) only once: if the triple is sampled multiple times, the value z ijk will be the same.
• Random. Select m triples (i, j, k) uniformly at random with replacement, and take each clause to be x i ⋅ x j ⋅ x k = z ijk , where z ijk is drawn from {±1} uniformly at random. Again, we sample the value z i,j,k for a triple (i, j, k) only once.
An algorithm for the distinguishing problem takes m clauses as input and outputs either "Planted" or "Random". The algorithm is said to succeed if it outputs "Planted" for planted instances and "Random" for random instances with probability at least 1o(1) over the draw of the instance. Note that the problem becomes easier as η gets smaller, and in particular when η = 0 the problem can be solved in polynomial time using Gaussian elimination.
Conjecture 1. There is some constant η < 1 4 such that no algorithm that succeeds for the 3-XOR distinguishing problem with m = o(d 3 2 ) runs in polynomial time.
All known polynomial time algorithms for distinguishing require m = Ω(d 3 2 ) clauses, and conjectured hardness of the closely related problem of strong refutation for random 3-XOR for with o(d 3 2 ) clauses has been used as a basis to establish hardness of other learning problems (Daniely, 2016;Raghavendra et al., 2017;Kothari et al., 2017;Feldman et al., 2018). Theorem 7. Let ε > 0 be fixed. Assuming the 3-XOR distinguishing conjecture, there is no polynomial time algorithm for agnostic tensor completion that guarantees that for any distribution D, with probability at least 1o(1),
Our results demonstrate the power of the sum-of-squares hierarchy for agnostic statistical learning, and show that sum-of-squares algorithms can obtain fast rates for prediction with the square loss. We hope our work will serve as a starting point for applying sum-of-squares to obtain polynomial time algorithms with fast rates in statistical learning for broader classes of models.
A few immediate technical questions emerge. Can the dependence on rank in our results be improved? Can the subgradient results be extended to the general undercomplete or even overcomplete case? Can similar agnostic learning results be obtained with a more practical algorithm that does not rely on solving the full sum-of-squares SDP?
A.1 Sum-of-squares proof system
and where and deg(p S ∏ i∈S f i ) ≤ ℓ for all S and deg(q i g i ) ≤ ℓ for all i. 8 We write A ⊢ ℓ {h ≥ 0} whenever such a proof exists. Our proofs going forward utilize the well-known duality of SoS proofs and pseudodistributions. See O'Donnell and Zhou (2013) and Barak and Steurer (2016) for further discussion, as well as inference rules for the SoS proof system.
We note the following well-known, but useful lemma: Lemma 1 (Pseudo-Cauchy Schwarz). Let f and g be polynomials and let ℓ = 2 max{deg f, deg g}. Then for any η > 0,
As a consequence, if µ is a degree-s pseudodistribution with s ≥ ℓ, then
A.2 Basic technical results
We state a few lemmas capturing useful properties of the sum-of-squares norms. Proposition 1. The SoS nuclear norm and SoS injective norm are dual:
Proof of Proposition 1. It is immediate from the norm definitions that
The other direction is a consequence of the standard duality theory for finite-dimensional Banach spaces.
See, e.g., Theorem 15.4 in Rockafellar (1970).
Lemma 2. Let T = ∑ r i=1 λ i ⋅ u i ⊗ v i ⊗ w i be an orthogonal rank-r tensor. Then for all k ≥ 4.
Lemma 2 states that the SoS relaxations of the nuclear norm and injective norm are essentially "integral" for orthogonal tensors. Note, this should not be a huge surprise since it is well-known that polynomial time methods such as power iteration succeed at decomposing orthogonal tensors (Kolda and Bader, 2009). We should mention it doesn't seem possible to directly apply such results to give agnostic learning guarantees along the lines of our main theorem. While our benchmark is an orthogonal tensor, the data itself may have no orthogonal structure, and thus there is no clear object to which one might apply such a decomposition.
Proof of Lemma 2. We may assume λ i ≥ 0 without loss of generality. We first prove equality for the injective norms. Let i ⋆ = arg max i≤r λ i . As a starting point, for any k we have
For the upper bound, let x, y, z be indeterminates and-exploiting orthogonality-let us change coordinates such that
From equation (20), we have
We also have
. By the additivity of SoS proofs, and since we have assumed λ i ≥ 0, this implies
Putting everything together, we see that A ⊢ 4 ⟨T, x ⊗ y ⊗ z⟩ ≤ max i≤r λ i . Thus, since the ℓ 2 norm is preserved under change of basis, it follows that if µ is any feasible degree-4 pseudodistribution for the maximization problem (6), we must have Ẽµ ⟨T, x ⊗ y ⊗ z⟩ ≤ max i λ i , and so T ĩ nj k ≤ max i λ i .
We now establish equality for the nuclear norms. We trivially have
as a feasible solution to the minimization problem in (4). For the other direction, define X ⋆ = ∑ r i=1 u i ⊗ v i ⊗ w i , and observe that the equality we just established for the injective norm implies X ⋆ ĩ nj k ≤ 1. Thus, using the duality of the SoS nuclear norm and injective norm from Proposition 1, we have
where the last equality uses that {u i }, {v i }, and {w i } are all orthogonal.
Proposition 2. Let k ≥ 4. For any degree-k pseudodistribution µ,
Furthermore, the following statements hold:
Proof of Proposition 2. Equation ( 23) follows by rescaling a given pseudodistribution µ by using x ′ =
x Ẽµ x 2 2 and so forth, so that the pseudodistribution is feasible for the maximization problem (6).
For (24), let µ be a degree-k pseudodistribution with µ ⊧ z 2 2 ≤ 1 . Then, using (23) and the AM-GM inequality we get 纀T, Ẽµ
Using linearity of the pseudoexpectation operator we have Ẽµ
2 + y 2 2 -⟨T, x ⊗ y ⊗ z⟩ ≥ 0, and so (24) follows from the duality of pseudoexpectations and sum-of-squares proofs. The remaining statements follow by symmetry.
Here we state some basic results regarding the projection operators defined in Section 2.2. Proposition 3. Let x, y, z ∈ R d be given. If at least two of the follow conditions hold:
Proof of Proposition 3. Suppose that x ∈ U and y ∈ V. Then P U ⊥ (x) = 0, and so
We also have P V ⊥ (y) = 0, and so
The remaining cases follow by symmetry.
Lemma 3. Let k ≥ 4. For any tensor X ∈ (R d ) ⊗3 , and any subspaces U, V, W we have
and in particular
Proof of Lemma 3. For any degree-4 pseudodistribution µ over indeterminates x, y, z we have
where the first inequality uses Proposition 2 and the second uses that ⊢ 2 P X x 2 2 ≤ x 2 2 for any subspace X. This establishes the first result. Now observe from (11
We thus obtain the second result by applying the first to each of the summands.
The multilinear rank of a tensor T ∈ (R d ) ⊗3 is the triple (r 1 , r 2 , r 3 ), where
is the dimension of the space spanned by the mode-1 fibers and r 2 (T ) and r 3 (T ) are defined likewise for the second and third mode.
We define the ith flattening map ♭i ∶
A standard result is that rank(♭ i (T )) = r i (T ) (Friedland and Lim, 2018). We also have the following comparison between the nuclear norm of the tensor and its flattenings. Lemma 4 (Friedland and Lim (2018), Theorem 9.4). For any tensor T ∈ (R d ) ⊗3 ,
Lemma 5 (Talagrand-type concentration for supremum of empirical process). Let F be a class of functions of the form f ∶ Z → R. Let z 1 , . . . , z n be sampled i.i.d. from a distribution D over Z that satisfies E[f (z)] = 0 and has f (z) ≤ c almost surely. Let σ 2 = sup f ∈F E f 2 (z). Then for any δ > 0, with probability at least 1 -2δ over the i.i.d. draw of z 1 , . . . , z n ,
Proof of Lemma 5. Follows from Theorem A.1 of Bartlett et al. (2005) applied to the classes F and -F separately, along with the standard in-expectation symmetrization lemma for uniform convergence.
The main result in this section is to prove Theorem 4, then use this result to prove Theorem 3. Before proceeding to the main proofs we state an intermediate result.
Lemma 6 (Potechin and Steurer (2017)). Let x, y, z ∈ R d be indeterminates. Let A = y 2 2 = 1 . Then for any r ∈ [d],
Proof of Corollary 1. We will show that A ⊢ 6 -∑ d i=1 ∑ j≠i y 2 i y 2 j x 2 2 = -∑ d i=1 ∑ j≠i y 2 i y 2 j ; the term involving z 2 2 follows from the same reasoning. The desired inequality is equivalent to ∑ d i=1 ∑ j≠i y 2 i y 2 j ( x 2 2 -1) = 0, which is clearly the product of a degree-4 polynomial and the equality constraint x 2 2 -1 = 0 .
Proof of Theorem 4. Preliminaries. We first claim that the following equalities hold:
Indeed, it is immediate from the definition of X ⋆ that Q 0 T ∥ (X ⋆ ) = X ⋆ , and it follows from Lemma 2 that X ⋆ ĩ nj k = 1 and ⟨X ⋆ , T ⟩ = T nuc k for all k ≥ 4.
Bounding dual norm is sufficient. To establish the inequality (13), we reduce to a simpler problem. The claim is as follows: Fix a constant α > 0. If for all X ∈ (R d ) ⊗3 with X ĩ nj k ≤ α, we have
then ( 13) holds for all X with X ĩ nj k ≤ α. To see that this is the case, observe that for any T ′ and all such X we have
where the first inequality uses Proposition 1, the second inequality uses ( 27), and the final equality uses the definition of X ⋆ and that ⟨Q T ⊥ (X), T ⟩ = ⟨X, Q T ⊥ (T )⟩ = 0. Rearranging the inequality yields (13).
Bounding the dual norm. The remainder of the proof establishes that ( 27) holds for α = 1 64.
Let x, y, z ∈ R d be indeterminates. We will provide a degree-(k + 2) SoS upper bound on the polynomial ⟨X ⋆ + Q T ⊥ (X), x ⊗ y ⊗ z⟩, which will suffice to establish (27).
Let
), and W = span({w i } r i=1 ), so that {u i } r i=1 is a basis for U, and likewise for the other modes. Let {u i } d i=r+1 be an arbitrary orthonormal basis for U ⊥ and likewise with {v i } d i=r+1 for V ⊥ , and {w i } d i=r+1 for W ⊥ . We perform a change of basis and let u i = v i = w i = e i , where e i is the ith standard basis vector. Then with x, y, z expressed in the new basis we can write
We now handle the second term in (28). We will establish that
under the assumption that X ĩ nj k ≤ α. To do this it suffices show that for each i individually,
with an extra additive factor of O(α) ⋅ y 2 i (x 2 i + z 2 i ) when i > r. Let 1 ≤ i ≤ d be fixed and let x ′ = xx i e i , y ′ = yy i e i , and z ′ = zz i e i . We write
Case: i ≤ r. Observe that with our change of basis we have e i ∈ U along the first mode, e i ∈ V along the second mode, and e i ∈ W along the third mode. In view of Proposition 3, this means we have
Consequently, using multilinearity we can write
In what follows we will repeatedly invoke that
2 ≤ 1, and so forth. We will also use that if X ĩ nj k ≤ α then-via Proposition 2 and Lemma 3-for any indeterminates a, b, c,
These inequalities allow us to bound the terms in (31) as follows:
Adding these inequalities, we get
and by the multiplication rule for SoS proofs,
Case: i > r. As in the previous case, we split the expression ⟨Q T ⊥ (X), (x i e i + x ′ ) ⊗ (y i e i + y ′ ) ⊗ (z i e i + z ′ )⟩ in (30) using multilinearity, however we can no longer argue that four of the eight terms vanish. As a starting point, for the four terms that appeared in the i ≤ r case we can adopt the same upper bound to get
We bound the four remaining terms as follows:
Adding together all of these inequalities, we get
and
Putting everything together. Taking the inequalities we proved for the individual coordinates i and summing them up, we have
Since y 2 2 = 1 ⊂ A, we get
Returning to (28), this inequality plus the earlier bound from Corollary 1 imply
By the duality of SoS proofs and pseudodistributions, we have
≤ 1 as desired.
Proof of Theorem 3. We first establish equation ( 14). We combine the assumption that T ′ nuc k+2 ≤ T nuc k with equation ( 13) to get
for all X with X ĩ nj k ≤ 1 64 and X ⋆ as in Theorem 4. Rearranging, this yields
We now use that X ⋆ ĩ nj k ≤ 1 (from Theorem 4) and choose X to be a point obtaining the supremum in
We now establish equation ( 9). Observe that we can write
Combining this with ( 14), we get
Using the triangle inequality, we upper bound the first term as
To proceed, we flatten each tensor in the summation above into a matrix and use Lemma 4 to show that the nuclear norm of the flattening leads to an upper bound. Let r 1 = dim U, r 2 = dim V, and r 3 = dim W. Then the following inequalities hold
The first inequality in each line above follows from Lemma 4 and the definitions in ( 11). The second follows from the fact that A nuc ≤ rank(A) A F for any matrix A, along with the fact that rank(♭ i (T )) = r i (T ) for any tensor, and that flattening does not change the entrywise ℓ 2 norm. We have
F as well by the same argument, though the choice of r 1 r 2 r 3 in this case is arbitrary. To combine all the bounds, we use that r 1 , r 2 , r 3 ≤ r and that orthogonal projection decreases the ℓ 2 norm, which yields
This section of the appendix is structured as follows.
First, in Appendix C.1, we provide we provide a generalization bound for general classes of tensors and measurement models, from which all of our main statistical results will follow as special cases. This bound assumes that a restricted eigenvalue-type property holds for the tensor class and measurement model under consideration.
In Appendix C.2 and Appendix C.3 we establish that this restricted eigenvalue property holds for the measurement models in Section 3.
In Appendix C.4 we combine these results to prove the main results of that section.
In this section we given generalization guarantees for empirical risk minimization in a general learning setup. We receive a set of examples S ∶= (X 1 , Y 1 ), . . . , (X n , Y n ) i.i.d. from a distribution D over (R d ) ⊗3 × R. We assume that a convex class of tensors eT ⊆ (R d ) ⊗3 is given, and that our goal is to achieve excess risk against an unknown benchmark T ⋆ ∈ T . We analyze the performance of empirical risk minimization over T :
where Ln is the empirical square loss. The main result from this section is Theorem 8, which bounds the performance of ERM under various assumptions on the data distribution, the class T , and the benchmark T ⋆ . To state the result, recall from Section 3 that Σ is the population correlation matrix and X n is the empirical design operator. Theorem 8. Let a benchmark T ⋆ ∈ T be fixed, and let ξ t = (Y t -⟨T ⋆ , X t ⟩). Suppose there exist a pair of dual norms ⋅ and ⋅ ⋆ for which the following conditions hold:
1. There are constants 0 ≤ c < 2, γ n > 0, and δ 0 ≥ 0 such that with probability at least 1δ 0 ,
2. There are constants M ≥ 0 and δ 1 ≥ 0 such that with probability at least
3. There is a constant κ ≥ 0 such that
Then with probability at least 1 -(δ 0 + δ 1 ),
Proof of Theorem 8. Since T is convex, and since Tn minimizes the (strongly convex) empirical risk, we have Ln (T ⋆ ) -Ln ( Tn ) ≥ 纀∇ Ln ( Tn ),
By rearranging and expanding the definition of Ln , this implies
Since the left-hand side is non-negative, we can add it to the population excess risk, which implies
Rearranging, this is equal to
Since Tn -T ⋆ is an element of T -T ⋆ , we move to an upper bound by taking a supremum over elements of this set. ≤ sup
This establishes inequality (18). It remains to use the assumptions in the theorem statement to bound the process. Property 1 states that with probability at least 1δ 0 , E⟨∆, X⟩ 2 ≤ c ⋅ Ên ⟨∆, X⟩ 2 + γ n for all ∆ ∈ T -T ⋆ . Define c ′ = 2c > 0, so that conditioned on this event we have sup
We expand the first term in the supremum as
It follows from Hölder's inequality that this expression is bounded as
, the development so far states that with probability at least 1δ 0 ,
Using Property 3 we upper bound the leading term by
and the event we already conditioned on implies that this is at most
where the second inequality follows from AM-GM. Finally, by Property 2 we have that with probability at least 1δ 1 , ψ n ≤ M √ n, which leads to the final bound of
The main result in this section is Theorem 9, which relates the empirical covariance and population covariance for all tensors with bounded entries and bounded SoS nuclear norm under sampling model for tensor completion. This result is then used in the proof of Theorem 5 to establish a restricted eigenvalue guarantee.
Theorem 9. Let d 3 2 ≤ n ≤ d 3 , and let ε ∈ (0, 1 2). Suppose observed entries are drawn with replacement. Then for any δ > 0, with probability at least
The proofs in this section pass back and forth between the with-replacement sampling model for tensor completion used in the main body of the paper and a without-replacement model, in which each entry is only observed a single time for tensor completion. To distinguish between the models, we use S ∼ D n wr to refer to the draw of the dataset under the with-replacement sampling model and S ∼ D n w o to refer to the draw under the without-replacement model. Ω ⊆ [d] 3 will denote the support of the set of observed entries.
Before proving Theorem 9, we state and prove a number of auxiliary lemmas, from which the main result will follow.
Proof of Proposition 4. This is an immediate consequence of Bernstein's inequality for without-replacement sampling. See Bardenet et al. (2015), Proposition 1.4.
Lemma 7. The Rademacher complexity of ⋅ ĩ nj 4 under without-replacement sampling is bounded as
Additionally, if n ≤ d 3 , then the Rademacher complexity under with-replacement sampling is bounded as
Proof of Lemma 7. We first bound the Rademacher complexity in the without-replacement sampling case, then handle the with-replacement case by reduction. This analysis follows Barak and Moitra (2016), except that we handle certain "diagonal" terms that arise in the analysis slightly more carefully so as to get the right scaling for our setup, which differs from theirs in that it does not assume incoherence.
Consider a fixed draw of ǫ 1∶n and X 1∶n , and let Z = ∑ n t=1 ǫ t X t . Leting x, y, z be indeterminates, we will give a degree-four SoS upper bound on the polynomial ⟨Z, x ⊗ y ⊗ z⟩. This will imply that the pseudoexpectation of ⟨Z, x ⊗ y ⊗ z⟩ is bounded for any feasible pseudodistribution in the maximization problem defining ⋅ ĩ nj 4 .
To begin, for any fixed constant η > 0, Lemma 1 implies that
and so
and
We bound the first term by the operator norm of B via
For the second term, define another matrix
By the duality of sum-of-squares proofs and pseudodistributions, this implies that any degree-four pseu-
Optimizing over η, we conclude that
The bound for the matrix B is taken care of Theorem 4.4 of Barak and Moitra (2016), which implies that
. For the matrix R, observe that under the without-replacement sampling model, for any j, k we have
Proposition 4 thus implies that for any fixed j, k, with probability at least 1δ,
and so, by taking a union bound and integrating out the tail, we have
Combining the bounds on B and R and using Jensen's inequality yields
This completes the bound for the without-replacement case. For the with-replacement case we reduce to the bound on the second moment above. Condition on the draw of S, and let
Then we have
Introduce a new sequence of Rademacher random variables σ ∈ {±1} d 3 . Then the right-hand side above is equal to
, where the inequality follows from the standard Lipschitz contraction lemma for Rademacher complexity (Ledoux and Talagrand, 1991). By the Hoeffding bound, we have that for any fixed index (i, j, k) with probability at least 1δ,
Taking a union bound and integrating out the tail, we have
We now move to the final bound by taking the expectation over S. Using Cauchy-Schwarz, the development above implies
Bernstein's inequality and the union bound imply that
where the second inequality uses that n ≤ d 3 . For the second term, we have
where the second inequality uses the bound we proved for the without-replacement setting and the second inequality uses m ≤ n and that the probabilities sum to one. Combining these two bounds completes the proof.
Under the with-replacement sampling model, when d 3 2 ≤ n ≤ d 3 , we have that for any δ > 0, with probability at least 1δ,
Proof of Lemma 8. To begin, we write
Using this representation, since entries are drawn i.i.d. with replacement, we can apply Lemma 5 with the function class F = X ↦ ⟨T, X⟩ 2 -E⟨T, X⟩ 2 T ∈ T . In particular, note that for all T ∈ T we have ⟨T, X t ⟩ = T it,jt,kt ≤ R, and furthermore
Consequently, Lemma 5 implies that with probability at least 1δ, for all T ∈ T ,
Using Jensen's inequality and splitting the supremum, we have
Using the Lipschitz contraction lemma for Rademacher complexity, we remove the square
Finally, using Lemma 7, we have
The final bound follows by using n ≥ d 3 2 to simplify this expression.
Proof of Theorem 9. Let T = T ∈ (R d ) ⊗3 T ∞ ≤ R . Recall that for tensor completion, the population correlation matrix Σ under with-replacement sampling is equal to 1
n, and let N = ⌈log(τ max τ min )⌉ + 1 and M = ⌈log(β max β min )⌉ + 1. For each i ∈ [N ] and j ∈ [M ] define τ i = τ max e 1-i and β j = β max e 1-j . Define
Using Lemma 8 and a union bound, we get that with probability at least 1δ, for all i, j simultaneously, for all T ∈ T i,j ,
Now consider a fixed tensor T ∈ T . There are two cases. First, if T nuc 4 ≥ τ min and Σ 1 2 T F ≥ β min , then there must be indices i and j for which τ i+1 ≤ T nuc ≤ τ i , β j+1 ≤ Σ 1 2 T F ≤ β j . Consequently, the uniform bound above implies
On the other hand, if either T nuc ≤ τ min or Σ 1 2 T F ≤ β min , we trivially have
Combining these cases, and using the values for N and M , we get that with probability at least 1δ, for all T ∈ T ,
Using the AM-GM inequality on the second-to-last term and rearranging, we have that for any ε > 0,
When ε ∈ (0, 1 2), this implies
In the remainder of the section we prove Lemma 9. The result follows from fairly standard techniques (e.g. Wainwright (2019)), but we include the proof for completeness. We first restate some basic results on gaussian concentration. Lemma 11 (Concentration for Lipschitz functions (Milman and Schechtman, 1986)). Let Z ∈ R n have entries drawn i.i.d. from N (0 ; 1), and let f ∶ R n → R be L-Lipschitz with respect to the ℓ 2 norm. Then for all t ≥ 0, Lemma 12 (Gordon's Inequality (Davidson and Szarek, 2001)). Let Z a,b and Y a,b be zero-mean gaussian processes indexed by A × B. Suppose that
Proof of Lemma 9. Part 1: Bound at a single scale.
We will prove that with probability at least 1 -2e
We will prove a lower bound on the random variable min ∆∈B(τ )
1 √ n X n (∆) 2 , which is equivalent to providing an upper bound on the random variable
As a starting point, we show how to upper bound the expectation
. Note that Z ∆,u is a gaussian process with variance n -1 , since ∆ F = 1. We now define a new gaussian process that will serve as an upper bound through Gordon's inequality. Let g ∈ R p and h ∈ R n be standard gaussian random variables, and define
Note that for any (∆, u) and (∆ ′ , u ′ ) we have
Interpreting ∆ and ∆ ′ as vectors in R d 3 , we also have
where we have used that
It is also easily seen from the representation above that for any triple (∆, u, u ′ ) we have equality:
. This means that the preconditions of Lemma 12 are satisfied, and so
The provides the desired upper bound in expectation. To establish the high probability result we appeal to gaussian concentration for Lipschitz functions. Let X ∈ R n×d 3 denote the sequence of measurements X 1 , . . . , X n , interpreted as a matrix with vectorized measurements as rows. Define
and so f is n -1 2 -Lipschitz with respect to ℓ 2 . Lemma 11 therefore implies that
In other words, (39) holds.
Part 2: Bound at all scales. We will show that for any ε < 2 π, with probability at least 1 -2e
Set µ = ε 2 and consider the classes B(0, µ) and B(2 i-1 µ, 2 i µ) for i ∈ N. Note that if equation ( 40) fails to hold and ∆ ∈ B(0, µ) then
Furthermore, if equation ( 40) fails to hold and
Our development in part 1 of the proof implies that for any fixed τ ℓ ≤ τ u , with probability at least 1 -
Thus, by a union bound, we get that with probability at least 1 -2e -n 32 ∑ ∞ i=0 e -2 2i nε 2 8
, or conservatively at
or in other words, equation ( 40) holds.
We extend the guarantee in equation ( 40) to arbitrary ∆ ∈ R p by rescaling so that ∆ F = 1 and then exploiting homogeneity to get
Proof of Theorem 5. We prove the theorem by appealing to the generic result of Theorem 8 using norms ⋅ = ⋅ ĩ nj 4 and ⋅ ⋆ = ⋅ nuc 4 . Let T ⋆ be an arbitrary rank-r orthogonal tensor with T ⋆ nuc 6 = τ and T ⋆ ∞ ≤ R. First, observe that all elements T ∈ T have T nuc 6 ≤ T ⋆ nuc 6 . Consequently, Theorem 3 implies that all
which establishes Property 3 with κ = O(r ⋅ d 3 2 ).
To establish Property 2 we appeal to Theorem 9, which implies that for any ε < 1 2, with probability at least
Using equation ( 42) this is upper bounded by
Using the AM-GM inequality, this is further upper bounded by
Rearranging, this is equivalent to
and since ε < 1 2 this implies
Making the somewhat arbitrary choice of ε = 1 100, and simplifying the right-hand-side, we get
So we can take c = 1.1 and
Finally, we establish Property 1. Lemma 5 establishes that with probability at least 1δ,
Using Lemma 7 with the standard in-expectation Lipschitz contraction lemma (e.g., Ledoux and Talagrand (1991)), we have
Since n = Ω(d 3 2 ), these bounds together imply that we can take M = O R
.
Theorem 8 now implies the claimed result.
Proof of Theorem 6. As in the tensor completion case, we prove the theorem by appealing to Theorem 8 using norms ⋅ = ⋅ ĩ nj 4 and ⋅ ⋆ = ⋅ nuc 4 .
Let T ⋆ be an arbitrary orthogonal tensor with
and thus, since Σ = I, we may take κ = 68r to establish Property 3.
To establish Property 2 we appeal to Theorem 10. This implies that for any ε < 2 π, with probability at
where C > 0 is some absolute constant. Using equation ( 43), we have that for all ∆ ∈ T -T ⋆ , conditioned on the event above,
This means that when n = Ω(r 2 (T ⋆ )d 3 2 log 1 2 d ε), we have
It suffices to set ε = 1 40 to get
So, simplifying, Property 2 is satisfied with c = 1.8 and γ n = 0 with probability at least 1e -n 64 when n = Ω(r 2 (T ⋆ )d 3 2 log 1 2 d).
To establish Property 1 we use Lemma 10, but some care needs to be taken to establish that this applies with high probability. Pick a constant τ ≥ 0, and observe via Lemma 11 that
Define a truncated sequence X ′ t = X t ½ X t F ≤ d 3 2 + τ , and set δ 0 = 2ne -τ 2 2 . Observe that with probability at least 1δ 0 , X t = X ′ t for all t, and so .
We apply Lemma 5 to the truncated complexity, which implies that with probability at least 1 -(δ + δ 0 ),
where σ 2 = sup T nuc 4 ≤1 E ⟨T, X ′ ⟩ 2 (⟨T ⋆ , X t ⟩ -Y t ) 2 ≤ sup T nuc 4 ≤1 T 2 F ⋅ 4R 2 ≤ 4R 2 . We now apply Lipschitz contraction to bound the in-expectation Rademacher complexity as
.
Integrating out the tail, we can bound the error due to truncation as
for some absolute constant C. We pick τ = ( (d 3 2 n + log(1 δ)) C ), so that the quantity above is o(1) and δ 0 ≤ δ. Lastly, since X 1∶n are gaussian, Lemma 10 implies
When n ≥ d 3 2 , we have d 3 2 ≤ d 3 4 √ n, and so we conclude that with probability at least 1δ,
Proof of Theorem 7. Let ε > 0 be fixed and let m = d 3 2-ε 2 .
We will generate an instance of tensor completion from the 3-XOR instance by treating the indices (i, j, k) in each clause as an observed entry. Precisely, for each clause, we set the corresponding X = e i ⊗ e j ⊗ e k , and the corresponding Y = z ijk . The induced risk for each tensor T in this setting is simply L D Z (T ) ∶= 1 d 3 ∑ i,j,k (T i,j,k -Z i,j,k ) 2 , where the tensor Z ∈ ({±1} d ) ⊗3 is defined as follows: in the random case, the entries of Z are selected uniformly at random from {±1}; in the planted case with planted assignment a ∈ {±1} d , we start off with the tensor a ⊗3 , then get Z by flipping each coordinate independently with probability η.
If we set n = Ω(m), then we are guaranteed to receive Ω(m) unique clauses under with-replacement sampling, since there are at most logarithmically many repeats with inverse polynomial probability for m = o(d 3 2 ). With this observation, it is clear that any algorithm that takes as input the examples S and outputs "Planted" with probability at least 1o(1) when Z comes from the planted distribution and "Random" with probability at least 1o(1) when Z is from the random distribution is a successful distinguisher for the planted 3-XOR problem with Θ(m) clauses. Going forward we assume n = Ω(d), since this is the interesting regime for distinguishing and refutation.
Now, suppose we have an algorithm that enjoys the excess risk bound (19) for any n, and let TS denote its output given input dataset S. Since Z ∈ ({±1} d ) ⊗3 we can take TS ∞ ≤ 1 without loss of generality. We will turn TS into a successful distinguishing algorithm for the planted 3-XOR problem as follows: Define γ = 1 -4η, and note the assumption that η < 1 4 implies that γ > 0. Split the sample set S into halves S 1 and S 2 , and let LS 1 and LS 2 denote the empirical risk on the respective halves. Let TS 1 be the output of the assumed algorithm on S 1 . If LS 2 ( TS 1 ) ≥ 1γ 4 2 return "Random", else return "Planted".
We will show that the algorithm succeeds in both the planted and random case by analyzing the value of LS 2 ( TS 1 ) in each case.
Random case. Let S ′ 2 be the result of removing all entries that appear in S 1 from S 2 . The number of repeats is at most O(n 2 d 3 + log(1 δ)) with probability at least 1δ. It follows that with probability at least, say, 1 -O(d -1 ), S ′ 2 S 2 ≥ 1o(1), and LS 2 ( TS 1 ) ≥ LS ′ 2 ( TS 1 )o(1).
Observe that for every remaining example X = e i ⊗e j ⊗e k in S ′ 2 , the value of TS 1 is statistically independent of the value of Z i,j,k . Abbreviating TS 1 to T , this means that we have
2 X=e i ⊗e j ⊗e k ∈S ′ 2 ( Ti,j,k ) 2 + 1 ≥ 1.
Condition on S ′ 2 . Since TS 1 and Z have bounded entries, it follows from Hoeffding's inequality that with probability at least 1δ over the choice of Z, This proves that our strategy will indeed return "Random" for random instances.
Planted case. For any Z, the assumed excess risk bound implies that for any rank-1 tensor T ⋆ with bounded entries, we have L D Z ( TS 1 ) -L D Z (T ⋆ ) ≤ o(1),
when n = ω(d 3 2-ε ). We choose T ⋆ = a ⊗3 , where a ∈ {±1} d is the planted assignment. Taking expectation over the flips in Z, we have
Applying Bernstein's inequality, we have that with probability at least 1 -O(d -1 ) over the choice of Z,
Finally, we use Bernstein once more to show that the empirical loss for S 2 converges to the population loss, leveraging that S 2 is an independent hold-out set for TS 1 . We have that for any choice of S 1 , with probability at least 1δ over the draw of S 2 ,
where c 1 and c 2 are absolute constants. Applying AM-GM, this implies that LS 2 ( TS 1 ) ≤ (1+γ 2 )L D Z ( TS 1 )+ o(1) with probability at least 1-O(d -1 ), and so by combining this with the excess risk bound and the bound on L D Z (a ⊗3 ), we have LS 2 ( TS 1 ) ≤ 1γ 4 + o(1).
Interestingly, their results also show that incoherence-usually taken as necessary in matrix completion for positive results -is not necessary to obtain prediction error bounds; boundedness suffices.
Here the word "exact" refers to the fact that the leading constant in front of the loss on the right-hand-side is 1; such guarantees generally do not easily follow from the usual machinery used to analyze well-specified models.
There are minor technical differences (e.g., scaling) between the SoS injective/nuclear norm definitions we use and those ofBarak and Moitra (2016);Potechin and Steurer (2017).
This equivalence is proven in Appendix A for completeness.
Following the convention in Section 1.3, if X = ∑ i ai ⊗ bi ⊗ ci, then (P U ⊗ P V ⊗ P W )X = ∑ i (P U ai) ⊗ (P V bi) ⊗ (P W ci). It is also useful to note that for any x, y, z we have ⟨(P U ⊗ P V ⊗ P W ), x ⊗ y ⊗ z⟩ = ⟨X, (P U x) ⊗ (P V y) ⊗ (P W z)⟩.
Note that we sample entries with replacement, whereas related works use without-replacement sampling(Barak and Moitra, 2016;Potechin and Steurer, 2017).
We work in the slightly non-standard with-replacement model to simplify the mapping onto the with-replacement tensor completion model in Theorem 5.
We use the convention ∏ i∈∅ fi = 1, so that if ⊢ ℓ h then h itself is a degree-ℓ sum of squares.