A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee

Given a matrix A∈ ℝn× d and a vector b∈ ℝn, we consider the regression problem with ℓ_∞ guarantees: finding a vector x'∈ ℝd such that |x'-x^*|_∞ ≤ fracε√d· |Ax^*-b|2· |A^dagger| where x^*=argminx∈ ℝd|Ax-b|2. One popular approach for solving such ℓ2 regression problem is via sketching: picking a structured random matrix S∈ ℝm× n with mll n and SA can be quickly computed, solve the ``sketched'' regression problem argminx∈ ℝd |SAx-Sb|2. In this paper, we show that in order to obtain such ℓ_∞ guarantee for ℓ2 regression, one has to use sketching matrices that are dense. To the best of our knowledge, this is the first user case in which dense sketching matrices are necessary. On the algorithmic side, we prove that there exists a distribution of dense sketching matrices with m=ε-2dlog3(n/δ) such that solving the sketched regression problem gives the ℓ_∞ guarantee, with probability at least 1-δ. Moreover, the matrix SA can be computed in time O(ndlog n). Our row count is nearly-optimal up to logarithmic factors, and significantly improves the result in [Price, Song and Woodruff, ICALP'17], in which a super-linear in d rows, m=Omega(ε-2d1+γ) for γ=Theta(√fracloglog nlog d) is required. We also develop a novel analytical framework for ℓ_∞ guarantee regression that utilizes the Oblivious Coordinate-wise Embedding (OCE) property introduced in [Song and Yu, ICML'21]. Our analysis is arguably much simpler and more general than [Price, Song and Woodruff, ICALP'17], and it extends to dense sketches for tensor product of vectors.