Fast Quantum Algorithms for Learning Linear Threshold Functions
In the authors' words
Linear threshold functions are , where the weight vector is a unit vector, is a threshold, and typically or . When , the LTF is called homogeneous, and we write . Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples. We give three positive results about learning LTFs: 1. Suppose we can make real-domain queries, meaning we can compute at any of our choice. We give a quantum algorithm that learns up to Euclidean error~ using membership queries and other gates. Then we have also learned up to error when is Gaussian. Classical algorithms need queries. 2. A homogeneous LTF on domain where has only nonzero entries of the same value, is the Majority function on the support of . Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns ) using queries. We give an exponential improvement, using queries. 3. Suppose we have a unitary that can produce (discretized) quantum examples under Gaussian measure, corresponding to . This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient Hermite transform of Jain et al.\ to learn homogeneous LTFs~ with error~ under the Gaussian distribution, using applications of and and other gates.
Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.