TY - GEN
T1 - Optimal Sketching Bounds for Sparse Linear Regression
AU - Mai, Tung
AU - Munteanu, Alexander
AU - Musco, Cameron
AU - Rao, Anup B.
AU - Schwiegelshohn, Chris
AU - Woodruff, David P.
N1 - Publisher Copyright:
Copyright © 2023 by the author(s)
PY - 2023
Y1 - 2023
N2 - We study oblivious sketching for k-sparse linear regression under various loss functions. In particular, we are interested in a distribution over sketching matrices S ∈ Rm×n that does not depend on the inputs A ∈ Rn×d and b ∈ Rn, such that, given access to SA and Sb, we can recover a k-sparse x̃ ∈ Rd with ∥Ax̃ - b∥f ≤ (1 + ε) mink-sparse x∈Rd ∥Ax - b∥f. Here ∥ · ∥f : Rn → R is some loss function - such as an ℓp norm, or from a broad class of hinge-like loss functions, which includes the logistic and ReLU losses. We show that for sparse ℓ2 norm regression, there is a distribution over oblivious sketches with m = Θ(k log(d/k)/ε2) rows, which is tight up to a constant factor. This extends to ℓp loss with an additional additive O(k log(k/ε)/ε2) term in the upper bound. This establishes a surprising separation from the related sparse recovery problem, which is an important special case of sparse regression, where A is the identity matrix. For this problem, under the ℓ2 norm, we observe an upper bound of m = O(k log(d)/ε + k log(k/ε)/ε2), showing that sparse recovery is strictly easier to sketch than sparse regression. For sparse regression under hinge-like loss functions including sparse logistic and sparse ReLU regression, we give the first known sketching bounds that achieve m = o(d) showing that m = O(µ2k log(µnd/ε)/ε2) rows suffice, where µ is a natural complexity parameter needed to obtain relative error bounds for these loss functions. We again show that this dimension is tight, up to lower order terms and the dependence on µ. Finally, we show that similar sketching bounds can be achieved for LASSO regression, a popular convex relaxation of sparse regression, where one aims to minimize ∥Ax - b∥22 + λ∥x∥1 over x ∈ Rd. We show that sketching dimension m = O(log(d)/ (λε)2) suffices and that the dependence on d and λ is tight.
AB - We study oblivious sketching for k-sparse linear regression under various loss functions. In particular, we are interested in a distribution over sketching matrices S ∈ Rm×n that does not depend on the inputs A ∈ Rn×d and b ∈ Rn, such that, given access to SA and Sb, we can recover a k-sparse x̃ ∈ Rd with ∥Ax̃ - b∥f ≤ (1 + ε) mink-sparse x∈Rd ∥Ax - b∥f. Here ∥ · ∥f : Rn → R is some loss function - such as an ℓp norm, or from a broad class of hinge-like loss functions, which includes the logistic and ReLU losses. We show that for sparse ℓ2 norm regression, there is a distribution over oblivious sketches with m = Θ(k log(d/k)/ε2) rows, which is tight up to a constant factor. This extends to ℓp loss with an additional additive O(k log(k/ε)/ε2) term in the upper bound. This establishes a surprising separation from the related sparse recovery problem, which is an important special case of sparse regression, where A is the identity matrix. For this problem, under the ℓ2 norm, we observe an upper bound of m = O(k log(d)/ε + k log(k/ε)/ε2), showing that sparse recovery is strictly easier to sketch than sparse regression. For sparse regression under hinge-like loss functions including sparse logistic and sparse ReLU regression, we give the first known sketching bounds that achieve m = o(d) showing that m = O(µ2k log(µnd/ε)/ε2) rows suffice, where µ is a natural complexity parameter needed to obtain relative error bounds for these loss functions. We again show that this dimension is tight, up to lower order terms and the dependence on µ. Finally, we show that similar sketching bounds can be achieved for LASSO regression, a popular convex relaxation of sparse regression, where one aims to minimize ∥Ax - b∥22 + λ∥x∥1 over x ∈ Rd. We show that sketching dimension m = O(log(d)/ (λε)2) suffices and that the dependence on d and λ is tight.
M3 - Article in proceedings
AN - SCOPUS:85165171261
T3 - Proceedings of Machine Learning Research
SP - 11288
EP - 11316
BT - Proceedings of The 26th International Conference on Artificial Intelligence and Statistics
PB - PMLR
T2 - 26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023
Y2 - 25 April 2023 through 27 April 2023
ER -