Agnostically Learning Juntas from Random Walks
Jan Arpe, Elchanan Mossel · arXiv (Cornell University) · 2008
We prove that the class of functions g:{-1,+1}^n -> {-1,+1} that only depend on an unknown subset of k {-1,+1}, finds with probability at least 1-delta a k-junta that is (opt(f)+epsilon)-close to f, where opt(f) denotes the distance of a closest k-junta to f.