Fast Quantum Algorithms for Learning Linear Threshold Functions

Linear threshold functions are f w,θ(x)= sign(x,w-θ), where the weight vector w in R n is a unit vector, θ in R is a threshold, and typically x in R n or x in-1,1 n. When θ=0, the LTF is called homogeneous, and we write f w:=f w,0. 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 f w,θ(x) at any x in R n of our choice. We give a quantum algorithm that learns f w,θ up to Euclidean error ε using O((n/ε)) membership queries and (n) other gates. Then we have also learned f w,θ up to error O(ε) when x is Gaussian. Classical algorithms need Ω(n (1/ε)) queries. 2. A homogeneous LTF f w on domain-1,1 n where w has only k nonzero entries of the same value, is the Majority function on the support of w. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns f w) using O(k 1/4) queries. We give an exponential improvement, using O(k) queries. 3. Suppose we have a unitary U that can produce (discretized) quantum examples under Gaussian measure, corresponding to integral x sqrt γ n(x) x f w(x) dx. 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 f w with error ε under the Gaussian distribution, using O(n 1/4/sqrtε) applications of U and U and (n 2/ε 4) other gates.