TY - CONF
T1 - FAST REGRESSION FOR STRUCTURED INPUTS
AU - Meyer, Raphael A.
AU - Musco, Cameron
AU - Musco, Christopher
AU - Woodruff, David P.
AU - Zhou, Samson
N1 - Funding Information:
Cameron Musco was supported by NSF grants 2046235 and 1763618, and an Adobe Research grant. David P. Woodruff and Samson Zhou were supported by National Institute of Health grant 5401 HG 10798-2 and a Simons Investigator Award. Christopher Musco and Raphael Meyer were supported by NSF grant 2045590 and DOE Award DE-SC0022266.
Publisher Copyright:
© 2022 ICLR 2022 - 10th International Conference on Learning Representationss. All rights reserved.
PY - 2022
Y1 - 2022
N2 - We study the ℓp regression problem, which requires finding x ∈ ℝd that minimizes ǁAx − bǁp for a matrix A ∈ ℝn×d and response vector b ∈ ℝn. There has been recent interest in developing subsampling methods for this problem that can outperform standard techniques when n is very large. However, all known subsampling approaches have run time that depends exponentially on p, typically, dO(p), which can be prohibitively expensive. We improve on this work by showing that for a large class of common structured matrices, such as combinations of low-rank matrices, sparse matrices, and Vandermonde matrices, there are subsampling based methods for ℓp regression that depend polynomially on p. For example, we give an algorithm for ℓp regression on Vandermonde matrices that runs in time O(n log3 n + (dp2)0.5+ω · polylog n), where ω is the exponent of matrix multiplication. The polynomial dependence on p crucially allows our algorithms to extend naturally to efficient algorithms for `∞ regression, via approximation of ℓ∞ by ℓO(log n). Of practical interest, we also develop a new subsampling algorithm for `p regression for arbitrary matrices, which is simpler than previous approaches for p ≥ 4.
AB - We study the ℓp regression problem, which requires finding x ∈ ℝd that minimizes ǁAx − bǁp for a matrix A ∈ ℝn×d and response vector b ∈ ℝn. There has been recent interest in developing subsampling methods for this problem that can outperform standard techniques when n is very large. However, all known subsampling approaches have run time that depends exponentially on p, typically, dO(p), which can be prohibitively expensive. We improve on this work by showing that for a large class of common structured matrices, such as combinations of low-rank matrices, sparse matrices, and Vandermonde matrices, there are subsampling based methods for ℓp regression that depend polynomially on p. For example, we give an algorithm for ℓp regression on Vandermonde matrices that runs in time O(n log3 n + (dp2)0.5+ω · polylog n), where ω is the exponent of matrix multiplication. The polynomial dependence on p crucially allows our algorithms to extend naturally to efficient algorithms for `∞ regression, via approximation of ℓ∞ by ℓO(log n). Of practical interest, we also develop a new subsampling algorithm for `p regression for arbitrary matrices, which is simpler than previous approaches for p ≥ 4.
UR - http://www.scopus.com/inward/record.url?scp=85146178642&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85146178642&partnerID=8YFLogxK
M3 - Paper
AN - SCOPUS:85146178642
T2 - 10th International Conference on Learning Representations, ICLR 2022
Y2 - 25 April 2022 through 29 April 2022
ER -