TR18-189 Authors: Ilias Diakonikolas, Daniel Kane

Publication: 8th November 2018 08:08

Downloads: 125

Keywords:

The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \R$ are its degree at most $d$ Fourier coefficients.

It is well-known that degree-$d$ Chow parameters uniquely characterize degree-$d$ polynomial threshold functions

(PTFs)

within the space of all bounded functions. In this paper, we prove a robust version of this theorem:

For $f$ any Boolean degree-$d$ PTF and $g$ any bounded function, if the degree-$d$ Chow parameters of

$f$ are close to the degree-$d$ Chow parameters of $g$ in $\ell_2$-norm, then $f$ is close to $g$ in $\ell_1$-distance.

Notably, our bound relating the two distances is completely independent of the dimension $n$. That is,

we show that Boolean degree-$d$ PTFs are {\em robustly identifiable} from their degree-$d$ Chow parameters.

Results of this form had been shown for the $d=1$ case,

but no non-trivial bound was previously known for $d >1$.

Our robust identifiability result gives the following algorithmic applications:

First, we show that Boolean degree-$d$ PTFs can be efficiently approximately reconstructed

from approximations to their degree-$d$ Chow parameters. This immediately implies

that degree-$d$ PTFs are efficiently learnable in the uniform distribution $d$-RFA model.

As a byproduct of our approach, we also obtain the first low integer-weight approximations of degree-$d$ PTFs, for $d>1$.

As our second application, our robust identifiability result gives the first efficient

algorithm, with dimension-independent error guarantees,

for malicious learning of Boolean degree-$d$ PTFs under the uniform distribution.

The proof of our robust identifiability result involves several new technical ingredients, including

the following structural result for degree-$d$ multivariate polynomials with very poor anti-concentration:

If $p$ is a degree-$d$ polynomial where $p(x)$ is {\em very} close to $0$ on a {\em large} number of points in $\bn$,

then there exists a degree-$d$ hypersurface that exactly passes though {\em almost all} of these points.

We leverage this structural result to show that if the degree-$d$ Chow distance between $f$ and $g$ is small,

then we can find many degree-$d$ polynomials that vanish on their disagreement region,

and in particular enough that forces the $\ell_1$-distance between $f$ and $g$ to also be small.

To implement this proof strategy, we require additional technical ideas.

In particular, in the $d=2$ case we show that for any large vector space of degree-$2$ polynomials

with a large number of common zeroes, there exists a linear function that vanishes on almost all of these zeroes.

The degree-$d$ degree generalization of this statement is significantly more complex, and can be viewed as an effective version

of Hilbert's Basis Theorem for our setting.