Source-linked AI summary
Sampling Algorithms and Coresets for Lp Regression
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney
TL;DR
The paper addresses efficient approximation for very overconstrained ℓp regression, where solving the full problem is costly. It constructs coresets with a two-stage sampling procedure and proves a (1 + ǫ)-approximation with probability at least 0.5.
Problem
Very overconstrained ℓp regression requires efficient approximation methods because the input has many more constraints than variables.
Method
The algorithm first samples using probabilities derived from a well-conditioned basis, then uses the first-stage residual to resample constraints.
Results
A (1 + ǫ)-approximation is obtained with probability at least 0.5 when both sampling stages are run.
Takeaways & Limitations
The framework constructs coresets and applies across all p ∈ [1, ∞), including extensions to constrained, generalized, and weighted regression.
Takeaways & Limitations
The stated theorem assumes 0 < ǫ < 1/7.
Abstract
from arXiv · showhide
The Lp regression problem takes as input a matrix $A \in \Real^{n \times d}$, a vector $b \in \Real^n$, and a number $p \in [1,\infty)$, and it returns as output a number ${\cal Z}$ and a vector $x_{opt} \in \Real^d$ such that ${\cal Z} = \min_{x \in \Real^d} ||Ax -b||_p = ||Ax_{opt}-b||_p$. In this paper, we construct coresets and obtain an efficient two-stage sampling-based approximation algorithm for the very overconstrained ($n \gg d$) version of this classical problem, for all $p \in [1, \infty)$. The first stage of our algorithm non-uniformly samples $\hat{r}_1 = O(36^p d^{\max\{p/2+1, p\}+1})$ rows of $A$ and the corresponding elements of $b$, and then it solves the Lp regression problem on the sample; we prove this is an 8-approximation. The second stage of our algorithm uses the output of the first stage to resample $\hat{r}_1/ε^2$ constraints, and then it solves the Lp regression problem on the new sample; we prove this is a $(1+ε)$-approximation. Our algorithm unifies, improves upon, and extends the existing algorithms for special cases of Lp regression, namely $p = 1,2$. In course of proving our result, we develop two concepts--well-conditioned bases and subspace-preserving sampling--that are of independent interest.
1 Introduction
The paper asks whether very overconstrained ℓp regression can be solved efficiently from a small sampled subset, and answers by constructing coresets through a two-stage sampling algorithm for all p ∈ [1, ∞).
- 1 Introduction: Coresets are small input subsets whose computed solutions can approximate the full problem well.The paper applies this concept to ℓp regression.
- 1 Introduction: Overconstrained regression has n ≫ m, making general convex-programming methods prohibitive when n is large.The paper targets runtimes near-linear in n while allowing approximation.
- 1 Introduction: The two-stage sampler constructs a coreset and achieves a (1 + ǫ)-approximation; its first stage already gives a constant-factor approximation.The second stage uses the first-stage output to refine sampling probabilities.
- 1.1 Our contributions: O(36^p d^{k+1}) rows are sampled in stage one, yielding an 8-approximation, where k = max{p/2 + 1, p}.Sampling probabilities are computed before solving the smaller regression problem.
- 1.1 Our contributions: Well-conditioned bases support sampling probabilities, while subspace-preserving sampling controls variance and preserves the rank-related structure needed for relative-error guarantees.These concepts generalize ideas used in special cases such as p = 1 and p = 2.
- 1.1 Our contributions: For p = 2, the sampling complexity matches O(d^2/ǫ^2), while for p = 1 it improves O(d^{3.5}(log d)/ǫ^2) to O(d^{2.5}/ǫ^2).The framework also extends to constrained, generalized, and weighted ℓp regression.
2 Preliminaries
The preliminaries define the norms, approximation target, ε-nets, and sampling-matrix formalism used to analyze sampled ℓp regression.
- 2 Preliminaries: The vector ℓp norm has dual norm ℓq, where 1/p + 1/q = 1, and the generalized matrix p-norm sums pth powers across entries.The generalized matrix norm extends the Frobenius norm beyond p = 2 but is not vector-induced.
- 2 Preliminaries: An ε-net approximates every point in a set within ε, and a d-dimensional unit ball has an ε-net of size at most (3/ε)^d.The construction can use a maximal set of pairwise ε-separated points.
- 2 Preliminaries: A sampling matrix independently retains row i with probability p_i and rescales it by 1/p_i^(1/p), otherwise setting it to zero.Premultiplying A or b selects corresponding constraints, with expected sample size r′ = Σ_i p_i.
- 2 Preliminaries: A κ-approximation is a vector x̂ whose residual norm is at most κZ, where Z is the optimum regression value.The sampled subproblem is represented by premultiplying the data with the sampling matrix.
3 Main technical ingredients
The paper develops p-well-conditioned bases and subspace-preserving sampling to control sampling variance while preserving the column-space structure needed for relative-error ℓp regression guarantees.
- Well-conditioned bases: A p-well-conditioned basis U spans the column space and relates the p-norm of Uz to the dual-norm of coefficient vectors z.Its parameters α and β are polynomial in d and independent of the matrix dimensions n and m.
- Well-conditioned bases: Theorem 4 guarantees efficient construction of such bases, with parameter bounds depending on whether p<2, p=2, or p>2.The construction takes O(nmd + nd^5 log n) time, or O(nmd) time when p=2.
- Well-conditioned bases: The basis is constructed from a QR decomposition and a Löwner–John ellipsoid transformation, yielding U = QG^-1.The resulting basis preserves the column space while adapting the geometry to the p-norm.
- Subspace-preserving sampling: Well-conditioned bases reduce sampling variance because row norms of U define probabilities that preserve the subspace structure of A.This preservation supports relative-error approximation guarantees for regression.
- Subspace-preserving sampling: Theorem 5 gives a uniform subspace-preservation guarantee for all coefficient vectors when rows are sampled according to the basis-dependent distribution.It also implies rank(SA) = rank(A), and its sampling complexity depends on α, β, p, d, and ε.
4 The sampling algorithm
The algorithm solves very overconstrained ℓp regression through two sampling stages: an initial subspace-based sample gives a constant-factor solution, and residual-based resampling refines it to relative error.
- First-stage sampling: The algorithm first computes a p-well-conditioned basis and samples constraints using probabilities derived from its row norms.It then solves the induced ℓp regression problem on the smaller sample.
- Second-stage sampling: The second stage uses the first-stage residual to refine sampling probabilities and samples O(r1/ε^2) additional rows.The new sample is represented by a diagonal sampling matrix T and used to solve another smaller ℓp regression problem.
- First-stage sampling: 8-approximation is obtained after the first stage, with probability at least 0.6, by solving the sampled regression problem.The proof combines the sampled residual bound with the optimality of the sampled solution.
- First-stage sampling: The first-stage failure probability is bounded by 2/5 after accounting for sampling guarantees, residual concentration, and the number of sampled rows.The row-count bound uses Markov’s inequality.
- Second-stage sampling: The second-stage failure probability is less than 1/10, combining failures from the first stage, sampling theorems, lemmas, and row-count concentration.The two stages together provide the stated constant-probability relative-error guarantee.
5 Extensions
The paper extends its sampling framework beyond ordinary ℓp regression to constrained, generalized, weighted, and more broadly parameterized sampling settings. These extensions preserve (1 + ǫ)-approximation guarantees under the stated sampling procedures.
- Constrained ℓp regression: The framework extends to constrained ℓp regression over a convex set C, provided the constrained sampled problem can be solved.The resulting running time is O(nmd + nd^5 log n + φ(40r^2, m)).
- Generalized ℓp regression: Generalized ℓp regression extends the method from a target vector b to a target matrix B and an output matrix X.Second-stage probabilities use the first-stage residual matrix, and the sampled solution is a (1 + ǫ)-approximation with probability at least 1/2.
- Weighted ℓp regression: Weighted ℓp regression computes a well-conditioned basis under the weighted p-norm and adapts both sampling stages to the weights.The weighted framework defines probabilities using row weights and the first-stage residual.
- General sampling probabilities: A single-stage scheme using refined probabilities samples O(36^p d^(p+1)/ǫ^2) rows and achieves a (1 + ǫ)-approximation with probability at least 1/2.Exact probabilities may depend on the unknown optimal residual, whereas the two-stage algorithm approximates them from coarse first-stage probabilities.
B.1 Proof of Theorem 5
The proof establishes a uniform norm-preservation guarantee for sampled subspace vectors by combining tail bounds, an ε-net, and a union bound. The argument begins with fixed-vector concentration and extends it to the entire range of A.
- Fixed-vector concentration: For a fixed x, the sampled quantity ∥SAx∥p is represented as a sum of random variables with expectation ∥Ax∥p.The proof defines Xi from sampled row contributions and uses A = Uτ to relate the rows to a well-conditioned basis.
- Fixed-vector concentration: Rows sampled with probability 1 are included deterministically, so their contributions equal their expectations.This observation is used when bounding the deviation of the sampled norm.
- Tail bounds: Bernstein tail bounds control deviations after bounding the variance and maximum contribution using the sampling probabilities.The proof sets Δ from the well-conditioned-basis bound and applies upper- and lower-tail inequalities with separate γ choices.
- Tail bounds: The proof chooses γ proportional to ǫ∥Ax∥p for both tails, yielding the deviation scale needed for the norm-preservation statement.The upper-tail argument uses γ = ((1 + ǫ/4)^p − 1)∥Ax∥p, while the lower-tail argument uses γ = (1 − (1 − ǫ/4)^p)∥Ax∥p.
- Uniform extension: An ε-net of the unit subspace ball reduces the uniform guarantee to finitely many points, after which a union bound gives simultaneous control.The triangle inequality then transfers the guarantee from the net to every point in the ball and, by scaling, to all vectors in the range of A.
C Proofs for Section 4
This proof section notes that unsubscripted norms are p-norms, fixing the norm convention used in the arguments for Section 4.
- Throughout these proofs, any norm without a subscript denotes the p-norm.
C.1 Proof of Lemma 7
The lemma analyzes the sampled optimal residual through its expected p-norm and bounds the probability of a large upward deviation using Markov’s inequality.
- The expected sampled residual norm equals the optimal residual value Z.Markov’s inequality then bounds the probability that the sampled residual exceeds 3^p times the optimum.
- The probability that ∥S(AxOPT − b)∥p exceeds 3^p∥AxOPT − b∥p is at most 1/3^p.
C.2 Proof of Lemma 8
The proof establishes Lemma 8 by contraposition: residual error above 8Z implies sampled residual above 3Z, yielding the lemma.
- 8Z is the contradiction threshold for the full residual, while 3Z is the resulting lower bound for the sampled residual.The proof explicitly assumes ||A x̂_c − b|| > 8Z and derives ||S(A x̂_c − b)|| > 3Z.
- The derived inequality establishes the lemma.
C.3 Proof of Lemma 9
The proof of Lemma 9 models sampled residual contributions as random variables and applies an upper-tail bound to control their deviation from expectation.
- Xi is defined as (T_ii|A_i⋆x_OPT − b_i|)^p, and summing the Xi gives ||T(Ax_OPT − b)||_p.
- The expected sum of the sampled contributions equals ||Ax_OPT − b||_p.
- Rows with q_i = 1 contribute deterministically because Xi = E[Xi] for those rows.
- For rows with q_i < 1, the proof bounds deviations using Xi − E[Xi] ≤ Xi ≤ |A_i⋆x_OPT − b_i|^p/q_i.
- The proof sets Δ = c_p(αβ)^pZ^p/r_2 and applies an upper-tail bound with γ = ((1 + ε)^p − 1)Z^p.
- The lemma follows from the upper-tail estimate and the chosen value of r_2.
C.4 Proof of Lemma 10
The proof of Lemma 10 combines triangle inequalities, an ε-net, tail bounds, and a union bound to transfer guarantees from net points to the sampled regression solution.
- The first-stage solution satisfies ||A x̂_c − b|| ≤ 8Z, which is used in the triangle-inequality argument.
- The sampled optimizer x̂_OPT is optimal for the sampled problem, supplying the second inequality in the proof.
- The proof analyzes points in an ε-net of a ball containing A x̂_OPT and uses tail bounds to control sampled residuals at those points.
- The net-point analysis uses the lower-tail bound of Equation (9) of Theorem 13 and a union bound over at most 36^d points.
- If ||A x̂_OPT − b|| > (1 + 7ε)Z, the contrapositive derives ||T(A x̂_OPT − b)|| > (1 + ε)Z.
- The final inequality establishes the lemma.