Kronecker regression is a highly-structured least squares problem min_𝐱‖𝐊𝐱 - 𝐛‖_2^2, where the design matrix 𝐊 = 𝐀^(1)⊗...⊗𝐀^(N) is a Kronecker product of factor matrices. This regression problem arises in each step of the widely-used alternating least squares (ALS) algorithm for computing the Tucker decomposition of a tensor. We present the first subquadratic-time algorithm for solving Kronecker regression to a (1+ε)-approximation that avoids the exponential term O(ε^-N) in the running t…