Near Optimal Sketching of Low-Rank Tensor Regression
We study the least squares regression problem
where ⇥ is a low-rank tensor, defined as
. Here, denotes the outer product of vectors, and A(⇥) is a linear function on ⇥. This problem is motivated by the fact that the number of parameters in ⇥ is only R · P
p d number of parameters in ordinary least squares regression. We consider the above CP decomposition model of tensors ⇥, as well as the Tucker decomposition. For both models we show how to apply data dimensionality reduction techniques based on sparse random projections 2 R m⇥n , with m ⌧ n, to reduce the problem to a much smaller problem min ⇥ k A(⇥) bk 2 2 , for which k A(⇥) bk 2 2 = (1± ")kA(⇥) bk 2 2 holds simultaneously for all ⇥. We obtain a significantly smaller dimension and sparsity in the randomized linear mapping than is possible for ordinary least squares regression. Finally, we give a number of numerical simulations supporting our theory.
where ⇥ is a low-rank tensor, defined as ⇥ = P p d number of parameters in ordinary least squares regression. We consider the above CP decomposition model of tensors ⇥, as well as the Tucker decomposition. For both models we show how to apply data dimensionality reduction techniques based on sparse random projections 2 R m⇥n , with m ⌧ n, to reduce the problem to a much smaller problem min ⇥ k A(⇥) bk holds simultaneously for all ⇥. We obtain a significantly smaller dimension and sparsity in the randomized linear mapping than is possible for ordinary least squares regression. Finally, we give a number of numerical simulations supporting our theory.
*Summary*
This paper studies the tensor L2 regression problem and proposed to use matrix sketching to reduce computation. 1+epsilon bound is established to guarantee the error incurred by sketching.
I don't like the writing. First, there is little discussion of and comparison with related work. Second, the proof in the main body of the paper is messy, and it takes much space which could have been used for discussion and experiments. Third, the use of notation is confusing. 
Some claims in the paper seems false or suspicious. I'd like to see the authors' response. I'll adjust my rating accordingly. 
*Details*
I'd like to see the authors' response to Questions 2, 4, 9, 10.
1. I don't find the description of your algorithm anywhere. I don't find the time complexity analysis anywhere. I want to see a comparison of the computational complexities w/ and w/o sketching.
2. How is this paper related to and different from previous work, e.g., [32], Drineas's work on sketched OLS, and tensor sketch? For example, if A is matrix, which is a special case of tensor, then how does your bounds compare to Drineas's and Clarkson&Woodruff's?
3. The notation is not well described. I look back and forth for the definition of D, p, r, R, m, s, etc.
4. In Line 67, it is claimed that no assumption on incoherence is made. However, in Line 169 and 231, there are requirements on the max leverage scores. How do you explain this?
5. There are incompleteness and errors in the citations.
* There are numerous works on sketched OLS. These works should be cited telow Eqn (6).
* In Definition 5: SJLT is well known as count sketch. Count sketch has been studied in numerous papers, e.g,
Charikar et al: Finding frequent items in data streams. 
Clarkson & Woodruff: Low rank approximation and regression in input sparsity time 
Meng and Mahoney: Low-distortion subspace embeddings in input- sparsity time and applications to robust linear regression 
Nelson & Nguyen: Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. 
Pham and Pagh. Fast and scalable polynomial kernels via explicit feature maps 
Thorup and Zhang. Tabulation-based 5-independent hashing with appli- cations to linear probing and second moment estimation
I don't think [11] is relevant.
6. How does this work extend to regularized regression?
7. Line 182: How is the assumption mild? The denominator is actually big. Matrix completion is not a good reference; it's a different problem.
8. The synthetic data in the experiments are not interesting. Sampling from normal distribution ensures incoherence. You'd better generate data from t-distribution according to the paper
* Ma et al: A statistical perspective on algorithmic leveraging.
I'd like to see real data  experiments to demonstrate the usefulness of this work.
9. The title claims "near optimal". Why is this true? Where's your lower bound?
10. Tensors are rarely low-rank; but sometimes they are approximately low-rank. How does your theory and algorithm apply in this case?
=== after feedback ===
I appreciate the authors' patient reply. I think my evaluation of the technical quality is fair. I won't change my rating.