Agnostically Learning Juntas from Random Walks
| dc.creator | Arpe, Jan | |
| dc.creator | Mossel, Elchanan | |
| dc.date | 2008-06-25 | |
| dc.date.accessioned | 2026-07-07T09:46:50Z | |
| dc.date.available | 2026-07-07T09:46:50Z | |
| dc.description | We prove that the class of functions g:{-1,+1}^n -> {-1,+1} that only depend on an unknown subset of k<<n variables (so-called k-juntas) is agnostically learnable from a random walk in time polynomial in n, 2^{k^2}, epsilon^{-k}, and log(1/delta). In other words, there is an algorithm with the claimed running time that, given epsilon, delta > 0 and access to a random walk on {-1,+1}^n labeled by an arbitrary function f:{-1,+1}^n -> {-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. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/0806.4210 | |
| dc.identifier | http://arxiv.org/abs/0806.4210 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/163669 | |
| dc.subject | Machine Learning | |
| dc.title | Agnostically Learning Juntas from Random Walks | |
| dc.type | text |