Constructive TT-representation of the tensors given as index interaction functions with applications
Authors: Gleb Ryzhakov
Ivan Oseledets
Venue: ICLR 2023 poster (2023)
Keywords: Tensor approximation
Discrete multivariate functions
Tensor train decomposition
TT-Tucker format
Game theory
Combinatorial problems

Abstract: This paper presents a method to build explicit tensor-train (TT) representations. We show that a wide class of tensors can be explicitly represented with sparse TT-cores, obtaining, in many cases, optimal TT-ranks. Numerical experiments show that our method outperforms the existing ones in several practical applications, including game theory problems. Theoretical estimations of the number of operations show that in some problems, such as permanent calculation, our methods are close to the known optimal asymptotics, which are obtained by a completely different type of methods.

Published as a conference paper at ICLR 2023
CONSTRUCTIVE TT-REPRESENTATION OF THE TENSORS GIVEN AS INDEX INTERACTION FUNCTIONS WITH APPLICATIONS
Gleb Ryzhakov,
Ivan Oseledets
Skolkovo Institute of Science and Technology, Moscow, Russia
Skolkovo Institute of Science and Technology and AIRI
g. k.rychaakv@@koltecchccc ru
Moscow, Russia
i Lsseeedetttkkkklleeelle ru
ABSTRACT
This paper presents a method to build explicit tensor-train (TT) representations. We show that wide class of tensors can be explicitly represented with sparse TT- cores, obtaining, in many cases, optimal TT-ranks. Numerical experiments show that our method outperforms the existing ones in several practical applications. including game theory problems. Theoretical estimations of the number of operations show that in some problems, such as permanent calculation, our methods are close to the known optimal asymptotics, which are obtained by a completely different type of methods.
INTRODUCTION
The tensor train is powerful tool for compressing multidimensional tensors (by tensor multidimensional array of complex numbers). It allows us to circumvent the curse of dimensionality in number of cases. In case of d-dimensional tensor with number of indices equal to for each dimension, direct storage of tensor involves O(n)) memory cells, while tensor train bypasses O(ndr²), where r is average rank of TT decomposition (Oseledets) 2011). In many important applications, the average rank may be small enough so that n >> ndr
Tensor approximation is hot topic in the paper (Richter et al. (202T) tensor train format is used to solve high-dimensional parabolic PDE with dimension in numerical experiments up to d 102. Problems of building tensor decomposition and
of machine learning. For example, in the
tensor completion are considered in (Lacroix et al. 2020 Fan 2022 Ma & Solomonik] [021].
The properties of tensor decompositions as applied to machine learning tasks are discussed in
Ghalamkari & Sugiyama 2021 Kileel et al. 2021 Khavari & Rabusseau, 2021).
Existing methods allow one to build TT-decompooitions by treating the tensor values as black box. The TT-cross approximation method (Oseledets & 'yrttshnikovv (010) adaptively queries the points where the tensor value evaluated. The iterative alternative schemes such as alternating least squares method (Oseledets & Dolgov] (012)) alternative linear schemes (Holtz et al. (2012), build a decomposition consistently updating the decomposition cores. These methods do not take into account the analytic dependence, if any, of the tensor value its indices. At the same time, for relatively simple tensors, these methods can build TT decomposition for a long time and in the vast majority of cases obtain answer with a given error greater than zero, even if the original tensor has an exact TT decomposition.
In this paper, we present fast method to directly construct tensor for which the analytica dependence of the tensor value on the values of its indices is known. Technically, our method works with functions, each of which depends on tensor index and which are sequentially applied to the values of the previous functions. This functions we call derivative
of the TT decomposition of
'By analytic dependence mean the known symbolic formula for the tensor value, not the definition of the term within complex analysis.

---

Published as a conference paper at ICLR 2023
functions hereafter. However, this assignment covers quite large range of functional dependences of tensor value on its indices if such a set of functions chosen skillfully. Examples are given in Section B and Appendix.
Our method works best cases where the derivative functions together with the tensor itself have a small number of possible values. In the Application section and Appendix there are several examples for indicator tensors taking values only and 1.
TT-cores, obtained by method, are highly sparse, which gives an additional gain in performance. In many cases our method gives the lowest possible TT-rank, so that no further rounding of the TT-cores is required. In some other applications, the ranks of the TT decomposition obtained by our method can be substantially higher than those obtained by approximate methods. However, in large number of such cases, the sparse structure of the cores allows one achieve performance comparable to known algorithms.
The advantage of representing tensors in the TT format not only in overcoming the curse of dimensionality,, but also in the implemented tensor algebra for them: we can easily add, multiply, round TT-tensors, calculate construct set of indicator tensors that represent some constraints in the given problem in advance, and then combine these constraints arbitrarily by multiplying these tensors with data tensor. practical of such scheme, we give an example of calculating the permanent of matrix. The cooperative games examples in Application section use the well-known algorithm for quickly finding the sum of all elements of the TT-tensor.
convolution (Oseledets) 2011). In this way we can, for example,
Other examples with practical problems are given in Appendix. They include: simple examples for sum, where explicitly show sparse TT-cores; cooperative games, where we show how one can build iterative algorithm, based
method; Knapsack problem (in several formulations), where we use existing algorithms to find the (quasi-) maximal element of the TT-tesorr; Partition problem; Eight queens puzzle in several extended formulations (see Fig. T for the result for the case of 10 queens); sawtooth sequence; standard Boolean satisfiability problem.
Python code with the examples is available the public domain In the vast majority of this examples we use products of tensors, convolution find multidimensional sums and maximum element search to solve optimization problems. These operations are sufficient to solve a large class of problems from different areas of mathematics.
Figure 1: The solution of 10-queen problem, obtained by our algorithm.
Our method has direct extension to more complex cases of tensor networks, for one the cooperative games below and in several examples in Appendix. Such construction is called Tu-Tucker (Dolgov & Khoromskij] 2013) Oseledets 2011).
Our main contribution and advantages of approach
the exact and fast representation of the tensor TT-format, which can then, necessary, be rounded to smaller ranks with given accuracy. In many of the given examples, this representation optimal in the sense that the ranks of the TT decomposition cannot be reduced without loss of accuracy;
highly sparse structure of TT-decomposition cores which leads to noticeable reduction in calculations:
unified approach and simple algorithmic interface to inherently different tasks and areas including those problems for which it is not immediately obvious the representation of the function specifying the tensor value in the form of consecutive functions (I) 3
the ability construct an approximate TT-decomposition with controlled error or/and with the specified maximum ranks of the TT decomposition;
2

---

Published as a conference paper at ICLR 2023
the possibility in cases to explicitly reduce the set of matrix operations on the TT- cores in calculating the required value to an iterative algorithm, since the cores of TT- decomposition sparse and their elements can be constructed explicitly in advance.
Related works In addition to the works mentioned above, let us list the following. In the paper (Oseleeets 2012) explicit representations of several tensors with known analytical dependence of indices are presented, bur for a fairly narrow class of tensors (see also (Khoromskij) 2018 Sec. 4.2)). In the survey (Grasedyck et al. 2013) techniques for low-rank tensor approximation are presented, including TT-formtt. In works (Cichocki et al. 2016 2017) many examples of applying Tucker and Tensor Train decomposition to various problems including machine learning and data mining algorithms. Tensor completion method described in the paper (Steinlechner, (2016) uses Riemannian optimization for reconstruction a TT-format blackbox. In the paper (Bian et al. 2022) energy- based learning approach for cooperative games is considered.
Background Consider a tensor K with the following dimensions {n1, n2. na). i... e C Xmaxx"Xnn where C is the set of complex numbers. IT-decomposition of the tensor K with TT-ranks fro, ri, ri,...; raj is defined as the product
K(i1, 12, ..... in)
Σ
Σ
Σ
Gi in, Gz in, 02)
ap=1a;
ad-1=la==1
Ga-G-------2 id-1, ad-1)Gu(aaa id, aa),
where tensors G; E Cri-1 Xn; are called cores of the TT-decomposition (we let ro = rd 1).
BUILDING TT-REPRESENTATION WITH THE GIVEN SEQUENCE OF FUNCTIONS
Note that if one needs to calculate the value of the TT-tensor in a given multi-index { .... i
it is more efficient to start the calculation from one end, as described in (Oseledets) 2011). In this approach, we take the vector == G1 i1, :) and multiply it by the matrix Gz(:, 12, :). Then we multiply the obtained vector v2 by the matrix Ga ia, :), etc. At each step we get 0%2 = o% Gs iR, :). The above process can be viewed as process of sequential transformation (in this case, linear) of the vector obtained at the previous step. Our algorithm is based on the idea the inverse step: knowing the sequence of arbitrary (in particular, nonlinear) transformations, can obtain cores TT-decomposition, each of which corresponds to its sequential transformation?
In addition, there is the problem of reducing arbitrary function of many variables to a sequence of functions, each of which depends on only one index and the value of the previous function.
2.1 DERIVATIVE FUNCTIONS
From an algebraic point of view, we want build TT-dccomposition of such tensors K, each element K(1,, i2, ..... ia) of which can be calculated in two consecutive passages. One, from to the left of the right, is follows
(6i) (12 0), az(in, in) (( at), ag(in, 12, ia) = f(3) a2).
a-1(1n, iz, i-1) = ((- ( ا12)
(1)
then from right to left
ad(ia) (bd: 0), as-i (r-1) ((d-I) dd);
astilia id-1, i+1) ((++)) a242),
(2)
and, finally,
K(in, i2, ..., id) (() a1-1; (1+1).
(3)
3

---

Published as a conference paper at ICLR 2023
G
plelit (18)))
80 1)
4-11
N+1
Gua
4-2
1112
(()
Tink
a.
G..1
6
1--1
(
4e-t te (1
Gest gorkiites o6s))
Ki (A) i ("
(b) Tensor in TT-format, corresponding to the computational tree
(a) Computation tree
Figure 2: Computation tree we can handle and the resulting TT-decomposition
The computation tree of this procedure is shown Fig. 2a
The underlying idea of reducing non-linear transformation (()) (Ιx; (x-1) - 0g to linear one Gg-1G&(: ig. :) - 2y quite simple: we assign to each possible input and output value of the derived function different basic vector then the specified transformation can be represented as matrix-vector multiplication (see Theorem 2.1 below). Thus, each function f(A) corresponds to core in the TT-decomposition of the resulting tensor, see Fig. 2b In this figure, the cores of the expansion, which are 3-dimensional tensors, are represented by circles. The blue lines with indices correspond to the input indices of the tensor. The black lines connecting the cores correspond the dimensions, by which the summation takes place. The red arrows show the correspondence between the output vector obtained by successive multiplication of the cores, starting from the left or right end, and the values of the derivative functions.
We write the first argument of the derivative functions f(k) as a lower index when describing examples and applications.
2.2 REPRESENTATION OF A MULTIVARIATE FUNCTION AS SEQUENCE OF FUNCTIONS
Unfortunately, there is no single algorithmic approach for constructing a sequence of derivative functions based such a representation is not unique and different representations can lead to different ranks of the resulting tensor. Several examples of different of derivative functions for the same tensor given further in the section with experiments and in Appendix. However, it turns out that there are fairly general patterss for derivative functions, and we hope that, based on the examples we give from various applications of the method, it is easy to construct by analogy the desired sequence of derivative functions for particular application problem.
given analytical dependence of the tensor value its indices. Moreover,
As an example, consider step function in the so-called Quantized Tensor Train decomposition (QTT) (Oseledets) 2010 Khoromskij 201I) when the tensor indices are binary is {0, 1} and all together represent binary representation of some integer from the set (0, 1, ...,, 2d_1). The value of the tensor represents the value of some given function defined on this set, with function P equal to the step function P
Pasp in this example:
M11, b2 id)= = Σ )
d-1
00 x 5 t
Psup(() 1xst
(4)
1, x x>t
for the given integer number 0 2d. Let the binary representation of be t = Σ3 ba-
Then the form of the derivative functions for this tensor are depend only on the value by and do not depend the index & itself. This function are the following:
If by 0, then (x)) (*) (0, x) xr,
[² = (1)) (1,
4

---

Published as a conference paper at ICLR 2023
if by = 1, then (x) = y(h) (0, 2) = None, == 0.
:[))== (1)
In our method, the functions / are predefined in the following way. If, in the process of calculating a tensor value, the function ((b) arguments are not in its domain, we assume that it returns an empty value (we denote this value by None as Python language). The next function (f(k-1) or f (k+11)) having received None, returns also None, and so on, up to the "middle" function f(), which returns 0 if at least one of its arguments is None. A detailed explanation with technical details of how such set of derivation functions leads the step function is given in the Appendix.
In this example, the "middle" function is the last function: 1 = d, thus we consider it as function of two arguments. The same is true for other examples in which the "middle" function is the first or last.
Note that in this example, the original analytic representation for the tensor did not assume pairwise interaction the indices. On the contrary, the formula 44) is quite integral: value depends on all variables at once. Nevertheless, the expressions for the derivative function turned out to be simple enough. This situation holds for many examples as well, see Applications and Appendix. Thus, method can find wide application.
is worth noting that the arguments the functions f have different physical meaning. The first argument is the original natural number, it corresponds to index of the tensor under consideration. By contrast, the second argument and the function value itself determine the relation between two indices of the tensor and this relation can be complex. In the general case, middle-function f()) is complex-valued, and the values of all other function (k),, + I, can be of any nature for which comparison operation is defined.
2.3 TT-DECOMPOSITION WITH THE GIVEN DERIVATIVE FUNCTIONS
Theorem 2.1. Let m, be the image of the j-th function f() from the derivative function set for 1 S
j < < ("left" function):
Dj (1 x): 1olssismn ni, I E DD-1, if f is defined at (i, x)}; ==1, 1,,,..., 1-1, 1.
We let Do (0}. Similarly for the "right" functions with 1 Sj
DD = (5 v): 15 i ni, x E DJ+1, if ((++) is defined at (i, x)}, j j=1, 1,,,.... d-1, 1,
where we let Da {0}. Then there exists TT-representation of the tensor K with TT-ranks not greater than
r= Dol = 1, [Di], ...,, Da-1), [aal = =1),
where A denotes the cardinality of a set A.
Proof. The proof is constructive. The construction of the required cores the TT-decomposition takes place in two stages.
We first enumerate elements of all images [ in arbitrary order, such that we can address them by index. Denote [n]n]] the 7ith element of j-th image, ..., [Dy]. Now we can switch from the initial functions with arbitrary values to functions f. the range of each is a consecutive set of natural numbers starting from 1:
(t) x) index of (f (,, ID)),
j = ..., 1, x .... D
(1) x) index_of ((0 (=l) DD). j j=l+ ...., d, x Dytal. (5)
where function index is defined as follows
index.ooroo index_of(y, A) > A[z] for some ordered set and any y E A.
We let index of A) None. Function f()), which corresponds to the "middle"
function ((), is defined as follows fi) v, y) (i, DD- [x], Di(v))-
5

---

Published as a conference paper at ICLR 2023
In the second stage, we assign each integer input and output of new functions {fi} to corresponding
basis vector e The basic idea is to construct the j-th "left" core (j < () of the desired TT-
decomposition corresponding to the function f() according to the following scheme:
if (i, x), then (e(*))TG,(t i, :) = (e(w)),, i= i=,,... ny
(6)
where G; i. :) E R | denotes the matrix representing the i-th slice of j-th core. The elements of this core are constructed explicitly:
1, if y= f0 (i, x)
(, v)
x= .... DD-1l, y y= ..... [Tyl
0,
else
We do the same for the "right" cores which i > I, except that multiplication on the basis vector takes place on the right: if y (i, a), then G (:. i, :)e(*) el3) i i= ..., ny--
Finally, we construct the middle-core G, which corresponds to the function (():
(i, x, v). if f() defined on (i, x. v)
Gi(;, 1,
x x= Di-il, = l..,, [Di].
O,
else
We summarize this two stages in Algorithms 1-2 in Appendix.
Theorem statement follows from this construction: after multiplying m "left" constructed cores, 1 S m < L, starting from the first one, we get the following basis vector: G1 11, :G)(: i2, : )...Gm(f (:: im: :) (e("m))T, where am is defined in (T). A similar basis vector e(*p) is obtained by successive multiplication of all cores, starting from the last one with the index d and up to some p > I with ap defined in (2). Conclusively. the statement of the theorem follows from the relation e( it, :)e(a++)) = K(ii, i2, ..., ia) the elements of the middle-core G, and which corresponds to the relation
which is a consequence of the definition of
Rank reduction One way to reduce the TT-rank in the case when image D; of function ((0 contains too many elements is to partition the image D; into several sets and map the basis vector e, discussed in the second stage of the Theorem, to one of these sets. This possible if the value of the function belongs to a space with given topology. In the simplest case, when the value of the function is real, we can combine into one specified set only those elements from the image of the function for which Jz y| < G, I. y E T3 is satisfied with the given In addition, we can specify maximum number of such sets, thus fixing the maximum rank, increasing the value of c or combining some sets with each other. Other ways of reducing the rank are described in the Appendix.
Complexity The cores, except perhaps the middle-core, obtained by our method are highly sparse. Fach row of the slice G(:, i, :) of the core to the left of the middle-core consists of zeros, except maybe one unit. The same true for the columns of the core to the right of the middle-core. When multiplying slice of core by vector, we consider only those operations which do not involve addition with zero or multiplication by zero or unit.
When using the compressed format, formally we do not need addition and multiplication to obtain a single tensor element, since its calculation is reduced only to choosing the desired slice indices.
Consider TT-tensor G obtained by our method with dimensions {πi, 72, ..., naa and ranks (ro. Tı, ..., ra} with the middle-core at the position I, 1 < I < d. To calculate the convolution of the tensor G and an arbitrary rank-one tensor W of the form
G. W)
Σ
Σ
G1 n1, r1) ... Ga(ra-1, na, 1)w(n1) ... w(na);
(7)
TL. .2... FA-1 NI. 122 .2..... Tdd
where w(n) W(1, n, 1), we need more than Teomy additions and no more than Teooy multiplications with Recenv Σ'=1 nTT;-1 Ei=tt1 n,F; + Pum (fi-17t + min(r:-1, ri)). Indeed, the first two sums in the last expression correspond to successive multiplication of the vector by the current core slice for successive multiplication from each end of the tensor train up to the middle kernel with index I. The last term corresponds to the multiplication of the two resulting vectors by the middle-core (which we assume dense) left and right.
column of the identity matrix of appropriate size.

---

Published as a conference paper at ICLR 2023
3 APPLICATIONS
As a practical application of our method, in this section we give: a) examples from the field of cooperative games, where we compare with existing methods and show our superiority both in execution time and in accuracy (our algorithm gives machine precision); b) the problem of calculating matrix permanent, where our method gives an estimated number of operations only twice as large as the optimized ad hoc method of calculating the permanent using Hamiltonian walks.
3.1
COOPERATIVE GAMES EXAMPLES
Weighted majority
10
Shoes game
Airport
Barkruptty
101
30
Crost
10
Brute force
Br ferce
Cross
105
10
Our
Ou!
10-1
10-1
Stals
15a4
15
23 Number playes
20 Namber (byees 1
22 Number ofpluyers,
20
(e) Weighted majority
Number payers
(a) Shoes game, times
(c) Airport, times
game, times
g Bankruptey, times
Shoes
Weighted
Bankruptey
10
10
10
10-
10-5
10
10-1
10a
10-11
12-3
10-14
10-42
0-31
10-14
10+1
1.5
22
10
15
23
28
20
20
15
(b) Shoes game, accuracy
(d) Airport, accuracy
(f) Weighted majority game, accuracy
(h) Bankruptcy, accuracy
Figure 3: Times in seconds and relative accuracy as functions of number of players for four cooperative games. Brute force-calculating the sum (8) directly, Cross-results from the paper (Ballester-Ripoll 2022).
As example, consider several so-called cooperative games (von Neumann & Morgenstem, 2007]. Omitting the details of the economic formulation of the problem, let us briefly consider its mathematical model. In general, in the theory of cooperative games it is necessary to calculate the following sum over all subsets of the given set T of players
x (k))
Σ ((S)) (k)) v()), for all k T. (CT((K)
(8)
Here p is some function of the number of players in a coalition S. The function of a coalition v is the function of interest, it depends on the game under consideration. This function denotes the gain that a given coalition receives (value of the coalition).
Below we briefly review several cooperative games and compare the performance and accuracy of our algorithm for solving them with the algorithm presented in (Ballester-Ripol]] 2022). which is based the TT-cross approximation method Due to space constraints, brief statement of the problem, the constructed derivative functions and the results of our method. A detailed description of the application of our approach to cooperative games can be found in Appendix. The results of the algorithm comparison are shown in Fig. 3 In all the examples shown in this figure our algorithm produces results with machine accuracy and faster than the one from the cited paper.
give only
WWe use the same setup described in the eited paper for the experiments, and take code from the open source repository https: / / thub. http://bbbblllsteeettggmssse of the author of this paper.

---

Published as a conference paper at ICLR 2023
Shoe sale game, In this game, participants divided into two categories those who sell left boots (indices through L) and those who sell right boots (indices L + 1 through 2L + 1). As shoes can be sold only in pairs, the value of coalition is the minimum of the numbers of "left" and "right" players in a coalition.
Let us build tensors for this game. To find the required value ( in the case of cooperative games, is convenient to construct tensors that have a dimension equal to the number players. Each index of this tensor is binary: 1 means player is member of coalition, 0 means he is not.
To construct the TT decomposition of the tensors p((S)){(S) using our method, let us take the following derivative functions:
f. (z) = -i 1 1 S k f(++11 (z, y+i) = min(z, y)p( 1), i == 0, 1, thus middle-core is placed on the position I == + 1. The derivative functions for constructing the tensor p[[) - (S) are selected in similar way (we let p(-1) = =p(2L + 1) 0). Once the cores for both tensors are constructed, we can calculate the sum (8) for different values of by taking the corresponding slices of the cores by the method described (Ballester-Ripol] 2022) and
performing the convolution.
Airport. not cooperative game in its purest form, as instead of gain we have payoff, but the mathematical essence is in the spirit of cooperative games. Each player represents an aireraft that needs a landing strip of length Ok- Thus, v(S) maxfe; E S). In order construct a TT- representation of the tensor corresponding to this v, let us first order the values of e in descending order. Then the derivative functions are
{ x, x x>0
(x))= =x ff(x)
Ck. x= 1sksd.
However, with these derivative functions the TT-ranks can get very large, especially for non- integer Cg. reduce the ranks, we do the following trick: we break the second function f into two terms,
(x)) (z) (z),
(1)())= = [None,
x,
x x>0
p (2) (
{ 1, x ==
else
[None, clse
After that, we use three derivative functions to build TT-cores, taking the multipliers e out of the build core as shown in Figure 4a This gives us TT-Tucker format with TT-ranks equal to 2 and
0
matrices As with the following elements: A
0 Ck
A
(a) Airport game
(b) Calculating of the permanent
Figure 4: Tensor network for two problems, d = 6. The numbers denote ranks (number of terms in sum). The dashed line shows that at this point the rank is 1, which means that there is no summation and the corresponding cores independent.
Other games. Fig. also shows comparisons with the other two games. In Weighted majority game tensor y has the form v(3) 1 if Eies > M and otherwise for given weights {wx) and threshold M. Bankruptey game, v()) = max(0, E - -igs 4) for the given values {c(} and E. The derivative functions for these problems chosen quite straightforwardly.
3.2 MATRIX CALCULUS: PERMANENT
Consider a task of calculating permanent a matrix {a.z) E Cddd To solve this problem using the presented technique, let construct two tensors in TT-format. The first tensor A will
8

---

Published as a conference paper at ICLR 2023
represent products of matrix A elements in the form: A(i,, i2 .... id) A A4 Asgd- This is rank-1 1 tensor and its cores (H& E Cixdxij ]k=1 are Ha (1, i, 1) Ass. i = ...., d.
The second tensor an indicator tensor for such a set of indices, in which all indices are different
1, if all 81, 12, .... are different,
Mi1 l2, (d) (o else.
The cores G of this tensor obtained using the following derivative functions
(x) { 22, x: 2' =' =0,
1, x &&2' =0 else
&<d; else
f((z)
(0,
None,
0,
where the ampersand sign stands for bitwise AND for integers. In this scheme the middle-core is the last (d-th) core. The k-th bit of the input of the derivative functions corresponds to the i-th value of the set {1, 2, ..., d]: if this bit is zero, then the i-th value of the index has not occurred before, and thus this value is valid for the current index. The function sets this bit in and the value x is passed on. the bit has already been set, the derivative function returns None, since two identical indexes are forbidden.
The permanent value equal to the convolution of tensor and tensor A. Since the tensor A is one- rank tensor, can look at the computation of the permanent weights equal to the corresponding elements the given matrix A, see Fig. 4b
contraction of the tensor I with
After calculating the function f we get number in the binary representation of which there are exactly & bits equal to one. From this one can concludes that the corresponding rank r3 is we can obtain an upper estimate on the total number of operations for the convolution of the given tensor as 2Theamy ~ (2N+1 (2)+ However, one can notice that on average half of the rows in the cores slices consist entirely of zeros, since index repetition is "forbidden": Ge(i, j. :) = O at index corresponds to the x with the j-th bit set.
d! equal r [d-k)IR!' Using relation
Thus, Nhaus = 1 1/2 and after the cores are built, total number of operations Thot (both additions and multiplications) required to obtain the result at these ranks has asymotics Tux = 22 ~ 2 N. This asymptotic is better than the one that can be obtained from the well-known Ryser's 's formula for calculating the permanent:
P(A) = (-1) Eec(1.2.... (-1)18) IT Ejes A.j. When applied head-on, this formula requires O(2
operations. It is that if one uses Hamiltonian walk on (N - c)-u (Gray code) for a more optimal sequence of subset walks, this formula will give asymptotic Thet (2N- which is only twice good ours (Nijenhuis & Wilf, 1978 pp- 220-2240
This is an example of problem where we can first pre-calculate the tensor with conditions and then reuse it with different data tensors A containing elements of a particular matrix.
4 CONCLUSIONS AND FUTURE WORK
We presented an algorithm for constructing the tensor in TT-format in the case when an explicit analytic dependence is given between the indices. The cores of the obtained TT-tensor sparse, which speeds up manipulations with such a tensor. Examples are given in which our method can be used to construct TTTrepresenttaioos of tensors encountered in many applied and theoretical problems. In some problems, our representation yields an answer faster and more accurately than state-of-the-art algorithms. Thus, in the vast majority of cases, we are not faced with trade-off between speed and accuracy.
As a limitation of our method, let us point out the fast growth of the ranks in the case when the derivative functions have large size of their image set. Although we have a rank restriction procedure for this case, as plans for the future we specify an extension of our algorithm to accurately construct a ITTdecomposiiiin for such cases as well, if it is known to be low-ranked.
ACKNOWLEDGEMEENTS
The work was supported by the Analytical center under the RF Government (subsidy agreement 000000D730311 Grant No. 70-2021-00145 02.11..025 1..221..

---

Published as a conference paper at ICLR 2023
REFERENCES
Titu Andreescu and Zuming Feng. 102 combinatorial problems. Birkhauser Boston, Secaucus, NJ, 2003 edition, October 2002.
Rafael Ballester-Ripoll. Tensor approximation of cooperative games and their semivalues. International Journal of Approximate Reasoning, 142:94 2022. ISSN 0888-613X. doi: http://o...rr11100011......aa.10 sci
URL https: wwwp://wwwww....om www.ncedireecttt.ccceeeceeeeeeee se com/
Yatao Bian, Yu Rong. Tingyang Xu, Jiaxiang Wu, Andreas Krause, and Junzhou Huang. Energy-
based learning for cooperative games, with applications to valuation problems machine learning. In International Conference Learning Representations, 2022. URL https:
Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo P. Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part I low-rank tensor decompositions. Foundations and Trends@ in Machine Learning, 94-5):249-429, 2016. doi:
10.1561/2200000059,
Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, Masashi Sugiyama, and Danilo P. Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part 2 applications and future perspectives. Foundations and Trends@ in Machine Learning, 9(6):249 429, 2017. doi: 10.1561/2200000067. URL https: //c:i////cc..../// http//cco..orr/////
22C0000067
Sergey Dolgov and Boris Khoromskij. Two-level -uc-er format for optimized tensor calculus. SIAM Journal on Matrix Analysis and Applicattions 34(2):593 623, January 2013. doi: 10.1137/ 120882597. httt:p::/bba..orr/11111///////// 11t.:///0......000000.03
Jicong Fan. Multimmde deep matrix and tensor factorization. In International Conference on Learning Representations, 2022. URL https::/ ew net. forum? ?
6YVIKOSAKF
Kazu Ghalamkari and Mahito Sugiyama. Fast tucker rank reduction for non-negative tensors using mean-field approximation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, ngs neurips. cc/ 6d7 ott.a/e............00.332235-3-.
pp. 443-454. Curran Associates, Inc., 2021. URL papp://02.1/E1ee/000a3333332
Lars Grasedyck, Daniel Kressner, and Christine Tobler. literature survey of low-rank tensor approximation techniques. GAMM-Mintellungenn MtMMMMMMMiielaageee...005-5----- 36(1):53-78, August 2013, doi: 10.1002/gamm. 201310004. http/::ss////ii.... /tt.///0..org..///// 1002 gamm. 201310004]
Sebastian Holtz, Thorsten Rohwedder, and Reinhold Schneider. The alternating linear scheme for tensor optimization in the tensor train format. SIAM Journal on Scientific Computing, 34(2); A683-A713, January 2012. doi: 10.1137/10081 URL htttps://// http:://dccooo/o///o... 1137/ 10C8188931
Behnoush Khavari and Guillaume Rabusseau. Lower and upper bounds the pscudo-dimension of tensor network models. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 10931-10943. Curran Associates, Inc., 2021. Wttphttpss://poooeeeeeeee neerrisss.. Paper.
cc ot//apeer/0022/ilee//88888bbb3b3
Boris N Khoromskij. Od -u-quantics approximation of N-d tensors in high-dimensional numerical modeling. Constructive Approximation, 3422:257-2888 2011.
Boris N. Khoromskij. Tensor Numerical Methods in Scientific Computing. De Gruyter, June 2018. doi: 10. 10.1515/97831 10365917. U...tttpe::/doo..org/11....1111.
10

---

Published as a conference paper at ICLR 2023
Joe Kileel, Timo Klock, and João M Pereira. Landscape analysis of an improved power method for tensor decomposition. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 6253-6265. Curran Associates, Inc., 2021. URL. httpttts//pproceeeeeneaaaea neur ps. cc cc/paper/
2021/F11e/31784Bffo hrt.://444.......00000o0eeee63a3
Timothée Lacroix, Guillaume Obozinski, and Nicolas Usunier. Tensor decompositions for temporal knowledge base completion. In International Conference on Learning Representations, 2020.
URL /ttt:s::/ppeereviieeee
net/ ftr//oormmtt Seee//ooruidddrrk22222 id=rke2P1BFvs
Linjian Ma and Edgar Solomonik. Fast and accurate randomized algorithms for low-rank tensor decompositions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances Neural Information Processing Systems, volume 34, pp. 24299- 24312. Curran Associates, Inc., 2021. URL
neuri cc/
Albert Nijenhuis and Herbert S. Wilf. Combinatorial Algorithms. Elsevier, 1978. doi: 10.1016/
-2013-0-11243-3, URL
V. Oseledets. Approximation of 24 x 2 matrices using tensor decomposition. SIAM Journal on Matrix Analysis and Applications, 31(4):113-21155 January 2010. doi: 10. 10/1137/090757861. URL
V. Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295
2317, January 2011.
I. V. Oseledets. Constructive representation of functions in low-rank tensor formats. Constructive Approximation, 37(1);1-18, December 2012. doi: 10. 10.1007/500365-022-97755 URL https: //doi. arooi.org/000 10. 1007/=00355-01--310
I. V. Oseledets and S. V. Dolgov. Solution lincar systems and matrix inversion the TT- format. SIAM Journal Scientific Computing, 34(5):22188-A273,, January 2012. doi:
108333 142. URL.ttps. LLL.ttpp.//6...rr//001/////00000
Ivan Oseledets and Eugene Tyrtyshnikov. TT-cross approximation for multidimensional arrays. Linear Algebra and its Applications, 432(1):70-88, January 2010.
Lorenz Richter, Leon Sallandt, and Nikolas Nüsken. Solving high-dimensional parabolic pdes using the tensor train format. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8998-9009. PMLR, 18-24 Jul 2021. URL https::/proceetee
mmr.
pzess/s139/richter22.a. html
Michael Steinlechner. Riemannian optimization for high-dimensional tensor completion. SIAM Journal Scientific Computing, 38(5):8461-S48) January 2016. doi: 10.1137/15m1105066
URL http:: //tp:.//o...o//.oo wtt.///..11///110..111
John von Neumann and Oskar Morgenstemn Theory of Games and Economic Behavior (60th
Anniversary Commemorative Edition). Princeton University Press, December 2007. doi:
15.1515/978 4008894600 URI.https: //doi 0100

---

Published as a conference paper at ICLR 2023
APPENDICES
A ALGORITHMS
Algorithms T22 summarize the constructive construction of TT-decomposition cores, which is described in Theorem 2.1 Here, the function order orders the set in any way, dom denotes the domain a function. If a function returns None on some set of its arguments, then we assume that it is not defined that set.
OTHER APPLICATIONS
The examples in this section fall into two (possibly intersecting) broad types. The first of them contains the calculation of the exact value of some quantity for which the TT decomposition of the tensor arising in the problem is needed. In this case, we do not perform a TT tensor rounding (except when we reduce the rank using SVD decomposition with zero threshold, but we assume that after that the tensor value remains the same within machine accuracy). From technical point of view, usually the convolution operations (or other similar operations) are performed without explicitly constructing the cores TT-decomposition completely in computer memory. Instead, use the functions obtained after applying the AlgorithmiI directly as arrays of their values. This is equivalent working with matrices in a compressed format.
The second type of application consists of problems in which rounding with a given accuracy is the advantage of the tensor approach- we get the answer with a certain error, but faster.
B. SIMPLE (MODEL) EXAMPLES
Sum Consider the following tensor S, which is some function P of the sum of the elements of the given vectors a1, a2 ... ad:
Iii. i2, ia) P(ai [i1) a2( +... a. (ia))
We can easily build its TT-representation using the presented technique if we put the derivative functions equal to
The view of these functions is the same for all cores except for the middle-core. The middle-core stand in any place in this case, but makes sense to put it in the middle of the tensor train (at the position [d + 1) to reduce the TT-ranks. For the middle-core on the m-th place the derivative functions equal
(T, (z. P(x + (m)
In the simple case, when the vector elements are consecutive numbers from zero given number: a, = {0, 1, ..... b.). we have a natural correspondence between the value of the function y and the basis vector (T) representing it:
(1+1)
Thus, for example, the third slice (of any of first m - cores) corresponding to the addition of number 2 will be of the form
0
0
0
0
0
0
0
0
0
G(: 3,
0
0
0
0
0
0
0
12

---

Published as a conference paper at ICLR 2023
Algorithm 1 Construction of the integer-valued functions based on the given complex-valued functions
Require:
Middle-index I, set of functions { of two variables (function (() have
arguments)
Ensure: Functions
(
1: # Initialization
2: nı = maximum of the domain of the function f(b) on first variable for ..... (dimensions of the resulting tensor)
3: Part Finding the function outputs R of each function. is a list of arrays.
4: R[[] < {0}, R[d]] f- {0}
5: for to do
6: R(i] order( (K, r):
n4y x E Ríi 1]})
7: end for
8: for d / step 11 do
9: R[i] order( f (k, r): k= ..... na, E R 1]})
10: end for
11: # Part II. Defining new functions
12: # From the left
do 14: for j to do
for i 1
for in Ríi 1] do if defined (k) then
16:
17:
I index index_of(k; Rii 1])
18:
y + index_of( (f (f (j. k). R(())
f (a):=
20:
end if
21:
end for
end for
23: end for
From the right
25: for i = d to 1 + step -o
26:
for j = 1 to n, do
27:
for A in R[j] do
28:
defined f3 (k) then r + index of,k, R(i))
29:
30:
y 4- indiin_ooo if (f) (G. k), Rli 1))
8 (x) =
31:
32:
end if
end for
34: end for
35: end for
36: # Middle-index function
37: for j = to n, do
38:
for h; in R( 1], 12 in R[] do
39:
if defined (() k1, k2) then
40:
(ilex_of(k,, (k,, Rl 1 1)) 22 + index_oofo 122, R(()
+- index_of
41:
(()) (x x2) = (() k1, k2)
42:
43:
end if
end for
45:
end for
Return functions ) (optionally) outputs R.
13

---

Published as a conference paper at ICLR 2023
Algorithm 2 Explicit construction of the cores of the functional tensor
Require: Middle-index I, set of integer- valued functions have arguments)
{ of one variable (function {
Ensure: Cores GT. ..., Ga of TT-decomposition of the functional tensor
1: # Initialization
2: ni = maximum of the index j value of the function 17.) for k: = ...., d
3: # From head
4: for to do
5: G: <- zeros( maxx sup f) n4, max fj (x))
j.
6: for j to do #Build each slice of the core as in (6)
for in dom f/ do
7:
8:
(r, J. (x))
(z))
9: end for
10: end for
end for
step -1 do 12: # From tail
to 1. 14: G. f zeros max f (x), nss map(smm )
for
15: for to n. do
for in dom f( do
(z), x) +
end for 19: end for
end for
21: # Build middle-index core
22: G + zeros max (xxx((x11))))) (x1, x2)
dom {(0))) my max max (( (x1, x2)
E
dom 1)) 23: for = to do
24: for (x1, x2) in dom f10) do
25:
Gx), 222) f/ (x1, x2)
26: end for
27:
end for
28:
Return cores G1, G
This matrix can be written in block form
0, O2 O₂5
G 3,
where O₁, O2 and O3 are zero matrices, and / is the identity matrix. If the result of the calculation of the previous function is 3, which corresponds to the vector (e(4))T the result of multiplication of
all previous kernels, then after multiplying by the slice data we obtain (e (e(4) T 3, :).
The basis vector (T) expectedly corresponds to the value of the function equal to 5.
But in the more complex case, the correspondence between the function value and its vector representation may not be obvious. Consider the following first two vectors
a = (1, 2, 10), a2 = {-1, 0, 5, 8}.
Then the second slice of the second core G (i, 2, :) which generated by the function f(x) I+0, is equal to
0
1
0
0
0
0
0
0
Gz(; 2,
0
1
0
0
0
0
0
0
0
0
0
0
14

---

Published as a conference paper at ICLR 2023
This is true because the first derivative function has three values, which correspond to the first three basis vectors:
1 e!!) 2 2
e(3)
whereas the value area of the second derivative function has elements, which correspond
0 0 e(!) 1 - e + el0)
10 = e 15 + e0)) 18 + e
Note that the examples above we chose to assign basis vectors to the values of the derived functions according to their their ascending sorting. This is not crucial point, since this correspondence is conditional, it can change and be different for each core.
In the degenerate case, when the function P is identical: P(æ) I we construct the desired TT- decomposition with ranks equal to 2. Namely, in this case the cores have the following explicit form
(1
a [1]
0.d
G i, :) = (1, ai l)); Ga(;, i, i)
d 1; Ga(;, i,
These cores can be constructed using our techniques as follows. Consider the following tensor with binary indices i& {0, 1} which is equal to 1 iff only one of its indices 1:
1,
1(11 82, .... id)
km
0,
else
We can construct its cores G using the following derivative functions
1, x =0 0,
(x) = f1 None, else.
And consider one-rank tensor H with values be summed up with the following cores (1 0, :) - (1), KR(;, 1, (vx).
For this tensor it is true that
H(O, 0, .... O, 1, 0, .... 0) uk
h-1
thus its convolution with the tensor gives the sum of elements of u:
ΣΣ
Min, i2, H(1,, i2, 1a)
Uk-
(10)
i f-=0
This convolution operation is shown schematically in Fig. 5a
82
na
nG
G
G.
6.
G.
G.
G.
(a) Representation of the
100
Ck {1, vk
(b) Obtaining G via the operation 111
Figure 5: Tensor network for TT-tensor for simple sum for d = 5.
Now, be able select the terms by choosing the indices of the tensor G, we replace the vectors in this network with matrices C₁ of the following form
1
1
C
2k [2]
ux [3]
2k (n2g - 1] u% [nE]
15

---

Published as a conference paper at ICLR 2023
where ng is the length of the vector ag- Finally, obtain the cores Gj: by the convolution of the cores G3 and the matrices Cj (see Fig. 5b):
Ga(; 1,
Σ G(: J. C, 8). j=0
(11)
Step function in QTT format The definition of step function in QTT format and its derivative functions are given in Section 2 Let us consider more detail how these functions give the desired value of the tensor built on them.
Further, we assume that the number appearing in the definition the step function constant, and that the multi-index {i1, i2, .... id} we choose to obtain particular tensor value may be different. Recall, that t has the following bit decomposition
t
b 2/.
Multi-index {úr, i2, ..., ia} have the meaning of bit decomposition of the argument æ of the step function
x
Thus, if x S t then the tensor must return 0, otherwise its value is equal to 1.
Recall, that in this example derivative functions are the following:
If by = O, then fot (z)) = (()) (0, x) = x,,
[+ = (1) x) =
1, x =
if by 1, then (x) = ((() x)) None, == 0.
(+)) = (1)) x)
Assume, that for some kt 115 S k < d all bit in the numbers of /. and x before this index are coincide:
by ij. 1 15 < k
and their k-th bits are different.
As the first case consider the case when by but 4 1. means that and the value of the tensor must be I: I 1, regardless of the correlation between subsequent bits, as they correspond the lower bits. Let's trace what values the derivative functions receives input and outputs to get the value of at the end. For bits with indices less than k, the derivative functions are equal to the identity function. Indeed, for some S j < k, by O, it means, that iz and derivative function corresponding to this sequence member is taken from the first line of the definition above:
(0) x) = I. If for some 1 < j < k, by = 1, then derivative function corresponding to this sequence member is taken from the second line of the definition above: f (1, x) = Thus, the k-th derivative function receives as input the initial value that is fed the input of the very first function and in this case this value is not essential. The k-th derivative function, in turn, returns according to its definition in the first line of the expression with definitions of f: f (A) x) 1. This value will be "carried" to the end without change as for all derivative functions in this example equality f(1) = holds. gives the resulting value 1 of the TT-tenor.. So we have achieved the expected behaviour in this case.
If, on the contrary, by 1 and is = 0 then we surely know that = P(z) = as x < in this case. As discussed in the previous case, the k-th derivative function receives initial value as input. In this case is important that this value is equal to O. The k-th derivative function is undefined at this value of the argument, which we symbolically write as f( 0) None. All derivative functions are pre-defined in such a way that they always return None if they are not an middle-functien and the middle-function returns 0 if it has least one argument that is None. In our example, the middle-function is the last (d-th) function, and therefore has two arguments. Thus, the None value will be "carry on" until the last function, which will return In the language of
16

---

Published as a conference paper at ICLR 2023
vectors, this means that after multiplication by the k-th core we get zero vector, not a basis vector, so that for any subsequent values of the indices the result will be zero. So we have achieved the expected behaviour in this case too.
In the remaining case when bj ig for all 1 S j I d, the derivative functions leave the initial argument unchanged. This argument is O. Thus, the constructed TT-tensor have the expected value in this case as well.
The maximum TT-rank value in this example is no more than 2. For the of rank equal to 2, the explicit form of the cores are the following, for by- = 0:
(x 0, (
:) Ga(: (:. 1, =
1
by = 0,
1
1
and for by =
0
1) 1
0)
0 9)
G1 0,
G. (1, 1, =
by = 1.
0
By direct calculations it can be seen that if we assign to number 0 the basis vector (2)) {1, 0}, and to number the basis vector e(2) = {0. 1), then multiplication of these vectors by the prescribed matrices gives exactly the same results as the application of derivative functions for this example.
B.2 COOPERATIVE GAMES
In this subsection, we take a closer look at the examples that were briefly given in Section 3.1 and we also give some more examples of applying our methods to cooperative games, which are described in (Ballester-Ripol 2022).
Shoe sale game Brief game conditions and the derivative functions for this game are described in general form above. Consider what happens when certain number k is given, i.e. the order number of the player for whom we calculate the payoff π (Re).. For each i: we rebuild tensors p((S))v(SU
and p( (S). At the k-th place we leave only one function of the two: f(A) for the first specified tensor, and f(()) for the second. Thus, although we formally have a tensor of dimension d, there actually no summation at the k-th index, and we obtain a sum over all subsets of the set T T [k). In addition, in the case of the tensor (((S)))(S U (k+)), we subtract a unit from the argument p since in this case p (S))v(S U {K)) p(S U [A}] ()2(S U {k}).
When we go through the computational tree of Figure 2a using the derivative functions of this example, we have the following. Let A: >>> L + 1 and multi-idex {11, i2, .... fd} has the meaning given in the main article: if any index i, equals 1, it means that the player with number j is part of the coalition, if O, he is not. When we go from the left end, each derivative function adds 1 to its argument if the corresponding index is 1. If the corresponding player is not part of the coalition, the corresponding index is and the derivative function returns the argument unchanged. The "left" functions thus count the number of players in the coalition.
When passing from the right end the same happens, the number of players with numbers greater than L + 1 ("right players" in terms of this cooperative game) is counted, except for the player with the number This player is always counted when we build cores for the tensor (((S))v(S U (k)) and is not counted is the case of tensor ((())))(()) as explained above.
Thus the middle-function with index + 1 gets two arguments: z-ehe sum the number of "left" players and the sum of the number of "right" players, excluding the player with the number L+1.
The diddle-function adds one to y if index i++1 is 1, and does not change it otherwise. Finally, the ceddle--functio returns min(z, y)p(r + 3) which coincides with the expected value of the tensor.
At the next step we contract each tensor with ones, namely, we calculate the following expression
m2
Σ
GI in,
Σ
Gz(:, iz, :) :))
Σ
Gali, ia. 1)
(12)
17

---

Published as a conference paper at ICLR 2023
from left to right in sequence. In the case of this example, all n, 2. 1, .... d. Thus we build
and contract 2N = 4L+2 2 tensors, but since we do not build full cores in memory and instead work in compressed format, get the computation times shown in Fig. 3a
Airport Brief game conditions and the derivative functions for this game are described in general form above.
In this problem we once explicitly build the cores for the tensor v, making a convolution with matrices Ag (see Fig. 4aa. This convolution in fact, is reduced to the replacement of the Separately. we construct the cores for
corresponding unit in the core slice by the value of the tensor p. which the given function of the sum of all indices equal 1. The construction of such tensor is described at the beginning of Sec. B.1 in this case we put ay(0) 0, a = 1, j 1, .......,,. d.
To calculate the value of x(k), we applied trick similar to the one used in (Ballester- 2022
Namely, for each we have left the core G from the TT-decomposition the tensor p only the first slice of dimensionality, which corresponds to the index in 0, so the following is true for (p)
the new core G
G b/ 0,
0,
6 ( (: 0,
(p) G xIxe""""
For the core G from the TT-decomposition of the tensor y we also removed the second slice and took the slice difference of the original core the first slice:
(v) k :) _ (c, 1, G (:, O, :),
(v)
IR
For the final result, we have taken convolution of these tensors, which TT-format is written as
2
T(k)- =
Σ G p i1 :) s G (1, (1,
Σ
( (3, i2, :) s G (c, 12, (2):))
1==1
G (:, ids 1) G id, 1))
G (: 1, G 2 1):).....
Σ
where @ denotes the Kronecker product of matrices.
For the numerical experiments we take values Cg as i.i.d. random values uniformly distributed on the interval [0, 1].
Weighted majority game For this game, briefly described in Section 3.1 we took the following
derivative functions for the tensor p(()))((SUU (k+) vS)) of dimension d [T] 1:
{ [x|[]] - Wy, x [|2 + 1},
x|1] + w S M, else
fx(x)= = A(x)
15 < k.
None,
[1(=== = ((x)) { [x|1] + wf+1, x x + 1},
x|1] + w S M, clse
k k <d,
None, and for the middle-function, which is the last one in this example, we have
(x { [p(x[2)+1) +), xx[1] + ima41 + wk 2 M x[1] + ima41,
i= 0, 1.
None,
else
(In the case of k [T| d + we take wa instead of ws41). Note that in this example the derivative functions are defined on a set of vectors of length 2. The first component accumulates
this vector of weights {w,} } to compare with the threshold M. The second component of the input vector counts the number of players in the coalition S, this value is passed to the function in the last derivative function.
at step j. j < d it turns out that the accumulated sum of weights already exceeds the threshold M (x:11 wy > M) then the derivative function returns None, thus zeroing out the value of the tensor.
18

---

Published as a conference paper at ICLR 2023
v())) will be obviously equal regardless of Indeed, in this case, the difference v/S U [k)) what other coalition members are added, i.c. regardless of i, >>>>>> j index values. This trick reduces the TT-ranks of the resulting tensors and thus reduces the execution time.
In this example, we construct the cores of the specified tensor N = |T] times, and then perform its convolution by the formula (12) in the sparse format. For the numerical experiments take values {wr} } as i.i.d. random integers uniformly distributed on the interval [1, 10) and take threshold equal M L1 wx. 1.
Technically, we can avoid passing vectors to the deriving functions, but limit ourselves to an integer argument X equal to X x[1] N where Nbig is sufficiently large integer
(Nbig 2). Then in each derivative function we produce "unpacking" x=1] = X mod Noig and [2 = [/
Bankruptey This game has a function of max on the sum of the values, so is mathematically similar to the airport game, but we have chosen different way of constructing derivative functions. Namely, we take
[(x11] { Cina(i), x|2]}, x[1] - (ada(() > O, A(x) = [x[1], x12]+11,, isj<d None,
else
where (odu(1) cli] if < and Cadu (i) = cli + 1). else. For the middle function, which is the last one (1 = d N 1), we have:
[0(x)) [x[1] - Cadd - max(0, x[1] - Cadi - c(x2))
x|1| aadd >> O,
0,
else
where Cadd
cld + 1] if k < d + 1, and Cadd cld if d +
ff(x) = (x|11] - max(0, x - c(+ +
Note that in the case of this example, the initial functions f1 are given the value (E, 0} as input instead of O. This is done to simplify the type derivative functions. Like in Weighted majority game, derivative functions take input a vector of 2 elements, the first of which accumulates the values of {cy}. J. and the second element summarizes the number of players in a coalition.
In this example, we construct the cores of the specified tensor N |T] times. and then perform its convolution by the formula (12) in the sparse format. For the numerical experiments we take values {cx) } as i.i.d. random integers uniformly distributed on the interval [1, 10) and take the value of E equal to E = Ex Ck-
One seller market game In this game, first player in selling some good, players 2, .... |T| offer prices {az, ......, ] for this good, a 0. If the first player is in coalition S, the value of this coalition is equal to the maximum price offered by the members of this coalition
(S) = max ag. kES, k#1
If there is no first player in the coalition, its price is zero: (S) 0. For the first player we take the following derivative functions
(x) None, f(x)) 0,
and for the rest of the players:
(x) = }((x) = max(x, ox).
The problem under consideration is another example of such tensor construction, the ranks of which depend the order of the indices. For an unsuccessful sequence, the TT-ranks of the resulting tensor can be large and it is necessary to perform an SVD-step for reducing the Ta-knss. The final ranks depend specific values of {at).
19

---

Published as a conference paper at ICLR 2023
To reduce the ranks, of the sum ( Namely, place the first player first, and sort the other players according to their pre- determined prices in descending order. With this sorting we can take the same derivative function for k > as Airport game.
change the sequence of players, it will not affect the calculation
Thus, in this problem come the tensor network shown in Fig- with matrices A of the same kind as the matrices in the airport problem with the following elements
Ab
Ax
Figure 6: Tensor network for building TT-tensor for the one seller market game with optimal players
ordering for |T] = 6. The numbers near lines denote ranks (number of terms in sum).
100 0
1
0
A
2, ...., [T]-
ak
Technically, the convolution procedure can omitted explicitly, taking it into account at the stage of tensor construction.
Note that since the cores G the resulting TT-tensor are constructed using the same pattern as well as the cores of the tensor representing values of they can be built the fly rather than stored when calculating the sum (8) Moreover, we can abandon the construction of the cores at all, immediately producing all algebraic operations, given the special (sparse) kind of kernels. For the considered problem, the sequence of matrix operations to calculate the sum (8) is reduced to the Algorithm
Algorithm Algorithm for calculating the sum f)rr one seller market game, based on obtained TT-cores
Require: Values {a:} sorted in descending order, number k, weight function P
Ensure: Value of T
1: v {0. 0. 0) Initialization
2T
2:
w/0
4] < {0. 1) & (1, 0}
3:
for to (T] 2 do
4:
i == 7: then
5:
for j i to 0 step - do
6:
v22 +
0:+1 x[2]]
7:
v v|2i] +- [22j
8:
end for
9:
else
10:
for
j = i step -
11:
3 + 2j + +| v/3 + 2j + a.41 -//2) + v + 1]
12:
end for
13: end if
14: end for
15: +--0 0
16: for
-rri= = [T] do s 11)ap
18:
s- + +(i+ 1))
19: end for
20: 8+ +
21: Return 8
20

---

Published as a conference paper at ICLR 2023
This algorithm works only for 1 < k [T] and it is not the most efficient. However, it is shown to illustrate the possibility of applying the technique described in the article to build this kind of efficient iterative algorithms. worth noting that the complexity of this algorithm is O((T)).
B.3 KNAPSACK PROBLEM
Consider knapsack problem. The formulation is the following: we have n type of items, each item have weight 0 and value 2 0, i
2, ..... The task is to solve optimization problem
maximize [2), com Fnd
U s.t.
W S W
where {a;}== are the unknown number of each item, value W I the given maximum total weight. By imposing different constraints on the unknowns Zi, we obtain different formulations of the problem.
0-1 knapsack problem First, consider formulation in which it is assumed that x; {0, 1} (so called 0-/ knapsack problem). To solve this problem, we construct two tensors. First tensor represent the total cost of the knapsack
d
V T2, Ln.
0,
Since the expression on the right side of this definition is linear, this tensor can be represented in TT- format with TT-ranks of no more than (see ()) Namely, the cores (H₂) of the TT-decomposition of the tensor V are
0
(: 0, (1,0);
Hk(: 0, :) =
2 k < 1;
Ha(:, 0,
H1(: 1, (1, vi); Ha(: 1, :)
1
2k
2 2 k: <d Ha(: 1,:)
Vd
Here we use indices 0 and 1 for the middle indices of the TT-cores so that they correspond to the physical sense of the task-the presence or absence of this item the knapsack.
The second tensor is the indicator tensor of the condition in the knapsack problem:
1. if
w S W
[a,, 02, In)
0, else.
We can build functional IT-dccomposition of the tensor I with the following set of functions
fx(x) = { iu(k),
iu[kk] < W,
i= 0, 1; 1sksd
None,
else
Note that the condition of not exceeding the weight is checked in each function, i. e., the conditions for partial sums are checked: w1.1 < W. w131 + W242 S W, etc. This does affect the final result as 2 0, but it allows us to reduce the ranks of the cores. The TT-ranks in this problem are highly dependent on the specific weights of the knapsack elements: whether they are integer, how large range of values they have, etc.
The final answer to the knapsack problem is given by finding the maximum of the tensor, which the elementwise product of the constructed tensors
arg (ai, 22, }
V(r1, 32, ..., In)) 1(11, I2, ..., Tn).
The TT-cores of such tensor are found as the Kronecker product of the slices of the multiplier cores (see (Oseledets] 201T)). The operation of approximate finding the maximum value of the tensor in 'T--frmmat is implemented, for example, in the package ttpy.
21

---

Published as a conference paper at ICLR 2023
Multi- multi-Dimmensonal bounded knapsack problem Another addition, which can be implemented with slight modifications of the above scheme, related to the presence of several constraints. Namely, let there be several weights {w, associated with each item, with separate conditions imposed on them
Σ
Σ
( w 24 S WG), j j=1, 1,..... M; 0, I...N,, N₁,
maximize
s.t.
1x1, 322
1=1
where M is the length of condition vector.
To solve this problem, we generate indicator tensors {M6) 1j=1= one for each condition, according to the algorithm above. The we find element-wise product of all this tensors, and find (quasi-) maximum element in the resulting tensor
M arg max V(ø1, 22, Ind II f=1
1 (I1, 22. ..... Zn)
{ dag. 2nd
The product of a large number of tensors (0] can lead to a rapid growth of ranks, to get around this round the tensor after each successive multiplication.
B.4 PARTITION PROBLEM
Consider the partition problem in the following formulation. We have multiset 8, [8] = d of positive integers (multiset a set with possibly repeating elements) and an integer n. The task is to partition the set 8 on n sets (S; Jm such that the sum of elements in each set are equal:
Σ a aES;
Σ a aES2
Σ a BES.
a
aES
In order to use our approach solve this problem, we construct n indicator tensors, each of which corresponds to one of the equalities in the expression above. Namely, the j-th tensor is defined as
1, if Σ s[k]
8(is, j) = T,
1y,,,, i2, .... id)
k=1
0, else
where s[k] is the k-th element of the (ordered some way) set is the Dirac delta function and T = E.Es
The maximum indices value of this tensor n. The index value i means that the k-th element of the set S belongs to the set Sy. Thus have one-to-one correspondence between indices set (ii, i2. ia} and a partition of the set
Derivative functions for the j-th tensor the following
(x) x + s[k], if
1sk<d, 1sisn,
x, else
and the middle function which is the last one:
1, if x + s = T and = j,
(x)
if r = 7 and + j., 15isn. 1, else
0,
Finally construct indicator tensor as a Hadamard product of the built tensors
l +
In-
The value of this tensor is 1 only for the indices corresponding the desired problem statement. We can find them by finding the maximal element of the indicator TT-tensor, see Section D in the Appendix.
22

---

Published as a conference paper at ICLR 2023
def f(x, 1): last =
if (x[il) > 0 or
(x[i + N]] > 0 or \
(x[i + 2+N]) > 0:
return None
if last: # middle-core
return
add our position
to all sets
x x[i] =1
x[i + N] =
x[i 2+N]
shift contom-to-tee set
[NN: [[N+1:24N] x[2+N-1] =
shift top top-to- sos-to-borie bottom -oottoo set
[[3*N+1:3<N] = N[=+N:3+N11
x[[+N] =0
return
(a) derivative functions Python
(b) Positions for N 9 10.
Figure 7: Eight queens puzzle
B.5 EIGHT QUEENS PUZZLE
Consider the classical problem of eight queens and its extensions. In the classical variant it is necessary to place queens on a usual 8 8 chessboard so that the queens do not beat each other. In other words, problem on an x N board with queens. To solve this problem by our techniques we construct tensor of dimension N, each k-th index ig of which denote the position of the queen the k-th vertical, so 1 < i < N. The value of the tensor is an indicator function of the desired state: 1 if the location of the queens satisties the condition and zero otherwise.
queens stand on the same vertical, horizontal, diagonal. We will consider this
The derivative functions (x) in Python for such a tensor are shown in Fig. 7a The are the same for all k middle-core is the last core, the above code also covers the function for the last
Let us briefly describe their work. The input is not a single number, but an array (it is allowed in our scheme) zeros and ones. The first N bits show the position of the previous (leftmost) queens horizontally. The bit corresponding to the current queen is added to them. The next N bits show those fields which are broken from bottom to top, and they are shifted forward. And finally, the last series of N bits shows those fields that are broken from top to bottom, and they are shifted back. position
the bit corresponding to the position of current queen contains a one in at least one of the sets, the producing function returns None, since it means that the condition has already been violated.
After constructing the tensor, a non-zero element in the tensor (in this case the value 1), and its algorithm described in the Appendix, Section D The result is shown Fig. 7bl
find the desired position: this problem is reduced to finding
Note that although the state that is passed to each derivative function is 3NN in length and thus can potentially take 2aN combinations, the real TT-rank much smaller, since only small fraction of this set of combinations admissible. See Table for the numerical values for the ranks together with the error in calculating the total number of combinations
23

---

Published as a conference paper at ICLR 2023
N and threshold
truncation
TT-ranks
# of positions
truncation
42
12--2200-0000 339
538
482
224
8, c
1 8-36 62
74
62
36 8-1
92.0 22.02.. 10
8, c 10
1 12-33-62--4--1
8 8-1
92.0 12.00... 0.0
9, w/o truncation
- 1-
1-9
352
1 1 119------21--22--1--19------
352.0
c 10-6
1 9----4--- 172 246
246
172 54 9-1
352.0=4-10-
10, w/o truncation
1-10
1393 120 8838 6426 2576
724
10, 0
1 1-00--72--300-1--------0-000
724.0 5-10-
10. 10
1-10-72 284 60044-52666663330 526 284-222222-22222288-221122111112 70-1--221111
724.0 + 0.0
Table I: TT-ranks and the number of positions calculated using the tensor depending the size of the boar N and the truncation threshold r.
Of course, solving the problem of finding permissible combinations in the described way is inefficient. But of them. This number is obtained by convolution the tensor with vectors consisting of ones. Besides, by constructing cores of decomposition, we solve extended problems. For example, the complement problem, when some of the queens are already placed on the board, and we need find the location of the others. Or can consider that queens are placed on the board randomly, with a given probability distribution law, and the problem is to find the probability that such an arrangement will result in the position given by the puzzle rules.
faster than finding one get the number of possible combinations
B.6 COMBINATORIAL PROBLEMS
Sawtooth sequence Sawtooth sequence is a sequence of integer numbers {a1, aa) such that 0;-1 < a, then o; 0;-1, and vice versa.
Suppose we have set of arrays { and for a given set of indices in, f2, ia we want to construct an indicator tensor equal to if the corresponding sequence {ci(d)), c2(iz], ..., calia]} is sawtooth.
In this example, the derivative functions receive as input a sequence of two elements, the first element contains the value of the previous member of the sequence, and the second denotes the direction, "up" or "down".
(c<li), "up"). if ex [i] < x[1] and w[2] "down" (x) = fexll,, "down"], if cx(i] x[1] and x22] "up"
None, else
Middle function is the last one and it is of the same form. We need to slightly alter this definition for the first function for l
Such sequences are often found in game problems. We can combine this indicator tensor with other conditions. For example, we can find the number of possible tooth sequences with certain conditions through convolution of the resulting tensor with units.
Number of subsets Consider Problem #10 from the Advanced problems chapter of the book (Andreescu Feng 2002): Find the numbers of subsets (l...., 2000), the sum of whose
elements is divisible by 5.
We can immediately construct an indicator tensor with binary indices, which equals the given subset (of indices with value 1) satisfies the condition of the problem. Namely, let us take the following derivative functions
f!(x)) (x ik) mod 5, 1 1 k: <d, d, i= 0,
24

---

Published as a conference paper at ICLR 2023
and the middle function which is the last one in this example as
1, if (x ik) mod 5 = 0
(x)
0, else
However, for the specified number elements of the sequence (2000), it can be a time-consuming task to convolve such tensor even in sparse format. Therefore, let try to solve this problem analytically, using the explicit representation of the cores of this tensor.
Note that for the product of any five cores of this tensor, starting from the number that gives 1 when divided by 5, it is true
Σ
2
(s lan+1; :)
Σ
Gsn+2(;, dsn+2, :) :))
Σ
2
Gan+a(: don+3: :)
x
Fom m
Fon 12m1
8
6
6
8
6
6
6
X
Gin44(i 85n44; :)
Σ ism16=1
Gan+5(i isn45.
6
6
14=1
6
6
8
6
Thus, to solve the problem it is necessary to power this matrix to 2000/5=400. To do this, let us write this symmetric matrix in the diagonal form:
8
6
6
6
32
0
0
0
0
6
8
6
0
0
0
6
6
8
6
6
=
0
0
2
0
0
A"
(13)
6
6
2
0
6
6
6
6
8/
0
0
0
0
2
By direct calculations we find that for the matrix A and any 9,
E R we have
q
0
0
+ 4s
9
0
8
Q
q +
q-5
q 5
B =
0
0
0
AT
q
9 4s
0
q
9
q-8 q +
4s
q
9
+ 4s
Given that the first and last cores of the TT-disposition are vectors, not matrices, we need only
the first element of the first row B[1, 1] 1/5(g + 4s). Using the diagonal form of the matrix (13) we can immediately power it to degree 400 by power its eigenvalues to this degree and obtaining q = 300 and = 2400
Thus, the final answer to the problem: 1/5 + 2400 number of subsets.
B.7 SAT PROBLEM
Consider the standard Boolean satisfiability problem (SATisfiability) in conjunctive normal form (CNF-SAT). Given d Boolean variables (x, ]d taking the value "True" or "False". From these
variables we form logical expressions (A, i= containing set of some variables {ax) their
negations (which we denote by the symbol -) united by logical OR (symbol V), for example:
A = Ti V 33 V 25.
A2 21 V U2 V IA V 05 V 410.
etc.
The problem is to determine if there is such a set variables x that expressions A,, combined with logical AND (symbol A), give logical "True":
A A A2
A. True.
25

---

Published as a conference paper at ICLR 2023
Let us our method to construct tensor with indices taking the values 0 and 1, corresponding to logical "True" and "False", which is equal to 1 if the latter equality is satisfied, and zero otherwise. Each index corresponds to a different variable zz-
In this problem, we construct m separate indicator tensors for each value A,, which we then multiply elementwise, which corresponds to the logical AND operator. The indices of these tensors binary and correspond to the True or Fals se value of the corresponding variable. The derivative functions for the j-th tensor are the following:
2, the variable zy is not part of the condition A, if the variable z4 is included in the condition Aj with the negation
al True (x)
1, else
2, if the variable zy is not part of the condition A,
fPatse (x)
2, if the variable Fy included in the condition A5 without the negation
1, else
The function that corresponds to the last numbered variable (æ10 for Ae in the above example) returns None if its argument member the condition A, took the value True.
0 thus zeroing out the tensor: zero value of æ means that no
In this problem, the final rank of the constructed tensor depends strongly the order of the indices, although should be noted that many SAT algorithms also have heuristics on the sequence of passes over the variables.
RANK OPTIMIZATION
The algorithm presented in the main Theorem 2.1 does not always give optimal ranks.
Below in this section we present additional steps that reduce the ranks. Let's now look more closely the method of rank reduction briefly described in section
In this method, we combine different, but close, values of the derivative functions. Let the values of the derived functions be real and we are given the parameter e of "smallness" We start by sorting all possible set values of each of the sets R[i]] i 1..., d in Algorithm i ascending order. We then partition all the values into such non-overlapping sets whose difference between a larger and a smaller element does not exceed Namely, we put
STi (x R[i]: RMJ[ s < R[][[]] +
and then sequentially define
k-1 U j=1
|ti[k] = f E RM:: min R(]
spibl
s < min
{ [M] \ stbb) +
j=1
until all elements in the initial set R[i] are exhausted. If additionally maximum rank is given and the number of elements in Sli] exceeds it, we combine the sets further, trying to do uniformly as possible.
For each we update R[] after defining all sets S[i] at each step:
R average (A)), 7:
[8]]]]
where the average function be chosen in different ways, reasonable choices for it the arithmetic mean and the average between the maximum and minimum elements. Finally, the change we make in the algorithm is replace the index_of function with the following set_index.of function
set indixiddxooll....
A) + y E Al2).
As the second argument, pass the sets 5 to this function instead of R. Technically, the searchsorts function from the numpy package, and work with interval bounds rather than looking in sets stated in the definition.
26

---

Published as a conference paper at ICLR 2023
C.1 DECREASE THE NUMBER OUTPUTS
Assume that the middle-index is the last index: ( d. This avoids duplicating operations.
If the number of possibles vales of the tensor is small, i. e. the length of the array R[d] is small, we perform the following trick. Consider the images (f(4)) of the th set of derivative functions
( -a) = {x:
aa, = Tdd
The idea of reducing the rank of the TT-decomposition is that the values from this set are indistinguishable for the function f/ Thus, if there exists a set indistinguishable for all set of the last derivative functions, then its elements can be encoded by a single basis vector. Namely,
consider the following array (ordered set) of sets
Sid- 11 == n
(a:): (a)) {ai, 02 ..... and E (R(d))*ni, * Ø
The array Sid 1] contains all nonempty sets, that are indistinguishable for functions f. for any value of 1 .... Nd- The order in which these sets are included Sid 1] unimportant, but it is fixed. The number of all this sets is not greater than the number of outputs in Rid 1]: (Snd - 1]) s len(fi(d - 1J) as each element of Ríd 1] belongs exactly to one set in Sid - 1]. Due to this, decrease in ranks is achieved.
This procedure is repeated sequentially for each output. At the 1hth step we find an array of sets
S|k - 1] = { ( (f! {A1, A2, .... And (S[K)) Xna, $ + 0
where {Ai} are sets and define the image on a set as
( := 1 (x) A}.
After all sets S[k] (k 1, d 1) are found, we construct integer-valued functions by analogy with the functions
A (x) set index of (f(²
(2). STi). a E Sik 1][z]. 9 1, d.
(14)
We let S[d] {(=} x E R[d).. The definition (14 is correct because the value of the functions f() does not depend on the choice of particular element & in the set Sli 1][x].
C.2 ROUNDING
The cores that are obtained using Algorithm have one important property they are ,,almost" orthogonal in the sense that
ΣΣ Gu i, G) i, m) = A1oim k k= =, d --1- 1.
(15)
Gb(:, i, :) consist of rows either identically equal to the zero vector or the basis vector e(j)" for some j. The values of the coefficients X have the physical meaning of the number of occurrences of the value number is equal to the number of occurrences of row vector e(I)T in all matrices (x. Thus A O. The consequence of relation (5) is the following theorem which is a modified Lemma 3.1
This is true, because matrices Q (i)
the value of the function f(k), This
from (Oseledets) 2011):
Theorem C.1. Let Qx (i) Ga(;, i, :), Qx(i) E RIT--IXFE, To = 1, be indexed matrices with
tensors GR satisfying (15).
Let the matrix Z be defined follows
Z (11i2 4. 1) = (((s)) ... Qu((e))
Σ Ci Dk-1
G(1, in Ge(Ga is. a2) Ga ig. 1).
27

---

Published as a conference paper at ICLR 2023
Then the matrix Z satisfy the following orthogonality condition
(z" [), m) = Σ 2(1182...66 () m) = Aạōim
with natural Ar E
Thus, when rounding the tensor with the algorithm described in (Oseledets) 2011), can start with the second step of this algorithm, skipping the orthogonalization step. In the case of setting the accuracy the threshold for discarding the singular numbers must take into account the values AІ.
In the case where we need an exact representation of the given tensor in TT-format, but with the smallest possible ranks, the following consequence helps us.
Consequence C.I. The cores, obtained by Algorithm 2 the last core is of full-column rank.
have the optimal ranks if the unfolding of
FINDING NON- ZON-ZERO ELEMENT IN A TT-TENSOR
Consider the when the TT-tensor is indicator tensor of subset of its index values, i.e. it is equal to one (or an arbitrary values greater than zero) on a small number combinations of its index values and to zero on the other combinations. The problem is to find least one combination where the tensor value is greater than zero.
The solution this problem is based the algorithmic simplicity of multidimensional summation of the tensor defined in the TT format. Let be the tensor of interest. Consider the sum of values of on all variables except the first one
ng
(1)
I[i, i2, .... id).
w=
Knowing Uh, find out the value of i of the first index of the desired combination:
å = arg max 01 (1) > 0.
Indeed, if 1 is not a part of any desired combination, then for any values of other indices the value of the tensor is zero: 1(1,, 22, ..... id) 0. But this contradicts the fact that the value of the sum over these variables greater than zero.
Then sequentially find the indices of the desired combination. For the second index:
02
M( i, is td),
1==1
82 arg max
ans so on. This sequence of steps is summarized in Algorithm
Algorithm Algorithm for calculating indices set of the non-zero value TT-tensor
Require: Cores (G Id of the TT-decomposition of the tensor that takes non-negative values
Ensure: Set of indices (i,, i2, ..., 3 s.t. K(i,, ..., ia) > 0
1: for k 1 to do
2: G + E Gk(1, (,
3: end for
4: for k == to do
5:
uu G (1, i, :) G2(:, 82, :)... Gk(;, 86-1, GKG i, :)G41 Ga
6: dg f- arg max un (i)
7: end for
8: Return {iz, bg ... 4d}
28


Reviews:
[{"review_id": "zcT0gQIjHAX", "reviewer": "Reviewer_ApYB", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper studied a new way to build the tensor train (TT) representation for a special group of functions. In particular, as proved in the paper, this paper claimed that a functional tensor could be represented in the low-rank TT format if the image of the “derivative functions” is sufficiently small. In the experiments, the proposed method was used for two applications: (1) cooperative games and (2) the computation of the matrix permanent. The proposed method gives a significant improvement in the performance for both two problems.", "summary_of_the_review": "It is hard to simply judge if this work is good or bad. It’s quite different from others I have reviewed recently. Both the strength and drawbacks are obvious. It would be a good work if the mentioned problem is revised.", "strength_and_weaknesses": "+Strength:\n\n1. The targeted problem is relatively novel. In machine learning, the problem is rarely discussed in the tensor community.\n2. The applications mentioned in the paper—cooperative games and the computation of matrix permanent—illustrate the potential of tensor methods in new applications.\n\n- Weakness\n\n1. The paper is hard to follow, even though the main idea seems not complicated.\n2. The experimental results for the cooperative game are not convincing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "zI4oGTe5I-", "reviewer": "Reviewer_gzvu", "summary": "", "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": "", "summary_of_the_paper": "The paper presents a method for formulating particular multivariate functions based on indices as a particular tensor train decomposition. An overview of the construction is presented, where so-called derivative functions are used to define index dependences as well as the cores of the TT representation. Analysis of the construction is presented, and a number of experimental settings are evaluated where particular problems can be framed within the proposed derivative function TT framework.", "summary_of_the_review": "Ultimately the paper is poorly organized, and fails to effectively motivate a reader as to why they should be interested in and value the proposed method. There are some particularly interesting pieces, but they are not communicated effectively in the current presentation.\n\n---\nAfter Rebuttal:\nThe authors have addressed a majority of my concerns (and mistaken confusions) and put significant effort in restructuring the paper for clarity and readability. It is still difficult for me to see the significance (theoretically or practically) outside of what is presented here, but it is interesting work nonetheless. The revision is much clearer to me;  I have increased my score to reflect this.", "strength_and_weaknesses": "\nStrengths\n1) The paper presents an interesting formulation building on existing work modeling functions as tensor representations.\n2) A large number of (cool!) example problems are provided, which are both individually interesting and strongly support the author's claims that the method is quite general and can be variously applied.\n3) All formulations and implementations are extremely detailed, and an interested reader would have no problem recreating this work given the paper and Appendix, as well as the anonymized linked code.\n\nWeaknesses\n1) The organization of the paper could be improved. In the main paper, the Appendix is referenced 11 times. Many of those places seem to allude to significant contributions or problems of interest. Personally, I was able to much more understand the motivation and the construction of the method through some of the examples given in the Appendix (knapsack, n-queens). Throughout the main paper as a reader, it was hard to understand and follow the motivation of why and where this could be valuable or interesting. The cooperative game examples were a bit further outside of my familiarity, and I assume this might be true for other readers; including a classical combinatorial optimization or other Hard problem from the Appendix could connect with a wider audience. Sections 3.3 and 4 could be merged with the introduction, they do not meaningfully add much currently.\n\n2) Theorem 2.1 does not seem to be revealing anything particularly interesting, a discussion of why this is not obvious or why it is valuable would be beneficial over the full proof which could be moved to the Appendix, leaving more space for additional examples.\n\n3) In the end, the practical value is not demonstrated that well. While the construction performs better than the cross-TT approach for the given problems, it's not clear why constructing functions in this way is particularly valuable over the existing, \"non-tensor\" problem formulations or functions. The complexity of the tensorized problem in both space and time seems to only be lower bounded by existing solutions/solvers. This is further demonstrated by the paper's own description that the rank can sometimes be low and sometimes significantly higher than approximation methods. The experiments do not compare solving the problem against traditional solvers.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dW9f2XDV3Z", "reviewer": "Reviewer_vyEW", "summary": "", "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": "", "summary_of_the_paper": "This paper presents a method to build a Tensor Train (TT) representation of a multidimensional tensor when the computation of the tensor entries has an analytical expression with a tree structure involving derivative functions that apply to single entries and values of their neighbor derivative functions (Fig. 1a). Moreover, the obtained representation is exact and it has low TT-ranks when the domain sets of the derivative functions are discrete and have small cardinality. The advantage of the proposed method is that, once the TT model is available, it is possible to operate with it in an efficient way for example to implement sums or convolutions of high-dimensional tensors directly in the TT format. The authors apply their method to several combinatorial problems, including game theory problems and to the calculation of the permanent of a matrix.", "summary_of_the_review": "I think that, although the paper could be highly improved in quality and clarity, the ideas and method introduced are interesting and could have large impact in future applications.", "strength_and_weaknesses": "Strengths\n-\tThe idea is novel, and it could have important applications beyond the scope of the present paper.\n\nWeaknesses\n-\tThe assumption that a set of analytical derivative functions is available is a very strong hypothesis so the number of cases where this method can be applied seems limited.\n-\tThe high dimensional tensor can be also compactly represented by the set of derivative functions avoiding the curse of dimensionality, so it is not clear what is the advantage of replacing the original compact representation by the TT representation. Maybe the reason is that in TT-format many operations can be implemented more efficiently. The paper gives not a clear explanation about the necessity of the TT representation in this case.\n-\tIt is not clear in which cases the minimum rank is achieved by the proposed method. Is there a way to check it?\n-\tIn the paper it is mentioned that the obtained core tensors can be rounded to smaller ranks with a given accuracy by clustering the values of the domain sets or imposing some error decision epsilon if the values are not discrete. It is not clear what is, in theory, the effect on the approximation in the full tensor error. Is there any error bound in terms of epsilon?\n-\tThe last two bullets in the list of main contributions and advantages of the proposed approach are not clear to me (Page 2).\n-\tThe method is introduced by an application example using the P_step function (section 2.2). I found this example difficult to follow and maybe not relevant from the point of view of an application. I think, a better option would be to use some problem easier to understand, for example, one application to game theory as it is done later in the paper.\n-\tVery relevant ideas and results are not included in the main paper and referred instead to the Appendix, which makes the paper not well self-contained.\n-\tThe obtained performance in terms of complexity for the calculation of the permanent of a matrix is not better than standard algorithms as commented by the authors (Hamilton walks obtained the result with half of the complexity). It is not clear what is the advantage of the proposed new method for this application.\n-\tThe comparison with the TT-cross method is not clear enough. What is the number of samples taken in the TT-cross method? What is the effect to increase the number of samples in the TT-cross method. I wonder if the accuracy of the TT-cross method can be improved by sampling more entries of the tensor.\n\nMinor issues:\n-\tPage 2: “an unified approach” -> “a unified approach”\n-\tPage 2: “and in several examples is Appendix” -> “and in several examples in the Appendix”\n-\tIn page 3, “basic vector e” is not defined. I think the authors refers to different elements of the canonical base, i.e., vectors containing all zeros except one “1” in a different location. This should be formally introduced somewhere in the paper.\n-\tPage 9: “as an contraction” -> “as a contraction”\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3_Js0M_gaY", "reviewer": "Reviewer_EMLj", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "Given a function f : Z^d -> R, the authors construct tensor-train representations for the implicitly defined tensor. They first need to build a computational tree for the entries of the tensor that involves left and right derivative functions. From this, they show that they can construct a TT format for the tensor X_{i1,...,id} = f(i1,...,id) that has a TT-rank vector that depends on the size of the image of each derivative function (see Theorem 2.1 and Algorithm 2). They use analytical techniques to write down the derivative functions. Once the tensor is in TT-format, subsequent tensor computations can be sped up.\n", "summary_of_the_review": "The paper presents a relatively simple, but effective, idea of deriving TT decompositions of tensors by analytically writing down a computational tree. The scope of this paper may be slightly limited, though in the appendix the authors do a good job at demonstrating the approach on a range of problems.", "strength_and_weaknesses": "The main observation in this paper is in Figure 1: A computational tree for the values of a tensor gives you a TT-decomposition. Going in the opposite direction is standard. A TT-decomposition gives you an efficient computational tree to recover any tensor entries. However, the usual challenge is finding a reasonable computational tree. In this paper, the authors give many applications where one can write a reasonably efficient computational tree. Before reading this paper, I always imagined that writing down reasonable computational trees for each entry of a tensor was challenging except in very simple examples. That's why we have to compute the TT format. \n\nHowever, the authors demonstrate this semi-analytic technique on several applications that ends up being quite convincing. In particular, the appendix contains many applications and examples of derived derivative functions. It would be nice to have more discussion on how one can construct a reasonable derivative functions (hence, computational tree). Or, are the authors just writing down anything that works? When one can write down a reasonable set of left and right derivative functions, then the resulting TT-decomposition is usually sparse. \n\nThe big weakness of the paper is the possibility that it is quite a specialized approach that only works on a handful of carefully selected functions, f, for the tensor entries.  It is hard to judge the generality of the approach, but the range of applications in the appendix is highly welcomed. I also assume that it is hard to write down a computational tree, in the setting when you are happy with a lossy compression. \n\nIn some of the applications in the appendix, it was unclear what the computational benefit is in terms of solving a problem.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster