Agnostically Learning Juntas from Random Walks

Details Agnostically Learning Juntas from Random Walks Agnostically Learning Juntas from Random Walks

2008-06-25

arxiv.org/abs/0806.4210v1

Computer Science

Learning

12 pages

Scientific paper

We prove that the class of functions g:{-1,+1}^n -> {-1,+1} that only depend on an unknown subset of k< 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.

Affiliated with

Also associated with

No associations

Rating

Agnostically Learning Juntas from Random Walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Agnostically Learning Juntas from Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Agnostically Learning Juntas from Random Walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-245279