Lower Bounds for Approximate Sign Rank
Pith reviewed 2026-05-09 14:25 UTC · model grok-4.3
The pith
Every sign matrix of approximate sign-rank d contains a monochromatic rectangle of size d to the minus O(d) by d to the minus O(d squared).
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Any m by n sign matrix with epsilon-approximate sign-rank d contains a monochromatic rectangle of size d to the minus O(d) times m by d to the minus O(d squared) times n. Consequently the approximate sign-rank of large-margin halfspaces in R^d is Omega of square root of d over log d. The key geometric ingredient states that for any n points in general position in R^d there exist d subsets each of size d to the minus O(d) n such that no single hyperplane splits all of them; this follows from the Forster-Barthe isotropic-position theorem combined with the Bourgain-Tzafriri restricted-invertibility principle.
What carries the argument
The hyperplane-avoidance theorem that produces d large subsets of points in R^d with no common splitting hyperplane, derived via isotropic position and restricted invertibility.
If this is right
- The epsilon-approximate sign-rank of large-margin halfspaces in d dimensions is at least Omega of square root of d over log d.
- There exist concept classes of VC-dimension 2 whose approximate sign-rank is super-constant.
- The 2^m by 2^m Hadamard matrix has approximate sign-rank between Omega_epsilon of m and m to the O of square root of m times log of 1 over epsilon.
- Approximate sign-rank lower bounds can now be obtained from combinatorial rectangle arguments rather than solely from margin or epsilon dependence.
Where Pith is reading between the lines
- The rectangle lemma may extend to other sign-pattern problems arising in communication complexity or learning theory.
- If the subset-size exponents can be improved, the halfspace lower bound would become closer to the known upper bounds.
- The separation between VC dimension 2 and large approximate sign-rank suggests that approximate sign-rank captures geometric complexity beyond combinatorial dimension.
Load-bearing premise
The input points lie in general position in R^d, allowing the isotropic-position and restricted-invertibility theorems to produce subsets whose sizes do not collapse below d to the minus O(d).
What would settle it
A set of n points in general position in R^d for which every choice of d subsets each of size d to the minus O(d) n admits some hyperplane that splits all d subsets at once.
read the original abstract
We prove new upper and lower bounds on $\epsilon$-approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every $m \times n$ sign matrix with approximate sign-rank $d$ contains a monochromatic rectangle of size $d^{-O(d)}m \times d^{-O(d^2)}n$, paralleling classical results for exact sign-rank. As an application, we establish a lower bound of $\Omega(\sqrt{d/\log d})$ on the $\epsilon$-approximate sign-rank of large-margin $d$-dimensional half-spaces. Prior to our work, the only general lower bound technique known for approximate sign-rank yielded bounds of strength $\epsilon^{-1} - 1$, which are constant for fixed $\epsilon$. A key ingredient is a new geometric theorem on hyperplane avoidance: for any set of $n$ points in general position in $\mathbb{R}^d$, there exist $d$ subsets, each of size $d^{-O(d)} n$, such that no hyperplane simultaneously splits all of them. The proof combines the Forster-Barthe isotropic position theorem with the Bourgain-Tzafriri restricted invertibility principle. We also study the relationship between approximate sign-rank and VC dimension. We prove a lower bound on approximate sign-rank in terms of VC dimension, and exhibit concept classes of VC dimension $2$ with large approximate sign-rank. Finally, we study the approximate sign-rank of the $2^m \times 2^m$ Hadamard matrix $H_m$. The sign-rank of $H_m$ is known to be $\Omega(\sqrt{2^m})$ by Forster's classic theorem. Contrasting this, we adapt an argument of Alman and Williams to show that the approximate sign-rank of $H_m$ is at most $m^{O(\sqrt{m} \log(1/\epsilon))}$, and hence the Hadamard matrix does not witness polynomial-strength lower bounds for approximate sign-rank. Using our VC dimension bound, we prove that the approximate sign-rank of $H_m$ is at least $\Omega_\epsilon(m)$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proves new bounds on the ε-approximate sign-rank of sign matrices. It shows that every m × n sign matrix with approximate sign-rank d has a monochromatic rectangle of size d^{-O(d)} m × d^{-O(d^2)} n. This follows from a new geometric theorem stating that for n points in general position in R^d, there are d subsets each of size d^{-O(d)} n with no hyperplane splitting all of them, proved using the Forster-Barthe isotropic position theorem and the Bourgain-Tzafriri restricted invertibility principle. As an application, the ε-approximate sign-rank of large-margin d-dimensional half-spaces is Ω(√(d / log d)). The paper also provides a lower bound on approximate sign-rank in terms of VC-dimension, examples of VC-dim 2 classes with large approximate sign-rank, and shows that the approximate sign-rank of the Hadamard matrix H_m is between Ω_ε(m) and m^{O(√m log(1/ε))}, contrasting with its sign-rank lower bound of Ω(√(2^m)).
Significance. Assuming the quantitative bounds in the geometric theorem are correct, this provides the first lower bounds for approximate sign-rank that grow with the dimension d, improving upon the trivial ε^{-1}-1 bound. The monochromatic rectangle result is a useful structural theorem paralleling classical exact sign-rank results. The geometric contribution combines two classical theorems in a novel way to obtain subset sizes sufficient for the application. The Hadamard matrix upper bound demonstrates that approximate sign-rank can be substantially smaller than sign-rank. The VC-dimension results further clarify the relationship between these measures.
major comments (1)
- The proof of the hyperplane avoidance theorem (combining Forster-Barthe isotropic positioning with Bourgain-Tzafriri restricted invertibility) must explicitly track and bound all d-dependent loss factors to confirm the claimed subset sizes are d^{-O(d)} n rather than worse; any additional d^{-ω(d)} or exp(-Ω(d)) factor would invalidate the subsequent Ω(√(d/log d)) lower bound on half-space approximate sign-rank.
minor comments (2)
- The introduction should briefly recall the definition of ε-approximate sign-rank from Chornomaz et al. (STOC 2025) for accessibility.
- In the Hadamard matrix section, a short outline of how the Alman-Williams argument is adapted would improve readability.
Simulated Author's Rebuttal
We thank the referee for their thorough review and positive assessment of our work. We address the single major comment point by point below.
read point-by-point responses
-
Referee: The proof of the hyperplane avoidance theorem (combining Forster-Barthe isotropic positioning with Bourgain-Tzafriri restricted invertibility) must explicitly track and bound all d-dependent loss factors to confirm the claimed subset sizes are d^{-O(d)} n rather than worse; any additional d^{-ω(d)} or exp(-Ω(d)) factor would invalidate the subsequent Ω(√(d/log d)) lower bound on half-space approximate sign-rank.
Authors: We agree that an explicit tracking of all d-dependent factors is necessary to rigorously confirm the quantitative bounds. In the manuscript, the proof sketch in Section 3 combines the two theorems but does not expand every loss factor in detail. Upon review, the factors from applying the isotropic positioning and the restricted invertibility theorem accumulate to at most d^{-O(d)} in the subset sizes, without introducing exp(-Ω(d)) terms. To fully address the referee's concern and strengthen the paper, we will revise the manuscript to include a detailed, step-by-step accounting of all parameters and loss factors in an expanded proof of the geometric theorem. This will explicitly verify the d^{-O(d)} n subset sizes and ensure the Ω(√(d/log d)) lower bound for the approximate sign-rank of large-margin half-spaces holds as claimed. revision: yes
Circularity Check
No significant circularity; all derivations rely on external theorems
full rationale
The paper establishes a new geometric hyperplane-avoidance theorem for n points in general position in R^d by invoking the external Forster-Barthe isotropic-position theorem followed by the external Bourgain-Tzafriri restricted-invertibility principle; the resulting subset sizes d^{-O(d)} n are direct consequences of those classical statements rather than any self-definition or fitted parameter. The monochromatic-rectangle theorem is then derived from this geometric claim by a standard combinatorial argument that does not reduce to the paper's own inputs. The Omega(sqrt(d/log d)) lower bound on approximate sign-rank of large-margin half-spaces follows immediately from applying the rectangle theorem to the sign matrix induced by half-spaces, again without circular reduction. The VC-dimension lower bound, the VC=2 construction, and the Hadamard-matrix upper bound (adapting Alman-Williams) each rest on independent combinatorial or probabilistic arguments plus non-overlapping external citations. No load-bearing self-citation, self-definitional step, or fitted-input-called-prediction appears anywhere in the derivation chain.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Forster-Barthe isotropic position theorem
- standard math Bourgain-Tzafriri restricted invertibility principle
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.