A Quadratic Sample Complexity Reduction for Agnostic Learning via Quantum Algorithms

2023/10/24 by Daniel Z. Zanger, Zanger, Daniel Z.
Computer Science · #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2310.15576

openalex publication_date 2023/10/24 · openalex created_date 2023/10/26 · openalex updated_date 2026/07/28

Abstract

Using quantum algorithms, we obtain, for accuracy ε>0 and confidence 1-δ,0<δ<1, a new sample complexity upper bound of O((log(\frac1δ))/ε) as ε,δ→ 0 for a general agnostic learning model, provided the hypothesis class is of finite cardinality. This greatly improves upon a corresponding sample complexity of asymptotic order Θ((log(\frac1δ))/ε²) known in the literature to be attainable by means of classical (non-quantum) algorithms for an agnostic learning problem also with hypothesis set of finite cardinality (see, for example, Arunachalam and de Wolf (2018) and the classical statistical learning theory references cited there). Thus, for general agnostic learning, the quantum speedup in the rate of learning that we achieve with respect to these results is quadratic in ε^-1.

Related

• An efficient quantum algorithm for generative machine learning
• Optimal Quantum Sample Complexity of Learning Algorithms
• New Bounds on Quantum Sample Complexity of Measurement Classes
• An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
• On establishing learning separations between classical and quantum machine learning with classical data