Research map / Learning theory and algorithms / Sample complexity
Data subsampling for Poisson regression with pth-root-link
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives coreset bounds for Poisson regression with ID- and square-root link via a novel balancing complexity parameter rho and domain shifting, showing Omega(n) lower bounds for coresets and sublinear coresets when rho is small.
Problem
Data subsampling (coresets) with (1±ε) guarantees for Poisson regression with pth-root links (ID and square-root), where classical sensitivity-based coresets fail due to the negative-log asymptote and the loss' translation with y.
Approach
Introduces a balancing complexity parameter rho bounding the ratio of sum |x_j beta|^p to sum |x_j beta - y_j^{1/p}|^p, and a domain-shifting approach restricting solutions to x_i beta > eta so sensitivity sampling yields sublinear coresets with (1+eps) guarantees; also a tight sqrt bound on Lambert W_0 for lower bounds.
Key results
- Omega(n) lower bound on coreset size for Poisson regression with pth-root link (points on circle), extending to any data reduction up to log factors.
- Square-root link admits O(log y_max) dependence on y_max; ID-link requires Theta(sqrt(y_max/log y_max)) dependence.
- Proves new bound W_0(x) <= sqrt(2(1+ex))-1 on [-1/e,0), improving prior cubic-root bound.
Surprising findings
- Domain shifting provably cannot give a 1+C*eps error for p>=3, indicating a limitation of the approach beyond p in {1,2}.
Limitations
- Lower bounds show Omega(n) coresets without small rho; coreset size linear in rho and d.
- Domain shifting fails for p>=3, so the method is limited to p in {1,2}.
- Convex hull extreme points must be stored, which can be Omega(n) in worst case.
Experimental setup
Metrics: approximation factor (1±ε) coreset size
Builds on: sensitivity framework well-conditioned basis l_p regression coresets
Closest papers by meaning
- Causal Discovery from Poisson Branching Structural Causal Model Using High-Order Cumulant with Path Analysis (AAAI 2024 · similarity 0.84)
- On the Identifiability of Poisson Branching Structural Causal Model Using Probability Generating Function (NeurIPS 2024 · similarity 0.83)
- Small coresets via negative dependence: DPPs, linear statistics, and concentration (NeurIPS 2024 · similarity 0.83)
- Coresets for Multiple $\ell_p$ Regression (ICML 2024 · similarity 0.83)
- Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation (ICML 2024 · similarity 0.83)
- Turnstile $\ell_p$ leverage score sampling with applications (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.