Source-linked AI summary
On Coresets for Logistic Regression
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff
TL;DR
Large datasets motivate data reduction, but logistic regression admits no sublinear streaming algorithm in general. The paper introduces a complexity measure and a sensitivity-sampling scheme; for small-µ-complexity data it provides provably sublinear coresets and reports favorable comparisons on real datasets.
Problem
Large datasets make data reduction attractive, while logistic regression has no sublinear streaming algorithm in general.
Source: §1 · pp. 1–2Method
The paper bounds sensitivity using µ-complexity and samples from a mixture of square-root ℓ2 leverage scores and uniform sampling.
Source: §1 · p. 2Results
For small-µ-complexity data, the first rigorously sublinear (1 ± ε)-coresets have leading factor O(ε^-2µ√n), and experiments report outperformance of uniform and state-of-the-art methods at competitive running time.
Source: §6 · pp. 8–9Takeaways & Limitations
A recursive construction reduces input-size dependence to O(log^c n) for absolute constant c, at the cost of increased dependence on µ.
Source: §6 · p. 9The coreset guarantee is restricted to data with small µ-complexity; the construction does not apply uniformly to all datasets.
Source: §2 · p. 3
Abstract
from arXiv · showhide
Coresets are one of the central methods to facilitate the analysis of large data sets. We continue a recent line of research applying the theory of coresets to logistic regression. First, we show a negative result, namely, that no strongly sublinear sized coresets exist for logistic regression. To deal with intractable worst-case instances we introduce a complexity measure $\mu(X)$, which quantifies the hardness of compressing a data set for logistic regression. $\mu(X)$ has an intuitive statistical interpretation that may be of independent interest. For data sets with bounded $\mu(X)$-complexity, we show that a novel sensitivity sampling scheme produces the first provably sublinear $(1\pm\varepsilon)$-coreset. We illustrate the performance of our method by comparing to uniform sampling as well as to state of the art methods in the area. The experiments are conducted on real world benchmark data for logistic regression.
1 Introduction
The introduction motivates data reduction for scaling analysis, then frames logistic-regression coresets as impossible in the general case but achievable under a bounded-complexity condition. It proposes a sensitivity-sampling mixture and reports that it outperforms uniform and k-means-based sensitivity sampling on real datasets.
1 Introduction
- Preprocessing data reduction can speed later optimization, and a coreset approximates the objective for every candidate solution using a smaller, possibly reweighted data subset.Source: §1 · p. 1
- Logistic regression has no sublinear streaming algorithm in general.Source: §1 · p. 2
- The sampling design uses square-root ℓ2 scores because large logistic-loss contributions grow almost linearly, while uniform sampling covers the exponential-decay region.Source: §1 · p. 2
- The proposed mixture distribution outperforms uniform and k-means-based sensitivity sampling by a wide margin on real datasets.It combines square-root ℓ2 leverage scores with uniform sampling.Source: §1 · p. 2
- For small-µ-complexity data, the proposed sampling scheme yields the first provably sublinear-size logistic-regression coreset.The total sensitivity is bounded in terms of µ.Source: §1 · p. 2
- Earlier sensitivity-based coreset work left explicit sublinear sensitivity bounds and an algorithm to compute them open; a recent construction differs in regularization and optimization-domain constraints.The prior sensitivity result is attributed to Huggins et al. (2016); the distinct construction to Tolochinsky & Feldman (2018).Source: §1 · p. 2
2 Preliminaries and Problem Setting
The section defines the logistic-regression objective and the goal of approximating it with a much smaller coreset. It introduces μ-complexity to distinguish data sets for which such compression can be guaranteed.
2 Preliminaries and Problem Setting
- The logistic-regression objective sums the negative log-likelihood over data rows, with labels folded into transformed rows x_i = −Y_iZ_i.The paper also considers a weighted version of this objective.Source: §2 · p. 3
- A coreset is a much smaller, possibly reweighted subset that approximates the logistic-regression objective for every query point.The setting assumes many observations relative to the number of dimensions.Source: §2 · p. 3
- The paper defines μ-complexity to quantify the compression difficulty of a weighted data set, and calls it μ-complex when μ_w(X) ≤ μ.The measure compares negative and positive weighted projections; the paper interprets small μ as a balance between incorrectly and correctly predicted odds.Source: §2 · pp. 3–4
- For μ-complex data, the coreset size has low-polynomial dependence on μ, d, and 1/ε but sublinear dependence on n.The value of μ_w(X) can be approximated in polynomial time, though the paper says this is unnecessary in practical applications.Source: §2 · p. 3
3 Lower Bounds
The section proves that logistic regression cannot have strongly sublinear coresets in general, even in two dimensions. This worst-case result motivates restricting guarantees to data sets with additional structure.
3 Lower Bounds
- Any one-pass streaming algorithm approximating the optimal solution within a finite multiplicative factor requires Ω(n/log n) bits on two-dimensional instances.Source: §3 · p. 4
- Any logistic-regression coreset for two-dimensional data requires at least Ω(n/log n) points.The result follows from a reduction to the INDEX communication game.Source: §3 · p. 4
- The lower bound also rules out finite additive error; it differs from prior work by applying regardless of whether coresets use input points.The authors state that the lower bounds are incomparable to those of Tolochinsky & Feldman (2018).Source: §3 · p. 4
4 Sampling via Sensitivity Scores
The section derives sensitivity bounds and sampling schemes for logistic-regression coresets. The base construction has roughly √n dependence, while a recursive construction reduces the dependence on n to polylogarithmic factors for μ-complex data.
Sensitivity Sampling
- Sensitivity sampling uses upper bounds on each point’s worst-case importance; its sample complexity depends on the sum of those bounds and the induced range-space VC dimension.The sensitivity estimates are used as sampling probabilities in a reweighted sample.Source: §4 · p. 5
Base Algorithm
- The base construction samples proportional to square-root ℓ2-leverage scores plus normalized weights, yielding coreset size roughly linear in μ and √n-dependent.Its theorem gives a two-pass construction with high probability; the stated size also depends on ε, d, μ, and weight range.Source: §4 · pp. 5–6
- The proposed mixture uses square-root ℓ2-leverage scores for the loss’s nearly linear tail and uniform sampling for the remaining domain.The authors report that the distribution outperforms uniform and k-means-based sensitivity sampling by a wide margin on real data sets.Source: §4 · pp. 5–6
- For the base algorithm, sensitivity bounds combine leverage scores and normalized weights, and the total sensitivity is bounded for μ-complex inputs.Source: §4 · p. 6
Recursive Algorithm
- The recursive construction reduces input-size dependence from √n to polylogarithmic factors for μ-complex data.It controls the growth of μ during recursion and handles the separate ℓ1 and uniform sampling components; the theorem gives a coreset with high probability using multiple passes.Source: §4 · pp. 6–7
- The recursive analysis uses an ℓ1 subspace embedding to control how much μ-complexity grows after subsampling and reweighting.The embedding holds simultaneously for all β with high probability.Source: §4 · p. 6
5 Experiments
The experiments compare QR-derived sensitivity sampling with uniform and k-means-based sampling on three real-world data sets. QR sampling is more accurate across the tested instances, with competitive running time and lower variability in the reported results.
Implementation Details
- The comparison includes uniform sampling and the k-means++-based sensitivity method of Huggins et al. (2016), with the optimization restricted to the full domain Rd.The Huggins et al. (2016) implementation was adapted to remove its small-radius restriction; QR’s exact decomposition was replaced by a fast sketching approximation.Source: §5 · p. 7
Experimental Assessment
- The experiments use WEBB SPAM, COVERTYPE, and KDD CUP ’99, with 30 subsampling sizes per data set and 20 repetitions per size.They measure relative negative log-likelihood error and running time after computing sampling probabilities, sampling, and optimizing on each sample.Source: §5 · p. 7
Evaluation
- QR sampling outperforms uniform and k-means-based sampling in accuracy across all instances, especially at small sample sizes.Figure 1 compares mean relative log-likelihood error and the error–running-time trade-off across data sets and coreset sizes.Source: §5 · p. 7, Figure 1 · p. 8
- For WEBB SPAM and COVERTYPE, QR is more accurate at similar time budgets except at high relative errors; for KDD CUP ’99, competitors stay above 15% error while QR falls below 4%.For KDD CUP ’99, QR never exceeds 22% relative error.Source: §5 · p. 8
- QR-distribution running time is comparable to k-means and slightly higher than uniform, never exceeding twice its competitors’ time.Its standard deviations were much lower than those of competing methods in the cases with larger variability, indicating more stable coresets for subsequent optimization.Source: §5 · p. 8
6 Conclusions
The paper establishes that general logistic-regression coresets cannot be sublinear, then introduces a data-complexity condition under which it constructs provably sublinear coresets. Its basic algorithm also outperforms the evaluated alternatives while remaining competitive in running time.
Conclusions
- For data with small µ-complexity, the paper develops the first rigorously sublinear (1 ± ε)-coresets for logistic regression.The leading size factor is O(ε^-2 µ√n); recursive construction reduces input-size dependence to O(log^c n), at increased dependence on µ.Source: §6 · pp. 8–9
- Sublinear coresets for logistic regression do not exist in general, so the construction requires assumptions on the data.The introduced µ(X) measures positive–negative class overlap and balance in their cardinalities.Source: §6 · p. 8
- The implementation of the basic algorithm outperforms uniform sampling and state-of-the-art coreset methods while remaining competitive in running time.Source: §6 · p. 9
A Proofs
The proofs establish a worst-case lower bound and derive the sensitivity-based sampling guarantees under µ-complexity. They also justify the QR sampling implementation, streaming variants, and recursive size reduction.
Proofs
- The µ-complexity calculation reduces to minimizing the negative-part ℓ1 norm over unit-ℓ1 vectors, which can be done by a linear program.The proof states that µ is bounded above by poly(d)/t and below by 1/t, where t is that minimum.Source: A Proofs · p. 12
- An INDEX reduction rules out sublinear-space streaming algorithms and, through the coreset–streaming connection, rules out general sublinear coresets.The reduction distinguishes a linearly separable instance with cost tending to zero from one with at least one misclassification and cost at least ln(2).Source: A Proofs · p. 12
- The range-space argument bounds the logistic-loss class’s VC dimension using affine hyperplane classifiers.The cited proof derives a d+1 bound for the unweighted class and an O(dt) bound for the partitioned weighted class.Source: A Proofs · pp. 12–13
- The QR-based sampler uses sensitivity upper bounds derived from a QR decomposition and samples input points proportional to rounded-up bounds.The rounding changes each bound by at most a factor of two; the sample-size result follows by applying the stated range-space theorem.Source: A Proofs · pp. 13–14
- A sketch and Johnson–Lindenstrauss transform approximate leverage-score row norms, enabling a two-pass streaming implementation in O(nnz(X) log n + poly(d) log n) time.The approximation increases the total sensitivity bound only by a small constant factor.Source: A Proofs · p. 14
- The recursive construction applies the sampler across levels, controlling the changing µ-complexity and failure probability to obtain the stated recursive coreset bound.At the final iteration, preserving µ-complexity is unnecessary, so the original approximation parameter can be used.Source: A Proofs · pp. 16–17
B Material for the experimental section
This appendix material reports full-data optimization baselines and additional variability and runtime summaries for the sampling methods.
B Material for the experimental section
- Table 1 reports each full data set’s optimal negative log-likelihood and mean optimization running time in seconds.Source: Table 1 · p. 18
- Figure 2 compares three sampling distributions across data sets and coreset sizes using 20 repetitions per size.Its rows show mean relative running time, standard deviation of relative log-likelihood error, and standard deviation of relative running time.Source: Figure 2 · p. 18
C Discussion of uniform sampling
On the constructed data set, uniform subsampling can miss two crucial points, leaving separable data; SGD then often returns a large β1 despite the optimum being (0, 0).
C Discussion of uniform sampling
- The example has m = 2n + 2 points in one dimension, with one extreme point in each class and n points at the opposite unit coordinate.Its optimal solution is β̂ = 0, with objective value m ln(2) < m.Source: C Discussion of uniform sampling · p. 19
- A uniform sublinear-size sample can miss the points at −n and n; sampling one of these has probability 1/(n+1), and without them the remaining data are separable, leading to large β.Adding penalization is not a remedy.Source: C Discussion of uniform sampling · p. 19
- 107.06 is the median β1 across 1,000 SGD runs, and a quarter of runs exceed the upper quartile of 492.35.The intercept β0 remains reasonably close to its optimal value of 0, while the large β1 values lead to a bad approximation ratio.Source: C Discussion of uniform sampling · p. 19, Figure 3 · p. 19
- For β0 = 0 and β1 ≫ (1 + ε), the objective exceeds 2nβ1 and thus greatly exceeds (1 + ε)m.The construction has m = 2n + 2, so the resulting large β1 yields a poor approximation ratio.Source: C Discussion of uniform sampling · p. 19