On the Cryptographic Hardness of Learning Single Periodic Neurons
Year: 2021

Abstract:
We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise. More precisely, our reduction shows that any polynomial-time algorithm (not necessarily gradient-based) for learning such functions under small noise implies a polynomial-time quantum algorithm for solving worst-case lattice problems, whose hardness form the foundation of lattice-based cryptography. Our core hard family of functions, which are well-approximated by one-layer neural networks, take the general form of a univariate periodic function applied to an affine projection of the data. These functions have appeared in previous seminal works which demonstrate their hardness against gradient-based (Shamir’18), and Statistical Query (SQ) algorithms (Song et al.’17). We show that if (polynomially) small noise is added to the labels, the intractability of learning these functions applies to all polynomial-time algorithms, beyond gradient-based and SQ algorithms, under the aforementioned cryptographic assumptions. Moreover, we demonstrate the necessity of noise in the hardness result by designing a polynomial-time algorithm for learning certain families of such functions under exponentially small adversarial noise. Our proposed algorithm is not a gradient-based or an SQ algorithm, but is rather based on the celebrated Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm. Furthermore, in the absence of noise, this algorithm can be directly applied to solve CLWE detection (Bruna et al.’21) and phase retrieval with an optimal sample complexity of d + 1 samples. In the former case, this improves upon the quadratic-in-d sample complexity required in (Bruna et al.’21).

heading: 1 Introduction
text: The empirical success of Deep Learning has given an impetus to provide theoretical foundations explaining when and why it is possible to efficiently learn from high-dimensional data with neural networks. Currently, there are large gaps between positive and negative results for learning, even for the simplest neural network architectures [61, 29, 14, 27]. These gaps offer a large ground for debate, discussing the extent up to which improved learning algorithms can be designed, or whether a fundamental computational barrier has been reached.
One particular challenge in closing these gaps is establishing negative results for improper learning in the distribution-specific setting, in which the learner can exploit the peculiarities of a known input distribution, and is not limited to outputting hypotheses from the target function class. Over the last few years, authors have successfully developed distribution-specific hardness results in the context of learning neural networks, offering different flavors. On one hand, there have been several results
⇤Equal contribution
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
proving the failure of a restricted class of algorithms, such as gradient-based algorithms [54, 52], or more generally Statistical Query (SQ) algorithms [33, 20, 57, 29, 17]. Notably, such results apply to the simplest cases, such as learning one-hidden-layer neural networks over the standard Gaussian input distribution [29, 17]. On the other hand, a different line of work has shown the hardness of learning two-hidden-layer neural networks for any polynomial-time algorithm by leveraging cryptographic assumptions, such as the existence of local pseudorandom generators (PRGs) with polynomial stretch [15]. Despite such significant advances, important open questions remain, such as whether the simpler case of learning one hidden-layer neural network over standard Gaussian input remains hard for algorithms not captured by the SQ framework. To make this question more precise, are non-SQ polynomial-time algorithms, which may inspect individual samples – such as stochastic gradient descent (SGD) [1] – able to learn one-hidden layer neural networks over Gaussian input? Understanding the answer to this question is a partial motivation of the present work.
A key technique for constructing hard-to-learn functions is leveraging “high-frequency” oscillations in high-dimensions. The simplest instance of such functions is given by pure cosines of the form f(x) = cos(2⇡ hw, xi), where we refer to w 2 Sd 1 as its hidden direction, and as its frequency. Such functions have already been investigated by previous works [57, 54, 52] in the context of lower bounds for learning neural networks. For these hard constructions, the frequency is taken to scale polynomially with the dimension d. Note that as the univariate function cos(2⇡ t) is O( )-Lipschitz, the function f is well-approximated by one-hidden-layer ReLU network of poly( )-width on any compact set (see e.g., Appendix G). Hence, understanding the hardness of learning such functions is an unavoidable step towards understanding the hardness of learning one-hidden-layer ReLU networks.
In this work, we pursue this line of inquiry, focusing on weakly learning the cosine neuron class over the standard Gaussian input distribution in the presence of noise. Our main result is a proof, via a reduction from a fundamental problem in lattice-based cryptography called the Shortest Vector Problem (SVP), that such learning task is hard for any polynomial-time algorithm, based on the widely-believed cryptographic assumption that (approximate) SVP is computationally intractable against quantum algorithms (See e.g., [49, 43, 19, 3] and references therein). Our result therefore extends the hardness of learning such functions from a restricted family of algorithms, such as gradientbased algorithms or SQ, to all polynomial-time algorithms by leveraging cryptographic assumptions. Note, however, that SQ lower bounds are unconditional because they are of an information-theoretic nature. Therefore, our result, which is conditional on a computational hardness assumption, albeit a well-founded one in the cryptographic community, and SQ lower bounds are not directly comparable.
The problem of learning cosine neurons with noise can be studied in the broader context of inferring hidden structures in noisy high-dimensional data, as a particular instance of the family of Generalized Linear Models (GLM) [45, 44]. Multiple inference settings, including, for example, the wellknown planted clique model [30, 5], but also GLMs such as sparse regression [23] exhibit so-called computational-to-statistical gaps. These gaps refer to intervals of signal-to-noise ratio (SNR) values where inference of the hidden structure is possible by exponential-time estimators but appears out of reach for any polynomial-time estimator. Following this line of work, we define the SNR of our cosine neuron learning problem to be the inverse of the noise level, and analyze its hardness landscape. As it turns out, weakly learning the cosine neuron class provides a rich landscape, yielding a computationalto-statistical gap based on a worst-case hardness guarantee. We note that this is in contrast with the “usual” study of such gaps where such worst-case hardness guarantees are elusive and they are mostly based on the refutation of restricted computational classes, such as Sum-of-Squares [10], low-degree polynomials [37], Belief Propagation [9], or local search methods [24].
Finally, we establish an upper bound for the computational threshold, thanks to a polynomial-time algorithm based on the Lenstra-Lenstra-Lovász(LLL) lattice basis reduction algorithm (see details in Section 3.3). Our proposed algorithm is shown to be highly versatile, in the sense that it can be directly used to solve two seemingly very different GLMs: the CLWE detection problem from cryptography and the phase retrieval problem from high-dimensional statistics. Remarkably, this method bypasses the SQ and gradient-based hardness established by previous works [54, 57]. Our use of the LLL algorithm to bypass a previously considered “computationally-hard” region adjoins similar efforts to solve linear regression with discrete coefficients [60, 26], [37, Sec. 4.2.1], as well as the correspondence retrieval problem [6], which includes phase retrieval as a special case. We show in Section 3.3 and Appendix F how our algorithms obtain optimal sample complexity for recovery in both these problems in the noiseless setting. An interesting observation is that in the latter case, the resulting algorithm, and also the very similar LLL-based algorithm by [6], improves upon AMP-based
algorithms [11] in terms of sample complexity, often thought to be optimal among all polynomial-time algorithms [41]. While our LLL algorithm can be seen as an appropriate modification of [6], our analysis employs different tools, leading to improved guarantees. More precisely, our analysis easily extends to distributions that are both log-concave and sub-Gaussian, as opposed to solely Gaussian in [6]. In addition, our algorithm incorporates an explicit rounding step for LLL, which allows us to determine its precise noise-tolerance (see details in Appendix F).

heading: 1.1 Related work
text: Hardness of learning from cryptographic assumptions. Among several previous works [34, 35] which leverage cryptographic assumptions to establish hardness of improper learning, most relevant to our results is the seminal work of Klivans and Sherstov [36] whose hardness results are also based on SVP. To elaborate, they show that learning intersections of halfspaces, which can be seen as neural networks with the threshold activation, is hard based on the worst-case hardness of GapSVP, a decision version (approximate) SVP. Our work differs, though, in several important aspects from theirs. First, and perhaps most importantly, our result holds over the well-behaved Gaussian input distribution over Rd, whereas their hardness utilizes a non-uniform distribution over the Boolean hypercube {0, 1}d. Second, at a technical level and in agreement with our continuous input domain and their discrete input domain, we take a different reduction route from SVP. Their link to SVP is the Learning with Errors (LWE) Problem [49], whereas our link in the reduction is the recently developed Continuous Learning with Errors (CLWE) Problem [13]. On another front, very recently, [15] presented an abundance of novel hardness results in the context of improper learning by assuming the mere existence of Local Pseudorandom Generators (LPRGs) with polynomial stretch. While the LPRG and SVP assumptions are not directly comparable, we emphasize that we rely on the worstcase hardness of GapSVP, whereas LPRG assumes average-case hardness. A worst-case hardness assumption is arguably weaker as it requires only one instance to be hard, whereas an average-case hardness assumption requires instances to be hard on average.
Lower bounds against restricted class of algorithms and upper bounds. As mentioned previously, a widely adapted method for proving hardness of learning is through SQ lower bounds [33, 12, 58, 20]. Among previous work, most closely related to our work is [57] and [54], who consider learning linear-periodic function classes which contain cosine neurons. By constructing a different class of hard one-hidden-layer networks, stronger SQ lower bounds over the Gaussian distribution, in terms of both query complexity and noise rate, have been established [29, 17]. Yet, for technical reasons, the SQ model cannot rule out algorithms such as stochastic gradient descent (SGD), since these algorithms can in principle inspect each sample individually. In fact, [1] carry this advantage of SGD to the extreme and show that SGD is poly-time universal. [7] establishes sharp bounds using SGD for weakly learning a single planted neuron, and reveals a fundamental dependency between the regularity of their dimension-independent activation function, which they name the “information exponent”, and the sample complexity. The regularity of the activation function has been leveraged in several works to yield positive learning results [31, 61, 27, 56, 4, 28, 21, 16]. Finally, statistical-to-computational gaps using the family of Approximate Message Passing (AMP) algorithms [18, 47] for the algorithmic frontier have been established in various high-dimensional inference settings, including proper learning of certain single-hidden layer neural networks [8], spiked matrix-tensor recovery [50] and also GLMs [11].
The LLL algorithm and statistical inference problems. For our algorithmic results, we employ the LLL algorithm. Specifically, our techniques are originally based on the breakthrough use of the LLL algorithm to solve a class of average-case subset sum problems in polynomial-time, as established first by Lagarias and Odlyzko [38] and later via a greatly simplified argument by Frieze [22]. While the power of LLL algorithm is very well established in the theoretical computer science [53, 39], integer programming [32], and computational number theory communities (see [55] for a survey), to the best of our knowledge, it has found only a handful of applications in the theory of statistical inference. Nevertheless, a few years ago, a strengthening of the original LLL-based arguments by Lagarias, Odlyzko and Frieze has been used to prove that linear regression with rational-valued hidden vector and continuous features can be solved in polynomial-time given access only to one sample [60]. This problem has been previously considered “computationally-hard” [23] and is proven to be impossible for the LASSO estimator [59, 25], greedy local-search methods [23] and the AMP algorithm [48]. In a subsequent work to [60], the suggested techniques have been generalized to the linear regression and phase retrieval settings under the more relaxed assumptions of discrete (and therefore potentially irrational)-valued hidden vector [26]. Our work is based on insights from
[60, 26], but is importantly generalizing the use of the LLL algorithm (a) for the recovery of an arbitrary unit continuous-valued hidden vector and (b) for multiple GLMs such as the cosine neuron, the phase retrieval problem, and the CLWE problem. However, for noiseless phase retrieval, we note that the optimal sample complexity of d+ 1 has previously been achieved by [6] using an LLL-based algorithm very similar to ours.

heading: 1.2 Main Contributions: the Hardness Landscape of Learning Cosine Neurons
text: In this work, we thoroughly study the hardness of improperly learning single cosine neurons over isotropic d-dimensional Gaussian data. We study them under the existence of a small amount of adversarial noise per sample, call it 0, which we prove is necessary for the hardness to take place. Specifically we study improperly (weakly) learning in the squared loss sense, the function f(x) = cos(2⇡ hw, xi), for some hidden direction w 2 Sd 1, from m samples of the form zi = f(xi) + ⇠i, i = 1, . . . ,m where xi i.i.d. ⇠ N(0, Id) and arbitrary |⇠i|  .
Information-theoretic bounds under constant noise. We first address the statistical, or also known as information-theoretic, question of understanding for which noise level one can hope to learn f(x) from polynomially in d many samples, by using computationally unconstrained estimators. Since the range of the functions f = fw is the interval [ 1, 1] it is a trivial observation that for any 1 learning is impossible. This follows because the (adversarial) noise could then produce always the uninformative case where zi = 0 for all i = 1, . . . ,m.
Our first result (see Section 3.1 for details), is a design and analysis of an algorithm which runs in O(exp(d log( / ))) time and satisfies the following property. For any smaller than a sufficiently small constant, the output hypothesis of the algorithm learns the function f with access to O(d log( / )) samples, with high probability. To the best of our knowledge, such an informationtheoretic result has not appeared before in the literature of learning a single cosine neuron. We consider this result essential and reassuring as it implies that the learning task is statistically achievable if is less than a small constant. Therefore, any hardness claim in terms of polynomial-time algorithms aiming to learn this function class is meaningful and implies a computational barrier.
Cryptographic hardness under moderately small noise. Our second and main result, presented in Section 3.2, is a reduction establishing that (weakly) learning this function class under any which scales at least inverse polynomially with d, i.e. d C for some constant C > 0, is as hard as a worst-case lattice problem on which the security of lattice-based cryptography is based on. Theorem 1.1 (Informal). Consider the function class F = {f ,w(x) = cos(2⇡ hx,wi) | w 2 S d 1
}. Weakly learning F over Gaussian inputs x ⇠ N(0, Id) under any inverse-polynomial adversarial noise when 2 p d and = 1/poly(d), is hard, assuming worst-case lattice problems are secure against quantum attacks.
The exact sense of cryptographic hardness used is that weakly learning the single cosine neuron under the described assumptions, reduces to solving a worst-case lattice problem, known as the Gap Shortest Vector Problem (GapSVP). The approximation factor of GapSVP obtained in our reduction, is not known to be NP-hard [2], but it is widely believed to be computationally hard against any polynomial-time algorithm, including quantum algorithms [43]. The reduction makes use of a recently developed average-case detection problem, called Continuous Learning with Errors (CLWE) [13] which has been established to be hard under the same hardness assumption on GapSVP. Our reduction shows that weakly learning the single cosine neuron in polynomial time, implies a polynomial-time algorithm for solving the CLWE problem (see Section 2 for the definition). The link here between the two settings comes from the periodicity of the cosine function, and the fact that the CLWE has an appropriate mod 1 structure, as well.
Interestingly, our reduction works for any class of function g(x) = ( hw, xi) where is a 1-periodic and O(1)-Lipschitz function and under 2 p d, generalizing the hardness claim much beyond the single cosine neuron. Moreover, our reduction shows that the computational hardness in fact applies to a certain position-dependent random noise model, instead of bounded adversarial noise (See Remark 3.5). Lastly, as mentioned above, we highlight that this is a (conditional) lower bound against any polynomial-time estimator, not just SQ or gradient-based methods.
Polynomial-time algorithm under exponentially small noise. We finally address the question of whether there is some polynomial-time algorithm that can weakly learn the single cosine neuron, in
the presence of potentially exponentially small noise. Notably, the current lower bound with respect to SQ [57] or gradient based methods [54] apply without any noise assumption per-sample, raising the suspicion that no “standard” learning method works even in the case = 0.
We design and analyze an algorithm for the single cosine neuron which provably succeeds in learning the function f = fw when  exp( Õ(d3)), and with access to only d+ 1 samples. Note that this sample complexity is perhaps surprising: one needs only one more sample than just receiving the samples in the “pure” linear system form hw, xii instead of cos(2⇡ hw, xii) + ⇠i. The algorithm comes from reducing the problem to an integer relation detection question and then make a careful use of the powerful Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm [40] to solve it in polynomial time. The integer relation detection allows us to recover the (unknown) integer periods naturally occuring because of the periodicity of the cosine, which then allows us to provably “invert” the cosine, and then learn the hidden direction w simply by solving a linear system.
The LLL algorithm is a celebrated algorithm in theoretical computer science and mathematics, which has rarely been used in the learning literature (with the notable recent exceptions [6, 60, 26]). We consider our connection between learning the single cosine neuron, integer relation detection and the LLL algorithm, a potentially interesting algorithmic novelty of the present work. We note that [13] likewise use the LLL algorithm to solve CLWE in the noiseless setting. When applied to CLWE, our algorithm, via a significantly more involved application of the LLL algorithm and careful analysis, improves upon their algorithm in terms of both sample complexity and noise-tolerance.
Application to noiseless phase retrieval: d+ 1 samples suffice. Notice that the cosine activation function loses information in two distinct steps: first it “loses” the sign, since it is an even function, and then it “loses” localisation beyond its period (fixed at [ 1/2, 1/2)). As a result, any algorithm learning the cosine neuron (such as our proposed LLL-based algorithm) can be immediately extended to solve the two separate cases, where one only loses the sign (which is known as the phase retrieval problem in high dimensional statistics) or only the localisation (which is known as the CLWE problem in cryptography). In particular, the noiseless cosine learning problem ‘contains’ the phase retrieval problem, where one is asked to recover an unknown vector w from measurements |hxi, wi|, since cos(2⇡ hw, xii) = cos(2⇡ |hxi, wi|). Therefore, as an immediate consequence of our algorithmic results, we achieve the optimal sample complexity of noiseless2 phase retrieval. As mentioned previously, this algorithmic result, while interesting and a consequence of our analysis for cosine learning, has already been established in the prior work [6] using a very similar LLL-based algorithm.
We note that achieving in polynomial-time the optimal sample complexity is perhaps of independent interest from a pure algorithm design point of view. While Gaussian elimination can trivially solve for w given d samples of the form hxi, wi where xi i.i.d. ⇠ N(0, Id), our algorithm shows that by “losing” the sign of hxi, wi one needs only one sample more to recover again w in polynomial-time. However, we remark that the LLL algorithm has a running time of O(d6 log3 M) [46]3, where d is the dimension and M is the maximum `2-norm of the given lattice basis vectors, which can relatively quickly become computationally challenging with increasing dimension despite its polynomial time complexity. We refer the reader to Appendix F for a formal statement of the phase retrieval problem and our results.

heading: 2 Definitions and Notations
text: Distribution-specific PAC-learning. We consider the problem of learning a sequence of realvalued function classes {Fd}d2N, each over the standard Gaussian input distribution on Rd, an instance of what is called distribution-specific PAC learning [35, 54]. The input is a multiset of i.i.d. labeled examples (x, y) 2 Rd ⇥ R, where x ⇠ N(0, Id), y = f(x) + ⇠, f 2 Fd, and ⇠ 2 R is some type of observation noise. We denote by D = Df the resulting data distribution. The goal of the learner is to output an hypothesis h : Rd ! R that is close to the target function f in the squared loss sense over the Gaussian input distribution. We say a learning algorithm is proper if it outputs an hypothesis h 2 Fd. On the other hand, we say a learning algorithm is improper if h is not necessarily in Fd [51]. We omit the index d, when the input dimension is clear from the context.
We denote by ` : R⇥R! R 0 the squared loss function defined by `(y, z) = (y z)2. For a given hypothesis h and a data distribution D on pairs (x, z) 2 Rd⇥R, we define its population loss LD(h)
2Or exponentially small noise; see Corollary F.1 for the precise statement 3The L2 algorithm by [46] speeds up LLL using floating-point arithmetic, but the running time still grows
faster than O(d5).
over a data distribution D by
LD(h) = E (x,y)⇠D [`(h(x), y)] . (1)
Definition 2.1 (Weak learning). Let ✏ = ✏(d) > 0 be a sequence of numbers, 2 (0, 1) a fixed constant, and let {Fd}d2N be a sequence of function classes defined on input space Rd. We say that a (randomized) learning algorithm A ✏-weakly learns {Fd}d2N over the standard Gaussian distribution if for every f 2 Fd the algorithm outputs a hypothesis hd such that for large values of d with probability at least 1
LDf (hd)  LDf (E[f(x)]) ✏ .
Note that E[f(x)] is the best constant predictor for the data distribution D = Df . Hence, we refer to LD(E[f(x)]) = VarZ⇠N(0,Id)(f(Z)), as the trivial loss, and ✏ as the edge of the learning algorithm.
From simplicity, we refer to an hypothesis as weakly learning a function class if it can achieve edge ✏ which is depending inverse polynomially in d.
Periodic Neurons. Let = (d) > 1 be a sequence of numbers indexed by the input dimension d 2 N, and let : R! [ 1, 1] be an 1-periodic function. We denote by F the function class
F = {f : Rd ! [ 1, 1] | f(x) = ( hw, xi), w 2 Sd 1} (2)
Note that each member of the function class F is fully characterized by a unit vector w 2 Sd 1. We refer such function classes as periodic neurons.
Cosine Learning. We define the cosine distribution on dimension d with frequency = (d), adversarial noise rate = (d), and hidden direction w 2 Sd 1 to be the distribution of samples of the form (x, z) 2 Rd ⇥ R, where xi.i.d.⇠ N(0, Id), some bounded adversarial noise |⇠|  , and
z = cos(2⇡ hw, xi) + ⇠. (3)
The cosine learning problem consists of weakly learning the cosine distribution, per Definition 2.1. This learning problem is the central subject of our analysis. Hence, we slightly abuse notation and denote the corresponding cosine function class by
F = {cos(2⇡ hw, xi) | w 2 S d 1 }. (4)
Continuous Learning with Errors (CLWE) [13]. We define the CLWE distribution Aw, , on dimension d with frequency = (d) 0, and noise rate = (d) 0 to be the distribution of i.i.d. samples of the form (x, z) 2 Rd ⇥ [ 1/2, 1/2) where x ⇠ N(0, Id), ⇠ ⇠ N(0, ) and
z = hx,wi+ ⇠ mod 1 . (5)
Note that for the mod 1 operation, we take the representatives in [ 1/2, 1/2). The CLWE problem consists of detecting between i.i.d. samples from the CLWE distribution or an appropriate null distribution. In the context of CLWE, we refer to the distribution N(0, Id)⇥ U([ 1/2, 1/2)) as the
null distribution and denote it by A0. Given = (d) and = (d), we consider a sequence of decision problems {CLWE , }d2N, indexed by the input dimension d, in which the learner is given samples from an unknown distribution D such that either D 2 {Aw, , | w 2 Sd 1}, and D = A0. The algorithm is asked to decide whether D 2 {Aw, , | w 2 Sd 1} or D = A0 in polynomial-time. Under this setup, we define the advantage of an algorithm as the difference between the probability that it correctly detects samples from D 2 {Aw, , | w 2 Sd 1}, and the probability that errs (decides “D 6= A0”) given samples from D = A0. We call the advantage negligible if it decays superpolynomially. For a more detailed setup of this problem, we refer the reader to Appendix B.
Bruna et al. [13] showed worst-case evidence that the CLWE problem is computationally hard even with inverse polynomial noise rate if 2 p d, despite its seemingly mild requirement of nonnegligible advantage. In fact, their evidence of computational intractability is based on worst-case lattice problems called the Gap Shortest Vector Problem (GapSVP) [42]. In particular, they showed that distinguishing a typical CLWE distribution, where the randomness is over the uniform choice of hidden direction w 2 Sd 1, from the null distribution is as hard as solving the worst instance of GapSVP. For a formal definition of the GapSVP, we refer the reader to Appendix B, but note that the (quantum) worst-case hardness of this lattice problems is widely-believed by the cryptography community [43] (See Conjecture 2.3).
Theorem 2.2 ([13, Corollary 3.2]). Let = (d) 2 (0, 1) and = (d) 2 p d such that / is polynomially bounded. Then, there is a polynomial-time quantum reduction from O(d/ )-GapSVP to CLWE , . Conjecture 2.3 ([43, Conjecture 1.2]). There is no polynomial-time quantum algorithm that solves GapSVP to within polynomial factors.
Weak learning and parameter recovery. Recall that every element of the function class F is fully characterized by the hidden unit vector w 2 Sd 1. Hence, one possible strategy towards achieving weak learning of the cosine distribution, could be to recover the vector w from samples of the form (3). The following lemma (proven in Appendix I) shows that given any w0 sufficiently close to w one can construct an hypothesis that weakly learns the function f(x) = cos(2⇡ hw, xi).
Proposition 2.4. Suppose = !(1). For any w0 2 Sd 1 with min{kw w0k22, kw + w0k22}  1/(16⇡2 2), the functions hA(x) = cos(2⇡ hA, xi), A 2 {w0, w} satisfy for large values of d that
Ex⇠N(0,Id)[`((hw(x), hw0(x))]  Varx⇠N(0,Id)[(hw(x))2] 1/12.
The LLL algorithm and integer relation detection. In our algorithmic result, we make use of an appropriate integer relation detection application of the celebrated lattice basis reduction LLL algorithm [40]. We say that for some b 2 Rn the vector m 2 Zn \ {0} is an integer relation for b if hm, bi = 0. We make use of the following theorem, and we refer the interested reader to the Appendix E for a complete proof and intuition behind the result. Theorem 2.5. Let n,N 2 N. Suppose b 2 (2 NZ)n with b1 = 1. Let also m 2 Zn be an integer relation of b. Then an appropriate application of the LLL algorithm with input b outputs an integer relation m0 2 Zn of b with km0k2 = O(2n/2kmk2kbk2) in time polynomial in n,N and log(kmk1kbk1).
Notation. Let Z denote the set of integers and R denote the set of real numbers. For a 2 R, We use Z a and R a for the set of integers at least equal to a, and for the set of real numbers at least equal to a, respectively. We denote by N = Z 1 the set of natural numbers. For k 2 N we set [k] := {1, 2, . . . , k}. For d 2 N, 1  p < 1 and any x 2 Rd, kxkp denotes the p norm ( Pd
i=1 |xi| p ) 1/p of x, and kxk1 denotes max1id |xi|. Given two vectors x, y 2 Rd the Euclidean
inner product is hx, yi := Pd
i=1 xiyi. By log : R+ ! R we refer the natural logarithm with base e. For x 2 Z and N 2 N we denote by (x)N := sgn(x)b2Nxc/2N . Throughout the paper we use the standard asymptotic notation, o,!, O,⇥,⌦ for comparing the growth of two positive sequences (ad)d2N and (bd)d2N: we say ad = ⇥(bd) if there is an absolute constant c > 0 such that 1/c  ad/bd  c; ad = ⌦(bd) or bd = O(ad) if there exists an absolute constant c > 0 such that ad/bd c; and ad = !(bd) or bd = o(ad) if limd ad/bd = 0. We say x = poly(d) if for some 0  q < r it holds ⌦(dq) = x = O(dr).

heading: 3 Main Results
text: In this section we present our main results towards understanding the fundamental hardness of (weakly) learning the single cosine neuron class given by (4). We present our results in terms of signal to noise ratio (SNR) equal to 1/ , where recall that > 0 is an upper bound on the level of adversarial noise ⇠ one may introduce at the samples given by (3). All proofs of the statements are deferred to the appendices of each subsection.
A key correspondence. At the heart of our main results are the following simple elementary equalities that hold for all v 2 R, and may help the intuition of the reader.
cos(2⇡(v mod 1)) = cos(2⇡v) (6) arccos(cos(2⇡v)) = 2⇡|v mod 1| , (7)
where in Eq (7), we recall that our mod 1 operation takes representatives in [ 1/2, 1/2).
An immediate outcome of these equalities, is a key correspondence between the labels of cosine samples and “phaseless” CLWE samples, where we reminder the reader that the notion of a CLWE sample is defined in (5). By (6), applying the cosine function to CLWE labels results in the cosine distribution with the same frequency, and hidden direction. Conversely, by (7), applying arccos to cosine labels results in an arguably harder variant of CLWE, in which the (mod 1)-signs of the labels are dropped, with again the same frequency and hidden direction. We say this “phaseless” variant of CLWE is harder than CLWE as we can trivially take the absolute value of CLWE labels to obtain these phaseless CLWE samples, and so an algorithm for solving phaseless CLWE automatically implies an algorithm for CLWE.
We have ignored the issue of additive noise for the sake of simplicity in the above discussion. Indeed, the amount of noise in the samples is a key quantity for characterizing the difficulty of these learning problems and the main technical challenge in carrying the reduction between learning single cosine neurons and CLWE. In subsequent sections, we carefully analyze the interplay between the noise level and the computational difficulty of these learning problems.

heading: 3.1 The Information-Theoretically Possible Regime: Small Constant Noise
text: Before discussing the topic of computational hardness, we address the important first question of identifying the noise levels under which some estimator, running in potentially exponential time, can weakly learn the class of interest from polynomially many samples. Note that any constant level of noise above 1, that is 1, would make learning impossible for trivial reasons. Indeed, as the cosine takes values in [ 1, 1] if 1 all the labels zi can be transformed to the uninformative 0 value because of the adversarial noise. One can naturally wonder whether any estimator can succeed at the presence of some constant noise level 2 (0, 1). In this section, we establish that for sufficiently small but constant > 0 weak learning is indeed possible with polynomially many samples by running an appropriate exponential-time estimator.
Towards establishing this result, we leverage Proposition 2.4, according to which to achieve weak lernability it suffices to construct an estimator that achieves `2 recovery of w or w with an `2 error O(1/ ). For this reason, we build an exponential-time algorithm that achieves this `2 guarantee.
Theorem 3.1 (Information-theoretic upper bound). For some constants c0, C0 > 0 (e.g. c0 = 1 cos(
⇡ 200 ), C0 = 40000) the following holds. Let d 2 N and let = (d) > 1, (d)  c0,
and ⌧ = arccos(1 )/(2⇡). Moreover, let P be data distribution given by (3) with frequency , hidden direction w, and noise level . Then, there exists an exp(O(d log( /⌧)))-time algorithm using O(d log( /⌧)) i.i.d. samples from P that outputs a direction ŵ 2 Sd 1 satisfying min{kŵ wk22, kŵ + wk 2 2}  C0⌧ 2/ 2 with probability 1 exp( ⌦(d)).
The following corollary follows immediately from Theorem 3.1, Proposition 2.4 and the elementary identity that arccos(1 ) = ⇥( p ) for small .
Corollary 3.2. Under the assumptions of Theorem 3.1 there exists some sufficiently small c1 > 0, such that if  c1 there exist a exp(O(d log( / )))-time algorithm using O(d log( / )) i.i.d. samples from P that weakly learns the function class F .
The proof of both Theorem 3.1 and Corollary 3.2 can be found in Appendix C.

heading: 3.2 The Cryptographically Hard Regime: Polynomially Small Noise
text: Given the results in the previous subsection, we discuss now whether a polynomial-time algorithm can achieve weak learnability of the class F for some noise level smaller than an inverse polynomial quantity in d, which we call an inverse-polynomial edge, per Definition 2.1. We answer this in the negative by showing a reduction from CLWE to the problem of weakly learning F to any inverse-polynomial edge. This implies that a polynomial-time algorithm for weakly learning F would yield polynomial-time quantum attacks against worst-case lattice problems, which are widely believed to be hard against quantum computers. As mentioned in the introduction, our reduction applies with any 1-periodic and O(1)-Lipschitz activation . We defer the proofs to Appendix D. Theorem 3.3. Let d 2 N, = !( p log d), = (d) 2 (0, 1). Moreover, let L > 0, let : R ! [ 1, 1] be an L-Lipschitz 1-periodic univariate function, and ⌧ = ⌧(d) be such that /(L⌧) = !( p log d). Then, a polynomial-time (improper) algorithm that weakly learns the function class
F = {f ,w(x) = ( hw, xi) | w 2 S d 1 } over Gaussian inputs xi.i.d.⇠ N(0, Id) under -bounded adversarial noise implies a polynomial-time algorithm for CLWE⌧, .
By the hardness of CLWE (Theorem 2.2) and our Theorem 3.3, we can immediately deduce the cryptographic hardness of learning the single cosine neuron under inverse polynomial noise. Corollary 3.4. Let d 2 N, = (d) 2 p d and ⌧ = ⌧(d) 2 (0, 1) be such that /⌧ = poly(d), and = (d) be such that /⌧ = !( p log d). Then, a polynomial-time algorithm that weakly learns the cosine neuron class F under -bounded adversarial noise implies a polynomial-time quantum algorithm for O(d/⌧)-GapSVP. Remark 3.5 (Robust learning under position-dependent random noise is hard). Robustness against advesarial noise in Theorem 3.3 is not necessary for computational hardness. In fact, the reduction only requires robustness against a certain position-dependent random noise. More precisely, for a fixed hidden direction w 2 Sd 1, the random noise ⇠̃ is given by ⇠̃ = ( hw, xi+ ⇠) ( hw, xi), where x ⇠ N(0, In) and ⇠ ⇠ N(0, ).

heading: 3.3 The Polynomial-Time Possible Regime: Exponentially Small Noise
text: In this section, in sharp contrast with the previous section, we design and analyze a novel polynomialtime algorithm which provably weakly learns the single cosine neuron with only d+1 samples, when the noise is exponentially small. The algorithm is based on the celebrated lattice basis reduction LLL algorithm and its specific application obtaining the integer relation detection guarantee described in Theorem 2.5. Let us also recall from notation that for a real number x and N 2 Z 1, we denote by (x)N := sgn(x)b2Nxc/2N . We establish the following result, proved in Appendix E. Theorem 3.6. Suppose that 1   dQ for some fixed Q > 0, and  exp( (d log d)3). Then Algorithm 1 with input (xi, zi)i=1,...,d+1 i.i.d. samples from (3) with frequency , hidden direction w and noise level , outputs w0 2 Sd 1 with
min{kw0 wk2, kw 0 + wk2} = O
✓ ◆ = 1 exp( ⌦((d log d)3)) ,
and terminates in poly(d) steps, with probability 1 exp( ⌦(d)). Moreover, if the algorithm skips the last normalization step, the output w0 2 Rd satisfies min{kw0 wk2, kw0 + wk2} = O ( ).
In particular, by combining our result with Proposition 2.4, one concludes the following result. Corollary 3.7. Suppose that !(1) = = poly(d) and  exp( (d log d)3). Then there exists a polynomial-in-d time algorithm using d + 1 samples from a single cosine neuron distribution (3), with frequency and noise level , that weakly learns the function class F .
Proof sketch of Theorem 3.6. For the purposes of the sketch let us focus on the noiseless case, explaining at the end how an exponentially small tolerance is possible. In this setting, we receive m samples of the form zi = cos(2⇡hw, xii), i 2 [m]. The algorithm then uses the arcosine and obtains the “phaseless” CLWE values z̃i which according to (7) satisfy for some unknown ✏i 2 { 1, 1},Ki 2 Z hw, xii = ✏iz̃i +Ki. Notice that if we knew the integer values of ✏i,Ki, since we know z̃i, the problems becomes simply solving a linear system for w. The algorithm then leverages the application of the powerful LLL algorithm to perform integer relation detection and identify the values of ✏i,Ki, as stated in Theorem 2.5. The way it does it is as follows. It first finds coefficients i, i = 1, 2, . . . , d+1
Algorithm 1: LLL-based algorithm for learning the single cosine neuron. Input: i.i.d. noisy -single cosine neuron samples {(xi, zi)}d+1i=1 . Output: Unit vector ŵ 2 Sd 1 such that min(kŵ wk, kŵ + wk) = exp( ⌦((d log d)3)). for i = 1 to d+ 1 do
zi sgn(zi) ·min(|zi|, 1) z̃i = arccos(zi)/(2⇡) mod 1
Construct a d⇥ d matrix X with columns x2, . . . , xd+1, and let N = d3(log d)2. if det(X) = 0 then
return ŵ = 0 and output FAIL Compute 1 = 1 and i = i(x1, . . . , xd+1) given by ( 2, . . . , d+1)> = X 1x1. Set M = 23d and ṽ = ( 2)N , . . . , ( d+1)N , ( 1z1)N , . . . , ( d+1zd+1)N , 2 N 2 R2d+2 Output (t1, t2, t) 2 Zd+1 ⇥ Zd+1 ⇥ Z from running the LLL basis reduction algorithm on the lattice generated by the columns of the following (2d+ 3)⇥ (2d+ 3) integer-valued matrix,
✓ M2N ( 1)N M2N ṽ 0(2d+2)⇥1 I(2d+2)⇥(2d+2) ◆
Compute g = gcd(t2), by running Euclid’s algorithm. if g = 0 _ (t2/g) /2 { 1, 1}d+1 then
return ŵ = 0 and output FAIL ŵ SolveLinearEquation(w0, X>w0 = (t2/g)z + (t1/g)) return ŵ/kŵk and output SUCCESS.
such that Pd+1
i=1 ixi = 0 which can be easily computed because we have d+ 1 vectors in Rd. Then using the definition of z̃i, the relation between the coefficient implies the identity
d+1X
i=1
✏i iz̃i + d+1X
i=1
Ki i = d+1X
i=1
ihxi, wi = 0. (8)
In particular, the ✏i,Ki are coefficients in an integer relation connecting the known numbers izi, i, i = 1, 2, . . . , d + 1. Now, an issue is that as one cannot enter the real numbers as input for the lattice-based LLL, the algorithm truncates the numbers to the first N bits and then hope that post-truncation all the near-minimal integer relations between these truncated numbers remain a (small multiple of) ✏i,Ki, a sufficient condition so that LLL can identify them based on Theorem 2.5. We establish that indeed this the case and this is the most challenging part of the argument. The argument is based on some careful application of the anticoncentration properties of low-degree polynomials (notice that the i are rational functions of xi by Cramer’s rule), to deduce that the numbers i, izi are in “sufficient general position”, in terms of rational independence, for the argument to work. We remark that this is a potentially important technical advancement over the prior applications of the LLL algorithm towards performing such inference tasks, such as for average-case subset sum problems [38, 22] or regression with discrete coefficients [60, 26] where the corresponding i, izi coefficients are (truncated) i.i.d. continuous random variables in which case anticoncentration is immediate (see e.g. [60, Theorem 2.1]). The final step is to prove that the algorithm is able to tolerate some noise level. We establish that indeed if N = ⇥̃(d3) then indeed the argument can still work and tolerate exp( ⇥̃(d3))-noise by showing that the near-minimal integer relations remain unchanged under this level of exponentially small noise.
Remark 3.8 (CLWE with exponentially small noise). Notice that the detection problem in CLWE (5) reduces to the cosine learning problem (3). Indeed, if ž = hx,wi + ⇠̌ mod 1 2 [ 1/2, 1/2) is a CLWE sample, then z = cos(ž) satisfies
z = cos(2⇡ hx,wi) + ⇠ ,
with |⇠|  2⇡ |⇠̌|. Algorithm 1 and the associated analysis Theorem 3.6 thus improve upon the exact CLWE recovery of [13, Section 6] in two aspects: (i) it requires d+ 1 samples as opposed to d2; and (ii) it tolerates exponentially small noise.
Acknowledgments and Disclosure of Funding
We thank Oded Regev, Ohad Shamir, Lenka Zdeborová, Antoine Maillard, and Afonso Bandeira for providing helpful comments. We also thank Daniel Hsu for pointing out the relevant prior work [6]. MS and JB are partially supported by the Alfred P. Sloan Foundation, NSF RI-1816753, NSF CAREER CIF-1845360, and NSF CCF-1814524. IZ is supported by the CDS Moore-Sloan Postdoctoral Fellowship.

Review summaries:
The first line of the abstract nicely summarises the work and I cannot summarise this any better.  "We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise".  The goal is to learn w using samples (x, cos(2 \pi \gamma <w, x>)+noise) where x~N(0, I_d). The noise considered is adversarial. Learning under large noise is not possible information theoretically. The authors give a discussion around their main result that includes an LLL based learning algorithm for the case when the noise is small. The main cryptographic reduction is for medium noise case and is through the CLWE (Continuous Learning with Errors) problem.

 The paper studies the problem of weakly learning single cosine functions (one periodic neuron) when samples come from a gaussian distribution, and in the presence of inverse polynomial amounts of noise. The main result shows that there is no polynomial time algorithm for this learning task under the cryptographic assumption that the Shortest Vector Problem is hard for quantum algorithms. In contrast, if the amount of noise is inverse exponentially small, the paper provides an efficient algorithm for learning. 

This paper considers a learning problem of the following form: given noisy labeled examples $(x, z)$ where $x \sim N(0, I)$ and $z = \cos(2\pi \gamma \langle w, x \rangle) + \xi$ (here $|\xi| \leq \beta$ is adversarial, additive, bounded noise), learn the hidden parameter $w$ (or at least weakly learn the mapping in terms of square loss). Thus $z$ is the (noisy) output of a single neuron with a periodic activation under Gaussian inputs. The main results are: - In the "moderate noise" $\beta = 1/\text{poly}(d)$ regime, a reduction showing that a learner for this problem could solve continuous LWE in a regime believed to be hard. - In the "small noise" $\beta = \exp(-d)$ regime, a novel efficient learning algorithm using LLL-based integer relation detection.  As one consequence, the hardness profile of this problem with respect to the noise rate $\beta$ exhibits interesting computational-to-statistical phase traditions / gaps.