mlsanityData to 14 Oct 2026

Deterministic Coreset for Lp Subspace

arXiv 2601.00361 ↗First posted 1 Jan 2026cs.DS cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We introduce the first iterative algorithm for constructing a varepsilon-coreset that guarantees deterministic ℓp subspace embedding for any p ∈ [1,∞) and any varepsilon > 0. For a given full rank matrix X ∈ ℝn × d where n gg d, X' ∈ ℝm × d is an (varepsilon,ℓp)-subspace embedding of X, if for every q ∈ ℝd, (1-varepsilon)|Xq|pp ≤ |X'q|pp ≤ (1+varepsilon)|Xq|pp. Specifically, in this paper, X' is a weighted subset of rows of X which is commonly known in the literature as a coreset. In every iteration, the algorithm ensures that the loss on the maintained set is upper and lower bounded by the loss on the original dataset with appropriate scalings. So, unlike typical coreset guarantees, due to bounded loss, our coreset gives a deterministic guarantee for the ℓp subspace embedding. For an error parameter varepsilon, our algorithm takes O(poly(n,d,varepsilon-1)) time and returns a deterministic varepsilon-coreset, for ℓp subspace embedding whose size is Oleft(fracd^max1,p/2varepsilon2right). Here, we remove the log factors in the coreset size, which had been a long-standing open problem. Our coresets are optimal as they are tight with the lower bound. As an application, our coreset can also be used for approximately solving the ℓp regression problem in a deterministic manner.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 29 of its 53 references that are in the map. First posted on arXiv 1 Jan 2026.

Builds on

29 of 53 references.

References · 29

  1. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  2. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  3. 2016Coresets for Scalable Bayesian Logistic Regressioncited by 79
  4. 2018On Coresets for Logistic Regressioncited by 67
  5. 2018Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Boundscited by 43
  6. 2020Coresets for Near-Convex Functionscited by 38
  7. 2015Optimal approximate matrix product in terms of stable rankcited by 37
  8. 2019Data-Independent Neural Pruning via Coresetscited by 35
  9. 2020Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimalcited by 31
  10. 2021Coresets for Classification -- Simplified and Strengthenedcited by 28
  11. 2018Coreset-Based Neural Network Compressioncited by 27
  12. 2020Coresets for Robust Training of Neural Networks against Noisy Labelscited by 24
17 more
  1. 2021Oblivious sketching for logistic regressioncited by 18
  2. 2022New Coresets for Projective Clustering and Applicationscited by 16
  3. 2022Online Lewis Weight Samplingcited by 15
  4. 2018Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and morecited by 14
  5. 2022Fast Regression for Structured Inputscited by 11
  6. 2020On Coresets For Regularized Regressioncited by 10
  7. 2021Coresets for Decision Trees of Signalscited by 10
  8. 2019Approximating Spectral Clustering via Sampling: a Reviewcited by 9
  9. 2020Streaming Coresets for Symmetric Tensor Factorizationcited by 9
  10. 2021Improved Iteration Complexities for Overconstrained p-Norm Regressioncited by 8
  11. 2021Computing Lewis Weights to High Precisioncited by 7
  12. 2021Coresets for Clustering with Missing Valuescited by 5
  13. 2017Coresets for Kernel Regressioncited by 4
  14. 2018Leveraging Well-Conditioned Bases: Streaming & Distributed Summaries in Minkowski p-Normscited by 4
  15. 2022The Vector Balancing Constant for Zonotopescited by 2
  16. 2017Randomized Composable Coresets for Matching and Vertex Covercited by 1
  17. 2024Accurate Coresets for Latent Variable Models and Regularized Regressioncited by 1

Built on by

Not cited yet.