Data subsampling for Poisson regression with pth-root-link

Summary

the paper considers sampling for Poisson regression, making explicit the dependence of the size of coreset on various parameters, in particular the effect of different link functions. The paper has a theoretical flavor

Strengths

the results seems to be new

Weaknesses

Frankly I am not familiar with this particular approach. One possible weakness may be that it is not clear how sharp this result is. It is also not clear what characteristics of Poisson regression make the study entirely different from many other regression models. I submit this particular review early so the chair may decide whether to look for additional reviewers.

Questions

none

Rating

6

Confidence

1

Soundness

3

Presentation

2

Contribution

3

Limitations

seems there is little discussion on limitation

Summary

Coresets are a technique in efficient algorithms for data analysis in which a dataset is compressed into a weighted subset of its examples. Typically, coresets are constructed such that a loss function for a given optimization problem (e.g. linear regression, logistic regression, or Poisson regression for this work) is preserved up to a $(1\pm\epsilon)$ factor error. This work extends this line of work to handle the Poisson regression case. While the most popular choice of the log-link does not admit small coresets, the authors study the case of the ID and square root link functions and show that for these log-link functions, Poisson regression admits small coresets, assuming the smallness of a complexity parameter $\rho$ which they introduce building on prior work on logistic regression.

Strengths

This work shows that under certain natural (and necessary) modifications, Poisson regression admits small coresets. Coresets are a popular topic of study in the recent machine learning literature, and this work makes progress on understanding coresets for Poisson regression.

Weaknesses

The first main weakness of this work is that there are many modifications and assumptions that must be made to the Poisson regression in order to obtain small coresets. As the authors mention, the canonical log-link for Poisson regression does not admit small coresets, and this is a standard fact in the literature (e.g. formalized in [23], as the authors cite). Thus, the authors instead consider a polynomial link function, but the authors do not provide sufficient arguments as to why this is still an interesting problem to study, either from a theory or practice perspective. Indeed, once the growth rate of the function is polynomial and one assumes a balancedness condition, then small coresets can be constructed using known techniques in theory [24]. While this type of result may still be interesting if the regression problem is widely studied, Poisson regression with noncanonical links seems too artificial of a setting to be interesting for a wide audience. The second main weakness is that the techniques largely are a straightforward generalization of techniques from [23, 24, 25] and the conclusions do not seem surprising given the prior work.

Questions

How are Lemmas 6.1 and 6.2 different from the lower bound argument of Theorem 6 in [23]?

Rating

7

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

See weaknesses.

Summary

This paper demonstrates the theoretical bound analysis on data subsampling for Poisson regression with ID-link and root-link functions based on coreset method and the leverage of $\ell_r$ norms to the loss function. The $\text { ‘ } \rho \text {-complex’ }$ is a novel meaningful parameter for data compressibility under the context of subsampling and is a good starting point of theoretical construction.

Strengths

This paper provides a way of subdividing the set of input functions into groups to obtain an improved $O(d)$ bound for VC-dimension. The overall bounds by combining VC dimension and total sensitivity is convincing and the proof is detailed for cases where $p \in\{(1,2)\}$.

Weaknesses

This paper lacks a well-constructed structure, as it does not clearly introduce important concepts, provide a detailed discussion of related work, or include a summary or conclusion. To improve clarity, the proposed data subsampling techniques for Poisson regression might be presented in a pseudo-code format. While numerical simulation is not necessary, it would be a beneficial addition.

Questions

The notation is a bit confusing for the Poisson regression models: is the discussion restricted to $p \in\{(1,2)\}$ cases so the notation in e.g., 119 line, are in scalar format? The notation should be more generalized as in Theorem 3.8.

Rating

6

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

The authors should consider restructuring the entire paper to clearly state the introduction, the proposed method along with its bound analysis, and the limitations and conclusion. Although the problem statement, proof, and results are meaningful, they lack clarity for the readers. Additionally, a major concern is the limited cases to which the analysis can be applied, specifically only for $p \in\{(1,2)\}$. This limitation significantly undermines the generalizability of the proposed method.

Summary

For Poisson regression, where the outcome variable is a positive integer, the paper provides sublinear coresets under certain assumption on the data characterized by parameter $\rho$. The link function is the $p^{th}$ root link function with $p = 1 , p=2$. Without any assumptions the authors show that no sublinear size coresets are possible, in fact, they show lower bound results for any other data reduction techniques also. For $p = 1 , p=2$ and the parameter $\rho$, the coresets are constructed using the standard sensitivity framework which involves calculating sensitivity upper bounds and bounding the VC-dimension. For other values of $p$, the authors show that their technique and analysis is not sufficient to get an $\epsilon$-coreset.

Strengths

1) Though the paper is very similar in structure and high-level ideas to the paper "On Coresets for Logistic Regression", extending those ideas to the setting of Poisson regression is non-trivial. The paper appears solid in terms of theoretical contributions. 2) The writing of the paper is generally very good. Though the proofs are in the appendices, high level ideas and intuitions are provided in the paper for most of the results in the main part. The trick to shift the domain to get sensitivity upper bounds is neat and may find interest in the community working on coresets.

Weaknesses

The only main weakness I think is the lack of any experimental results in the paper. Some small set of proof-of-concept experiments would have further strengthened the paper. There are some small issues with writing. $x$ in $R^d$ is described in terms of its coordinates $1, x_1, x_2 \dots x_{d-1}$. However later $x_j$ is used to denote the $j^{th}$ vector in the dataset. The writing in the final part of the paper appears rushed, may be due to space constraints. The authors talk about Lambert functions however there is no introduction as to what they are. It is difficult for readers not familiar with the concept.

Questions

This may be basic question, maybe I am mission something, the feasible $\beta$ is such that $x_i\beta > 0$ is for the pth-root link or it will also hold in case of ID-link Poisson regression?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

see weaknesses