Dynamic Tensor Product Regression
Authors: Aravind Reddy
Zhao Song
Lichen Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Regression
Sketching
Tensor Product
Kronecker Product
Dynamic data structures

Abstract: In this work, we initiate the study of \emph{Dynamic Tensor Product Regression}. One has matrices $A_1\in \mathbb{R}^{n_1\times d_1},\ldots,A_q\in \mathbb{R}^{n_q\times d_q}$ and a label vector $b\in \mathbb{R}^{n_1\ldots n_q}$, and the goal is to solve the regression problem with the design matrix $A$ being the tensor product of the matrices $A_1, A_2, \dots, A_q$ i.e. $\min_{x\in \mathbb{R}^{d_1\ldots d_q}}~\|(A_1\otimes \ldots\otimes A_q)x-b\|_2$. At each time step, one matrix $A_i$ receives a sparse change, and the goal is to maintain a sketch of the tensor product $A_1\otimes\ldots \otimes A_q$ so that the regression solution can be updated quickly. Recomputing the solution from scratch for each round is extremely expensive so it is important to develop algorithms which can quickly update the solution with the new design matrix. Our main result is a dynamic tree data structure where any update to a single matrix can be propagated quickly throughout the tree. We show that our data structure can be used to solve dynamic versions of not only Tensor Product Regression, but also Tensor Product Spline regression (which is a generalization of ridge regression) and for maintaining Low Rank Approximations for the tensor product.






Dynamic Tensor Product Regression
Aravind Reddy"
Zhao Song?
Lichen Zhang
Abstract
In this work, we initiate the study of Dynamic Tensor Product Regression. One has matrices A1 Raxxd, .....; Ag goal to solve the regression problem with the design matrix A being the tensor product of the matrices A1, Ag....... Ag i.c. min gin [l (,),, At each time step, one matrix A, receives sparse change, and the goal is to maintain sketch of the tensor product A ... @ Ag that the regression solution can be updated quickly. Recomputing the solution from scratch for each round very slow and is important develop algorithms which can quickly update the solution with the new design matrix. Our main result is a dynamic tree data structure where any update throughout the tree. We show that our data structure can be used to solve dynamic versions of not only Tensor Product Regression, but also Tensor Product Spline regression (which is a generalization of ridge regression) and for maintaining Low Rank Approximations for the tensor product.
xd, and a label vector b RR..... and the
single matrix can be propagated quickly
Introduction
The task fitting data points to line well-known as the least-squares regression problem [Sti81], which has wide range of applications in signal processing [RGIY78], convex optimization [Bub15], network routing [Mad13, 3, Mad16), and training neural networks [BPSW21, SZZ21J. In this work, study generalized version of least-squares regression where the design matrix A is tensor product & smaller matrices A @ A2 @ ..... 8 Aq-
Tensor products have been extensively studied in mathematics and the physical sciences since their introduction more than a century ago by Whitehead and Russell their Principia Mathe- matica [WR12]. They have been shown to have humongous number of applications in several areas of mathematics like applied linear algebra and statisties [VL00]. In particular, machine learn- ing applications include image processing [NK06], multivariate data fitting [GVL13], and natural language processing [PSA21]. Furthermore, regression problems involving tensor products arise in surface fitting and multidimensional density smoothing [EM06], and structured blind deconvolution problems [OY05], among several other applications, as discussed [DSSW18, DJS 19].
Solving tensor product regression in E2 norm [DJS+ 19, FFG22] to (1 + ε) precision takes time O nnz(A,) + voly(dq/(dE))) where each matrix A, Xd, and d d1dg ... dg. and (nz(A) denotes the number of nonzero entries of A. However, these algorithms are inherently static, meaning that even if there is sparse (or low-rank) update to single design matrix A, needs to completely recompute the new solution from scratch. modern machine learning appli- cations, such static algorithms and recomputing the solution from scratch every time computationally too expensive. Hence, important develop efficient dynamic algorithms that adaptively update the solution. For example, graphs for real-world network data are modeled as the tensor product of large number of
practical due to the fact that data points always evolving
"aravind. reddy@es. www.twwwteern.n..m edu. Northwestern University.
'zsongeadobe. com. Adobe Research.
$ "ichenzomit..c edu. MIT. (Author names alphabetical order, equal contribution)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

smaller graphs [LCK 10]. Many important problems on these graphs can be solved by regression of the adjacency and Laplacian matrices of these graphs [ST04]. Real-world network data always time-evolving and so it is crucial to develop dynamic algorithms for solving regression problems where the design matrix is a tensor product of large number of smaller matrices. Hence, we ask the following question:
Can we design dynamic data structure for tensor product regression that can handle updates to the design matrix and quickly updates the solution?
We provide a positive answer to the above question.
At the heart of our data structure is a binary tree that can maintain a succinct sketch of A @.... & A, and supports update to one of the matrices quickly. Such tree structures have been useful in designing efficient sketching algorithms for tensor products of vectors TAKK+20, SWY721J. However, the goal of these works has been in reducing the sketching dimension from exponential dependence on q to a polynomial dependence on q. Their results can be directly generalized to solving tensor product regression statically but not dynamically. In this work, we build upon the tree structure to solve the Dynamic Tensor Product Regression problem and other related dynamic problems like Dynamic Tensor Spline Regression and Dynamic Tensor Low Rank Approximation. Our key observation is that updating the entire tree is efficient when single leaf of the tree gets an update: specifically, we only need update the nodes which fall on the path from the leaf to the root.
Technical Contributions.
We design a dynamic tree data structure DYNAMICTENSORE TREE that maintains succinct representation of the tensor product A @ ... Ag and supports efficient updates to any of the A,'s ss
Consequently, we develop a dynamic algorithm for solving Tensor Product Regression, when one of the matrices A,'s ''s is updated and need to output an estimate of the new solution to the regression problem quickly.
We also show that we can use our DYNAMICTENSOR TREE data-structure in a fast dynamic algorithm solve the Tensor Product Spline Regression problem, which is generalization of the classic Ridge Regression problem.
We also initiate the study of Dynamic Tensor Low Rank Approximation, where the goal is to maintain low rank approximation (LRA) of the tensor product with dynamic updates, and show how we can use our DYNAMICTENSORTHHR
data structure to solve this problem.
Roadmap. In section 2, first discuss some related work. Then, we provide notation, some background for our work, and the main problem formulation in section In section 4, we provide technical overview of paper. Following that, we provide our dynamic tree data structure in section 5. We then show how can be used for Dynamic Tensor Product Regression, Dynamic Tensor Spline Regression, and Dynamic Tensor Low Rank Approximation in section 6. We end with our conclusion and discuss some future directions in section 7.
2 Related Work
Sketching. Sketching techniques have many applications in numerical linear algebra, such as lin- ear regression, low-rank approximation (3W13, NN13, MM13, BW14. RSW16, SWZ17, HLW17, ALS 18, BBB + 19. IVWW19, SWZ19a, SWZ19b. MW21, WY22, CSTZ22], distributed problems [W716, BWZ16), reinforcement learning [WZD+20, SSX21J, projected gradient descent [XSS21], training over-parameterizer neural networks [SYZ21, S7Z21], tensor decomposition [SWZ19c], clustering [EMZ21], cutting plane method [JLSW20], generative adversarial networks [XZZ18), recommender systems (RRS+22],, and linear programming [LSZ19, JSWZ21, SY21J.
Dynamic Least-squares Regression. A dynamic version of the ordinary least-squares regression problem (without tensor product design matrix) was recently studied in [JPW22]. their model, at each iteration, row is prepended to the design matrix A and a new coordinate is prepended

---

to the vector b. To efficiently maintain the necessary parts of the design matrix and the solution, they make use of fast leverage score maintenance data structure by [CMP20] and achieve running time ((nnz(A(r)) + poly(d, =1)) where is the number time steps.
Tensor/Kroneeckr Product Problems. Many machine learning problems involve ten- sor/Kronecker product computations such as, regression [HLW17, DSSW18, DJS+19]. low- rank approximation [SWZ19c], fast kernel computation [SWYZ21], semi-definite programming [JKL+20, 20, HIS*211 and training werr-parameterized neural networks [BPSW2I, SZZ21]. Apart from solving problems which directly involve lensor/Kronecker products, another line of research focuses on constructing polynomial kernels efficiently so that the computation of various kernel problems can be improved [AKK* 20, SWYZ21J.
3 Preliminaries
3.1 Notation
For any natural number n, use [n] to denote the 21. nn.. tation of random variable if it exists. We use 1[-] and Pr[.] to denote the indicator function and probability of event respectively. For any natural numbers a, we use Tmat b, c) denote the time it takes to multiply two matrices of sizes a X b and b x c. For a vector I, we use ||1||2 denote its lg norm. For a matrix A, we use ||A|[F to denote its Frobenius norm. For a matrix A
We use E[[- to denote expec-
denote the transpose of A. Given two matrices A R and B R=2xd2, we use A 8 B to denote their tensor product (which is also referred to as Kronecker product), i.e., Air. Bia.22 For example, for x 2 matrices A and B,
A.
(A & B) B),, + (12-1))2mn- 1)mm (: (f2-111)
Tanbi 0m1b1
ajgii
d12b12
(11
012
a11 B
012 B
411b21
011b22
012621
012b22
2 B
022
a2 B
B22
0g1b11
ag1b12
agab11
422b12 ag2b22
021b21
021b22
ag2b21
We use X to denote tensor product of more than two matrices, i... 0¹ A, = 8 For non-negative real numbers and For a real matrix A, we use (A) to denote its i-th largest singular value. For any function f. we use Of)) to denote ((fpoly(log.f)
a = (1 e)b to denote e) b S a (1 +
3.2 Problem Formulation
In this section, we define our task. We start with the static version of tensor product regression.
Definition 3.1 (Static version). In the &a Tensor Product Regression problem, we are given matrices A1, A2, ... Ag where A, Ra and E RR:....... Let us define n m1 ... Bl and d = di d2 .. dg. The goal is output Rdd such that minimize the objective:
[I A & Ag) b1|2
Our dynamic version &z Tensor Product Regression involves updating of the matrices A, with an update matrix B. We formally define the problem as follows:
Definition 3.2 (Dynamic version). In the Dynamic &g Tensor Product Regression problem, we are given matrices A1, A2,..., Ag where A; E 1g";xd, sequence {(11. B1), (42, B2)..., , (fz, Br) with i, E [g], B, IR Xdi, for all [T], and the goal is to design data structure with the following procedures:
INITIALIZE: The data structure initializes A Ag and maintains an approximation to
8'_1 Aj.
UPDATE: At time step 1, given an index i, and an update matrix B,, the data-structure needs to update As, t- As, + Br, and maintain an approximation to A 60 ... 60 (A;, + B,) & Aq.
3

---

QUERY: The data structure outputs a vector I E Rd such that
A bl22 = (1 (1 +)
min wER
II A,)x bll2.
Note that although we don't 't discuss updates to the vector b in model, they easy to implement in our data-structure. In addition to the standard regression problem, we also consider the spline regression (which is generalization of ridge regression) and low rank approximation problems. We will provide the definitions for these problems in their respective sections.
Technical Overview
The two main design considerations for our data structure are as follows: 1). We want a data structure that stores a sketch of the tensor product, this has the advantage having smaller storage space and a faster time to form the tensor product. 2). The update time to one of the matrices A₁ should be fast, ideally we want to remove the linear dependence on q. With these two goals in mind, we introduce dynamic tree data structure that satisfies both of them simultaneously. building on the sketch of [AKK* 20]. Specifically, we use each leaf of the tree to represent A, sketch the base matrix that only has rows instead of n rows, where is proportional to the small dimension d. Each internal node represents sketch of the Tensor product of two children. To speed up computation, adapt tensor-typed sketching matrices to avoid the need to explicitly form the Tensor product of the two children. The root of the tree will store a sketch for the tensor product x A..
We point out that in order for this tree to work, we need to apply an independent sketching matrix each tree node. Since there are 2q- - nodes total, we will still have a dependence on q in the initialization phase (which will be dominated by the d term). However, during the update phase, our tree has a clear advantage: one of the leaves has been updated, we only need to propagate the change along the path to root. Since the height of the tree is most Ollog q). we remove the linear dependence on y in the update phase. This is key insight for obtaining a faster update time using our dynamic data structure. Moreover, the correctness follows naturally from the guarantee of the tree: as shown [AKK 20), the tree itself is an Oblivious Subspace Embedding (OSE) for matrices of proper size, hence, it also preserves the subspace after updating one of the leaves. Figure is an example tree for tensor product of 4 matrices.
s
52
T2
T
T5
T
Figure 1: tree for sketching the tensor product of 4 matrices A1, A2, As and A4. The leaves use sketches of type Tasse and internal nodes use sketches of type Shase. The algorithm starts to apply T; each matrix A,, and then propagates them up the tree.
With this data structure, we provide efficient algorithms for dynamic Tensor product regression, dynamic Tensor Spline regression, and dynamic Tensor low rank approximation. For all these prob- lems, we do not explicitly maintain the solutions, rather, we use our tree to quickly update sketch of the design matrix. In the query phase (when we need to actually solve the regression problems), we use this sketch of updated design matrix to quickly compute the solution.
Dynamic Tree Data Structure
In this section, we introduce our data structure, which contains INITIALIZE and UPDATE procedures. We'll define task task- specific QUERY procedures later. We defer proofs in this section to Appendix B. We start with an outline of Algorithm 1.

---

Algorithm Our dynamic tree data structure
1: data structure DYNAMICTENSORTT
D Theorem 5.
2:
3: members
4: Jk,e Rm for 0 S E S logg and 0 0 9/2
> l is the level of the tree.
5: end members
6:
7: procedure INITIALIZE(A) E R xd1 ,..,,,,,, Ag E Ra xdy m E N+, Cbase Tase)
8: for f= 0 log q do
9:
for = 0 + q/22 do
10:
if f = then
11:
Choose Cg E IRmx from Chase. D Casse can be COUNTSKETCH, SRHT or
OSNAP.
12:
Ju + C2AR
else
14:
Choose Th, E Rmmmm" from base.
>> base can be TENSORSKETCH or
TENSORSRHT
15:
Ja.e + 1-Tx,e(J2xx--1 @ J2k+1.e-1)
Sketch of tensor product of its children
end if 17: end for
end for
19:
end procedure
20:
21: procedure UPDATE(i E [o], B e [
22:
for = 0 + log(4) do
23:
if f 0 then
24:
J + C,B
25:
J4,0 < J1,0 + 1.0
26:
else
27:
Jnew
(3/21-1),-1 1, Tk, (1/2 (1122))))111--11
Sibling is the left also
sometimes
28:
J/s/2f1, - J13/299,8 + 1./291,e
Sketch of tensor product of its children
29:
end if
30:
end for
31:
end procedure
Outline of Tree: For simplicity, let us assume that the number of matrices is a power of 2. Also, let us assume that all the matrices are of the same dimension 01 d1. The output dimension m x d where (such as COUNTSKETCH (Def. A.6), SRHT (Def. A.8)) (T, E Rmxni, i E [q]} to each of the matrices AI, A2.... Ag. After this step, all the leaf nodes are of size m d₁. Then, we have a tree height log q. Let us use = + log to represent the level the tree nodes where
matrix of poly(g, d First, we apply independent base sketch matrices
l represents the leaves and f log represents the root node. Let use Jk.E E B to denote the matrix stored at the node k, l. For leaf nodes, we choose base sketches Tj. mmxm and compute Ja.0 = AR. At each internal node, we use sketch for tensor-typed inputs (such as TENSORSKETCH (Def. A.7) or TENSORSRHT (Def. A.5)), apply it to its two children. The sketching matrix S, E m and it can be applied its two inputs fast, obtaining running time of (m) instead of (mm)). We inductively compute the tree all the way up to the root for initialization. Note that at the root, we end up with matrix of size m x d, which is significantly smaller than the tensor product n x d.
The running time guarantees of Algorithm 1, which we will prove Appendix B, are as follows:
Theorem 5.1 (Running time of our main result. Informal version of Theorem B.1). There is an algorithm (Algorithm 1) that has the following procedures:
5

---

We will now describe how our data structure can extended to handle an adaptive adversary. We store all initial factor matrices A,,..., Ag. During an update, suppose we are given pair (i, B:). Instead of using the sketching matrices correspond to the i-th leaf during initialization, we instead INITIALIZE(A) E Raixds Ag E R=2xds R Ag E R m E N.. Cbase base): Given matrices A₁ E R A2 E R_axdd, ,..., Ag E R" sion m, families of base sketches Chase and T bases the data-structure pre-processes in time o nnz(A.) + qmdd).
" a sketching dimen-
UPDATE(i E [g], B E R=xxd:): Given matrix B and an index i E [g]. the data structure updates the approximation A @ ..... @ (A4 + B) @ ... @ Ag in time (nnz((B) + md). Remark 5.2. In our data structure, we only pay the linear g term in INITIALIZATION (which will be dominated by the term d), since we are maintaining a tree with 2q nodes, each node corresponds matrix of m rows. In the UPDATE phase, we shave off the linear dependence on q. We also want to point out that the sketching dimension m is typically at least linear on however, it only depends on 9. the small dimension d and the precision parameter E, hence it is far more efficient use this sketch representation compared to the original tensor product. Also, note that though we only design a data structure for q being a power of 2, it is not hard generalize to q being an arbitrary positive integer via the technique introduced in [SWYZ21]. We only incur a log y factor by doing so.
The approximation guarantee for our dynamic tree, which follows from [AKK and for which we provide brief sketch in Appendix are follows:
Theorem 5.3 (Approximation guarantee of our dynamic tree. Informal version of Theorem B.1). Let II denote the sketching matrix generated by the dynamic tree, then have that:
A,)=112 (1 + E) A.)=112.
Choices of parameter m: An important parameter to be chosen is the sketching dimension m. Intuitively, it should depend polynomially on .d.q. We list them in the following table.
Chase
Thase
m(dim)
Init time
COUNTSKETCH
TENSORSKETCH
qq. dim (1/8)
nnz A,)
OSNAP
TENSORSRHT
9r dim log 1/0)
nnz A.)
OSNAP
TENSORSRHT
9. 2..dim* lo/(1/))
nnz
Table 1: How different choices of Chase and Thase affect the sketching dimension m(dim) and initialization time that depends on the choice of sketch. We note that the sketching dimension m is function of dim, the fundamental dimension of the problem. For example, dim d for tensor product regression and dim = k for k-low rank approximation. The sketching dimension corresponds to the problem of computing an (c, 5, dim, d, OSSE.
Robustness against an Adaptive Adversary: An often encountered issue in dynamic algo- rithms is the presence of an adaptive adversary [BKM+22], Consider sequence of update pairs (ii, Bo in which the adversary can choose the pair (7, B,) based on the output of our data structure on (i - 1, 12 Such an adversary model naturally captures many applications, in which the data structure is used in an iterative process, and the input to the data structure depends on the output from last iteration.
choose fresh sketching matrices along the path from the leaf to the root. Since the only randomness being used the sketching matrices along the path, by using fresh randomness, our data structure works against adaptive adversary.
Such modification does not affect the update time too much: during each update, we need to apply the
base sketch C.ew both A, and B, incurring a time of ((nnz(A,) mnz Along the path, the data structure repeatedly apply The to its two children, which takes Ō (md) time. The overall time is thus
((nz(AA)) mnz (B) + md).
Thus, in later applications of our data structure, present the runtime without this modification.

---

Faster Dynamic Tensor Product Algorithms with Dynamic Tree
In this section, we instantiate the dynamic tree data structure introduced in section for three appli- cations: dynamic tensor product regression, dynamic tensor spline regression, and dynamic tensor low rank approximation.
6.1 Dynamic Tensor Product Regression
We present an algorithm (Algorithm. 2) for solving the dynamic Tensor product regression problem. Our algorithm uses the dynamic tree data structure to maintain sketch of the design matrix and updates it efficiently. Additionally, we maintain sketch of the label vector b via 119.. During the query phase, we output the solution using the sketch of the tensor product design matrix and the sketch of the label vector. We have the following guarantees, the proof of which we defer to Appendix C:
Theorem 6,1 (Informal version of Theorem C.I). There is an algorithm (Algorithm for dynamic Tensor product regression problem with the following procedures:
Ag E Rd Xd,, m E N4,, Chase: Tusse, E )= Given matrices A E Ra Raixd, xd. .2 E Ruuxxda ,..., Ag E 1Rn sketching dimension m, families of base sketches Chaser Thase and label vector b E .un.... the data-structure pre-processes in time 0(Ei= nnz (A:) qmd
INITIALIZE(A, E R xd1, AA E Ra2xd2,
nnz(b)).
UPDATE(i E [q], E Rusxd.) Given a matrix B and an index i E [q], the data structure updates the approximation to A @ .... @ (A, + B) 8 @ Ag in time (nnz(B) + md).
QUERY: Query oulputs an approximate solution & to the Tensor product regression prob- lem where || 8 A& bl22 (1 + e)]l 0 Axx"* - bll2 with probability at least 1 - ô in time (md=~1 d²) where x= is optimal solution to the Tensor product regression problem i.e. x= = arg min 10 A, bli2-
To realize the input sparsity time initialize and update time, we can use the combination of OSNAP and TENSORSRHT, which gives a sketching dimension
m = E qdd log(1/5).
Hence, the update time is Óunz (B + E 2dd log(1/8)). Compared to the static algo- rithm [DJS+ 19], we note that their algorithm is suitable to be modified into dynamic setting, with running time of Ó(nz (A.) + nuz( + =-2 + d)d//)). their algorithm cannot accommodate general dynamic setting due to the 1/8 dependence in running time. Suppose the length dynamic sequence at least d, then one requires the failure probability be most 1 for union bound. In such scenario, the algorithm of [DIS+ 19] is strictly worse. [FFG22] improves the dependence on d, yielding a subquadratic update time in the form of (((nn(()) + nnz(B) + e 22 + --122-0 log( L/))). While their algorithm is more efficient in solving the regression problem, their approach does not scale with the statistical dimension of the problem, and is geared only towards regression, whereas our data structure also handles low rank approximation.
6.2 Dynamic Tensor Spline Regression
Spline regression models are a well studied class of regression models [MCO1]. In particular, Spline regression problems involving tensor products arise in the context of B-Splines and P- Splines [FM96]]. For a very brief but relevant introduction to Spline regression, we refer the reader to 18). In this section, we first define the Spline regression problem it pertains to sketching application. Algorithm 3, which shows how we can use our DINAMICTENSORTREE data structure to solve a dynamic version of the Spline regression problem provided in Appendix D. Definition 6.2 (Spline Regression). In the Spline regression problem, given a design matrix A e Rmxa target vector I E R. regularization matrix L. E Rexd and a non-negative penalty coefficient X E R, the goal is to optimize
min A b11 + X || FER
(1)
7

---

Notice that the classic ridge regression problem is a special case of spline regression (when = π). In the TENSOR SPLINE REGRESSION problem, we want solve the Spline regression problem where the design matrix A can be decomposed the tensor product of multiple smaller matrices i.e. = A 80... Ag. Our DYNAMICTENSORI MAISSRTRREE TREE data structure can used to solve dynamic version of TENSOR SPLINE REGRESSION. In our dynamic model, at each time step, the update is of the form E [g]. B E Ru.xd, and the data structure has to update A, + A + B.
Before introducing our main result, we define an important metric to measure the rank of Spline regression:
Definition 6.3 (Statistical dimension of Splines). For matrix E Rexd and E Rexd with Given the generalized singular value decomposition [GVLI3]
rank(L) and rank (4)
[
Σ
(px(n-M) ld-p
of (A, L) such that A U
RQT L v [2 (px(n=p) RQT, where Rpxp are diagonal matrices. Finally, let
(n-))xp
0 diag(
.iag(oi....... (.p)) = oi/M for [p].
The statistical dimension of the Spline is defined sdx 1/0
The statistical dimension of the Spline can be much smaller than and we will show that the sketching dimension depends on the statistical dimension instead of d.
Let x² denote optimal solution of the Spline regression problem, i.e.
x
arg min| Ax - bll2 + A [
#ER"
and let OPT |Ax" b112 X Lx 122
We can compute x² given b, b, x= A
AL -)-1A
Theorem 6.4 (Guarantees for DTSREGRESSION. Informal version of Theorem D.5), There exists an algorithm (Algorithm 3) with the following procedures:
INITIALIZE(A Raixd, Xd,, the data structure pre-processes in time
xd, ..... E R)x Given matrices A E Raixd ..... Ag
inz(A.) + gmd + m nnz(b)).
UPDATE(i E [g), E Ra.xd)); Given an index E [q] and an update matrix E Ruxd the data structure updates in time Ó(nnz B) + md)).
QUERY: Let A denote the tensor product 8 A, Query outputs a solution T E Th with constant probability such the z is an approximate the Tensor Spline Regression problem i.e.
|| A b12
|| s (1 c)) OPT
where OPT = min || 1 + L Query takes time md(w-1) 1) + -pd 1) +d
We defer the proof of the above theorem to Appendix D.
The sketching dimension here depends the statistical dimension of the Spline, which is most d. To realize the above runtime, one can pick OSNAP and TENSORSHRT, which gives m = = sd (A, L) log(1/8) and an update time Ó(nnz B) + s sa, (A, log(//()))). The improved dependence on e comes from using approximate matrix product directly, instead of OSE.
6.3 Dynamic Tensor Low Rank Approximation
In this section, we consider problem studied [DJS+ 19]; given matrices AI...., Age the goal to compute low rank approximation for the tensor product matrix A . & A, Rexd specifically, a rank-k approximation B xa such that
|B A < (1 + OPPT
8

---

where OPTr = minkakk- 14' - AAFF and A = - A, The [DJS 19] algorithm works as follows: they pick independent COUNTSKETCH matrices [CCFC02] with (s= -gk2) rows, then apply each sketch matrix St A. After that, they form the tensor product .M and rum SVD on M UEV.. Finally, they output B AUg Us factored form (as matrices A...... Aq. U&), where Us E R denotes the top & right singular vectors. By doing so, they achieve an overall running time of
S,A,
O nnz(A,) + 2
Two central issues around their algorithm are 1). exponential dependence on parameters e- q. and 2). the algorithm is inherently static, natural way to make it dynamic is to apply St to the update B, reforming the tensor product of sketches and compute the SVD.
We address these two issues simultaneously by using our tree data structure. For the sketching dimension, we observe is enough design sketch that (c, 6, k. d, n>-OSE and (e/k: 8)- approximate matrix product, therefore, we can set sketching dimension As we will show later, this gives a much improved running time. By using the dynamic tree, we also provide dynamic algorithm.
= E = log()
Theorem 6.5 (Guarantees for LOWRANKMAINTENANE
Informal version of Theorem E.3).
There exists an algorithm (Algorithm 4) that has the following procedures
INITIALIZ(A)) E 1 (Rmixd,,.. ...., Ag E Rd)x) Given matrices A1 E R xd ,...,A Ag E IR xdy, the data structure processes in time
Ō nnz(A) + qmd).
UpdAtE(i [a], E Rn.xd.); Given an index E [g] and an update matrix B Ru, the data structure updates the approximation for A1 @ ... @ (A, + B) B) &.... @ Ag in time
Ö(nnz( B) + md).
QUERY: Let A denote the tensor product X % approximation C such that
As.
The data structure outputs a rank-k
|[C- - All S (1
=)
min
I - AA'-A|EE.
rank
The time to output is ((md"1))
By choosing m = gkh2 log(1/)), we can provide good guarantees for low rank approximation.
This gives
Initialization time in Ô mnz + qdkk log(1/8)):
Update time in ((nz + - qdkk² log(1/8));
Query time in Ō( 0
Without using fast matrix multiplication, our algorithm improves upon the prior state-of-the- art [DJS+ 19] on all parameters even in the static setting.
Conclusion & Future Directions
In this work, we initiate the study of the Dynamic Tensor Regression, Dynamic Tensor Spline Re- gression, and Dynamic Tensor Low-Rank Approximation problems, and design a tree data structure DYNAMICTENSORTTER
which can be used to provide fast dynamic algorithms for these problems. The problems we study are very interesting and there are a lot of exciting future directions, some of which we discuss below. First, it is unclear whether the algorithms we proposed are optimal and so having lower bounds for the update times would be an important direction. Second, we have focused exclusively regression problems with the & norm whereas solving Dynamic Tensor Regression and Dynamic Tensor Spline Regression with respect to the more robust E -orm as well as for more general pormrs also very appealing.

---

Acknowledgments
We would like thank all the NeurIPS 2022 reviewers of our paper and also the ICML 2022 reviewers who reviewed an earlier version of this work. Most of this work was done while LZ was CMU, AR was supported in-part by NSF grants CCF-1652491, CCF-1934931, and CCF-1955351 during the preparation of this manuscript.
References
[ACW17] Haim Avron, Kenneth L. Clarkson, and David P. Woodruff. Sharper bounds for regular- ized data fitting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 20th International Workshop, APPROX 2017 and 21 International Workshop, RANDOM 2017, August 2017.
[AKK*20] Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Vel- ingker, David P Woodruff, and Amir Zandich. Oblivious sketching of high-degree polynomial kemells. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 141-160, 2020.
[ALS 18] Alexandr Andoni, Chengyu Lin, Ying Sheng. Peilin Zhong, and Ruiqi Zhong. Subspace embedding and linear regression with orlicz norm. In International Conference Machine Learning (ICML), pages 224-233. PMLR, 2018.
[BBB + 19] Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, and David P. Woodruff. ptas for lp-low llw rank approximation. In Proceedings the Thirti- eth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 199, page 747-766, 2019.
[BKM*22] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranu- rak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1671-1684, 2022.
[BPSW21] Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (over- parametrized) neural networks in hear-lineat time. In ITCS, 2021.
[Bub15] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):211-357, 2015.
[BW14] Christos Boutsidis and David P Woodruff. Optimal cur matrix decompositions. In Proceedings of the 46th Annual ACM Symposium Theory of Computing (STOC), 2014.
[BWZ16] Christos Boutsidis, David Woodruff, and Peilin Zhong. Optimal principal component analysis in distributed and streaming models. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC), pages 236-249, 2016.
[CCFC02] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002.
[CEM+11 + 15] Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing. pages 163-172, 2015.
[CMP20) Michael B. Cohen, Cameron Musco, and Jakub Pachocki. Online row sampling. Theory Comput., 16:Paper No. 15, 25, 2020.
[CSTZ22] Sitan Chen, Zhao Song, Runzhou Tao, and Ruizhe Zhang. Symmetric sparse boolean matrix factorization and applications. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Biestuul-Leeibni--eeeee für Informatik, 2022.
10

---

[CW13] Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 2013.
[DIS 19] Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, and David Woodruff. Optimal sketching for kronecker product regression and low rank approximation. Advances in neural information processing systems, 32:4737-4745 2019.
[DSSW18] Huaian Diao, Zhao Song, Wen Sun, and David Woodruff. Sketching for kronecker product regression and p-splines. In International Conference on Artificial Intelligence and Statistics, pages 1299-1308. PMLR, 2018.
[EM96] Paul HC Eilers and Brian D Marx. Flexible smoothing with b-splines and penalties. Statistical science, 11(2)899-211, 1996.
[EM06] Paul HC Eilers and Brian D Marx. Multidimensional density smoothing with p-splines. In Proceedings of the 21 international workshop on statistical modelling, 2006.
[EMZ21] Hossein Esfandiari, Vahab Mirrokni, and Peilin Zhong. Almost linear time density level set estimation via dbscan. AAAI, 2021.
[FFG22] Matthew Fahrbach, Thomas Fu, and Mehrdad Ghadiri. Subquadratic kronecker re- gression with applications to tensor decomposition. arXiv preprint arXiv:2209.0487 2022.
[GVL13] Gene H. Golub and Charles F. Van Loan. Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2013.
[HJS* Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang. Solving sdp faster: A robust ipm framework and efficient implementation, 2021.
[HLW17] Jarvis Haupt, Xingguo Li, and David Woodruff. Near optimal sketching of low-rank tensor regression. In ICML, 2017.
[IVWW19] Pitor Indyk, Ali Vakilian, Tal Wagner, and David P Woodruff. Sample-optimal low- rank approximation of distance matrices. In Conference on Learning Theory, pages 1753-1751. PMLR, 2019.
[J] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In FOCS, 2020.
[JLSW20] Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games and its applications. In STOC, 2020.
[JPW22] Shunhua Jiang, Binghui Peng, and Omri Weinstein. Dynamic least-squares regression. arXiv preprint arXiv:2201.00228, 2022.
[SW7211] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. Faster dynamic matrix inverse for faster lps. STOC. arXiv preprint arXiv:2004.07470, 2021.
[LCK*10] 10] Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kronecker graphs: an approach to modeling networks. Journal of Ma- chine Learning Reseurch, 11( 2010.
[LDFU13] Yichao Lu, Paramveer Dhillon, Dean Foster, and Lyle Ungar. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural informa- tion processing systems, pages 369-377, 2013.
[LSZ119] Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In COLT, 2019.
[Mad13] Aleksander Madry. Navigating central path with electrical flows: From flows to match- ings, and back. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 253-262. IEEE, 2013.

---

[Mad16] Aleksander Madry. Computing maximum flow with augmenting electrical flows. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 593-602. IEEE, 2016.
[MC01] L.C. Marsh and D.R. Cormier. Spline Regression Models. Number 137 in Quantitative Applications in the Social Sciences. SAGE Publications, 2001.
[MM13] Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in input-sp time and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium Theory of computing (STOC), pages 91-100, 2013.
[MW21] Arvind V. Mahankali and David P. Woodruff. Optimal l column subset selection and fast ptas for low rank approximation. In Proceedings of the Thirty-Second Anmual ACM-S SIAM Symposium on Discrete Algorithms, SODA '21, page 560-578, 2021.
[NK06] James G Nagy and Misha Elena Kilmer. Kronecker product approximation for pre- conditioning in three-dimensional imaging applications. IEEE Transactions on Image Processing, 15(3)6604-613, 2006.
[NN13] Jelani Nelson and Huy Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013.
[OY05] S. Oh, S. Kwon and J. Yun. A method for structured linear total least norm on blind deconvolution problem. Applied Mathematics and Computing, 19:151-164, 2005.
[Pag13] Rasmus Pagh. Compressed matrix multiplication. ACM Trans. Comput. Theory, 5(3), aug 2013.
[PP13] Ninh Pham and Rasmus Pagh. Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowl- edge discovery and data mining, pages 239-247, 2013.
[PSA2I] Aliakbar Panahi, Seyran Sacedi, and Tom Arodz. Shapeshifter: a parameter-efficient transformer using factorized reshaped matrices. Advances in Neural Information Pro- cessing Systems, 34, 2021.
[RGIY78] L. R. Rabiner, B. Go ld, and C. K. Yuen. Theory and application of digital signal processing. IEEE Transactions on Systems, Man, and Cybernetics, 8(2): 1978.
[RRS+22] Aravind Reddy, Ryan A Rossi, Zhao Song, Anup Rao, Tung Mai. Nedim Lipka, Gang Wu, Eunyee Koh, and Nesreen Ahmed. One-pass algorithms for map inference of nonsymmetric determinantal point processes. In International Conference on Machine Learning, pages 18463-18482. PMLR, 2022.
[RSW16] Ilya Razenshteyn, Zhao Song, and David P. Woodruff. Weighted low rank approxi- mations with provable guarantees. In Proceedings of the Forth-Eighth Annual ACM Symposium on Theory of Computing, STOC '1,, page 250-263, 2016.
[Sar06] Tamás Sarlós. Improved approximation algorithms for large matrices via random pro- jections. In Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006.
[SSX21] Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu. Sublinear lqaates value iteration via locality sensitive hashing. arXiv preprint 10Xiv:2105.08285. 2021.
[ST04] Daniel A Spielman and Shang- Teng. Nearly-linear time algorithms for graph par- titioning, graph sparsification, and solving linear systems. In Proceedings of the thirty- sixth annual ACM symposium on Theory of computing, pages 81-90, 2004.
[Sti81] Stephen M. Stigler: Gauss and the Invention of Least Squares. The Annals of Statistics, 9(3):465- 474, 1981.
12

---

[SWYZ21] Zhao Song, David P. Woodruff, Zheng Yu, and Lichen Zhang. Fast sketching of poly- nomial kernels of polynomial degree. ICML, 2021.
[SWZ17] Zhao Song, David P Woodruff, and Peilin Zhong. Low rank approximation with en- trywise -norr error. In Proceedings of the 49th Annual Symposium on the Theory of Computing (STOC), 2017.
[SWZ19a] Zhao Song, David Woodruff, and Peilin Zhong. Average case column subset selec- tion for entrywise f1-nrrm loss. Advances in Neural Information Processing Systems (NeurIPS), 32: 11111111111111111111111111111111 2019.
[SWZ19b] Zhao Song, David Woodruff, and Peilin Zhong. Towards a zero-one law for column subset selection. Advances in Neural Information Processing Systems, 02:6123-6134 2019.
[SWZ19c] Zhao Song, David P Woodruff, and Peilin Zhong. Relative error tensor low rank ap- proximation. In SODA. arXiv preprint urXiv:1704.0822 2019.
[SY21] Zhao Song and Zheng Yu. Oblivious sketching- central path method for solving linear programming problems. In 38th International Conference on Machine Learning (ICML), 2021.
[SYZ21] Zhao Song, Shuo Yang, and Ruizhe Zhang. Does preprocessing help training over- parameterized neural networks? Advances Neural Information Processing Systems (NeurIPS), 34, 2021.
[SZZ21] Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training multi-layer wver-parametrized neural network in subquadratic time. arXiv preprint arXiv:2112.07628, 2021.
[VL00] Charles F Van Loan. The ubiquitous kronecker product. Journal of computational and applied mathematics, 123(1 (23(1-2):5--000, 2000.
[WR12] Alfred North Whitehead and Bertrand Russell. Principia mathematica, volume 2. Cam- bridge University Press, 1912.
[WY22] David P Woodruff and Taisuke Yasuda. Improved algorithms for low rank approxi- mation from sparsity. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2358-2403. SIAM, 2022.
[W716] David P Woodruff and Peilin Zhong. Distributed low rank approximation of implicit functions of a matrix. In 2016 IEEE 32nd International Conference on Data Engineer- ing (ICDE), pages 847-858. IEEE, 2016.
[WZD+20] Ruosong Wang, Peilin Zhong, Simon S Du, Russ R Salakhutdinov, and Lin F Yang. Planning with general objective functions: Going beyond total rewards. In Annual Conference on Neural Information Processing Systems (NeurIPS). 2020.
[XSS21] Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava. Breaking the linear itera- tion cost barrier for some well-known conditional gradient methods using maxip data- structures. Advances in Neural Information Processing Systems (NewrIPS), 34, 2021.
[XZZ18] Chang Xiao, Peilin Zhong, and Changxi Zheng. Bourgan: generative networks with metric embeddings. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS), pages 2275-2286, 2018
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Please refer to Section 7.
13

---

(c) Did you discuss any potential negative societal impacts of your work? [Yes] Our work theoretical and it provides dynamic algorithm for tensor product-typed problems. We analyze the runtime complexity of our algorithm, which relates to energy con- sumption in practice. We do not foresee potential negative societal impact of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] Please refer to Section 3.2.
(b) Did you include complete proofs of all theoretical results? [Yes] Please refer to Section B, C, D, and E in the supplementary materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "NaMjphkbQZz", "reviewer": "Reviewer_uETh", "summary": "Given an input of $q$ matrices ${A_1, ..., A_q}$ (dimension of the matrices might differ) and a response vector $b$ of size equal to the product of all the input sizes from the $q$ matrices the 'tensor product regression problem' is to find the unknown vector whose dimension is equal to the product of all the dimensions from the $q$ matrices. such that it minimizes the $\\ell_2$ norm of the difference vector between the response vector b and a vector which is a matrix-vector product between the Kronecker/tensor product all the input matrix and $x$ i.e., $||kr(A_1,...,A_q)x - b||_2$.\nThis paper studies a dynamic version of the problem, where at each time stamp some matrix $A_i$ gets updated and the goal is to quickly update the tensor product and also quickly update the solution $x$ (without recomputing it). To solve this problem the author shows how [AKK+20] tree data structure can be used in combination with known sketching techniques. They also show its application to tensor spline regression problems and tensor low rank approximation problems. ", "questions": "I would like the authors to comment on the following questions. \n\n- Since tensor product follows a well-defined structure a bottom-up tree like structure is quite intuitive. Apart from ensuring that all the sketch matrices are independent, can you point out some challenges or subtleties that one should be careful about while using this data structure? \n\n- To realize the novelty, I would like to understand the most non trivial analysis in the paper. Can you explain why it is non trivial?\n\n- How useful is the update time improvement from $O(q)$ to $O(\\log(q))$ while the running time still depends on $d$ where $d = \\exp(q)$?\n\n- In the case of dynamic tensor product regression, at any time stamp, is your update only limited to $A$ or your tree can also handle updates in the response vector $b$? Also, can you handle the case when $B = -A_i$? I mean when the update simply deletes a matrix.\n\n- There are many ways to decompose a tensor, e.g., cp, tucker, tensor train etc. A low-rank approximation based on these decompositions preserves the structural properties of tensors. Can you comment if there are any relation between these decompositions and your low rank approximation in section 8?", "limitations": "Yes, authors do talk about both scope of improvement and extension from the current result in section 9. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper introduces a dynamic tree structure to handle tensor product updates in $O(\\log(q))$ time instead of $O(q)$ time.\n- The paper handles a more generalized version of regression and low rank approximation problems that depend on tensor products.\n- The paper is very well written. I liked reading it.\n\nWeakness:\n- Motivation for the problem is limited. Some experimental results or highlighting the exact improvements in terms of running time/working space compared to naive techniques could help motivate up to some level. \n- Once you build the tree, the majority of guarantees come readily from the existing results. \n- Here d itself is exp(q), so improving the running time in terms of $q$ is less productive. \n\nTypos/suggestions:\n- From line 173, I understand that the leaf $T_i = S_i*A_i$, however in line 200 you use $T_i$ to represent your sketch matrix. If I am correct then the notational inconsistency makes it hard to follow else please fig-1 as an example to explain the outline of tree line-197-209. \n- The sudden introduction of $J_{k,\\ell}$ in line 203 is not clear. Again a relation to the fig-1 might be helpful. \n- In the related work please discuss more about known tensor decomposition techniques and if your low rank approximation can be used to get an approximate decomposition of the known techniques. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JkFIUiVbU9F", "reviewer": "Reviewer_xUrd", "summary": "This paper studies a lightweight computation of a special case of linear regression where the design matrix is given by a tensor product. Specifically, it considers the case where one of the factor matrices temporally changes. The authors propose a tree-based data structure to maintain the sketch of the data so that we can keep up with the temporal changes. ", "questions": "### Q1. Motivation\nI can imagine that the tensor product regression is a fundamental problem and has several applications in machine learning. However, I have no idea about its dynamic extension. I think the authors could elaborate on this direction. More specifically, the application seems to be more limited in the problem setting the paper considered. Namely, for each time step, 1) only a single factor of the design matrix is changed, and 2) the exact location (index) of the factor that changes in time t is given. Can you introduce a few machine learning examples that your method particularly fits? \n\n### Q2. Notations\n- This is not a question but a suggestion. Although the proposed algorithm largely depends on the T-type sketch, its definition is in Appendix. It would be better to move to the main body. \n- What is the role of matrix J? Is it either internal or leaf nodes? It suddenly appears in Section 5 without explanation. \n- The description of Theorem 5.1 is too limited. What parameters do depend on \\epsilon? What is the tradeoff between \\epsilon and the compression efficiency (e.g. the sparseness of \\Pi)?", "limitations": "See Questions. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n1. (quality) Solid, reasonable data structure and algorithm are proposed. \n2. (significance) The error analysis is provided.\n\n\nWeaknesses\n1. (significance) The motivation of the proposed method is not described. See Question 1.\n2. (clarity) Some notations are not clear. See Question 2.\n3. (significance) Empirical evaluations are not provided. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-J0CCJRo5iG", "reviewer": "Reviewer_7iXa", "summary": "The paper considers standard linear algebra problems with two twists on the input. First, the design matrix $A = \\otimes_{i=1}^q A_i$ is a kronecker product of many smaller matrices, and it is these smaller matrices that are given to the algorithm. Second, it is a dynamic setting where, at every point of time, exactly one of the matrices undergoes arbitrary changes (so long as the matrix doesn't change dimension).\n\nIn this \"Dynamic Tensor Product\" setting, the paper studies standard L2 regression, Spline regression (i.e. generalized ridge regression), and Low-Rank Approximation in the Frobenius norm. These problems have been studied in the _static_ tensor product regime, but not the dynamic one, so the new results focus on the improved rates for _dynamic-ness_. They initialize this line of research.\n\nThey show that in this dynamic setting, by maintaining a binary tree of sketches of tensor products of $A_i$ matrices, their algorithms can achieve runtimes $q$ times better than the naive algorithm, where a new static data structure is generated at every update.\n\nThis is a theoretical paper -- there are no experiments. This paper makes no claims about the optimality of their algorithms, and only gives upper bounds.", "questions": "## Big Question\nI have one core question about understanding the technical correctness of the paper:\n> How can a single sketch matrix (e.g. on one of the leaf nodes) be used for arbitrarily many additive updates to the underlying matrix $A_i$?\n\nUsually, my intuition is that sketching a matrix from $n \\times d$ to $O(d) \\times d$ works because we can preserve the exact span of the column of $A_i$ which span a $d$ dimensional subspace, so just $d$ columns suffice. (Suppose $n \\gg d$) So, the sketch matrix just has to preserve these specific $d$ directions in an $n$ dimensional space. However, arbitrary additive updates can arbitrarily change the span of the columns of $A_i$, so an updated $A_i+B_i$ could span a totally unrelated column space. This paper seems to still use the exact same sketch, so that the sketch matrix has to simultaneously maintain accurate sketches for ALL possible spans of $d$ directions in an $n$ dimensional space. Usually, this would requires a sketch of size $O(n)$. \"Update\" (Lines 597-608) doesn't seem to generate any new randomness, so I don't see how this works.\n\n## Middle-Size Questions\n1. Can you include a discussion of the rates of $m$ in the body of the paper? Not really knowing the value of $m$ sticks out like a sore thumb.\n1. Why define statistical dimension in the body of the paper if it's never used in the body of the paper? I'd pull statistical dimension into the discussion of splines in the body of the paper, to make the rate more distinct from that of L2 Regression.\n1. Consider keeping $T_{mat}$ from line 609 of the paper in the rate that appears in the body of the paper, so people can tell what the runtime is if they want to use standard matrix-matrix multiplication. This can really go either way, but I've always appreciated seeing how the GEMM runtime interacts with the algo, since practical implementations of small $\\omega$ algorithms don't exist yet (to the extent of my knowledge).\n1. Can you include a fully elaborated runtime somewhere, without any $\\tile O()$ notation. This would be fine in the appendix.\n1. Theorem 8.1 (Lines 297) doesn't seem to run any faster given the value of $k$, while the static algorithm seems to benefit quiet a bit. When is the dynamic algo faster for $k=O(1)$? I'm thinking of the $O(qd^{3.5})$ runtime from above, and $O(qd \\text{poly}(k/\\varepsilon))$ sounds much worse.\n\n## Small Notes\n1. [Lines 106-108] Short paragraph seems unnecessary. The subsection headers too.\n1. [Lines 127-130] Sarlos doesn't seem to define a ridge based definition of OSE in his paper. Be sure to cite wherever this notion came from, be it Mahoney or Musco or whoever is the author of this notion of regularized subspace embedding.\n1. [Lines 123-133] None of these definitions seem to be used anywhere in the body of the paper. If they all are just used in the appendix, then just define them in the appendix.\n1. [Line 141] Should be $\\sigma_1$ and $\\sigma_2$, not just $\\sigma$\n1. [144 - 146] Remove \"will\", move \"in Appendix A\" to be before the colon.\n1. [157] Clarify that $b$ is fixed at the beginning of the process.\n1. [171] Clarify which linear dependence on $q$ you're referring to. No runtimes have been stated yet, so this is odd to see. Also, clarify that it'll still be exponential in $q$, but that because one one of the $q$ matrices is being changed, the runtime should roughly be a $1/q$ fraction of the static algo's runtime.\n1. [199] (Related to previous questions I asked), specify some rate on $m$\n1. [203] What is $J_{k,\\ell}$? It's a new symbol and it isn't clearly defined in this paragraph.\n1. [206] Remove the comma after $S_i \\in R^{m \\times m^2}$\n1. [207] Consider citing something for the fast matrix-vector product runtime, or specifying why this can be done quickly.\n1. [231] $\\Pi^q$ is not the matrix $\\Pi$ multiplied to itself $q$ times (at least, I don't think it is...). So, consider using a different symbol. Why not just $\\Pi$, without any $q$?\n1. [279] Add \"such that\" before \"with\". Remove \"such the\".\n1. ", "limitations": "No concerns", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper initializes an interesting line of research, it is very clearly and well written, it has a single core observation that explains the design of their algorithm and their improved runtimes. **It's a clean and easy paper to accept, but nothing groundbreaking.** I elaborate below.\n\n## Originality\nThe paper has two cores of originality:\n1. Initializing the research of dynamic tensor products regression and low-rank approximation\n1. Designing a dynamic data structure that can outperform repeatedly building the static data structure\n\nThe first point is stronger, since there seems to be no particular prior work on this precise problem, and because tensor product data does arise in practice (Lines 21-28). The second point is a bit weaker since the problem statement allows for updates to be *very* small -- just changing one of the $q$ base matrices, so an algorithm with updates that are $q$ times faster than rebuilding from scratch is ... believable. The way that the paper builds and updates matrices via sketches is nice and the intuition is clear, but it's hard to ascribe the construct a huge weight of novelty.\n\n## Significance\nThis ties closely into the \"Originality\" section above. The paper's new line of research, on specifically _dynamic_ tensor product regression and low-rank approximation, is conceptually significant. I don't want to undersell how important it is to formally design a theoretical problem. It can be hard to translate an intuitive notion like \"tensor product regression, but in a dynamic setting\" into a formal problem statement. Formalizing this is a legitimate contribution. That said, for a paper with no experiments which introduces a new problem to solve, I feel it is very important to state why your specific definition of a dynamic setting is meaningful. Recall their definition of the dynamic setting:\n> At every time point, one matrix $A_i$ in the kronecker product $A = \\otimes_{i=1}^k A_i$ changes arbitrarily.\n\nWhy is this the natural setting of dynamic tensor product regression that people in downstream applications would care about? For instance, the authors specifically site how large graphs are modeled as tensor products of smaller graphs, and that these smaller graphs can change dynamically as (eg) social networks evolve (Lines 36-41). Why should I expect a small update to a social network to appear as a single arbitrary change of only one of the $A_i$ matrices, and not as a super-sparse change to all of the $A_i$ matrices? Why doesn't the response vector $b$ change with each update? While the authors argue that dynamic tensor product regression is natural, **they don't justify their precise formulation of the problem**.\n\nFor significance, it's worth examining the runtimes they achieve in clear detail. The body of the paper, i.e. before the appendix, is all written out in terms of a sketching dimension $m$, whose rates are not clearly stated (Line 199). Taking constant failure probability and constant error tolerance, we can state the runtimes of the static and dynamic algorithms for Least Square Regression pretty clearly:\n- Statically solving Least Squares Regression takes $\\tilde{O}(\\sum_{i=1}^q \\text{nnz}(A_i) + qd^{3.5})$ time\n- Dynamically updating the Least Squares Solution takes $\\tilde{O}(\\text{nnz}(B_i) + d^{3.5})$, where $B_i$ contains the additive changes to $A_i$.\n- _(the details of how I derive these rate are in paragraph are at the end of this text box)_\n\nwhere $d$ is the number of columns of $A$, which is the product of the number of columns in each $A_i$, so generally a very large number even for moderate $q$.\nSo the dynamic runtime improvement is genuinely by a factor of $q$, but a factor of $q$ seems very small compared to $d^{3.5}$. If each base matrix $A_i$ had exactly $d_0$ columns, then $d^{3.5} = d_0^{3.5q}$. So, saving a factor of $q$ time is nice, but the runtime is still prohibitive for even moderate $q$ and small $d_0$.\n\n**Sure, a factor of $q$ times faster is good, but it doesn't tackle the real bottleneck which should be the term that's exponential in $q$.**\n\nOf course, for tensor-shaped problem, this may be very hard to resolve. I mostly intend this little analysis to emphasize the scale of the improvements relative to the runtime of the algorithm. It should be $q$ times faster than the static algorithm, but if both algorithms have runtime exponential in $q$, then saving a linear factor seems relatively meager.\n\n## Clarity and Quality\n\nThe paper is well written overall. I have notes on clarity in the \"Questions\" box below. My only real qualm of clarity is that precise rates for $m$ should be stated in the body of the paper instead of the appendix, and the fact that $m = \\Omega(qd)$ for all given constructions feels somewhat significant.\n\n---\n\n### Showing my work\nI'm taking $m=O(qd^2)$ from Line 618 where I use CountSketch and TensorSketch with constant $\\varepsilon$ and $\\delta$. Then, $md^{3/2} = O(qd^{7/2})$ and $md^{\\omega-1} + d^{\\omega} = O(qd^{\\omega+1})$. Since $7/2 = 3.5 > 3.37 = \\omega+1$, the term $qd^{3.5}$ which arises from the _Initialize_ and _Update_ runtimes (Lines 244, 246) dominates the _Query_ runtime (Line 249). So, the runtime of the static method is $O(\\sum \\text{nnz}(A_i) + qd^{3.5})$ and the runtime of a single dynamic update is $O(\\text{nnz}(B_i) + qd^{3.5})$, even including the time to run the _Query_ procedure.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept