Agnostically Learning Juntas from Random Walks

Probability Inequalities for Sums of Bounded Random Variables

Wassily Hoeffding · 1963

Earlier work this paper cites.

Learning From Noisy Examples

Dana Angluin and Philip D. Laird · 1988

Earlier work this paper cites.

Learning Decision Trees Using the Fourier Spectrum

Eyal Kushilevitz and Yishay Mansour · 1993

Earlier work this paper cites.

Toward efficient agnostic learning

Michael J. Kearns, Robert E. Schapire, and Linda Sellie · 1994

Earlier work this paper cites.

A markovian extension of valiant’s learning model

David Aldous and Umesh V. Vazirani · 1995

Earlier work this paper cites.

Selection of Relevant Features and Examples in Machine Learning

Avrim Blum and Pat Langley · 1997

Earlier work this paper cites.

A Chernoff Bound for Random Walks on Expander Graphs

David Gillman · 1998

Cited alongside, same era.

Chernoff-type Bound for Finite Markov Chains

Pascal Lézaud · 1998

Cited alongside, same era.

Exploiting Random Walks for Learning

Peter L. Bartlett, Paul Fischer, and Klaus-Uwe Höffgen · 2002

Cited alongside, same era.

On Using Extended Statistical Queries to Avoid Membership Queries

Nader H. Bshouty and Vitaly Feldman · 2002

Cited alongside, same era.

Extension of the PAC Framework to Finite and Countable Markov Chains

David Gamarnik · 2003

Cited alongside, same era.

Online convex programming and generalized infinitesimal gradient ascent

Martin Zinkevich · 2003

Later among the works it cites.

Learning functions of k k relevant variables

Elchanan Mossel, Ryan W. O’Donnell, and Rocco A. Servedio · 2004

Later among the works it cites.

Learning DNF from random walks

Nader H. Bshouty, Elchanan Mossel, Ryan O’Donnell, and Rocco A. Servedio · 2005

Later among the works it cites.

On Learning Thresholds of Parities and Unions of Rectangles in Random Walk Models

Sébastien Roch · 2007

Later among the works it cites.

Agnostically Learning Decision Trees

Parikshit Gopalan, Adam Tauman Kalai, and Adam R. Klivans · 2008

Closest in time.