Beyond the Signs: Nonparametric Tensor Completion via Sign Series
Year: 2021

Abstract:
We consider the problem of tensor estimation from noisy observations with possibly missing entries. A nonparametric approach to tensor completion is developed based on a new model which we coin as sign representable tensors. The model represents the signal tensor of interest using a series of structured sign tensors. Unlike earlier methods, the sign series representation effectively addresses both lowand high-rank signals, while encompassing many existing tensor models— including CP models, Tucker models, single index models, structured tensors with repeating entries—as special cases. We provably reduce the tensor estimation problem to a series of structured classification tasks, and we develop a learning reduction machinery to empower existing low-rank tensor algorithms for more challenging high-rank estimation. Excess risk bounds, estimation errors, and sample complexities are established. We demonstrate the outperformance of our approach over previous methods on two datasets, one on human brain connectivity networks and the other on topic data mining.

heading: 1 Introduction
text: Higher-order tensors have recently received much attention in enormous fields including social networks [3], neuroscience [38], and genomics [26]. Tensor methods provide effective representation of the hidden structure in multiway data. In this paper we consider the signal plus noise model,
Y = Θ + E , (1)
where Y ∈ Rd1×···×dK is an order-K data tensor, Θ is an unknown signal tensor of interest, and E is a noise tensor. Our goal is to accurately estimate Θ from the incomplete, noisy observation of Y . In particular, we focus on the following two problems:
Q1 [Nonparametric tensor estimation]. How to flexibly estimate Θ under a wide range of structures, including both low-rankness and high-rankness?
Q2 [Complexity of tensor completion]. How many observed tensor entries do we need to consistently estimate the signal Θ?
Inadequacies of low-rank models. The signal plus noise model (2) is popular in tensor literature. Existing methods estimate the signal tensor based on low-rankness of Θ [28, 34]. Common low-rank models include Canonical Polyadic (CP) tensors [24], Tucker tensors [11], and block tensors [40]. While these methods have shown great success in theory, tensors in applications often violate the low-rankness. Here we provide two examples to illustrate the limitation of classical models.
The first example reveals the sensitivity of tensor rank to order-preserving transformations. Let Z ∈ R30×30×30 be an order-3 tensor with tensor rank(Z) = 3 (formal definition is deferred to the end of this section). Suppose a monotonic transformation f(z) = (1 + exp(−cz))−1 is applied to Z
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
entrywise, and we let the signal Θ in model (1) be the tensor after transformation. Figure 1a plots the numerical rank (see Appendix B.1) of Θ versus c. As we see, the rank increases rapidly with c, rending traditional low-rank tensor methods ineffective in the presence of mild order-preserving nonlinearities. Similar observations apply to both CP and Tucker models, and more generally, to lowrank models with scale-sensitive rank measures. In digital processing [17] and genomics analysis [26], the tensor of interest often undergoes unknown transformation prior to measurements. The sensitivity to transformation makes the low-rank model less desirable in practice.
The second example demonstrates the inadequacy of classical low-rankness in representing special structures. Here we consider the signal tensor of the form Θ = log(1 +Z), where Z ∈ Rd×d×d is an order-3 tensor with entries Z(i, j, k) = d−1 max(i, j, k) for i, j, k ∈ {1, . . . , d}. The matrix analogy of Θ was studied in graphon analysis [8]. In this case neither Θ nor Z is low-rank; in fact, the rank is no smaller than the dimension d as illustrated in Figure 1b. Again, classical low-rank models fail to address this type of tensor structure.
In the above and many other examples, the signal tensors Θ of interest have high rank. Classical low-rank models will miss these important structures. The observations have motivated us to develop more flexible tensor modeling.
Our contributions. We develop a new model called sign representable tensors to address the aforementioned challenges. Figure 2 illustrates our main idea. Our approach is built on the sign series representation of the signal tensor, and we propose to estimate the sign tensors through a series of weighted classifications. In contrast to existing methods, our method is guaranteed to recover a wide range of low- and high-rank signals. We highlight two main contributions that set our work apart from earlier literature.
Statistically, the problem of high-rank tensor estimation is challenging. Existing estimation theory [3, 34, 7] exclusively focuses on the regime of fixed r and growing d. However, such premise fails in high-rank tensors, where the rank may grow with, or even exceed, the dimension. A proper notion of nonparametric complexity is crucial. We show that, somewhat surprisingly, the sign tensor series not only preserves all information in the original signals, but also brings the benefits of flexibility and accuracy over classical low-rank models. The results fill the gap between parametric (low-rank) and nonparametric (high-rank) tensors, thereby greatly enriching the tensor model literature.
Computationally, a number of polynomial-time algorithms are readily available under moderate-tohigh signal-to-noise ratio for 1-bit tensor estimation [39, 20, 17]. These algorithms enjoy computational efficiency while being restricted to binary inputs. Our work is orthogonal to these algorithm development, and we show that the high-rank tensor estimate is provably reducible to a series of binary tensor problems with carefully-designed weights. This reduction provides a generic engine to empower existing algorithms for a wider range of structured tensor problems. We use a divideand-concur approach to combine efficient base algorithms, thereby achieving computational accuracy without the need to reinvent the wheel. The flexibility to import and adapt existing tensor algorithms is one advantage of our method.
We also highlight the challenges associated with tensors compared to matrices. High-rank matrix estimation has been studied under graphon models [41, 44, 8], nonlinear models [15], and subspace clustering [35, 13]. In particular, the recent work [30] proposes a general nonparametric framework to address a variety of matrix problems including regression and completion. However, high-rank tensor problems is more challenging, because the tensor rank often exceeds the dimension when
order K greater than two [4]. This is in sharp contrast to matrices (K = 2). We show that, applying matrix methods to higher-order tensors results in suboptimal estimates. A full exploitation of the higher-order structure is needed; this is another challenge we address in this paper.
Notation. We use [n] = {1, . . . , n} for n-set with n ∈ N+, an . bn if limn→∞ an/bn ≤ c for some constant c > 0, and an bn if c1 ≤ limn→∞ an/bn ≤ c2 for some constants c1, c2 > 0. We use O(·) to denote the big-O notation, Õ(·) the variant hiding logarithmic factors. Let Θ ∈ Rd1×···×dK denote an order-K (d1, . . . , dK)-dimensional tensor, and Θ(ω) ∈ R denote the tensor entry indexed by ω ∈ [d1]× · · · × [dK ]. An event A is said to occur “with very high probability” if P(A) tends to 1 faster than any polynomial of tensor dimension d := mink dk →∞. The tensor rank [24] is defined by rank(Θ) = min{r ∈ N : Θ = ∑r s=1 a (1) s ⊗ · · · ⊗ a(K)s }, where a(k)s ∈ Rdk are vectors for k ∈ [K], s ∈ [r], and ⊗ denotes the outer product of vectors. We use sgn(·) : R→ {−1, 1} to denote the sign function, where sgn(y) = 1 if y ≥ 0 and −1 otherwise. We allow univariate functions, such as sgn(·) and general f : R→ R, to be applied to tensors in an element-wise manner.

heading: 2 Model and proposal overview
text: Let Y be an order-K (d1, . . . , dK)-dimensional tensor generated from the model
Y = Θ + E , (2)
where Θ ∈ Rd1×···×dK is an unknown signal tensor, and E is a noise tensor consisting of zero-mean, independent but not necessarily identically distributed entries. We allow heterogenous noise, in that the marginal distribution of noise entry E(ω) may depend on ω. For a cleaner exposition, we assume the noise is bounded and the range of observation is in [−1, 1]; the extension to unbounded observations with sub-Gaussian noise is provided in Appendix B.3. Our observation is an incomplete data tensor from (2), denoted YΩ, where Ω ⊂ [d1]× · · · × [dK ] is the index set of observed entries. We consider a general model on Ω that allows both uniform and non-uniform samplings. Specifically, let Π = {pω} be an arbitrarily predefined probability distribution over the full index set with∑ ω∈[d1]×···×[dK ] pω = 1. We use ω ∼ Π to denote the sampling rule, meaning ω in Ω are i.i.d. draws with replacement from distribution Π. The goal is to estimate Θ from YΩ. Note that Θ is not necessarily low-rank.
Proposal intuition. Before describing our main results, we provide the intuition behind our method. In the two examples in Section 1, the high-rankness in the signal Θ makes the estimation challenging. Now let us examine the sign of the π-shifted signal sgn(Θ − π) for any given π ∈ [−1, 1]. It turns out that, these sign tensors share the same sign patterns as low-rank tensors. Indeed, the signal tensor in the first example has the same sign pattern as a rank-4 tensor, since sgn(Θ− π) = sgn(Z − f−1(π)). The signal tensor in the second example has the same sign pattern as a rank-2 tensor, since sgn(Θ(i, j, k)−π) = sgn(max(i, j, k)−d(eπ−1)) (see Example 5 in Section 3).
The above observation suggests a general framework to estimate both low- and high-rank signal tensors. Figure 2 illustrates the main crux of our method. We propose to estimate the signal tensor Θ by taking the average over structured sign tensors
Θ̂ = 1
2H + 1 ∑ π∈H sgn(Ẑπ), where Ẑπ = arg min low rank tensor Z Weighted-Loss(sgn(Z), sgn(YΩ−π)). (3)
Here sgn(Ẑπ) ∈ {−1, 1}d1×···×dK is the sign tensor estimated at a series of π ∈ H = {−1, . . . , −1/H, 0, 1/H, . . . , 1}, and Weighted-Loss(·, ·) denotes a classification objective function with an entry-specific weight to each tensor entry; its specific form will be described in Section 3.2. To obtain sgn(Ẑπ) for a given π, we propose to dichotomize the data tensor into a sign tensor sgn(YΩ− π) and estimate the de-noised sign by performing weighted classification.
Our approach is built on the nonparametric sign representation of signal tensors. We show that a careful aggregation of dichotomized data preserves all information in the original signals and brings benefits of accuracy and flexibility over classical low-rank models. Unlike traditional methods, the sign representation is guaranteed to recover both low- and high-rank signals. In addition, a total of H = poly(d) dichotomized problems suffice to recover Θ under the considered model. The method therefore enjoys both statistical effectiveness and computational efficiency.

heading: 3 Oracle properties of sign representable tensors
text: This section develops sign representable tensor models for Θ in (2). We characterize the algebraic and statistical properties of sign tensor series, which serves the foundation for our method.

heading: 3.1 Sign-rank and sign tensor series
text: Let Θ be the tensor of interest, and sgn(Θ) the corresponding sign pattern. The sign patterns induce an equivalence relationship between tensors. Two tensors are called sign equivalent, denoted ', if they have the same sign pattern. Definition 1 (Sign-rank). The sign-rank of a tensor Θ ∈ Rd1×···×dK is defined by the minimal rank among all tensors that share the same sign pattern as Θ; i.e.,
srank(Θ) = min{rank(Θ′) : Θ′ ' Θ, Θ′ ∈ Rd1×···×dK}.
This concept is important in combinatorics [10], complexity theory [1], and quantum mechanics [12]; we extend the notion to continuous-valued tensors. Note that the sign-rank concerns only the sign pattern but discards the magnitude information of Θ. In particular, srank(Θ) = srank(sgnΘ).
Like most tensor problems [23], determining the sign-rank is NP hard in the worst case [1]. Fortunately, tensors arisen in applications often possess special structures that facilitate analysis. The sign-rank is upper bounded by tensor rank. More generally, we show the following properties. Proposition 1 (Upper bounds of the sign-rank). (a) [Upper bounds] For any strictly monotonic function g : R → R with g(0) = 0, we have srank(Θ) ≤ rank(g(Θ)). (b) [Broadness] For every order K ≥ 2 and dimension d, there exist tensors Θ ∈ Rd×···×d such that rank(Θ) ≥ d but srank(Θ− π) ≤ 2 for all π ∈ R. Propositions 1 demonstrates the strict broadness of low sign-rank family over the usual low-rank family. In particular, the sign-rank can be much smaller than the tensor rank, as we have shown in the two examples of Section 1. We provide several additional examples in Appendix B.2 in which the tensor rank grows with dimension d but the sign-rank remains a constant. The results highlight the advantages of using sign-rank in the high-dimensional tensor analysis.
We now introduce a tensor family, which we coin as “sign representable tensors”. Definition 2 (Sign representable tensors). Fix a level π ∈ [−1, 1]. A tensor Θ is called (r, π)-sign representable, if the tensor (Θ−π) has sign-rank bounded by r. A tensor Θ is called r-sign (globally) representable, if Θ is (r, π)-sign representable for all π ∈ [−1, 1]. The collection {sgn(Θ− π) : π ∈ [−1, 1]} is called the sign tensor series. We use Psgn(r) = {Θ: maxπ∈[−1,1] srank(Θ− π) ≤ r} to denote the r-sign representable tensor family.
We next show that the r-sign representable tensor family is a general model that incorporates most existing tensor models, including low-rank tensors, single index models, GLM models, and structured tensors with repeating entries. Example 1 (CP/Tucker low-rank models). The CP and Tucker low-rank tensors are the two most popular tensor models [29]. Let Θ be a low-rank tensor with CP rank r. We see that Θ belongs to the sign representable family; i.e., Θ ∈Psgn(r + 1) (the constant 1 is due to rank(Θ− π) ≤ r + 1).
Similar results hold for Tucker low-rank tensors Θ ∈Psgn(r + 1), where r = ∏ k rk with rk being the k-th mode Tucker rank of Θ. Example 2 (Tensor block models (TBMs)). Tensor block model [40, 9] assumes a checkerboard structure among tensor entries under marginal index permutation. The signal tensor Θ takes at most r distinct values, where r is the total number of multiway blocks. Our model incorporates TBM because Θ ∈Psgn(r). Example 3 (Generalized linear models (GLMs)). Let Y be a binary tensor from a logistic model [39] with mean Θ = logit(Z), where Z is a latent low-rank tensor. Notice that Θ itself may be high-rank (see Figure 1a). By definition, Θ is a low-rank sign representable tensor. Same conclusion holds for general exponential-family models with a (known) link function [25]. Example 4 (Single index models (SIMs)). Single index model is a flexible semiparametric model proposed in economics [36] and high-dimensional statistics [5, 14]. The SIM assumes the existence of a (unknown) monotonic function g : R→ R such that g(Θ) has rank r. We see that Θ belongs to the sign representable family; i.e., Θ ∈Psgn(r + 1). Example 5 (Structured tensors with repeating entries). Here we revisit the model introduced in Figure 1b of Section 1. Let Θ be an order-K tensor with entries Θ(i1, . . . , iK) = log(1+maxk x (k) ik ), where x(k)ik are given numbers in [0, 1] for all ik ∈ [dk], k ∈ [K]. We conclude that Θ ∈ Psgn(2), because the sign tensor sgn(Θ− π) with an arbitrary π ∈ (0, log 2) is a block tensor with at most two blocks (see Figure 2c). Similar results extend to structured tensors with entries Θ(i1, . . . , iK) = g(maxk x (k) ik
), where g(·) is a polynomial of degree r. In this case, Θ is a high-rank tensor with at most dmax distinct entries but we have Θ ∈Psgn(2r) (see proofs in Appendix B.2). These structured tensors are related to hypergraphons [45, 33]. We discuss the connection in Appendix B.2.

heading: 3.2 Statistical characterization of sign tensors via weighted classification
text: We now provide the explicit form of the weighted loss introduced in (3), and show that sign tensors are characterized by weighted classification. The results bridge the algebraic and statistical properties of sign representable tensors.
For a given π ∈ [−1, 1], define a π-shifted data tensor ȲΩ with entries Ȳ(ω) = (Y(ω) − π) for ω ∈ Ω. We propose a weighted classification objective function
L(Z, ȲΩ) = 1 |Ω| ∑ ω∈Ω |Ȳ(ω)|︸ ︷︷ ︸ weight × |sgnZ(ω)− sgnȲ(ω)|︸ ︷︷ ︸ classification loss , (4)
where Z ∈ Rd1×···×dK is the decision variable to be optimized, |Ȳ(ω)| is the entry-specific weight equal to the distance from the tensor entry to the target level π. The entry-specific weights incorporate the magnitude information into classification, where entries far away from the target level are penalized more heavily in the objective. In the special case of binary tensor Y ∈ {−1, 1}d1×···×dK and target level π = 0, the loss (4) reduces to usual classification loss.
Our proposed weighted classification function (4) is important for characterizing sgn(Θ− π). Define the weighted classification risk Risk(Z) = EYΩL(Z, ȲΩ), (5) where the expectation is taken with respect to YΩ under model (2) and the sampling distribution ω ∼ Π. The form of Risk(·) implicitly depends on π; we suppress π when no confusion arises. Proposition 2 (Global optimum of weighted risk). Suppose the data YΩ is generated from model (2) with Θ ∈Psgn(r). Then, for all Θ̄ that are sign equivalent to sgn(Θ− π),
Risk(Θ̄) = inf{Risk(Z) : Z ∈ Rd1×···×dK} = inf{Risk(Z) : rank(Z) ≤ r}.
The results show that the sign tensor sgn(Θ− π) optimizes the weighted classification risk. This fact suggests a practical procedure to estimate sgn(Θ−π) via empirical risk optimization of L(Z, ȲΩ). In order to establish the recovery guarantee, we shall address the uniqueness (up to sign equivalence) for the optimizer of Risk(·). The local behavior of Θ around π plays a key role in the accuracy.
Some additional notation is needed for stating the results in full generality. Let dtotal = ∏K k=1 dk denote the total number of tensor entries, and ∆s = 1/dtotal a small tolerance. We quantify the
distribution of tensor entries Θ(ω) using a pseudo density, i.e., histogram with bin width 2∆s. Let G(π) := Pω∼Π[Θ(ω) ≤ π] denote the cumulative distribution function (CDF) of Θ(ω) under ω ∼ Π. We partition [−1, 1] = N c ∪N , such that the pseudo density based on 2∆-bin is uniformly bounded over N c; i.e,
N c = { π ∈ [−1, 1] : G(π + ∆s)−G(π −∆s)
∆s ≤ C
} , for some universal constant C > 0,
and N otherwise. Informally, the set N collects the jump points for which the pseudo density is unbounded. Both Θ and its induced CDF G implicitly depend on the tensor dimension. Assumption 1 (α-smoothness). Fix π ∈ N c. Assume there exist constants α = α(π) > 0, c = c(π) > 0, independent of tensor dimension, such that,
sup ∆s≤t<ρ(π,N ) G(π + t)−G(π − t) tα ≤ c, (6)
where ρ(π,N ) := minπ′∈N |π − π′|+ ∆s denotes the adjusted distance from π to the nearest point in N . We make the convention that ρ(π,N ) = ∞ when N = ∅. The largest possible α = α(π) in (6) is called the smoothness index at level π. We define that α = ∞ if the numerator in (6) is zero. A tensor Θ is called α-globally smooth, if (6) holds with global constants α > 0, c > 0 for all π ∈ N c. A similar notion of α-smoothness was previously developed in different contexts of nonparametric function estimation; see Figures 3 in Lee et al [30] for an illustration.
The smoothness index α quantifies the intrinsic hardness of recovering sgn(Θ − π) from Risk(·). The value of α depends on both the sampling distribution ω ∼ Π and the behavior of Θ(ω). The recovery is easier at levels where points are less concentrated around π with a large value of α > 1, or equivalently, when G(π) remains almost flat around π. A small value of α < 1 indicates the nonexistent (infinite) density at level π, or equivalently, when the G(π) jumps by greater than the tolerance ∆s at π. Table 2 illustrates the G(π) for various models of Θ (see Section 5).
We now reach the main theorem in this section. For two tensors Θ1,Θ2, define the mean absolute error (MAE) as MAE(Θ1,Θ2) = Eω∼Π|Θ1(ω)−Θ2(ω)|. Theorem 1 (Identifiability). Assume Θ ∈Psgn(r) is α-globally smooth. Then, for all π ∈ N c and tensors Θ̄ ' sgn(Θ− π), we have
MAE(sgnZ, sgnΘ̄) . C(π) [ Risk(Z)− Risk(Θ̄) ]α/(α+1) + ∆s, for all Z ∈ Rd1×···×dK ,
where C(π) > 0 is independent of Z . The result establishes the recovery stability of sign tensors sgn(Θ − π) using optimization with population risk (5). The bound immediately shows the uniqueness of the optimizer for Risk(·) up to a ∆s-measure set under Π. We find that a higher value of α implies more stable recovery, as intuition would suggest. Similar results hold for optimization with sample risk (4) (see Section 4).
We conclude this section by applying Assumption 1 to the examples described in Section 3.1. For simplicity, suppose Π is the uniform sampling. The tensor block model is∞-globally smooth. This is because the setN consists of finite 2∆s-bin’s covering the distinct block means in Θ. Furthermore, we have α =∞ for all π ∈ N c, since the numerator in (6) is zero. Similarly, the high-rank (d, d, d)dimensional tensor Θ(i, j, k) = log(1+ 1d max(i, j, k)) is∞-globally smooth because α =∞ for all π except those inN , whereN collects dmany 2∆s-bin’s covering log(1+ i/d) for all i ∈ [d].

heading: 4 Nonparametric tensor completion via sign series
text: In previous sections we have established the sign series representation and its relationship to classification. In this section, we present our learning reduction proposal in details (Figure 2). We provide the estimation error bound and address the empirical implementation of the method.

heading: 4.1 Statistical error and sample complexity
text: Given a noisy incomplete tensor observation YΩ from model (2), we cast the problem of estimating Θ into a series of weighted classifications. Specifically, we propose the signal tensor estimate using
averaged structured sign tensors
Θ̂ = 1
2H + 1 ∑ π∈H sgnẐπ, with Ẑπ = arg min Z : rankZ≤r L(Z,YΩ − π), (7)
where H = {−1, . . . ,−1/H, 0, 1/H, . . . , 1} is the series of levels to aggregate, L(·, ·) denotes the weighted classification objective defined in (4), and the rank constraint on Z follows from Proposition 2. For the theory, we assume the true r is known; in practice, r could be chosen in a data adaptive fashion via cross-validation or elbow method [21].
The next theorem establishes the statistical convergence for the sign tensor estimate (7). Theorem 2 (Sign tensor estimation). Suppose Θ ∈Psgn(r) and Θ(ω) is α-globally smooth under ω ∼ Π. Let Ẑπ be the estimate in (7), d = maxk∈[K] dk, and td = dr log |Ω||Ω| . 1. Then, for all π ∈ N c, with very high probability over YΩ,
MAE(sgnẐπ, sgn(Θ− π)) . tα/(α+2)d + 1
ρ2(π,N ) td. (8)
Theorem 2 provides the error bound for the sign tensor estimation. Compared to the population results in Theorem 1, we explicitly reveal the dependence of accuracy on the sample complexity and the level π. The result demonstrates the polynomial decay of sign errors with |Ω|. Our sign estimate achieves consistent recovery using as few as Õ(dr) noisy entries. Recall that N collects the levels for which the sign tensor is possibly nonrecoverable. Let |N | be the covering number of N with 2∆s-bin’s, i.e, |N | = dLeb(N )/2∆se, where Leb(·) is the Lebesgue measure and d·e is the ceiling function. Combining the sign representability of the signal tensor and the sign estimation accuracy, we obtain our main results on nonparametric tensor estimation.
Theorem 3 (Tensor estimation error). Consider the same conditions of Theorem 2. Let Θ̂ be the estimate in (7). For any resolution parameter H ∈ N+, with very high probability over YΩ,
MAE(Θ̂,Θ) . (td logH) α α+2 + 1 + |N | H + tdH logH. (9)
In particular, setting H = (1 + |N |)1/2t−1/2d poly(d) yields the tightest upper bound in (9).
Theorem 3 demonstrates the convergence rate of our tensor estimation. The bound (9) reveals three sources of errors: the estimation error for sign tensors, the bias from sign series representations, and the variance thereof. The resolution parameter H controls the bias-variance tradeoff. We remark that the signal estimation error (9) is generally no better than the corresponding sign error (8). This is to be expected, since magnitude estimation is a harder problem than sign estimation.
In the special case of full observation with equal dimension d1 = · · · = dK = d and bounded |N | ≤ C, our signal estimate achieves convergence
MAE(Θ̂,Θ) . rd−(K−1) min( α α+2 , 1 2 ) log2 d,
by setting H d(K−1)/2. Compared to earlier methods, our estimation accuracy applies to both low- and high-rank signal tensors. The rate depends on the sign complexity Θ ∈Psgn(r), and this r is often much smaller than the usual tensor rank (see Section 3.1). Our result also reveals that the convergence becomes favorable as the order of data tensor increases.
We apply our general theorem to the main examples in Section 3.1, and we compare the results with existing literature (Table 1). The numerical comparison is provided in Section 5. Example 2 (TBMs). Consider a tensor block model with r multiway blocks. Our result implies a rate Õ(d−(K−1)/2) by taking α = ∞ and |N | ≤ rK . O(1). This rate agrees with the previous root-mean-square error (RMSE) for block tensor estimation [40]. Example 3 (GLMs). Consider a GLM tensor Θ = g(Z), where g is a known link function and Z is a latent low-rank tensor. Suppose the CDF of Θ(ω) is uniformly bounded as d→∞. Applying our results with α = 1 and finite |N | yields Õ(d−(K−1)/3). This rate is slightly slower than the parametric RMSE rate [43, 39, 27], as expected. The reason is that our estimate remains valid for unknown g and general high-rank tensors. The nonparametric rate is the price one has to pay for not knowing the form Θ = g(Z) as a priori.
Example 4 (SIMs). The earlier example has shown the nonparametric rate Õ(d−(K−1)/3) when applying our method to single index tensor model. In the matrix case with K = 2, our theorem yields error rate Õ(d−1/3). Our result is consistent with the rate obtained by Xu [41] and is faster than the rate O(d−1/4) obtained by Ganti et al [15]. Example 5 (Structured tensors with repeating entries). We consider a more general model than that in Section 1. Consider an r-sign representable tensor Θ ∈ Psgn(r) with at most d distinct entries with repetition pattern. Applying our results with α =∞ and |N | = d yields the rate Õ(d−(K−2)/2). The following corollary reveal the sample complexity for nonparamtric tensor completion. Corollary 1 (Sample complexity for nonparametric completion). Assume the same conditions of Theorem 3 and bounded |N |. Then, with high probability over YΩ,
MAE(Θ̂,Θ)→ 0, as |Ω| dr log2 |Ω| → ∞.
Our result improves earlier work [42, 18, 31] by allowing both low- and high-rank signals. Interestingly, the sample requirements depend only on the sign complexity dr but not the nonparametric complexity α. Note that Õ(dr) roughly matches the degree of freedom of sign tensors, suggesting the optimality of our sample requirements.

heading: 4.2 Implementation via learning reduction
text: This section addresses the practical implementation of our estimation (7). We take a learning reduction approach by dividing the full procedure into a meta algorithm and 2H + 1 base algorithms. The meta algorithm takes the average of (2H + 1) poly(d) sign tensors, whereas each base algorithm estimates the tensor sgn(Θ−π) given binary input sgn(Y−π) and a target rank r. The full procedure is described in Algorithm 1 and Figure 2.
Algorithm 1 Nonparametric tensor completion via learning reduction Input: Noisy and incomplete data tensor YΩ, rank r, resolution parameter H , ridge penalty λ.
1: for π ∈ H = {−1, . . . ,− 1H , 0, 1 H , . . . , 1} do 2: Define π-shifted tensor Ȳ = Y − π and corresponding sign tensor sgn(Ȳ) = sgn(Y − π). 3: Perform 1-bit tensor estimation algorithm [17, 39, 25, 2] on ȲΩ and obtain Ẑπ ←
arg minlow-rank Z ∑ ω∈Ω |Ȳ(ω)|F (Z(ω)sgnȲ(ω)) +λ‖Z‖2F where F (·) is the large-margin loss.
4: end for Output: Estimated signal tensor Θ̂F = 12H+1 ∑ π∈H sgn(Ẑπ).
The base algorithm reduces to a low-rank 1-bit tensor estimation problem. Following the common practice in classification [6], we replace the 0-1 loss `(z, y) = |sgnz − sgny| in (4) with a continuous large-margin loss F (m) where m = zsgn(y) is the margin. Examples of large-margin loss are hinge loss F (m) = (1−m)+, logistic loss F (m) = log(1+e−m), and ψ-loss F (m) = 2 min(1, (1−m)+) with m+ = max(m, 0). A number of polynomial-time algorithms with convergence guarantees are readily available for this problem [17, 39, 25, 2]. We implement hinge loss [2, 16, 22] which maintains desirable statistical properties as in 0-1 loss, because of the linear excess risk bound [37]
Risk(Z)− Risk(Θ− π) ≤ C[RiskF (Z)− RiskF (Θ− π)], for all π ∈ [−1, 1] and all tensor Z.
Here RiskF (·) is defined similarly as in (5) with hinge loss in place of 0-1 loss. The resulting estimate enjoys both statistical and computational efficiency under mild conditions.
Theorem 4 (Large-margin loss). Let Θ̂F be the output from Algorithm 1 with F being the hinge loss. Under the set-up of Theorem 2 and technical assumptions on base algorithms, Θ̂F has the same error bound as in (9). Furthermore, the total complexity is within a poly(d) factor of base algorithms.
The full statement of Theorem 4 can be found in Appendix A.5. Technical assumptions in the theorem depend on the chosen base algorithm. For example, a signal-to-noise ratio for base problem is needed for the polynomial complexity of algorithms [39, 20]. We remark that we did not attempt to propose a new tensor algorithm. Instead, we present a learning reduction by adopting existing algorithms for a more challenging high-rank problems almost for free, i.e., at only an extra poly(d) computational cost, but at almost no extra statistical cost. The developed sign-representable tensor model unifies low-rank and high-rank tensors, thereby empowering exiting algorithms for broader implications.
In principle, uses can choose their own favorite large-margin losses, as long as the base algorithms are sample efficient. The comparison between various large-margin losses has been studied before [6]. Note that, instead of using Ẑπ as in existing 1-bit tensor algorithms [17, 39], we use sgn(Ẑπ) for more challenging nonparametric estimation. The sign aggregation brings the benefits of flexibility and accuracy over classical low-rank models.

heading: 5 Numerical experiments
text: Finite-sample accuracy. We compare our nonparametric tensor method (NonparaT) with two alternative approaches: low-rank tensor CP decomposition (CPT), and the matrix version of our method applied to tensor unfolding (NonparaM). The performance is assessed under both complete and incomplete observations. We generate signal tensors based on four models summarized in Table 2, including block tensors, transformed low rank tensors, and structured tensors with repeating entries. We consider order-3 tensors of equal dimension, and set d ∈ {15, 20, . . . , 55, 60}, r ∈ {2, 3, . . . , 10}, H = 10+(d− 15)/5 in Algorithm 1. All summary statistics are averaged across 30 replicates.
Figure 3a-b compares the estimation error under full observation. For space consideration, only results for models 2-3 are presented in the main paper, and the rest in the Appendix C.1. We find that MAE decreases with tensor dimension for all three methods. Our method NonparaT achieves the best performance in all scenarios, whereas the second best method is CPT for model 2, and NonparaM for model 3. The model 2 has controlled multilinear rank along mode 3, which makes tensor methods NonparaT and CPT more accurate than NonparaM. The model 3 fits poorly into low-rank tensor families, and therefore, the two nonparametric methods NonparaT and NonparaM exhibit the greater advantage. Figure 3c-d shows the completion error against observation fraction. We fix d = 40 and gradually increase the observation fraction |Ω|/d3 from 0.3 to 1. Again, we find that NonparaT achieves the lowest error. The simulation covers a wide range of complexities, and our method shows good performance in experiments.
Data applications. We apply our method to two tensor datasets, the MRN-114 human brain connectivity data [38], and NIPS data [19]. The brain dataset records the structural connectivity among 68 brain regions for 114 individuals along with their Intelligence Quotient (IQ) scores. We organize the connectivity data into an order-3 tensor, where entries encode the presence or absence of fiber connections between brain regions across individuals. The NIPS dataset consists of word occurrence counts in papers published from 1987 to 2003. We focus on the top 100 authors, 200 most frequent words, and normalize each word count by log transformation with pseudo-count 1. The resulting dataset is an order-3 tensor with entry representing the log counts of words by authors across years.
Table 3 compares the prediction accuracy of different methods. Reported MAEs are averaged over five runs of cross-validation, with 20% entries for testing and 80% for training. Our method substantially outperforms the low-rank CP method for every configuration under consideration. Further increment of rank appears to have little effect on the performance, and we find that increased missingness gives more advantages to our method (see details in Appendix B.2). The comparison highlights the advantage of our method in achieving accuracy while maintaining low complexity.
Figure 4a shows the top 10 brain edges based on regression analysis of denoised tensor from NonparaT against normalized IQ scores. We find that the top connections are mostly inter-hemisphere edges, consistent with recent research on brain connectivity [32, 38]. Figure 4b illustrates the results from NIPS data, where we plot the entries in Θ̂ corresponding to top authors and most-frequent words (after excluding generic words such as figure, results, etc). The identified pattern agrees with active topics in the NIPS publication. Among the top words are neural (marginal mean = 1.95), learning (1.48), and network (1.21), whereas top authors are T. Sejnowski (1.18), B. Scholkopf (1.17), M. Jordan (1.11), and G. Hinton (1.06). We also find strong heterogeneity among word occurrences across authors and years. For example, training and algorithm are popular words for B. Scholkopf and A. Smola in 1998-1999, whereas model occurs more often in M. Jordan and in 1996. The detected patterns and achieved accuracy demonstrate the applicability of our method.

heading: 6 Conclusion
text: We have developed a tensor estimation method that addresses both low- and high-rankness based on sign series representation. Our work provides a nonparametric framework for tensor estimation, and we establish accuracy guarantees for recovering a wide range of structured tensors. Our proposed learning reduction strategy empowers existing algorithms for broader implication, thereby connecting the low-rank (parametric) tensors and high-rank (nonparametric) tensors. We hope the work opens up new inquiry that allows more researchers to contribute to this field.

heading: Acknowledgements
text: This research is supported in part by NSF grant DMS- 1915978, NSF DMS-2023239, and Wisconsin Alumni Research Foundation.

Review summaries:
The paper considers estimating a signal tensor from noisy and incomplete measurements. A new models is proposed based on sign-ranks of tensors. Statistical estimation rates are provided (which pretty much follows standard template). Algorithms and extensive numerical results are provided selling the proposed model.   

This work studies the problem of tensor estimation from noisy observations with possibly missing entries. A nonparametric approach to sign tensor completion is developed. which can deal with both low-rank and high-rank tensor decomposition. Theoretical analysis is provided in terms of risk bound, estimation error, and sample complexity.