PaperlayerView exact revision on arXiv

Source-linked AI summary

Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee

Zhao Song, Lichen Zhang

arXiv:2608.26552v1cs.DScs.LGstat.ML

TL;DR

The paper addresses coordinate-wise accuracy in randomized sketch-and-solve least-squares regression, where standard subspace embeddings primarily control residuals or global solution error. It introduces balanced Gaussian pooling, whose conditional Gaussian-regression structure yields the simultaneous ℓ∞ guarantee with nearly linear row count and efficient application.

  • Problem

    Coordinate-wise solution accuracy is not ensured by standard subspace-embedding guarantees, and a prior nearly-linear row-count argument used a fixed-vector guarantee for a sketch-dependent direction.

  • Method

    The balanced Gaussian-pooled transform combines randomized Hadamard flattening, a random permutation, and balanced disjoint Gaussian pooling.

  • Results

    m = O(ε^-2d log(d/δ)) rows suffice for the guarantee on all d coordinates simultaneously, with padded internal dimension N = eO(n + ε^-2d^3) and runtime eO(nd + ε^-2d^4).

  • Takeaways & Limitations

    Conditioning on the Hadamard-and-permutation stage makes the sketched problem an exact Gaussian regression with noise independent of the entire sketched design.

  • Takeaways & Limitations

    The construction's analysis relies on conditional row independence from disjoint pooling; isotropy alone is not a concentration statement.

Abstract

from arXiv · show

Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a smaller problem. Standard subspace embeddings guarantee that the cost of the regression is nearly preserved, but coordinate-wise accuracy of the solution is more delicate: we want the solution vector itself to be close to the optimal solution in $\ell_\infty$ norm. In particular, we want to find a vector $x'\in \mathbb{R}^d$ such that $\|x'-x^*\|_\infty\leq \fracε{\sqrt d}\cdot \|Ax^\star-b\|_2\cdot \|A^\dagger\|_{\rm op}$. Price, Song and Woodruff initiated the study of this problem and showed that the subsampled randomized Hadamard transform (SRHT) with $O(ε^{-2} d^{1+Θ(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee. A subsequent work of Song, Ye, Yin and Zhang claimed to improve the row count to $O(ε^{-2}d\log^3 n)$. Unfortunately, their proof relies on an independence assumption that does not hold in general, and we exhibit an explicit instance on which it fails. To achieve a truly nearly-linear-in-$d$ row count, we introduce a new fast, dense randomized transform, which combines a randomized Hadamard flattening, a random permutation, and balanced, disjoint Gaussian pooling. Conditioned on the Hadamard-and-permutation stage, the sketched problem becomes an exact Gaussian regression in which the noise is independent of the entire sketched design; this conditional independence is exactly what the earlier argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows, uses one Hadamard pass with a padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$, and is efficient to apply: the sketched pair $(SA, Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.

1 Introduction

The paper addresses coordinate-wise accuracy in sketched least squares, where standard subspace embeddings mainly control residual or global solution error. It introduces balanced Gaussian pooling to obtain an ℓ∞ guarantee with a nearly linear row count while preserving conditional independence for the regression analysis.

  • Motivation: Standard subspace embeddings preserve norms in a fixed subspace and support relative-error regression objectives, but primarily control residual or global solution error.Dense randomized Hadamard transforms and sparse hashing-based embeddings provide fast implementations.
  • Motivation: The SRHT achieves coordinate-wise accuracy, but its rigorous row count is superlinear in d, while a later nearly-linear claim has an invalid adaptive-direction argument.The disputed argument applies a fixed-vector guarantee to a direction containing the inverse of the random sketched Gram matrix.
  • Construction: The balanced Gaussian-pooled transform combines zero-padding, randomized Hadamard flattening, random permutation, Gaussian weights, and balanced disjoint block pooling.Pooling sums Gaussian-weighted coordinates within equal-size blocks; flattening and permutation distribute relevant subspace energy nearly evenly across blocks.
  • Construction: Conditional on Hadamard flattening and permutation, disjoint pooling produces independent Gaussian rows, with noise independent of the entire sketched design.This converts the sketched least-squares problem into an exact Gaussian regression and supplies the independence needed by the proof.
  • Main result: m = O(ϵ^-2d log(d/δ)) rows suffice for the simultaneous guarantee over all d coordinates.The fixed-direction guarantee uses m = O(ϵ^-2d log(1/δ)) rows, with failure parameter δ/d for the simultaneous result.

2 The original dependency bug

The earlier proof misused a fixed-vector coordinate-wise embedding on a direction that depends on the sketch. An explicit construction shows this dependence creates a genuine gap, even when subspace preservation and fixed-vector guarantees hold.

  • The dependency issue: The OCE definition applies only to fixed vector pairs chosen independently of the sketch.The original argument applies it to (u(S), r), but u(S) depends on S through the inverse sketched Gram matrix.
  • The dependency issue: Conditioning on column-space embedding does not fix the problem because it changes the sketch distribution while u(S) still depends on remaining randomness.A norm bound on u(S) does not make it fixed, independent, or uniformly covered by the OCE statement.
  • The gap is genuine: OSE plus fixed-vector OCE does not imply the adaptive inverse-Gram conclusion.The paper states this insufficiency as the motivation for an explicit counterexample.
  • The gap is genuine: All singular values in the counterexample lie deterministically in [0.9, 1.1], while fixed-vector OCE still holds with logarithmic dependence on 1/δ.The construction uses a random direction v in span(e2, ..., ed) and a positive-definite perturbation M(v).
  • The gap is genuine: The fixed one-dimensional regression contrast remains bounded below by an absolute constant, independent of d.This contradicts the claimed fixed-OCE conclusion, which would tend to zero as d grows.

3 Why a Gaussian diagonal in the usual position also fails

Replacing the usual Rademacher diagonal with a Gaussian diagonal does not repair the dependency problem. Gaussian imbalance can instead preserve a constant regression error with nonvanishing probability.

  • Failure of the usual placement: A Gaussian diagonal in the usual SRHT position does not repair the argument.The construction samples Hadamard rows and places Gaussian weights before the adaptive regression analysis.
  • Gaussian imbalance: The Gaussian ratio Rγ is standard Cauchy and supplies disjoint imbalance events with constant total probability.The relevant events are |Rγ| ≥ 2 and |Rγ| ≤ 1/2.
  • Gaussian imbalance: When Gaussian imbalance combines with small Hadamard correlation, the absolute regression contrast is at least 3/7.The two events are independent, so the lower bound persists with nonzero probability even for arbitrarily large m.
  • The repair: The proposed construction instead places Gaussian weights after norm flattening, while disjoint pooling supplies the independence used in the analysis.This changes the placement and organization of randomness rather than merely replacing the diagonal distribution.

4 The balanced Gaussian-pooled transform

The balanced Gaussian-pooled transform exposes randomness in stages: Hadamard flattening and permutation create balanced block geometry, then disjoint Gaussian pooling yields an exact conditional regression with independent noise and design.

  • Definition and implementation: The sketch pads the input, applies random signs and one normalized Hadamard transform, randomly permutes coordinates, multiplies by independent Gaussians, and sums balanced blocks.Its factored form is S = BDγΠFNDσJ, with blocks partitioning the padded internal dimension.
  • Definition and implementation: The solver receives only SA and Sb; no preliminary regression or postcompression of another solution is used.Although dense in the original coordinates almost surely, the transform is applied through its factorization.
  • Stage 1: balanced block geometry: After fixing Q, Hadamard flattening and permutation make every pooling block nearly isotropic for the augmented column-space and residual subspace.This produces nearly uniform block design covariance, small design–residual covariance, and controlled residual variance.
  • Stage 2: exact conditional Gaussian regression: Disjoint blocks make pooled rows independent Gaussian vectors conditional on Q, and the residualized noise vector ξ is independent of the entire design X.The score decomposes into a design-dependent fluctuation Z and Gaussian noise term X^Tξ.
  • Stage 3: concentration and assembly: Conditioning further on (Q, X) fixes M^-1 and Z, leaving only centered Gaussian noise for the variance bound.The proof combines failure events by the tower property and obtains simultaneous coordinate control by a union bound.

5 Conditional Gaussian pooling

Conditioned on the Hadamard-and-permutation stage, Gaussian pooling produces independent Gaussian sketch rows with explicit covariances. This conditional row independence is stronger than isotropy and enables the later regression decomposition.

  • The pooled rows’ exact conditional Gaussian law is the distributional property extracted from the transform.This property is established before applying the conditional regression argument.
  • Conditional on Q, pooled rows are mutually independent centered Gaussian vectors with explicit blockwise covariances.The construction uses disjoint Gaussian coordinate blocks, so each pooled row depends on an independent Gaussian block.
  • Taking T = J makes the pooled transform itself have independent centered Gaussian rows conditional on Q.The conditional expectation satisfies Eγ[S⊤S|Q] = I_n.
  • The isotropy identity alone does not provide concentration; conditional row independence drives the regression analysis.The subsequent decomposition relies on independence rather than only on Eγ[S⊤S|Q] = I_n.

6 Block geometry supplied by the randomized Hadamard transform

The randomized Hadamard stage flattens the fixed augmented regression subspace, while permutation and balanced blocks yield simultaneous block embeddings. These geometric bounds control the conditional covariances used later.

  • 6 Block geometry supplied by the randomized Hadamard transform: The Hadamard stage makes every block an accurate embedding of the fixed augmented subspace containing the columns and residual direction.The relevant subspace has dimension d + 1 after padding and normalization.
  • 6 Block geometry supplied by the randomized Hadamard transform: With probability at least 1 − δ, simultaneous block embedding holds for every block of a fixed orthonormal-column matrix W.The guarantee applies when W is independent of the randomized signs and permutation.
  • 6 Block geometry supplied by the randomized Hadamard transform: The internal dimension satisfies N = O(n + mK), with logarithmic parameter dependence absorbed into the definition of K.The bound follows from the power-of-two choice of the block size and the assumptions n ≥ d and p ≤ d + 1.
  • 6 Block geometry supplied by the randomized Hadamard transform: The blockwise covariance matrices remain close to identity, cross-covariances are small, and scalar residual covariances are controlled on Eblock.These consequences follow from the principal, rectangular, and scalar compressions in Claim 6.2.
  • 6 Block geometry supplied by the randomized Hadamard transform: The block-sum identities use the partition of coordinates and orthogonality of Q to recover the global covariance and residual orthogonality relations.In particular, the covariance sum and cross-covariance sum simplify through Q⊤Q = I_N and U⊤r = 0.

7 Conditional Gaussian regression: the adaptive-safe step

After fixing the Hadamard-and-permutation realization, the pooled least-squares problem admits an exact Gaussian regression decomposition. Its noise is independent of the entire sketched design, avoiding the adaptive-vector flaw in the earlier argument.

  • 7 Conditional Gaussian regression: the adaptive-safe step: Conditioned on Q, each observation satisfies yi = x_i⊤θ_i + ξ_i, with independent Gaussian residuals ξ_i having conditional variances τ_i^2.The design and response pairs are jointly Gaussian because they are generated from disjoint Gaussian blocks.
  • 7 Conditional Gaussian regression: the adaptive-safe step: The entire noise vector ξ is independent of the entire design matrix X conditional on Q.Joint Gaussianity plus zero cross-covariance yields this independence, including across distinct blocks.
  • 7 Conditional Gaussian regression: the adaptive-safe step: The score decomposes as X⊤y = Z + X⊤ξ, where Z is a centered design-dependent fluctuation and X⊤ξ is independent Gaussian noise conditional on Q.The cancellation identity for the blockwise covariance terms defines Z and separates the two contributions.
  • 7 Conditional Gaussian regression: the adaptive-safe step: The block covariance bounds ensure Ci is invertible and give ∥θ_i∥∥h_i∥2 ≤ 2κ∥r∥2 under κ < 1/2.Invertibility follows from the positive-definite covariance bound, while the norm estimate uses θ_i = C_i^-1 h_i.
  • 7 Conditional Gaussian regression: the adaptive-safe step: The repair permits M−1 to depend arbitrarily on X without applying a fixed-vector coordinate-wise embedding bound to a sketch-dependent direction.This directly addresses the dependence created by the inverse sketched Gram matrix.

8 Concentration of the design and centered bias

Conditional concentration controls the design Gram matrix and centered bias uniformly over good Hadamard realizations. The transform also satisfies an oblivious subspace embedding guarantee, though that property is not needed for the core lemma.

  • 8 Concentration of the design and centered bias: If m ≥ C(d + log(8/δ)), then conditional concentration controls the Gram matrix M and centered bias Z with probability at least 1 − δ/2.The bounds hold uniformly for every fixed Q satisfying the block event.
  • 8 Concentration of the design and centered bias: For each fixed unit vector u, Gaussian quadratic-form concentration yields exponentially small deviation probabilities for u⊤(M − I_d)u.A net argument upgrades the fixed-direction bound to an operator-norm bound on M − I_d.
  • 8 Concentration of the design and centered bias: The centered bias is controlled by applying conditional scalar Bernstein to independent centered Gaussian-product variables.The resulting ψ1 scale is proportional to κ∥r∥2/m before the net argument.
  • 8 Concentration of the design and centered bias: The concentration estimates are uniform over every good Q because the conditional Gaussian structure and numerical bounds depend only on the deterministic block event.Adding the two conditional failure probabilities gives δ/2.
  • 8 Concentration of the design and centered bias: m ≥ Cε^-2(d + log(1/δ)) makes the balanced Gaussian-pooled transform an (ε, δ, d)-oblivious subspace embedding.This OSE result is stated for completeness and comparison, not used in the core lemma.

9 The corrected core lemma

The corrected core lemma establishes full column rank and a coordinate-relevant bound by conditioning on the Hadamard-and-permutation variables, which restores the required Gaussian independence.

  • 9 The corrected core lemma: With probability at least 1 −δ, SU has full column rank under the lemma’s parameter choices.The lemma selects a sufficiently small universal c0 and corresponding s, N.
  • 9 The corrected core lemma: For r ≠ 0, the proof augments JU with the normalized residual direction Jr/∥r∥2 and applies the block and conditional lemmas sequentially.The conditional application of Lemma 8.1 has failure probability at most δ/2 after fixing a good Q.
  • 9 The corrected core lemma: On the success event, ∥M − I_d∥ ≤ 1/2 makes M positive definite with ∥M^-1∥ ≤ 2, while SU = X and Sr = y.These identities connect the sketch to the Gaussian regression quantities used in the lemma.
  • 9 The corrected core lemma: The proof controls bias, Gaussian noise, block embedding, and design-and-bias failures, whose failure probabilities sum to δ.The displayed decomposition includes δ/4 + δ/2 + δ/4 = δ.
  • 9 The corrected core lemma: Conditioning on (Q, X) is essential because ξ is independent of X given Q, while mixing over Q need not preserve independence.This conditional structure permits the Gaussian analysis of the second term on the measurable design-and-bias success event.
  • 9 The corrected core lemma: When r = 0, Sr = 0 makes the numerator vanish identically, and separate conditioning yields M ≻ 0 with probability at least 1 −δ.The proof applies Lemma 6.1 to JU and repeats the conditional argument with failure probability δ/4.

10 Regression consequence and desired row count

The core lemma transfers to least-squares regression through the SVD, yielding a unique sketched minimizer and simultaneous coordinate-wise guarantees after a δ/d adjustment.

  • 10 Regression consequence and desired row count: For all coordinates simultaneously, the construction replaces δ by δ/d in every parameter, including m, Λ, s, and N.This is the union-bound parameterization used for the coordinate-wise statement.
  • 10 Regression consequence and desired row count: The full-column-rank conclusion for SU implies full column rank for SA because SA = (SU)ΣV^⊤.The residual decomposition b = Ax⋆ + r supplies U^⊤r = 0 for the core lemma.
  • 10 Regression consequence and desired row count: The SVD decomposition expresses the sketched error as VΣ^-1(U^⊤S^⊤SU)^-1U^⊤S^⊤Sr.Applying the core lemma with c := Σ^-1V^⊤a bounds a fixed direction using ∥c∥2 ≤ ∥A†∥∥a∥2.

11 Running time

The one-shot estimator is efficient because the Hadamard stage dominates the application cost, while the resulting dense least-squares solve remains within the stated near-polynomial bound.

  • 11 Running time: The estimator can be computed in O(Nd log N + Tmat(d,m,d) + d^ω) arithmetic operations.This bound holds under Theorem 10.1’s assumptions and parameter choices on the success event.
  • 11 Running time: N = eO(n + ϵ^-2d^3), and applying S to A and b costs O(Nd log N).The transform is applied to d + 1 inputs, with one-vector cost O(N log N).
  • 11 Running time: The general running time is eO(nd + ϵ^-2d^4).Classical multiplication gives Tmat(d,m,d) = eO(ϵ^-2d^3), while d^ω = O(d^3).
Loading 2608.26552v1…