Data subsampling for Poisson regression with pth-root-link

We develop and analyze data subsampling techniques for Poisson regression, the standard model for count data y N. In particular, we consider the Poisson generalized linear model with IDand square root-link functions. We consider the method of coresets, which are small weighted subsets that approximate the loss function of Poisson regression up to a factor of 1 ε. We show Ω(n) lower bounds against coresets for Poisson regression that continue to hold against arbitrary data reduction techniques up to logarithmic factors. By introducing a novel complexity parameter and a domain shifting approach, we show that sublinear coresets with 1 ε approximation guarantee exist when the complexity parameter is small. In particular, the dependence on the number of input points can be reduced to polylogarithmic. We show that the dependence on other input parameters can also be bounded sublinearly, though not always logarithmically.