Improved Approximation of Linear Threshold Functions

Ilias Diakonikolas, Rocco A. Servedio

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

Abstract

We prove two main results on how arbitrary linear threshold functions f(x) = sign(w ldr x - thetas) over the n-dimensional Boolean hypercube can be approximated by simple threshold functions. Our first result shows that every n-variable threshold function f is isin-close to a threshold function depending only on Inf(f) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ldr poly (1/isin) many variables, where Inf(f) denotes the total influence or average sensitivity of f. This is an exponential sharpening of Friedgut's well-known theorem [Fri98], which states that every Boolean function f is isin-close to a function depending only on 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(Inf(f)/isin)</sup> many variables, for the case of threshold functions. We complement this upper bound by showing that OmegaInf(f) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> + 1/isin <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) many variables are required for isin-approximating threshold functions. Our second result is a proof that every n-variable threshold function is isin-close to a threshold function with integer weights at most poly(n) ldr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2Omacr(1/isin</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2/3</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">)</sup> This is a significant improvement, in the dependence on the error parameter isin, on an earlier result of [Ser07] which gave a poly(n) ldr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2Omacr(1/isin</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">)</sup> bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original [Ser07] result, and extends to give low-weight approximators for threshold functions under a range of probability distributions beyond just the uniform distribution.
BibTeX
@article{diakonikolas2013improved,
  author = {Ilias Diakonikolas and Rocco A. Servedio},
  title = {{Improved Approximation of Linear Threshold Functions}},
  journal = {Comput. Complex.},
  year = {2013},
  doi = {10.1007/s00037-012-0045-5},
}
Figure