## Abstract

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, d^{O(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 log^{3} n + (dp^{2})^{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.

Original language | English (US) |
---|---|

State | Published - 2022 |

Event | 10th International Conference on Learning Representations, ICLR 2022 - Virtual, Online Duration: Apr 25 2022 → Apr 29 2022 |

### Conference

Conference | 10th International Conference on Learning Representations, ICLR 2022 |
---|---|

City | Virtual, Online |

Period | 4/25/22 → 4/29/22 |

## ASJC Scopus subject areas

- Language and Linguistics
- Computer Science Applications
- Education
- Linguistics and Language