Learning symmetric k-juntas in time n^o(k)

Mihail N. Kolountzakis, Evangelos Markakis, Aranyak MehtaarXiv 2005 · DOI · arXiv

Abstract

We present an algorithm for learning symmetric $k$-juntas—Boolean functions of $n$ variables that depend on an unknown subset of $k$ variables—under the uniform distribution in the PAC model. The algorithm achieves a running time of $n^{O(k/\log k)}$, providing the first $n^{o(k)}$ time algorithm for this class. This result is derived from a new structural theorem in Fourier analysis: every symmetric Boolean function on $k$ variables, excluding parity and constant functions, possesses a non-zero Fourier coefficient of order $t$, where $1 \leq t \leq O(k/\log k)$. This improves upon the previous best known bound of $(3/31)k$.

Introduction

In computational learning theory, the "junta" problem is a classic challenge: how can an algorithm efficiently identify a small set of $k$ relevant variables hidden among $n$ total variables? Formally, a function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if there exists a set $J$ of size $|J| \leq k$ such that $f$ depends only on the variables in $J$.

While identifying these variables is trivial in $O(n^k)$ time via exhaustive search, the quest for more efficient algorithms is a central theme in the field. This paper focuses on the class of symmetric $k$-juntas, where the function's value is determined solely by the number of relevant variables set to 1 (the Hamming weight of the input restricted to $J$). Examples include majority gates and threshold functions. Prior to this work, the best algorithms for symmetric juntas required $n^{ck}$ time for some constant $c$, leaving the $n^{o(k)}$ regime unexplored.

Fourier Analysis and the Learning Task

The standard approach to learning juntas under the uniform distribution involves Fourier analysis of Boolean functions. Any Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ can be uniquely represented as a polynomial:

$$f(x) = \sum_{S \subseteq [n]} \hat{f}(S) \chi_S(x)$$

where $\chi_S(x) = \prod_{i \in S} x_i$ are the parity functions. The coefficients $\hat{f}(S)$ are the Fourier coefficients.

A crucial property of juntas is that if a variable $i$ is not in the set of relevant variables $J$, then $\hat{f}(S) = 0$ for all $S$ containing $i$. Consequently, to identify the set $J$, it suffices to find a set $S \neq \emptyset$ such that $\hat{f}(S) \neq 0$. If we can guarantee that such a set $S$ exists with size $|S| \leq t$, we can identify $J$ in approximately $n^t$ time by checking all subsets of size up to $t$.

The Structural Result: A New Fourier Bound

The core contribution of this research is a proof that symmetric functions cannot "hide" their influence in high-order coefficients indefinitely. The authors prove that for any symmetric function $f$ on $k$ variables (excluding the trivial cases of constant functions and the parity function itself), there must exist a non-zero Fourier coefficient $\hat{f}(S)$ with $1 \leq |S| \leq O(k/\log k)$.

This result significantly improves the previous state-of-the-art bound of $3k/31$. By reducing the required "search depth" $t$ from a linear fraction of $k$ to a sub-linear function $O(k/\log k)$, the authors achieve the first $n^{o(k)}$ learning algorithm for this class.

Technical Overview

The proof of the Fourier bound involves several sophisticated mathematical tools:

  • Polynomial Representation: The authors represent the symmetric function as an integer-valued polynomial. The problem of vanishing Fourier coefficients is translated into the problem of this polynomial being constant over a specific range.
  • Number Theory and Periodicity: To show the polynomial must be constant, the authors use the Siegel-Walfisz theorem to identify primes in arithmetic progressions. By applying Lucas’ Theorem, they analyze the behavior of binomial coefficients modulo these primes. They demonstrate that if low-order Fourier coefficients vanish, the function must exhibit a form of periodicity that eventually forces it to be a constant or a parity.
  • Moment Equivalence: The authors utilize a connection between Fourier coefficients and the moments of random variables. Specifically, the vanishing of coefficients up to order $r$ implies that the first $r$ moments of the Hamming weight under the function's support match those of a uniform distribution.

Implications and Limitations

The algorithmic consequence is a learning procedure that runs in $n^{O(k/\log k)}$ time. This represents a qualitative shift in the complexity of learning symmetric juntas, breaking the "linear-in-$k$ exponent" barrier. However, several open questions remain:

  1. General Juntas: The $n^{o(k)}$ result is currently restricted to symmetric functions. For general $k$-juntas, the best known bound remains approximately $n^{0.7k}$, and achieving $n^{o(k)}$ for the general case remains a major open problem.
  2. Tightness: The authors suggest that the $O(k/\log k)$ bound might be further improvable. It is possible that for all symmetric functions, a non-zero Fourier coefficient exists at a constant order $t$, which would imply a learning time of $poly(n)$ for any fixed $k$.
  3. Balanced vs. Unbalanced: While balanced symmetric functions (those with mean zero) were already known to have lower bounds, this work provides a unified approach that handles the more difficult "unbalanced" cases effectively.

Conclusion

By combining tools from number theory and Fourier analysis, this paper provides a new upper bound on the complexity of learning symmetric juntas. The transition to $n^{o(k)}$ time marks a significant milestone in the study of Boolean functions and computational learning theory.

Summary updated

Abstract

We give an algorithm for learning symmetric k-juntas (boolean functions of $n$ boolean variables which depend only on an unknown set of $k$ of these variables) in the PAC model under the uniform distribution, which runs in time n^{O(k/\log k)}. Our bound is obtained by proving the following result: Every symmetric boolean function on k variables, except for the parity and the constant functions, has a non-zero Fourier coefficient of order at least 1 and at most O(k/\log k). This improves the previously best known bound of (3/31)k, and provides the first n^{o(k)} time algorithm for learning symmetric juntas.
BibTeX
@misc{kolountzakis2005learning,
  author = {Mihail N. Kolountzakis and Evangelos Markakis and Aranyak Mehta},
  title = {{Learning symmetric k-juntas in time n^o(k)}},
  year = {2005},
  eprint = {math/0504246},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/math/0504246},
}
Figure