The Condition-Number Barrier in Sparse Least Squares

The Condition-Number Barrier in Sparse Least Squares Honghao Lin∗

Vahab Mirrokni†

David P. Woodruff‡

arXiv:2608.02588v1 [cs.DS] 3 Aug 2026

Abstract In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Concretely, for every fixed γ ∈ (0, 1], there is no randomized polynomial-time algorithm that, with probability at least 2/3, returns a vector x such that, writing s = ∥x∥0 ,   1−γ ∥Ax − b∥22 ≤ min ∥Az − b∥22 + ε and s = O k κs+k , ∥z∥0 ≤k

where κr is the restricted condition number at sparsity level r. The result holds even on rational instances with A of full column rank. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.

1

Introduction

Sparse convex optimization seeks a vector with few nonzero coordinates and small objective value. Given a target sparsity k and an accuracy ε > 0, the bicriteria goal is to attain an objective value no greater than the best k-sparse value plus ε, while allowing the output to use more than k coordinates. We study this question for the least-squares objective Q(x) = ∥Ax − b∥22 ,

(1.1)

Even the closely related task of finding the sparsest vector subject to a prescribed residual tolerance is NP-hard [Nat95]. The central question here is how much additional support suffices for an efficient additive approximation. The relevant structural parameter is the restricted condition number. For least squares, let κr denote the ratio between the maximum and minimum values of ∥Ah∥22 over r-sparse unit vectors h. Suppressing the sparsity level in the notation, earlier analyses gave either a support bound linear in κ with an additional logarithmic dependence on the desired accuracy [Nat95, SSSZ10], or an accuracy-independent O(kκ2 ) bound [SSSZ10, JTK14]. Axiotis and Sviridenko introduced Adaptively Regularized Hard Thresholding and obtained an accuracy-independent O(kκ) bound. Their algorithm is randomized, and the guarantee holds with high probability [AS21]. They later gave a deterministic adaptive-regularization method with the same O(kκ) support dependence and an improved runtime [AS22]. ∗

Google Research, Carnegie Mellon University / Texas A&M University. honghaol3010@gmail.com Google Research. mirrokni@google.com ‡ Google Research and Carnegie Mellon University. dpwoodru@gmail.com †

1

Axiotis and Sviridenko discuss in Section 5.1 of their paper [AS21] a construction that appears in Appendix B of the full version of Foster, Karloff, and Thaler [FKT15]. They interpret it as an obstruction matching the linear dependence on κ for several greedy and hard-thresholding methods. The construction is algorithm-specific and does not rule out a different polynomial-time algorithm. Axiotis and Sviridenko therefore formulated the remaining question as Conjecture 27 [AS21]. Writing γ for the proposed improvement in the condition-number exponent, the conjecture rules out any polynomial-time algorithm that retains the additive objective guarantee while returning a vector whose sparsity s satisfies   s = O kκ1−γ (1.2) s+k . The occurrence of s on both sides is intentional: the restricted condition number is evaluated at the combined target and output support sizes.

1.1

Our result

We establish this general computational barrier conditional on the randomized exact-volume SmallSet Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12], as formalized in Hypothesis 2.1. The conclusion covers arbitrary randomized polynomial-time algorithms. The hardness holds even when A and b have rational entries and A has full column rank. The hypothesis asks one to distinguish a regular graph containing a low-expansion set of one fixed volume from a graph in which every set of exactly that volume has expansion close to one. This exact-volume YES/NO structure is the SSE(η, δ) formulation of Raghavendra, Steurer, and Tulsiani [RST12], where the prescribed cardinality is k = δn. Our hypothesis considers randomized hardness on rational weighted regular graphs. The exact-size character is central to the proof: the core argument derives the needed control over arbitrary returned supports from expansion at the single target volume. The formal statement below makes the hidden constant in Equation (1.2) explicit. As usual, that constant may depend on the algorithm and on the fixed exponent γ, but not on the input. Theorem 1.1 (Main theorem). Assume the randomized weighted exact-volume Small-Set Expansion Hypothesis stated in Hypothesis 2.1. Fix constants γ ∈ (0, 1] and C ≥ 1. There is no randomized algorithm, with running time polynomial in the binary encoding length of (A, b, k, ε) and in 1/ε, that, given A ∈ Qm×n , b ∈ Qm , k ∈ {1, . . . , n}, and ε ∈ Q>0 , with A of full column rank, returns x ∈ Qn such that, with probability at least 2/3, writing s = ∥x∥0 , both ∥Ax − b∥22 ≤ min ∥Az − b∥22 + ε,

(1.3)

s ≤ Ck κ1−γ s+k .

(1.4)

∥z∥0 ≤k

Consequently, conditional on this hypothesis, the algorithmic guarantee ruled out by Conjecture 27 of Axiotis and Sviridenko is impossible for every fixed 0 < γ ≤ 1. Moreover, for each fixed (C, γ), there is a constant KC,γ < ∞ such that the hard instances may be chosen to satisfy κr (A) ≤ KC,γ

for every r,

and every row of A has at most two nonzero entries. The feasibility premise in Conjecture 27 [AS21] is automatic for the instances in our reduction. Because A has full column rank, Q is coercive and attains its minimum over the finite union of 2

coordinate subspaces {z : ∥z∥0 ≤ k}. Let z ⋆ be such a minimizer and write r⋆ = ∥z ⋆ ∥0 . Then r⋆ ≤ k ≤ Ckκ1−γ r⋆ +k . The second inequality follows from C ≥ 1, κr⋆ +k ≥ 1, and 1 − γ ≥ 0. Thus z ⋆ itself satisfies both guarantees.

1.2

Proof overview

Let G be a rational weighted regular graph with n vertices. Normalize its weighted degree to one, and let LG be its Laplacian. We choose a constant c > 0 later as a function only of the fixed pair (C, γ) and set µ = c. Consider FG (x) = x⊤ LG x + µ∥x∥22 − 21⊤ x.

(1.5)

Here 1 ∈ Rn is the all-ones vector. To expose the least-squares structure, first work over R. For √ each non-loop edge {u, v} of weight wuv , add the edge row wuv (eu − ev )⊤ with response zero. For each vertex v, add the ridge row and response √

1 √ , µ

µ e⊤ v,

respectively. Thus every edge row has two nonzero entries and every ridge row has one. Expanding the squared residuals gives  X X √ 1 2 2 2 ∥Ax − b∥2 = wuv (xu − xv ) + µ xv − √ µ u<v v∈V (1.6) n n ⊤ 2 ⊤ = x LG x + µ∥x∥2 − 21 x + = FG (x) + . µ µ ⊤B If BG denotes the block of edge rows, then BG G = LG , while the ridge rows contribute µI. Therefore A⊤ A = LG + µI.

Since LG is positive semidefinite and µ > 0, this matrix is positive definite, so A has full column rank. Moreover, the spectrum of the Laplacian of a weighted graph of degree one lies in [0, 2] [Chu97]. Thus, for every r and every r-sparse unit vector h, µ ≤ ∥Ah∥22 = h⊤ (LG + µI)h ≤ 2 + µ. By the definition of κr , these bounds imply κr ≤

2+µ 2 =1+ µ c

for every sparsity level r. The square roots above need not be rational. In Lemma 3.2, each edge or ridge coefficient is instead realized as a sum of squares of rationals. The resulting rows have the same supports, so this replacement preserves ∥Ax − b∥22 , A⊤ A, and the property that every row has at most two nonzero entries. We next establish a gap between the two cases of the SSE instance. Write ΦG (S) for the normalized edge expansion of S. The parameter η specifies the SSE promise: in the YES case, G contains a set S ⋆ of size k with ΦG (S ⋆ ) ≤ η, whereas in the NO case every set of size k has 3

expansion at least 1 − η. In the YES direction (completeness), consider the k-sparse vector α1S ⋆ , ⋆ where 1S ⋆ is the indicator of S ⋆ . Since 1⊤ S ⋆ LG 1S ⋆ = kΦG (S ) ≤ kη and µ = c,
FG (α1S ⋆ ) ≤ k (η + c)α2 − 2α . The right-hand side is minimized at α = 1/(η + c), giving min FG (x) ≤ −

∥x∥0 ≤k

k . η+c

In the NO direction (soundness), assume that G is a NO instance and let S = supp(x) be the support returned on a run in which the hypothetical algorithm satisfies its guarantees. The support guarantee and the uniform condition-number bound imply 1−γ |S| ≤ Ckκ1−γ ≤ Lk |S|+k ≤ Ck(1 + 2/c)

for a suitable constant L. We prove a lower bound on minsupp(y)⊆S FG (y) for every such S. The difficulty is that |S| need not equal k and may be larger, whereas the exact-size SSE NO promise applies only to sets of size exactly k. It therefore cannot be applied directly to S. Fix a nonempty S and take η = θ2 , with θ > 0 chosen sufficiently small later. We decompose S into a nonexpanding core U and an expanding residual W . Initialize U = ∅ and R = S. Whenever some nonempty X ⊆ R satisfies wG (X, R \ X) + wG (X, V \ S) < (1 − θ)|X|, move X from R to U . At termination, set W = R. Summing the removal inequalities shows that ΦG (U ) < 1 − θ when U = ̸ ∅, while the absence of another removable set means that W has modified Dirichlet expansion at least 1 − θ when W ̸= ∅. The exact-size NO promise nevertheless forces U to be small. On the sufficiently large instances used in the reduction, k ≥ 2. Suppose first that |U | > k. For a uniformly random k-element subset T of U , the low expansion of U and the bound |U | ≤ Lk give EΦG (T ) < 1 −

θ < 1 − θ2 = 1 − η, 2L

where the second inequality follows by choosing θ < 1/(2L). This contradicts the NO promise, so |U | ≤ k. When U = ̸ ∅, pad U to a set T of size exactly k. The added vertices contribute at most one unit of boundary weight each, and hence 1 − η ≤ ΦG (T ) ≤

|U |ΦG (U ) + k − |U | . k

Rearranging gives
|U | 1 − ΦG (U ) ≤ ηk. Since η = θ2 and 1 − ΦG (U ) > θ, the preceding inequality gives |U | < θk. When W = ̸ ∅, a Dirichlet Cheeger inequality [Chu07] turns its modified expansion into the spectral bound 1 λmin (L′W ) ≥ (1 − θ)2 , 2 where L′W retains the edges inside W and the boundary contributions from W to V \ S, but not the edges between U and W . 4

Deleting these edges can only decrease the Laplacian quadratic form and decouples the coordinates in U from those in W . For a positive-definite matrix M ,
min y ⊤ M y − 21⊤ y = −1⊤ M −1 1. y

Applying this identity to the two blocks, using the fact that the core block is bounded below by µI and that the residual block is bounded below by (λmin (L′W ) + µ)I, gives the following bound, with the W -term omitted when W = ∅: min supp(y)⊆S

|U | |W | − µ λmin (L′W ) + µ Lk θk ≥− − 1 . 2 c 2 (1 − θ) + c

FG (y) ≥ −

The second line uses |U | < θk, |W | ≤ Lk, and µ = c. Finally, Lemma 5.1 chooses c, L, θ so that C(1 + 2/c)1−γ ≤ L,

θ<

1 , 2L

Γ(c, L, θ) > 0,

where Γ is the difference between the completeness and soundness coefficients above. The resulting least-squares gap is ∆G = kΓ(c, L, θ). Calling the hypothetical algorithm with εG = ∆G /3 would distinguish the YES and NO cases with probability at least 2/3, contradicting Hypothesis 2.1.

1.3

Related work

For sparse convex optimization, early algorithms either retained a dependence on the requested accuracy or gave accuracy-independent support bounds of order kκ2 [Nat95, SSSZ10, JTK14]. Axiotis and Sviridenko introduced Adaptively Regularized Hard Thresholding and obtained an O(kκ) support bound with high probability, removing both the accuracy dependence and the extra factor of κ [AS21]. Their later deterministic variant retains the O(kκ) support guarantee, improves the runtime, and does not require prior knowledge of the optimal value or sparsity [AS22]. Classical worst-case hardness results for sparse regression are not parameterized by the restricted condition number. Natarajan proved that it is NP-hard to find the sparsest vector attaining a prescribed residual tolerance [Nat95]. Foster, Karloff, and Thaler introduced a bicriteria (g, h)sparse-regression formulation that simultaneously relaxes support and prediction error [FKT15]. For an m × p design, under the assumption NP ⊈ BPTIME(N polylog N ), where N denotes the input length, their main result shows that for any fixed positive constants δ, C1 , C2 there are functions 1−δ g(p) ∈ 2Ω(log p) and h(m, p) ∈ Ω(pC1 m1−C2 ) for which no quasipolynomial-time randomized algorithm exists. Under the Biregular Projection Games Conjecture together with NP ⊈ BPP, they obtain analogous hardness against randomized polynomial-time algorithms with g(p) ∈ pΩ(1) , and they establish corresponding results for a noisy statistical formulation. These theorems give strong general bicriteria inapproximability, but do not calibrate the hardness to κ. Separate from those complexity-theoretic results, Appendix B of the full version of Foster, Karloff, and Thaler gives a concrete bad instance for forward stepwise selection [FKT15]. In Section 5.1, Axiotis and Sviridenko interpret this construction as a linear-in-κ barrier for OMP, OMPR, IHT, and Partial Hard Thresholding, and note that the same example applies to ARHT and Exhaustive Local Search [AS21]. Their discussion also lists LASSO; the Foster, Karloff, and Thaler full version itself states that the example thwarts LASSO but does not include that proof. For the OMP-like methods, the mechanism is explicit: the gradient criterion, when initialized outside the optimal 5

support, favors distractor coordinates and never enters that support. This is an algorithm-specific obstruction, rather than a complexity lower bound for arbitrary polynomial-time algorithms. Conjecture 27 of Axiotis and Sviridenko asks whether the exponent of κ can be improved by any polynomial-time algorithm. Our result addresses this remaining question for least squares: conditional on Hypothesis 2.1, it rules out the support bound O(kκ1−γ s+k ) for arbitrary randomized polynomial-time algorithms. Thus the lower bound is directly parameterized by the same restricted condition number that appears in the upper bounds. The Small-Set Expansion Hypothesis arose from work relating graph expansion to the Unique Games Conjecture [RS10]. Reductions among exact-volume and robust expansion problems were developed by Raghavendra, Steurer, and Tulsiani [RST12]. The hypothesis used here concerns randomized hardness of this exact-volume problem on rational weighted regular inputs. Our main soundness step converts expansion at one prescribed cardinality into a bound on the nonexpanding core of an arbitrary relaxed support.

2

Preliminaries

Throughout, numerical inputs and outputs are rational and encoded in binary.

2.1

Expansion and randomized exact-volume SSEH

Let G be an undirected weighted graph on V = [n], represented by symmetric nonnegative rational weights wuv = wvu , with its nonzero weights listed and encoded in binary. We allow self-loops. The weighted degree of every vertex is normalized to one: X wuv = 1 for every u ∈ V. (2.1) v∈V

This normalization loses no generality: if the common weighted degree is d, dividing every weight by d converts the usual conductance wG (S, V \ S)/(d|S|) into the degree-one expression below and preserves polynomial bit complexity. For sets S, T ⊆ V , write XX wG (S, T ) = wuv , IG (S) = wG (S, S). u∈S v∈T

For a nonempty set S ⊆ V , its normalized edge expansion is ΦG (S) =

wG (S, V \ S) . |S|

(2.2)

IG (S) . |S|

(2.3)

Regularity gives ΦG (S) = 1 − Let WG = (wuv )u,v∈V and LG = I − WG . Then x⊤ LG x =

X 1 X wuv (xu − xv )2 = wuv (xu − xv )2 . 2 u<v

(2.4)

u,v∈V

In particular, for every nonempty S, 1⊤ S LG 1S = wG (S, V \ S) = |S|ΦG (S). 6

(2.5)

The exact-volume YES/NO structure below is the SSE(η, δ) promise of Raghavendra, Steurer, and Tulsiani [RST12]; equivalently, it may be stated using the uniform vertex measure ν(S) = |S|/n. We state its randomized finite-precision version, with rational edge weights encoded in binary. The usual NP-hardness formulation together with NP ⊈ BPP implies this randomized formulation. Hypothesis 2.1 (Randomized weighted exact-volume SSE hypothesis). For every constant η ∈ (0, 1/2), there exists a constant δSSE ∈ Q ∩ (0, η] such that the following promise problem cannot be solved by a randomized polynomial-time algorithm with success probability at least 2/3 on every promised input. Given an undirected, weighted graph G on n vertices satisfying Equation (2.1), with rational weights encoded in binary, and restricted to admissible values of n for which k = δSSE n is an integer, distinguish between YES:

there exists S ⋆ ⊆ V, |S ⋆ | = k, ΦG (S ⋆ ) ≤ η;

NO:

every S ⊆ V, |S| = k, ΦG (S) ≥ 1 − η.

The hard family contains arbitrarily large admissible values of n. The restriction δSSE ≤ η entails no loss: for a uniformly random k-element set T , one has EΦG (T ) ≤ (n − k)/(n − 1), so arbitrarily large NO instances require δSSE ≤ η. The equality |S| = k is part of both sides of the promise: in particular, the NO case makes no assertion about sets of smaller or larger cardinality. This exact-size restriction is used in Lemma 4.5. The probability in Hypothesis 2.1 is over the internal randomness of the distinguishing algorithm; the constant 2/3 may be replaced by any fixed constant greater than 1/2 by standard amplification.

2.2

Restricted condition numbers

Let A ∈ Rm×n have full column rank. For an integer r ≥ 1, define κr (A) =

max

∥Ah∥22

min

∥Ah∥22

h∈Rn : ∥h∥2 =1, ∥h∥0 ≤r h∈Rn : ∥h∥2 =1, ∥h∥0 ≤r

.

(2.6)

For r ≥ n, we use the convention κr (A) = κn (A). The denominator is positive because A has full column rank. If AT denotes the submatrix formed by the columns indexed by T , then the maximum and minimum of ∥Ah∥22 over unit vectors supported on T are λmax (A⊤ T AT ) and λmin (A⊤ A ), respectively. Thus Equation (2.6) is equivalent to the usual principal-submatrix T T definition. In the normalization of Axiotis and Sviridenko, the restricted smoothness and strongconvexity constants are twice the numerator and denominator of Equation (2.6) for the least-squares objective ∥Ax − b∥22 , respectively. The factor of two cancels, so this is exactly the condition number used in Conjecture 27 [AS21]. When the matrix A is understood, we write κr for κr (A). For later reference we isolate the algorithmic guarantee that the reduction rules out. Definition 2.2 (Condition-number-improving sparse least squares). Fix constants γ ∈ (0, 1] and C ≥ 1. A (C, γ) sparse least-squares algorithm is a randomized algorithm that, on every input A ∈ Qm×n , b ∈ Qm , k ∈ {1, . . . , n}, and ε ∈ Q>0 , with A of full column rank, returns x ∈ Qn for which the two guarantees ∥Ax − b∥22 ≤ min ∥Az − b∥22 + ε, ∥z∥0 ≤k (2.7) ∥x∥0 ≤ Ckκ∥x∥0 +k (A)1−γ . hold simultaneously with probability at least 2/3 over the internal randomness of the algorithm. The index ∥x∥0 + k in Equation (2.7) depends on the output itself. The reduction handles this self-reference by bounding κr (A) uniformly over all r. 7

3

Graph-to-regression construction

Fix a positive rational constant c; its final value will be chosen in Section 5.1.

3.1

Quadratic construction and conditioning

Given an SSE instance G, set µ=c

(3.1)

FG (x) = x⊤ LG x + µ∥x∥22 − 21⊤ x.

(3.2)

and define Lemma 3.1 (Uniform condition-number bound). The matrix LG + µI has spectrum contained in [µ, 2 + µ]. Consequently, every restricted condition number of a least-squares objective with normal matrix LG + µI is at most 2 K(c) = 1 + . c Proof. For every x ∈ RV , 0 ≤ x⊤ LG x =

X

wuv (xu − xv )2 ≤ 2

u<v

X

wuv (x2u + x2v ) ≤ 2∥x∥22 ,

u<v

where the last inequality uses Equation (2.1); self-loop weights only reduce the total non-loop weight incident to a vertex. Hence LG has spectrum in [0, 2], as is standard for normalized Laplacians [Chu97]. Adding µI puts the spectrum in [µ, 2 + µ]. Every principal submatrix has eigenvalues between the global minimum and maximum by Cauchy interlacing. Since µ = c, the ratio is at most (2 + µ)/µ = 1 + 2/c.

3.2

Exact rational realization

√ Let BG be the weighted incidence matrix having one row wuv (eu − ev )⊤ for each non-loop edge {u, v}. Its diagonal and off-diagonal entries satisfy X ⊤ ⊤ (BG BG )uu = wuv = 1 − wuu , (BG BG )uv = −wuv (u ̸= v). v̸=u ⊤ B = I − W = L . The most direct real least-squares representation is Hence BG G G G     0 ebG = eG = √BG , A . µI µ−1/2 1

Indeed,

eG x − ebG ∥2 = x⊤ LG x + µ∥x∥2 − 21⊤ x + n = FG (x) + n , ∥A 2 2 µ µ

e⊤ A e and A G G = LG + µI. This factorization may contain irrational square roots of edge weights or of µ. The next lemma replaces both blocks by rational rows without changing either identity. Lemma 3.2 (Exact rational realization). There is a polynomial-time construction of a rational matrix AG and a rational vector bG such that, for every x ∈ RV , QG (x) := ∥AG x − bG ∥22 = FG (x) + 8

n , µ

(3.3)

and A⊤ G AG = LG + µI.

(3.4)

The construction has polynomial size, every row of AG has at most two nonzero entries, and all entries have polynomial bit complexity. Proof. We first record a deterministic rational sum-of-squares decomposition. Given a positive rational number a/b in lowest terms, put N = ab. Read the binary expansion of N . A nonzero bit 22j contributes the square (2j )2 , whereas a nonzero bit 22j+1 contributes two copies of (2j )2 . Thus, in polynomial time, we obtain N=

ℓ X

rt2 ,

ℓ = O(1 + log N ).

t=1

Setting λt = rt /b gives ℓ X

λ2t =

t=1

a N = . 2 b b

(3.5)

Apply this decomposition to every positive non-loop edge weight, writing wuv =

ℓuv X

λ2uv,t .

t=1

For each coefficient, add the row λuv,t (eu − ev )⊤ to AG and response zero to bG . Together these rows contribute exactly wuv (xu − xv )2 . Self-loops require no rows, because they make no contribution to LG . Apply the same decomposition to µ, writing µ=

ℓµ X

λ2µ,t .

t=1

For every vertex i and every t ∈ {1, . . . , ℓµ }, add the row λµ,t e⊤ i to AG and the response λµ,t /µ to bG . For a fixed coordinate i, these rows contribute  ℓµ  X λµ,t 2 1 λµ,t xi − = µx2i − 2xi + . µ µ t=1

Summing over vertices and edges proves Equations (3.3) and (3.4). Every edge row has two nonzero entries, while every ridge row has one. This proves the asserted row-sparsity property. For a weight a/b, the construction uses O(1 + log a + log b) rows, and every coefficient rt /b has O(1 + log a + log b) bits. Summed over the explicitly encoded nonzero weights, the number of rows and their total bit complexity are polynomial in the graph encoding. The ridge coefficient µ = c is fixed, so its block has constant overhead per vertex. By Lemmas 3.1 and 3.2, A⊤ G AG is positive definite and every restricted condition number of AG is at most K(c). The additive shift n/µ affects neither minimizers nor value gaps.

9

4

Completeness and soundness

Fix rational constants L ≥ 1 and θ ∈ (0, 1) satisfying θ<

1 , 2L

(4.1)

and set η = θ2 . Let G be an instance of the resulting exact-volume SSE promise, write k = δSSE n, and restrict attention to admissible instances with k ≥ 2. Define n k − 2 , µ θ +c 1 θ L Γ(c, L, θ) := 2 − − 1 . θ +c c (1 − θ)2 + c 2 YG :=

(4.2) (4.3)

The next theorem records the two bounds for arbitrary parameters satisfying Equation (4.1); Section 5.1 will choose them so that Γ(c, L, θ) > 0. Theorem 4.1 (Reduction gap). For the rational least-squares instance QG constructed in Section 3, the following bounds hold: 1. If G is a YES instance, then min QG (x) ≤ YG .

∥x∥0 ≤k

2. If G is a NO instance, then every x with ∥x∥0 ≤ Lk satisfies QG (x) ≥ YG + kΓ(c, L, θ). The remainder of this section proves Theorem 4.1.

4.1

Completeness

Lemma 4.2 (YES-instance upper bound). If G is a YES instance, then k min FG (x) ≤ − 2 . θ +c ∥x∥0 ≤k

(4.4)

min QG (x) ≤ YG .

(4.5)

Equivalently, ∥x∥0 ≤k

Proof. Let S ⋆ be the promised set of size k and expansion at most θ2 . For x = α1S ⋆ , x⊤ LG x = α2 wG (S ⋆ , V \ S ⋆ ) ≤ α2 θ2 k. Consequently,
FG (α1S ⋆ ) ≤ k (θ2 + c)α2 − 2α . The right-hand side is minimized at α = 1/(θ2 + c), where it equals the right-hand side of Equation (4.4). Adding n/µ proves Equation (4.5).

10

4.2

Support decomposition and Dirichlet expansion

Fix a support S ⊆ V , and let LS be the principal submatrix of LG indexed by S. Directly from the Laplacian quadratic form, every x ∈ RS satisfies X X x⊤ LS x = wuv (xu − xv )2 + wG ({v}, V \ S)x2v . (4.6) u<v u,v∈S

v∈S

Now fix a partition S = U ∪ W with U ∩ W = ∅. Each edge between U and W contributes a nonnegative square to Equation (4.6). Deleting precisely these squares separates the form into two blocks and can only decrease it. Let LG[W ] denote the Laplacian of the weighted graph induced by W , put cw = wG ({w}, V \ S), and define the modified Dirichlet Laplacian L′W := LG[W ] + diag(cw )w∈W .

(4.7)

Thus L′W retains the edges inside W and the Dirichlet boundary terms from W to V \ S, but not the edges between W and U . Equivalently, X X x⊤ L′W x = wuv (xu − xv )2 + cw x2w , (4.8) u<v u,v∈W

w∈W

For X ⊆ W , put ′ EW (X) = wG (X, W \ X) + wG (X, V \ S)

and h′ (W ) =

′ (X) EW . ∅̸=X⊆W |X|

min

(4.9) (4.10)

Define L′U symmetrically, retaining the edges inside U and the Dirichlet boundary terms from U to V \ S while deleting the edges to W . By Equation (4.6), for every x ∈ RS , X X ′ ⊤ ′ x⊤ LS x − x⊤ wuw (xu − xw )2 ≥ 0. U LU xU − xW LW xW = (4.11) u∈U w∈W

Equivalently, LS ⪰ L′U ⊕ L′W .

(4.12)

Here ⊕ denotes the block-diagonal direct sum, with the U -coordinates ordered before the W coordinates. The following is the standard Dirichlet form of Cheeger’s inequality [Chu07]; we include the short proof to record the normalization used here. Lemma 4.3 (Modified Dirichlet Cheeger inequality). If W ̸= ∅, then 1 λmin (L′W ) ≥ h′ (W )2 . 2

(4.13)

Proof. Let x ∈ RW be nonzero. Replacing x by |x| does not increase the quadratic form in Equation (4.8), so assume x ≥ 0. Apply Cauchy–Schwarz to two vectors indexed jointly by the

11

internal edges and the vertices of W : their edge coordinates are √ while both boundary coordinates are cw xw . This gives X X wuv |xu − xv |(xu + xv ) + cw x2w u<v u,v∈W

√

wuv |xu − xv | and

√

wuv (xu + xv ),

w∈W

1/2



X   X wuv (xu + xv )2 + cw x2w  ≤ (x⊤ L′W x)1/2  u<v u,v∈W

w∈W

√ ≤ (x⊤ L′W x)1/2 2∥x∥2 . The last step uses (a + b)2 ≤ 2(a2 + b2 ) and 2 degW (w) + cw ≤ 2, where degW (w) denotes the total weight from w to the other vertices of W ; this is where the degree-one normalization Equation (2.1) is used. For t ≥ 0, let Wt = {w ∈ W : xw > t}. Since x ≥ 0, Z ∞ Z ∞ 2 2 2 |xu − xv | = 1{xu >t} − 1{xv >t} 2t dt, xw = 1{xw >t} 2t dt. 0

0

Summing these identities gives the coarea formula X X wuv |x2u − x2v | + cw x2w u<v u,v∈W

w∈W

Z ∞ =

′ EW (Wt ) 2t dt ≥ h′ (W )

0

Z ∞

|Wt | 2t dt = h′ (W )∥x∥22 .

0

The left-hand side is the same expression bounded above by Cauchy–Schwarz. Combining the two estimates and squaring gives x⊤ L′W x 1 ≥ h′ (W )2 . 2 ∥x∥22 Taking the infimum over nonzero x proves the claim. The next lemma is the usual low-expansion peeling argument; closely related decompositions appear, for example, in the proof of the Small-Set Expansion algorithms of Arora, Barak, and Steurer [ABS10]. Lemma 4.4 (Greedy support decomposition). Let S ⊆ V be nonempty and let τ ∈ (0, 1). There is a partition S = U ∪ W , with U ∩ W = ∅, such that 1. if W ̸= ∅, then h′ (W ) ≥ τ ; 2. if U ̸= ∅, then ΦG (U ) < τ . Proof. Initialize W = S and U = ∅. While there is a nonempty set X ⊆ W with wG (X, W \ X) + wG (X, V \ S) < τ |X|,

(4.14)

move X from W to U . The process terminates because S is finite, and the first conclusion is exactly the absence of a violating set at termination. If U = ∅, the second conclusion is vacuous. Otherwise, let X1 , . . . , Xm be the removed sets. Summing Equation (4.14) over the iterations counts all the boundary weight wG (U, V \ U ) and 12

possibly some additional nonnegative contributions from edges between different removed pieces. Hence m X wG (U, V \ U ) < τ |Xi | = τ |U |. i=1

Division by |U | proves the second conclusion. We use Lemma 4.4 with Then, whenever W ̸= ∅,

τ = 1 − θ.

(4.15)

1 λmin (L′W ) ≥ (1 − θ)2 2

(4.16)

by Lemma 4.3.

4.3

The exact-volume core lemma

The next lemma is the step that uses the exact-cardinality NO promise. It controls a set whose cardinality is not known in advance using only expansion information at cardinality exactly k. Lemma 4.5 (Size of the nonexpanding core). Assume G is a NO instance with promise parameter η = θ2 and target cardinality k = δSSE n ≥ 2. Let L ≥ 1 and θ ∈ (0, 1) satisfy θ < 1/(2L), let S ⊆ V satisfy |S| ≤ Lk, and apply Lemma 4.4 with τ = 1 − θ. Then the removed core satisfies |U | < θk.

(4.17)

Proof. There is nothing to prove when U = ∅. Otherwise, Lemma 4.4 gives ΦG (U ) < 1 − θ.

(4.18)

We first prove that |U | ≤ k. Suppose instead that m := |U | > k, and let T be a uniformly random k-element subset of U . Recall that IG (A) = wG (A, A) = |A|(1 − ΦG (A)). Each ordered pair of distinct vertices in U belongs to T × T with probability k(k − 1)/[m(m − 1)], while a diagonal pair (u, u) belongs to T × T with probability k/m, which is larger. Therefore EIG (T ) ≥

k(k − 1) IG (U ). m(m − 1)

Using Equation (2.3), k − 1 IG (U ) . m−1 m By Equation (4.18), IG (U )/m > θ. Moreover, m ≤ |S| ≤ Lk and k ≥ 2, so EΦG (T ) ≤ 1 −

(4.19)

k−1 k−1 1 ≥ > . m−1 Lk − 1 2L Consequently, θ . 2L Every realization of T has cardinality exactly k, so the NO promise gives EΦG (T ) ≥ 1 − θ2 . Since θ < 1/(2L), θ EΦG (T ) < 1 − < 1 − θ2 ≤ EΦG (T ), 2L EΦG (T ) < 1 −

13

a contradiction. Hence |U | ≤ k. Choose any R ⊆ V \ U with |R| = k − |U | and put T = U ∪ R. The NO promise gives ΦG (T ) ≥ 1 − θ2 , while wG (T, V \ T ) ≤ wG (U, V \ U ) + |R|, where the degree-one normalization Equation (2.1) bounds the total weight incident to every added vertex by one. It follows that 1 − θ2 ≤ ΦG (T ) ≤

|U |ΦG (U ) + k − |U | . k

After rearranging,
|U | 1 − ΦG (U ) ≤ θ2 k. Since Equation (4.18) implies 1 − ΦG (U ) > θ, we obtain |U | < θk.

4.4

Soundness

Lemma 4.6 (Restricted-support minimum). Let S ⊆ V be nonempty, and let S = U ∪ W with U ∩ W = ∅. If W ̸= ∅, then min supp(x)⊆S

FG (x) ≥ −

|W | |U | . − µ λmin (L′W ) + µ

(4.20)

If W = ∅, the second term is absent. Proof. Let LS be the principal submatrix of LG indexed by S. For vectors supported on S, ⊤ FG (x) = x⊤ S (LS + µI)xS − 21S xS .

By Equation (4.12), LS ⪰ L′U ⊕ L′W . After adding µI, both sides are positive definite. For positive-definite matrices, a larger quadratic form has a smaller inverse, so (LS + µI)−1 ⪯ (L′U + µI)−1 ⊕ (L′W + µI)−1 . Completing the square and applying this inverse bound gives min supp(x)⊆S

−1 FG (x) = −1⊤ S (LS + µI) 1S ′ −1 ⊤ ′ −1 ≥ −1⊤ U (LU + µI) 1U − 1W (LW + µI) 1W .

Since L′U ⪰ 0 and, when W ̸= ∅, L′W ⪰ λmin (L′W )I, the corresponding inverse bounds are (L′U + µI)−1 ⪯

1 I, µ

(L′W + µI)−1 ⪯

1 I λmin (L′W ) + µ

(W ̸= ∅).

Taking quadratic forms with 1U and 1W , and using ∥1U ∥22 = |U | and ∥1W ∥22 = |W |, gives the claimed bounds. Theorem 4.7 (NO-instance lower bound). If G is a NO instance, then every x with ∥x∥0 ≤ Lk satisfies θk Lk FG (x) ≥ − − 1 . (4.21) 2 c 2 (1 − θ) + c Equivalently, QG (x) ≥

n θk Lk − − 1 . 2 µ c 2 (1 − θ) + c 14

(4.22)

Proof. Let S = supp(x). If S = ∅, then FG (x) = 0, and Equation (4.21) is immediate. Otherwise, apply Lemma 4.4 with τ = 1 − θ to obtain S = U ∪ W with U ∩ W = ∅. By Lemma 4.5, |U | < θk, and |W | ≤ |S| ≤ Lk. If W = ∅, Lemma 4.6 gives |U | θk FG (x) ≥ − ≥− , µ c which is stronger than Equation (4.21). If W = ̸ ∅, combine Lemma 4.6 and Equation (4.16) with µ = c to obtain |U | |W | − µ λmin (L′W ) + µ θk Lk ≥− − 1 . 2 c 2 (1 − θ) + c

FG (x) ≥ −

Adding the shift n/µ proves Equation (4.22). Proof of Theorem 4.1. The YES bound is Lemma 4.2. In the NO case, Theorem 4.7 and the definitions in Equations (4.2) and (4.3) give QG (x) ≥ YG + kΓ(c, L, θ) for every ∥x∥0 ≤ Lk.

5

Parameter selection and hardness

5.1

Choosing the constants

Fix constants γ ∈ (0, 1] and C ≥ 1. We choose constants in the order (γ, C) −→ c −→ L −→ θ −→ η = θ2 −→ δSSE . The constant c controls the ridge strength, while L bounds the output support blow-up. Lemma 5.1 (Parameter selection). There exist rational constants c ∈ (0, 1), L ≥ 1, and θ ∈ (0, 1) such that 1 Γ(c, L, θ) > 0 and θ< . 2L Moreover, if the design matrix A of an instance satisfies κr (A) ≤ K(c) := 1 +

2 c

for every r,

(5.1)

then the output of a (C, γ) algorithm has support at most Lk on every run on which its support guarantee holds. Proof. Let   ) 2 1−γ L0 (c) = max 1, C 1 + . c (

As c → 0+ ,   2 1−γ cC 1 + = Ccγ (2 + c)1−γ −→ 0. c 15

Since also c → 0, it follows that c(L0 (c) + 1) → 0. We may therefore choose a rational c ∈ (0, 1) so small that c(L0 (c) + 1) < 1/2. Choose a rational L with L0 (c) ≤ L < L0 (c) + 1. In particular, cL < 1/2. At θ = 0, the first term in Equation (4.3) is 1/c, whereas the last term is L/(1/2 + c). Since cL < 1/2 < 1/2 + c, we have 1 L > . c 1/2 + c By continuity and the density of the rationals, a sufficiently small rational θ > 0 makes Γ(c, L, θ) positive and satisfies Equation (4.1). Finally, suppose that Equation (5.1) holds and that x is the output on a run on which the support guarantee in Equation (2.7) holds. With r = ∥x∥0 , we have r ≤ Ckκr+k (A)1−γ ≤ CkK(c)1−γ ≤ L0 (c)k ≤ Lk.

For the rest of the paper, fix c, L, θ as in Lemma 5.1, set η = θ2 ∈ (0, 1/2), and invoke Hypothesis 2.1 with this value of η. These constants are fixed for the chosen (C, γ) and are hardwired into the reduction. Write k = δSSE n and restrict attention to sufficiently large admissible instances, so in particular k ≥ 2. Since δSSE ≤ η = θ2 and θ < 1/(2L), LδSSE ≤ Lθ2 < 1, and hence Lk < n. Thus the dense zero-residual solution µ−1 1 lies outside the support range of the NO-instance lower bound.

5.2

Proof of the main theorem

Define the positive gap ∆G = kΓ(c, L, θ) > 0,

(5.2)

where Γ is from Equation (4.3). By Theorem 4.1, the stated YES upper bound and NO lower bound are separated by ∆G . Set ∆G εG = . (5.3) 3 Proof of Theorem 1.1. Suppose for contradiction that an algorithm ruled out by Theorem 1.1 exists. It is a (C, γ) algorithm in the sense of Definition 2.2. Given a graph G from the promise problem fixed above, the finitely many smaller input sizes are handled directly by enumerating their k-element subsets, so assume that n lies in the sufficiently large regime. Construct (AG , bG ) as in Lemma 3.2. By Lemmas 3.1 and 3.2, AG has full column rank, every row of AG has at most two nonzero entries, and κr (AG ) ≤ K(c) for every r. Because c was fixed as a function only of (C, γ), this proves the structural assertion in the theorem with KC,γ = K(c). Call the algorithm on (AG , bG , k, εG ),

16

let x be the returned vector, and let E be the event that both guarantees in Equation (2.7) hold. By the assumed success guarantee, 2 Pr(E) ≥ . (5.4) 3 Hence, on E, Lemma 5.1 gives ∥x∥0 ≤ Lk. Recall YG from Equation (4.2). Output YES if and only if QG (x) < YG +

2∆G ; 3

(5.5)

otherwise, output NO. If G is a YES instance, then on E the additive guarantee and Theorem 4.1 give ∆G QG (x) ≤ min QG (z) + εG ≤ YG + , 3 ∥z∥0 ≤k so the rule outputs YES. If G is a NO instance, then on E the support bound allows us to apply Theorem 4.1, yielding QG (x) ≥ YG + ∆G , so the rule outputs NO. Thus the decision rule is correct whenever E occurs. The constructed instance has a polynomial-size rational encoding by Lemma 3.2. Since c, L, θ are fixed rational constants, all quantities in the decision rule also have polynomial-size rational encodings. Moreover, k ≥ 1 and Γ(c, L, θ) > 0, so 1 3 3 = ≤ . εG kΓ(c, L, θ) Γ(c, L, θ) Thus the call to the hypothetical algorithm remains polynomial-time. Its rational output x has encoding length bounded by its running time, so ∥x∥0 and QG (x) can be computed exactly in polynomial time. The decision rule would therefore solve the SSE promise in randomized polynomial time with success probability at least 2/3, contradicting Hypothesis 2.1. Corollary 5.2 (Hardness at fixed additive accuracy). Fix any rational constant ε0 > 0. Under Hypothesis 2.1, the conclusion of Theorem 1.1 continues to hold even for algorithms specialized to the single accuracy value ε = ε0 . Proof. Since ∆G = kΓ(c, L, θ) = δSSE nΓ(c, L, θ), we have ∆G > 3ε0 for all sufficiently large n in the hard family. On those instances, repeat the proof of Theorem 1.1, calling the hypothetical algorithm at its fixed accuracy ε0 . In the YES case, QG (x) ≤ YG + ε0 < YG +

∆G , 3

whereas the NO-case bound is unchanged. Hence the same decision rule distinguishes the two cases, contradicting Hypothesis 2.1.

Acknowledgements The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation, and take responsibility for the final version. The authors would like to thank Kyriakos Axiotis for helpful discussions. 17

References [ABS10] Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 563–572. IEEE Computer Society, 2010. [AS21]

Kyriakos Axiotis and Maxim Sviridenko. Sparse convex optimization via adaptively regularized hard thresholding. Journal of Machine Learning Research, 22(122):1–47, 2021.

[AS22]

Kyriakos Axiotis and Maxim Sviridenko. Iterative hard thresholding with adaptive regularization: Sparser solutions without sacrificing runtime. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 1175–1197. PMLR, 2022.

[Chu97] Fan R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997. [Chu07] Fan Chung. Random walks and local cuts in graphs. Linear Algebra and its Applications, 423(1):22–32, 2007. [FKT15] Dean Foster, Howard Karloff, and Justin Thaler. Variable selection is hard. In Proceedings of the 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 696–709. PMLR, 2015. Full version available as arXiv:1412.4832. [JTK14] Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high-dimensional M-estimation. In Advances in Neural Information Processing Systems, volume 27, pages 685–693, 2014. [Nat95]

B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM Journal on Computing, 24(2):227–234, 1995.

[RS10]

Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 755–764. Association for Computing Machinery, 2010.

[RST12] Prasad Raghavendra, David Steurer, and Madhur Tulsiani. Reductions between expansion problems. In Proceedings of the 27th Conference on Computational Complexity, pages 64–73. IEEE Computer Society, 2012. [SSSZ10] Shai Shalev-Shwartz, Nathan Srebro, and Tong Zhang. Trading accuracy for sparsity in optimization problems with sparsity constraints. SIAM Journal on Optimization, 20(6):2807–2832, 2010.

18

Related documents

• Recovering linear images of sparse signals from indirect observations#973782
• An Overview of Minimum Convex Cover and Maximum Hidden Set#180512
• An Overview of Minimum Convex Cover and Maximum Hidden Set#179650
• An Overview of Minimum Convex Cover and Maximum Hidden Set#179255
• An Overview of Minimum Convex Cover and Maximum Hidden Set#179057