-Regression in the Arbitrary Partition Model of Communication

We consider the randomized communication complexity of the distributed $$ -regression problem in the coordinator model, for $$ . In this problem, there is a coordinator and $$ servers. The $$ -th server receives $$ and $$ and the coordinator would like to find a $$ -approximate solution to $$ . Here $$ poly(nd) for convenience. This model, where the data is additively shared across servers, is commonly referred to as the arbitrary partition model. We obtain significantly improved bounds for this problem. For $$ , i.e., least squares regression, we give the first optimal bound of $$ ) bits. For $$ , we obtain an $$ upper bound. Notably, for $$ sufficiently large, our leading order term only depends linearly on $$ rather than quadratically. We also show communication lower bounds of $$ for $$ and $$ for $$ . Our bounds considerably improve previous bounds due to (Woodruff et al. COLT, 2013) and (Vempala et al., SODA, 2020).