Beyond the Signs: Nonparametric Tensor Completion via Sign Series
Authors: Chanwoo Lee
Miaoyan Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Tensor completion
high dimension
nonparametric learning
classification.

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 low- and 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. 

Beyond the Signs: Nonparametric Tensor Completion via Sign Series
Chanwoo Lee Department of Statistics University of Wisconsin-Madise chanwoo lee@wisc. edu
Miaoyan Wang Department of Statistics University Wisconsin-Madison miaoyan. wang@wisc. edu
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 new model which we coin as sign representable tensors. The model represents the signal tensor of interest using series of structured sign tensors. Unlike earlier methods, the sign series representation effectively addresses both low- and high-rank signals, while encompassing many existing tensor models- including CP models, Tucker models, single index models, structured tensors with repeating entries special cases. We provably reduce the tensor estimation problem to a series structured classification tasks, and we develop learning reduction machinery empower existing low-rank tensor algorithms for more challenging high-rank estimation. Excess risk bounds, estimation errors, and sample complexities established. We demonstrate the outperformance of our approach over previous methods on two datasets, one on human brain connectivity networks and the other topic data mining.
Introduction
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 multiway data. this paper we consider the signal plus noise model,
θ E
where )' Rdd xxx is order-K data tensor, θ is an unknown signal tensor of interest, and & is a noise tensor. Our goal is to accurately estimate @ from the incomplete, noisy observation V In particular, we focus on the following two problems:
QI [Nonparametric tensor estimation]. How to flexibly estimate under a wide range 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 t
Inadequacies of low-rank models. The signal plus noise model 22 is popular in tensor literature. Existing methods estimate the signal tensor based on low-rankness of + 28 Common low-rank models include Canonical Polyadic (CP) tensors (24] Tucker tensors 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.
and block tensors [40].
The first example reveals the sensitivity of tensor rank to onder-preserving transformations. Let E 30x33000 be an order-3 tensor with tensor rank Z) (formal definition is deferred to the end of this section). Suppose monotonic transformation fz) (1 + (xp((ce)))- is applied to Z
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

entrywise, and we let the signal θ in model 1 be the tensor after transformation, Figure a plots the numerical rank (see Appendix B.I) of θ versus c. As we see, the rank increases rapidly with 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 low- rank 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.
sngllar value on log scale
numertaa rank:
80
6-
100
P80
constormation level (C)
Index
Figure 1: (a) Numerical tensor rank of θ vs. transformation level c in the first example. (b) Top = 30 tensor singular values in the second example.
The second example demonstrates the inadequacy of classical low rankness in representing special structures. Here we consider the signal tensor of the form θ log + Z). where Z E Rd is an order-3 tensor with entries Zii.j. k) = d max(i. k) for i. j. k E {l..... d). The matrix analogy of ④ was studied in graphon analysis (8) In this case neither O nor 2 is low-rank; in fact, the rank is no smaller than the dimension d as illustrated in Figure Tb. 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 new model called sign representable tensors to address the aforementioned challenges. Figure illustratss our main idea. Our approach 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 B 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-ting algorithms are readily available under moderate-to- high signal-to- -onii-to-noise ratio for 1-bit tensor estimation 39 20 17]. These algorithms enjoy computa- tional 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 series of binary tensor problems with carefully-desinnee weights. This reduction provides a generic engine to empower existing algorithms for wider range of structured tensor problems. We use a divide- and-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 X nonlinear models [15), and subspace clustering 35 13 In particular, the recent work 330 proposes 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 [.. This is in sharp contrast to matrices (K = 2). We show that, applying matrix methods to higher-order tensors results 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, [I..... n for neset with n E N+ On X b, if lim an/b, bb, S c for some constant > 0, and an x bn if ci < limn--oo 0n/b, S c2 for some constants C12 02 > 0. We use (()) to denote the big-O notation. (-)) the variant hiding logarithmic factors. Let O R xxxxx denote an order-K (d1..... dx) >dimensional tensor, and ( E R denote the tensor entry indexed by [d,] x ... x [dx]. 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 == min; dg + co. The tensor rank [24] is defined
(k) E Ie are vectors for by ran = min(r E N: θ- = Σ a.!) @ ... @ (K) where as
E [K] E [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 2 0 and -1 otherwise. We allow univariate functions, such
as sgn(-) and general f: R + R. to be applicd to tensors in an clement-wis wise manner.
2 Model and proposal overview
Let )/ be an order-K (d1..... dx) dimenssioal tensor generated from the model
y = -
where O E Rdxxxxxxxx is unknown signal tensor, and & is 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(w) may depend on w. For cleaner exposition, assume the noise is bounded and the range of observation is in [-1, 1]: the extension to unbounded observations with sub- uub-Gaussian noise is provided in Appendix B.3] Our observation is an incomplete data tensor from (2). denoted V/, where Ω C [dy] x... x [dx] is the index set of observed entries. We consider general model on 32 that allows both uniform and non-uniform samplings. Specifically, let II = } be an arbitrarily predefined probability distribution over the full index set with Ewejdi x---x x x[dx] Pw 1. We use II denote the sampling rule, meaning w in l are i.i.d. draws with replacement from distribution IT. The goal is to estimate from Yg. Note that O 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 [ the high-rankness in the signal θ makes the estimation challenging. Now let us examine the sign of the r-shifted signal sgn(@ - о) for any given π E [--1, 1]. 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(O σ) = sgn(Z f (T)) The signal tensor in the second example has the same sign pattern rank-2 tensor, since (gn(@@(i,)))) k) -)) = -gnssggnnnnn (max(i. j. k) -d(e" - 1)) (see Example in in Section
The above observation suggests general framework to estimate both low- and high-rank signal tensors. Figure Zilluustrttes the main crux of our method. We propose to estimate the signal tensor θ by taking the average over structured sign tensors
è - 2H
Σ sgn( (2),, where 2, TEH
arg min low rank tensor Z
Weighted-Loss sg(()n (3)
Here (2x) 1-1, - -1/ 1. ..... 1). 1. entry-specific weight to each tensor entry; its specific form will be described in Section 3.2 To obtain
is the sign tensor estimated at a series of π H .-,,...,
and Weighted-Loss(;-) denotes a classification objective function with an
sgn(2,) for given æ. we propose dichotomize the data tensor into sign tensor sgn - R and estimate the de-noised sign by performing weighted classification.
Our approach 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, total of H (oly(d) dichotomized problems suffice to recover under the considered model. The method therefore enjoys both statistical effectiveness and computational efficiency.
3

---

toompers Ciservaiion
vat and FoLt Bar
serie Diwyy temoors ruris
rNc2vvee Hightaa Agras
Figure 2:
Illustration of our method in the context of an order-2 tensor (a.k.a. matrix). (a): a noisy, incomplete tensor input. (b)-(c): estimation of sign tensor series sgn(O л) for (-l..... ......--HHH...
-1/H, 0, I/H..... 1}. (d): recovered signal Ô The depicted signal is full-rank matrix based on Example 5 in Section
Oracle properties of sign representable tensors
This section develops sign representable tensor models for θ in We characterize the algebraic and statistical properties of sign tensor series, which serves the foundation for our method.
3.1 Sign-rank and sign tensor series
Let O be the tensor of interest, and sgn(O) the corresponding sign pattern. The sign patterns induce an equivalence relationship between tensors. Two tensors are called sign equivalent, denoted =, they have the same sign pattern.
Definition (Sign-rank). The sign-rank a tensor E IRd xxx defined by the minimal rank among all tensors that share the same sign pattern O; ie.,
srank(O) min min O' O, O' Rd x.xxx.
This concept important combinatorics 10,, complexity theory [1. and quantum mechanics [2]: extend the notion to continuous-valle valued tensors. Note that the sign-rank concerns only the sign pattern but discards the magnitude information of e. In particular, srank( = srank(sgn@)).
Like most tensor problems 23 determining the sign-rank is NP hard in the worst case [1]. For- tunately, tensors arisen 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) we have srank(O) < rank(g (9))
(b) [Broadness] For every order K 2 2 and dimension d, there exist tensors E R Rdx xd such that rank(O) d but srank(@ T) < 2 for all π E R.
Propositions I demonstrates the strict broadness low sign-rank family over the usual low-rank family. In particular, the sign-rank can be much smaller than the tensor rank, have shown in the two examples of Section [ We provide several additional examples in Appendix B.2 in which the tensor rank grows with dimension d but the sign-rank remains constant. The results highlight the advantages of using sign-rank in the high-dimensional tensor analysis.
We now introduce tensor family, which we coin as "sign representable tensors".
(Sign representable tensors). Fix a level æ E [-1,1], 1]. A tensor θ is called (r: mr)rsssggg representable, if the tensor (o 7) has sign-rank bounded by A tensor θ is called r-sign (globally)
Definition
representable, if θ is (r, π --in representable for all E [-1, 1]. The collection (sgn(e - -T): :
[-1, I]} is called the sign tensor series. We use P sgn (r) {@: maxx=e[-1,1 srank( T) sr to
denote the r-sign representable tensor family.
We next show that the r-sign representable tensor family is general model that incorporates most existing tensor models, including low-rank tensors, single index models, GLM models, and structured tensors with repeating entries.
Example (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.c., ④ E (r 1) (the constant 1 is due to rank O =) < 1).

---

Similar results hold for Tucker low-rank tensors Q E sg + 1). where r [[ with Th being the k-thh mode Tucker rank of O.
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
distinct values, where is the total number of multiway blocks. Our model incorporates TBM because E P (rsg(r)
Example 3 (Generalized linear models (GLMS)). Let J' be binary tensor from a logistic model (39 with mean θ = logit(2), 2), where 2 is latent low-rank tensor. Notice that è itself may be high-rank (see Figure T.). By defimition, θ is a low-rank sign representable tensor. Same conclusion holds for models with a (known) link function [25].
general exponential
Example 4 (Single index models (SIMs)). Single index model a flexible semiparametric model proposed in economics [36] and high-dimensional statistics [5] 14]. The SIM assumes the existence of (unknown) monotonic function g: IR such that g(O) has rank r. We see that é belongs to the sign representable familyy i.e., θ S sgn (r + 1).
Example (Structured tensors with repeating entries). Here we revisit the model introduced in log(1 maxe T. (!!)) where it are given numbers in [0, 1] for all i E [d&], A: E [K]. We conclude that O E 3 sgu (2), (0, log 2) is block tensor with at most two blocks (see Figure 2p). Similar results extend to structured tensors with entries ((,,...... ix) =
Figure b of Section Let θ be an order-K tensor with entries Oii
(k)
because the sign tensor sgn(@ x) with an arbitrary
gmmax, [ where g(-) is polynomial of degree In this case, θ is high-rank tensor with at most dmax distinct entries but we have θ E 3 sgn (2r) (see proofs in Appendix B.2). These structured
tensors are related to hypergraphons
We discuss the connection in Appendix B.2
3.2 Statistical characterization of sign tensors via weighted classification
We now provide the explicit form of the weighted loss introduced in (3) and show that sign tensors characterized by weighted classification. The results bridge the algebraic and statistical properties of sign representable tensors.
1]. define r-shifted data tensor Do with entries M(w (D(w) - T) for w E Q. We propose a weighted classification objective function
For given E [-1,
L(2,Do) = |&]
Σ WE
[w)]] x Isgn (w))
(4)
weight
classification loss
where Z Ru xdxxxxxxxx is the decision variable to be optimized, [[w)] is the entry- speccfip 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
penalized more heavily in the objective. In the special case of binary tensor y E E {-1,1] 1), xxxxxx and target level π O, the loss (4) reduces usual classification loss.
Our proposed weighted classification function (4) is important for characterizing sgn(O - T). Define the weighted classification risk
Risk (3) = Ey,, L(Z,
(5)
where the expectation is taken with respect to Vn under model (2) and the sampling distribution
w ~ II. The form of Risk(-) implicitly depends on n, we suppress v when no confusion arises.
Proposition 2 (Global optimum weighted risk). Suppose the data Yn is generated from model 2 with θ E P (Png(r) (r). Then, for all è that are sign equivalent to sgn(@ ( - IT)
@isk(@) = inf (Risk(Z): Z E IR: xxdxxxxxxx) = inf inf( (Risk()) Z rank () r).
The results show that the sign tensor sgn(O ( T)) optimizes the weighted classification risk. This fact suggests practical procedure to estimate sgn(E) ( T via empirical risk optimization of (.) 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 key role in the accuracy.
Some additional notation is needed for stating the results in full generality. Let dromal = II denote the total number of tensor entries, and As 1/dooal small tolerance. We quantify the
_ de
5

---

distribution of tensor entries (ww) using pseudo density, i.e., histogram with bin width 24s. Let G(a) := Pu (W) π denote the cumulative distribution function (CDF) ((w) under w II.
We partition [-1 1. = N UN,, such that the pseudo density based on 2A-bin is uniformly bounded
over Ne: i.e.
N TE|-1.1] G( As) - G( As)
<c <c]. for some universal constant C 0,
As
and N otherwise. Informally, the set N collects the jump points for which the pseudo density is unbounded. Both e and its induced CDF G implicitly depend on the tensor dimension.
Assumption (a-smoothness). Fix E A Assume there exist constants a(x)) 0, <(π) 0, independent of tensor dimension, such that,
G( + G - -t) SC
sup AeSLC
(6)
to
where p(x,A\= == min |a -'| + As denotes the adjusted distance from iT the nearest point
in .N. We make the convention that ((rr,N) = oo when N = 0. The largest possible = a(x)
in (6) is called the smoothness index at level я. We define that a = oc if the numerator in (6) is zero. A tensor θ is called a-globally smooth, if ( holds with global constants > 0, >> 0 for
all π E N A similar notion of a-smoothness was previously developed different contexts of nonparametric function estimation; see Figures 3 in Lee et al [30] for an illustration.
The smoothness index a quantifies the intrinsic hardness of recovering sgn(O - T) from Risk(-)- The value of a depends on both the sampling distribution ~ II and the behavior of ((w). The recovery easier at levels where points are less concentrated around æ with a large value of a > 1, or equivalently, when G(Tr) remains almost flat around A small value of a < 1 indicates the nonexistent (infinite) density at level π,, or equivalently, when the G(xx) jumps by greater than the tolerance As at Table illustrates the G(xz) for various models of θ (see Section
We now reach the main theorem in this section. For two tensors O1, O2. define the mean absolute етгог (MAE) as MAE(O), θ2) = Ew-II ( O2(w).
Theorem (Identifiability). Assume E (rga(r) is a a-globally smooth. Then, for all π E N and tensors sg T., we have
MAE(sgnZ,sgne) sgn@) x ((*) Risk(2) - Risk(E) a/(a+1) + Ass for all Z Rd aodxx-a xxxxxx
where C(xx)= > 0 is independent Z.
The result establishes the recovery stability of sign tensors sgn(O- T) using optimization with population risk (5). The bound immediately shows the uniqueness of the optimizer for Risk(-) up to As-measure set under II. We find that higher value of implies more stable recovery, intuition would suggest. Similar results hold for optimization with sample risk (4) (see Section 4
We conclude this section by applying Assumption I to the examples described in Section 3.1 For simplicity, suppose II is the uniform sampling. The tensor block model is o-globally smooth. This is because the set consists of finite 2in-bin's covering the distinct block means in é. Furthermore, N since the numerator (6) is zero. Similarly, the high-rank (d, d, d)- co for all ı except those in N, where A collects many 2As-bin's 's covering log(1 + ifdd) for all E [d].
we have a = oo for all dimensional tensor (i,, j. k) log(1 + max(i, j. k)) is oc-globally smooth because
Nonparametrie tensor completion via sign series
In previous sections we have established the sign series representation and its relationship to classifi- cation. 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.
4.1 Statistical error and sample complexity
Given a noisy incomplete tensor observation Yn from model (2). we cast the problem of estimating @ into series of weighted classifications. Specifically, propose the signal tensor estimate using

---

averaged structured sign tensors
Σ sgn with 2. = arg min 112332 T)
2H
2: rank
REH
where H. = - H O, 1/1,,........................ 1 is the series of levels to aggregate, L(-.)) denotes the weighted classification objective defined in ( and the rank constraint on Z follows from Proposition 2 adaptive fashion via gross-validatte
For the theory. we assume the true is known; in practice, 7 could be chosen in data
elbow method [2T].
The next theorem establishes the statistical convergence for the sign tensor estimate
Theorem (Sign tensor estimation). Suppose O E sg)(() and (w)) is a-globally smooth under
II. Let nn be the estimate in 7 d = max des and ta dr [0] E NV with very high probability over J/2,
S 1. Then, for all
R
MAE (AggSsn22n. sgn(@ n)) S to
aa((+22)
NT ta
Theorem 2 provides the error bound for the sign tensor estimation. Compared to the population results in Theorem [ we explicitly reveal the dependence of accuracy on the sample complexity and the level The result demonstrates the polynomial decay of sign errors with [St]. Our sign estimate achieves consistent recovery using as few as (dr) noisy entries.
Recall that / collects the levels for which the sign tensor is possibly nonrecoverable. Let [ be the covering number of A with 2As-bin's, s, i.e, [ [eb(A))22ss where Leb(-) is the Lebesgue measure and [-] is the ceiling function. Combining the sign representability of the signal tensor and the sign estimation accuracy,
obtain main results nonparametric tensor estimation.
Theorem (Tensor estimation error). Consider the same conditions of Theorem 2 estimate in 7 For any resolution parameter H E N_., with very high probability over Vn-
Let é be the
MAE(ê, θ) & (ta log 2 + 1+ [W]
+ la log H.
In particular, setting = (1 + WW) 12 = poly(d) yields the tightest upper bound 9
Theorem 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) 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 dj [W] < C, our signal estimate achieves convergence
dx and bounded
MAE(ê, +) $ rd- (K-1) minl wtz +) log²
by setting H x 1)/21 Compared to earlier methods, our estimation accuracy applies to both low- and high-rank signal tensors. The rate depends on the sign complexity O E P (r)),, and this is often much smaller than the usual tensor rank (see Section 3.1). Our result also reveals that the convergence becomes favorable the order of data tensor inereases.
We apply our general theorem to the main examples in Section 3.1 and we compare the results with existing literature (Table [ The numerical comparison is provided in Section
Example 2 (TBMs). Consider a tensor block model with r multiway blocks. Our result implies a rate ((d-(K-1)/2) by taking a = oc and | < K S O(1). This rate agrees with the previous boot-mean-square error (RMSE) for block tensor estimation [40]
Example 3 (GLMs). Consider GLM tensor é = g(Z), where g is a known link function and Z latent low-rank tensor. Suppose the CDF of ( uniformly bounded as d co. Applying our results with a 1 and finite W yields Odd-(K-1)/3) This rate slightly slower than the parametric RMSE rate 43 39 27 as expected. The reason is that our estimate remains valid for unknown y and general high-rank tensors. The nonparametric rate is the price one has to pay for not knowing the form θ g(Z) as priori.
7

---

Table 1: Summary of our statistical rates compared to existing works under different models. For notational simplicity, we present eπrоr rates assuming equal tensor dimension in all modes and finite [W] for the smooth tensor model. Here K denotes tensor order and denotes tensor dimension.
Model
W Finite
Our rate (power of
Comparison with previous result Achieves minimax rate (Q). Not available for general K > 3: Improves
Tensor block model
-(K 1]/2
Single index model
0
(K 1)/3
previous rate -/4 for A 15
Generalized lincar model
0
-(K 1)/3
Close to minimax rate 33 39
Structure with repeating entries
d
(K 21//2
Not available.
Smooth tensor
Finite
(K 2) min(....))
Not available.
Example (SIMs). The earlier example has shown the nonparametric rate ((d when applying our method to single index tensor model. In the matrix case with K 2, our theorem yields error rate (d3133) Our result is consistent with the rate obtained by Xu 41 and is faster than the rate O(d-1/4) 1/4) obtained by Ganti et al [15].
Example 5 (Structured tensors with repeating entries). We consider more general model than that in Section Consider an r-sign representable tensor θ E 9 (r) with at most distinct entries with repetition pattern. Applying our results with
and [ d yields the rate Old (K 22/2))
The following corollary reveal the sample complexity for nonparamtric tensor completion. Corollary (Sample complexity for nonparametric completion). Assume the same conditions of Theorem and bounded [V.. Then, with high probability over Va.
[22]
MAE(ê, +) + O, as
000
dr log
Our result improves earlier work 42 18 31 by allowing both low- and high-rank signals. Interest- ingly, the sample requirements depend only the sign complexity dr but the nonparametric complexity Note that (dr)) roughly matches the degree of freedom of sign tensors, suggesting the optimality of our sample requirements.
4.2 Implementation via learning reduction
This section addresses the practical implementation of our estimation 77. We take a learning reduction approach by dividing the full procedure into a meta algorithm and 2H + base algorithms. The meta algorithm takes the average of (2H7 + 1) x poly(d) sign tensors, whereas each base algorithm estimates the tensor sgm ( given binary input sgn (Y- - T) and a target rank r. The full procedure
described in Algorithm and Figure 2
Algorithm Nonparametric tensor completion via learning reduction
Input: Noisy and incomplete data tensor Vn, rank r, resolution parameter H, ridge penalty X. I: for E H. = (-1..... # 0. H . 1} do
2: Define r--siftted tensor ) =
and corresponding sign tensor sgn())) sgn()) T). 3: Perform 1-bit tensor estimation algorithm
[I7 39 25
Da and obtain 2, +
arg mill Z Ewen (Z()))((())) + X Z where F(-) is the large-margin loss.
4: end for
Output: Estimated signal tensor θ 2H41 ΣTEN sgn(2+)
The base algorithm reduces to low-rank 1-bit tensor estimation problem. Following the common practice classification (6]. we replace the 0-1 loss f(2. y) |sgnæ sgny/ in (4) with a continuous large-margin loss ((m) where m =sgn(y) is the margin. Examples of large-margin loss are hinge loss ((m) = (1-m)4, logistic loss F(m) = log(1+e~")) and n-loss F(m) = min (1-m)+) with m = mm. 0). A number of polynomial-time algorithms with convergence guarantees are
readily available for this problem [17 39 2] We implement hinge loss [6] 22) which maintains
desirable statistical properties as in 0-1 loss, because of the linear excess risk bound (37
Risk(Z) Risk(@ x) < C'Riskk(ZZ) Riske(O x)), for all [-1, 1] and all tensor Z.

---

Here (-) 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 (Large-margin loss). Let θ be the output from Algorithm | with F being the hinge loss. Under the set-up of Theorem and technical assumptions on base algorithms, Ô has the same error bound in (9). Furthermore, the total complexity is within poly(d) factor of base algorithms.
The full statement of Theorem can be found Appendix A.. Technical assumptions the theorem depend on the chosen base algorithm. For example, a signal-to-non ratio for base problem is needed for the polynomial complexity of algorithms [39 20]. We remark that we did not attempt to propose new tensor algorithm. Instead, present learning reduction by adopting existing algorithms for more challenging high-rank problems almost for free, i.c., at only an extra poly(d) (d) computational cost, but 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 2, as in existing 1-bit tensor algorithms [17 39]. we use sgn(2,) for more challenging nonparametric estimation. The sign aggregation brings the benefits of flexibility and accuracy over classical low-rank models.
Numerical experiments
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 E (15, 20..... 55, 60). r E {2, (2,),, H 10- (d 15)/5 /5 in Algorithm All summary statistics averaged across 30 replicates.
Table 2: Simulation models used for comparison, Here Ms E f0, 1 1 denotes membership matrix; C 3xx3x3 the block mean tensor; a d (1, d)" is a length-d vector; Ziuax and Zmin are order-3 tensors with entries d-1 max (i, j. k) and d- min(i, k). respectively.
Simmlation
Signal Tensor @
Rank
Siga Rank
a
[
CDF of Tensor Entries
Noise
1
x M, x M, x M,
3
s 33
0c
S 3
Uniform |00.3, 0.3]
2
a 8 0 1 1 (901
d
53
Normal (7 0 0.15)
(0. (0.5 + mmax)
2 d
2
Uniform 00.1, 0.1]
4
2.5 exp( 2,10
2 d
2
Normal (0, 0. 0.15)
Figure 3 b-bb 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..] We find that MAE decreases with tensor dimension for all three methods. Our method NonparaT achieves the best performance 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 NonparaTT and CPT more accurate than NonparaM. The model 3 fits poorly into low-rank tensor families, and therefore, the two nonparametric methods Nonpara'T and NonparaM exhibit the greater advantage. Figure 3 shows the completion error against observation fraction. We fix = 40 and gradually increase the observation fraction [ 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 14 human brain connec- tivity data (38], and NIPS data [1).. The brain dataset records the structural connectivity among 68 brain regions for 14 individuals along with their Intelligence Quotient (IQ) scores. We organize the connectivity data into an order-3 3 tensor, where entries encode the presence or absence of fiber connec- tions 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 The resulting dataset an order-3 tensor with entry representing the log counts of words by authors across years.

---

GPT
NonpanaT (ours)
0065
6180
occe
0015
00N-
Figure 3: Performance comparison between different methods. (a)-(b): Estimation error versus tensor dimension. (c)-(d): Estimation error versus observation fraction. Panels (a) and (c) are for model 2, whereas (b) and (d) are for model 3.
Table 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 (.2). The comparison highlights the advantage our method achieving accuracy while maintaining low complexity.
Table 3: MAE comparison between Non- paraT (H 20) and CPT in the real data analysis. Standard errors are parenthesis.
Lrosbrainieett
crestruimittee
Spenstt Voueer
Spersene
Liapoly
rcluds)
MRN 114 brain
Lprecettral
Form entral
Method
12
Graarscastral
NonparalT (Ours) 0.1 0.14())01)
0.12/0.01) 0.12(0.001)
CPT
0,200008)
0.200.004) 0.100.000)
NBP word cocernnce datnet
Method
Figure 4: (a) top IQ-associated edges in the brain con- nectivity data. (b) top (authors, words, year) triplets the NIPS data.
NomparalT
0.00))))))
0.15(0.01)
0.34(0.031)
CPT
0. 0.300.007) 0.1200.007 0.37(0.007)
Figure f 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 comnectivity [32 38
Figure 4 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 11.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.
6 Conclusion
have developed tensor estimation method that addresses both low- and high-rankness based on sign series representation. Our work provides 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 contribute this field.
Acknowledgements
This research is supported part by NSF grant DMS- 1915978, NSF DMS-202322 2023239, and Wisconsin Alumni Research Foundation.
10

---

References
[1] Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank versus VC dimension, In Conference on Learning Theory, pages 47-80, 2016.
[2] Pierre Alquier, Vincent Cottet, Guillaume Lecué, et al. Estimation bounds and sharp ora- cle inequalities of regularized procedures with lipschitz loss functions. Annals of Statistics, 47(4):2117-2144,2000 2019.
[3] Animashree Anandkumar, Rong Ge. Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15(1):2773-2832, 2014.
[4] Animashree Anandkumar, Rong Ge, and Majid Janzamin. Analyzing tensor power method dynamics in overcomplete regime. Journal of Machine Learning Research, 18(1):752-791, 2017.
[5] Fadoua Balabdaoui, Cécile Durot, and Hanna Jankowski. Least squares estimation in the monotone single index model. Bernoulli, 25(4B):3276-3111 2019.
[6] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-155) 2006.
[7] Changxiao Cai, Gen Li, H Vincent Poor, and Yuxin Chen. Nonconvex low-rank tensor comple- tion from noisy data. In Advances in Neural Information Processing Systems, pages 1863-1874, 2019.
[8] Stanley Chan and Edoardo Airoldi. A consistent histogram estimator for exchangeable graph models. In International Conference on Machine Learning, pages 208-216, 2014.
[9] Eric C Chi, Brian J Gaines, Will Wei Sun, Hua Zhou, and Jian Yang. Provable convex clustering of tensors. Journal of Machine Learning Research, 21(214):1-58, 2020.
[10] Henry Cohn and Christopher Umans. Fast matrix multiplication using coherent configurations. In Proceedings of the twenty-fourth annual ACM-SIAN symposium on Discrete algorithms, pages 1074-1087, 2013.
[11] Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. multilinear singular value decomposition. SIAM Journal on Matrix Analysis and Applications, 21(4):1253-122) 2000.
[12] Ronald De Wolf. Nondeterministic quantum query and communication complexities. SIAM Journal on Computing, 32(3):681-695 2003.
[13] Jicong Fan and Madeleine Udell. Online high rank matrix completion. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 8690-8698, 2019.
[14] Ravi Ganti, Nikhil Rao, Laura Balzano, Rebecca Willett, and Robert Nowak. On learning high dimensional structured single index models. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 1898-1904, 2017.
[15] Ravi Sastry Ganti, Laura Balzano, and Rebecca Willett. Matrix completion under monotonic single index models. In Advances in Neural Information Processing Systems, pages 1873-1881, 2015.
[16] Martin Genzel and Alexander Stollenwerk. Robust 1-bit compressed sensing via hinge loss minimization. Information and Inference: A Journal of the IMA, (2):361-422, 2020.
[17] Navid Ghadermarzy, Yaniv Plan, and Ozgur Yilmaz. Learning tensors from partial binary measurements. IEEE Transactions on Signal Processing, 67(1):29-40 40, 2018.
[18] Navid Ghadermarzy, Yaniv Plan, and Özgür Yilmaz. Near-optimal sample complexity for convex tensor completion. Information and Inference: Journal of the IMA, 8(3):577-619 2019.
11

---

[19] Amir Globerson, Gal Chechik, Fernando Pereira, and Naftali Tishby. Euclidean embedding of co-occurrence data. Journal of Machine Learning Research, 8:2265- 2295, 2007.
[20] Rungang Han, Rebecca Willett, and Anru Zhang. An optimal statistical and computational framework for generalized tensor estimation. arXiv preprint arXiv:2002.11255. 2020.
[21] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science Business Media, 2009.
[22] Lifang He, Chun-Ta Lu, Guixiang Ma, Shen Wang, Linlin Shen, S Yu Philip, and Ann B Ragin. Kernelized support tensor machines. In International Conference on Machine Learning, pages 1442-1451. PMLR, 2017.
[23] Christopher Hillar and Lek-Heng Lim. Most tensor problems are NP-hard. Journal of the ACM (JACM), 60(6):45, 2013.
[24] Frank L Hitchcock. The expression of tensor or a polyadic as a sum of products. Journal of Mathematics and Physics, 6(1-4):164-18)) 1927.
[25] David Hong, Tamara G Kolda, and Jed A Duersch. Generalized canonical polyadic tensor decomposition. SIAM Review,
2020.
[26] Victoria Hore, Ana Viñuela, Alfonso Buil, Julian Knight, Mark I McCarthy, Kerrin Small, and Jonathan Marchini. Tensor decomposition for multiple-tissue gene expression experiments. Nature genetics, 48(9):1094, 2016
[27] Jiaxin Hu, Chanwoo Lee, and Miaoyan Wang. Generalized tensor decomposition with features on multiple modes. Journal of Computational and Graphical Statistics, 0(0):1-15, 2021.
[28] Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data. In Advances in Neural Information Processing Systems, volume 27, pages 1431-1439, 2014.
[29] Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM Review, 51(3):55-5004 2009.
[30] Chanwoo Lee, Lexin Li, Hao Helen Zhang, and Miaoyan Wang. Nonparametric trace regression in high dimensions via sign series representation. arXiv preprint
2021.
[31] Chanwoo Lee and Miaoyan Wang. Tensor denoising and completion based on ordinal observa- tions. In International Conference on Machine Learning, pages 5778-5788 2020.
[32] Yonghui Li, Yong Liu, Jun Li, Wen Qin, Kuncheng Li, Chunshui Yu, and Tianzi Jiang. Brain anatomical network and intelligence. PLoS Comput Biol, 5(5):e100039) 2009.
[33] László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933-99) -977,,977577 2006.
[34] Andrea Montanari and Nike Sun. Spectral algorithms for tensor completion. Communications on Pure and Applied Mathematics, ((11))2331-2425 2018.
[35] Greg Ongie, Rebecca Willett, Robert D. Nowak, and Laura Balzano. Algebraic variety models for high-rank matrix completion. In International Conference on Machine Learning, pages 2691-2700, 2017.
[36] Peter M Robinson. Root-nn-consiteet semiparametric regression. Econometrica: Journal of the Econometric Society, 56(4))931-9544 1988.
[37] Clayton Scott. Surrogate losses and regret bounds for cost-sensitive classification with example- dependent costs. In /CML, 201
[38] Lu Wang, Daniele Durante, Rex E Jung, and David B Dunson. Bayesian network-response regression. Bioinformatics, 13(12):1859-1866 2017.
[39] Miaoyan Wang and Lexin Li. Learning from binary multiway data: Probabilistic tensor decomposition and its statistical optimality. Journal of Machine Learning Research, 21(154):1-
38, 2020.
12

---

[40] Miaoyan Wang and Yuchen Zeng. Multiway clustering via tensor block models. In Advances in Neural Information Processing Systems, pages 713-723, 2019.
[41] Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. International Conference Machine Learning, pages 5433-5442, 2018.
[42] Ming Yuan and Cun-Hui Zhang. On tensor completion via nuclear norm minimization. Founda- tions of Computational Mathematics, 16(4):0031-1068, 2016.
[43] Anru Zhang and Dong Xia. Tensor SVD: Statistical and computational limits. JEEE Transactions on Information Theory, 64(11):7311 7338, 2018.
[44] Yuan Zhang, Elizaveta Levina, and Zhu. Estimating network edge probabilities by neighbour- hood smoothing. Biometrika, 104(4):771-783, 2017.
[45] Yufei Zhao. Hypergraph limits: regularity approach. Random Structures & Algorithms, 27(2):205-226, 2015.
13


Reviews:
[{"review_id": "iz2Cs-mPjvQ", "reviewer": "Reviewer_UX9r", "summary": "This paper presents a nonparametric tensor completion technique that recovers a tensor that is not necessarily low-rank. At each target level to compare the entries to, it finds a low rank tensor that can approximate the sign tensor of difference between the original tensor and the level, and gets an approximation to the original tensor by averaging over multiple levels. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- This paper offers a new and provable perspective for low-rank and high-rank tensor completion, which should be very interesting to the tensor decomposition community.\n\n- The main theorems are presented clearly in general.\n\n- The results seem original.\n\nSome questions:\n\n- When partitioning [-1, 1] as $\\mathcal{N}^c \\cup \\mathcal{N}$, how would $\\rho(\\pi, \\mathcal{N})$ be defined if $\\mathcal{N} = \\emptyset$? That corresponds to the case in which $G(\\pi)$ is flat across [-1, 1], and should be a case in which recovery is the easiest. So, if we define $\\rho(\\pi, \\mathcal{N}) := \\Delta s$ in this case, it is strictly smaller than $\\mathcal{N} \\neq \\emptyset$, and the bound in Line 248 Equation 8 seems to be looser. This aspect does not seem to have been (intuitively) addressed either in the proof in Appendix A.3. Similarly, it might be helpful to show how theorems hold for corner cases. \n\n- What would happen if we set the rank upper bound (which is a hyperparameter in the algorithm) in Line 240 Equation 7 to be either larger or smaller than the true $r$? Is it hard to show such results that the rank upper bound no smaller than $r$ would give a much better performance than smaller?\n\nSome minor questions or suggestions:\n\n- The loss L in Line 183 Equation 4 is simultaneously parameterized by $Z$, $Y$ and $\\pi$. It might be clearer if the parameter $\\pi$ can be added to the equation, to make it more evident that this is with respect to a single target level.\n\n- I would suggest the authors show an illustrative figure of the definition of $G(\\pi)$, $\\mathcal{N}$ and $\\mathcal{N}^c$, as I find it helps to understand the relevant notations that are central to this paper.\n\n- Notation: In Appendix A.2 Equation 5, does $|\\hat{\\Theta}|$ refer to the entrywise norm (based on equations around Line 204 and 207 in the main paper)? It might be better to introduce this notation as well in the section in Line 77.\n\n- This is certainly beyond the scope of this paper, but can we make the difference among target levels in $\\mathcal{H}$ nonuniform? Namely, can we sample target levels more densely in $\\mathcal{N}$ than in $\\mathcal{N}^c$, so that we may get a better recovery with the same number of positive levels $H$?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "fvV8qsG7mLY", "reviewer": "Reviewer_uYrq", "summary": "The authors proposed a decomposition method which represents a tensor as sum of a series of sign tensors, $\\text{sign}(Z)$. Each tensor, $Z$, is estimated by minimizing a weighted classification objective function with the rank constraint, $rank(Z) <= r$, e.g., using 1-bit tensor estimation algorithms.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n- The authors present two examples to demonstrate the motivation of the proposed model. According to the paper, the canonical polyadic tensor decomposition (CPD) fails in finding low-rank approximation of tensors obtained from low-rank tensors after nonlinear transforms.\n\nFirst the nonlinear transforms do not preserve the low-rank structure of the original tensor, hence it is natural that the generated tensor can have higher rank. The data simply does not admit the CP model. \n\nSecond, even the transformed data can have higher rank than that of the original data, the numerical ranks at the relative approximation error of 0.1, shown in Figure 1, are not optimal, too high, perhaps due to incorrect decomposition. The authors do not explain the algorithm for CPD and its implementation used in their experiments.\n\nFor example the authors generated tensors of size $30 \\times 30 \\times 30$ $Z = {\\bf a}^{\\otimes3} + {\\bf b}^{\\otimes3} + {\\bf c}^{\\otimes3}$ where ${\\bf a}$, ${\\bf b}$, ${\\bf c}$ consist of $N(0,1)$ entries. \nThe transformed tensor $\\Theta = f(Z)$ can be approximated by a CP model with a rank of 60 with a relative approximation error smaller than $\\frac{\\|\\Theta - \\hat{\\Theta}\\|_F}{\\|\\Theta\\|_F}<0.1$ for the case $c = 200$. This numerical rank is much smaller than the rank of 150 that the authors show in Figure 1.a.\n\nFor c = 50, the tensor $\\Theta$ can have a numerical rank of 47, which is much smaller than the rank of 130 determined by the authors.\n\nThis is to show that the authors do not achieve the best results for CPD. The results for two examples in Section 5 may face the same problem, and the conclusions are not very accurate or bias.\n\n\n- The proposed method approximates the tensor by a sum of $H = 20$ (or even more) low-rank tensors. Each estimated tensor can be low rank but not the mean tensor of low-rank tensors.\n\nFor a fair comparison, the authors should do the CPD completion method similarly, the final result should be mean of low-rank tensor approximated by CPD. \n\nIn summary, the obtained results using CPD are not optimal as shown above for Example1, and \nand should be estimated as mean of multiple CP models.\n\nOther comments\n\nCPD (not CPT) is used for abbreviation of Canonical polyadic decomposition.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main concern is Comparison. \nThe proposed method may be promising but comparison is not good.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "dJA10QyEJP3", "reviewer": "Reviewer_UqMu", "summary": "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.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The sign tensor decomposition problem is important, and the paper is clearly written However, the major concern lies in the lack in numerical tests. \n\nThe experiments were only done to compare with the basic low-rank tensor CP decomposition (CPT), and the matrix version of the proposed method was applied to tensor unfolding (NonparaM). The reviewer finds this inadequate and cannot support the effectiveness of the proposed algorithm. As CPT is a basic tensor decomposition algorithm that is for low-rand tensor decomposition, and the tensor-version outperforms the matrix version of the proposed model is also obvious. In order to improve the significance and novelty of the manuscript, more comparisons with state-of-art sign-tensor decomposition methods should be provided.\n\nMore discussion about the disadvantage and advantage of the theoretical analysis with respect to existing works on sign tensor decomposition is also required.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3cDnykTlGY", "reviewer": "Reviewer_cuu7", "summary": "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. \n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1) I am not sure if the results in figure 1(a) provide sufficient motivation. It is folklore results in tensor community that CP ranks are unstable in various sense and Tucker ranks provide a more stable notion of rank for higher-order tensors. Is there any reason why CP rank is used for motivation (not in the form of citation to prior works) ? Can the authors provide a plot of c versus Tucker rank in this experimental setup ?  More importantly, even for the provided result, there is a big discrepancy between the actual CP rank and the numerical computation due to the computational complexity results. \n\n2) The second example provided in lines 41-45 is closely related to hypergraphons (https://arxiv.org/pdf/1302.1634.pdf). This should be discussed carefully. \n\n3) The statement in line 63-64 is not clear and perhaps hiding a lot of things. For example, in the example considered in [20, Theorem 4.1], they require the condition on the signal-to-noise ratio (i.e., the term \\bar{\\lambda}/\\sigma) to obtain the initializer. Only in this high signal-to-noise ratio regime, polynomial time algorithms exists. Similarly, in [36, page 15], it is not at all clear what the order T_0 is. It is well know that most tensor problems have a statistics-computation gap and proving no algorithms exists in this gap regime is (one of the) most interesting problem with tensor estimation/learning.\n\n4) Regarding Theorem 4, how is (27) solved ? From the way the results are presented, it is not clear what the signal-to-noise ratio of the problem is. \n\n5) Given all the above issues (unclear parts, at least to this reviewer) the paper looks like it is proposing yet another model for tensor problems. Agreed, some models might be useful to some (practical) problems and I do see some merits in the proposed model for some applications. Hence, I am on the fence with respect to this paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none (to my knowledge)", "review_text": "", "extra_scores": {"ethical_concerns": "none (to my knowledge) ", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "10 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an interesting and innovative new notion of tensor rank
that can model high rank tensors with low complexity, 
and show how to use this idea to solve tensor completion problems.
While the reviewers differ in their beliefs about the impact this method will have,
none dispute that the paper is clear, interesting, correct, and even (mostly) complete,
after the new experiments the authors added in the discussion.
This paper is a novel and solid contribution that deserves to be published.
Decision: Accept (Poster)