English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The degree-d Chow parameters of a Boolean function 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 ℓ2-norm, then f is close to g in ℓ1-distance. Notably, our bound relating the two distances is independent of the dimension. That is, we show that Boolean degree-d PTFs are robustly identifiable from their degree-d Chow parameters. 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 very close to 0 on a large number of points in { ± 1 }n, then there exists a degree-d hypersurface that exactly passes though 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 ℓ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.

Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)