Data subsampling for Poisson regression with pth-root-link
Authors: Han Cheng Lie
Alexander Munteanu
Venue: NeurIPS 2024 poster (2024)
Keywords: Poisson regression
subsampling
coresets
Lambert function
Primary area: learning_theory
TL;DR: We show novel results on data subsampling for approximating Poisson regression via coresets, as well as their limitations.

Abstract: We develop and analyze data subsampling techniques for Poisson regression, the standard model for count data $y\in\mathbb{N}$. In particular, we consider the Poisson generalized linear model with ID- and square root-link functions. We consider the method of \emph{coresets}, which are small weighted subsets that approximate the loss function of Poisson regression up to a factor of $1\pm\varepsilon$. We show $\Omega(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\pm\varepsilon$ 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. In particular, we show that the square root-link admits an $O(\log(y_{\max}))$ dependence, where $y_{\max}$ denotes the largest count presented in the data, while the ID-link requires a $\Theta(\sqrt{y_{\max}/\log(y_{\max})})$ dependence. As an auxiliary result for proving the tightness of the bound with respect to $y_{\max}$ in the case of the ID-link, we show an improved bound on the principal branch of the Lambert $W_0$ function, which may be of independent interest. We further show the limitations of our analysis when $p$th degree root-link functions for $p\geq 3$ are considered, which indicate that other analytical or computational methods would be required if such a generalization is even possible.

Data subsampling for Poisson regression with pth-root-link
Han Cheng Lie Institut für Mathematik Universität Potsdam Germany hanlie@uni -oo.duummppttddmmdde
Alexander Munteanu
Department of Statistics TU Dortmund University Germany
alexander www..eaeeeettttd-drooddddddeood
Abstract
We develop and analyze data subsampling techniques for Poisson regression, the standard model for count data E N. In particular, we consider the Poisson generalized linear model with ID- and square root-link functions. consider the method of coresets, which are small weighted subsets that approximate the loss function of Poisson regression up to a factor + E. We show 2(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 domain shifting approach, show that sublinear coresets with + & approximation guarantee exist when the complexity parameter is small. In particular, the dependence the number of input points be reduced polylogarithmic. We show that the dependence on other input parameters can also be bounded sublinearly, though not always logarithmically, In particular, we show that the square root-link admits an (llg(yymad dependence, where Ymnx denotes the largest count presented in the data, while the ID-link requires a O( (///max// log( (max)))))) dependence. As an auxiliary result for proving the tightness of the bound with respect to Umax in the case of the ID-link, we show an improved bound on the principal branch of the Lambert Wo function, which may be of independent interest. We further show the limitations of our analysis when pth degree root-link functions for Z are considered, which indicate that other analytical or computational methods would be required if such a generalization is even possible
Introduction
Random sampling is arguably of the most popular approaches to reduce large amounts of data to save memory, runtime, and further downstream resources such as communication bandwidth and energy. In contrast, classic statistical learning theory often uses uniform sampling and provides only asymptotic approximation guarantees. These guarantees often require strict assumptions such as i.i.d. data and for model assumptions be met exactly. However, data collected from real applications often violate these conditions: only finite samples are available, independence might not be satisfied, and the model may deviate from reality. When model fitting algorithms applied to such data, are not only interested in reducing the above-mentioned resource requirements, but also in providing rigorous worst-case guarantees approximation.
Arguably, the most popular approach is the Sensitivity Framework 26 19 which provides a general- coreset that given
purpose importance sampling scheme that yields a weighted subsample data matrix X approximates some loss function f(XB) within a factor (1 + :) for any query point 3. This guarantee can be stated as follows: significantly smaller subset K C X, k == [K] <<< [X]
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

together with corresponding weights E R is a (1 + E) coreset for X if it satisfies
V3 E R²: 1S(X3) J.m (K 3)] S s ((x
(I)
We point the interested reader to
37
35
32] for a gentle introduction and overview on coresets.
Our aim is of course not only to obtain good approximation accuracy as stated in Equation (I)
but also for the subsample achieving the bound to be sublinear in the imput size. Unfortunately. most generalized linear models do not admit strongly sublinear data summaries with reasonable
approximation guarantees [3 B1]. This also holds for the Poisson models considered in this paper.
To go beyond the worst-case setting and enable meaningful data reduction, a natural approach is to parameterize the analysis with a quantity that captures the fit of data to the statistical model and quantifies the achievable size of succinct data summaries [36]. Another ingredient that is commonly used to tackle data reduction for generalized linear models relate their loss l, norms, for which
Ep sensitivities or leverage scores yield viable importance sampling distributions [6 12 36 34
1.1 Our contributions
We provide the first rigorous analysis for (1 + E) -approximate data reduction for Poisson models:
1. We show ((n) lower bounds against coresets for Poisson regression (Lemma 6.1]. showing that changing the link function alone does not resolve the problem of bounding the com- plexity of coresets for the log- bog-,ink, which is incompressible. Our lower bound extends to arbitrary data reduction techniques up to a log(n) factor (Lemma 6.2).
2. We introduce novel complexity parameter p that captures the compressibility of data under a Poisson yth-root-link model (Equation (2)) This parameter corresponds naturally to the statistical model assumptions and establishes a relationship between these assumptions and an optimization perspective of the compressibility problem.
3. We conduct a parameterized analysis, showing that sublinear coresets exist under the statistically natural assumption of small parameter (Theorem 3.8), and using a novel domain shift idea for their optimization [Thoremm 4.2)
4. We prove a square root upper bound for the Lambert Wo function over [-1/e, 0) [Lemma 6.3) that allows us to prove tight bounds for the slope of a linear lower enve- lope <emma 6.4). This justifies an Ô ((vhuaxx)) dependence for the ID-link, which is contrasted by an (log (ymax)) dependence for the square root-link.
5. We show the limitation of our domain shifting approach, showing that the error of this method cannot be bounded give the required (1 + =) approximation for p 2 3 (Lemma 6.5). This indicates a limitation to the common choices E [1,2), and suggests that different techniques than the ones we develop below may be needed to overcome this limitation.
1.2
Our techniques
The general outline of our analysis follows the established method of sensitivity sampling 26 19 Several steps along this outline require novel ideas due to peculiarities of the Poisson loss function defined in Equations (3) and below. A VC dimension bound of d? is easy to obtain by counting the number of arithmetic operations required to compare an individual loss to a given threshold as measure of complexity [4) A near-linear (d/e) bound is obtained by a more fine-grained analysis, by grouping and rounding the associated count data (respectively, sensitivity scores) powers of (1++) e) (resp. to powers of 2). This results in surrogate loss function that admits group-wise linear VC dimension, by splitting the domain of each loss function at its unique global minimum into two regions such that the restriction of the function to each region is monotone, and connecting the resulting construction to hyperplane classifiers. Approximating the surrogate finally implies the desired (1 + e) approximation for the original loss as well.
For bounding the sensitivities, the domain of the loss function g(2) is split into three intervals: 1) one interval consisting of 'moderate' values of 2, such that the g(2) values are bounded above and below within constants and can be treated using simple uniform sampling: 2) one interval where has large
OÔ)) hides lower order log terms, analogous notation applies to all Landau symbols.

---

values, in which case g(2) is closely related to 2"; 3) one interval, where 2 is close to 0, in which case the negative logarithm dominates the loss.
Tackling the interval in 2) requires relating the loss function (y(2) to 2P. Specifically we would like bound =" 9y(2) =² /A for sufficiently large and for some value of X. This requires special care, since the loss function gy (2(22) is translated polynomially towards larger values of 2 with growing y, but the minimum of 9y(2) grows only logarithmically with y. Informally speaking, the loss function 'widens', and its minimum 'moves mainly to the right', so for large y, we would need a very flat lower bound, which requires large À = y (ignoring polylogarithmic terms). However, this is undesirable, since À appears to be crucial parameter for bounding the subsample size. Specifically, this would yield a EiE(n] 3: = (2()) dependence in the coreset size. So instead, we bound the loss
roughly as 2" 2 gy(2) 2 (2- (2-y1/7)/ ///r//>, />, which amounts to translating the lower envelope with growing y as well. Additionally, we introduce a novel complexity parameter p which balances the translated (z - -yy/pjp lower bound with the 2" upper bound. We stress that these translation and balancing arguments are not artificial just used to make calculations go through, but they are naturally consistent with the statistical model (see the discussion below [Equation (2)). This proof strategy eventually captures the loss function within interval 2) more closely and yields sublinear bounds for À as well.
We remark that in contrast to j-complexity in previous work 33 34 bounded balancing complexity parameter p does not handle the asymmetry between intervals 2) and 3). Tackling the interval in 3) thus also requires completely new ideas, as the negative logarithm has an infinite asymptote at 0, which we exploit to prove (2(n) lower bounds on subsample size in Lemma 6. Lemma 6.2 Such asymptotes have not been mentioned or analyzed in previous related work on sensitivity sampling for GLMs. To circumvent the lower bound, we avoid this interval by introducing novel domain shifting approach, requiring all feasible solutions to satisfy = > 1j for a suitable v > 0 for optimization. Choosing 7) in the order of e, we can argue that the solution in the shifted domain is a (1 + e) approximation. Avoiding the asymptote enables a coreset construction for the shifted domain.
We believe that the domain shifting approach is necessary: if an instance consists of the extreme points on the convex hull, and all but small (sublinear) number of points are separated by an distance to the boundary, then required structure is already in the data. But if non-extremal points are allowed to be arbitrarily close to the boundary, and we do not shift the domain, then we will not avoid high sensitivity points that are strictly inside the convex hull. Then the coreset size would necessarily depend on the distance of these non-extremal points to the boundary, and crucially on the number of points that are very close to the boundary of the convex hull, which again can be M(n).
Exploiting the asymmetry between the intervals and 3) where the loss exhibits =" and - log(=) growth respectively, we prove (2()) lower bounds on subsample size, by adapting known reduction We also provide lower bounds on parameters used in our analysis, showing their tightness. In particular, the aforementioned À slope parameter is of size e(Vu/ log(y)) in the case p = 1. The proof is conducted by an exact characterization of the tangent point between our linear lower envelope and the loss function. Since this requires balancing between and log(z) and examining the log(y!) function, further bounds rely on Stirling's approximation and the principal branch of the Lambert Wo function. Recent bounds in [38] for the Lambert Wo function imply square root upper bound but only a cubic root lower bound. We thus significantly tighten their bound in appropriate interval. This result may be of independent interest, since the Lambert function cannot be expressed in terms of elementary functions and has many important applications in various fields. As result, obtain matching square root lower bound on À in our context.
techniques [3 36 41
1.3 Related work
Classic work on data subsampling started with linear &g regression [16] and was extended to linear lp regression [12]. More recently, the study continued with non-linear transformations such as in
generalized linear regression models. The first guaranteed finite subsample bounds for logistic regres-
sion appeared in (36,, while impossibility results for Poisson regression were given in [1]. Research on generalized linear models was continued for Probit regression [4]. Asymptotic properties of subsampling for generalized linear models, including for Poisson regression, were studied in 3 27
A mnite-sample size result is given in 3 Theorem 5] that exhibits O(V approximation error.
13
3

---

studied a sampling- based feature space reduction for wide array of generalized linear models with additive errors. However, parts of their assumptions specifically do not apply Poisson regression.
2 Preliminaries and the Poisson pth-root-link model
Poisson regression models aim to predict a count variable Y E No using a generalized linear model with link function h I R, i...
((E [x)) = =x,3,
where x (1, (1) ,.,,, ()) E IR is row vector, and 3 E 12 is column vector carrying the model parameters that in particular include an intercept 31 [3) Common choices for / are the canonical log-link h(v) = In(v), the ID-link h(r)) v, and the root-link l((v) = v1/2_ The latter
two can be cast into a general framework by introducing the pth-root-link h(v) = v v1/0, for any R 3 p 1, where the ID-link and root-link correspond to p E {1,2] [10]
Subsampling for the log-link is not possible with the multiplicative (1 + 8) error guarantees that we aim for, since it entails preserving the exp(x;3) function 311. We will also show impossibility results for the pth-root-link. However, we parameterize our analysis with a data-dependent parameter that reflects naturally how well the realized data distribution is captured by the Poisson model. This parameter is inspired from previous work [6]: we will refer to data X, y as being p-complex: there exists 0 < o oo such that denoting by x, the j-th row of the data matrix X E ga and by Vj the j-th entry of the vector y E No. holds that
Σラ=1 3
sup BER
/mp S.p.
We may interpret the parameter P as follows. The rate parameter of the predicted Poisson distribution is B(Y u²) = (a: Hence, the mean and variance of Yj given zij is (zz,)), for each j = 1,...,.... To obtain the maximum likelihood estimator of B, we seek 33 such that for every j = 1, ,,.... n1, x is
as close possible to / since Vj 1/p minimizes the jth summand Iu; of the loss function specified
in Equations (3) and (4) below. However, choosing 33 so that [r, Vjj 1/p| is small will imply that each summand in the numerator of Equation (2) will be close to y, j/p In this case, the variance of the (Yz)ā=1 will not be captured effectively by the Poisson model, and p will be large. Thus, smaller values of p. i.e., values of p that are closer to 1, indicate that the true data distribution is better captured by the Poisson model. Thus the p parameter in |Equation (2) plays similar role of quantifying model fit as the pm (X) parameter from [36] Section 2]; see in particular the comments at the end of that section.
Assuming that the value of p is small allows us to use the proximity of the negative log- likeelild to L. norms, together with some novel optimization ideas involving shifted domain. This yields the first provable finite and sublinear subsample size with rigorous (1 (1+2 E) approximation guarantee. We focus on the special cases p E {1, since they the most popular (in fact the only practical) alternatives to the intractable log-link 10 31. The ID-link has been used in epidemiology [40] 29].
(39] and to account for misspecification bias in maximum likelihood estimation [7]. When the estimated mean count of the data is zero, then the canonical log-link causes problems that can be avoided by using the root-link: see e.g. (28) Section 5.4]. We also discuss in our lower bounds section other choices for and show that for any natural number p the bound implied by our novel shifting idea must fail. This bound is crucial to obtain our final approximation. indicating that other methods would be required to tackle a generalization for p 2 3, if this is even possible.
The root-link function has been applied forecasting for queueing systems
Given parameters 3 and an input x, the rate parameter of the predicted Poisson distribution is / == E x) (x;)),
which corresponds to its mean and variance. Its probability mass function is P(Y = y) = Poisson ..56) = ~M (x e tzgp Given a set of i.i.d. observations expressed as the rows x; of data
y!
y!
matrix X add with corresponding labels E Ni we can obtain a maximum likelihood estimate of the parameter 3 by minimizing the negative log-likelihood, which takes the form
[x(33)= = Σn Iy. (x:3)= = Σn 1=1 (xx3)P - pys In (xx33) + In(y:!)
(3)
4

---

where
9y. (2,35) :- (z, py, lzg log(y.!).
(4)
For any pth-root-link, the loss function includes log(x:3) term, which restricts the feasible set to all such that for all z4, 2 E [m] it holds that z,, > 0. We note that for summands corresponding to Y/ 0, the function go(2) simplifies to go(2) = 2 > 0 with well-known properties of the lp norm.
We thus focus on summands Jy, for yE E N below.
For arbitrary y E N, the function (y(=) 2" py In(2) + In(y) on Ry0 is strictly convex with first and second derivatives (z)2) pz - and 0[(2) - p(p -1) + E > 0 respectively,
Thus gy (z) decreases on the interval E (0.))/), increases on (yl/P, oo), and has a unique minimizer at z" / with corresponding value y - y log(v) log(v!) ~ & log(v) + @(1) > 1 by Stirling's approximation. We shall use the following lower bounds to capture the y-dependence.
Lemma 2.1. It holds for all E Ry0. p E [1, y E that
(2(2) 2 - -py (og())()) log(y!) 2 max {1 plog(E))
The next two results bound the individual loss contributions from above and below by roughly a value of zP, For the lower bound, however, we note that as the value of y grows, the loss function is translated polynomially towards larger values, since its minimum is attained x y'/p. However, by Lemma 2.1, and the properties above, the increase of 9,(2") ) is only logarithmic in =*, and thus also logartthmic in y. Denote by À the scaling parameter of the lower bound on By given in Lemma 2.2. Then the logarithmic growth of (y()) implies that we would need = y/ log(v). Unfortunately, the value of À will affect the coreset size, which is undesirable, since it can become linear simply due to large values of y. We thus require a sublinear dependence on ymax. i.e., the largest value of y presented in the data. To this end, we shift the lower envelope by the minimizer The value of À can subsequently be bounded in desirable way, but differs significantly 1 we prove À Ol y/ log(y)) to be sufficient, while
2" 2"= y /p_ depending the value of p. in the case the case p = 2 even constant À = 1 will suffice. In Section 6 we will show a separation by a superconstant and matching square root lower bound on the value of X in the dominating case 1.
Lemma 2.2. For any p 2 1 and y N it holds that z² 2 gn for = > y2/P. Ifp 1, then for some À E O( /v log(y)), it holds that gy(z) > (2 (3-
x for y2/p.
Lemma 2.3. Let p 2 2 and y E N, and x = 1. Then gy(2) 2 (z-w/en for > y y1/v.
3 Coreset construction
We begin by summarizing some key aspects of the sensitivity framework. Formal definitions for the sensitivity framework (including sensitivities, the VC dimension, and the main subsampling theorem) are given in Apppenddxx
In the sensitivity framework, the goal is to obtain coresets using importance sampling techniques to approximate loss functions (26). Given loss function whose value depends on a collection of input points, the main idea of the framework is measure the sensitivity of any input point in terms of its worst-case contribution to the loss function. More precisely, given point Jy, its sensitivity for the loss function of the form f(Xn) Σje(n ((2,7) is given by
g(
oj = sup f(Xn)
The main subsampling theorem. Proposition A.5 combines the sensitivities together with the theory of VC dimension. The idea is to sample points according probabilities that are proportional to the sensitivities, in order to create an appropriately reweighted subsample of the initial collection of points. Suppose the total sensitivity S Σje(n Jj of the points and the VC dimension A associated with a set system based on the summands g(xar)) in the loss function f(Xr) are bounded, and choose a failure probability ö. the subsample is of size k = 0 S (A log( (S) + log( }))). then is fact (1 + --coreset [19] with probability at least 1 - 8. Unfortunately. it is often just as difficult to compute the exact sensitivities as is to solve the original problem. The remedy to exploit the fact that one does not need the exact sensitivities themselves: it suffices to use any upper bounds on the
5

---

sensitivities, provided that the upper bounds are not too loose, since a larger upper bound will lead to a larger coreset. Thus, we can reduce the task of coreset construction to two tasks: control of the VC dimension and sensitivity estimation of the loss function. This is handled in the following sections.
3.1 Bounding the VC dimension
We prove two different bounds on the VC dimension. The first one is simple quadratic bound of (dP). Our proof in the appendix simply counts the number of operations required to compare the loss function to a given threshold. The VC dimension bound then follows from standard result in the context of bounding the VC dimension of neural networks [ Thm. 8.14].
Lemma 3.1. The VC dimension of the range space associated with the class of Poisson loss functions as in Equation (3) is bounded by (R S (df)).
is noteworthy that the quadratic dependence is implied already only from one single application of the exponential function, which is sufficient but likely not necessary in our context. Hence, show in the remainder more refined hear-linest bound of O & log(n) log(Vmux)) = Ö(d/e), while keeping the dependence on other input parameters-nnmely: on n and ymax logarithii.....
To this end, we subdivide the set of input functions into groups of growing values of their response parameter 3/s, and of their sensitivity S geometric progression. By rounding these values in each group their next power in the geometric progression, we obtain disjoint sets of functions that closely approximate the original weighted loss functions, and whose VC-dimension can be bounded in (d). Since there is only logarithmic number of groups in both progressions, we obtain the claimed VC dimension bound.
Recall the responses (v%); are nonnegative integers. We define their largest value (for given input) to be Mmax = max(y; i E [n]]. Therefore, they are naturally bounded between 0 S y/4 S 9max for all i E [n] and there are at most Umax + 1 different values of y;- Also note that the sensitivity values are naturally bounded by 0 S & S 1, but since they are continuous, they must be bounded away from 0 in order for the geometric progression to end in finite (logarithmic) number of steps. If we increase each sensitivity by 1/n then the total sensitivity grows only by a constant, since S' S'= -ie((n)(F=
1/n) = S + 1. For these reasons, we can thus assume that 1/n S s S 1.
Now, we would like to increase the sensitivities even more to their next power of 2, which will clearly increase the total sensitivity by no more than
(5) By our above upper and lower bounds on the sensitivities, this will result in O(log(n) groups, where in each group all sensitivities equal. Note that in [Proposition A.5] the reweighting of points depends only on fixed terms except for the sensitivities. Thus, in each group, all weights are constant. We have the following bound that applies to each group and for any fixed y E No-
25' = 25 2 2 3S.
Lemma 3.2. The VC dimension of the range space induced by the set of functions F. = (3) =
9y: () i E [n]] with equal weight e E Rzp. and equal y; y Nor all i E [n] satisfies A ( = (d).
For the values of yis we proceed in a very similar way. However, unlike the sensitivities, a constant approximation as in Equation (5) provided by powers of will not suffice. Instead, we group the values of yi into powers of (I + e) and round all y; that belong to the same group to the next larger power. We argue that this preserves a (1 + Os))) approximation to the original loss function. Indeed, this claim even holds for each summand 9y. if ys is large enough, as the following lemma shows.
Lemma 3.3. Let y and 2 0. Let y < s' s (1 + e)ys- Then for arbitrary z >> 0 it holds that (1 - 3e) g,) (2) Σ 9v (2) S (1 + (z).
A direct consequence of Lemma 3.3 is that any coreset for the rounded version is a coreset for the original loss function and vice versa, up to an additional (1 + O())) error. We can therefore work with the rounded version of the loss function, which yields better bounds for the VC dimension.
A general theorem for bounding the VC dimension of the union or intersection of t range spaces, each of bounded VC dimension at most D, was given in (6. Their result yields O(t log(t)). Here, we give a bound of OLLD) for the special case that the range spaces are disjoin
TThe same bound and proof also appeared in 20 in a different context.

---

Lemma 3,4. Let F be any family of functions, and let Fi..... F. partition of F, i.e., their disjoint union satisfies Uveta = F. Let the VC dimension of the range space induced by F, be bounded by D for all i [t]. Then the VC dimension of the range space induced by FF satisfies A (Rx) I tDD
Fi F be nonempty sets that form
As result of our previous partition into groups and the O(d) bound on each group, we obtain the desired result.
Lemma 3.5. Let F be the set of functions in the Poisson model. We can round and group the values of Yi and the associated sensitivities S to obtain F such that each function F weighted by -log The range space induced by FF
O < wN E W = {u1,-.. ,......,,.. M4 for E
satisfies A (Ry-) & O log(n) log(Umax))
As a direct corollary Lemmas 3. and 3.5
we obtain the following combined bound.
Corollary 3.6. The VC dimension A of the range space associated with the class of Poisson loss functions in Equation (3) bounded by
A (R So ( d (4minn {d. log(n) log(Huasx) })
3.2 Bounding the sensitivities
We split the loss function into two parts:
(x(9) = E
Ins (z,3)+ +
E Ius (z,3)
(6)
We will ignore the first sum, since we will see later in the main approximation ofeSccn 4] that by shifting the hyperplanes defined by parameter vectors in the solution space, everything can be shifted to the second sum where 2,8 2 1). In this way, we preserve a (1 + approximmtton,, if rz +(c) is small enough. We note that this shifting technique still requires the extreme points on the convex hull Ext(X) to be maintained; sensitivities for the remaining points with x,3 2 1). In the next lemma we require the concept of well-condiitioned-asss [12]. Let q E {2, x0) denote the dual norm of p E (1, 2). respectively, We say that U is a '(a, Y. well) satisfics
address this issue in Section 5) We will focus bounding the
basis' for the column span of X UR Raxd
|Ul|p aa e Rd ||=1|g S 2/1
(7)
Lemma 3.7. Let E Buxd, .y E NJ be a p-complex dataset, i.e., Equation (2) holds. Let {1,
Let X 2 1 be the slope parameter from either Lemma 2.2) or Lemma 2.3 depending on the value
of p. Let o be conditioning parameter and r) > be arbitrary. Then the sensitivity for each I; with z4, > 17 is bounded by < App>'| 2/n. Their total sensitivity is bounded by 6 S
O (pd ymax/ hoda//mx//an Almax/log(/ (ymax) + log log(1/n)) for p 1, and @ O(pd + log (ymax) log log (l)))
for = 2.
3.3 Combining the results into the sensitivity framework
Putting all steps (VC dimension, total sensitivity) together into the sensitivity framework, Propo- sition A.5 yields the following computational result, where in particular Ep well-conditioning is established constructively using l subspace embeddings 99, resp. using & spanning sets
Theorem 3.8. Let X E Raxd y E NT be a p-complex dataset, i.e., Equation (2) holds. We can compute weighted coreset (K, w) Rxx x o for the pth-root-link Poisson regression problem with p E {1, 2] on D(n) = {B E Id Vi, x43 > n). The size of the coreset is bounded by Ö( 2d min(d, log(n) (m) 1og()max)) m), where
log log(d) /maxx/ log( (mmxx) + log log(1/n) pd + log (Vmux) + log log (1/r)
p= 1
p = 2.
7

---

Main approximation result
In the previous section, we developed coreset for the sum of individual losses where x,8 1) ie.. for the second sum of Eqqaatin (6) Since we cannot bound the remaining first sum where 2, < we choose to simply avoid instead, by shifting each solution by n. Define for any 1j 2 0
((n) = {3 E Rd Vi, x m
The original domain of optimization is (() and the shifted domain is (1)). Shifting the domain does not remove the need to store the extreme points on the convex hull of the input, since we need these points determine the feasible domain ((n) during optimization. However, shifting removes the need to approximate the first sum in Equation (6) over points with unbounded sensitivity located in small slab of width 1 within the convex hull.
Since we have a (1 + 5) coreset for ((n), we need to find a suitable choice for v and show that the optimizer (B")* (()) is (1 + (e)) approximation for the optimizer in the original domain 3* E D()). We thus define
8 argmin prg 3* = BeDi)
(8)
Lemma 4.1. It holds for sufficiently small > that
5 s (1+
Now we combine the preceding results, namely the coreset and the domain shifting bound, for our main theorem.
Theorem 4.2. Let E E 1/,4/ Let (C, be a coreset according to Theorem 3.8 Let B := argminseD(e) (C3). 9* == argmin ((X Then
f(x,*) < f( s (1 (1+ ()x
5 Extreme points on the convex hull
In the previous sections, we argued that for obtaining a (1 + 8) approximation, it suffices to calculate coreset that is valid for all 3 E (es), and then to minimize the coreset instead of the full data. Note that for the optimizer to stay in the feasible set (Es). one must store the extreme points on the convex hull of the input points denoted by Ext(X). This true even when e = 0, i.e., even when the original function is considered and no shifting occurs. Note that there exist datasets such as our 'points on a circle" example considered in the lower bounds of Section 6 such that (Ex((X)
loss function over /8 E D(e) using
There are several ways to either characterize [Ex((X) for typical inputs in sublinear way, to approximate the convex hull by smaller sublinear subset, called an e-kernel, with an error of at most Since these methods usually relative the diameter of the data, and since we need an additive error for our shifting approach, we first normalize the data to be within the unit ball. We note that this does not change the value of the loss function, since this involves scaling by fixed value C 1, and since we can use the fact that
f(XB) f (0 (()) (C3)
as well as the me-too-ne correspondence between any 33 and CB. Thus, we can run the algorithm on the rescaled data, obtain a good or optimal solution CB and rescale C to obtain the corresponding 3* Rescaling steps such as normalizing data to zero mean and unit variance are standard in statistical data analysis 22
Smoothed complexity of the convex hull Instead of the worst case |Ex((X] over all possible datasets X xRd in smoothed complexity we consider
sup E=- Ext(X E)),
x
Such domain restrictions do not lead to feasibility issues, discussed in Appendix due page limitations.
8

---

where N' denotes the distribution over matrices E with the same dimensions as X and with i..d. Gaussian entries with mean 0 and variance o², i.c., E.,; _N( o²) for all i [n]. [d] M. This is motivated by the fact that many datasets are recorded with measurement errors, which can often be assumed to he Gaussian. Specifically for the convex hull, [ Chapter 4] showed that for normalized data in the unit cube, the supremum above is bounded by
log 3 σd
(n)
+ log d- (n)
which is sublinear in n, though exponential in d.
e-kernels The purpose of e-kernels is approximate the extent of point set up to an error of 1 for any direction in Ie based on subset of the data. They were introduced by []] and improved by g to optimal ( (cd)//))) size, see the survey [2]. Since we assume our data to be normalized within the unit ball, this translates to additive error that is bounded by e. Thus, the houndary of the convex hull of the s-kernel can be smaller than the boundary of the original convex hull by at most e.
Improvement for structured data is known that e-kennlls can have size up to (2(1/((d1))2) in the worst case. Beyond the worst case, the structure of the given data may allow for much smaller e-kernels to exist, even in high dimensions. Motivated by this, S developed 'greedy clustering' approach that produces an e-kernel of size OKhmin/ /s²), where kmin =
kmin x) denotes the smallest possible size of a subset that gives the required e-kernel guarantee for the original input X.
Using s-kernels for optimizing Poisson models The above options include the possibility to calculate the convex hull and rely on the sublinear smoothed complexity bound, if this is reasonable in the given context. Otherwise, if we have access to any of the above e-kernel constructions, we shift the hyperplane away from the approximation of the convex hull, provided by the e-kernel, by a distance of = 2c instead of just e. As a result, the hyperplane will be shifted away from the original convex hull by least E and at most 2z. Thus, we still compute a (1 + +(=)) approximation in this way.
Lower bounds
We complement our coreset constructions for the variants of the Poisson model by a series of lower bounds. Our bounds in Lemma 6. and Lemma 6.2 are specifically for the pth-root-link, and not for the log-link, which was studied in [11. We use similar constructions of the bad dataset as those used frequently in previous literature, e.g., in 3l Theorem 6], and in [3 23 21 However, each of these references require specific adaptations to the respective loss function that do not directly apply to our setting. Our arguments are thus adapted to the Poisson pth-root-ling link model to show that it does not admit sublinear coresets without imposing assumptions on the data or restricting the model.
The hard instance consists of n equidistant points on the unit circle. Recall that in the Poisson regression formulation, every point has an additional intercept coordinate which is 1, and the corresponding parameter of / determines the affine translation; see see Section 2 For every E [n]. let I; (1, cos( 2 sin( 2m1) )) and y = 1. Recall that any feasible 33r must satisfy 2,, > 0, Vi [n]. The hyperplane parameterized by / is thus always outside the point set and / points in the direction of the (z:)se[m]-
The idea for showing that any point has sensitivity 1 is that if ,3 points to the center of the point set, and the hyperplane is translated to just 'touch' point 2;, then 2;, is arbitrarily close to 0, implying that the cost is arbitrarily large. All other points are sufficiently bounded away from the hyperplane, but also not too far away, so their cost bounded. This implies that the sensitivity of point x; can be made arbitrarily close to 1. By symmetry of our construction, this holds for any point.
Lemma 6.1. Consider number n 2 of points equidistant on unit circle in a 2-dimensional affine subspace embedded in Rd, d > 3, each with label y; 1. Then the sensitivity of each point for the Poisson model with pth-root-link for p E (1,2) is arbitrarily close to 1. Consequently, any coreset for the Poisson regression model must comprise all Q(n) inpul points.
Below, we prove an even more interesting statement, i.e., that no compression is possible below ((n) bits. While this statement appears to give weaker Q(n/ log(n)) bound against coresets, it in fact gives a stronger bound in some sense. This because the bound holds against any possible data reduction algorithm and against any data structure that answers negative log- likelihodo queries

---

to within a small error, independent of what (possibly randomized) operations the data reduction algorithm performs. For example, the algorithm could subsample, could select input points as coreset constructions do, or it could take linear combinations as in linear sketching. More generally, the bound holds against any sort of bit encoding that represents the reduced data. The reduction is based on the same data example of equidistant points on circle embedded in d 2 3 dimensions.
Lemma 6.2. Let En be a data structure for D = [x. y] E Raxd x RR, d 2 3, that approximates negative log-likeldhood queries (B) for Poisson regression with the pth-mott-link for p {1,2), such that for some & 2 1 it holds that
v3 E Rd 3(X3) S En(3) S x
If T 8 Blog(n) then ED requires (n)) bits of memory.
Next, prove that the parts of our analysis that are specific to the Poisson model are tight. In particular, the scale parameter À is only a constant for = 2, but in the case p = 1 we only have a Vy/log(y) upper bound. Since Ymax. ie.. the largest y. can potentially be very large, one may ask we can do better. Our next result exactly characterizes the smallest possible parameter À such that our linear lower envelope approximation is tangent to the actual loss function, in order to show a tight À = VM/lllg(()) bound. This characterization of tangent points relies on properties of the principal branch Wo of the Lambert function, which defined by the equation
Wo(z)e 5. for -//e.
The only approximations that the final bounds obey follow from Stirling's approximation and from the following upper bound on the Lambert function Wo by square root function. This upper bound improves the recent cubic root bound of [38 Theorem 3.2] within a small region, and is crucial to obtaining a tight square root (rather than cubic root) lower bound on X.
Lemma 6.3. For all x [-1/e, 0), holds that Wo(z) S /2 + ex) 1
The above bound on the Wo function is novel and may be of independent interest. In our context, it allows us to prove the following tight bound on X that resembles the same asymptotic upper bound as in Lemma 2.2 and establishes a matching lower bound.
Lemma 6.4. Let E N be arbilrury, p 1, and
y//p in the definition Equation (4) of
Gv. Let (2) = (z- for 2 > 0. Then 9y and h2 are tangent to each other if and only if (y) (Wo(
2 y exp(2) + +1 which case the unique tangent point 2" 2²(y) = 21)
yx² (v)
In addition, (1) = O(V /max log M)
The next lemma shows for 2 3 that there exists no constant C such that the domain shifting approach that we developed in Sectionn 4 yyields a 1 + Cs error bound. As this error bound is a crucial sufficient condition for our main approximation results given in Ln[mema 4.1 and a Theorem to hold, the lemma suggests that different techniques may be needed. It indicates a limitation of our analysis to the most common values p (1,2), which are the main parameterizations considered in our work.
Lemma 6.5. Let p E N, 2 3. Then there does not exist an absolute constant C 2 0 such that for all sufficiently small 1) > 0 and for all 3 E D(0), B == 3 + nen E D(n) satisfies
1(x < ((X +
7 Concluding remarks
we recalled that previous finite sample size results had either unbounded or O(v d) error instead of our (1 + E) approximation. Our lower bounds on the parameters, together with linear VC dimension, linear sensitivity, and linear & dependence in our main quantitative bounds of Theorem 3.8] leave no room for improvement (up polylogarithmic factors) if one uses a black-box application of the sensitivity framework. We remark that recent improvements on Ep sensitivity 3 suggest that the dimension dependence can be improved to linear as well. Exploiting the fact that our coreset gives guarantee for all B E D(e), it would be interesting to extend the statistical treatment to the Bayesian setting, inferring the distribution of parameters over this was recently accomplished in the case of logistic and probit regression [4.
In Section 1.3
sampling
10

---

Acknowledgments and Disclosure of Funding
The authors thank the reviewers for their constructive feedback and discussions. We also thank Simon Omlor for valuable discussions that inspired the domain shift idea and Tim Novak for help with experiments. The research of HCL has been partially funded by the DFG Project-ID 318763987 - SFB 1294. AM was mainly supported by the German Research Foundation (DFG) grant MU 4662/2-1 (535889065) and by the TU Dortmund Center for Data Science and Simulation (DoDaS).
AM acknowledges additional travel funding by the University of Cologne.
References
[1] Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. J. ACM, (114))6666663,,...) 2004.
[2] Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, 52(1):1 100, 2005.
[3] Mingyao Ai, Jun Yu, Huiming Zhang, and Hai Ying Wang. Optimal subsampling algorithms for Big Data regressions. Statistica Sinica, (1))):p. 749-772, 2021.
[4] Martin Anthony and Peter I.. Bartlett. Neural Network Learning- - Theoretical Foundations. Cambridge University Press, 2002.
[5] Avrim Blum, Sariel Har-Peled, and Benjamin Raichel. Sparse approximation via generating point sets. ACM Trans. Algorithms, 15(3):32:1 12::11,,26662 2019.
[6] Anselm Blumer. Audrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Sapmik-Chervonenkee dimension. J. ACM, 36(4):929 965, 1989.
[7] Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. CoRR, abs/ 1hs/0692,00889, 2016.
[8] Timothy Chan. Faster core-set constructions and data stream algorithms fixed dimensions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 152-159, 2004.
[9] Kenneth L Clarkson David P Woodruff. Low-rank approximation and regression in input sparsity time. Journal of the ACM, 63(6):1455 2017.
[10] W. G. Cochran. The analysis of variance when experimental errors follow the Poisson binomial laws. The Annals of Mathematical Statistics, 11(3):35-347, 1940.
[11] Valentina Damerow. Average and smoothed complexity of geometric structures. PhD thesis, University of Paderborn, 2006.
[12] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney. Sampling algorithms and coresets for lp regression. SIAM J. Comput., 38(5):2060-25)) 2009.
[13] Gregory Dexter, Rajiv Khanna, Jawad Raheel, and Petros Drineas. Feature space sketching for logistic regression. CoRR, abs/2303. 144244 2023.
[14] Zeyu Ding, Simon Omlor, Katja Ickstadt, and Alexander Munteanu. Scalable Bayesian p-generalized probit and logistic regression. Advances Data Analysis and Classification, pages 1-35, 2024.
[15] Petros Drineas, Malik Mamaon-Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approximation of matrix coherence and statistical leverage. J. Much. Learn. Res., 13:3475-3506, 2012.
[16] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for l2 regression and applications. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium Discrete Algoritims
(SODA), pages 1127-1136, 2006.
[17] Bradley Efron. Poisson overdispersion estimates based on the method of asymmetric maximum likelihood. Journal the American Statistical Association, 877417):98-107, 1992.
[18] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC). pages 569-578. ACM. 2011.
[19] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning Big Data into tiny data: Constant-size coresets for k-means, PCA, and projective clustering. SIAM J. Comput., 49(3);601 665,660016666666 2020.

---

[20] Susanne Frick, Amer Krivosija, and Alexander Munteanu. Scalable learning of item respoase theory models. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1234-1242, 2024.
[21] Sariel Har-Peled, Dan Roth, and Dav Zimak. Maximum Margin Coresets for Active and Noise Tolerant Learning. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), page 836-841, 2007.
[22] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer Series in Statistics. Springer New York Inc., 2001.
[23] Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable Bayesian logistic regression, In Advances Neural Information Processing Systems (NIPS), volume 29, 2016.
[24] Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press. 1994.
[25] Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Compu- tational Complexity, 8(1):21-45 1-4,, 1999.
[26] Michael Langberg and Leonard J. Schulman. Universal epsilon-approximator for integrals. In Proceedings of the 21st Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 598-607, 2010.
[27] JooChul Lee, Elizabeth D. Schifano, and HaiYing Wang. Fast optimal subsampling probability approxima- tion for generalized linear models. Econometrics and Statistics, 29:224- 237, 2024.
[28] John Maindonald and W. John Braun. Data analysis and graphics using R - an example-hased approach, volume 10 of Camb. Ser. Stat. Probah. Math. Cambridge: Cambridge University Press, 3rd edition, 2010.
[29] Ian Marschner. Stable computation of maximum likelihood estimates in identity link Poisson regression. Journal of Computational and Graphical Statistics, 19()):666683, 2010.
[30] P. McCullagh and J. A. Nelder. Generalized Linear Models. Chapman Hall, London, 1989.
[31] Alejandro Molina, Alexander Munteanu, and Kristian Kersting. Core dependency networks. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI), pages 3820-3827, 2018.
[32] Alexander Munteanu. Coresets and sketches for regression problems on data streams and distributed data. In Machine Learning under Resource Constraints, Volume 1 Fundamentals, pages 85 98. De Gruyter,
2023.
[33] Alexander Munteanu and Simon Omlor. Optimal bounds for lp sensitivity sampling via & augmentation. In Forty-first International Conference on Machine Learning (ICML), 2024.
[34] Alexander Munteanu, Simon Omlor, and Christian Peters. p p-Generalized probit regression and scalable maximum likelihood estimation via sketching and coresets. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2073-2100, 2022.
[35] Alexander Munteanu and Chris Schwiegelshohn. Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms. Künstliche Intell., 32(1):37-53, 2018.
[36] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff. On coresets for logistic regression. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 6562-6571, 2018.
[37] Jeff M Phillips. Coresets and sketches. In Handbook of discrete and computational geomerry, pages 1269-1288. Chapman and Hall/CRC, 2017.
[38] Biel Roig-Solvas and Mario Sznaier. Euclidean distance bounds for LMI analytic centers using novel bound on the Lambert function, 2022. arXiv:2004.01115.
[39] Haipeng Shen and Jianhua Z. Huang. Forecasting time series of inhomogeneous Poisson processes with application to call center workforce management. The Annals of Applied Statistics, 2(2):61 623, 2008
[40] Donna Spiegelman and Ellen Hertzmark. Fasy SAS Calculations for Risk or Prevalence Ratios and Differences. American Journal of Epidemiology, 162(3):199-20)) 2005.
[41] Elad Tolochinsky, Ibrahim Jubran, and Dan Feldman. Generic coreset for scalable learning of monotonic kernels: Logistic regression, sigmoid and more. In International Conference on Machine Learning (ICML). pages 2022.
12

---

[42] Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer. New York, USA, 1995.
[43] Ruasong Wang and David P. Woodruff. Tight bounds for & oblivious subspace embeddings. ACM Trans. Algorithms, 18(1 ):::1 1-::32, 2022.
[44] David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approximation: Offline and online. In Proceedings of the 55th Annual ACM Symposium Theory of Computing (STOC), pages 1802-1813, 2023.
13

---

A Details on the Sensitivity Framework
Definition A.I (Coreset, cf. [9]. Let Raxd be a set of points (I1,..., In.. weighted
by w Rg For any 7 RR let the cost of n w.r. the point x, be described by function w; w.- (w()) mapping from R to (0, oo). Thus, the cost of w.rl. the (weighled) set X is fw (X1)) = E;w; W/ - (ww)). Then a set K E RRlxd, (re)weighted by a E R is a (1 + e--crrestt of X for the function Sno if < and
EE 1f (Xn) fu (Kn) Se fno (Xn).
In our analysis we sampling based so-called sensitivity scores, the range space induced by the set of functions, and the VC-dimension. We define these notions next.
Definition A.2 (Sensitivity. (26)). Consider a family of functions = (gi..... In) mapping from IR. to [0, co) and weighted by w E R250- The sensitivity of 96 for the function f (n) -te(m) Wege(n), where 1) E Rdd is
Wegt (11)
Se = sup fw)
(10)
The total sensitivity
-EE((n) Sr-
Definition A.3 (Range space; VC dimension). A range space is pair Ri (F, ranges), where F a set and ranges is a family of subsets of F. The VC dimension A (RR of R is the size [G] of the largest subset G C such that G is shattered by ranges, i.e., K R R E ranges) = 2 Gl
Definition A.4 (Induced range space). Let F be a finite set of functions mapping from R$ to R>0- For every I E Id and r E Rxo, let range, = {f F f(x) 2 r}, and ranges(F) = (range> r) E Idd E R20). Let R7 (F, ranges(F)) be the range space induced by F.
To construct coresets for Poisson models, we use a framework that combines sensitivity scores with the theory of VC dimension, originally proposed by [18 77. We use a more recent and slightly updated version as stated in the following theorem.
Proposition A.5 (19), Theorem 31). Consider a family of functions J = [// ..... Sn) mapping from Id to [0, oo) and vector of weights
By0- Let e, E (0,1/2). Let st 2 Sa. Let S Di i=1 G. Given s; can compute in time O(IFI) a R C of
o (
S Alog + log
functioos functions such that with probability 1 - we have for all 17 E Bd simultaneously
Σ
waf((n) -
Σ (nfi(n) JER
SE Σ wxfi(n).
JEF
JEF
where each element of is sampled i.i.d. with probability Pj = from F. u, = Sw denotes the R
weight of a function fo R that corresponds to fg E F, and where A is an upper bound on the VC dimension of the range space Ry- induced by F² that can be obtained by defining F to be the set of functions Sj where each function scaled by Swy
[
B Proofs for Poisson pth-root-link model
Lemma 2.1. It holds for all E RR p E [1, oo), that
(o(2) 2p -p log() log(u!) 2 max {1,5(1 + plog(3))
Proof of Lemma 2.1
For y direct calculation yields (2) 2 (v 1.
14

---

Finally for For all other y E N \ {1} we get from Stirling's approximation
log(v!) 2 y log(v) y + log(2 +
12y + 1
2 yog((y) + log(v) 2
log(2T)
2
2 y - + log(y) 10
Since By has unique minimizer x" y /r it follows that (x) 2 (,( = y + log( 2
log(u) > 1.
10 2
To prove the claimed bound generalizing to all 2 E Rso. we first argue that
9
(y)
log(y + 1)),
(11)
10
which is equivalent to showing for arbitrary y E N it holds that
y ((++))=
{
1+ log log 1 (1+
1)
2 3
9
1 log
S
3y
10"
where the first inequality follows from the inequality 1+ S Ex for all values of x. We see that by monotonicity of the functions h(z)= {1 + log(z²)) and the above properties of gy (z), have for
all 2 - (y + 1/ that
9
Equarion (IT)
(x) 2
+
log(y) 2
log(y)
(1 + log(y + 1)) 2 M(2),
10
10 3
3
where the first inequality above follows from the inequality one line above Equation (11)
2 (y + 1)2/D the function By grows at least as fast as the lower bound, since
(²(2) = p2
py
p x
y
=
2
2
p
y +
P h2(2).
2
2
2
32
Lemma 2.2. For any p 2 1 and N it holds that 2D 2 By (2(2) for 2 > /r, If 1, then for
some À O(v // log(y)), it holds that 9y(2) 2 (py for y/
Proof of Lemma 2.2) We start with the upper bound. Using the fact that the assumption 2 // implies log 2 > 0, and setting = 1 in Equation (4) yields
gn (2) = =" -p--pplee log((z) + log 1 < xP.
It remains prove the claim for 2. From Stirling's approximation we get
1
1 2
1
log(y!) s y log(y) - log(u) + log log(2r) +
12'
Now, note that since the derivative of the function + 2 log is strictly negative over the interval [2, oo), follows that the function itself decreasing over the same interval. By rearranging terms and replacing y in Eqquatin (4) with an arbitrary 2, it follows that
Iu (z) = 2 ylog(=?) + log(y!) - z"
y log(y) + log(y!)
5 n
log(y) y log(2x)
1
2
log(2) - 2 + log(2iT)
+
2
12
23
= 2
log(TT)
< 2P.
2
12
15

---

where the last inequality holds since π < e², and thus log(()) < log(e) = 1.
In the remainder, let p 1. Let
LB(y) = max 11,3(11 (1- log(v)) }
1 3
be the lower bound given in Lemma 2.1 Now, we want to prove that (2) 2 X =: h(z) for X 2 1 as small as possible.
To this end, we consider the derivatives gy(2) = 1 8 and h'(z) = 2. and find that
2 | x+x=-)==
Next, we see that since h(y) = 0, we can guarantee h(z) S LB(y) S gy(z) for all & E [v. + A),
where A := A Ly()).
To obtain a general lower bound on By (2), we want both conditions hold simultaneously, which is true whenever
X - < < U 1))B(y)
y
Solving for À yields that (z) 2
شニル holds for all AZ 1 (V
by
+1+1).
LB(yl
Lemma 2.3. Let 2 2 and y E N. and À = 1. Then gy(2) 2 (z-gllopp
2 for = > y//..
Proof of Lemma 2.3
First we define for 0 the function hx, and compute its derivatives:
hx(2)= = (z - T)P
(x(2) = (z r
(x(2) p(p - 1) (z T)p-
2 ZE Eyu- (12)
X
Setting T y2/p in Equation (12) obtain
(r) (y>/r /2/
- 2
log((Ty) < Jy (y())
where the second incquality follows from the fact that the minimizer of gy is / and from Stirling's approximation:
1 min (n(=) - y - y yloog y log y!.
2 Log(2Ty) + 12y +1 #>0
Thus, 9, (P) 2 hs (w) and sufficient condition for gy(2) 2 1x hold for > 11/0 is that
(z) h(2)) nondecreasing
/2/ i.e.
- (z) = p (x-- - 2) 11 s -=)
(2 12-yWpapr
p-1
y +
Note that
>> 1 + (z y1/030-1
(z y1/1p011
y/
11 +
so a sufficient condition for J/ (2) - (x) to be nonnegative for all z > y1/ is
(2 y + (v /p// V= > y /r.
If X 2 1, then a further sufficient condition for g((2)) 1/1 (2) to be nonnegative for all 2 /1/
2 (z y 11/ + (y 1ppp-1, Vz > yd/p,
which is equivalent
2 p-1
2 p-1
11/p -
+1, Vz VE > 11.
(13)
16

---

For E IR, let [x] = suppp E Z : p x be the floor of z. We will prove that Equation (13) holds. We have
p-1
//
11
|m-1J
y
11/11
11
1F-1
2
+ 1)
y//r
1//1
1p-11
L
1
81/p -1
binomial thm., p 2
///r
11
(00
1w-1!
g1/D
2
1
+1)
y//n > 1
1/
(p-11
p-1-1p-11
2
1/1/1
11/p
p- 1p-11
1x-1]
p-1-1p-11
2
yy/p -1
2
+
2
r20= d dx
x²² 20
//
y1/p
p-1
12/p -1
+1
1²/p > 1,
as desired.
C Proofs for coreset construction
Lemma 3.1. The VC dimension of the range space associated with the class of Poisson loss functions as in Equation (3) is bounded by ( S ((d)).
Proof of Lemma 3.1
the coreset approach, need to consider weighted subsets of the data, and thus weighted sums Σ w.9y, (x,3) that allow for different weights in Equation (3) In determining the VC dimension we range over all r E R, 8 E Idd, and need to check whether wi9y, (z,,3) r. Note that the log factorial terms are independent of 2,3. In particular, for each r E IR, there exists IR 3 s == w; log(y.!). We can thus instead count the number of operations required for evaluating each summand
Because
w;( w;((x=))' pyji In(x;3)) 2
This can be rearranged to
(a,,8pp - s/ s/Ww
8 < exp
which can be accomplished using (at most) the following operations
division to compute s/tu
d multiplications and d additions to compute x;3
p multiplications of z.3 compute (r,3))
subtraction to compute (I, s/W,
1 multiplication to compute py: (0 for 1)
division by pt
(2,0)P_s/ws
exponential function evaluation to compute exp
operation to verify whether x,,3 < exp (2,8)P-s/mn holds
17

---

operation output depending on whether r, exp
[a:,8)==s/w,
holds
pds
for total of = 2d p operations, exactly == of which is an exponential function evaluation. Putting these quantities into the final conclusion of Thm. 8.14] yields
A(Rx.) (d(4 1)) 11d(g 1) loga (og2 1))) (2d)² 22d
logo (18) (dd).
Lemma 3.2. The VC dimension of the range space induced by the set of functions FC (3) c. Sy (2,33 E [n]] with equal weight e E Rz0. and equal yi = E No for all i E [n]] satisfies
A (RF..) = O(d).
Proof of Lemma 3.2
We split the functions di into subfunctions 25 (2r(3) and gzy. (I;3) de-
1/2 Since gi minimized when w. y/ 1/p and due to pending on whether r; yr 1/2 x.33 Vi yi"
strict convexity, the two subfunctions /g (0, w/
[g(w; oo) and y (v1 1/p xc)
[a(u: 1/P), oo) are strictly monotonic and invertible on their respective ranges and domains.
Now fix an arbitrary subset C Fo. Let Ω = Rd x R R20. We have the following bound:
KGG R R ranges (F.)l = (range 1 Rd R2o
U (8.r)R
Ho e G (3) 2 r}}
Hi E G c (oy)o(o,5)) rr ا (x,3) 2 rT} (8r))R
U
Ha e GI 2 y (8.))R
U
U Hg E G GIIIIB8. 2,829 2 (Br)en
(14)
The inequality holds, since each non-empty in the collection on the LHS satisties either of the conditions of the sets in the collections on the RHS, or both, and is thus the union of two of the sets, one from each collection. can thus comprise at most all unions obtained from combining any two of these sets.
2;B 2 s1} where si = -9 (r/c) maps any Now, note that both sets are of the form {g: G
real to value of some subset of the reals D IR as specified above. Extending the domain of and r to the reals, we obtain exactly the points that are shattered by the affine hyperplane classifier 2, + -20).. The VC dimension of the set of hyperplane classifiers is d 24
The argument holds verbatim for 82 = (r/c)
We conclude the claimed bound on ( by showing that the above term Equation (14) is strictly
less than 2| for GG] = 10(d + 1). By a bound on the growth of the sets (see 16 24)), we have for this partieular choice
U Ha G 2 9 2g (ree)) (B
U Ho G 2 29 (r (Brr)e
119 EG 2; - 81 2 03 Rd ERH H[l E E 24 - 52 N 0} 3 E Rd 82 RH
||G|| ((IG)
(d+1))
< (306d+1)) 2 20g+ log, < 210(++1) = 2|
<
d++1)
which implies that A(Rr,)) 10(d 1).
18

---

Lemma 3.3. Lery 2 8 and > 2. 0. Lery < (1 (1++)ye E)us. Then for arbitrary 2 > 0 it holds
that (1) - By (2) - (1+ (e)g
Proof of Lemma 3.3
Recall that
9y (z) (2) py log(z) + log(s/!)
(8)
(16)
We bound the two parts separately. The first part (i) is straightforward from the assumption on y'. We only need to distinguish two cases, depending on which either the upper or the lower bound of the assumption y y' S (1+ applies: If log(2) 2 0, then there is nothing to prove since in that case
x² - py log(2) (2) S " py polo)(z),
given the hypothesis that y < y.. Suppose that log(z) < 0. Then
2" py' log(2) 2) - 2 (1 + E)py log 2) - (1 + 3=) py log(2)),
where the first inequality follows from the hypothesis that y' S (1 e)yı and the second inequality follows since 1 + 38 > 1 1+ 1.
For the second part (dt) we need some technical claims. Since y, v' E No, it must hold that y' 2 y 1. Then
12y'
12(y + 1) 12y + 1
Further, for any x 2 holds that
log((1 + =)x) = =log(>) + log(1 + +.) < log(x) t 1 S (1+ ++) (1+ log(z),
where the last inequality uses the condition that x 2 e.
With this in place, and using y/ y 2 8> e2, apply Stirling's approximation with constant C=== & 1og(2x) that independent of y, y', and that common to both the upper and lower bounds from Stirling's approximation for the factorial function. We thus obtain
log(v/!) s s log(v') y + log(s/) +
+C
2
12y
1
1
5/llo((s/)
+ log(?') +
+
2
12y
= 5/lg((/ /e)) log(y') + 12y +C
2
1
< (1 (1 +1++)) log(u/e) + (1 log(y)
+
12y
$ (1+ ylog(w/e) log(y) + 12y +1
+C
(1 33)+))log()) log(y!)
where the first inequality follows from the upper bound in Stirling's approximation for the factorial, the second inequality follows from the hypothesis that y' I (1+e)y and the inequality 12y +2 proven above, and the last inequality follows from the lower bound in Stirling's approximation of the factorial and from the fact that (1 + = similar way. Overall, our claim follows.
= 1 + 28 + < 1 + 3e. The lower bound can be treated in
Lemma 3.4. Let F. be any family functions, and let Fi...., F₁ C F be nonempty sets that form partition of F. i.e., their disjoint union satisfies Üke(t) = F. Let the VC dimension of the range space induced by F3 be bounded by for all i [t]. Then the VC dimension of the range space induced by FF satisfies A x)) tDD
19

---

Proof of Lemma 3.4 We prove the claim by contradiction. To this end suppose the VC dimension for F strictly larger than tD. Then there exists set G of size |G] > tD that shattered by the ranges of Rg. Consider its intersections G; G F,, i E [4] with the sets F;. By their disjointness, each G; must be shattered by the ranges of Rr,- Note, that at least one G, must therefore satisfy |G.l/t > D, which contradicts the assumption that their VC dimension is bounded by D. Our claim thus follows.
Lemma 3.5. Let F be the set of functions in the Poisson model. We can round and group the values of Yy and the associated sensifivities S₃ to obtain F= such that each function in F is weighted by O w; E W = {ui...., Ue) for E 0( log(n) 1yg(Ymax)). The range space induced by F* satisfies A (R==) O log(n) (ymm))))).
We partition our input functions Iy. i E [n]] into disjoint sets with boundaries that increase in a geometric progression, depending on the sensitivities resp. weights, and on the response values
Proof of Lemma 3.5
Giy = (9 18. (1 +e) < yv < 18 (1+6)*
J 2 Smin I S < 2/+ Smin ) i [0, Ologi++ (Umax))l M..j j E [o, O(log(n)))
Additionally, we put the remaining values y into constant number of disjoint sets
Hyj 1y Uk y, 2 Smin S Sa < 2 Smin J. 1,,1,2,..... ..... 7), E [0. (log()))).
In particular, we note that
F= =- (U,C,C.) ú
(n)
UJ Man
forms partition of the whole function family, since the sets are disjoint and cover all functions by construction.
Each member of a set is of the same form, i.e., after rounding the weights and y;. all members of a subset have equal y y, and they have equal weight. The assumptions are thus satisfied for invoking Lemma 3.2 to bound the VC dimension for each of the induced range spaces by O(d). By
construction, the subsets are disjoint and their number is bounded by
log(Uraax) ) log(1 + +)
( = O(lggg()) 1001++ (Mmaax) = O (log(n)
O(s llog(n) log(Vmax)
We can thus invoke Lemma 3.4 to obtain
A (Rx=) & O(t)) = =0 0
log(n) log(Vmax) = =0(2)
Recall the condition Equation (7) for an (a,, wel--oeel-oond basis.
Lemma 3.7. Let E Raxd, y E No be p-complex dataset, i.e., Equation (2) holds. Letp E {1,2).
Let 2 1 be the slope parameter from either Lemma 2.2 or Lemma 2.3 depending on the value
of p. Let 7 be conditioning parameter and rj > 0 be arbitrary. Then the sensitivity for each x; with x²3 > 1i is bounded by S: S \p + 2/n. Their total sensitivity bounded by G S
O /dd ymaxx/ lla.:/lg@aaaa + log log(1/1)) for p- 1, and G S O(pd + log (Jmax) - log log(1 1/1))
for p 2
Proof of Lemma 3.7 Case 1: = 0: We start with the special case where 0. Recall that x,3 O. Then,
9v. (2, = (z, & |U < | |
= IIll U l = 7
1 En Ius (1,
Next, we consider 0 * y E N. and divide this into two sub-cases.
Case 2(): y/ E N. 17 < 2,3 < y, 1/p.
20

---

We start with the case 0 < 1/ 248 S 1/P.
For Sy. defined in Equation (4)
9y, (2. (x:3)² pyc (og(2; + log(vi!)
it holds using Lemma 2.1 the bounds rB and the monotonicity of gy(2) in the interval that
[_]
S 9y, (z, S o/ + ye log
+ log(u)!) UB(U))
np
Let {i [n] 1 9v. (x, UB (ymaxx)) We subdivide G Ú 9j into disjoint sets
=== = 9 (Bmmxx)) 2 < Iv. (mx3) S (Umux)))) .2 2- 1, (1......).
Since Py (x,5) E [1, UB (1mama)) there can be at most - [log2( (U (ymax)))
groups. So
1 5 logg
1/" + Ymax log
log((maxx))
(log(ummax) + log log
Y/max
vpp
7J
Now let n. i E 9j by
G-|- We bound the sensitivity (see Definition A.2
for each summand Iys (xx:3 for
Iy (I;3)
Iy. (I,3)
UB (B(mmax) 2- 2
S sup 3
E Ib (xr
sup
8
Eieg, Iy. (II
n2 UB (1taax))) 2-j ny
Summing over i E g yields
Eieg$ St = E
2
Σ
21 < 0 log(Umaxx + log log 2nj
Vmax
iEG, nj
j=1 Nj
7
$ 0
log(Uuuxx) log log
17
Case 2(ii): y/ E N, > vt 1/p.
Now we take care of the remaining region where r,, > y y//v.
In particular, by Lemmas 2.2 and 2.3 for some scaling X Ap that depends on p {1,2}, have that
(z Vi 1/pp
S 9ys (z) S nD
in that region.
Let be decomposition of X, so that v. R,3, and U is again a p-well conditioned basis, in the sense of Equation (7)
Now, using our assumption given Equation (2) we have the following inequalities
9y, (xx (M/B)= S | STUIIBBRRRS
= >> 1=1 (0,8)² s PP 2
S App E 9n, (I,
Summing over all sensitivities, we get that the total sensitivity is bounded by
G S p>(ar) + + [Iog( (1og(Ummun) + log log
Immx
))
"
21

---

For the first summand, there exists for each E [1, a so-called Auerbach basis attaining a = d. 7
see 4S Lemma 2.22]. For the special case p 2, we even have that any orthonormal basis satisfies
a dd, = since ||U|| = vd, and for any 2 E : || 2 2 - = V = V==² =V="= ||
Thus, in both cases we have suitable bases with (ar)) d.
For Lemma 2.2 yields X v O( "ymax//lo Umax)) With this, the overall bound simplifies to
6 f O ( (pdv /maxx/ / log Vmax
log log(L/)))
For = we have that x = 1 suffices by Lemma 2.3)
With this, the overall bound simplifies to < Oppd + log (Jmax) + log log(1/n)))
Theorem 3.8. Let X E Raxd, . E No be p-complex dataset, i.e., Equation (2) holds. We can compute a weighted coreset (K, w) E Bixd x IR for the pth-root-link Poisson regression problem with p E {1,2] on D(n) {B Rd Vi, 2,3 > n)- The size of the coreset is bounded by k O( 2d min (d, E log(n) (og()max)) m), where
log log(d) / ymax / /og (mmx)) ) + log log(1/n) pd + log (Vmax) + log log(1/1)
p 1
p = 2.
We put our bounds from Corollary 3.6 and Lemma 3.7 together into the main theorem of the sensitivity framework Proposition A.5] That is, we calculate the sensitivity upper bounds 8t, take a sample according to the distribution p; si/ Σj=1 $j of the respective size, and reweight them accordingly. Then, the calculated bounds on the VC dimension and total sensitivity yield a bound on the required size, such that Proposition A.J]yields with constant probability that the reweighted subsample gives a (1 + -))-apprxximation uniformly over / E D(1)-
Proof of Theorem 3.8
Since the Auerbach basis used in the sensitivity calculations of Lemma 3.7 can be expensive to compute depending on the value of p, we use more efficient approximation techniques here.
In the case p 2, we use a sparse oblivious fz subspace embedding by [9] which was explicitly proven in 34 Lemma 2. 2.14], to give (V2d, v2, 2)- wendl-condiiooned basis. This is within absolute constant factors the (vd, 1, condiitiini of the Auerbach basis. Thus, the complexities given in Lemma 3.7 do not change in O-notation.
In the case p- spanning sets. This a relaxation of the vell-conditioned basis U given in Equation (7) where U E R and E R", are allowed to have slightly increased dimension only need to bound norms of vectors of the form X 8 in the columnspan of the data matrix whose rank is bounded by d. We thus require the bounds to hold only for y E R 8 > d that actually represent vectors X x in a different basis. Other aspects of Equation (7) remain unchanged.
use more recent technique introduced in 44 called (a, % collccciiiidd
d. "We also note that
Our proof is nearly verbatim to [44 Theorem 1.11]. Their algorithm constructs a matrix R E igx's We set U = XR E Rn gnxs, By [44] Lemma 4.1], this can be done with s = O log log(d)). such that each column U70), for E [s] satisfies [ = 1, and for every || XX BI = there exists a vector y E R such that X33 3 Uy and ||yl|a = 0(1).
For p 1. this yields that U is an (a, y, 1) --eeel-condiiioneed spanning set, where a Od log(d)), and = O(1). For the bound on a, it holds that
|1||1 = Σ |100 = O(dloglog(()
For the bound on y, note that the Hölder dual for p 1 is g co. Now, it follows for every y R that represents any X33 as a linear combination of columns of U that,
ll < || I 0(1) = 0(1) = Uyl)
As a consequence in the case p = 1, this computational result replaces the d factor from the Auerbach basis in the proof of Lemma 3.7 by factor (a7)²² = O(dlog (d)), we have claimed. D
22

---

D Proofs for main approximation result
Recall Equation Dn) 3 = argmin S
Lemma 4.1. It holds for sufficiently small > that
( & (1 ((3)))((X3)))
Proof of Lemma 4.7] Recall from Section 2 that we choose X to be the design matrix that includes an intercept, i.c., every row of X is of the form (1,)(1) 22)) ..... zd)-1)). Note that by definition we have that D(1) (0) is proper subset. Thus, f(X (X follows immediately.
Next, define for every 3 E (() its shifted version to in one-to-one correspondence with a unique 3' D(1) via the translation
B = B 7e1
(15)
where 61 is the first standard basis vector. Recall that we choose the first column of X to be (1..... 1) R".
Now consider (8*) E D(n) to be the shifted version of the global optimizer 3 E D(0). Since 3 minimizes the loss function over D()), it follows that f(X (*) S f(X()*)).
Finally, claim that there exists absolute constant C 2 0 such that for all sufficiently small
> 0 we have for all 3 that Equation (9) holds, i.e.,
f(x8') S f(X C)
By summing the result of Lemma 2.1 over all inputs, we have that f(X3*) Applying our claim to 3* thus yields
((X()))) s f(X3)) + nf'n + nCf((3*) s (1 + Cn)s((B)) (1 (X8*)
This proves that Lemma 2.1 and Equation (9) imply the upper bound of the lemma.
It remains prove claim of Equation (9) for 1, and p 2 separately.
Case p = 1: We have
S(X = Σ
(r: + 7) log(2; + +) + log(us!)
se(n
< Σ
xxB y: log(x,,)) + log(ys!) + ((x3)) + m
xE(a
which satisfies Equation (9) with C' O.
Case 2: We have
f(X8') Σ (x, 21j038 + 1)2 2y log(2; + m) + 2y, log(2:5) 2y, (2g(3;)))))))))))))))))))) log y:!
iE|M]
x,3 x,5+n +1 x,3
(x + 2n + n2² - 2y, log
2y log(z,3) + log y:!
:E[m]
x.B 1
=f(X + Σ 2np08 + 12² - -2 log
xz
iE(m]
=f(X3) + Σ
21pr,,3 3 11² 22, log
1 1 17
KE mg
=f(X0) + nn
2 + 2n
xx3
yí log
+
z
m
23

---

Now using that log(1 + x) Qy.
2
2_ Itx
Vx >
1, we bound the error for every y E N by function
L log
[
?
=
y =: d(2),
(16)
"
2 2+1
The first and second derivatives are given by
o'(z) = +
21
2 1,
+ 8)2
2y(z +6)
(²(2) (= 6)1
< 0,
from which we know that the function is monotonically increasing and concave. On the other hand, we know that 9y(2) is convex, monotonically increasing on E ly 1/2 oo) and is bounded below by
1. We can thus show the claim for C = 3 by comparing the functions as well as their derivatives at
2 = /1/ + 1.
First note that by monotonicity, we have for all S y1/2 + 1 that
x(2) S (ly + 1) (2 + 1)² 7( 1/2 + y
y + 2y 1/2
+ ny
12 17 y
22 + + 7
12/2
+ 77
11/2 1 77 + (1 + 2/2
(1+ n)y 1/2
11/2 + 11
11 - +
(1 + n)y 1/2
1 +
1/ = 1+ 1 3. 3g(2).
In particular this holds for /2 1 as well.
remains to compare the derivatives for the choice of 2 = =/ + 1. We have
o'yy 1/2 (1) 01/2+1+877 8)2
y
I 1 +
12)2 = 2,
y
which implies that we also have
3/' + 1) = 3-2 1/2 /2 + +1)2
11 +1
=3.2 + U 2y 1/2 + 1
11/2 +
1/2 2yy2/2 +1
23
2
2 2- 2 (2
1/2 + +1)
y2/2 +1
This completes the proof of (0z) < 3g(z) for all by convexity of g and concavity of ạb
Overall, the claim of Equation (9) follows with C =3pp - 1), for both p E {1,2), which also concludes the proof of the lemma.
Theorem 4.2. Let E E 1/14) Let (C,w) be a coreset according to Theorem 3.8 Let B argminseDie (C3), 3" := argmin B)) Then
f(x3) < f(x)) < (1 (1+ +))
Proof of Theorem 4.2 We invoke Lemma 4.1 with & to show that the shifted version of 3* i.e.
ggood y = 8" nec1 is (1 apprroxxiataoo and Byood D(r). Thus, the optimizer
(f')* E ((n) cannot be worse than a (1 + E) -aprrxximation.
The coreset construction of Theorem 3.8 works uniformly over D(m). It thus yields coreset C C X of size l with weights E Re such that if we denote the weighted loss on the coreset by fw (CB3) it satisfies
VB E D(n) =)) < (c < (1+s)
(17)
24

---

Then defining ggood == 8" + ne,, we have f(x3) 2 f(X since D(n) C D(0). Moreover,
assuming 0 < 5 S 1/2 we have
1
1
f(X3) - 1 fv(33)
Fu(CB
1 1
1 + E [(X
(1 5)
S 1
S (1+
rescaling finishes our main result.
E Proofs for lower bounds
Lemma 6.1. Consider number n. 8 of points equidistant on unit circle in a 2-dimensional affine subspace embedded in R
,, 2 3, each with label yı 1. Then the sensifivity of each point for the Poisson model with pth-root-link for p E {1,2] arbitrarily close to L. Consequently, any coreset for the Poisson regression model must comprise all (2()) imput points.
Proof of Lemma 6.1] We first note that our construction can be embedded arbitrarily in 2 dimensional spaces. For simplicity, we describe the construction for d = 3, where the first dimension corresponds the affine translation and the other two describe the location in the 2 2-dimensional subspace.
Recall that our point set is given by x; (1, cos( 2xd) ), sin( (xz )), [n]. and ys for every i E [n]. By symmetry of the construction, suffices to analyze w.l.o.g. the sensitivity of point Tn (1, cos(2 sin sin (2+)) = (1, 0). Since the sensitivity is defined as the supremum over all B, it also suffices to find one 3 for which the sensitivity is arbitrarily close to 1. To this end, for a small
n yet to be determined, we choose
B (1 + 7/ cos( sin((T))) 7, -1.00"
where + 17 represents a translation term and (-1,0) 0) represents a 'normal' term that lives within the 2-dimensional subspace mentioned above. This normal term defines a hyperplane H (which is in fact line) within the 2-dimensional subspace. The normal points towards the center of the point set, and the hyperplane H/ is at distance exactly xr, 1 +
1) from In.
simple trigonometric calculation yields that the separation between Vn, and the neighboring points I1 and In-1 along the direction orthogonal to H is exactly 1 cos(2 Since n 2 8, it holds that (2t/n)² /3 < 1 cos(2 /n) < (2 /n/) 2 /2 by second order Taylor series expansion of the cosine function. All other points are even farther away from 2n than 21 and In-1, and therefore also further from H. Also note that we let s (1, (1,-1,0) 0) be the antipodal point of x, on the circle, we see that the distances of all points from H are less than x/ 1 + 17
2 + < 3.
Recall that for arbitrary p 2 1, the function gy defined in Equation (4) is minimized at y 1/,, which in this case equals y; 1. We have that roughly half of the points distance at most 3 from H. By strict convexity, we have that is also strictly increasing on the interval [1, oo). We thus upper bound the contribution of each of these points by at most
distance at least + 7 and
gi (x,3)=
<
n2 9 (3) = (3 - (3g(33)) 9 - 8 < 8 8log(n).
(18)
For the other half of the points (except xx,) the contribution is upper bounded by the loss that occurs closest to H. By strict convexity again, we have that is also strictly decreasing on the interval (0, 1]. We argued that the points are sufficiently separated, so we get that each of their contributions is bounded by
91 (x+3) < 91 (1 (os((7/n)) 9 ((2T/))3/3 S (1/n²)
< 1/n22 2p log 1/n) = 1/n² 2p (og()))
< 1 + 4 log(n) < 8 log(n))
(19)
Now, choosing 7 exp(-n²), we have that the cost of the point In is lower bounded by
1
91 = ())
(exp(nz))
+ +plog(exp(n2)) 2 n²
25

---

Thus, we have that
91 (Tn
n²
Sz sup 3'
30
1.
E 91 (x,35)
n² + 8n log(n)
Since there is no sensitivity upper bound below 1 that holds for arbitrarily large n and for each point, 4T Lemma A.IJ implies that the coreset must comprise all Q(n)) points.
that approximates negative log eeglikklihood queries (B) for Poisson regression with the pth-root-link for E {1, such that for some yp Z 1 holds that
Lemma 6.2. Let Ei be a data structure for D [X, y] Baxd R", d
vB E B. _(X3) S En(3) S 9 ((X
If 8log(n) then ED requires Q(n) bits of memory.
Proof of Lemma 6.2 We reduce from the indexing problem for which know that it has one-way randomized communication complexity 2(n) [25). We construct a protocol as follows. Alice is given a vector E {0, 1 She produces for every with b, the points x; = (1, cos( (mm ), sin 2mi )) n set to Y/ = 1. She builds and sends En Bob, whose task to guess the bit by. Let the size of En in bit complexity be s(n) bits, and note that s(n) corresponds to the amount of bits that have been communicated. Bob chooses query (1 + 77, cos( 2md sin( 2xz/ n
in canonical order. The corresponding counts
By symmetry of the construction, we can assume w.l.o.g. that the upper bounds Equations (18) and (19] on the costs in the proof of Lemma 6.I continue to hold.
Thus, bj = 0, then 2; does not exist and the cost of all other points is bounded from above by
3(X S 8n log(n).
If by 1, then xy is at distance exactly
2
[mT
2
zy = [1,00
sin
1 + 17, COS
sin
2
2
+1+10 17 008
sim
1 1) - 1
11
Thus, choosing 1) exp( n the cost is bounded below by f(x3) 2 91(1)) 2 n² as in the proof Lemma 6.1
I) Bob can distinguish these two cases based on the data structure only, by deciding whether ( is strictly smaller larger than n²², Consequently, holds that
Given that < NT (n)
s(n) 2 Q()), since this solves the indexing problem.
Lemma 6.3. For all (-1/e,0), 0), holds that Wo(x) S 2 ter) -.
Proof of Lemma 6.3 First we claim that
T - log(1 + r) 2 log(1 - 72) -loo 127), T TE (-1,0).
(20)
Define ((T) = T - log(1 + +) + 1 log(1 - 72). Then 1(0) = The derivative of
1
2r
1- 72 - 11
- 22
((7)=
1- O, (-E
1 1-
1-
which implies that for every T E (-1,0) have 1(7) 2 0. This proves Equation (20) Next, we
+1) follow the proof strategy of (38 Theorem 3.2]: define new variable - = 7(x) = -(W(x)) +1)
so that - Wo(x)= = 1 11+4. T. Since Wo(z)eWo(u) = x for x 2 -1/e, the definition of r implies that
(1+T)e -(+tr) = --r. Let E [-1/e, 0) be arbitrary. Then since (0) = and (-(-//) = 11
have ((x) E (-1,0), and thus
(1 + T)e (1+T) (1+ - +
log(1 +7) log(-a)
26

---

log( -1- S loog( (xx( -
by Equation (20)
1 ++|og(-1)) slog( VI - -2).
The last inequality is equivalent to
-I-
e --- - ExX S VI 72.
1 1 log
Now since (vI- 72)2 = 1 that
+ (5)² -
< -
= (1- = for every T E (-1, it follows =01
1
ex
< - 2 2 el ex + [o(c) + 5 + ex),
where the rightmost equivalence above follows from the definition = (Wo(z)+ The inequality on the right-hand side above implies the desired conclusion.
Recall the function B9: defined in Equation (4)
Lemma 6.4. Let y E N be arbitrary, p 1, and y in the definition Equation (4) of
By. Let (2) = (a-gb/m)) for 2 > O. Then By and hx are tangent to each other if and only if (y) = (Wol (z!)"/ exp(2)) ) +1)=1, in which case the unique tangent point is z² (v) = -x))) In addition, X (v) = @(v Ymax/ log (m
ux² (w)
Proof of Lemma 6.4) A point of tangency å of the curves By and hy is defined as a point where the functions agree and their derivatives agree. To identify the point where the derivatives of gy and hy agree, we observe
1 - -2
03(3)= = 1- 2
-
Ay -
Since gy 2 2 log(2ry) and (=) < 0 for < y if y, the tangent point cannot lie in the interval (0, v]. Hence, 8 >>> y must hold. Combining this observation with the equation غ = X-1 the point where the derivatives agree, we conclude that À > 1.
Ay for
Now suppose that E is point where the functions By and hy agree:
h2 (3) - (2)
(0 - + ī
y
+ log(y!)
x
y log(2) -
1
y
+ log(v!)
A
x
Ay
-1
1
log(3) 33 -
+ log(v!)
Ay
-1
exp (
B exp
(/!)2/0
Xyy
Ay
Au
1
exp
exp
A
If is a point of tangency, then by the equivalent condition above for d' 11z. it follows that
2 Ay Substituting this into the last equation above yields
Ay
11
(2) (21)
- -1ex((11) =-
exp
1/ expl
=
1
exp
1
1
A
27

---

(1 (1-1 exp x -1)
(/!) exp(-2)
The last equation above yields that
- X
exp(2) ex)))))
E Z.
(21)
We can further specify the branches of the Lambert W function follows. By definition of the factorial, 1 S (o1)tvv for all E N. On the other hand, by Stirling's approximation,
exp(1
exp(1 T2
12y
y
exp(1), D BEN
(22)
(2my) 1/(2g)
(y1)
(2mT)
Hence,
exp(-11 (u!)z/1
y 5 exp( exp((-), 2), VEN.
This implies that the argument of the Lambert W function in Equation (21) lies in the interval ----,---2 By definition of the Lambert W function, this in turn implies that in Equation (21)
we need to consider only k- = 0 and & = 1, which means that
1 X
{ Wh (2!) (0p())) + & {0, -1]
(z)
For all x E [- exp(-1). This follows from the definition of Wo as the principal branch of the Lambert W function. Hence,
2)). Wo(x) 2 (2),, with equality holding only for a
(²)
y VEN,
Wo (ul)z/v exp(2)
which proves the first statement of Lemma 6.4.
Next, we show that X (v) @(v Vmax/ log(ymax)) We use a lower bound for the principal branch Wo of the Lambert W function for negative arguments from [38 Theorem 3.2]:
(ex ( - < Wo(x),
Vo E 0j.
(23)
Since we showed above that the argument of the Lambert W function in Equation (21) lies in the interval (-e-1, 22, we may apply Equation (23)
Combining Lemma 6.3 with Equation (23)
implies that for all 1-e-1,0,
ex + - 1 (x) & 22(1 + ex)
Wo(z)+I I
2(1 ex)
(((+ez)
By Equation (22). we may thus
Whit
in the above inequalities, which yields
-1/2
-y - -1/2
2 2-1/2
(y!)1/2
e- +1)
<
= =x= -
(Tvt)//v'
e- +1
Wo
( e-2 +
(24)
for all y E N. Again by Equation (22)
1
1
1
1 - exp
log (2gg))y))
-l +1<11-1-- exp
log (TTy)
12y² + y
2y
(1!)1/""
12ny²
2y
Note that
1
1
0
+ log log (2Ty)
log log(2 (2zy).
12y + y
2y
12y²
2y
Since y + 12y + 2y (2(y)) is decreasing on [1, oc) and has the value 1 log(2x) at yty= =
12
it suffices to consider the quantity exp(-z) 2) for x E [0, 21. By Taylor's approximation, we have
exp(-x) x, Vr [0,1)
(25)
2
28

---

and applying the lower bound in Equation (25) to the lower bound for (y!)ur e- Equation (24) yields
+ below
log (2g()
(y!)'/9
exp
12y² + +
2y
1
1 log(2Ty)
12y² +
2y
1
1 6
1/12) log (2ry)
12y² +
for y E N. Applying this upper bound for X (v)
Equation (24) yields for all y E N
12y² +
1/2
26y²
1/2
= =0
=0(1
(V log(u)
(1) < 2
6(y 1/12) log (2Ty)
Gy (2xg)
Applying the upper bound in Equation (25) tion (24) yields
to the upper bound for
w1/f/7 e
below
Equa-
y (yl)
1
1
log(2ny)
1 + by (2g(2)y)) 12y²
12y log
12y²
2y
12y²
where the rightmost inequality follows since the function y + 6y log(2ry) is increasing on [1, oo) and has value strictly larger than 1 at 1. Applying the inequality above to the lower bound for X (y) in Equation (24) yields
(w) 2
(1
y²
1/2
-o(V ([Tg(u)
= =S
Vy E N.
2 log(2Tr)
log(u)
This completes the proof that X X²())
O(v Ymaxx/ log(Uuass)
Lemma 6.5. Let p E N. p 2 3. Then there does not exist an absolute constant C 2 such that for all sufficiently small r > 0 and for all 3 E D(0), 8 = 3 + nei D()) satisfies
f(x3') < f(X +
(9)
Proof of Lemma 6.5
First note that
f(XB')
Σ
(r, + 1)) py: log(r; + +)) log(vi!)
im(m]
p-1
Σ
(x,3)) + n/² + Σ
(x,,)) xp-e)) py, log(I;; + +n) + log(u:))
1E/m]
=((X3) + n
Σ
(x:3)² pp= piy log
Ir, + 17
3
XE|M
where the last equation follows by the definition of f(XB), given the hypothesis on Define for every y E N the auxiliary function
2 (x+1)) (2 )
(2) = 7
1
Σ
ippe
py log
2 0.
(26)
f=1
Then the inequality Equation (9) is equivalent to
Σ (1.3) < C
Σ 9ys (x.
05 Σ
Cgn, (xxB) 40 (.:.),
3E(n]
iEin]
which implies the following statement: there exists C, such that for every N, (Ji)ee())
N" 7 S 17", and (zi)kE(n)
IIsEjn]U 1/,, xo), it holds that
0 < Σ Cgy.(z)) - (P..)..p..).
(27)
sE[m]
29

---

This statement yields the following necessary condition for Equation (9) there exists C, > 0 such that for every n E N. (yi)xe[n) N", 7) S n),, and (zi) E II(m() Bi 1/p 00), least one summand on the right-hand side must satisfy 0 I Cg (2,) - (...).((2)) This is because every summand in the sum in Equatton (27) were strictly negative, then the sum itself must be strictly negative. If the necessary condition above does not hold, then by considering the contrapositive, we conclude that Equation does not hold either.
We now show that the necessary condition does not hold, by proving that for every C, 17 > 0 and E N, there exists (y))e(() E N" such that for every i E [n], Cgy, (v: 01. ((e 1/P) < 0. Indeed, for every E [n]. suppose that every Yi E N satisfies
2C
g(r-2)/p
(28)
p(p-1) 1)m
logg(2T) + 12y
By the hypothesis that p 2 3 and by the fact that the denominator of the right-hand side grows more slowly than the numerator, it follows that there exist infinitely many values of y that satisfy Equation (28) Thus it remains to show that Equation (28) implies Cgy (r)) -1... < O.
By the inequality
_ 14x
< log(1 + z). x >> 0, we obtain
1 < log 1+=- ) Vn, 0.
2 "
Rewrite the auxiliary function Pl.pp from Eqqution (26) and bound it from below, first by using the lower bound above, and then by using the hypothesis that p N. 2 3:
(1,,,p(2)=
p
11 p-t-1_
-1- log
2 +
2
IV
2
=np--e e-1
p
y
pz 1
p(p
2
p-2
2n
- p y
2
Setting yl/r, it thus suffices to show that
(yy < yoo-D)/ n7 2
/002)//0 -y-- y111/0
p1
1-1
y00-2)/p
21/p.
(29)
2
Using 4 to evaluate By (3-111) (P) and using the upper bound on log(y!) from Stirling's s approximation,
we conclude that 9y (y'/P) /PP) < log(2 + 12y" Now Equation (28) implies Equation (29)
because
c
ct log(2my) + 12y
p p-1
(1--2)/ 2)/r
2C p(p - 1)m
(2-2))/ y y 2)/F
< prj
2/ log (2TT) + T2y
This completes the proof.
F On the shifted domain and feasibility
In this section, we show that the restriction to D(n) in Theorem 3.8 and Section 4 do not lead to feasibility issues.
First recall that we had defined for any 2 0
D(n) = {B E TRdd Vi, 2. > 1))
Also recall that for the ID- and square root-link - and in fact for any pth-root-link the loss function defined in Equations (3) and (4) includes a log(2;33 (x)8) term, which restricts the feasible region to 3 such that for all F,, & E [r]] it holds that 3 > Thus 3 E D(0) is the natural domain induced by the model. In particular, this restriction is not our choice.
Our domain shift idea restricts the domain even further to D(7) C D(0), for vj > 0. Clearly, some solutions that are feasible in the problem formulated over (00) are no longer feasible in the
30

---

problem formulated over D()).. But as we prove in Appendix D we can construct a coreset that holds for all [ E (r)), and D()) contains at least one that is (1 + -a-appooximttion for the optimal solution 3 of the problem on the original domain ((0), and evaluated on the full dataset. These two parts combined to prove that the final minimizer / E D(n) optimized on the coreset is (1+
compared to the value of f", when both are evaluated on the full dataset.
In the other direction, no infeasible solution can become feasible because of the proper subset relation D(n) C ((). Finally, note that for any data and any fixed 1) < oc, both, D(1) and D(0) are non-empty, since they consist of all /3 that parameterize hyperplanes that put the convex hull of input points (respectively, the additive r--inflation of the convex hull of input points) in the positive open halfspace. Thus there always exist feasible solutions, which means that no instance can become completely infeasible by means of our methods.
G Pseudocode, data and experimental results
G.1 Pseudocode
Here we give pseudocode for our coreset construction Algorithm 1 and for the subsequent optimization procedure Algorithm
Algorithm 1 Coreset algorithm for pth-root- Poisson regression.
Input: data X Raxd Y E No number of rows ls (see Theorem 3.8
Output: coreset C (X', Y', w) xgk' N²' I& with k' + [Ext(X)) rows
1: Let XCH be the extreme points Ext(X) on the convex hull of X or their e-kernel approximation
(cf. [Section 5), let Ycи their corresponding labels
2: Assign weight vector WCH = 1 corresponding to all points in XeH, Yeи
3: Let X = XeH. Y = = YCи
4: p 1 then
5: Calculate well-conditioned spanning set B (see Lemma 4.1))
6: Set Q XB
7:
else for p 2 2
8: Sketch the data obtain X = IIX (see
9: Calculate the Q decomposition of the sketch X QR
10:
Set Set = X (see [15 34))
11: Approximate the ép sensitivities by s; IQ + 1/n
12: Sample rows of X and Y i.i.d. with probability p: 8i/ E3 8j to obtain X Rexd and their corresponding labels Ycore E N4
Set Weore R such that Weore.j = 1/(kp)) ) if sample j corresponds row 14: Concatenate Xcr with Xeore to obtain X"
Concatenate YeH with Yoore obtain y"
16: Concatenate WCH with Wcore to obtain w
return C (X', Y¹, 82',0 w
Algorithm 2 Domain shift optimizer for pth-root-ling Poisson regression.
Input: data X Raxd Y e NH. error parameter E (0, 2)
Output: (1 +1+22 8) -ppprroxie solution 3.
Run Algorithm I with input X, and & as specified obtain the coreset (X', Y w.. Let XcH be defined as in Algoorihh !]
2:
Run any convex optimization algorithm to find the optimal solution 3 for the pth-root-ling link Poisson regression objective on (X', Y", w) under the constraint that Vz, XcH x,8 > (see Theorem 4.2)
3:
return 3.
31

---

G.2 Synthetic data generation
We generated for each p {1,2} dataset with dimensions 100 000, d 7 with labels corresponding to each point.
Construction of X:
Start with standard basis vectors (2:) and add the all zero vector 2g = be the extreme points on the convex hull.
Construct a matrix in R(n-7)xd with i.id. standard Gaussian entries. Translate and rescale the rows of this matrix so that the resulting rows lie in the interior of the convex hull of the points (z+); Concatenate the matrix with the resulting to the matrix with rows given by (z:)² generated by the first step. Call the resulting matrix E Raxd Horizontally concatenate a column of length n consisting only of ones to the left the matrix Z (add an intercept) to get X Rx(((+1)
3.
Construction of 3:
1. Draw one sample 3 ~ 10 N(0, Ta), with d = 6 as above.
2. Find min.g(m] (Z33); for Z from the construction of X
Compute 6 == max 1, 2// ( |2i),
4. Define B (b, B) E Rd+11
Construction of y:
1. Compute À == () E R
2. For each i = ,,...,,7,,, draw Y; Poisson(A:). and store the resulting vector as y.
G.3 Experimental illustration
All experiments were run on a commodity machine with Intel Core i7-7700K processor (4 cores, 4.2GHz, 32GB RAM) and took overall around 50 minutes complete. The Python code of [34] was adapted to the Poisson regression setting We applied it with the appropriate E {1, 2} to the 100 000, d generated detailed in the previous section.
datasets with dimensions
We compared our method to uniform sampling as a baseline, which is widely popular due to its simplicity and general applicability.
We varied the reduced size between 50 and 600 equal increments of size 50. For each reduced size and each method, we performed 201 independent repetitions.
Our results are shown in Figure The red (Poisson with pth-root-link) and blue (uniform sampling) solid lines display the median approximation ratio across 201 independent repetitions for each reduced size. The shaded areas below and above the solid lines indicate 2x standard errors of the respective medians.
For both p 21, the results look widely similar, although the case p 1 is slightly more distinctive. We thus focus our further description on the case p =
Our novel Poisson subsampling method generally outperforms uniform sampling, and their 2x standard error intervals are very narrow.
The shaded blue area under the blue solid line indicates that the 2x standard error for uniform sampling is slightly more narrow than the 2x standard error for I-Poisson regression, i.e., Poisson regression with ID-link. However, this error is optimistically calculated only on repetitions that succeed in providing a valid approximation when applied the original full data.
The shaded blue area above the blue solid line unbounded, which indicates that some of the repetitions yield solutions that are infeasible for the original full data problem, and thus fail to give appropriate approximation. Even in a few feasible cases, approximation ratios were 1.5 2.5 x 109, which may be explained by missing points that very close to the boundary of the convex hull, thus causing huge errors. The fraction of repetitions leading to infeasible solutions was always
*Our new code available at
32

---

Synthetic, p-1
Synthetic, p-2
1.010
1,020
Loisson
2 Polssoo
1,088
medi on spproximation ratio
1.015
1.006
1,010
1.001
1.005
1.002
1,000
1,000
100
200
300
400 500
600
100
200
300
400
500
600
reduced
reducced
Figure 1: Experimental results for two synthetic data sets with p (left), respectively p (right). Our method is presented in red and compared against uniform sampling, which is presented blue. Solid lines indicate the median and shaded areas indicate #2 standard errors around the median taken across 201 independent repetitions for each reduced size between 50 and 600 in equal increment steps of 50. For the blue shaded area below the blue solid line, only feasible repetitions while the blue shaded area above represents the unbounded standard error without this restriction. For some lower reduced sizes, line. This indicates that more than half of the repetitions gave infeasible results when using uniform sampling with low sample sizes, while our method never produced infeasible results.
counted,
the median was infinite, which results in interrupted blue solid
non-negligible and we note that the solid blue line was interrupted below a reduced size of 250 (respectively 150 for p 2) meaning that even the median was infinite, indicating that more than half of the repetitions of uniform sampling were infeasible for the original problem.
In contrast to that, our method produced feasible results in all repetitions, across all reduced sizes, confirming our discussion in Appendix F. and giving approximation ratios very close to 1.
33

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We state the contributions of our work in the abstract and also Section I.] We support claims with proven theoretical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We prove several lower bounds in Section 6 that indicate the limitations of constructing coresets for Poisson models general, as well as limitations of our specific approach and analysis.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
34

---

Answer:
[Yes]
Justification:
The proof of every lemma and theorem is given in the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: This information is provided in Appendix G Experiments and data can be reproduced statistically as well as exactly using the code in the public repository.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
35

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: See the Git code repository https: wwt.ecccmmmiia com/Tim907/ poisson mrisson-regressionn
regression/ which contains all required code and instructions to install and reproduce all experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
y /nips. /nips.cc//ppp httpss/ccccclcgguideeeee///////e htwpbll//ggiiiee//dduuubiiiiiiie
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/ettails
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
This information is provided in Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report 2SE of the median in our plots. See the caption for Figure and the detailed description in Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
36

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computing resources and total runtime are detailed in Appeedix G| We only used standard commodity hardware on which all experiments could be carried out in around 50 minutes.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps:/neurrpps wwwpuurrps.ccpcuuueeeee c http:////ccppppcceiccctcccccaaee
Answer: [Yes]
Justification: Our research does not involve human subjects or human participants, and addresses all data-related concerns in the NeurlPS Code of Ethics. We not anticipate any potentially harmful consequences of our research.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
37

---

Justification: We consider the research in this paper to be foundational research that is not tied any particular application or deployment. We do not anticipate any negative application unique to the research presented in this paper. Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The risks posed by the Poisson model analyzed in this paper are no greater than the risks posed by other statistical models used in regression, for example. No datasets were released as part of this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We only used existing code for which one the authors has full rights to modify and reuse. The original source appropriately eited.
Guidelines:
38

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thcode. com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The new codes published an open GitHub repository and documented so as to allow installing, running and reusing them.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
39

---

Justification:
The paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
40


Reviews:
[{"review_id": "Cy5DUc5swb", "reviewer": "Reviewer_SQxM", "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.", "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?", "limitations": "see weaknesses", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n2) 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. \n\nThere 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. \n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We will describe some proof-of-concept results that have been obtained since we submitted the paper for review.\nWe have generated 6-dimensional data that consists of the vertices of a regular simplex (as extreme points on the convex hull) and $n$ further points from a normal distribution rescaled to be in the convex hull. Our resulting approximation factors are close to $1$ even for only $20-50$ subsamples except for a few repetitions where it fails, and gives factors $2-7$. In contrast, even for $500$ samples, uniform sampling fails even to produce feasible $\\beta$ in one third of the cases, and even when results are feasible and the extreme points are included, some approximation ratios are in the order of $1.5-2.5 \\times 10^9$ which are clearly explained by missing points that are very close to the boundary of the convex hull, thus causing huge errors. We will elaborate more on this and add corresponding numerical proof-of-concept in the supplementary material.\n\nWe agree that the notation can be improved and will change the notation of coordinates of $x\\in\\mathbb{R}^d$ to $x=(1,x^{(1)},x^{(2)},\\ldots,x^{(d-1)})$. We will continue to write $x_j$ to denote the $j$-th vector in the dataset.\n\nIf by 'final part of the paper' the reviewer was referring to Section 6, then it is true that we had to remove some text from this section due to space constraints. In particular, we will give the definition of the Lambert function in the text and give some intuition as to why it is necessary to consider this function. Some intuition is already included in the last paragraph of Section 1.2.\n\nFor ID-link Poisson regression, the set of feasible $\\beta$ also consists of $\\beta$ such that $x_i\\beta >0$. This is because the loss function involves $\\log (x_i\\beta)$ for the ID link as well.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fdStYcJA2D", "reviewer": "Reviewer_73Rm", "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.", "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.", "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.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. We have difficulty understanding what exactly is lacking in the structure of the paper. We remind the reviewer of the structure of our paper: In Section 1, we provide an introduction that introduces the crucial concepts of a $(1+\\varepsilon)$-coreset and sublinear bounds on the coreset size. In Section 1.1, we list our contributions. In Section 1.2, we describe the high level ideas of our techniques --- for almost one page --- and introduce the important ideas that underpin our results. In Section 1.3, we give a representative sample of related work. In Section 2, we introduce more important concepts, e.g. the complexity parameter in (2) and the loss functions in (3) and (4) that are essential for the rest of the paper. In Section 3, we again introduce important concepts relating to VC dimension and the loss function from Section 2. After more than six pages of structured introduction of concepts, our first novel result appears on page 7 in Theorem 3.8, which gives an upper bound on the coreset size. In Section 4, we state our main approximation result, and introduce a novel shifting idea to overcome a difficulty posed by our loss function. There still remain difficulties for the subsequent optimization. We address these difficulties in Section 5, using ideas based on previous literature. In Section 6, we give further context to the upper bound on the coreset size from Theorem 3.8. We do this by providing lower bounds on the coreset size.\n\nThe above shows that we introduced important concepts and presented our main results in a logical progression. Note also that we already summarized the contents of our paper in the abstract. We do not agree that a conclusion is absolutely necessary for a \"well-constructed structure\", but we would be willing to include a conclusion on a tenth page. For our initial submission, we had already moved as much content as possible to the supplementary and kept only the important results of our work in the main paper. Note that no other reviewer had issues with the structure of our paper. \n\n2. The goal of a literature review in an 8-page paper is not to be detailed or exhaustive. Instead, the goal is to point the reader to representative examples of relevant literature, and to explain the differences between these examples and our present work, and this is exactly what we have done on lines 109-117. If the reviewer can point to specific examples of literature that they feel should have been included in the review, then we invite the reviewer to state these examples and to indicate why these suggestions are not adequately represented by the references we cite in lines 109-117.\n\n3. We are willing to provide pseudocode in the supplementary material. \n\n4. We agree that numerical results that provide proof of concept are not necessary but could be beneficial. We now have results of this kind and are willing to report them in the supplementary material.\nPlease refer to our response to reviewer SQxM for more details regarding numerical results.\n\nWe suspect that the confusion is due to an issue with our notation: on line 119, \"$x=(1,x_1,\\ldots,x_{d-1})\\in\\mathbb{R}^{d}$\" indicates a row vector, whereas in Theorem 3.8, $x_i$ on line 277 indicates a row vector. We will change the notation of coordinates of $x\\in\\mathbb{R}^d$ to $x=(1,x^{(1)},x^{(2)},\\ldots,x^{(d-1)})$ on line 119 and consistently write $x_i$ to denote the $i$-th row vector in the data matrix $X\\in\\mathbb{R}^{n\\times d}$ as in Theorem 3.8.\n\nThe reviewer describes the problem statement, proof, and results  as lacking clarity, and also as being meaningful. It is difficult for us to understand how both these statements can be true, since a necessary condition for a statement to be meaningful is that it is clear. We invite the reviewer to give one or two specific examples of results from our paper and to explain exactly what they do not understand about those results. Without this information, the reviewer's feedback appears vague and generic.\n\nWe point out that the other reviewers who are familiar with the area of coresets had no issues with the clarity of our problem statements, proofs, or results.\n\nOur paper is about constructing coresets of suitable size for Poisson regression, and we achieve this goal for some link functions that satisfy two criteria: 1) they can be treated using a combination of known coreset construction methods and our novel techniques and results; and 2) they have been and continue to be used in statistics (see response to reviewer HZmN). At no point do we claim generalizability of the proposed method to all link functions or all $p$. For this reason, the reviewer's comment appears to be finding issue with aspects of the paper that are not relevant to our stated goals.\nOn the contrary, our lower bound results (together with [23]) indicate the restriction to $p\\in\\\\{1,2\\\\}$, and exclude $p\\geq 3$, in particular the limiting case $p=\\infty$ that corresponds to the canonical log-link. According to the reviewing guidelines for NeurIPS: \"authors should be rewarded rather than punished for being up front about the limitations of their work\" (see lines 18-20, and 62-65 for early mentions of the limitations). Moreover $p\\in\\\\{1,2\\\\}$ are important standard choices in statistics (see response to reviewer HZmN).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b6XGKHnqdJ", "reviewer": "Reviewer_HZmN", "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.\n\nWhile 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.", "questions": "How are Lemmas 6.1 and 6.2 different from the lower bound argument of Theorem 6 in [23]?", "limitations": "See weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We do not agree with the statement that Poisson regression with links other than the canonical log link is 'artificial'. The identity link was applied in epidemiology, see e.g. [a], or [b]. The root link function has been applied to forecasting for queueing systems [c], and to account for misspecification bias in maximum likelihood estimation [d]. When the estimated mean count of the data is zero, then the canonical log link causes problems that can be avoided by using the root link; see e.g. the paragraph \"Use of the square root (sqrt) link function\" in Section 5.4 of [e]. There are also informal discussions on stackexchange that shed more light on the choice of link function, which we unfortunately are not allowed to link in our response.\n\nWhile the general outline follows the same structure as previous papers (in fact almost all papers based on the sensitivity framework share this outline), the details are quite different. First note that the change of link function changes the norms to relate to from $\\ell_\\infty$-norm to $\\ell_1/\\ell_2$. The reviewer seems to suggest that this choice of polynomial functions resolves the problem given previous literature, which is indeed not the case as our linear lower bounds prove. Indeed, the fact that even after chosing polynomial functions, the loss still depends on the convex hull (i.e. $\\infty$-norm) is somewhat challenging in our analysis.\nNext, the 'balancedness' $\\mu$ assumption in [24,25] is needed due to the asymmetry of logistic/probit losses. However, in our paper, the asymmetry of Poisson loss is taken care of by our *novel domain shift* idea to avoid large contributions. It is not taken care of by the $\\rho$ parameter!\nAlso, $\\rho$ has a different interpretation that is natural for Poisson, but not applicable to logit nor probit. It balances the mean and the variance, and motivates 'moving' the polynomial lower envelopes. Without this, we stress that the slope $\\lambda$ parameter would need to be $y_{\\max}/\\log(y_{\\max})$ since with growing $y$ the loss function 'moves' polynomially along the $x\\beta$ axis but only logarithmically along the $g_y(x\\beta)$ axis. See our high level discussion in lines 83-89.\nIndeed, though not obvious from the current writeup, this induces a $\\sum_{i \\in[n]} y_i =\\Omega(n)$ dependence. So it is a completely different difficulty that the supposedly 'not surprising' or 'straightforward' analysis addresses by the balancing condition. The most common point between $\\rho$ and $\\mu$ is the fact that both correspond to or arise naturally from their respective statistical modeling.\nPlease also consider the further discussion and the separation between the $p\\in\\\\{1,2\\\\}$ cases with respect to the $y_{\\max}$ dependence. These are further points that were previously completely unexplored and led to novel and interesting non-trivial results regarding the important Lambert $W_0$ function as a byproduct.\nSo while some basic parts were borrowed from previous literature that we cited, we kindly ask the reviewer to recognize as well our non-trivial extensions and modifications that go beyond the polynomial growth and $\\ell_p$ space approximation of [24,25] and other previous literature.\n\nLemmas 6.1 and 6.2 are not significantly different from the lower bound argument of Theorem 6 in [23]. Indeed, we had already stated in lines 96-97 that these results are adapted from previous literature, admittedly without specifying Lemmas 6.1 and 6.2 exactly. This was an oversight on our part and we will clarify the connection to Theorem 6 in [23]. While the construction of the bad dataset is similar to [23] and is widely standard across previous literature as in e.g. [25,27], [f], [g], **each** of these references as well as ours adapt the construction to the peculiarities of their loss function under study. In particular, [23] puts the hyperplane into the convex hull to detect the query point being 'far' on the expensive exponential side of the loss (other points are on the cheaper linear side). In our case, we put the hyperplane outside the convex hull, to detect the query point being 'close' to the hyperplane, so that its negative logarithmic loss dominates the polynomial loss of all other points. While this can in hindsight be considered a minor modification, with the same reasoning, we should reject a lot of previous NeurIPS, ICML, AAAI publications for building on the IJCAI paper [g] (and maybe even older references).\n\n[a] I. C. Marschner (2010). \"Stable Computation of Maximum Likelihood Estimates in Identity Link Poisson Regression\", Journal of Computational and Graphical Statistics, 19(3), 666–683. DOI: 10.1198/jcgs.2010.09127\n\n[b] Donna Spiegelman, Ellen Hertzmark (2005). \"Easy SAS Calculations for Risk or Prevalence Ratios and Differences\", American Journal of Epidemiology, Volume 162, Issue 3, Pages 199–200. DOI: 10.1093/aje/kwi188\n\n[c] Haipeng Shen. Jianhua Z. Huang (2008). \"Forecasting time series of inhomogeneous Poisson processes with application to call center workforce management\", Ann. Appl. Stat. 2 (2) 601 - 623. DOI: 10.1214/08-AOAS164\n\n[d] B. Efron (1992). \"Poisson Overdispersion Estimates Based on the Method of Asymmetric Maximum Likelihood\", Journal of the American Statistical Association, 87(417), 98–107. DOI: 10.1080/01621459.1992.10475180\n\n[e] J. Maindonald, W. J. Braun (2010). \"Data analysis and graphics using R: an example-based approach\" (4th ed.). Cambridge University Press. DOI: 10.1017/CBO9781139194648 \n\n[f] J. Huggins, T. Campbell, T. Broderick (2016). \"Coresets for scalable Bayesian logistic regression\". Advances in neural information processing systems, 29. NeurIPS 2016.\n\n[g] Sariel Har-Peled, Dan Roth, Dav Zimak (2007). \"Maximum Margin Coresets for Active and Noise Tolerant Learning\". 836-841, Proceedings of the 20th International Joint Conference on Artificial Intelligence. IJCAI 2007.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Gafdx0MvjU", "reviewer": "Reviewer_L5wz", "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", "questions": "none", "limitations": "seems there is little discussion on limitation", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "In the last line of our abstract (lines 18-20) we state that we show the limitations of our analysis for $p$-th degree root link functions for $p\\geq 3$, and state that these limitations show the need for other methods if one aims to generalize our approach to this range of values of $p$. We repeat this point in lines 62-65. We also indicated on the NeurIPS Paper Checklist that Section 6 contains lower bounds that indicate the limitations of constructing coresets for $p$-th power link Poisson models in general, and the limitations of our specific approach and analysis, for instance the limitations regarding input/complexity parameters such as $y_{\\max}$. We also point to [23] for limitations regarding the canonical log link.\n\nOur lower bounds on the parameters, together with linear VC dimension and linear sensitivity, and linear $\\rho$ dependence leave no room for improvement if one uses the sensitivity framework. We also refer to the related work Section 1.3, where previous finite sample size results were either unbounded or $O(\\sqrt{d})$ error, instead of our $1+\\varepsilon$. We will add some comments on this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for their time and valuable comments on our submission, which we would like to address in individual responses below.

Meta-review: This paper studies the problem of constructing coresets for Poisson regression, obtaining sample complexity bounds that depend on a novel and natural complexity parameter of the problem. It builds on a growing line of work on constructing corsets for various “generalized linear models”, including, e.g., recent work on logistic regression. The paper has some clear draw backs, including a lack of experiments, limited new theoretical techniques, and it studies a non-canonical form of Poisson regression. Nevertheless, given the recent interest in coreset problems (e.g., due to their connection to agnostic active learning) we believe the paper will be of interest to many in the NeurIPS community, and all of the reviewers felt it should be accepted to the conference.
Decision: Accept (poster)