Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides faster algorithms for solving the $\ell_2$ - Kronecker product regression problem, which is a least squares regression problem where the design matrix is a Kronecker product of several smaller matrices with dimensions $I_n \times R_n, n \in [N]$. They also extend their techniques to provide faster algorithms for Kronecker ridge regression, and speed up the Alternating Least Squares (ALS) algorithm for computing the Tucker decomposition of a tensor. Prior work (Diao et.al, 2019) for Kronecker product regression cared about the case where $R_n \gg I_n$ for all $n \in [N]$ and this work improves the runtime when $R_n$ might be comparable to $I_n$ and justify that this case is important through their experiments.

Reference:
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, 2019.
strengths_and_weaknesses: Originality: I am not an expert in this area so I am not entirely sure about other related work and how novel this work's contributions are compared to other papers in the area.

Quality: The submission is technically sound. All claims are well-supported with proofs.

Clarity: The submission is clearly written and well-organized.

Significance: Yes, the problems being studied are significant. Kronecker product regression is a well-studied problem with several applications.

questions: I briefly went over the Diao et.al [16] paper and their runtimes seem to have a factor of $1/\epsilon^2$ (see footnote 9 on page 6) rather than $1/\epsilon$ as claimed on Line 46 of this paper?

Editing suggestions:  
It would be better if you define $\omega$ (along with a reference and an approximate value) before using it on page 2.

Line 93, 260 - “pseduoinverse” -> “pseudoinverse”


limitations: Primarily theoretical work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The work considered the fundamental problem of Kronecker regression and proposed the first sketching-based subquadratic algorithm to obtain a (1+\epsilon)-approximation solution. Both rigorous proofs and empirical validations were shown. The block-sketching methodology can be of independent interests itself.
strengths_and_weaknesses: The work focused on an accelerated solution for a fundamental problem which makes the work very meaningful. The technique itself is quite interesting. The math is well presented and validated by empirical results.
questions: In the experiment part, was fast matrix multiplication methods used? How does the runtime complexity compared to the theoretical results in Theorem 1?
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose the first subquadratic-time algorithm for solving Kronecker regression. Kronecker regression is a structured problem where the design matrix is a Kronecker product of multiple matrices. This problem appears when trying to compute the Tucker decomposition of a Tensor. The use score sampling and iterative methods to achieve a complexity reduction for Kronecker regression problems. Then, they extend their approach to block design matrices. They use synthetic and real examples to demonstrate the computational advantages of their approach. 
strengths_and_weaknesses: The paper reads well, and the English level is satisfactory. I am not familiar with how important the addressed problem is, but the method seems novel with solid justification, both theoretical and empirical. The runtime improvement seems substantial, and the relative error of the algorithm on synthetic data seems low. The related works are reviewed well and proper background to the problem is provided. 
questions:  Can you also provide examples on real data? 
What is nnz on page two? This is now explained.
Perhaps the paper would read better if the theorems can be pushed forward outside of the introduction. 
P5L201 what is s (the scalar s).

limitations: The limitations of the proposed work are properly detailed in section F.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors study fast sketching based algorithms for Kronecker Product Regression and show how this algorithm can be used to speedup Alternating Least Squares (ALS) algorithm for computing Tucker Decomposition. The main improvement over previous work of Diao et. al. [16], which introduced leverage score sampling for Kronecker Product Regression seems to be recognizing that the matrix $M = (K^{\intercal}K +\lambda  I$) can be used as a preconditioner for solving the sketched ridge regression using Richardson's Iteration and showing a way to quickly compute $(K^{\intercal}K +\lambda  I)^+v$ for a vector $v$ using fast matrix multiplication by appropriately dividing the matrices in the Kronecker Product into two disjoint subsets.. Although updating the core tensor in Tucker Decomposition requires one to solve a simple Kronecker Product Ridge Regression problem, the factor matrix update requires one to solve a more complicated Kronecker Product Ridge Regression with a subspace constraint. The authors show that their techniques can be used to solve this version of the Kronecker Product Ridge Regression and therefore all the steps in ALS algorithm for computing Tucker Decomposition are made faster.
strengths_and_weaknesses: Strengths:
- Shows how speeding up Kronecker Product Ridge regression helps in running ALS for Tucker Decomposition. This wasn't observed in the previous works [15,16].
- Improving the running times over previous work by observing that solving the sketched problem using Richardson Iteration with $(K^{\intercal}K + \lambda I)^{+}$ is preconditioner leads to faster running times.

Weaknesses:
- The paper doesn't have any new contributions for sketching literature. Note that sketching a submatrix $A_1$ by leverage score sampling rows of $A_1$ using leverage scores with respect to $A_1$ obviously works because of the property that leverage scores only decrease when the new rows are added. This observation is not new and can be seen in the paper "Sharper Bounds for Regularized Data Fitting".
- It is not clear how the authors claim input sparsity running times for Kronecker Product Ridge Regression when in their algorithm, they compute singular value decompositions of $A_1,\ldots, A_N$. If one doesn't compute singular value decompositions, how is $(K^{\intercal}K + \lambda I)^{+}$ used as a preconditioner? Am I missing something here? I understand input sparsity time algorithms are probably not necessary for intermediate problems of ALS for tucker decomposition as one cannot guarantee that the intermediate matrices will be sparse but how is the claim in Theorem 1.1 correct?
- Writing could be a bit better by introducing Tucker Decomposition in the introduction. I found it a bit hard to follow without knowing what the core tensor and factor matrices are. This is probably not that big an issue as the target audience are aware of the terminology.

Some typos:
- In definition 3.2, you also need to state that $\||p\||_1 = 1$ -- not a big problem
- Missing $\||\cdot\||_2$ at a few places like in Corollary 3.5

———————————————————————————————————————
Update after author responses:
- Authors answered my questions and made a few changes to the manuscript which address most of my concerns.
- Although the paper does not contribute to the sketching literature as I said earlier, there are a lot of details and new techniques required to apply the existing techniques to the important problem of Tucker Decomposition which lead to my acceptance decision.
questions: - Can you clarify my doubts about the input sparsity claims in Theorem 1.1?
- I am confused about where Theorem 4.5 is used in $\texttt{FastKroneckerRegression}$. Isn't the only product of a vector with a kronecker product in line 13? And the vector there isn't sparse. Am I missing anything in regards to where it is used?
- If I understand correctly, the main speedup over [16] is obtained by not computing the product $\tilde{K}^{\intercal} \times \tilde{K}$ and instead using the Richardson's iteration which using Fast Kronecker Product you can perform quickly? Can you explain how the term $\tilde{O}(\text{MM}(\Pi_{n \in T} R_n, R\varepsilon^{-1}, \Pi_{n \notin T}R_n))$ arises in line 13?
- How does solving intermediate problems of ALS to a small approximation affect the overall convergence? I'd think it shouldn't be affected too much but do you have any small experiments where you observe anything significant?
- Please let me know if I am misunderstanding or missing anything. I can take a closer look at sections in the appendix if they are explained there better.
limitations: NA
review_title: null

Meta-review: metareview: All reviewers felt that this paper made a solid technical contribution on algorithms for Kronecker regression and should be accepted to the conference.

confidence: Less certain
Decision: Accept