On learning k-parities with and without noise
This addresses fundamental challenges in learning theory for computational efficiency in parity learning, with incremental improvements over prior work.
The paper tackles the problem of learning k-parities in two settings: improving the time complexity by an exp(k) factor in the mistake-bound model, and breaking the n choose k/2 barrier for small noise rates in the classification noise setting, achieving a running time of poly(n) * (n choose k)^{1-α} * e^{-k/4.01} under specific conditions.
We first consider the problem of learning $k$-parities in the on-line mistake-bound model: given a hidden vector $x \in \{0,1\}^n$ with $|x|=k$ and a sequence of "questions" $a_1, a_2, ...\in \{0,1\}^n$, where the algorithm must reply to each question with $< a_i, x> \pmod 2$, what is the best tradeoff between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et al. by an $\exp(k)$ factor in the time complexity. Second, we consider the problem of learning $k$-parities in the presence of classification noise of rate $η\in (0,1/2)$. A polynomial time algorithm for this problem (when $η> 0$ and $k = ω(1)$) is a longstanding challenge in learning theory. Grigorescu et al. showed an algorithm running in time ${n \choose k/2}^{1 + 4η^2 +o(1)}$. Note that this algorithm inherently requires time ${n \choose k/2}$ even when the noise rate $η$ is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the $n \choose k/2$ barrier. In particular, if for some function $f(n) = ω(1)$ and $α\in [1/2, 1)$, $k = n/f(n)$ and $η= o(f(n)^{- α}/\log n)$, then there is an algorithm for the problem with running time $poly(n)\cdot {n \choose k}^{1-α} \cdot e^{-k/4.01}$.