On Coreset for LASSO Regression Problem with Sensitivity Sampling
Authors: YuanBin Zou
Junyu Huang
Jianxin Wang
Qilong Feng
Venue: ICLR 2026 Poster (2026)
Keywords: LASSO regression
sampling algorithm
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: In this paper, we study coreset construction for LASSO regression, where a coreset is a small, weighted subset of the data that approximates the original problem with provable guarantees. For unregularized regression problems, sensitivity sampling is a successful and widely applied technique for constructing coresets. However, extending these methods to LASSO typically requires coreset size to scale with O(\mathcal{G}d), where d is the VC dimension and \mathcal{G} is the total sensitivity, following existing generalization bounds. A key challenge in improving upon this general bound lies in the difficulty of capturing the sparse and localized structure of the function space induced by the \ell_1 penalty in LASSO objective. To address this, we first provide an empirical process-based method of sensitivity sampling for LASSO, localizing the procedure by decomposing the functional space into separate components, which leads to tighter estimation error. By carefully leveraging the geometric properties of these localized spaces, we establish tight empirical process bounds on the required coreset size. These techniques enable us to achieve a coreset of size \tilde{O}(\epsilon^{-2}d\cdot(\log^3 d\cdot\min\{1,\log d/\lambda^2\}+\log(1/\delta))), which ensures a  (1\pm\epsilon)-approximation for any \epsilon,\delta\in(0,1) and \lambda > 0. Furthermore, we give a lower bound showing that any algorithm achieving a (1+\epsilon)-approximation must select at least $Omega(\frac{d\log{d}}{\epsilon^2}) rows in the regime where \lambda=O(d^{-1/2}). Empirical experiments show that our proposed algorithm is at least 4 times faster than the existing LASSO solver and more than 9 times faster on half of the datasets, while ensuring high solution quality and sparsity.

Published as a conference paper at ICLR 2026
ON CORESET FOR LASSO REGRESSION PROBLEM WITH SENSITIVITY SAMPLING
Yuanbin Zou
Junyu Huang
School of Computer Science and Engineering
School of Computer Science and Engineering
Central South University
Central South University
Changsha, China
Changsha, China
yuanbinzou@csu. edu. en
junyahuangesue foxma com
Jianxin Wang
Qilong Feng"
School of Computer Science and Engineering
School of Computer Science and Engineering Central South University
Central South University
Hunan Provincial Key Lab on Bioinformatics Xiangjiang Laboratory
Changsha, China csufenglmail. csu edu.cn
Changsha, China
jxwangemall, csu. edu. en
ABSTRACT
In this paper, study coreset construction for LASSO regression, where set is a small, weighted subset of the data that approximates the original prob- lem with provable guarantees. For unregularized regression problems, sensitivity sampling is a successful and widely applied technique for constructing coresets. However, extending these methods to LASSO typically requires coreset size scale with OGGd), where d is the VC dimension and G is the total sensitivity, fol- lowing existing generalization bounds. general bound lies in the difficulty of capturing the sparse and localized structure of the function space induced by the & penalty LASSO objective. To address this, first provide empirical process-based method of sensitivity sampling for LASSO, localizing the procedure by decomposing the functional space into separate components, which leads to tighter estimation error. By carefully lever- aging the geometric properties of these localized spaces, we establish tight empir- ical process bounds the required coreset size. These techniques enable us achieve coreset of size O(c-2d (log* d. min log d/ log(1 (1)))), which ensures a (1 + -)appooxxiitaonn for any c, E (0 and X >> 0. Furthermore, we give lower bound showing that any algorithm achieving (1 approxxmattin O(d-1/3) Empirical experiments show that our proposed algorithm is at least 4 times faster than the
key challenge in improving upon this
must select least Q( (llogd) rows in the regime where
existing LASSO solver and more than times faster on half of the datasets, while
ensuring high solution quality and sparsity.
INTRODUCTION
In machine learning and regression analysis, sparse models have been extensively studied over the past decades. These models typically address issues such as sparse regression (Natarajan) [195). variable selection (Zou & Hastic 2003), and multicollinearity (Altelbany 202T), aiming to improve model interpretability and computational efficiency by reducing the number of features. One of the most widely used methods for solving sparse models is the Least Absolute Shrinkage and Selec- tion Operator (LASSO), which is first introduced in (Tibshirani 1997). The core idea of LASSO regression is to apply fornrmm penalty, ensuring sparsity by shrinking some coefficients to zero. Therefore, in practice, LASSO widely applied in sparse models due to its effectiveness in enabling
"Corresponding Author.

---

Published as a conference paper at ICLR 2026
both variable selection and regularization with improved interpretability and prevented overfitting issues. The formal definition of the LASSO regression is given as follows.
LASSO Regression Problem. Given an n x d matrix A, an n-dimension vector b, and a regulariza- tion parameter À > O, the goal of LASSO problem is to find a d-dimension vector æ that minimizes || - -113 + X X||2 where || - bl2 is the residual sum of squares, and the ||>||| denotes the sum of the absolute values of the entries in x.
Although LASSO regression has been extensively studied over the past decade, the efficiency of LASSO algorithms for handling large-scale data still depends heavily on the number of rows n of the input matrix A. Specifically, the running time of existing algorithms, such as coordinate descent (Friedman et al. 2010), ISTA (Daubechies et al. 2004), and FISTA (Beck & Teboulle| 2009), is typically Onn''' poly(d)), where T' denotes the number of iterations. However, for datasets with a large number of samples n, LASSO may suffer from scalability issues. Consequently, developing now-subsampling methods for LASSO regression is crucial for improving computational efficiency.
Among the vast literature on large-scale regression tasks, coreset techniques have played a major role in data subsampling. These algorithms aim to construct a weighted subset of rows from both A and b, forming compact representation that effectively approximates the original regression problem with strong theoretical guarantees. Along this line of research, several coreset construction algorithms have been proposed for the E, linear regression (Clarkson) 2005 Drineas ct al. 2006 Dasgupta et al.,
2009 Cohen & Peng 2013 Woodruff & Yasuda 2024 2023] Munteanu & Omlor 2024). For reg-
ularized regression, Avron et al. (017)) constructed coreset of size O (dx +lgg) log sdx (A) for ridge regression, where (A) S denotes the statistical dimension of the matrix A. Moreöver, Kacham & Woodrufi (2020) introduced deterministic algorithms for coreset construction and also explored streaming model for this problem. Curtin et al.) (2019) provided a coreset for logistic regression of size (dd/n). Chhaya al. (2020) proposed coreset based on sensitivity sampling for the norm-based regularized regression problem || - blly + A||æ!|y with p 2 2. In a related recent work. Chhaya et al. (2020) studied modified LASSO problem by constructing coreset for the objective | - b + x|= However, the regularization term A |a]| = x(E, |=x:)?, due to its quadratic form, introduces cross terms among the coordinates x4. This may lead solutions with substantially more nonzero coefficients than those of standard LASSO, thereby preventing it from promoting sparsity in the same way as the & norm and weakening its sparsity-inducin effect. To the best of our knowledge, there are currently no relevant theoretical results on coreset construction for standard LASSO, which motivates our work on developing such a coreset.
Coreset for LASSO. Let A E Ruxd be a matrix and b E R". Define S E R as diagonal matrix, where the i-th row of both A and are independently sampled with probability ps for each i [m]. Let m denote the number of sampled rows. If row i is selected, set S = 1/ /mp, and set St, = otherwise. We say that defines an (e, -cooesst for LASSO problem if, with probability at least 1 8, for all E Rdd and >> O, the following holds
|((zz b) 12 + A||=1111 e (1 + E) (IlAr - bll2 + A||=|11),
where (0, 1). The coreset size is defined as the number of nonzero entries on the diagonal of S, i.., the number of sampled rows m.
Sensitivity sampling (Feldman & Langberg 201 Chhaya et al. 2020 Woodruff & Yasuda 2023)
has been extensively studied in regression without regularization, where rows are sampled in pro- portion to their importance in the regression objective. A common challenge in directly applying sensitivity sampling to LASSO lies in bounding the generalization error under the fi-regularized objective using standard empirical process tools. In the general framework of sensitivity sampling. Braverman et al.) (2016) showed that, given sensitivity scores {e: }r a (1 + a)aapoooximate coreset typically requires size of Ô (d) where G is the sum of the sensitivity scores and d denotes the VC dimension of the given problem. This bound arises from applying a union bound worst-case e-net methods and variance analysis. Consequently, directly applying traditional analysis to LASSO leads to large coreset sizes, which can limit scalability in high-dimensional settings. To address this issue, empirical process techniques and chaining methods have been developed to reduce the de- pendence on the Gd term in the coresct-size bound (Cohen et al., 2015 Woodruff & Yasuda [023] Munteanu & Omlor 2024 Bansal et al. 2024). However, integrating empirical process theory with
We write Ó(f(n)) denote O(f(m) poly log f(m)).
2

---

Published as a conference paper at ICLR 2026
LASSO regression requires addressing the sparse and localized structure of the parameter space induced by the & peenalyy In particular, the functional space = {a E Rd +p(r) Σ R). de- fined for fixed radius R 0, is determined by the residual term h(z)) ||
- b11 and the penalty
term p(a)) = A||z||| in the objective function. The interaction between the residual and penalty terms results in highly complex geometry for S2 complicating the standard empirical process anal- ysis. Additionally, the non-smooth boundary induced by the 11-ennllty leads to large error bounds when applying the Bernstein's 's inequality and e-net arguments, in (Chhayy al. 2020). Therefore, developing sensitivity sampling method for LASSO that constructs a coreset of size smaller than (Gd) remains a key challenge.
1.1 OUR CONTRIBUTION
In this paper, we aim to improve upon existing standard bounds for LASSO coresets, which often yield large coreset sizes due to the use of union-bound-basee e-net methods. The main difficulty arises from the intricate structure of the function space induced by both the residual error and the l regularization term. This complexity makes it difficult to directly apply standard empirical pro- cess techniques to sensitivity sampling. To address this issue, we propose localized empirical process method that reformulates the sensitivity scores and sampling error in a more tractable man- ner. Specifically, we define weighted Gaussian baase empirical process for the coreset loss and decompose the overall function space into two separable components: the residual space and the l penalty space. Each of these components has lower complexity than the original space Ω2 al- lowing for tighter bounds on the Gaussian diameter and metric entropy of each component. By carefully applying symmetrization techniques and leveraging the geometric properties of these lo- calized spaces, we derive upper bounds on the localized Gaussian diameter and metric entropy. With probability least 1 ô-ô,
ō, these bounds allow us to control the sampling error and construct a coreset of size Ō(e dd (log* 3 d. min log d/ {2 + log(1/))), achieving + apprroxiimttoonn for all E E 10 and À > 0.
To complement our upper bound analysis, we establish a near- wear-matching lower bound on the coreset size for LASSO regression via an information-theoree classical sparse recovery setting, we show that any estimator achieving a (1 [1+=)-apprxximmtion from the coreset must access minimum number of rows to achieve the sparse recovery task. In particular, in the regime where X = O v ). corresponding to the case in which the number of nonzero entries
method. By reducing the problem to a
may be large, we prove that the number of required rows at least C2 d log(d)). Our coreset size matches this lower bound up to polylogarithmie factors in the dimension d. Empirical experiments show that our proposed algorithm is at least 4 times faster than solving LASSO directly on the full dataset and more than 9 times faster on half of the datasets, while preserving high solution quality. Notably, on a dataset with million samples, our method completes in only 15 minutes.
22
1.2 OTHER RELATED WORK
LASSO regression, first introduced in (Tibshirani 1996). has been widely studied for learning sparse models, such as variable selection (Tibshirani 1997| Hans 2010) and compressed sensing (Angelosante et al. 2009). Many optimization algorithms have been developed for LASSO, includ- ing the fast iterative shrinkage-thresholdde
algorithm (Beck & Teboulle, 2009), coordinate descent (Friedman et al. 2010), the smooth & algorithm (Schmidt et al.) 2007). and the path-following al- gorithm (Tibshirani & Taylor 2011). LASSO regression uses rereulaarizitio
relax the sparsity penalty (typically denoted by [0|o)), which is hP-hard (Natarajan 1995). However, tuning the reg- ularization parameter often leads high computational costs. To address this, several methods have been proposed. FFieedman et al. (2010) provided the glmeet package based on coordinate descent for solving LASSO. Obozinski & Bach (2012) proposed a stochastic variant that improves conver- gence via random selection. [Wang et al. (2025) accelerated hyperparameter tuning using Markov resampling. To the best of our knowledge, there is currently no coresct construction method for the standard LASSO problem.
Sensitivity sampling is a well-studied technique for coreset construction in both theory and practice. It was first introduced by Agarwal et al. (2004), and has since been widely applied to various prob-
lems, including clustering (Feldman & Langberg] [011]] Braverman et al., [2022] Bansal et al. 2024).
linear regression (Drineas al.) 2006 Woodruff & Yasuda 2024 2023 Munteanu & Omlor 2024
3

---

Published as a conference paper at ICLR 2026
and matrix approximation regression, (Drineas et al. 2006) proposed coresct algorithm based on the well-known statistical leverage score sampling. Dasgupta al. (2009) extended this line of work to lp linear regression using the well-conditioned basis method. More recently, a tight framework for constructing coresets for unregularized regression has been developed in a series of works (Woodruff & Yasuda 2023 2024 Munteanu & Omlor 2024), leveraging chaining techniques from empirical process theory.
Dasgupta et al. 2009 Cohen et al. 2015). For ordinary least-squares
Sensitivity sampling techniques have been extensively studied for regularized regression prob- lems. For logistic regression, sensitivity-based sampling has been successfully applied in a se- ries of works Munteanu al. (2018); Curtin et al. (2019); p Mai et al. (202I); Munteanu & Om- lor (2024). In particular, Munteanu & Omlor (2024) recently provided a strong coresct of size O(ud/E") based on Lewis-weight sampling Parulekar et al. (202)), where captures the com- plexity of the input data distribution. For ridge regression, [Avron et al. (2177) pioneered the use of coreset techniques by showing that a weak coreset of size O(sdx (A))e² suffices to achieve a (1 + e-aappooximation KKacaam & Woodruff] (2020) developed optimal deterministic coreset constructions for multi-response ridge regression. Their method selects ((sd)(A)/c rows and achieves a (1 + <) --aappoxximaton, with matching lower bounds that establish the tightness of the dependence on sdx (A). In the regime where n >> d. the statistical dimension sdx satisfies (A) I rA))(A) S d, and larger values of the regularization parameter À can lead to smaller coreset sizes for ridge regression.
In the broader context of norm- conm-regularized regression, Chhaya et al. structions for Ep regularized regression problems of the form Ar
(020) considered coreset con- bI + >||=||p. where p > 2.
They provided coreset of Ö ((22((1+7/ (p)
d=+1
based on sensitivity sampling techniques. Moreover,
they first showed that when r * 8, no strong coreset can be smaller than the optimal coreset size for the unregularized term || |Ax - b1pp-- This result applies in particular to LASSO, where p --= = 2 and
q = s = 1. To address the LASSO objective. Chhaya et al. (2020) proposed a modified formula- tion in which the regularization term
||| is replaced by || enabling the use of ridge regression coreset techniques Avron al. 2017 to construct a coreset of size (A) However, this modification introduces cross terms among the components of æ, which may weaken the sparsity- inducing effect of the standard & regularization. In this paper, we propose a coreset for the standard LASSO objective with size Ö(e-2d (log² d min I, log d/X²} + log((/)))), which preserves the Ö(d/ 22) bound when approaches or oo. In addition, sketching- based methods using randomized projections have also been applied to LASSO in recent work Mai et al. (2023). Designing sensitivity sampling methods for constructing coresets for LASSO remains an interesting open problem.
2 PRELIMINARIES
Given a positive integer n, let [n] = (1.2....., For a d-dimensional vector r E RRd, the fy-norm of x is |,||| = (Ei= p2/p)//p. For n x d matrix A, the induced p-norm is ||All(p) which A is defined as ||All(m)) Zu ||||| The fg-norm (or spectral norm) ||A|](2) corresponds
to the maximum singular value of A. For a matrix A E Raad the Ep norm of A is | = (E== Σ |Ag 1/, and the Frobenius norm of A is ||A||| (E Σ/= 43,) Let A be the i-th row of A, and let Aij be the entry in the i-th row and j-th column of A. Let AT be the transpose matrix of The Singular Value Decomposition (SVD) of a matrix A where U x and V g are orthogonal matrices, and Σ E Raxd is a diagonal matrix containing the singular values Op. where r S min(n, d}. For a vector x E R²" and a weight vector 20 the weighted f,-norm is || = (En wi/zx:1))// 1/p and the weighted Eox norm is || max | An e-net for set K in metric space (X, d) is a subset T C K such that for every point K, there exists y T with d(x. y) S Given a parameter À > 0, we define the statistical dimension of a matrix A as sd, (A) = Ex 1+8/07 where r denotes the rank of A.
UEVT,
For any vector x E Rdd let supp(x)) = {i E [d] x4 + 0} denote its support, and write |supp(x)] for the number of nonzero coordinates.
4

---

Published as a conference paper at ICLR 2026
2 Leverage Scores. The Eg-leverage score of the i-th row of matrix A is
| 2012
(42 sup ZER ||
Alternatively, the leverage scores be expressed TA,(AA) |e, U1É. where U Ruxd is an orthonormal basis for the column space of A (Cohen et al.
2015). Therefore, the sum of the & leverage scores satisfies Σ 11 (A, = rank(A) A) (which equals d when A has full column rank).
3 SENSITIVITY SAMPLING FOR LASSO REGRESSION
In this section, we propose sensitivity sampling algorithm for LASSO regression, called LASSO- Sens. The main goal is to derive a better upper bound on the coreset size using empirical process methods applied to the LASSO objective. The primary technical challenge lies in handling the interaction between the residual loss and the & penalty, as standard empirical process techniques typically rely on analyzing the ratio between them, which is difficult handle and may lead to bet- ter coreset size bounds. To address this issue, we provide a localization method for coresets within the empirical process framework, which decouples the problem into two components over localized regions. This allows us to analyze the empirical process in localized spaces involving only a sin- gle term. Over these localized sets we develop weighted Gaussian empirical process framework and derive upper bounds on the Gaussian diameter, covering numbers, and metric entropy. These ingredients yield coreset of size Ō (log* d min(1 [ (gg(1)))), which nearly matches (L/vdd) The detailed algorithm for constructing the LASSO
the lower bound in the regime
coreset is given in Alllorthhm I
In sensitivity sampling, the sensitivity score of the i-th row for the LASSO objective is defined
|| [Ar b):112 + x ||=||
P: = sup =cRd
|
612 + A||z||1
where À > O. The definition of 0 captures the worst-case contribution to the LASSO objective, with the regularization term A||z[|i ensuring that each row contributes equally to sampling. Bounding the score & by the & leverage score т; with an additive 1/n in this paper is straightforward; see Appendix A. for the formal details.
The LASSO-Sens algorithm mainly consists of sampling procedure for coreset construction. We initialize an empty set of indices Q and zero vector w. Then, we calculate the sampling probability = min(1, (e):= + }.), where a represents the over-sampling parameter. Next, the algorithm randomly selects row index
'n] with probability ps, assigns the weight of the i-th row to By repeating this sampling process m times, Algorithm returns the final set row indices Q and the corresponding weight vector w.
1/ /mpp and updates the set of indices to Q Q U {i}. (i}.
Before providing the theoretical guarantees for the coreset, we first present equivalent transfor- mation of the LASSO objective and its sensitivity scores. Let A' = [A b] E [d*(d+1) be the matrix obtained by concatenating A and b, and let r' [a: 1] be the vector obtained by concatenating with 1. Using A' and z', the original objective function min, || bll2 + A||x=|1 is rewritten as
||4'''113 A||20|| I|1- min
Thus, we reformulate the sensitivity score Q as
+2 0. sup
A''''1 + +|112111
3.1 SAMPLING ERROR ANALYSIS
In this subsection, we develop a localized empirical process framework to analyze the sampling emor introduced by sensitivity sampling in the LASSO objective. To achieve this, we decompose
5

---

Published as a conference paper at ICLR 2026
Algorithm LASSO-Sens
Input: a matrix A E IR"xd a vector b E R", a regularized parameter X, the over-sampling parameter a, the coreset size m, and
of approximate sensitivity scores {0:)=1
Output: set of indices Q, and a weight vector w E Ro00
1: Initialize empty set Q, and let w be n-dimensional zero vector.
2: for + 1,2,.... do
3: Compute the sampling probability for the i-th row p; (1, ))
4: end for
5: for / .,,, T..,,To do
6: Sample a row index i E [n]] with probability pt, and set the weight wy l/ympi.
7: Q-Qu [i)
8: end for
9: return Q and w.
function space into residual component and a penalty component, and localize our study to their intersection. This separation enables us to independently bound the Gaussian complexity and metric entropy of cach component using a combination of weighted chaining techniques. By constructing multi-scale e-nets and applying concentration inequalities for Gaussian processes, we establish an upper bound on the coreset size that controls the sampling error.
We now analyze the sampling error introduced by sensitivity sampling. Let {pr denote the sampling probabilities associated with each row of the augmented matrix A'. Let S E {0, 1) 1)mx be sampling matrix with exactly one nonzero entry in each row, where represents the number of rows sampled from A'. Let w be the weight vector corresponding to the selected rows. Let T {a: a Rd+1 Id+1 0}, and let Ω fxr ar T, I Axxl + A||x=||1 } be the unit ball of the LASSO objective. Then, we define the sampling error over the domain Ω2 as
E = sup ||''''''ll Il + A||='|l - 21 + A||a
x² Ef
sup
5 x I| ||. ||
e'eft
Our goal is to bound & by 6, leading to the inequality
||SA''' Il + A||='|| (1 + (114''''13 A||=>(1b) [h)
for every x E Ω. To bound & using the chaining method (Cohen Peng 2015 Koltchinskii 2001 Hu al. 2022), we analyze the moments of with the symmetrization technique, which allows us to construct Gaussian reduction as follows. (A detailed proof of Lemma is given in Appendix Lemma II]
Lemma 1. Let A' E Rnx(d+1), let S be a random sampling matrix, and let Q denote the set of sampled rows from A'. For X > 0 and an integer 2 the following inequality holds
Es 1l6 < (23) (B sup
Σ g:00 (A ZER
where g (O, I.) represents Gaussian vector with independent entries.
We bound the sampling error & by analyzing the associated Gaussian process, as described in Lemma T To handle higher-order moments of E, we apply a moment bound from Woodruff & Yasuda (2023). which uses Dudley's 's tail inequality for Gaussian processes. Consequently, we ob- tain the following inequality for the sampling error.
(2) where C is an absolute constant, Mg denotes the metric entropy of the Gaussian process, and D is the Gaussian diameter. (The detailed definitions of Mg and are provided in the following.)
Es[lE') < (CM&)'(M// + O(ViD))
By appropriately choosing the parameter I and bounding both the metric entropy Mg and the Gaus- sian diameter D of the Gaussian process, we can ensure that Es [[ < é. which leads to a suffi- ciently small coreset size m. We now decompose the unit ball L = {x Ir E A| + A||a||i S

---

Published as a conference paper at ICLR 2026
1}. which arises from the residual term ||4'xz/22 and the l penalty term. (The proof of Lemma 2 is provided in Appendix Lemma 12)
Lemma 2. Let E Rxx(d+1) be a matrix and À > O. Define the sets = for x T, | +
A||ar|11 S 1 and L = {a T, || < and ||rr11 S }).. Then, it holds that 92 S L.
Define (2(A') {o x T, || s }} as the unit ball in the residual space, and Bi (i( {x
x T, | S } as the unit ball in the E-penaly space. By Lemma 2 we have
L CCL B2(A") Bi
This allows us to proceed with bounding both the Gaussian diameter DD and the metric entropy Mg for the convex sets (2') and B1 (1). respectively. Let M SA', where S {0, [0,1)mmX 1]mmx is sampling matrix.
We start by bounding the Gaussian diameter D by relaxing the pseudo-metric dx using an upper bound involving the maximum &g leverage score and A. Define the convex set Las {y Mr E LA }. Let T suppren,ie(m)) |A'_x'1? be the maximum row contribution (under the normal- ization x' E Qt). Next, we prove that the diameter D with respect to dy is bounded by the following inequality. (Detailed proof of Lemma Iis given in Appendix Appendix[Lemma 13)
Lemma 3. Let M E Rmxx(d11), and lel w be the weight vector. Define the pseulo-metric
12)
1/2
dx(y,v))= (Boo.rOLLS
m
m
Σ
gows 1vi
Σ
for any y. E Las. Then, the diameter D(CM) with respect dx is bounded by
D(LM) s O(T (og//og////
To obtain a precise bound for the Gaussian process over Las apply the chaining method to construct a sequence of t-nets at varying scales t > 0, which capture the convex structure of the function class associated with & on LM- Utilizing this chaining method, we can derive bound on Es|El' via the covering numbers of the sequence of t-nets. Thus, we aim to bound the minimal number of weighted unit lp (or foo) balls required cover the convex set Las for E 30). We define the weighted unit ball of the residual space (2, as (M) {a r E T, Marl S 1}, and define f. = (y Ma x E (M) n (1/A)) Let G ==11 1+ & = 1 + sup |||SA' 122,2 - ||A'=/113)
To bound the metric entropy of the convex set (w.) we first define the weighted Ep-unit ball as (M) = far E T, M < 1}. Let Tp denote a t-net of Bu,)(M) with respect to the weighted 6p norm, i.c., a finite subset of (m.,((M) such that every point in (MM) is within distance & (measured in || llw.p) from some point in Tp- We define the minimal cardinality of such a set Ty, and the metric entropy of (,,)(M) with respect to the weighted en-norm is then defined as log N (Bw, (M,), || Ilw.,p.) t). (Detailed definitions are provided in Appendix Definition 14 and Definition 15
Il=.,p: as
Lemma ( (Munteanu & Omlor 2024), slightly modified). Let S p OC, and let M E mm be an orthonormal matrix with weight vector w E R Then, the following inequalities hold log N (B,,, || (1w.p: < O(1) "n"/ppr and log N ((m,,2(M)
11 1) S O(1) log mir
For bounding the metric entropy of the convex set B, (2), we aim to bound the number of B balls of radius needed to cover the B, -all. Specifically, the covering process can be decomposed into two steps: first, cover the Balball using -blls, and second, cover the Bbal using Ba-balls. The Bj ball has a unique geometric structure, with large portion of its volume concentrated near its center, as pointed out in [Vershynin 2018). This concentration implies that fewer small-radius balls are required to cover B, compared to naive volume-based estimates. While a straightforward volumetric argument yields a worst-case covering number of O((1 + 2)d), this bound can be quite loose. To obtain tighter estimate, we leverage the Sudakov minoration inequality (Vershynin 2018), which provides a way to control the covering number N Boo: t). (A Detailed proof of Lemma is given in Appendix[Lemma 2
Lemma
7

---

Published as a conference paper at ICLR 2026
Lemma 5. Let p be parameter, and let Bp fo E R ||>||pp I 1) be the unit ball for the Ep
norm. Then, log. (B1, Bx.
0 logd
To bound the metric entropy of these t-nets, need calculate the following integral
Me - / Vlog (CW, dx, t) dt.
For radii t >> D)). the covering number satisfies log (f dx, t) = O, which implies that any single vector y ar serves t-net. Therefore, only need to focus the case where the radius lies within the interval [0, D(C,,M)], We derive the following inequality, whose proof provided in Appendix Lemma 27
Lemma 6.
Let M E Rmx((+1) be a matrix and let be a positive parameter. Then, the metric entropy ME of fo satisfies
log (Lw, dx,t) dt s OCTr/Io (1 (1+ log min 11, Vlog d }).
where is the maximum weighted ég-leverage score of M.
We now present the main result, which provides bound the coreset size required to ensure that El e. (The proof of Theorem is provided in Appendix Theorem 30)
Table I: Comparison results of loss, runtime, and sparsity CTs dataset (n 53,500, d 386) for varying coreset sizes at = 0.5.
Metries
Algorithms
Coresct Sizes
1d
2d
5d
10d
15d
20d
LASSO
0.11
Loss
LASSO-Sena
29.27-+.005
25.43++0.17
25.32-+0.02 25.34-10.03
25.32++0.11
25.32-+0.02
LASSO- Uniform
LASSO-Uniform
61,58=22286
30.39::.19 25.94 42 25.58=10.17
25.55+:013
25.4610.13
LASSO
505.65
Time (s)
LASSO-Sens
9.07
13.75
20.84
34.58
66.40
113.34
MASSO-Unifont
8.70
13.41
21.12
36.96
72.74
122.72
LASSO
325
Sparsity
LASSO-Sens
360
336
329
322
LASSO-Uniform 379
360
343
337
329
325
Theorem Let A' e Rnx(d+1) be an input matrix, let S be a random sam- pling matrix, and let e,8 E (0,1) and X > O be a parameters. If (log (dlog(1/)))(nd)}) min 11 logd } + log ) and all i E [n] it holds that x
P 2 (ii,) 1
where (A') denotes the Eg leverage score of the i-th row of A'. Then, with failure probability at most holds that for all x E Id+1 with Id+1 =
A'xx + A1 S (1 (11 + A||x||1),
and the coreset size at most m Ō (d(ogdd) min
A + log 2
To establish lower bound on the coresct size m. we utilize a reduction from the support recovery problem in sparse recovery. We consider the task of recovering the support of sparse vector z", and apply information-theoreti techniques to LASSO regression. Our analysis shows that, under certain conditions, any algorithm achieving (1 apppoooximtaioon from the coreset requires least 2 & log d) rows. Since Mai et al. (2023) pointed out the lack of scale-invariance in LASSO objective, we normalize the ipputs by assuming ||Al]] I and |b]] S Detailed proofs are provided in Appendix B.4
8

---

Published as a conference paper at ICLR 2026
Synthelic
LeG00
Lebal
Ser
1005
20d
14
15d
205
14
155
20d
36
15d
20d
Cor Coresalt30 Size
Conuast Siew
Cornust Sice
Content Sia0
(a) A 0.5
CB
Synthotic
mediamil
mniittm
1.5
140
LAiiu--ees send
Lib-a send.
LAGS0-Untivm
Lown
3:
10c
54
20d
24
5d
20d
15d
(b) A
Synthelic
mediamll
mnstfim
LeAGO LAAkGH
Love
LOSE
260
1.5
24
50
105
15d
20d
1d
28
5d
10d
15d
20d
3d
24
5d
10d
15d
20d
35
24
55
1.00
15d
20d
Cornset
Size
Coreset Size
Coneset Size
Coftect
Size
(c) A =
Synthetic
medimii1
minletfm
LASSO
134
LASSO
LASSO
LASGO Ser Lobeo
120
15d
Commust Size
Comseet Size
Comsset Sioe
Conssar Size
(d) À 10
Figure 1: LASSO regression loss comparison across varying coreset sizes for À = (0.5,103
Lemma 8. Let A E Raxd e R", and X E (0,1). 1). Assume that ||Al|2 S 1 and [|b|| S 1. Let S be a diagonal sampling matrix with m nonzero entries. Suppose there exists an estimator whose output I = arg min SAx Sbll + A||=||1 satisfies
A b12 A|[l|| I c)
min (IlAx bl2 A||=|11)- wERd
Then, the coreset size m must satisfy
2 log 12.22
ft 52 }/) it 0 (
22 4 logd),
EXPERIMENTS
In this section, we compare three algorithms for solving the LASSO regression problem: direct optimization using the full dataset, and solving LASSO on subsamples selected via sensitivity sam- pling and uniform sampling, respectively. All experiments conducted on a machine with 72 Intel Xeon Gold 6230 CPUs and 340 GB of memory, and all implementations are executed in MATLAB 2017A.

---

Published as a conference paper at ICLR 2026
Datasets. We evaluate the three algorithms on 4 datasets: Synthetic (n 100000,,000 d = 200), me- diamill (n = 30, 993, d = 120), CTs (n = 53, 500, d = 386), and mnist8m (n = 8. 100, 000, d = 784). The synthetic dataset is generated by constructing a matrix A R 10000000000 where small number of rows have high leverage scores. This construction follows the method de- scribed in (Chhaya al. 2020). 'he resulting matrix is designed to exhibit a non-uniform lever- age score distribution while maintaining a well-conditioned structure. For all datasets, the re- sponse vector is defined as b = Aa + 10-5 [bll where x E
{0, 1]d is a randomly gen- erated sparse vector, and is noise vector. All datasets used in our experiments are pub- licly available at the following URLs: /tt.ttpp//aaccie..eee ics uci edd and https: / www.wwie..e.......ww..wwwww...ww www..uu..uu................ tw wtw.:/wwwwww..iiittteeeaa http::/wwwooo..iimoooooo///tttaa
|ell
Algorithms. In our experimental evaluation, we compare the following three algorithms:
* LASSO. The standard LASSO regression is solved using the FISTA method as described in (Beck& & Teboulle 2009).
LASSO-Sens. Our proposed approach (see Algorithm 1, which first constructs coreset via sensitivity-based sampling and then solves the LASSO problem on the coreset using FISTA.
. MAASSO-Unifomm A baseline that first uniformly samples rows from the input data and then applies FISTA to solve the LASSO problem on the sampled data.
Methodology. We evaluate algorithm performance using the loss function f(x) = |LAz bl2 + X||=||| where lower value of the loss indicates better solution. To evaluate the sparsity of the solution, we follow the method introduced in (Chhaya et al. 2020) by setting any entry of with an absolute value less than 10 6 to O, and we count the remaining nonzero entries. Our experiments test three methods: LASSO, LASSO-Sens, and LASSO-Uniforn on four datasets. To ensure a fair comparison, we test each algorithm 10 times and report the average loss, runtime, and sparsity. To compare the performance of different sampling strategies, we run LASSO-Sens and MASSOO-nnifors across a range of coreset sizes and regularization parameters, with the values A {0.5, 1,5, 5, 10}. Specifically, the coreset size is selected from 21,2,5, 10, 15, 20} x d for each dataset.
Results for the LASSO Regression. As shown in Figure 1 the LASSO-Seas Senss algorithm achieves loss values that closely match those of the exact LASSO solver as the coreset size increases, partic- ularly for À 0.5 and A 10. The comparison of performance metries across four datasets under varying values of and coreset sizes is reported in Table I| and Appendix Tables 2 including average loss, standard deviation, runtime, and solution sparsity. On the Synthetic, Mediamill, and CT' datasets, LASSO-Sens is at least 4 times faster than LASSO, and up to 18 times faster on CTs. On the mnist8m dataset, LASSO-Sens obtains a feasible solution within 15 minutes, whereas the standard LASSO solver fails to return solution even after 48 hours. Furthermore, the LASSO- Sens algorithm generally outperforms MASSOO-Unionna in terms of both accuracy and sparsity on the mnist8m dataset. At a coreset size of 10d, the sparsity of the solutions produced by LASSO- Sens closely matches that of the exact LASSO solver across all datasets. These experimental results show the sensitivity sampling in accelerating the LASSO regression process while preserving high- quality solutions and solution sparsity. All of these findings, together with our Theorem 7 confirm the effectiveness of sensitivity sampling for LASSO.
5 CONCLUSION
In this paper, we propose the first coreset construction method for LASSO regression via a sensi- tivity sampling algorithm. Directly applying existing coreset techniques for regularized regression to LASSO yields coreset size bound of O(Gd/e2). To achieve smaller coreset, propose an empirical process analysis that addresses the complex function-space arising from the interaction between the residual error and the & penalty in LASSO objective, thereby achieving coreset of size Ö(c-2d 2d (log" d min 1o log 2/ + log(1/8)) An interesting future direction is to study how our method can be extended to the elastic net and other regression problems involving more complex regularization.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
This work was supported by National Natural Science Foundation China (62432016, 62502545), and Central South University Research Programme of Advanced Interdisciplinary Studies (2023QYIC023). This work was also carried out in part using computing resources at the High Performance Computing Center of Central South University.
ETHICS STATEMENT
This work does not involve any human subjects, sensitive data, or other ethical concerns outlined in the ICLR Code of Ethics.
REPRODUCIBILITY STATEMENT
This paper is committed to ensuring the reproducibility of our work. To ensure the completeness of the comparison, have provided detailed descriptions of our proposed method and its components in Section 4 of the main paper. To enable accurate replication, we clearly specify all hyperparame- ters, training procedures, and evaluation protocols in the same section. Additional implementation results, including figures and tables, are provided in the Appendix.
REFERENCES
Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. Approximating extent measures of points. Journal of the ACM, 51(4)600--33,, 2004.
Shady Altelbany. Evaluation of ridge, elastic net and lasso regression methods in precedence of mul- ticollinearity problem: simulation study. Journal of Applied Economics and Business Studies, (1):131-142, 2021.
Daniele Angelosante, Georgios B Giannakis, and Emanuele Grossi. Compressed sensing of time- varying signals. In Proceedings of the 16th International Conference on Digital Signal Process- ing. pp. 1-8, 2009.
Haim Avron, Kenneth I. Clarkson, and David P Woodruff. Sharper bounds for regularized data fitting. Proceedings of the 17th Annual Conference on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, pp. 27:1-27:22, 2017.
Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: Worst case and stability optimal coreset bounds. In Proceeding of the 65th IEEE Annual Symposium on Foundations of Computer Science, pp. 1707-1723, 2024.
Amir Beck and Mare Teboulle. fast iterative problems. SIAM Journal on Imaging Sciences,
algorithm for linear inverse 2009.
Lindenstrauss J Bourgain J and Milman V. Approximation of zonoids by zonotopes. Acta Mathe- matica, 162:73-141, 1989.
Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. New frame- works for offline and streaming coreset constructions. arXiv preprint arXiv:16/2.00889, 2016.
Vladimir Braverman, Vincent Cohen-Addad, H-C Shaofeng Jiang, Robert Krauthgamer, Chris Schwicgelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, pp- 462 473, 2022.
Bernd Carl. Inequalities of bemsstein-jackkon-type and the degree of compactness of operators in banach spaces. Annales l'institut Fourier, 35(3):79-118, 1985.
Rachit Chhaya, Anirban Dasgupta, and Supratim Shit. On coresets for regularized regression. In Proceedings of the 37th International Conference Machine Learning, pp. 1866-1876. 2020.

---

Published as a conference paper at ICLR 2026
Kenneth L Clarkson. Subgradient and sampling algorithms for & regression. In Proceedings of the 16th Anmual ACM-SIAM Symposium on Discrete Algorithms, pp. 257 266, 2005.
Michael B Cohen and Richard Peng. E row sampling by lewis weights. Proceedings of the 47th Annual ACM Symposium Theory of Computing, pp. 183-192, 2015.
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng. and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 6th Innovations in Theoretical Computer Science Conference, pp. 181-190, 2015.
Ryan R Curtin, Sungjin Im, Ben Moseley, Kirk Pruhs, and Alireza Samadian. On coresets for regularized loss minimization. arXiv preprint arXiv:1905.
2019.
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney. Sampling algorithms and coresets for lp regression. SIAM Journal Computing, 38(5):2000-200 2009.
Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics, 57(1 (7(11))1413-11 1457, 2004.
Petros Drincas, Michael W Mahoney, and Shan Muthukrishnan. Sampling algorithms for l2 regres- sion and applications. In Proceedings of the 70th Annual ACM-SIAM Symposium on Discrete algorithm, pp. 1127-1136, 2006.
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd annual ACM symposium on Theory of computing, pp. 569-578, 2011.
Jerome Friedman, Trevor Hastie, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of Statistical Software, 33(1):1-22, 2010.
Chris Hans. Model uncertainty and variable selection in bayesian lasso regression. Statistics and Computing, 20(2):221-229, 2010.
Lunjia Hu, Charlotte Peale, and Omer Reingold. Metric entropy duality and the sample complexity of outcome indistinguishabiiit. In Proceedings of the 32nd International Conference Algo- rithmic Learning Theory. pp. 515-552, 2022.
Praneeth Kacham and David Woodruff. Optimal deterministic coresets for ridge regression. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, pp- 4141-4150, 2020.
Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transactions Information Theory, 1755):1902-1914, 2001.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991.
Michael W Mahoney et al. Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning, 3(2): (223:123-224 2242222222222 2011.
Tung Mai, Cameron Musco, and Anup Rao. Coresets for ceassfiiation-smmpiin and strengthened. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems, pp. 11643- 11654, 2021.
Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, and David Woodruff. Optimal sketching bounds for sparse linear regression. Proceedings of the 26th International Conference Artificial Intelligence and Statistics, pp. 18888-13316. 2023.
Alexander Munteanu and Simon Omlor. Optimal bounds for lp sensitivity sampling via & augmen- tation. In Proceedings of the 45th International Conference on Machine Learning, pp. 36769- 36796, 2024.
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David Woodruff. On coresets for logistic regression. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 3562-6571, 2018.
12

---

Published as a conference paper at ICLR 2026
Balas Kausik Natarajan. Sparse approximate solutions linear systems. SIAM Journal on Comput- ing, 24(2):227-3344 1995.
Guillaume Obozinski and Francis Bach. Convex relaxation for combinatorial penalties, arXiv preprint 1rXiv:1205.12444 2012.
Aditya Parulekar, Advait Parulekar, and Eric Price. L1 regression with lewis weights subsampling. In Proceedings of the 24th International Workshop on Approximation Algorithms for Combinato- rial Optimization Problems and the 25th International Workshop on Randomization and Compu- Iation, pp. 49:1-49:21, 2021.
Mark Schmidt, Glenn Fung, and Rómer Rosales. Fast optimization methods for & regularization: A comparative study and two new approaches. Proceedings of the 11th European Conference Machine Learning, pp. 286-297, 2007.
Robert Tibshirani. Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
Robert Tibshirani. The lasso method for variable selection in the cox model. Statistics in Medicine, 16(4):385-395, 1997.
Ryan Tibshirani and Jonathan Taylor. The solution path of the generalized lasso. The Annals of Statistics, 39(3):1335-1377 2011.
Roman Vershynin. High-dimenssooal probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Martin Wainwright. Information-theerrti limits on sparsity recovery in the high-dimensional and noisy setting. IEEE transactions on Information theory, 55(12):5728-5741, 2009.
Wei Wang, Martin Wainwright, and Kannan Ramchandran. Information-theorete limits on sparse signal recovery: Dense versus sparse measurement matrices. IEEE Transactions Information Theory, 56(6):2967-2979, 2010.
Yuhang Wang, Bin Zou, Jie Xu, Chen Xu, and Yuan Yan Tang. Alr-ht: A fast and efficient lasso regression without hyperparameter tuning. Neural Networks, 181:106885, 2025.
David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-157, 2014.
David P. Woodruff and Taisuke Yasuda. Sharper bounds for Ep sensitivity sampling. In Proceedings of the 40th International Conference on Machine Learning, pp. 37238-37222 17738-37772, 2023.
David P. Woodruff and Taisuke Yasuda. Coresets for multiple E, regression. In Proceedings of the 41st International Conference on Machine Learning, pp. 53202-53233, 2024.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B: Statistical Methodology, 67(2):301-322 -320, 2005.
13

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.1 1 MISSING PROOF OF SENSITIVITY SCORES
In this subsection, we provide an upper bound on the sensitivity score p, using the &g leverage score and fixed term 1/n. While this result is not fundamentally new (see, e.g., (Mahoney et al. 2011 Woodruff 2014 Chhaya al. 2020)), we slightly extend the well-conditioned basis method the LASSO objective.
Definition 9. (l2 Well-Conditioned Basis.) Given matrix A Raxd, we define (Vd, 1, well-conditioned basis for A such that ||U||2 S Vd, and for all E Rd ||l|2 S ||Ux|12. where U E Raxx is the orthogonal matrix obtained from the SVD of A.
Lemma 10. Let A' E Rax(d+1), and let X >> 0 be regularization parameter: Then, the estimated 2TT;2((') + z Qi. where Te,(AA) denotes the lz leverage score of the i-th row of A'. All sensitivity scores O can be computed in time ((nz((A)) (') log n + d log (n/d) log d), where nnz(A') denotes the number of nonzero entries in A'. Moreover, the total sensitivity is bounded as G S 2d 3.
sensitivity score @s satisfies
Proof. Let A' = UV, where U E Rxx(d+1) is
basis for A'. Denote the i-th row of A' A u, V, where u, is the i-th row of U. For any x' E Ig++1 define Vx', so that A'x' Uz. Let T (x' E &Rd+1 :2'411 = 1}. Then, we obtain
A + ||اا|||
luf =/ + A VV -211
12 AllV 1 sup 1 21
1
T12( + 1
= sup ET
A'''' + A|l''1 sup
1
d + 2, where T (A') = ug 3 denotes the &a leverage score of the i-th row. Furthermore, by extending Lemma of Cohen et al. 2015), the approximate leverage score ( < (A')( can be computed in time O (nnz (A') log n + d log d ll)))dd)). Substituting this into the bound yields S 2A',((A)) + and 9 < 2d 3.
Thus, the total sensitivity satisfies = Ei= S Σ (Tt2
B OMITTED PROOFS OF SAMPLING ERROR ANALYSIS
In this section, we reduce the empirical process associated with the sampling error to a Gaus- sian process using the symmetrization technique. The sampling error & is defined on the set Q = fa E T || + >||=/|1 = 1}. where T {i Rd+1
Id+1 = 1]. .. To analyze the func- tional complexity, we consider the larger set T = {a E Rd+1 Øa+1 + 0). since any x E T can be obtained by scaling an element of T'. Specifically, for each E T, there exists a scalar e and vector x' E T such that Z c x', which implies T S T'. Consequently, we define the extended domain = x E T' ||A''| + A||z||| = =} and focus our subsequent analysis on this set us- ing tools from Gaussian process theory, particularly those developed for unregularized regression in Woodruff & Yasuda (2023).
Lemma 11. Let A' [=ax(d+1), let S be random sampling matrix, and let Q denote the set of sampled rows from A'. For X > 0 and an integer 2 2. the following inequality holds
Es 18 < (2T) (0.1.) sup
Σ g:m0 (A :EQ
where g (O, represents Gaussian vector with independent entries.
Proof. We consider the simple convex function la + bit for a, b R4, where > 1 is positive number. Given a random sampling matrix S, the linearity expectation implies
E [|| + A||=][]] ||4 x||x||1
for any vector x E gd+ Next, without loss of generality, we assume that |A'x [ + A||z[|| 1; otherwise, rescale æ by constant satisfy this condition.
14

---

Published as a conference paper at ICLR 2026
We now analyze the following quantity
E Es
sup
||SA'> + A||z]|1 1
| -
Let S' be an independently copy of S. Applying Jensen inequality, we have
Es
sup
|| + A||==|| - (1112=11 + \||>||))|
||| - ||4'=|13 + o
-ss
sup
[|A'a] 3
-Es
sup
||| 1 m1 ||A'=11 + Es (11A'x11 1|5" 2'x12,2))))
[| +|lll+=/ll
< "Es,s' ||A=a|3++A|el]]=t.ee7
sup
|||SAA'<|| - Es
Es,
sup |||SAA'=| A' 1
Using a standard symmetrization argument (Vershynin 2018), we obtain
Es.s'
sup
|SA''11 A'x'''=l (
All 11
< 22,,,
Σ r:ws (A/)) iEQ
sup || 13++
$ (T/22
12 E.
Σ iEQ
grws (A4,)
sup | |A
where {=1}* are independent Rademacher variables in the first inequality, and the second in- equality follows from the Rademacher Gaussian comparison theorem (Ledoux Talagrand 1991) with ~ NO, In) standard Gaussian vector in R..
Lemma 12. Let A' [d+x()+1) be matrix and À > 0. Define the sets Ω fx a T, |AA' A||=||a 5 1} and C = {o x E T, ||Axx|| < 1 and ||=||1 S }. Then, it holds that f2 C C.
Proof. Take any Ω. By the definition of the set Ω have
||A'x|1 + A||=|| S
Since ||A'' is non non-negative, it follows that
A|20|1 I ||/' + A||=||1 $ 1,
hence
|x||| S
Next, since A||x||1 2 0, we have
||'x| < |A'x >||==|| < 1.
Thus, we have
A' < 1.
Since x E Q implies x E T by definition, we conclude that 0 E L. Since æ was arbitrary, we have
Ω C L.
15

---

Published as a conference paper at ICLR 2026
B.1 BOUNDING THE GAUSSIAN DIAMETER
We start by bounding the Gaussian diameter 'D with respect to the pseudo-metric dx.
Lemma 13. Let M E Rmx((+1), and let be a weight vector. Define the pseudo-metris
1/2
(EONNIOAA)
2
m
dx dx(y.0')=
gows
grw, 1/!
for any y. sf E Las- Then, the diameter D(Css) with respect to dx is bounded by
D(CM) S OlTV/ogd/A)
Proof. Let W (w) and recall the pseudo-metric
dx(u, v/) (Ey~~10....) Σ g 1213) 1/2
where y, v' LM-
Since g ~ ~N(0 Im) and the coordinates are independent, we have
m W (1ull lb612)
dx dx(
hence
dx (x. = w O (1a12-10 11/l))) ll2.
For each coordinate, using la² - b²1 la bl a bl and |1ys1 lu/ll S 1y: 3/11 obtain
||wi 10/101 s (19s (B( 1ys - s/1.
Then 14ll V for y, E LMs get
||v|| - luAl < 2 1y; 2/1-
Plugging this into the expression of dx yields
dx (y. v/) < 2 ||w @ (y (y- = (I -2')l2- Taking the supremum over v/ Lm gives
D(CM, dx) 2/F ( (W LM, 112).
By /Vershynin 2018 Proposition 7.5.4), it follows that
diam(W WLM, - (12) S 2m W(WLM)
Moreover, since WLM WM Lv the Gaussian width is monotone under linear maps and W(WLM) x [[M W(C.v) =: || W(Lrr)
Combining the above inequalities, we obtain
D(C dx) E CCC[IIIM W(CA) CCW((CN),
= 2V/2T.
remains bound A'. Let d and K B2(A') B so that CA K and hence W(C.r) < W(K). We have the bound K 1/4 Br. which implies
W(K) < w( ( B.)
= W(BI), and W(B1) = max
(g, S Co/log(2p).
SSSSP
Thus, follows that W(K) < O y /loRdd) of D(LM, dx) yields the claim.
Plugging the bound on W(C,) into the upper bound
16

---

Published as a conference paper at ICLR 2026
B.2 BOUNDING THE METRIC ENTROPY
In this subsection, we establish an upper bound for the metric entropy Me of the space Lw, To estimate this entropy, first provide detailed definitions of covering numbers and metric entropy. Definition 14. Let d be a pseudo-metre on IR Given vector x E IR and t 2 O, we define the dx-ball of radius centered
as (x(x,)) = {x' Id dx (2, S 1).
Definition 15. Let K,T C TR. be two convex bodies. The covering number N(K, T) represents the minimum number of copies of required cover K
A U + T)}-
T min E N: 3ad K
TT).
Let dx be a pseudo-metric and be a scalar. The covering number of a set K with respect to dx and radius t is denoted by [KK, dx,t)= N(K, (x(0tt)) t)), where 3x (0, t) is the dx-ball of radius t centered at the origin. The metric entropy is given by Mg = log (K, dx,t).
We now apply standard tool, the Dual Sudakov minoration (Bourgain J & V. 1989), to bound the covering numbers in both the residual space and the & e-penally space. The following theorem provides an upper bound on the covering numbers of the Euclidean unit ball within metric space using nnor balls with radius >
Definition 16. The Lévy mean of tp is defined as
E EgeN(,,talll9l
Mp
E to
Theorem 17.
(Dual Sudakov Minoration) Let llp be norm, and let B₂ C R.d denote the Eu- clidean unit ball, defined B2 {a Rd |2012 1}. Then,
M² +2
log (B2, (1 < O(d)
Lemma 18. (Woodruff & Yasuda 2023). slightly modified) Let q 2 2, let M E Rmx((+11 be matrix, and let w E 1.th be weight vector. Then, for standard Gaussian vector 9 ~ N(O,T), it holds that
Eg [[l m /qTT
and
Eg- [llalle] S vd+I.
We now focus the fi-penalty space for the Gaussian process. To bound the metric entropy of the set (1/A) using the unweighted ball, we decompose the process into two steps: covering the Fuclidean unit ball with Bxc, and covering B₁ using the Fuclidean unit ball. We define the unweighted Ep (including fxx) unit ball as B₁ = {or x E dR provides bound for the first step.
||>||p I 1}. The following lemma
Lemma 19. (Woodruff & Yasuda 2023 Let 2 and let Bp be the unit ball for the lp norm. Then,
log
log N (B2,, Boc, t) 0
+2
Since the B, ball has a non-smooth geometric structure, a substantial portion of its volume is con- centrated near center. This concentration implies that fewer smaller balls are needed to effectively cover the unit ball. A direct application of the e-net argument typically yields general bound of O((1 + 1)d+1) in the worst-case. To obtain the better bound by utilizing this concentration, we use the Sudakov minoration inequality (Vershynin) 2018), specifically for the non-smooth B ball, as follows.
Theorem 20. Let K. be convex body in IRd and let N(C, B2, denote the covering number of balls of radius required to cover K.. Then, for any >>
Vlog N(K B2, C. W(K)
where is an absolute constant, and W(K) = [suu (g. x)) represents the Gaussian width with respect standard Gaussian vector g N(O, Ta).
17

---

Published as a conference paper at ICLR 2026
Lemma 21. Let B1 {ar R | I 1/ and Bx far R
|| S 1/.
For any (0, 1].
holds that
log (B,, tx. $0 log d
Proof. Fix & E (0, and let E [t. 1]. We use the standard chaining rule for covering numbers log [(B,, Bxo, () I log (B1, B2, 7) log N (B2, Box 1/7).
Let g (0, Ia). The Gaussian width of B1 satisfies
W(B) = E sup ().z) = Bllg]lo = max [as| ||
2 12log(2d)
15i5d
By the Sudakov inequality Theorem 20). there exists a universal constant C₁ such that
W(
logg(2d)
log (B1, B2,2) s Ci
C1
y2
72
Let || 1lx = -loo- By Definition 16 Lévy mean
E g |o
12llog(2)
log(2d)
Mx
S C22
g
cvd
d
for universal constants c, C2 > O. Applying the dual Sudakov minoration theorem (for covering the Euclidean ball by || -balls,, we obtain that for E (0, 1].
M s
log(2d)
log N(B2, B3,, & C3 d
S C4
s²
for universal constants C3, C4. Substituting the two bounds into log ((B,, Bxc 1) yields
1 log N(B1, B t) Cs log(2d)
(~ +
72 tz
72
Choose 7 Vt E [t, (since (0, (). Thus, we conclude that log (B1, Boc,) f) S ( log d
which proves the claim.
Lemma 22. Muntteanu & Omlor 2024 Let M Immdd and let E Lgg be a non-negativee weight vector corresponding to the rows of M. Then, for any 1 S I 9 and any > 0,
N(BI,,(M), B,, (M), 2 ((B..((M) Bw. (M),
In the following, we give two upper bounds for the covering numbers in the l--pnallt space based on the radius t. For larger radii (t >> fn/A), the covering number scales as (1/t)?, indicating quadratic increase as decreases. Conversely, for smaller radii (t ta/ the covering number grows logarithmically with 1/t.
Lemma 23.
Let = d A > O, and let M E Rmxp have orthonormal columns. Define the set Boc (M) = {r x E T. || & 1) the unit ball in the coe-norm mapped by M. Let H
maxigigm lle Ml where e; E Re the i-th standard basis vector. Let to O(H logm Then, the following bounds on the metric entropy hold for t. >> to/X
/1ogm
log (MI) S0H2)) log d log m
X212
and 0 < < tu/
log (M),)) 50 (dlog d/x² + m ml (1+ to
)) Xt
18

---

Published as a conference paper at ICLR 2026
Proof. Let p d 1, and assume that M R has orthonormal columns, i.., M M 1p. Let ||.m. be the norm || = ||Malo on R", and denote its unit ball by
Hm == f= E IR" || 1 = {> | S 1).
Note that ox = Hm nT', hence by monotonicity of covering numbers.
S ENNDNN((G (N (2B1. Hm, t) = N (BI. Hm, 1e).
(I)
Let H == maxigigm lee
M|sso and let to = 0 H logm
By the Bernstein Bernstein-Jackson (Carl-
type) entropy bound for the embedding (R², -1:11l111111 a universal constant C1 such that for all 8 2 to.
PP 11 (see (Call 1985 ) there exists
H log d logm
log (B1. Hm, 8) C1
(2)
s2
Substituting s = At. and using equation yields, for 2 to/A,
H log d log m
log
Ba
log N(1, Hm M1 S Ci
X212
For < $ to/ we use the standard volumetric bound in (R", 11 11 leading to
log (B1, Hm, Xt) < log (B1,, Hm, Xto) + log N (toHHm Hm, Xt)
2 log d log m
40
- Ci
+ ml
1
X212
Xt
<0 (llod//2 + m log
to 1
))
Xt
This completes the proof.
In the following lemma, we present two different upper bounds on the metric entropy of the inter- section between the residual space (M) and the ipeenalyy space B₃ (1/A). Specifically, we employ the weighted &oo unit ball to cover both the weighted ball (w.)(M) and the unweighted ball B, with the same radius. We then provide bounds for two cases: when the radius t larger than to, and when is smaller than ln- Let Sup,'EC...
|| liu 2, be the weighted maximum of & supreec [||S A'x''' Il 1|/2'113).
leverage score, and define G ==1++
Lemma 24. Let > O, and let fw. ty Mx E (0, the metric entropy of fm with respect to the metric dx satisfies the following bounds, for 0 < 1 Lo/2,
(M) (1(A/)}- For any
log N (Cw,M dx,t) S (id Gmh) Od d/X² + m mllog1+ + Glo ))}:
At
and for to
T log m log N NL $ $0("
log min(1,
}),
t
x²
where to = =TV/ log m
Proof. For all y. yf E Bw.2(M), we have dx v/) < v''l.w'......22 (hence, in particular, dx controlled by weighted -tc- norm after the embedding used below). Next, define the matrix M Rmx((+1) such that each row of M,, is obtained by multiplying the corresponding entry of the weight vector w by the respective row of the matrix M, i.c., (Mw),, ); = vw, . -4, Since w; 1/p; represents the weight of the i-th row and p; is the sampling probability, we have w, for all i. Then, the convex body (M,) is equal to B2 (Mw, G), since
(w,((M) {
y range(M)
woy? < 1 BM
19

---

Published as a conference paper at ICLR 2026
Thus, for any t > 0, we have
log (M, I log N (B, 1lo,,o,
=log N
(M), Boo (Mw), 2G
By Lemma Lemma 4 and Lemma Lemma 22 Appendix, the following inequality holds
log N N(B,:2(M), O(dlog Gm
Moreover, by a slight adaptation to Ollog G²T).
Lemma we also have log N ( dx,t) I
Let H maxigism ||e, ooo be the maximum row-wise -nom of matrix M. By the inequality || | for any vector I, it follows that H maxigigm |c. M|] S maxigism ||e, M| VT. Consequently, applying Lemma 23 in Appendix, following bounds on the metric entropy log N (1/A)) Bo (M t/2)) I O(T log d-log for
obtain the
231 1 1o/2, and the inequality log (1/A),,, Box (, 1/2)) S (d d/ x + m log (1+ +1+0 1))
for 0 S to/A. where to O(T
log mg
Next, we consider the metric entropy on the L..M
log N (Lm, M, dx,() 1) log N (Cw,, M, M |1,01 )
=log N (B n (1/AA), M 11,0 )
t
S min (( 2 Mw 1l,0, 2G (BB(A) 11,0, 20 )
Combining the above inequalities, we conclude that
log N (C dx, t) I min(O((log Gm O(dlog d/X² + mlgg01 +
Gto ))},
At
for 0 < to/A A, and
log (LW,, dx min)) log m log d log
min(O
X212
fort > tu/A.
B.3 COMPUTING ENTROPY INTEGRAL
In this subsection, we bound the entropy integral of these (-nets using the following Dudley inequal- ity /Vershynin 2018) for Gaussian processes.
Theorem 25. (Dudley (heruality/Verssynin 20181) Let (X(t))er be standard Gaussian process defined on a measurable space with a pssudo-metric dx. Then, it holds that
C [
E
sup
X,
Vlog (T, dx dt,
LET
where T is convex set, C is an absolute constant, and X, alue of the Gaussian process indexed by t T.
Lemma 26.
[Woodruff Yasuda
2023) Let O < 8 1 and be a positive constant. Then,
C
(wi0g log
C CVT
V log dt <
5
20

---

Published as a conference paper at ICLR 2026
Lemma 27. Let M Rmxx(d+1) be matrix, where O(d and ler X, O. Then, the metric entropy of L..M satisfies
In Vlog (Cw, dx,t) dt s o (GV log m) (
(1 1 (1+ log d min {1, v logd 1)
X
where T the maximum weighted &y Ez-leverage score of M.
Proof. Note that it suffices to integrate the entropy integral from 0 to the diameter D tiam((w.aa) because for t > D, the entropy is zero. Let to O logm) and let t' be a dius with l' E [ D). For small radii < t', we use the first bound of Lemma in Appendix as follows
Cm
Glo
log (Lo,, dx, 1) S min log +.
(g + m log(11 + At.
))}
By Lemma 26 in Appendix, the entropy integral is bounded by
L' log N (Cw, dx, dt
Gm $ &minl// f/" Vocalos (m)
dt, 1/ V Vo(mlog(1 +
Gto
+ log m m/22) df}
1A
Gm /dlog F. vm / log (ot(1+ [1
Glo
m log
st(t) min
+
At'
Ott) min
[V
Gm Vdllog t'
V Vmlog 1
Gr
V
log
m log
At'
d
On the other hand, for large radii t > t', we use the second bound of Lemma 24 (in Appendix), which gives
7G2 log min(1,
log d X }).
log N (C M, dx s O
f2
Combining these inequalities, we obtain
log N(Lw, dx, dx, di s 0(1)v logm m- min(1, Vog d
(o) 1
dt
X
t
=0 log min(1, Vlog
(
G
log
By setting m = O(d + log(1/))), applying Lemma and choosing the radius t' G///d, obtain
V log N (Cw.M, di
- 1/' Vlog dx, dt +
So
D
Vlog N(Lu, dx. t) dt
m < O(GVF) min Vlog m, V d
V log(
1 +
vlog m
+
v m log m
A
+ +o(Gv logm) min
Vlogd d
log d
A
v Mlg d
(OGG/llogm)
1 log d min
21

---

Published as a conference paper at ICLR 2026
Lemma 28. WWodruff & Yasuda 2023) Let A' E I=x((++) and X O. Let A
siili + st srrnn++ M 9s A'r (1) Given a convex set L. let Mg be the metric en- tropy of L, and let D Gaussian complexity associated with L. Then,
Eg-NOo,)lAA" & (2Mc) (Me/D) + O(VID)'
Lemma 29. Let A' E [ux((+1) and let S E Rax= be diagonal sampling matrix with exactly m nonzero diagonal entries. Assume that with probability at least 3/4,
|SA' = (1 211
for all x E Rd+11
(3)
I=
E [n]] Sa + 0} be the sampled index set, and define
wi ( + A|ll|
G(SA) = Σ
sup SA'230
|SA'x] 1. A|12211
SE
Then
Pr (((S)) <89(A)) 2 2
Proof. Define for E [n] the (unweighted) sensitivity
AA,= + A ||=||1
ec(A)) = sup A'rşe00
AAxx1 + >||>=|11
and define the distortion factor
||/4 13 + A||=1| 11
I(s) = sup
S
12 u2 + A
A||==||
SA'an60
On the event equation 3 we have ||AA''] 2 w.2 2 ||4 1/ for all x. hence for all x.
|| 2 + X
A| <
| \|=||||
12 + A||=||| S 2,
|SA'x ?. A||==|11
1
and therefore I(S) < 2. Consequently, we get
3 4' e I= {i i E [n]] Su # 0}. Since S is diagonal, (SA'): SuAle and Sis # 0. In particular, ((SA")).)) 5 Ma 2. Since w; 2 1, we have
Pr [r(S) 52] 2
2 11/l| I w ||,,001 m
X 11oll1)
wi (SA(AA))
Thus, for every E I, we get
w/ (SA' + ||||||
|
| + A||z||1
sup SA'200
I S sup
sup
||SA'' + A||==|11
5A'270
||A'' + A|
5A'200
||A 12,2 + +||==|
S w.S (1') T(S).
Summing over i 7 gives
G(SA') & I(S)
Σ
w. S. (A') < I(S) Σ w, 5
VE!
Then, we have
n
a
w. Sh (1()))
= Σ El Bl Slw,S
Σ (A4 9(A))
i=1
By Markov's inequality,
Pr Σ w. (A') < 40(A') 2
With probability at least 4. both events (T(S) < 2} and EE, w. (. < 4G(A)) hold. There- fore, it follows that Pr(G(SA') 89(4') 1
22

---

Published as a conference paper at ICLR 2026
In the following theorem, we present the main result provides bound on the 1-th moment of the sampling error E|E|'.
Theorem 30. Let A' E Rax(d+t) be an input matrix, let S be random sam-
pling matrix, and let E E (0,1) and X
O be parameters. If
2 (log (d (Inn min 1, logd } + !og and for all E [n] it holds that x²
dj2
- |,)1
P: 2 min
n
where (A)) denotes the 2 leverage score of the i-th row of A. Then, with failure probability at most 6, it holds that for allx E Rd+1 with x4+1 1,
a + A||2|11 & (1 + (11 + A|[x[11),
and the coreset size is at most
m = Ö (4leg min(1,
log d X2 2
d log 5)
Proof. By the construction of the sampling matrix S, for any E [n]. the sampling probability satisfies < Pj S 1, and the corresponding sampling weight S. = 1/p: 2 1. This im- plies that E(|SA'xx| + \||=]||
||x'= + A||2||1 for X > 0 and any vector x. We set
Ō log min(1, logd) + log :). where vi Ö ( log dllog min (1, x ) de- notes the maximum number of finite moments of the sampling error &. To bound the coreset size m, let X; be the indicator random variable that represents whether the i-th row included in S. Applying Lemma i0 Appendix, we get
1 nt = a (2+2d) s 4ad.
E
Σ Xi = L p. = a 1+
1++(20 (2T +
Similarly, we can derive the lower bound m follows
I
X
P.
2
Σ
2T,
2ad.
i=1
1=1
By applying the Chernoff inequality, we have
n
m7 2. E
Σ X2
S 8ad
with failure probability at most 2xxp (-E X:)/3) S 2 -x2epp(222 (gd) <
Applying Lemma I the analysis of the empirical process associated with the sampling error can be reduced to Gaussian process. Specifically, we obtain
Es sup A +|=]]= ||| xl ||A
I (27)) sip A -|/|=||==1,2er
Σ iEQ
grws AKe 2
where 1 an integer, w; denotes the weight for sampling the i-row, Q the indices of nonzero diagonal entries in S. and g (O, I..) is standard Gaussian vector.
Next, we define A = supp + =||=||= (Eies gow; A(xrl²) for the random sampling matrix S. To further bound the quantity A, we apply Lemma 28) which connects A with the metric entropy Mg and the diameter D geometric body resulted by the Gaussian process. This gives us the following bound
23

---

Published as a conference paper at ICLR 2026
for fixed I.
Let M = SA' denote the sampled and rescaled matrix with m rows, and let w represent the weight vector corresponding to each row of M. Next, bound the maximum weight leverage score T sup Mall w, wi M
We set the number of samples m be O(d + log((/0)) using the lg leverage scores sampling method (Cohen et al. 2015), which achieves || A'x 1 |. S (1 + A'xl1 for fixed sampling matrix S" with probability at least 1 - 6. By applying Lemma 29 in Appendix and the definition of sampling probability. we have T I O(1/a).
According to Lemma 6 by choosing the constants in sufficiently large, we obtain a bound on the metric entropy
(GVTlog 1+ log d min 11, vlog d })
(1+ (1+ log d. min
{1, vlogd d
s 0 (Gaa-112/1o0)
$ ==/8:=Me
By Lemma 3 we derive a bound on the diameter O OTT/log d/A) S Vaao-Vologooo d/A) S 2v D.
By combining the bounds on the metric entropy Mg and the diameter D, we ensure the sampling error Eg--N((....)]AAA)) I é'. Since the sampling error & = sup='ecw ||| 1''A''''le l - | 11
have E¹ < 3''8, which yields EEEY (3z)'8. By using Markov's inequality, we have & < 32
with probability at least
B.4 OMITTED PROOFS OF LOWER BOUND FOR CORESET SIZE
In this section, provide the lower bound of the coreset size for LASSO regression, using standard information-theoretic approach (Wang et al. 2010 Wainwright 2009 Parulekar et al.
2021 Mai et al. 2023) based Fano's inequality and KI. divergence computations. Here, we start by constructing a hard instance over the k-sparse supports.
Let C c {0, 13dd be set of k-sparse binary vectors (i.e., each vector has exactly is nonzero entries), such that |C| N > (d/k)* and any two distinct vectors c(0), ,ef)) E C satisfy (supp(c()) n supp(c(()) Ck for some constant C' (0, Such codebook can be constructed using standard techniques from coding theory. For each codeword c( C. define
1,
(
E Rd+1
Let G E mad be a matrix with i.i.d. standard Gaussian entries. Define the data matrix Z G(I + T10(0 Then, each row 2) No ,()(T and the data distribution is
P. (0 (TT)
We show that exact support recovery impossible with fewer measurements than those suggested by the information-theoree lower bound, given the input distribution.
Lemma 31. Let e (0, 1). and let u gd+1 be the vector with (1, xc), where i codeword uniformly chosen from C. Let P. be the multivariate Gaussian distribution with covariance I + To Then, for any estimator attempting to recover a k-sparse vector c, with at least 1/2 probability, the number of samples m. must satisfy
A: (log(d/k))
m 12
2
Proof. Let Pi.... PN be the distributions constructed above. By Fano's inequality, we have Pr[error] 2 Ent, DKL (P,])P,) + log2
log(N (N - 1)
24

---

Published as a conference paper at ICLR 2026
where (PI(P. denotes the Kullback-Leible divergence between distributions P, and P,- To ensure the error probability less than 1/2, it suffices to ensure
DKL. (P.IP))) S 4 log N.
N
According to the definition P,, the KL divergence between two such distributions
DKL DKL (P.)) m (e..
where Σ; = + NOT Using the formula for KL divergence between zero-mean Gaussian distribution, have
(V E.)I((, 1 (tr(E) d + log det Σg det Σ;
Since Σ; is a rank-1 perturbation, by the Sherman-Morrison formula, we have del (E;) = 11=+++/u00 1+||/(001
,00 and Σ,' 1 Thus, we obtain
(PL(P) (110001123 11 (w00) 20)
|| |13 + | 113
+ log
1+ |
For any i E [N]. holds that [|,:(0] 112 = + 2 Similarity, for any i # j. the inner product satisfies
(ubiTyylt (1
k ((()) s (1+C,)).
Plugging these bounds into the expression for KL divergence, get
DKL (P,)II,) s O(2m).
Let log N = ( (og(kk)). Applying Fano's inequality, it holds that
Pr(error] 2 1 mC'e2 + logg 2 log
To ensure Pr[error] & 1/2, we have
koog(d) log(d//))
Ce m 2
log N 2(k log(//k))) + 2 0
Our proof method, while differing in approach from previous work (Wainwright 2009 Mai et al, 2023) that focuses on sketching algorithms, is based on similar ideas. In particular, by analyzing the coreset algorithm on a constructed hard instance, we establish lower bound on the sample size required by any algorithm to achieve (1 + e)- approximation on this constructed hard instance.
12 < 1 and [|bl|2 S 1. Let be diagonal sampling matrix with m nonzero entries. Suppose there exists estimator that returns I arg minger4 Ax Sbl} + A||æ=|11 and satisfies
Lemma 32. Let E Raxd b R", and E (0, Assume that ||A|
A
bll + ا||ا|| I (1+ E)
min (1 b12 -1[=
reRd
Then, the coreset size m must satisfy
(2 log x.c
it Ω Ta
m
02 d log
i 0
(1)
25

---

Published as a conference paper at ICLR 2026
Proof. We prove this result using similar approach to Theorem 13 in (Mai al. 2023). We take [b A] G(T + vv )1/2, where is codeword in the set C. Let S be sampling matrix that selects rows of and b. Since only the row indices selected by S affect the coreset, and the weights can be absorbed into the analysis via rescaling, we may, without loss of generality, assume that all nonzero diagonal entries of S are equal to Under this assumption, the compressed matrix SG(T + wo )1/2 has the same distribution G(T vu )1/2.
By the concentration properties of Gaussian matrices (see Exercise 4.7.3 in (Vershynin 2018). with high probability, the LASSO objective satisfies
Ar
bll2 + A||2||1 ~ 1 + | (1 ec x)² A||=|11 L(x),
where e = (1 c). Since L(x) a 1-strongly convex function, we get
L(#) 2 L(x") || - x x=1
for any L, where x² is the minimizer of L(x).
Fix e = 1/2, we set X = 2v _ Here, it holds that x² = c/5 and L(x*) s 2. Suppose there exist a estimator algorithm satisfies T( s (1 (T) for sufficiently small Then we have
(1 + 0. Lz)) 2 L(x") 1| - x" x=1
which means the gap || xx"
Choosing small enough constant C1, we can recover supp(u). By Lemma 31 if कxट o(d), the required lower bound of O (x log d) the coreset size; if 4x O(d), the required size is at least (2( E log d).
C COMPLEMENTARY EXPERIMENTS
C.1 EXPERIMENTS ON SKETCHING ALGORITHMS AND LASSO-SENS
In this section, we present experimental results comparing the performance of our proposed LASSO- Sens algorithm with a "ketching-baser algorithm for solving LASSO regression. We also acknowl- edge recent advances in sketching for LASSO, such as the work in Mai et al. (2023), which utilizes random projections accelerate the optimization process.
To ensure fair comparison, we follow the same experimental setup used in Section 4 conducting experiments on the Synthetic, CT's, and mediamill datasets with identical coreset sizes and regular- ization parameters. We evaluate algorithm performance in terms of loss, runtime, and sparsity. For the sketching- based algorithm, we set the number of sketching rows equal to the coreset size and run each experiment 10 times, reporting the average results.
As shown Tables 6 and 7 the proposed LASSO-Sens algorithm consistently achieves lower loss values than the sketching method on both small- and large-scale datasets. On the large-scale mnist8m dataset, LASSO-Sent -ensSSS--Sii-- is up to to
times faster than the sketching algorithm when the coreset size is set m {15, 20} x d. Moreover, on the Synthetic dataset, the sparsity of the LASSO- Sens solution is much lower than that of the sketching algorithm. Overall, the experimental results show that the proposed algorithm achieves lower regression loss and lower sparsity, particularly large-scale datasets.
C.2 EXPERIMENTS ON SENSITIVITY SAMPLING FOR STANDARD AND MODIFIED LASSO OBJECTIVES
In this section, we compare the performance of the sensitivity sampling algorithm on both the stan- dard LASSO objective and the modified LASSO objective proposed in Chhaya et al. (2020), which takes the form Arr blli + A||=|| In Section
used the FISTA algorithm solve the standard LASSO problem, as it leverages the proximal operator of the l norm. However, this solver is not applicable to the modified LASSO formulation, which involves squared & regularization term and lacks an efficient proximal operator. As a result, directly comparing the two objectives under our original framework would be unfair.
26

---

Published as a conference paper at ICLR 2026
To ensure fair comparison, we follow the methodology of Chhaya al. 2020), which utilizes the Global Optimization Toolbox from MATLAB. Specifically, we use the patternsearch solver to address both the standard and modified LASSO problems. In experiments, the solver pa- rameters are set as follows: MaxFunct i onEva vations = 1 1,00,,000 and MaxItera ons 25,000. To quantify the approximation quality of the coreset algorithm, error, defined as V
utilize the relative Iv where Vi denotes objective value on the full dataset and 1/2 denotes the objective value on the coreset solution evaluated on the full dataset. The experiments are con- ducted machine equipped with Intel(R) Core(TM) 15-14400F 16-core processor with 32GB of memory, and the implementation is executed in MATLAB R2018a.
We first Algorithm to construct the coreset, and then apply the patte patternsearch solver to solve both objective functions on the coreset samples. The experiments are conducted on mediamill dataset using the same coreset sizes and regularization parameters ment is repeated 10 times, and we report the average results. As shown in Table 9 the sensitivity sampling algorithm for standard LASSO generally achieves a lower relative error compared to the modified objective at the same sparsity level. Meanwhile, the computational time required by the two objectives is comparable.
in Section 4 Each experi-
D USE OF LARGE LANGUAGE MODELS (LLMS)
No large language models were used in the ideation or writing of this paper.
Table Comparison results loss, runtime, and sparsity on CTs dataset (n = 53,500, d 386) for varying coreset sizes at À {1,5, 103.
Lambda Metries
Algurithms
Coreset Sizes
10d
15d
20d
LASSO
50.52-10
Loss
LASSO
66 56.5627.58
00.57-40.33
50.57-10.02 50.78:10.16
LASSO-Unifore
84.57+22.59
51.36=0.45
50.87:1.200
50.7110.14
A
LASSO
507.01
Time (8)
LASSO-Sens
9.32
13.17
21.20
36.72
68.46
121.51
LASSO-Umform
13:25
21.75
38.00
72.04
132.07
LASSO
229
Sparsity
LASSO-Sens
339
255
236
234
223
226
LASSO-Uniform
341
265
228
224
220
230
LASSO
252
Loss
LASSO-Sens
270.90==14.83
254. 254.70-1-0.6
253.04+:0.30
252.71=1..12
252 63.007
252.62--0008
LASSO-Unte Uniiorm
323.35-140.59
263.83-16.21
254.30-10.90
253.30-10.51
253.08=0047 +0.30
=
LASSO
502.08
Time (8)
LASSO-Sens
9.51
13.56
20.96
35.76
66.54
118.12
LASSO-Unifom
8.95
13,40
21.24
37.12
74.12
129.55
LASSO
156
Sparsity
LASSO-Sens
176
169
161
160
154
159
LASSO MASSSO-nnffoma Uniform
183
172
165
153
173
162
LASSO
8.10.9
Loss
LASSO-Sens
548.67- 73.6633179.1
512.16-13,00
10.954--11.1
70-.73-+..50
505.60
305.30
AASSO-Uniform
534.78-22.85
510.78:13.99
506.99.11.49
306.1011.00
705.7510..5
10
LASSO
517.13
Time
LASSO-Sens
36.70
70.58
110.78
LASSO- Uniform
8.92
13.42
21.80
37.16
73.78
124.45
LSSOO
156
Sparsity
LASSO-Sens
1.6
154
158
LASSO-Umform
157
154
27

---

Published as a conference paper at ICLR 2026
Table 3: Comparison results of loss, runtime, and sparsity on Synthetic dataset (n
10, 000,00 d
200) for varying coreset sizes at {0.5, 1,,,
Lambda Metrics
Algorithm
Coreset Sizes
1d
5d
10d
15d
20dl
LASSO
11. 80-8801222
Loss
LASSO-Sens
12.78-0049 14.75=0.14
12.89+0.48 14.76#0.15
12.55+00.39
+2.28
12.23++0.32
12.25-00.33
LASSO-Unifont
14.55+0.33
14.30=+0.47
13.87=0.50
13.36=0.49
LASSO
72.76
(8)
LASSO-Sems
5.74
7440
9,27
14.49
18.24
21.06
LASSO LASSO-Unifon Uniform
3.86
7.99
10.17
15.02
19.81
23.69
LASSO
Sparsity
LASSO-Sens
35
LASSO-Uniform
28
28
28
28
30
32
LASSO
20.85=0.15
Loss
LASSO-Sens
20.51::.117
20.51:10.19
20.57:10.14
20.67.
20.60
LASSO-Umiorm
20.90 20.10
20.96:10.12
21.05:10,16
20.92.10.15
20.79-10.1 12
20.69:1.22
A=1
LASSO
78.34
Time (5)
LASSO-Sens
5.68
9.28
14.31
18.65
21.29
LASSO-Uniferm
5.93
9.76
14.84
20.46
23.11
LASSO
28
Sparsity
LASSO-Sens
31
29
28
28
LASSO-Uniform
LASSO
69
0,20
Loss
LASSO-Sens
69.31-0.11 69.95 ..68
69.18++0.03
19.16-10.01
69.15++0.00
69.15=00000
69. 19-15==0:00
LASSO-Uniforn
70.624 1.84
70.65 1.68
69.35:10.49
69. 69.28-10.33
69 69.22-10.26
LASSO
72.55
Time (8)
LASSO-Sens
5.64
7.41
9.35
14.48
18.57
21.49
LASSO-Uniform
5.90
7.82
9.81
15.86
20.39
24.88
LASSO
Sparsity
LASSO-Sens
28
27
27
27
27
27
LASSO-Unifem
27
27
27
27
27
27
LASSO
129.53-10.08
LASSO-Sens
130.27-L0.58
129.66:10.07
129.
560063
129 54:10.02
129.53-10.01
139-53-10.00
LASSO-Uniform
131,4343.100
130.78-11.8 1383
129.55 0.03
129.5340000
129.53-100.1
129.53-40.01
10
IASSSO
Time
LASSO-Sens
5.67
7.31
9.27
18:09
20.92
LASSO-Umiform
5.85
7.92
9.96
15.07
19.35
24.56
LASSO
Sparsity
LASSO-Sens
LASSO-Unit Uniform
27
27
28

---

Published as a conference paper at ICLR 2026
Table 4: Comparison results of loss, runtime, and sparsity on mediamill dataset (n
30, 19,993, d
120) for varying coreset sizes at
5, 10).
Lambda Metrics
Algorithms
Coreset Sizes
2d
5d
10d
15d
20d
LASSO
7.35
Loss
LASSO-Sens
7.68+0.114 7.89:0.42
7.41=0.03
7.37++0.01
7.36++0.00
7.36++0.00 7.36=t0.01
7.35++0.00
LASSO-UniEE
7.47=0.04
7.38+0.01
7.37+:0.01
7.36=#0.00
LASSO
148.66
Time
LASSO-Sens
4.01
5.05
7,70
11.09
2.95
4.03
LASSO LASSO-Unifore Uniform
3.90
4.99
7.56
10.81
2.92
3.97
LASSO
Sparsity
LASSO-Sens
57
LASSO-Unifore
46
50
53
55
S7
LASSO
14.68
Loss
LASSO-Sens
15.50-0.335
14.87:40.07
14.74-10.03
14.71=0.01
14.00:1000
14.69:10.01
LASSO-Unform
16.23:10.71
15.12:10.25
14.79.10.04
14.73-0.03
14.70:10.01
14.69-10.00
A ==
LASSO
149,90
Time (8)
LASSO-Sens
11.06
LASSO-Umifrm
5.12
7.55
11.01
2.95
4.14
LASSO
58
Sparsity
LASSO-Sens
52
55
54
LASSO
72. 0.22
Loss
LASSO-Sens
18.18+22.81 8.81
74.88++ 1.08
73.43++0.30
73. 13.16-0.18
73.05=#0.19
72.92++0.01
LASSO-Uniform
1.76
73.66:10.61
73.37=0.49
73.1510.28
73.07-10.29
LASSO
151.54
Time (5)
LASSO-Sens
3.78
4.77
8.00
11.08
3.04
4.03
LASSO-Unifom
3.63
4.82
7.56
10.98
2.97
4.03
LASSO
Sparsity
LASSO-Sens
40
45
48
49
SS
LASSO-Uniorm
36
40
47
49
52
54
LASSO
Loss
LASSO-Sens
152. 40-.44413.84
147, 26-12.233
145.
13:10.82
144 444.42-1..3
144.18:10.22
144.4700455
LASSO-Umifrm
160.69-110.11 10.16
150.62-:4.67
146.29::1.73
144.63-40.61
144.9741.12
142.73-0.27
10
LASSSO
155.54
Time
LASSO-Sens
4.94
10.86
3.03
4,26
LASSO-
3,58
4.81
8.35
10.75
2.98
4.22
LASSO
47
Sparsity
LASSO-Sens
LASSO- LASSO-Uniforn
42
29

---

Published as a conference paper at ICLR 2026
Table 5: 8, 100, 000, d = 784) for varying coreset sizes at 10.5,1,5. 10}. If an algorithm fails to output a solution within hours, the metries are marked as 48 h.
Comparison results of loss, runtime, and sparsity on mnist8m datasets (n
Lambda
Metrics
Algorithms
Coreset Sizes
10d
15d
20d
LASSO
Loss
LASSO-Sems
1.27E7 LO3E7
3.30E4
7.71E3
161E4
4.0322
145E4 6.53E6
1062
143E4
L80ED
1.371
L.KED
LASSO- Unsioom
5.8328 1 2.1358
L,798 2 4,25E7
3.59E7
3.63E7
2,006
4,466
I 2,85E6
5,00E6 I 1,0966
0.5
LASSO
46 >
Time (5)
L-ASSO-SeRs
304.32
314.23
370.11
512.79
203
K59,2
LASSO-Umioem
19.39
30.61
$8.05
184.22
336.58
459.11
48
Spanity
LASSO-Sems
JASSO-Unnffomm
704
712
725
728
LASSO
Loss
LASSO-Sems
161E7 4.77EX
LO1E?
3.16E4
8.18E3
168E4
5.17E2
148E4
2.052
141EA
1,3E2
1.3E4 + 7.5
LASSOOUnnitem
5.68E7
1,3588 + 6.33E7
1.007
3,20E5
9,35E6
4.36F6
5,37E6 # 2.2166 3.04hh + 1.1366
A=
LASSO
48
Time (5)
LASSO-Sems
302.37
316.26
366.99
$22.60
724.51
$38.05 463.57
LASSO-Umilee Unufom
20.25
30.3
38.01
187.43
352.15
LASSO
48
Sparsity
LASSO-Sees
Loss
LAASSO-Sems
4.5066
2.87E4
4.2183
1.7284
4.57F22
49944
2.52F2
4554
18882
1,2244
14992
LASSO-Unifmm
5,98ES
7.60E
1,2388
3,26E7
2.15E7
7.61E6
9.22E6
2.22E6
3.99E6
1.09E6
3,05E6 1 9.0SES
LASSO
48
Time (5)
LASSO-Sems
299.24
317.45
368.02
$27.51
708.16
$75.08
JASSO-Umifom
19.32
26,66
$7.07
186.32
341.58
401.96
LASSO
46
Sparsity
LASSO-Sems
780
776
770
767
765
763
Uniform
Loss
LASSO-SSms
9,47E4
1,27E5
1.73R4
100E2
5SB4
1.54F2
4994
3.28E1
1,4744 K8IEI
LASSO-Unifora
1,96ES
181E8
1,2588
5,99E7
1,58E7
5.71E6
8 8.34E6
1.86E6
3.99E6
9.91ES
3.50E6 1 66ES
10
LASSO
48
Time (5)
LASSO-Sems
302.45
318 28
363
528 66
720.44
870.80
LASSO-Unioen
19.95
21.2
39.64
187.25
327.57
513.11
LASSO
46
Spanity
LASSO-Uniiomm
LASSO-SenS
781
713
769
765
763
Table 6: Comparison of the sketching algorithm and LASSO-Sens on the CTs dataset (n 53,500, d = 386).
Lambda Metries
Algorithms
Coreset Sizes
2d
1.5d
20d
Loss
LASSO-Sens
Sketching
24.11+0.30
0..03
23.99=0.01 23.99=00.00
23.98++0.00
23.98-+0.00
23,97=20.00
23.97-t0.00
23.97=10.00
23.97:+0.00
23.97=0.00
23.97-0.00
0.5
Time (s)
LASSO-Sens
Sketching
7.21
5.91
7.18
6.61
10.49
9.66
13.58
16.05
21.37
17.68
22.62
Sparsity
LASSO-Sens
Sketching
382
383
360
359
319
314
313
309
Loss
LASSO-Sens
Sketching
48. 10=10.75
18.0060
47.98=0.01
47.97=00.02
47.94:10.00
47 47.93+00.00
47.93-10.04
47.93-10.00
47.93-10.02
47.93-10.00
47.93=0.03
47.92-0.00
Time (s)
LASSO-Sens
Sketching
6.83
6.11
7.26
6.74
10.40
9.95
13.38
16.12
21.54
18.51
22.27
27.23
Sparsity
LASSO-Sens
Sketching
345
327
243
241
219
222
214
215
217
214
216
215
LASSO-Sens
242.48-11 1.44
240.20)--0.22
711177--011
Sketching
1.3
240,39110.14
239
130.05
60.00
239.65:10.05
239.64:10.02
Time
LASSO-Sens
Sketching
6.12
7.13
6.79
7.28
10.20
9.90
13.85
16.36
21.52
18.00
26.74
21.96
Sparsity
LASSO-Sens
179
168
156
154
158
157
Sketching
174
166
159
155
159
158
Loss
LASSO-Sens
Sketching
495.48 195.48-12..57
395.54++2.59
481.58- 1.01
482.36:11.05
479
479.98-10.24
479.52 52.1012
479, 17-9188-
479.33-10.17
479.177--00
479.00-+0.23
479. 27:0005
À 10
Time
LASSO-Sens
Sketching
7.21
7.29
7.05
13.34
21.51
18.26
21.74
Sparsity
LASSO-Sens
169
153
157
153
155
153
Sketching
170
159
149
149
156
153
30

---

Published as a conference paper at ICLR 2026
Table 7: Comparison of the sketching algorithm and LASSO-Sens on the Synthetic dataset (n 10, 000, 200).
Lambda Metries
Algorithm
Coreset Sizes
1d
2d
5d
10d
15d
20d
Loss
LASSO-Sens
Sketching
14.24=0.41 25.52:14.57
17.15+0881
14.02=00330
13.27400559 14.12+0.51
13.52+00200
12.83-0044
13.39:10.12
12.93-40.26
13.12-0.10
13.19-0.16
À = 0.5
Time
LASSO-Sens
Sketching
4.23
3.84
4.77
4.96
5.55
3.72
6.19
6.38
7.60
7.93
9.21
8.21
Sparsity
LASSO-Sens
Sketching
101
40
106
34
113
38
111
9
111
40
108
40
Loss
LASSO-Sens
Sketching
21.41:0.17 31.52=#1992
24.89=0.22
21-42-0.22
22,90++0.18
21 53:4
21.47:0.14
22.31-20.08
22.23:+0.03
21.57:00112
21.61=0.06
22.14-0.05
Time (8)
LASSO-Sens
Sketching
4.02
4.98
4.99
6.51
7.67
7.85
7.99
Sparsity
LASSO-Sens
35
24
27
26
26
Sketching
90
Loss
LASSO-Sens
Sketching
66, 78-10.08 72.24
69.02=0.43
66.77=00.01
67.5840.19
66. 7.010000000
67.09:20.05
66. 66.76-1-000
66 76-10.00
67 67.00=10.06
66 76-0000
66 66.82
Time (s)
LASSO-Sens
Sketching
3.90
3.82
5.29
5.40
5.18
4.81
6.39
6.64
7.64
7.84
9.20
8.04
Sparsity
LASSO-Sens
Sketching
80
25
78
24
Loss
LASsO-Sens
Sketching
122.99-10.28 127.4910.81
124.60:1.355
02.007-10.09
123.4811.116
122 81 +0.02
122 0.01
123.02-0.04
122.96:10002
122-82-10.00
122.92:10.03
122.83-10001
Time (s)
LASSO-Sens
4.13
5.30
4.83
6,48
7.63
8.07
Sketching
3,95
3,20
5.11
6.65
7.71
9.16
Sparsity
LASSO-Sens
25
24
Sketching
65
59
47
37
33
27
Table 8: Comparison of the sketching algorithm and LASSO-Sens on the mediamill dataset (n 30, 993, d 120).
Lambda
Metries
Algorithms
Coreset Sizes
1d
2d
5d
10d
15d
20d
Loss
LASSO-Sens
Sketching
8.40-10.43 8.54:0.15
8.19:10.04 8.25:10.04
8.174:0.22 8.18:10.01
8.15-0.01
8.16=0.00
8.15:00.0
8.15+0.00
8.15:100.00
À = 0.5
Time
LASSO-Sens
Sketching
2.57
2.14
3.37
3.28
4.69
5.07
4.94
4.69
5.13
5.81
Sparsity
LASSO-Sens
58
600
62
63
61
Sketching
57
60
62
60
62
63
Loss
LASSO-Sens
Sketching
16.77-0.23 17.16:20.45
16.4620.07
16.34-0.16
16.27-10:03
16.29:1004
16.24:10.02
16.25:10.01
16.23-10.02
16.25
16.24=0.01
16.22-0.11 0.01
À
Time (8)
LASSO-Sens
Sketching
2.47
2.13
3.07
3.68
4.91
4.91
4,48
5.30
5.78
Sparsity
LASSO-Sens
Sketching
54
57
58
59
59
59
61
57
61
60
Loss
LASSO-Sens
Sketching
83.62-4..37 87.07=11.31
82.6620.93
01.00
80.5710.37
80 30-10.-1111 18
80.2410.11
79 99-95-10111
80.07
80.26:10.17
80.20-0.11
80.01 0.009
Time (8)
LASSO-Sens
Sketching 2,26
2.46
3.45
3.30
4,71
4.64
4.93
5.02
4,49
5.20
5.90
5.82
Sparsity
LASSO-Sens
44
51
$1
Sketching
49
Loss
LASSO-Sens
Sketching
177.471:5.33
163.26+-8.88
5.5269-55.25
163.25::0.83
5.25
160.31
1.59.24--038
158
159
0.55
0.330
158.91+-0
159.08
159.03-10.14
158.65++D.40
Time (s)
LASSO-Sens
2.56
3.45
4.65
4.90
4.47
5.81
Sketching
2.11
3.23
4,50
4.80
5.31
5.83
Sparsity
LASSO-Sens
51
49
Sketching
41
46
49
49
49
31

---

Published as a conference paper at ICLR 2026
Table Comparison sensitivity sampling applied to standard and modified LASSO objectives on mediamill dataset (n 30, 993, d 120).
Lamhda
Metrics
Algorithms
Coresct Sizes
2d
Si
10d
15d
20J
Relative error
modilied LASSO
LASSO
0.1016:20.668
1013
0.11-3:20.0552
0.1659:00.616
1.0972=0.0944
0.0417=000291
0.0430=0.0372
0.0800=0.0626
0.04342000405
0.0557=000057
0,0543=0..491
0.0243=0002155
A=1
Time (5)
modilied LASSO
LASSO
8.04
7.81
13.49
13.25
15.09
14.84
16.90
16.73
1868
18.49
22.23
21.97
Sparsity
modified LASSO
LASSO
120
120
Relative error
modified LASSO
LASSO
0.1267+0.1121
2:02-42022204
0.0646:00.0299
0.15 0.1166:20.133 1329
0.0520-0.8321
0.0809 -000547
0.0306:00034 0.330-000443
0.048550.022
0.0919
0.0145
A
Time
modilied LASSO
LASSO
8.10
7,94
13.54
13.34
15:17
15.04
16.68
18.93
18.33
21.97
Sparsity
LASSO
Relative error
DOL4X-00
0.0331:00.022
LASSO
modilied LASSO
13.37
Sparsity
modifedd LASSO
LASSO
120
32


Reviews:
[{"review_id": "KJ9PpbWb8q", "reviewer": "Reviewer_SFut", "summary": "The paper considers the problem of coreset construction with sensitivity sampling for LASSO. Note that the coreset construction via sensitivity sampling is a known method. The main contributions of this paper are providing theoretical guarantees for sensitivity sampling in LASSO. The authors then provide some experiments to validate their methods.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clear and easy to follow.", "weaknesses": "First things first, I am not an expert in this field, so my evaluation might be unreliable. I did not check the proof, and I will revisit it in the rebuttal phase. Here are my two cents on the paper's weaknesses.\n\n1. Comparison with sketching methods: I see that the experiments of this paper were only conducted with Vanilla LASSO, sensitivity sampling, and uniform sampling. However, they did not compare this method with other approaches for handling big data, like projection methods/sketching. As a general audience, I expect a comparison here, to see if I should really care about sensitivity sampling for LASSO, or if advanced sketching methods for LASSO should work for me/or even work better than the proposed method, when the number of samples ($n$) is large.\n\n2. Comparison with modified LASSO coreset: again, I see that the problems of sensitivity sampling with modified LASSO (using $\\|x\\|_1^2$ instead of $\\|x\\|_1$) are also considered. The authors should also compare their method with this one. Although the authors claimed that the modified LASSO introduces some unexpected correlation between features, it is good to know how their performance compares to their proposed approach. \n\n3. Cost of sensitivity score calculation: I see that the computation of the coreset score scales cubically ($O(d^3)$) with the number of features $d$. It should not be the problem for the case $d \\ll n$ as the authors considered. However, in a general high-dimensional case, $d$ will scale with $n$, and if $d/n = \\alpha$ for a constant $\\alpha$, there would be a serious problem. I expect that in such a case, sketching methods would work better. Can the authors comment on this point?\n\n4. Dependence on regularization parameter $\\lambda$: I see that the bound on the coreset size includes a term proposional to $1 / \\lambda^2$. I expect that things would get ugly when $\\lambda$ is close to 0 (e.g., weak regularization). Can the authors comment on this point?\n\nOverall, I am uncertain whether the experiments presented in this paper are sufficient. However, I think that the main punchline of this paper is not totally about the experiments, but the theoretical guarantees the authors established for the coreset construction with sensitivity sampling for LASSO. However, I am not an expert and can only have lukewarm support for this paper, with a low confidence score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "wTenNpitqA", "reviewer": "Reviewer_FxuS", "summary": "This paper studies coresets for standard LASSO (least-squares + $\\ell_1$ penalty) using sensitivity sampling. The authors propose a sensitivity-based sampling algorithm for augmenting matrix A′ = [A −b] and localizing the function class into a residual $\\ell_2$ part and an $\\ell_1$‑penalty part, then, they apply empirical process and chaining tools to bound Gaussian diameter and metric entropy on the localized sets, and finally uses those bounds to show a coreset of size is smaller than linear regression.", "questions": "1. In Theorem 7, why $\\log(\\frac{1}{\\delta})$ is an additive term in the coreset size?\n\n2. The lasso negative result in Chhaya et al seems to be general, that is, a smaller strong coreset or sketch or summarization is impossible for any $\\lambda$, i.e., the claim is independent of how the coreset is constructed and then analyzed. Can you clarify how your result negates this claim and if it does not negate, then how do you give a strong coreset guarantee on lasso. \n\n3. How is the coreset size using the localization of the function class related to other standard regularized regressions, such as ridge (Avron et al) and modified lasso?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- Localizing the analysis into residual $\\ell_2$ and $\\ell_1$ penalty components and applying Gaussian/chaining bounds on each piece is a fresh and appropriate way to tackle the complexity introduced by the $\\ell_1$ term.", "weaknesses": "- A thorough discussion and comparison with the existing literature, such as Avron et al and Chhaya et al, is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "qKLE64b94T", "reviewer": "Reviewer_VhuG", "summary": "This paper introduces ``LASSO-Sens``, the first coreset construction method for the standard LASSO regression problem based on sensitivity sampling.\nThe key challenge in applying coreset techniques to LASSO stems from the complex, non-smooth geometry of the function space induced by the l1 penalty, which complicates standard analysis . The authors overcome this barrier by developing a localized empirical process method that effectively decomposes the function space into independent residual and l1 penalty components.\nThis new analysis yields a provably tight coreset size up to logarithmic terms. The authors confirm this bound is nearly optimal by providing a matching lower bound .\n\nExperimental results supplement the theory, demonstrating that ``LASSO-Sens`` is significantly more efficient (four times faster) than the standard LASSO solver and substantially outperforms a uniform sampling coreset baseline, all while maintaining high solution quality and sparsity.", "questions": "**Statistical Significance:** Are the results in Figures 1 and 2 (and appendix figures) from a single run or averaged over the 10 trials mentioned? Could you please add error bars (e.g., standard error or 95% CIs) to the plots to allow for a proper statistical comparison between ``LASSO-Sens`` and ``LASSO-Uniform``?\n\n**Practical Justification:** Given that ``LASSO-Uniform`` performs comparably, and sometimes better, than ``LASSO-Sens`` in the provided experiments, could you further emphasize the empirical justification for using the more complex sensitivity sampling method? The theoretical advantage is clear, but the practical advantage over this strong, simple baseline is not.\n\n**Cost of Sensitivities:** Do the runtimes reported for ``LASSO-Sens`` (e.g., in Table 1) include the pre-processing time required to compute the sensitivity scores? A clear breakdown of the (sampling vs. solving) costs for both coreset methods would be essential for a fair comparison.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "**High-Quality Presentation:** The paper is exceptionally well-written and easy to follow. The authors do an excellent job of situating their work within the existing literature, clearly motivating their approach and making the theoretical breakthroughs highly compelling.\n\n**Significant Theoretical Contribution:** The primary contribution, a comprehensive and provably near-tight coreset size bound, is a significant theoretical achievement. Overcoming the noted analytical hurdles of bounding the sampling error for the LASSO objective is a noteworthy accomplishment. *Though, I am unfamiliar with this field and defer to other reviewers to confirm the novelty of this result within the broader literature.*\n\n**Comprehensive Analysis:** The paper's theoretical claims are well-supported, complete with a matching lower bound in the relevant regime, which confirms the near-optimality of the proposed method. *Again, I defer to other reviewers to confirm that the relationship between $\\lambda$ and $d$ is common for comparing the here proven upper and lower bounds.*", "weaknesses": "The primary weakness of the paper lies in its experimental validation. While the theory is the main focus, the empirical results section feels underdeveloped and, in some cases, seems to contradict the narrative that LASSO-Sens is the superior practical approach.\n\n**Overstated Claims of Empirical Superiority:** The text emphasizes multiplicative speedups of ``LASSO-Sens`` over the full LASSO procedure. However, this comparison obscures a more critical one: the performance against the LASSO-Uniform baseline.\n\n**LASSO-Sens vs. LASSO-Uniform:** Across many of the provided plots (Figures 1, 2, and appendix figures), ``LASSO-Sens`` does not demonstrate a clear, significant advantage over ``LASSO-Uniform`` in terms of final loss . In several instances (e.g., Synthetic $\\lambda = 0.5, 1$), ``LASSO-Uniform`` even appears to achieve a better loss.\n\n**Lack of Statistical Rigor:** The plots do not include statistical error bars, and the text does not clarify if the results are from a single replication or averaged over many trials. Without this, it is impossible to determine if the small observed differences between ``LASSO-Sens`` and ``LASSO-Uniform`` are statistically significant or simply noise. Given that ``LASSO-Uniform`` is a lighter-weight approach (avoiding the sensitivity score computation), its comparable effectiveness in these experiments weakens the practical argument for the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)