Fetching the paper…
Reading the bibliography…
$ \newcommand{\eps}{\varepsilon} $In learning theory, the VC dimension of a concept class $C$ is the most common way to measure its "richness." In the PAC model $$ \Theta\Big(\frac{d}{\eps} + \frac{\log(1/\delta)}{\eps}\Big) $$ examples are necessary and sufficient for a learner to output, with probability $1-\delta$, a hypothesis $h$ that is $\eps$-close to the target concept $c$.
On the uniform convergence of relative frequencies of events to their probabilities
V. Vapnik and A. Chervonenkis · 1971
Earlier work this paper cites.
Theory of pattern recognition
V. Vapnik and A. Chervonenkis · 1974
Earlier work this paper cites.
A theory of the learnable
L. Valiant · 1984
Earlier work this paper cites.
Learning from noisy examples
D. Angluin and P. Laird · 1988
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis dimension
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1989
Earlier work this paper cites.
A general lower bound on the number of examples needed for learning
A. Ehrenfeucht, D. Haussler, M. J. Kearns, and L. G. Valiant · 1989
Earlier work this paper cites.
Learning DNF under the uniform distribution in quasi-polynomial time
K. A. Verbeurgt · 1990
Earlier work this paper cites.
Decision theoretic generalizations of the PAC model for neural net and other learning applications
D. Haussler · 1992
Earlier work this paper cites.
A ‘pretty good’ measurement for distinguishing quantum states
P. Hausladen and W. K. Wootters · 1994
Earlier work this paper cites.
Toward efficient agnostic learning
M. J. Kearns, R. E. Schapire, and L. Sellie · 1994
Earlier work this paper cites.
Cryptographic limitations on learning Boolean formulae and finite automata
M. J. Kearns and L. G. Valiant · 1994
Earlier work this paper cites.
An introduction to computational learning theory
M. J. Kearns and U. V. Vazirani · 1994
Earlier work this paper cites.
Sharper bounds for Gaussian and empirical processes
M. Talagrand · 1994
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Classical information capacity of a quantum channel
P. Hausladen, R. Jozsa, B. Schumacher, M. Westmoreland, and W. K. Wootters · 1996
Earlier work this paper cites.
General bounds on the number of examples needed for learning probabilistic concepts
H. U. Simon · 1996
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
J. C. Jackson · 1997
Earlier work this paper cites.
Sample size lower bounds in PAC learning by algorithmic complexity theory
B. Apolloni and C. Gentile · 1998
Earlier work this paper cites.
Learning DNF over the uniform distribution using a quantum example oracle
N. H. Bshouty and J. C. Jackson · 1999
Cited alongside, same era.
Quantum fingerprinting
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf · 2001
Cited alongside, same era.
On quantum detection and the square-root measurement
Y. C. Eldar and G. D. Forney Jr · 2001
Cited alongside, same era.
Improved lower bounds for learning from noisy examples: An information-theoretic approach
C. Gentile and D. P. Helmbold · 2001
Cited alongside, same era.
Reversing quantum dynamics with near-optimal quantum and classical fidelity
H. Barnum and E. Knill · 2002
Cited alongside, same era.
Quantum DNF learnability revisited
J. C. Jackson, C. Tamon, and T. Yamakami · 2002
Cited alongside, same era.
New bounds on classical and quantum one-way communication complexity
R. Jain and S. Zhang · 2009
Later among the works it cites.
The geometry of quantum learning
M. Hunziker, D. A. Meyer, J. Park, J. Pommersheim, and M. Rothstein · 2010
Later among the works it cites.
An improved lower bound on query complexity for quantum PAC learning
C. Zhang · 2010
Later among the works it cites.
Quantum predictive learning and communication complexity with single input
D. Gavinsky · 2012
Later among the works it cites.
The quantum query complexity of learning multilinear polynomials
A. Montanaro · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Designing optimal quantum detectors via semidefinite programming
Y. C. Eldar, A. Megretski, and G. C. Verghese · 2003
Cited alongside, same era.
Equivalences and separations between quantum and classical learnability
R. Servedio and S. Gortler · 2004
Cited alongside, same era.
Improved bounds on quantum learning algorithms
A. Atıcı and R. Servedio · 2005
Cited alongside, same era.
Machine learning in a quantum world
E. Aïmeur, G. Brassard, and S. Gambs · 2006
Cited alongside, same era.
Optimal measurements for the dihedral hidden subgroup problem
D. Bacon, A. Childs, and W. van Dam · 2006
Cited alongside, same era.
The learnability of quantum states
S. Aaronson · 2007
Cited alongside, same era.
Quantum speed-up for unsupervised learning
E. Aïmeur, G. Brassard, and S. Gambs · 2013
Later among the works it cites.
Quantum algorithms for search with wildcards and combinatorial group testing
A. Ambainis and A. Montanaro · 2014
Later among the works it cites.
An optimal quantum algorithm for the oracle identification problem
R. Kothari · 2014
Later among the works it cites.
Analysis of Boolean Functions
R. O’Donnell · 2014
Later among the works it cites.
Understanding machine learning: From theory to algorithms
S. Shalev-Shwartz and S. Ben-David · 2014
Later among the works it cites.
N. Wiebe, A. Kapoor, and K. M. Svore · 2014
Later among the works it cites.
Quantum machine learning algorithms: Read the fine print
S. Aaronson · 2015
Later among the works it cites.
An almost optimal PAC algorithm
H. U. Simon · 2015
Later among the works it cites.
Complexity theoretic limitations on learning DNF’s
A. Daniely and S. Shalev-Shwartz · 2016
Closest in time.
The optimal sample complexity of PAC learning
S. Hanneke · 2016
Closest in time.
A. Kontorovich and I. Pinelis · 2016
Closest in time.
Quantum perceptron models, 2016
N. Wiebe, A. Kapoor, and K. M. Svore · 2016
Closest in time.
A survey of quantum learning theory, 2017
S. Arunachalam and R. de Wolf · 2017
Closest in time.