Introduction
Linear Threshold Functions (LTFs), also known as halfspaces or neurons, are fundamental primitives in computational learning theory and the building blocks of neural networks. Defined as $f(x) = \text{sign}(w \cdot x - \theta)$, these functions represent the simplest form of a decision boundary. Despite their ubiquity, understanding their structural complexity—specifically how they can be approximated by simpler functions or represented with smaller weights—remains a central challenge in theoretical computer science. This paper presents two significant breakthroughs: an exponential sharpening of Friedgut’s Theorem for the class of LTFs and a substantial reduction in the weight complexity required for $\epsilon$-approximation.
Sharpening Friedgut’s Theorem: From Exponential to Polynomial Juntas
A "junta" is a Boolean function that depends on only a small subset of its input variables. Friedgut’s Theorem is a landmark result in the analysis of Boolean functions, stating that any function with low total influence (a measure of how much the output changes when input bits are flipped) can be approximated by a junta. However, the general theorem provides a bound on the number of variables that is exponential in the ratio of influence to error ($2^{O(\text{Inf}/\epsilon)}$).
This research demonstrates that for the specific class of LTFs, this dependence can be improved to polynomial. Specifically, the authors prove that every $n$-variable LTF $f$ is $\epsilon$-close to an LTF depending on only $\text{Inf}(f)^2 \cdot \text{poly}(1/\epsilon)$ variables. By providing a matching lower bound of $\Omega(\text{Inf}(f)^2)$, the authors establish that their result is nearly optimal. This exponential sharpening shows that LTFs are significantly "simpler" than general Boolean functions with equivalent influence, allowing for much more efficient variable reduction.
Weight Complexity and Anti-concentration
The second major contribution addresses the "weight complexity" of LTFs. While any LTF can be represented using integer weights, the magnitude of these weights can be astronomically large, potentially reaching $2^{\Omega(n \log n)}$. In many computational contexts, it is desirable to find an LTF that is $\epsilon$-close to the original function but uses much smaller integer weights.
Previous work established a bound of $\text{poly}(n) \cdot 2^{\tilde{O}(1/\epsilon^2)}$ for such approximations, largely relying on Gaussian approximations and the Central Limit Theorem. This paper breaks the $1/\epsilon^2$ barrier, achieving a bound of $\text{poly}(n) \cdot 2^{\tilde{O}(1/\epsilon^{2/3})}$.
The technical innovation driving this improvement is the application of Halász’s anti-concentration bounds. Rather than treating the sum of weights as a coarse Gaussian distribution, the authors utilize the fact that if weights are "well-separated," the probability of the sum falling into a narrow interval near the threshold is extremely low. This "margin" allows for weights to be rounded to smaller integers without shifting the sum across the threshold $\theta$.
Methodology: A Function-First Perspective
The authors depart from traditional techniques by employing a mix of Fourier analysis and high-dimensional probability theory:
- Randomized Construction for Juntas: Instead of standard hypercontractivity tools, the authors use a randomized construction to build approximators. They decompose LTFs into a set of "large" weight variables and a "regular" remainder where no single weight dominates, allowing for more precise control over the influence.
- Existence over Transformation: Instead of attempting to round an arbitrary, potentially "ugly" weight vector, the authors prove that every LTF possesses a weight vector with favorable additive properties. This shift in perspective—focusing on the existence of a nice representation rather than the transformation of a given one—was key to leveraging Halász’s stronger probabilistic bounds.
Conclusion and Impact
These results provide the most precise structural characterization of LTFs to date. The jump to polynomial junta bounds and the $1/\epsilon^{2/3}$ weight exponent represent significant theoretical progress. The authors have shown these results are robust, holding not just for the uniform distribution but also for constant-biased product distributions and $K$-wise independent distributions.
While the authors conjecture that these junta results may extend to higher-degree Polynomial Threshold Functions (PTFs), the total influence of PTFs remains an open area of study. Furthermore, while the new weight bounds are a major step forward, the authors suggest that even better bounds—perhaps $\text{poly}(n, 1/\epsilon)$—might be possible with even more sophisticated structural results.
Summary updated