Fast Quantum Algorithms for Learning Linear Threshold Functions

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\mathrm{/}\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 $\mathrm{\Omega }(n\log (1\mathrm{/}\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\mathrm{/}4})$ queries. We give an exponential improvement, using $O(\log k)$ queries. 3. Suppose we have a unitary $U$ that can produce (discretized) \emph{quantum examples} under Gaussian measure, corresponding to ${\int }_x\sqrt{{\gamma }_n(x)}\mathrm{\mid }x⟩\mathrm{\mid }{f}_w(x)⟩dx$. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient \emph{Hermite transform} of Jain et al.\ to learn homogeneous LTFs~$f_w$ with error~$\epsilon$ under the Gaussian distribution, using $O(n^{1\mathrm{/}4}\mathrm{/}\sqrt{\epsilon })$ applications of $U$ and $U^{†}$ and $\tilde{O}(n^2\mathrm{/}{\epsilon }^4)$ other gates.