Nonnegative Tensor Completion via Integer Optimization
Authors: Caleb Xavier Bugg
Chen Chen
Anil Aswani
Venue: NeurIPS 2022 Accept (2022)
Keywords: tensor completion
machine learning

Abstract: Unlike matrix completion, tensor completion does not have an algorithm that is known to achieve the information-theoretic sample complexity rate. This paper develops a new algorithm for the special case of completion for nonnegative tensors. We prove that our algorithm converges in a linear (in numerical tolerance) number of oracle steps, while achieving the information-theoretic rate. Our approach is to define a new norm for nonnegative tensors using the gauge of a particular 0-1 polytope; integer linear programming can, in turn, be used to solve linear separation problems over this polytope. We combine this insight with a variant of the Frank-Wolfe algorithm to construct our numerical algorithm, and we demonstrate its effectiveness and scalability through computational experiments using a laptop on tensors with up to one-hundred million entries.

Nonnegative Tensor Completion via Integer Optimization
Caleb Xavier Buggi
Chen Chen
Anil Aswanit
University of California, Berkeley, {caleb_ _ugg_,_uugg__ee aaswani aaswani)@berkeeeeeeea Joberkeley.eddee 'hee Ohio State University, chen. 80188osu edu
Abstract
Unlike matrix completion, tensor completion does not have an algorithm that is known to achieve the information-theoreti sample complexity rate. This paper develops new algorithm for the special case completion for nonnegative tensors. We prove that algorithm converges in linear (in numerical tolerance) number oracle steps, while achieving the information-theored define a new norm for nonnegative tensors using the gauge of particular 0-1 polytope; integer linear programming can, in turn, be used to solve linear separation problems over this polytope. We combine this insight with variant of the Frank- Wolfe algorithm to construct our numerical algorithm, and we demonstrate its effectiivneess and scalability through computational experiments using laptop on tensors with up to one-hundred million entries.
rate. Our approach is
Introduction
Tensors generalize matrices. tensor of order p is 1p E T="xx"",,,, where r; is the dimension of the tensor in the i-th index, for .. Though related, many problems that are polynomial-tine solvable for matrices are NP-hard for tensors. For instance, it NP-hard to compute the rank of tensor (Hillar and Lim 2013). Tensor versions of the spectral norm, nuclear norm, and singular value decomposition are also NP-hard to compute (Hillar and Lim 2013 Friedland and Lim 2014).
1.1 Past Approaches to Tensor Completion
Tensor completion is the problem of observing (possibly with noise) subset of entries of a tensor and then estimating the remaining entries based on an assumption low-rankness. The tensor completion problem is encountered in number of important applications, including computer vision (Liu et al.)
2012; Zhang et al. 2019), regression with only categorical variables (Aswani) 2016), healthcare (Gandy et 2011 Dauwels et al. 2011), and many other application domains (Song al.) 2019).
Although the special case of matrix completion now well understood, the tensor version this problem has an unresolved tension. To date, tensor completion algorithm has been shown to achieve the information- -teooretic sample complexity rate. Namely, for tensor completion problem on rank à tensor with sample size n, information-theorete rate estimation error is /k: Σe ri / (Gandy et al. 201T). In fact, evidence suggests computational barrier in which no polynomial-time algorithm can achieve this rate (Barak and Moitra 2016)). One set of approaches has polynomial computation but requires exponentially ctt al., 2011] Mu et al., 2014: Barak and Moitra 2016 Montanari and Sun 2018). whereas another set of approaches achieve substantially closer the coormationn-hhoreee rate but (in order to attain global minima) requires solving NP-hard problems that lack numerical algorithms (Chandrasekaran
samples than the information seaaationnthhoree theoretic rate (Gandy
et al. 2012 Yuan and Zhang 2016 2017 Rauhut and Stojanac 2021
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

However, algorithms that achieve the information -thooretic rate have been developed for few special cases tensors. Completion of nonnegative rank-1 I tensors can be written as a convex optimization problem (Aswani 2016). For symmetric orthogonal tensors, variant of the Frank-Wolfh algorithm has been proposed (Rao al. 2015). Though this latter paper does not prove their algorithm achieves the information-theowe
rate, this can be shown using standard techniques (Gandy et 20112011)) T). This latter paper is closely related to the approach we take in this paper, with one the key differences being the design of different separation oracle in order to support a different class of tensors.
1.2 Contributions
This paper proposes a numerical algorithm for completion of nonnegative tensors that provably converges to global minimum in a linear (in numerical tolerance) number of oracle steps, while achieving the information-thorres
rate. Nonnegative tensors are encountered in many applications. For instance, image and video data usually consists of nonnegative tensors (Liu et al. 2012: ZZhang et al., 2019). Notably, the image demosaicing problem that must be solved by nearly every digital camera (Li et al.) 2008) is an instance of nonnegative tensor completion problem, though it has not previously been interpreted as such. Nonnegative tensor completion also encountered specific instances of recommender systems (Song et al.) 2019), healthcare applications (Gandy et al. 2011 Dauwels et al. 201T), and statistical regression contexts (Aswani) 2016).
Our approach is to define new norm for nonnegative tensors using the gauge of specific 0-1 polytope that we construct. We prove this norm acts as a convex surrogate for rank and has low statistical complexity (as measured by the Rademacher average for the tensor, viewed as a function from set of indices the corresponding entry), but is NP-hard to approximate to an arbitrary accuracy. Importantly, we prove that the tensor completion problem using this norm achieves the information-iie theorrticc rate in terms of sample complexity. However, the resulting tensor completion problem is NP-hard to solve. Nonetheless, because our new norm is defined using 0-1 polytope, we can use integer linear optimization as practical means to solve linear separation problems over the polytope. We combine this insight with a variant of the Frank- Wolfe algorithm to construct our numerical algorithm, and we demonstrate its effectiveness and scalability through experiments.
Norm for Nonnegative Tensors
Consider tensor v IRnX--XTy, To refer to specific entry in the tensor the notation 2/2 == U....... where x (Z....., . Ip), and æ, E [r.] denotes the value of the i-th index, with [8] 3). Let p = Σ, Pi. π II, ri. and R [m] ................................ [rp]-
A nonnegative rank-1 tensor is the = II 0!h), where g( RT are nonnegative vectors indexed by the different values of z& E [rx]. To simplify notation, we drop the superscript in o!!)) and write this as an when clear from the context. For nonnegative tensor vb its nonnegative rank is
rank (+)) min[g x/ = Ei wh zbth E B for k E [4]),
(1)
where we define the ball of nonnegative rank- 1 tensors whose maximum entry is X R4 to be
BA {v 1he = A II Om,, Oz. E [0, for I E R}
(2)
and Boc lim oo Bx A nonnegative CP decomposition is given by the summation v rrank (w) u/, where with E Bx for le E [rank+())]
2.1 Convex Hull of Nonnegative Rank-1 Tensors
Now for X E R4, consider the finite set of points:
S = (vb th IT 6o.. Oz. E {0,11) for R}.
(3)
Using standard techniques from integer optimization (Hansen) 1979 Padberg 1989), the above set of points can be rewritten
set of linear constraints on binary variables: SA (v0 A (1 p) +
A Eh_ Ozp. < 222,00 0 < 2h < X Ozg- Oz, E {0, 1}. for k E [p]. E RJ. Our first result is that the convex hulls of the set of points S₃ and of the ball B, are equivalent.
Proposition 2.1. We have the relation that Cx conv((x) conv(Sx).

---

Proof. We prove this by showing the two set inclusions conv(Sx) S conv(Bx) and conv S conv(S2). The first inclusion is immediate since by definition we have S c Bx, and so we focus on proving the second inclusion. We prove this by contradiction: Suppose conv [xx) & conv(Sx). Then there exists a tensor v E B, with v² & conv(Sx). By the hyperplane separation theorem, there exists y E R= and 5 > O such that (i,, v²)) 2 (4,, v)) + H for all s E conv(Sx), where (+-)) is the usual inner product that is defined as the summation of clementwise multiplication. Now consider the multilinear optimization problem
max (p, 4+)
s.t. V/ = A I.T Oxxi 2z.- [0,
for a E R
(4)
for R
Proposition 2.1 of (Drenick, 1992 shows there exists a global optimum v of 4 with 8 Sy- By construction, we must have (p, v²") 2 (p,, v²)), which implies (4p, )) 2 (p.)) + for all
& (Sn) But this last statement a contradiction since vi" Sx S (Snv(S.).
Remark 2.2. This result has two useful implications. First, CΛ is a polytope since it is the convex hull of finite number of bounded points. Second, the elements of S2 are the vertices of Cx. since any individual element cannot be written as convex combination of the other elements.
We will call the set Cx the nonnegative tensor polytope. A useful observation is that the following relationships hold: Bx ABI, Sx XS1, and C2 AC1.
2.2 Constructing a Norm for Nonnegative Tensors
Since the set of nonnegative tensors forms cone (Qi al. 2014), we need to use a modified definition of a norm. A norm on a cone K. is a function p K + R, such that for all x, y E KC the function has the following three properties: p(z) 0 if and only if 0; p(> - x) = ? p(a) for E R4; and p(r + y) S p(z) + p(y). The difference with the usual norm definition is subtle: The second property here is required to hold for y E R.,, whereas in the usual norm definition we require p(7- x)) = hyl p(x) for all y E R.
We next use Cx to construct new norm for nonnegative tensors using a gauge (or Minkowski functional) construction. Though constructing norms using a gauge is common in machine learning (Chandrasekaran al., 2012), the convex sets used in these constructions are symmetric about the origin. Symmetry guarantees that scaling the ball eventually includes the entire space (Rockafellar and Wets 2009). However, in our case C2 is not symmetric about the origin, and without proof do not a priori know whether scaling Ci eventually includes the entire space of nonnegative tensors. Thus we have to explicitly prove the gauge a norm.
Proposition 2.3. The function defined as
| == inf }
(S)
is a norm for nonnegative tensors v E ERT -'"'"-X>
Proof. We first prove the above function is finite. Consider any nonnegative tensor & E R x and note there exists a decomposition 3o- Σi= 55* with s** E || B₁ (Qi et al. 2016). (This holds because we can choose each 2 to have single non-zero value that corresponds to a different entry of vb.) Hence by Proposition 2.1 1.1. 26 E || C1. Recalling the decomposition of t. this means & E TT| max C, which by definition means || I π || Thus || must be finite.
Next we verify that the three properties of a norm on a cone are satisfied. To do so, we first observe that by definition: C1 is convex; 0 Cr: and C1 is closed and bounded. Thus by Example 3.50 of (Rockafellar and Wets 2009) we have {w || = 0 {0). which means the first norm property holds. Also by Example 3.50 of (Rockafellar and Wets 2009) we have XC₁ C XC, for all 0 <<> A < X', which means the second norm property holds. Last, note Example 3.50 of (Rockafellar
and Wets 2009) establishes sublinearity of the gauge, and so the third norm property holds.
2.3
Convex Surrogate for Nonnegative Tensor Rank
An important property of our norm ||++|+ that can be used as a convex surrogate for tensor rank, whereas the max and Frobenius norms cannot.
3

---

Propasition 2.4. if is nonnegative tensor, then we have If rank (+) = then || = 1 |
| S | S rank (+)
|| max
max-
Proof. Consider any X 0. if Sx, then by definition ||v/]| X. By the convexity of norms
we have that: e E Cx. then || max S. X. This means that for all 2 we have Cx C U := {
|mal I X} Thus have the relation inf f 2 0 d { I inf 2 0 d AC1)- But the left side is || |max and the right side is | This proves the left side of the inequality.
Next consider the case where rank, (+b) = 1. By definition we have vó E || B, Thus & E ||al| C1, and so ||+++++ I || max. This proves the rank-1 case.
Last we prove the right side of the desired inequality. Consider any nonnegative tensor db. Recall its nonnegative CP decomposition & Exak+ (19)
zb with 2h E Boo The triangle inequality gives
| - =k=1 - (0)
|| -
(v)) || Ilmax:
(6)
where the equality follows from the phove--roved rank-1 I case since rank, (4²*) 1 by definition of the CP decomposition. But ||v/ Ilmax I || since the tensors are nonnegative.
Remark 2.5. These bounds tight. The lower and upper bounds achieved by all nonnegative rank-1 1 tensors. The identity matrix with columns achieves the upper bound with rank (v) = k.
3 Measures of Norm Complexity
3.1 Computational Complexity
We next characterize the computational complexity of our new norm on nonnegative tensors.
Proposition 3.1. is NP-hard to approximate the nonnegative tensor norm ||+ to arbitrary accuracy.
Proof. The dual norm is || = s (pp, e) | S 1} for all tensors E R Xr.xx--Xr, Xrp, Theorems 3 and 10 of (Friedland and Lim 2016) show that approximation of the dual norm || llo polynomial- time reducible to approximation of the norm Il+ We proceed by showing a polynomial-tmme reduction approximation of Il.. Without loss of generality assume p 2 and
T1 72. The appendix of (Witsenhausen 1986) proves that MAX CUT is polynomial -iemimeeeeeeeeeeeee reducible to sup (ip, v)) d E S.). However, since the objective function is linear and the set S consists of the vertices of C1. this means that optimization problem is equivalent to sup ((p, eb) vb E CT). This is the desired polynomial-time reduction of MAX CUT to approximation of the dual norm || llo because
Ci = ( |++++ < 1}. The result now follows by recalling that approximately solving MAX CUT to arbitrary accuracy NP-hard (Papadimitriou and Yannakakis 1991 Arora et al. 1998).
D
Corollary 3.2. Given K R2 and va R Xp"xx"" it is NP-complete to determine 01 S K.
Proof. The problem is NP-hard by reduction from the problem of Proposition 3.1 In particular, a binary search can approximate the norm using this decision problem, (1|= < K)? ? as oracle.
By Proposition 2.4, the search can be initialized over the interval [0, π ||| max] Furthermore, the
decision problem is NP because can the (polynomial-sized) from (2) as certificate.
0
3.2 Stochastic Complexity of Norm
We next show that our norm || |+ has low stochastic complexity. Let X = (x)), (n)). and suppose di independent and identically distributed (i.i.d) Rademacher random variables (i.e.,
σ, = +1 with probability }) (Bartlett and Mendelson 2002 Srebro et al. 2010 The Rademacher complexity for set of functions H. is R(H) = E(supRen =l 2i=1 o. h(2 (x)())) and the worst case D G. ()) These notions
Rademacher complexity of H. is W(H) = supx E, (supkeR : - can be used to measure the complexity of sets of matrices (Srebro and Shraibman, 2005) or tensors (Aswani 2016). The idea is to interpret each nonnegative tensor as function v R - R4, from set of indices æ E R. to the corresponding entry of the tensor v/z. This complexity notion useful for the completion problem because it can be directly translated into generalization bounds.

---

Proposition 3.3. We have R(CA) & W(CA) & 2
Proof. First note that from their definitions we get R(CA) W(C)). Next define the set Pa
f
ab E Sx). and recall that Cx = conv(Sx) ) by Proposition 2.1 This means W(Cx) W(Sx) (eedoxx
and Talagrand 1991, |Brrtlett and Mendelson 2002). Next observe that
W(Cx) W(Sx) supx E, su Σ i= of (.0(0)
supx E. paP Σ 02 12x0)) S supx r log #PX/n
where in the second line we replaced the supremum with a maximum, since the set Px finite, and used the Finite Class Lemma (Massart 2000) with r = maxœep> (Var)) ) v A/n. This inequality is due to the fact that PA consists of tensors whose entries from {-), 0, A}. Thus W(Cx) S A (2 log 2) (p + 1)/n. The result follows by noting that log 2 (p + 1) S 2p.
Remark 3.4. Because has norm (e.g., max and Frobenius norms) will be O(v 2// O(yrP/n) However, the Rademacher complexity in our norm || + is O( ((v = ((vrp/n) which is exponentially smaller.
O(r²) entries, the Rademacher complexity in typical tensor
Tensor Completion
n. Let I (ui,...,āu] dx) C [n]] be any set of points that specify all the unique =ii for I...., n, meaning the set ( ((( does not have any repeated points and x(i) U for all I....,n. The nonnegative tensor completion problem using our norm ||+|| is given by
Suppose we have data (i)) E x R for ,,..,,
e E arg min 1. EL (v(1) 22
(
s.t. || <
We will study the statistical properties of the above estimate and describe the elements of algorithm solve the above optimization problem. The purpose of defining the set U is that it is used in constructing the algorithm used to solve the above problem.
4.1 Statistical Guarantees
Though in the previous section we calculated Rademacher complexity for nonnegative tensors in Cx viewed as functions, here we use an alternative approach to derive generalization bounds. The reason is that generalization bounds using the Rademacher complexity are not tight here.
Our approach is based on the observation that the nonnegative tensor completion problem using our norm || || is equivalent to convex aggregation problem (Nemirovski) 2000; Tsybakov Lecué et al. 2013) for a finite set of functions. In particular, by Proposition 2.1 we have 3 X} Cx conv(S)). The implication is we can directly apply existing results for
2003
convex aggregation to provide a tight generalization bound for the solution of (8)
Proposition 4.1 ((Lecué et al. 2013)). Suppose ly| < almost surely. Given any ô 0, with probability at least 46 we have that
B((v $2) < min E ((v - px) ((1y-pa))) + co max (p] mmx (Sm.
log( log(1/8)
(9)
EcCx
where Og is an absolute constant and
2 n
2 vm
Sn
(10)
log
20
2 Vni
Remark 4.2. We make two comments, First, note that Čn O pp/n). Second, in some regimes Gr. can be considerably faster than the Vp/n rate.
Generalization bounds under specific noise models, such as an additive noise model, follow as corollary to the above proposition combined with Proposition 2.4
5

---

Corollary 4.3. Suppose i is a nonnegative tensor with cank+(p) = k and llp/|max S If (())) are independent and identically distributed with (y(i) (Pati) I almost surely and Ey(i) = Pz(s). Then given any 6 > 0, with probability at least 48 we have
B( )²) f e² co (pk + e)²² max [Sn, 1os(1/61
(11)
where Sn is as in 10 and co is an absolute constant. Remark 4.4. The above result achieves the information-theoreiic rate when the rank k O().
4.2 Compatational Complexity
Though (8) is a convex optimization problem, our next result shows that solving it is NP-hard. Proposition 4.5. It is NP-hard solve the optimization problem to arbitrary accuracy.
Proof. Define the ball of radius 5 > 0 centered at a nonnegative tensor & to be B(b, 6) = { 11
b/ S 8}. Next define W ((1,,) 6) = U Uvec, ( 5) and W(G, = {v E C1 B(b,, 6) C.). The weak membership problem for C₁ is that given nonnegative tensor v/ and 8 0 decide whether 30 E W[C,, 6) or & & WC.1_-8%
Theorem 10 of (Friedland and Lim 2016) shows that approximation of the norm || ||+ is polynomial-time reducible to the weak membership problem for C, Since Proposition 3.1 shows that approximation of the norm || ||+ is NP-hard, the result follows if we can reduce the weak membership problem to
Suppose we are given inputs s and for the weak membership problem. Choose x(1) for 1,..., IT such that each element in R is enumerated exactly once. Next choose y(i) (2)()) Finally, note if we solve (8) and the minimum objective value is less than or equal to 6, then we have & E WC1,, 6); otherwise we have vi & W(1, -)). The result now follows since this was the desired reduction. [
We note that the decision version of (8), that is ascertaining whether given tensor 2b attains an objective less than given value while also satisfying || S X, is NP-complete. This follows directly from Corollary 3.2 and Proposition 4.5
4.3 Numerical Computation
Although it is NP-hard, there is substantial structure that enables practical numerical computation of global minima of (8). The key observation is that C1 is a 0-1 polytope, which implies the linear separation problem this polytope can be solved using integer linear optimization. Integer optimization has estalestablished global algorithms that are guaranteed to solve the separation problem for this polytope. This is critical feature that enables the use of the Frank-Wolfe algorithm or one of its variants to solve (8) to a desired numerical tolerance. In fact, the Frank-Wor variant known Blended Conditional Gradients (BCG) (Braun al. 2019) is particularly well-suited for calculating a solution to (8) for the following reasons:
The first reason is that our problem has structure such that the BCG algorithm will terminate in linear (with respect to numerical tolerance) number of oracle steps. A sufficient condition for this linear convergence is if the feasible set is polytope and the objective function is strictly convex over the feasible set. For our problem (8), the objective function can be made strictly convex over the feasible set by an equivalent reformulation. Specifically,
the equivalent reformulation in which we change the feasible set from ( : || < A} = Cx to Projur (Cx) where the projection is done over the unique indices specified by the set U. In fact, this projection is trivial to implement because it simply consists of discarding the entries of v that are not observed by the zi(i indices.
The second is that the BCG algorithm uses weak linear separation, which accommodates early- termination of the associated integer linear optimization. Integer optimization software tends to find optimal near-optimal solutions considerably faster than certifying the optimality of such solutions. Furthermore, a variety of tuning parameters (Berthold et al. 2018) can be used to accelerate the search for good primal solutions when exact solutions not needed. We also deploy a fast altermating maximization heuristic in order to avoid integer optimization oracle calls where possible. Thus, early-termination allows us deploy a globally convergent algorithm with practical solution times.
Hence we use the BCG algorithm to compute global minima of (8) to arbitrary numerical tolerance. For brevity we omit a full description of the algorithm, and instead focus the separation oracle,

---

Algorithm 1: Weak Separation Oracle for C2
Input:
linear objective c E x"x point vb E CΛ. accuracy K 2 1, gap estimate t norm bound X
Output: Either (1) vertex E Sx with (c, Φb - () 2 o K, or (2) false: (c, vb pp I for all y Cx
Algorithm 2: Alternating Maximization
Input: linear objective E R xpp,, point v/2 E CA, norm bound X, incumbent (binary)
solution E Sx
Output: Best known solution
(9) for i to do
for to ri do
0()) + 1-0 (()
if MM (0) > then
2 PM (0)
else
0
(
end if end for
end for
which is the main component specifically adapted to application. The oracle is described in Algorithm[ where (: the dot product for tensors viewed as vectors; for notational simplicity state the oracle terms of the original space, ignoring projection onto U. Output condition (1)
provides separation with some vertex while (2) requires certification that no such vertex exists.
In implementing the weak separation oracle, we first attempt separation with our alternating maxi- mization procedure. Described as Algorithm 2, it involves the following objective function:
zM =- ΣZER (Cx, Vie À -I Oz.))
(12)
The separation problem is thus treated as multilinear binary optimization problem, and the algorithm successively minimizes in each dimension. We apply this heuristic fixed number of times, randomly complementing entries in the incumbent each time. The procedure runs in polynomial-ting and not guaranteed to separate nor can it certify that such separation is impossible. However, in our experiments it succeeds often, offering substantial practical speedups.
alternating maximization fails to separate, then we solve the integer programming problem:
max(c, v/ ip) $4,0
s.t. A (1 -p) x. +. Ozz Spp
E R
(13)
5 Pr S A -0mm
h: E |pl, R
Oz E 1}
k E [p], E R
Note that early termination is deployed: stop whenever incumbent solution is found such that the objective is greater than 4/K. If no such solution exists, then the integer programming solver is guaranteed (eventually) establish dual bound 20 such that (c, (p) S 2 Φb
Numerical Experiments
Here we present results that show the efficacy and scalability of our algorithm for nonnegative tensor completion. Our experiments were conducted on a laptop computer with 8GB of RAM and an Intel Core i5 2.3Ghz processor with 2-cores/4-threes The algorithms were coded in Python 3. We used
7

---

30
ALS
0.8
SILRTC
0.6
Time (3)
TNCP
15
BCG
10
ALS
0.2
SILRTC
TNCP
20
40
60
80
100
20
40
60
80
100
Figure 1: Results for order-3 nonnegative tensors with size X P X and 500 samples.
1.0
0.8
BCG
Time (s)
10
ALS
100
0.4
BCG
10
SILRTC
10
0.0
P
Figure 2: Results for increasing order nonnegative tensors with size 10 and 10, 000 samples.
102
0.8
SILRTC
Time (s)
10
TNCP
0.4
108
0.2
SILRTC
TNCP
10-1
10
10
109
10
10
10
10a
10
Sample
Sample
Figure Results for nonnegative tensors with size x0x6 and increasing n samples.
BCG
0.8
SILRTC
BCG
TNCP
10a
SILRTC
0.4
TNCP
10
10a
0.0
10-2
10-1
100
10a
10-2
10 -1
10a
10a
Sample
Sample
Figure Results for nonnegative tensors with size 10x7 and increasing n samples.

---

Gurobi v9.1 (Gurobi Optimization, LLC 2021 to solve the integer programs (33). As a benchmark, we use alternating least squares (ALS) which is often called a "workhorse" for numerical tensor problems (Kolda and Bader 2009) as well as two state-of-the-art methods implemented by the PyTen package (Song et 2019), namely the simple low rank tensor completion (SiLRTC) algorithm (Liu et al., 2012) and the trace norm regularized CP decompasition (TNCP) algorithm (Liu et al.) 2014). PyTen is available from httph: //githu. coom/datamllan aaattamllab/ptterrr under a GPL 2 license.
To minimize the impact of hyperparameter selection in our numerical results, we provided the ground truth values when possible. For instance, in our nonnegative tensor completion formulation 8 we chose À to be the smallest value for which we could certify that || S À for the true tensor v. This was accomplished by construction of the true tensor 3. For ALS and TNCP, we used nonnegative rank k that was the smallest value for which we could certify that rank (v) S k. This was also accomplished by construction of the true tensor tb. A last note that ALS often works better when used with 1.2 regularization (Navasca et al. 2008). The hyperparameter for the 1.2 regularization for ALS was chosen in a way favorable ALS in order to maximize its accuracy.
5.1 Experiments with Third-Order Tensors
Our first set of results concerns tensors of order = 3 with increasing dimensions. In each experiment, the true tensor was constructed by randomly choosing 10 points from S, and then taking random convex combination. This construction ensures || < and rank (v) < 10. We used n = 500 samples (with indices sampled with replacement). Each experiment was repeated 100 times. and the results are shown in Figure ! A table of these values and their standard error is found in the Appendix. We measured accuracy using normalized mean squared error (NMSE) || |1 which is more stringent measure than used in Corollary 4.3 because the statistical theoretical result does not include normalization. The results show that our approach provides modestly higher accuracy but requires more computation time. However, computation time remains on the order of seconds for the various tensor sizes. We note that the NMSE value of approximately 0.48 that TNCP converges to is the value achieved by a tensor that is identically the average of y(i) in all its entries.
5.2 Experiments with Increasing Tensor Order
Our second set of results concerns tensors with increasing order p, where each dimension takes the value r; 10 for i 1..... p.. In each experiment, the true tensor was constructed by the method in 10, 000 samples (with indices sampled with replacement). Fach experiment
Sec. 5. We used was repeated 100 times, and the results are shown in Figure 2 with the full values and standard error given in the Appendix. SiLRTC and TNCP were unable to run for tensors with 108 entries. The results show that our approach provides much higher accuracy but requires more computation time. However, computation remains on the order of minutes even for the largest tensor with 10 entries.
5.3 Experiments with Increasing Sample Size
Our third and fourth set of results concerns tensors of size 10x6 and 10x7, respectively, where experiments are conducted with increasing sample size, given in the table as percentage of total entries. The true tensor & was constructed in Sec. 5.1 We begin with sample percentage 0.01% % (with indices sampled with replacement), and extend each set of experiments' sample size by one order of magnitude. Each experiment was repeated 100 times, and the results are shown in Figures and with the full values and standard error given in the Appendix. Again, the numerical results show that our approach provides substantially higher accuracy but requires more computation time. The computation time remains on the order of minutes for most of the sampling schemes, excepting the draw of 1 entries for a tensor with 10" entries (i.e., about 1.5 hours).
Conclusion
We defined a new norm for nonnegative tensors and used it to develop an algorithm for nonneg- ative tensor completion that provably converges in a linear number of oracle steps and meets the informationntheorreti sample complexity rate. Its efficacy and scalability were demonstrated using experiments. The next step is to generalize this approach to all tensors. In fact, our norm definitions, optimization formulations, algorithm design, and theoretical analysis all extend to general tensors.

---

Acknowledgements
This material is based upon work partially supported by the NSF under grant CMMI-1847666.
10

---

References
Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. (1998). Proof verification and the hardness of approximation problems. Journal of the ACM (JACM), 45(3):501-555.
Aswani, (2016). Low-rank approximation and completion of positive tensors. SIAM Journal on Matrix Analysis and Applications, 37(3):1337-1344,
Barak, and Moitra, A. (2016). Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory, pages 417-445. PMLR.
Bartlett, P. and Mendelson, S. (2002). Rademacher and gaussian complexities: Risk bounds and Structural results. J. Mach. Learn. Res.
Berthold, T., Hendel, G., and Koch, T. (2018). From feasibility improvement to proof: three phases of solving mixed- -ittger programs. Optimization Methods and Software, 33(3):49--517,
Braun, G., Pokutta, S., Tu, D., and Wright, S. (2019). Blended conditonal gradients. In International Conference on Machine Learning, pages 735-743. PMLR.
Chandrasekaran, V., Recht, B., Parrilo, P. A., and Willsky, A. S. (2012). The convex geometry of linear inverse problems. Foundations of Computational mathematics, 12(6):805-849,
Dauwels, J., Garg, L., Earnest, A., and Pang. L. (2011). Handling missing data medical questionnaires using tensor decompositions. In 2011 8th International Conference Information, Communications Signal Processing, pages 1-5.
Drenick, R. (1992). Multilinear programming: Duality theories. Journal of optimization theory and applications, 72(3):459 486.
Friedland, S. and Lim, L.-H. (2014). Computational complexity of tensor nuclear norm. Submitted.
Friedland, S. and Lim, L.-H. (2016). The computational complexity of duality. SIAM Journal on Optimization, 26(4):2378-22
Gandy, S., Recht, B., and Yamada, I. (2011). Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse problems, 27(2):025010.
Gurobi Optimization, LLC (2021). Gurobi Optimizer Reference Manual.
Hansen, P. (1979). Methods of nonlinear 0-1 programming. In Annals of Discrete Mathematics, volume 5, pages 53-70. Elsevier.
Hillar, C. and Lim, L.-H. (2013). Most tensor problems are np-hard. J. ACM, 60(6))45:1-45) 45::99.
Kolda, T. and Bader, B. (2009). Tensor decompositions and applications. SIAM Review, 51()):455- 500.
Lecué, G. et al. (2013). Empirical risk minimization is optimal for the convex aggregation problem. Bernoulli, 19(5B:215332166.
Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces: Isoperimetry and Processes. Springer.
Li, X., Gunturk, B., and Zhang, L.. (2008). Image demosaicing: systematic survey. In Visual Communications and Image Processing 2008, volume 6822, page 68221J. International Society for Optics and Photonics.
Liu, J.. Musialski, P., Wonka, P., and Ye, J. (2012). Tensor completion for estimating missing values in visual data. IEEE transactions on pattern analysis and machine intelligence, 35(1):208 2200.0
L Liu, Y., Shang. F., Jiao, L.., Cheng, J., and Cheng, H. (2014). Trace norm regularized cande- comp/parafac decomposition with missing data. IEEE tronsactions on cybernetics, 45(11):2437. 2448.

---

Massart, P. (2000). Some applications of concentration inequalities to statistics. Annales de la faculté des sciences de Toulouse Sér. 6, 9()):245-303.
Montanari, A. and Sun, N. (2018), Spectral algorithms for tensor completion. Communications on Pure and Applied Mathematics, 71 71(11):2381-242)
Mu, C., Huang, B., Wright, J., and Goldfarb, D. (2014). Square deal: Lower bounds and improved relaxations for tensor recovery. In International conference on machine learning, pages 73-81. PMLR.
Navasca, C., De Lathauwer, L.,, and Kindermann, S. (2008). Swamp reducing technique for tensor decomposition. In 2008 16th European Signal Processing Conference, pages 1-5, IEEE.
Nemirovski, A. (2000). Topics in non-parametric statistics. Ecole d' Eté de Probabilités de Saint- Flour, 28:85.
Padberg, M. (1989). The boolean quadric polytope: some characteristics, facets and relatives. Mathematical programminng 45(1-3):139-172.
Papadimitriou, C. H. and Yannakakis, M. (1991). Optimization, approximation, and complexity classes. Journal of computer and system sciences, 43(3):425
Qi, Y., Comon, P., and Lim, L.-H. (2014). Uniqueness of nonnegative tensor approximations. arXiv preprint
Qi Y., Comon, P., and Lim, L.-H. (2016). Uniqueness nonnegative tensor approximations. IEEE Transactions Information Theory, 62(4):2170-2183.
Rao, N., Shah, P., and Wright, S. (2015). Forward-backward greedy algorithms for atomic norm regularization. IEEE Transactions on Signal Processing, 63321):5798-5811
Rauhut, H. and Stojanac, 2. (2021). Tensor theta norms and low rank recovery. Numerical Algorithms, 88(1):25-66.
Rockafellar, R. and Wets, R. (2009). Variational Analysis. Springer.
Song, Q., Ge, H., Caverlee, J., and Hu, X. (2019). Tensor completion algorithms in big data analytics. ACM Transactions on Knowledge Discovery from Data (TKDD), 13(1):1-48.
Srebro, N. and Shraibman, (2005). Rank, trace-norm and max-norm. In International Conference on Computational Learning Theory, pages 545-560. Springer.
Srebro, N., Sridharan, K., and Tewari, A. (2010). Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, pages 2199-2207.
Tsybakov, A. B. (2003). Optimal rates aggregation. In Learning theory and kernel machines, pages 303-313 Springer.
Witsenhausen, H. (1986). A simple bilinear optimization problem. Systems & control letters, 8(1):1-4.
Yuan, M. and Zhang, C.-H. (2016). On tensor completion via nuclear norm minimization. Foundations of Computational Mathematics, 16(4):1031-1063
Yuan, M. and Zhang, C.-H. (2017). Incoherent tensor norms and their applications in higher order tensor completion. IEEE Transactions Information Theory, 63(10):6733-676
Zhang, X., Wang, D., Zhou, Z., and Ma, Y. (2019). Robust low-rank tensor recovery with rectification and alignment. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(1):238- -255.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec. S
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is
foundational research and not tied particular applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URLY? [Yes] See Supple- mental Material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Sec. [
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] See Appendix.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Sec. [
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators?
[Yes] See See, for
citation to the PyTen package.
(b) Did you mention the license of the assets? [Yes] See Sec. 5 for the license of the PyTen
package.
(c) Did you include any new assets either the supplemental material or as URL? [Yes] There is new code in the Supplemental Material.
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "kxAjMwQIHOb", "reviewer": "Reviewer_7JBT", "summary": "The authors proposed an approximated algorithm for nonnegative tensor completion that seems to work very efficiently (the claim is in linear time).\n", "questions": "In order to become fully convincing, the paper should report much stronger numerical evidence of scalability (i.e. linear behaviour with n) and efficiency (i.e. ability to work close to the IT threshold).\nMoreover, I have to admit to being very surprised that an algorithm that performs a local optimization by flipping single variables one at a time is able to reach the optimal solution in general. The authors should discuss the reasons beyond this unreasonable effectiveness.\nI would like to understand whether the apparent very good performance depends on the tensor low-rank (which is not larger than 10 in all numerical experiments shown by the authors). What happens if the tensor rank is increased? Does the algorithm keep working with the same efficiency and scalability?\n\n", "limitations": "The authors do not really discuss the issue.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written and the authors present their results in a clear way.\nThe result is definitely original and very important.\nMy only concern is about the authors' claims based on Figures 3 and 4\nThe data for the BCG algorithm in the right panels are far from being linear!\nData in Fig. 3 are very noisy and those in Fig. 4 have a clear upwards curvature, suggesting a more than linear growth for larger n values.\nMoreover, from the numerical experiments is not clear at all whether the algorithm is matching the IT threshold: data supporting this claim are completely missing or should be presented in a more evident way.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HQpLR0zD0Q", "reviewer": "Reviewer_skYN", "summary": "The authors introduce an algorithm for nonnegative tensor completion. For that, a new tensor norm is defined which is shown to be a convex surrogate of the tensor rank. To define this norm, the authors first show that the convex hull of the ball of the nonnegative rank-1 tensors whose maximum entry is 1 is the same as the convex hull of all the binary rank-1 tensors. Since the latter is a polytope and the binary rank-1 tensors are the vertices of the polytope, linear integer programming techniques can be used to optimize over it. Therefore, the norm of a nonnegative tensor of any rank is defined using such polytopes. The authors further study the norm by proving its NP-hardness and its stochastic complexity, in terms of Rademacher complexity. Finally, it is shown how integer linear programming can be used for efficient computation of the global minima. The numerical results show that the proposed method can achieve better estimation error and is able to complete tensors with fewer samples. ", "questions": "It would have been interesting to evaluate the algorithm for hyperparameters other than the ground truth. ", "limitations": "There is no dedicated \"limitations\" section. But the authors discuss the limitations, such as the solution being limited to nonnegative tensors, the computational complexity, and the running time.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n* The problem of tensor completion is an interesting problem that shows up in different applications from recommender systems to wireless communications. Aside from that, the introduction of a norm that is a convex surrogate of the tensor rank and has nice properties for optimization problems is impactful on its own. \n* The authors study the different aspects of the problem and the proposed norm theoretically, prove the claims, and/or refer the reader to the relevant papers.\n* A numerical algorithm is proposed to use the introduced norm for the nonnegative tensor completion problem. Although the proposed norm is NP-hard to calculate to arbitrary accuracy, the proposed algorithm is able to calculate the global minima. This is due to the proposed norm being a 0-1 polytope. \n* The paper is well-structured and the proofs are well-written. The authors discuss the limitations\n\nWeaknesses:\nThere are not many weaknesses. The authors could have moved all or some of the proofs to the appendix. This would have opened some space to provide more intuition to the reader, add some visualizations, explain the algorithm in more detail, and possibly add more experiments. For example, it would have been interesting to evaluate the algorithm for hyperparameters other than the ground truth. This is of great practical importance, as we usually do not have access to the true rank or the true maximum value of the tensor. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "506j9dMN3e", "reviewer": "Reviewer_4C1A", "summary": "This paper studies the tensor completion problem for tensors with non-negative entries. The paper proposes a non-negative analog of the nuclear norm, denoted $\\Vert \\cdot \\Vert_{+}$ whose 1-ball is defined to be a convex combination of rank-1 $\\{0, 1\\}$-tensors. The paper proposes to solve the problem, dual to $\\Vert \\cdot \\Vert_{+}$-minimization to recover unknown non-negative tensor from a subset of observed entries. This approach is a natural analog of the nuclear norm minimization for general tensors. The paper proves that this approach w.h.p. can recover the unknown tensor from an essentially statistically optimal number of unknown samples. The authors prove that this minimization problem is NP-hard. At the same time, they show that the BCG algorithm can solve the problem with a linear number of calls to a linear separation oracle. Moreover, the paper proposes a heuristic algorithm for the oracle and studies its performance on synthetic data. ", "questions": "1) Can you please clarify what results in the papers cited on lines 33-34 achieve information-theoretic bounds? Are there specific numbered theorems? As far as I know, for $n\\times n \\times n$ tensors of rank r, Yuan and Zhang'16 prove recovery from r^{1/2}n^{3/2} samples, which is not the information-theoretic rate ($\\widetilde{O}(rn)$). I was not able to locate the corresponding information-theoretic rate results in the other two cited papers. I would like to kindly suggest to include exact statements of the prior work that achieves information-theoretic bounds in the appendix, as they are quite rare and are directly related to the main contribution of this paper.\n\n2) Cor 4.3 does not seem to achieve the information-theoretic bound unless the rank $k = O(1)$. Do I understand correctly that if $e = 0$, Cor 4.3 proves recovery from essentially $k^4\\cdot \\rho$ entries (as opposed to $k\\cdot \\rho$)? If that's correct, I believe the authors should either explicitly say that $k = O(1)$, or they should be more explicit in the description of their results.\n\n3)  The abstract and the text of the paper contain the claim: \"We prove that our algorithm converges in a linear (in numerical tolerance) number of oracle steps, while achieving the information-theoretic rate.\" However, the nature of the oracle does not seem to be mentioned until the end of the paper. In particular, it is not mentioned that this oracle solves an NP-hard problem. I believe those are important details, which if mentioned early give a better understanding of the results of the paper.\n\n4) Are there any additional simple assumptions that guarantee that the oracle can be implemented in polynomial time? This will give specific assumptions under which your algorithm for (8) works in polynomial time. Note that for standard nuclear norm (NN) minimization there are some regimes in which problem can be solved in polynomial time, even though the general problem is NP-hard. For example, using SOS, NN minimization is known for tensors with orthogonal components by Potechin-Steurer'17 and for low-rank tensors with random components by Kivva-Potechin'20.\n\n5) Prop. 3.1 and Cor 3.3 are a bit hard to understand, and I needed to look into the paper of Lecue et al to understand the claim. For example, in Prop 3.1, what is y? This variable seems to have meaning only when comes in pair with x, i.e., in pair $x\\langle i\\rangle, y\\langle i\\rangle$. It will also simplify reading if the definition of $\\mathbb{E}$ used in L197 is included. I believe it just stands for average over all entries of the tensor, but there are other ways to interpret it. What is the difference between $\\psi$ and $\\widehat{\\psi}$ in Prop. 4.1 and Cor 4.3?\n\n6) Did you try to run your algorithm on any real-world dataset? How does it compare to state-of-the-art approaches on such datasets? How does your algorithm compare to Liu-Moitra NeurIPS'20?\n\n7) In line 199 it seems that $o(\\sqrt{\\rho/n})$ should be $O(\\sqrt{\\rho/n})$. How can $\\xi_n$ be faster than $O(\\sqrt{\\rho/n})$ if this is an information theoretic bound? Can you clarify this claim please? Also, in the context of tensor completion $2^{\\rho}>\\pi>\\sqrt{n}$.\n\n8) What do you mean by \"NP-hard to solve to any accuracy\"? These words can correspond to different orders of quantifiers, which would result in different claims.  \n\n9) L 226 has claim: \"Although it is NP-hard, there is substantial structure that enables efficient numerical computation of global minima of (8).\" Efficient computation typically stands for \"polynomial time\", which suggests that you claim P = NP. Clearly, that's not what you claim. I would kindly suggest to reformulate or clarify this claim. \n\n10) In line 249 you claim that your implementation converges to the global optima. However, the experimental results, in the regimes where your theory suggests almost exact recovery (Table 2), have an error in the range 0.01-0.16 (which is much better than other approaches), but is still far from 0. Can you please clarify this? \n\n11) Line 30 says \"exponentially more samples than the information-theoretic rate\". Can you please clarify what do you mean? Exponential in which variable? The number of samples is always at most linear in the size of the tensor.", "limitations": "The paper proposes an approach that is NP-hard in the worst case and this paper does not seem to prove any runtime guarantees. However, the authors show that the problem can be solved in a linear number of calls to an integer-programming oracle (which is still NP-hard). It will be nice to explore special cases in which a polynomial-time algorithm (say, for oracle)  is available. \n\nI believe the paper will also significantly benefit from experiments on real-world data.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Significance: Tensors with non-negative entries frequently appear in practice, hence improved algorithms for this setup are likely to have further applications. This paper proposes a natural idea for the problem, which does not seem to be explored in the prior work. The experimental results presented by the authors show that their heuristic algorithm has better performance on tensors with low non-negative rank compared to some state-of-the-art approaches.\n\nClarity: The technical proofs seem to be correct and the paper is reasonably well-written. However, there is a number of vague statements, typos, or claims that are potentially overstated. See questions below. Additionally, it will be very helpful for the reader if details of BCG algorithm are included at least in the appendix.\n\nFinally, the paper uses notation that is non-standard in the literature, which makes it a bit harder to read. For instance, $r$ is typically reserved for the rank of the tensor, while this paper uses $k$ for the rank and $r_i$ for the dimensions of the tensor. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept