Fast Quantum Algorithms for Learning Linear Threshold Functions

Abstract

Linear threshold functions are $f_{w,\theta }(x)=\text{sign}(⟨x,w⟩-\theta )$, where the weight vector $w\in {\mathbb{R}}^n$ is a unit vector, $\theta \in \mathbb{R}$ is a threshold, and typically $x\in {\mathbb{R}}^n$ or $x\in \{-1,1{\}}^n$. When $\theta =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,\theta }(x)$ at any $x\in {\mathbb{R}}^n$ of our choice. We give a quantum algorithm that learns $f_{w,\theta }$ up to Euclidean error $\epsilon$ using $O(\log (n/\epsilon ))$ membership queries and $\tilde{O}(n)$ other gates. Then we have also learned $f_{w,\theta }$ up to error $O(\epsilon )$ when $x$ is Gaussian. Classical algorithms need $\Omega (n\log (1/\epsilon ))$ 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(\log k)$ queries. 3. Suppose we have a unitary $U$ that can produce (discretized) quantum examples under Gaussian measure, corresponding to ${\int }_x\sqrt{{\gamma }_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 $\epsilon$ under the Gaussian distribution, using $O(n^{1/4}/\sqrt{\epsilon })$ applications of $U$ and $U^{†}$ and $\tilde{O}(n^2/{\epsilon }^4)$ other gates.

v2: In section 3, new optimal lower bound. Small improvements in the presentation