CS Paper Radar

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

Zhao Song, Lichen Zhang

cs.DS cs.LGstat.ML ·submitted 2026-08-27 02:43 UTC · v2

Abstract

Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a much smaller, randomly projected problem. While standard subspace embeddings nearly preserve the regression cost, coordinate-wise accuracy is more delicate: rather than the objective value, we want the solution vector itself to be close to the optimum in $\ell_\infty$ norm. Specifically, we seek $x'\in\mathbb{R}^d$ with $\|x'-x^\star\|_\infty\leq\fracε{\sqrt d}\|Ax^\star-b\|_2\|A^\dagger\|_{\mathrm{op}}$, where $A\in\mathbb{R}^{n\times d}$ is the design matrix, $b\in\mathbb{R}^n$ the label vector, $x^\star$ the optimal solution and $A^\dagger$ the pseudo-inverse of $A$. Price, Song and Woodruff introduced this problem and claimed that the subsampled randomized Hadamard transform (SRHT) with $O(ε^{-2}d^{1+Θ(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee; we point out a gap in the proof. Song, Ye, Yin and Zhang later claimed $O(ε^{-2}d\log^3 n)$ rows, but 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 combining 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 whose noise is independent of the entire sketched design, exactly what Song, Ye, Yin and Zhang's argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows, using one Hadamard pass with padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$. It is also efficient to apply: $(SA,Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.

Comment
Improve presentation and add more discussions on prior work. Abstract shortened to meet arxiv requirement

Closest papers

Nearest neighbours by meaning across the whole index.

Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers

cs.LG math.OCmath.ST ·2026-10-11 ·Faris Chaudhry, Anthea Monod, Keisuke Yano
similarity 0.63
Abstract · 51 pages, 4 figures

Hoffman constants quantify the distance to the solution set of a polyhedral system in terms of its residual; they control error bounds, geometric conditioning, the convergence rate of first-order iterative algorithms, and the stability of regression estimators to target perturbations. Despite their importance, explicit values of Hoffman constants are rarely available due to their computational complexity. In this paper, we derive explicit bounds on the Hoffman constant for a class of structured polyhedral systems arising in sparse regularization. We show that the constants admit a decomposition into spectral, geometric, and interaction components, which together determine their scaling behavior. This framework explains the gap between worst-case dimension-dependent bounds and the favorable conditioning observed empirically in structured problems. As a primary application, we analyze $\ell_1$-regularized least squares, demonstrating that the effective constants depend on low-dimensional active subspaces rather than the ambient dimension. We then extend to the elastic net and adaptive $\ell_1$-regularized formulations, demonstrating how the underlying optimization geometry is altered by the $\ell_2$ penalty and reweighting scheme. Furthermore, we relate our results to classical statistical assumptions and show that the restricted eigenvalue condition bounds only the primal curvature of the active set, leaving the dual interaction geometry unconstrained and is thus insufficient alone for fast theoretical convergence rates. We further show standard $\ell_\infty$ coherence conditions do not yield dimension-independent Euclidean bounds to close this gap. Our theoretical results show that Hoffman constants admit explicit, interpretable forms in structured regression settings and, in practice, provide actionable tools for post-hoc feature pruning and a priori optimal hyperparameter selection.

0.28

Faster Linear Programming with $\sqrt{\mathrm{rank}}$ Linear System Solves

cs.DS math.OC ·2026-09-25 ·Zhao Song
similarity 0.63
Abstract

Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $ε$ using $O(\sqrt n\log^{13}m\cdot\log(mU/ε))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagonal matrices $\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\log^{13}m$ factor is an interesting future direction. Given an interior point and a finite certified magnitude bound $U$, we give an algorithm that uses $O(\sqrt n\log^{4}m\cdot\log(mU/ε))$ solves of such linear systems, improving the Lee--Sidford bound by a factor of $\log^{9}m$. We conjecture that $O(\sqrt n\log(mU/ε))$ such linear-system solves suffice.

0.26

Hutch#: Optimal non-adaptive Frobenius norm estimation

cs.DS math.NA ·2026-09-23 ·Tyler Chen, Diana Halikias, Christopher Musco, David Persson
theory similarity 0.63
Abstract

The Girard--Hutchinson estimator provides an extremely simple randomized estimate of the Frobenius norm of a matrix $A$ that can only be accessed implicitly via matrix-vector products. In particular, if $Ω$ is a random Gaussian matrix with $r = O(1/\varepsilon^2)$ columns, than $\frac{1}{r}\|AΩ\|_F^2$ provides a $(1\pm \varepsilon)$ multiplicative approximation to $\|A\|_F^2$ with high probability. In this work, we introduce a closely related estimator, given by \begin{align*} {\frac{1}{r}\|AΩ\|_F^2 + \frac{1}{r}\|Ψ^T A\|_F^2 - \frac{1}{r^2}\|Ψ^T AΩ\|_F^2}, \end{align*} where $Ψ$ is a second, independent random Gaussian matrix with $r$ columns. We prove that this estimator yields a $(1\pm\varepsilon)$ multiplicative approximation to $\|A\|_F^2$ when $r = O(1/\varepsilon)$, a quadratic improvement over Girard--Hutchinson. This dependence on $\varepsilon$ is optimal. Our method, which we call Hutch# (pronounced ``Hutch sharp''), matches the complexity of the Hutch++ algorithm [Meyer, Musco, Musco, Woodruff, 2021]. However, unlike Hutch++, Hutch# uses only \textit{non-adaptive} matrix-vector products with $A$ and $A^T$ and requires no orthogonalization or other advanced linear algebra steps. Thus, Hutch# combines the simplicity of the Girard--Hutchinson estimator and the optimal query complexity of Hutch++.

0.15

Improved Leverage Score Sampling for Constrained Active Linear Regression

cs.LG stat.MLmath.NA ·2026-11-18 ·Aarshvi Gajjar, Syamantak Kumar, Aditya Makkar, Christopher Musco, Joey Zhou
top venuetheory similarity 0.59
Abstract · To appear in NeurIPS 2026 (Spotlight)

In this paper we study active learning for constrained linear regression. Given a design matrix $A\in\mathbb{R}^{n\times d}$, a constraint set $C\subseteq\mathbb{R}^d$, and query access to $b\in\mathbb{R}^n$, we seek an approximate solution to $\min_{x\in C}\|Ax-b\|_2^2$ using as few queries as possible. This problem arises in many scientific and engineering applications, and randomized leverage score sampling provides a powerful method to solve it. However, existing leverage score methods ignore the constraint or encode it through ridge regularization, suffering unfavorable query complexity for anisotropic constraint sets. We propose ellipsoid-regularized leverage scores, where we approximate the constraint set by an outer ellipsoid and use its shape matrix to bias sampling toward directions that matter under the constraint geometry. We prove that the query complexity is governed by an anisotropic effective dimension $d_{\text{eff}}(C)\le d$. With appropriate parameters, $O(d_{\text{eff}}(C)\log d/\varepsilon^2)$ queries suffice to return a point in $C$ with objective value at most $(1+\varepsilon)$ times the optimum. This bound can substantially improve on the standard leverage-score bound, since anisotropic constraints can make $d_{\text{eff}}(C)$ much smaller than $d$. For convex constraints, we improve the dependence on $\varepsilon$ from $1/\varepsilon^2$ to $1/\varepsilon$. We also prove two lower bounds: first, the $d/\varepsilon^2$ dependence is unavoidable without convexity assumptions on $C$, and second, in some regimes, the effective dimension dependence $d_{\mathrm{eff}}(C)/\varepsilon$ is necessary for ellipsoidal constraints. Experiments on synthetic regression problems and a parametric heat conduction problem show lower regression error than standard baselines for similar query budget.

0.36

Convex Regression at Scale: Geometry-Preserving Constraint Sparsification

cs.LG stat.MLmath.OC ·2026-11-01 ·Anish Senapati, Jose Blanchet
similarity 0.58
Abstract · 37 pages, 4 figures

Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has $O(n^2)$ supporting-hyperplane constraints creating a computational bottleneck as the sample size $n$ increases. We study a $K$-nearest-neighbor (KNN) localized relaxation for convex regression where we for each sample, we only maintain the $K$ nearest hyperplane constraints. Under mild regularity conditions, we establish statistical guarantees for our modified estimator in every fixed dimension $d\ge2$. In particular, for $d>4$, the population risk of our modified problem can be shown to have equivalent convergence rates as the original least square convex regression estimator of $\widetilde O(n^{-2/d})$ using neighborhoods sizes (i.e. $K=K_n$) of order $\widetilde O(n^{2(d-1)/(2d-1)})$ for general convex functions and $\widetilde O(n^{(d+1)/(d+2)})$ for strongly convex functions. To corroborate our theory, we implement iterative optimization methods to compare the prediction accuracy of the KNN relaxation with those of the full estimator across synthetic convex benchmarks. Our experiments demonstrate that KNN prediction risk approaches the full-estimator prediction risk at neighborhood sizes matching the theoretical scale.

0.35

Inapproximability of L1->L2 Subspace Distortion

cs.CC ·2026-11-17 ·Vijay Bhattiprolu
similarity 0.58
Abstract

We show, assuming NP is not contained in randomized quasipolynomial time, almost polynomial factor inapproximability for maximizing the $\ell_2/\ell_1$ ratio over a real subspace -- a problem also known as subspace distortion. This is a central problem in compressed sensing but also has connections to many areas such as real error correcting codes, dictionary learning, hypercontractive operator norms, small-set expansion, quantum information and random matrix theory. Distortion seems to be at the heart of building inapproximability theory for continuous optimization. Extending our results to the case of $\ell_2/\ell_p$ for all $p<2$ would lead to a near characterization of the convex sets over which one can efficiently and approximately maximize an arbitrary quadratic form. A recurring obstruction appears in hardness considerations of distortion -- how does one use a sparsity measure to test proximity to an exponential sized discrete set over the reals? This issue also appears in a host of other problems that involve measures of sparsity, shortness, density or expansion. We believe hardness of distortion is an intermediate step to understanding the complexity of small-set expansion and quantum separability, both of which are important directions of research. The main insight in our hardness reduction is the construction of a randomized affine linear map $T:\mathbb{R}^n\to \mathbb{R}^m$ such that the distortion of $Tx$ measures proximity to the hypercube $\{\pm 1\}^{n}$. Crucial to our construction is subsampling $x$ at *all* dyadic sample sizes, which gives an inverse polylogarithmic gap. This is a highly non-local tester, and thus departs from the local testing paradigm in PCP theory. Our reduction is also quite succinct, and so it suggests a rather simple distribution of subspaces for which approximately finding a planted sparse vector is intractable.

0.31

Recovering linear images of sparse signals from indirect observations

cs.IT stat.MLcs.LGmath.OC ·2026-09-05 ·Anatoli Juditsky, Arkadi Nemirovski
hot direction similarity 0.58
Abstract

In this paper, we develop and analyze techniques for recovering a linear image $Bx$ of an unknown signal $x$ from indirect noisy observation $ω=Ax+ξ$. It is {\em a priori} known that $x\in \cX$, a given convex compact set, and that $x$ is $s$-sparse---has at most $s$ nonvanishing entries. The proposed estimates belong to a large family of recovery routines by $\ell_1$-minimization. However, unlike the classical result describing performance of such estimates, we do not make any special (and hard to check) assumptions about the sensing matrix $A$ such as nullspace or Restricted Isometry condition and the like. As a consequence, parameters of the estimates and the upper bounds on their risks are not available in a closed analytic form, but are delivered instead by efficient computation as solutions to explicit convex optimization problems.

0.26

Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing

cs.IT math.FAmath.NA ·2026-08-23 ·Mingxuan Sun, Zhiqiang Xu
theory similarity 0.57
Abstract

In this paper we focus on the stability of positive semidefinite matrix sensing maps $Φ_{\mathcal{A}}=(\langle A_i,X\rangle)_{i=1}^m$ where $A_i\succeq 0$, $X\succeq0$ and $\operatorname{rank}(X)\le r$. We introduce the bi-Lipschitz constants of $Φ_{\mathcal{A}}$ and define the global condition numbers as the ratio of upper and lower Lipschitz constants. We give deterministic universal lower bounds for these condition numbers that depend only on the rank $r$ and on the underlying field. We then show that rank-one Gaussian measurements asymptotically attain these bounds, except for the operator-norm condition number over $\mathbb R$ when $r=1$. For this exceptional case, we establish a sharper universal lower bound and prove its asymptotic sharpness. As an application, we derive stability guarantees for an $\ell_1$-residual PhaseLift-type estimator at the optimal sampling scale. These results identify the intrinsic limits of conditioning in positive semidefinite matrix sensing and connect these limits to stable low-rank recovery.

0.15