Approximating the Number of Relevant Variables in a Parity Implies Proper Learning
This addresses fundamental challenges in computational learning theory for researchers, by linking approximation hardness to proper learning of parities, which is incremental but could lead to breakthroughs in noise-tolerant learning.
The paper tackles the problem of approximating the number of relevant variables in parity functions under random classification noise, showing that this approximation is as hard as properly learning parities, potentially resolving long-standing open problems in computational learning theory.
Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities. More specifically, let $γ:{\mathbb R}^+\to {\mathbb R}^+$, where $γ(x) \ge x$, be any strictly increasing function. In our first result, we show that from any polynomial-time algorithm that returns a $γ$-approximation, $D$ (i.e., $γ^{-1}(d(f)) \leq D \leq γ(d(f))$), of the number of relevant variables~$d(f)$ for any parity $f$, we can, in polynomial time, construct a solution to the long-standing open problem of polynomial-time learning $k(n)$-sparse parities (parities with $k(n)\le n$ relevant variables), where $k(n) = ω_n(1)$. In our second result, we show that from any $T(n)$-time algorithm that, for any parity $f$, returns a $γ$-approximation of the number of relevant variables $d(f)$ of $f$, we can, in polynomial time, construct a $poly(Γ(n))T(Γ(n)^2)$-time algorithm that properly learns parities, where $Γ(x)=γ(γ(x))$. If $T(Γ(n)^2)=\exp({o(n/\log n)})$, this would resolve another long-standing open problem of properly learning parities in the presence of random classification noise in time $\exp({o(n/\log n)})$.