On the Cryptographic Hardness of Learning Single Periodic Neurons
Authors: Min Jae Song
Ilias Zadik
Joan Bruna
Venue: NeurIPS 2021 Poster (2021)
Keywords: Learning with Errors
computational learning theory
lattice algorithms
cryptography
computational-to-statistical gap

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\'asz (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).

On the Cryptographic Hardness of Learning Single Periodic Neurons
Min Jae Song" Courant Institute New York University minjae. song@nyu.co edu edu
Ilias Zadik" Department of Mathematics Massachusetts Institute of Technology
Joan Bruna
Courant Institute
Center for Data Science New York University bruna@cims nyu. edu
edu
Abstract
We show simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the pres- ence of noise. More precisely, reduction shows that any polynomial-time algorithm (not necessarily gradient-based) for learning such functions under small noise implies 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-approximmted by one-layer neural networks, take the general form of a univariate periodic function applied to an affine projection the data. These functions have appeared in previous seminal works which demonstrate their hardness against gradient- basedd (Shamir' 18), and Statisti- cal 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 algorithmss, beyond gradient-bar based and SQ algorithms, under the aforementioned cryptographic assumptions. Moreover, we demonstrate the necessity of noise for learning certain families of such functions under exponentially small adversarial noise. Our proposed algorithm is not gradient- based or an SQ algorithm, but is rather based on the celebrated algorithm. Furthermore, in the absence of noise, this algorithm can be directly applied to solve CLWE detection (Bruna et al. 1l) and phase retrieval with an optimal sample complexity of + 1 samples. In the former case, this improves upon the quadratic-in in-d sample complexity required in (Bruna et al. 21).
hardness result by designing a polynomial--in
algorithm
(LLL) lattice basis reduction
Introduction
The empirical success of Deep Learning has given an impetus to provide theoretical foundations explaining when and why it 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
4 27] These gaps offer 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.
29
One particular challenge in closing these gaps is establishing negative results for improper learning the distribution-speeiicc 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-Se -eeecfffe hardness results in the context of learning neural networks, offering different flavors. On one hand, there have been several results
Equua contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

proving the failure of a restricted class of algorithms, such as gradient-based algorithms [54 52 or more generally Statistical Query (SQ) algorithms
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 [T.. Despite such significant advances, important open questions remain, such as whether the simpler case of learning one midden-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 -ime algorithms, which may inspect individual samples - such as stochastic gradient descent (SGD) [ 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.
+ 20
57 29
A key technique for constructing hard-to-learn functions is leveraging "high-frequens in high-dimensions. The simplest instance of such functions is given by pure cosines of the form f(x) = (2s 2z)), where we refer to E St-1 as its hidden direction, and 7y as its frequency. Such functions have already been investigated by previous works 157 54 52] in the context of lower bounds for learning neural networks. For these hard constructions, the frequency Ty is taken to scale polynomially with the dimension d. Note that as the univariate function y2 is (07y)-(ischhit the function f is -ell-oppro by mne-hidden-laye ReLU network of poly( 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- one-hidden www-hhhddddn-eae layer ReLU networks.
oscillations
any
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 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-beliveed cryptographic assumption that (approximate) SVP is computationally intractable against quantum algorithms (See e.g..
and references therein). Our result therefore extends the hardness of learning such functions from a restricted family of algorithms, such as gradient- based 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 -theorrtttttc nature. Therefore, our result, which is conditional on a computational hardness assumption, albeit well-founded one in the cryptographic community, and SQ lower bounds are not directly comparable.
49
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 Multiple inference settings, including, for example, the well- but also GLMs such as sparse regression 23 exhibit so-called computational-to--s -o-ttaattt-----cccaaa-l gaps. These gaps refer to intervals of hignal-to-nois ratio (SNR) values where inference of the hidden structure is possible by exponential
Linear Models (GLM) 45 44
known planted clique model
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 rich landscape, yielding computational. to-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-Squaree [IO,, low-degree polynomials 37
Belief Propagation Y or local search methods 24
Finally, we establish an upper bound for the computational threshold, thanks to a polynomial -imee monstra-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 GLMMs the CLWE detection problem from cryptography and the phase retrieval problem from high-dimensional statistics. Remarkably, this method bypasses the SQ and brasee hardness established by previous works
algorithm based on the
(54] 57 Our
use of the LLL algorithm to bypass a previously considered "computationally-nna
region adjoins 37 Sec. 4.2.1], as well as
similar efforts to solve linear regression with discrete coefficients 60 26
the correspondence retrieval problem K. which includes phase retrieval as a special case. We show in Section 3.3 and Appendix [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 A.MP-based
2

---

algorithms in terms of sample complexity, often thought to be optimal among all polynomial-timg algorithms 11 While our LLL algorithm can be seen as an appropriate modification of [ our analysis employs different tools, leading to improved guarantees. More precisely, our analysis easily extends to distributions that are both log-coneave 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
1.1 Related work
Hardness of learning from cryptographic assumptions. Among several previous works K 35 which leverage cryptographic assumptions to establish hardness of improper learning, most relevant to our results is the seminal work of Klivans and Sherstov RC whose hardness results also based on SVP. To elaborate, they show that learning intersections of halfspaccs,, 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-behane Gaussian input distribution over IRd, whereas their hardness utilizes a non-uniform distribution over the Boolean hypereube {0, J. 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, [ 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 worst- case hardness of GapSVP, whereas LPRG assumes average-case hardness. A worst-case hardness assumption is arguably weaker requires only one instance to be hard, whereas an average- 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 periodde 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 22 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, | carry this advantage of SGD to the extreme and show that SGD poly-time universal. M establishes sharp bounds using SGD for weakly learning single planted neuron, and reveals a fundamental depen- dency between the regularity of their dimension-inee dimension--nddeeedden 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 [II 61 27 [56 4 28, 21 [6]. Finally, algorithms [8 47
to-copuutaiionl gaps using the family of Approximate Message Passing (AMP) for the algorithmic frontier have been established in various high-dimensional
inference settings, including proper learning of certain single-hidden layer neural networks [ spiked
matrix-tensor recovery (50) and also GLMS [T.
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 (2 While the power of L.L. algorithm is very well established in the theoretical computer science 53 39).
integer programming 3 and computational number theory communities (see [ for 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-valus hidden vector and continuous features can be solved in polynomial-tin time given access only to one sample [6). 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 2 and the AMP algorithm 48). In a subsequent work to 600) the suggested techniques have been generalized to
the linear regression and phase retrieval settings under the more relaxed assumptions of discrete (and therefore potentially siatiionll-valucee hidden vector (26]. Our work is based on insights from
3

---

but is importantly generalizing the use of the LLL algorithm (a) for the recovery of an arbitrary unit continuous-values 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 + has previously been achieved by G using an L.LL-based algorithm very similar to ours.
60 26.
1.2 Main Contributions: the Hardness Landscape of Learning Cosine Neurons
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 B 2 O, 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()) = ( (w, x), for some hidden direction w E 5 from y samples of the form Lid. A = (2x) + E. = =1...., where x; ~ (0,, Ia) and arbitrary |&x1 S 3.
Information- theoretic bounds under constant noise. We first address the statistical, also known as informationntheorettie question of understanding for which noise level / one can hope to learn fxx from polynomially in d many samples, by using computationally unconstrained estimators. Since the range of the functions f = fm is the interval [-1, 1] it is a trivial observation that for any learning is impossible. This follows because the (adversarial) noise could then produce always the uninformative case where 2; = 0 for all 1,..., m..
Our first result (see Section 3.1 for details), is design and analysis of algorithm which runs in ((xxp(d log(3/3)) time and satisfies the following property. For any smaller than a suffi- ciently small constant, the output hypothesis of the algorithm learns the function f with access to Old (olo(()))) samples, with high probability. To the best of our knowledge, such an information- theoretic result has not appeared before in the literature of learning single cosine neuron. We consider this result essential and reassuring as it implies that the learning task is statistically achiev- able if 3 is less than 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 i.e. B 2 d'C for some constant C 0, is as hard as a worst-case lattice problem on which the security of auttice-based cryptography is based on.
Theorem 1.1 (Informal). Consider the function class F.,- = (x), = cos(2T7(2, w)) | w E (d-1). Weakly learning F. over Gaussian inputs I ~ N(0, Ia) under any inverse-polynoiil adversarial noise when " 2 2 and B = 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 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 < The reduction makes use of a recently developed average-case detection problem, called Continuous Learning with Errors (CLWE) [33 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 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 structure, as well.
Interestingly, our reduction works for any class of function g(x) = o(y(w, x)) where ş is a 1-periodic and ((1) function and under 7 2 2/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 (conditional) lower bound against any polynomial-tin -imee estimator, not just SQ or gradient- based methods.
Polynomial-timm 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 3 = 0.
We design and analyze an algorithm for the single cosine neuron which provably succeeds in learning the function f fn when 3 S exp(-o(d")) 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 (w,a::) instead of cos(277y(u, xx)) + &.- The algorithm comes from reducing the problem to an integer relation detection question and then make a careful use of the powerful Lenstra--enstra- -ovászz (LLL) lattice basis reduction algorithm [+0 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 linear system.
The LLL algorithm is celebrated algorithm in theoretical computer science and mathematics, which has rarely been used in the learning literature (with the notable recent exceptions [6] 60] (6)). 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 [3] likewise use the LLL algorithm 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 terms of both sample complexity and noise-tolerance.
Application to noiseless phase retrieval: d ++1 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 asked to recover an unknown vector w from measurements K(, w)), since (2 (w, ,.)) = cos(2 w²) ). Therefore, as an immediate consequence of our algorithmic results, we achieve the optimal sample complexity of noiseless
phase retrieval. As mentioned previously, this algorithmic result, while interesting and 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
given d samples of the form (I;; w) where 2; (0, Ia). our algorithm shows that by "losing" the sign of (I:, w) 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 (d log M) 46 where d is the dimension and M is the maximum l2- (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 formal statement of the phase retrieval problem and results.
2 Definitions and Notations
Distributionnsspecffi PAC-learning. We consider the problem of learning a sequence of real- valued function classes {Fa) each over the standard Gaussian input distribution Rd an instance of what is called distribution-specifee PAC learning B5 54) The input is a multiset of ii.d. labeled examples (sr, y) E IRd x RR where
f Fa. and & E IR. is some type of observation noise. We denote by D = D, the resulting data distribution. The goal of the learner is to output an hypothesis h: Rd + R that is close to the target function I in the squared loss sense over the Gaussian input distribution. We say learning algorithm is proper if it outputs an hypothesis h E Fa- On the other hand, we say a learning algorithm is improper if h is not necessarily in Fd [5T]] We omit the index d, when the input dimension is clear from the context.
N f())
We denote by &: IR x R - R2o the squared loss function defined by Ely, 2) = (y - 2)2. For a given hypothesis and a data distribution on pairs (ar, 2) E d x I, we define its population loss Ln(h)
"rr exponentially small noise: see Corollary for the precise statement
'The L algorithm by 4ol speeds up LLL using toint arithmetic,, but the running time still grows faster than (dd).
5

---

Comp-to-Statistical Gap
Crypto Hard
Polynomial-Time Possible
Impossible
O(1)
poly(d) d))
exp((dlog d)²)
SNR & 3
Figure 1: Our results at glance for weakly learning the class Fa.. Section 3.1
describes information-
theoretical limits, Section 5.2 presents the reduction from CLWE, while Section 3.3 introduces an efficient algorithm based on LLL.
over data distribution D by
LD(h)
E [((M)))))) (a.0)~
(1)
Definition 2.1 (Weak learning). Let 6 6 c(d) 0 be sequence of numbers, å E (0, 1) fixed constant, and let {FaJaen be sequence of function classes defined on input space Rd We say that a (randomized) learning algorithm A e-weakly learns {Falden over the standard Gaussian distribution if for every f E Fa the algorithu outputs hypothesis ha such that for large values of d with probability at least
LD, (ha) LD, (E(f(())
Note that [ is the best constant predictor for the data distribution D = Dy- Hence, refer [n(E(((>)) = Varz-N(o.1a) as the trivial loss, and e as the edge of the learning algorithm.
From simplicity, we refer an hypothesis as weakly learning a function class it can achieve edge which is depending inverse polynomially in d.
Periodic Neurons. Let 7 (dd)= be a sequence of numbers indexed by the input dimension d E N, and let R + 1, be 1- 1-periodic function. We denote by F the function class
F ( R [-1, f(x) = ((>(w,)))) E Std Sdd11
(2)
Note that each member of the function class Fe is fully characterized by a unit vector w E Sd-1 We refer such function classes periodic neurons.
Cosine Learning. We define the cosine distribution on dimension d with frequency 7 7(d).
adversarial noise rate B(d), and hidden direction E S to be the distribution of samples of the form (Ir, 2) E Rd R. where x ~ N(0, Ia), some bounded adversarial noise [<] < {3 and
z = (2 x)) +
(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
Fyy = {cos((2r)(u x)) w E 5d-1).
(4)
Continuous Learning with Errors (CLWE) [3] We define the CLWE distribution Aw. dimension d with frequency 7 = 7d) 2 0, and noise rate 3 = 3(d) 2 0 to be the distribution of i.i.d. samples of the form (ar, 2) E RRd x [ 1/2, 1/2) where x N(0, Ta). N(O,, 3) and
72, w) + mod 1.
(5)
Note that for the mod operation, we take the representatives in 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 (0, La) U[-11/2 1/2)) the

---

null distribution and denote it by Ag. Given = y(d) and 8 = ((d), we consider a sequence of decision problems 3 indexed by the imput dimension d, in which the learner given samples from an unknown distribution such that either D E (Av.3.7
E 5d-1), and D Ag- The algorithm is asked to decide whether E {Aw.8.7 w S } or D Ay 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 {Am.8.7 (decides "D a Ao") given samples from D> = Ap. We call the advantage negligible if it decays superpolynomially. For a more detailed setup of this problem, we refer the reader to Appendix [
E 1d
}. and the probability that errs
I3] showed worst-case evidence that the CLWE problem is computationally hard even with inverse polynomial noise rate 33 if 7 2 2vd, despite its seemingly mild requirement of non- negligible advantage. In fact, their evidence of computational intractability is based on worst-case lattice problems called the Gap Shortest Vector Problem (GapSVP) E2]. In particular, they showed that distinguishing rypical CLWE distribution, where the randomness is over the uniform choice of hidden direction w E 5 from the null distribution is as hard as solving the worst instance of GapSVP. For 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 iidely-believed by the cryptography community 4
Bruna et al.
(See Conjecture 2.3
Theorem 2.2 (13 Corollary 3.2)). Let B = B(d) E (0, 1) a -d) > 2 such that 7/ is polynomially bounded. Then, there is a polynomial-tin time quantum reduction from O(d/3) GaaPSP
to CLWE B.y
Conjecture 2.3 [ Conjecture 1.2)). There is no polynomial-tins quantum algoritlu that solves GapSVP to within polynomial factors.
Weak learning and parameter recovery. Recall that every element of the function class Fry is fully characterized by the hidden unit vector w 5 Hence, one possible strategy towards achieving weak learning of the cosine distribution, could be to recover the vector w from samples of the form f The following lemma (proven in Appendix (] shows that given any w/ sufficiently close to w one can construct an hypothesis that weakly learns the function f(x) = cos(2 x)).
Proposition 2.4. Suppose fy
w().. For any w/ S with min [|w w w|w w w(1l2) S
1/(167²^²), ) the functions (z))) = c2 (A, A)) A (w', satisfy for large values of d that
((hoo)))))((((h))))))))))))))) lw (x)) S Var
1/12.
The LLL algorithm and integer relation detection. In algorithmic result, make use of an appropriate integer relation detection application of the celebrated lattice basis reduction LLL. algorithm 44 We say that for some b E IR" the vector E Zn {0) is an integer relation for b if (m, b) 0. We make use of the following theorem, and we refer the interested reader to the
Appendix B for a complete proof and intuition behind the result.
Theorem 2.5. Let n,
N. Suppose b E (2- (2-Nz)" with b 1. Let also m. E 2nd be an integer relation of b. Then an appropriate application of the LLL algorithm with input b outputs an integer relation m' E nn of b with ||m']| 0(2 / in time polynomial in n, N and log([Im)lloe bb]loo))
Notation. Let E denote the set of integers and E denote the set of real numbers. For a E R, We use Zza and 22 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 = Σ2ι the set of natural numbers. For E N we set [k] := (1.2...., .k.. For d N, S p < dc and any x E Idd, ||>/[| denotes the pono E (///))// of x, and || denotes maxigigd |a:]] Given two vectors x, y E I2d the Euclidean inner product (a. = Ed Feli. By log R - we refer the natural logarithm with Throughout the paper we use the standard asymptotic notation, o, o.w, O, 0, 2 for comparing the growth of two positive sequences (a.)deN and (ba)dex: we say aa ((ba) if there an absolute constant e >> such that 1/c S da/ba S <. aa M(ba) or ba O(az) if there exists an absolute constant >> 0 such that aa/ba 2 e; and ag = (haa) or ba = o(aa) if lima as/ba = We say x = poly(d) if for some 0 S 9 < r it holds 2(d')= x O(d").
base e. For E Z and N E N we denote by (æ) := sgu(z)[2"x1//2)
7

---

3
Main Results
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/8, where recall that B >> is an upper bound on the level of adversarial noise & one may introduce at the samples given by 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 E R, and may help the intuition of the reader.
cos(2 mod 1)) = cos(22V)
(6)
arccos(cos((TrT)) 2 |v mod 1/,
where in Eq 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 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 s--iinss of the labels are dropped, with again the same frequency and hidden direction. We say this "phaseless" variant of CLWE is harder than CLWE these phaseless CLWE samples, and so an algorithm for solving phaseless CLWE automatically implies an algorithm for CLWE.
sample is defined in 5 By o6
can trivially take the absolute value of CLWE labels to obtain
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.
3.1 The Information- Information-Theorticaall Theoretically Possible Regime: Small Constant Noise
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- if 3 2 all the labels 2; can be transformed to the uninformative 0 value because of the adversarial noise. One can naturally wonder whether any estimator can succeed the presence of some constant noise level 8 E (0, 1). In this section, we establish that for sufficiently small but constant 8 > 0 weak learning is indeed possible with polynomially many samples by running an appropriate exponential-tne -time estimator.
Towards establishing this result, we leverage Proposition according to which to achieve weak lernability it suffices to construct an estimator that achieves & recovery of w or -w with an lg error 0(17)). For this reason, we build exponential-tine -imee algorithm that achieves this & guarantee.
Theorem 3.1 (Information-theontt 1- cos( 200 ), Cu = 40000) the following holds. Let d E N and let y 7(d) > 1, B(d) S co. and r arccos(1 (1 5)/(2n] Moreover, let P be data distribution given by B with frequenc % hidden direction w. and noise level 3. Then, there exists an exp (dd((o(())) (T)) -time algorithm
upper bound). For some constants co. Co > 0 (e.g. co
using O (l log(r/////// /T) i.i.d. samples from P that outputs a direction v E Sd satisfying min{]]
w| 10
{ S Cor2/ /72 with probability ex)(-S(dd))
The following corollary follows immediately from Theorem identity that arccos(1 - 3) O(VB) for small B.
3.1 Proposition
2.4 and the elementary
Corollary 3.2. Under the assumptions of Theorem 3. there exists some sufficiently small e₁ > 0, such that if 3 S ei there exist a exp( (d log(r/ B)])) -time algorithm using O(dlog(7/33 i.dd samples from P that weakly learns the function class F,.
The proof of both Theorem and Corollary 3.2 can be found in Appendix C
8

---

3.2 The Cryptographically Hard Regime: Polynomially Small Noise
Given the results in the previous subsection, we discuss now whether a polynomial-time algorithm can achieve weak learnability of the class Fy for some noise level 3 smaller than inverse polynomial quantity in d, which we call an inverse- polesommll 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-polyy porysssill edge. This implies that a polynomial- would yield polynomial-timg 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 ((1)-Lipschizz activation Φ. We defer the proof' to Appendix D
algorithm for weakly learning F,
Theorem 3.3. Let d E N. 7 = w( Vlog d), ((d) E (0, 1). Moreover, let L > O, let Φ R + [-1,]] be an L-Lipschitz 1-periodic univariate function, and T r(d) be such that (/T w(Vlog d). Then, a polynomial-time (improper) algorithm that weakly learns the function class F = (z)))(z)= = 6(7(w,, x)) |w E E over Gaussian imputs x Lid. (0,, Ta) under 3-bounded adversarial noise implies polynomial-time algorithm for CIWEE,7
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 E N. 7 = (dd 2 2vd and 7(d) E (0, be such that 7/t = poly(d), and 3 = (d) be such that 3/T = w( /log d). Then, a polynomial algorithm that weakly learns the cosine neuron class F-, under 3-bounded adversarial noise implies polynomial time quantum algorithm for GapSSP
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 random noise. More precisely, for a
only requires robustness against a certain fixed hidden direction w E sd-1, the random noise & is given by & (6 + E) - @(r(W,, (.((W,))) x)),
where I (0, In) and & ~ (0, B).
3.3 The Polynomial- Timee Possible Regime: Exponentially Small Noise
In this section, in sharp contrast with the previous section, we design and analyze a novel polynomial- time 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.3 Let us also recall from notation that for a real number x and N E Z>1, , we denote by (z)N == sgn (2)22>)2_///))
We establish the following result, proved in Appendix
Theorem 3.6. Suppose that 1 S S dº for some fixed Q 0, and B S exp(- d)²). Then with input (I,, 2,) =.);=1....411 i.dd samples from 3 with frequency y, hidden direction w and noise level B, outputs w' E Sdd11 with
Algorithm D
min(llw' - w112, Il + w||l)] =0 (0
-eeppp exp(-S2((dlog d)²)),
and terminates in poly(d) steps, with probability 1- ex-p((((((()) Moreover, the algorithm skips the last normalization step, the output w' E TRdd satisfies min(]lw: - -w1l2,,11 1|w' + + [2]] = 0 (3).
In particular, by combining result with Proposition 2.4 one concludes the following result.
Corollary 3.7. Suppose that w(1) 7 = (oly(d) and 3 < exp(-(d log d)²). Then there exists
polynomial-ine time algorithm using d samples from single cosine neuron distribution B with frequenc y and noise level B, 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, explain- ing at the end how an exponentially small tolerance is possible. In this setting, we receive m samples of the form 2; (2s(2 2x)), E [m]. The algorithm then uses the arcosine and obtains the "phaseless" " CLWE values 2 which according to ? satisfy for some unknown E 1-,,1), K; E Z (w, x;) = ह + K,. Notice that if we knew the integer values of e,, K,, since we know ž,, the prob- lems becomes simply solving a linear system for w. The algorithm then leverages the application of the powerful I.I.I algorithm to perform integer relation detection and identify the values of 6; K,, as
stated in Theorem 2.5 The way it does it is as follows. It first finds coefficients A i = 1, 1,2, ... d

---

Algorithm 1: LLL-bbsed algorithm for learning the single cosine neuron.
Input: i..dd noisy 7-Sinele cosine neuron samples ((zi, =))]==
Output: Unit vector úi E Sd-1 such that min([ - w|l. || + +lll) exp( d)²)).
for i 1 to d + do
2, - sgm(2 (.) min(
(x.coos(2)/(e)
mod 1
Construct a d x matrix X with columns T2,... Td41, and let N dlolo d
det(X) then
L return v and output FAIL
Compute 2 and A, A( [L...... .... Fd+1) given by (A2,.... (4t11) = x-11-00 21.
Set M 23d and 0 ((22) N...., (Ae+1)N, (AI2)),, (Aa+1 2 RR2++2
Output (t,, t2,t) E Zd+1 1 Zd+1 from running the LLL basis reduction algorithm on the lattice generated by the columns of the following (2d 3) x (2d - 3) integer-valued matrix,
M2 (A1)
M2N
0(2d+2)x1
(22+2)x(24+2)
Compute g gtd( by running Euclid's algorithm. if g = 0 (t2/9) & {-1, 1) 1 then
L return v and output FAIL
à + Sigratinn (w', X =
return // and output SUCCESS.
such that > Di-1 Ar2; = 0 which can be easily computed because we have d + vectors in Rd Then using the definition ā the relation between the coefficient implies the identity
d+1
d+1
Σ &
K.A
Σ
X1 w) O.
(8)
In particular, the 6;; K; are coefficients in integer relation connecting the known numbers Now, an issue that as one cannot enter the real numbers as in- put for the lattice-based LLL. the algorithm truncates the numbers 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) e;, 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 poly- nomials (notice that the A; are rational functions of by Cramer's 's rule). to deduce that the numbers Az, Ar²; are in "sufficient general position", in terms of rational independence, for the argument to work. We remark that this is potentially important technical advancement over the prior applications of the L.L. algorithm towards performing such inference tasks, such as for average-case subset sum or regression with discrete coefficients (60) 26 where the corresponding A, Xıa; coefficients are (truncated) i.idd continuous random variables which case anticoncentration is immediate (see e.g. 600 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 = ((d)) then indeed the argument can still work and tolerate exp( exp(-)(dd)) -noise by showing that the near-minimal integer relations remain unchanged under this level of exponentially small noise.
Aæz,, dj. = 1.2....,dl
problems 33 22
Remark 3.8 (CLWE with exponentially small noise). Notice that the detection problem in CLWE reduces the cosine learning problem (3). Indeed, if =xx w) mod E [-1/2, is CLWE sample, then cos(2) satisfies
(2 w)) E,
with lgl < 2. Algorithm I and the associated analysis Theorem 3.6 thus improve upon the exact CLWE recovery of [1 Section 6] in two aspects: (i) it requires + samples as opposed to d2; and (ii) it tolerates exponentially small noise.
10

---

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 Sloan Foundation, NSF RI-1816753, NSF CAREER CIF-1845360, and NSF CCF-1814524, IZ is supported by the CDS Moore-Sloan Postdoctoral Fellowship.
References
[1] Emmanuel Abbe and Colin Sandon. Poly-time universality and limitations of deep learning, 2020.
[2] Dorit Aharonov and Oded Regev. Lattice problems in np n conp. ACM, 52(5):749-765, September 2005.
[3] Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, John Kelsey, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, and Daniel Smith-Tone. Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process. Technical Report NIST Internal or Interagency Report (NISTIR) 8309, National Institute of Standards and Technology, July 2020.
[4] Zeyuan Allen-Zhit Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers, 2018.
[5] Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique random graph. Random Structures & Algorithms, 13(3-4):5774666 1998.
[6] Alexandr Andoni, Daniel Hsu, Kevin Shi, and Xiaorui Sun. Correspondence retrieval. In COLT, volume 65 of Proceedings of Machine Learning Research, pages 105-126. PMLR, 2017.
[7] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high- sigh-dimensional inference, 2021.
[8] Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, and Lenka Zdeborová. The committee machine: Computational to statistical gaps learning two-layers neural network. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124033, 2019.
[9] Afonso S. Bandeira, Amelia Perry, and Alexander S. Wein. Notes on computational to-sttiiiiittt gaps: predictions using statistical physics, 2018.
[10] B. Barak, S. B. Hopkins, J. Kelner, P. Kothari, A. Moitra, and A. Potechin. A nearly tight sum- of-squares lower bound for the planted elique problem. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 428-437, 2016.
[11] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(12):5551-546) 2019.
[12] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In STOC, STOC '94, pages 253-262, 1994.
[13] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous Iwe, In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021.
[14] Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shward Sgd learns over- parameterized networks that provably generalize linearly separable data, 2017.
[15] Amit Daniely and Gal Vardi. From local pseudorandom generators to hardness of learning,
2021.

---

[16] Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. In Conference on Learning Theory, pages 1452- 1485. PMLR, 2020.
[17] Ilaas Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks. In Conference on Learning Theory, pages 1514-1539. PMLR, 2020.
[18] David L. Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):8811418819 2009.
[19] Leo Ducas, Tancrede Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehle. Crystals dilithium: Digital signatures from module lattices. Cryptology ePrint Archive, Report 2017/633, 2017.
[20] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2), 2017.
[21] Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent, 2020.
[22] Alan M. Frieze. On the lagarias-odlyzko algorithm for the subset sum problem. SIAM J. Comput., 15:536-533 1986.
[23] David Gamarnik and Ilias Zadik. High dimensional linear regression with binary coefficients: Mean squared error and phase transition. In Conference on Learning Theory (COLT), 2017.
[24] David Gamarnik and Ilias Zadik. The landscape of the planted clique problem: Dense subgraphs and the overlap gap property, 2019.
[25] David Gamarnik and Ilias Zadik. Sparse high high-dimensional linear regression. algorithmic barriers and local search algorithm, 2019.
[26] David Gamarnik, Eren C. Kızıldag, and Ilias Zadik. Inference high-dimensional linear regression via lattice basis reduction and integer relation detection, 2019.
[27] Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden- layer neural networks with landscape design, 2017.
[28] Surbhi Goel, Sushrut Karmalkar, and Adam Klivans. Time/accuracy tradeoffs for learning a relu with respect to gaussian marginals. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[29] Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Super- polynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference Machine Learning, pages 3587-3596. PMLR, 2020.
[30] Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms, (4):347-359, 1992.
[31] Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of gener- alized linear and single index models with isotonic regression. In J. Shawe-Taylee R. Zemel, Bartlett, F. Pereira, and K. Q Weinberger, editors, Advances Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[32] Ravi Kannan. Improved algorithms for integer programming and related lattice problems. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, page 193-206, New York, NY, USA, 1983. Association for Computing Machinery.
[33] Michael Kearns. Efficient noise-tolerant learning from statistical queries. ACM, 45(6): 983-1006, November 1998.
12

---

[34] Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. J. ACM, 41(1):67-95, January 1994.
[35] Michael Kharitonov. Cryptographic hardness of cetrriuttion-speciie learning. Proceedings of the Twenty-Fifth Annual ACM Symposium Theory of Computing, STOC '93, page 372-381, New York, NY, USA, 1993, Association for Computing Machinery.
[36] Adam R Klivans and Alexander A Sherstov. Cryptographic hardness for learning intersections of halfsspaces. Journal of Computer and System Sciences, 75(1):2-12, 2009.
[37] Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira. Notes computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio, 2019.
[38] J. C. Lagarias and A. M. Odlyzko. Solving low-density subset sum problems. ACM, 32(1): 229 229-246, January 1985.
[39] Jeffrey C Lagarias. Knapsack public key cryptosystems and diophantine approximation. In Advances in cryptology, pages 3-23. Springer, 1984.
[40] Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261 261(4):515-533 534444,,, 1982.
[41] Antoine Maillard, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase retrieval in high dimensions: Statistical and computational phase transitions, 2020.
[42] Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective. The Springer International Series in Engineering and Computer Science. Springer US, 2002.
[43] Daniele Micciancio and Oded Regev. -asse Cryptography, pages 147-191. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
[44] Marlene Müller. Generalized Linear Models, pages 205-228. Springer Berlin Heidelherg, Berlin, Heidelberg, 2000.
[45] J. A. Nelder and R. W. M. Wedderburn. Generalized linear models. Journal of the Royal Statistical Society. Series (General), 135(3):370-384, 1972.
[46] Phong Q. Nguyen and Damien Stehlé. An III algorithm with quadratic complexity. SIAM Journal Computing, 39(3):874-903, 2009..
[47] Sundeep Rangan. Generalized approximate message passing for estimation with random linear mixing. In 2011 IEEE International Symposium on Information Theory Proceedings, pages 2168 2172. IEEE, 2011.
[48] Galen Reeves, Jiaming Xu, and Ilias Zadik. All-or-nothing phenomena: From single-letter high dimensions. In 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pages 654 2019.
[49] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC, STOC '05, pages 84-93, 2005.
[50] Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Marvels and pitfalls of the langevin algorithm in noisy high- dimensional inference. Phys. Rev. X, 10:01 1057, 2020.
[51] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014.
[52] Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In International Conference on Machine Learning, pages 3067-3075. PMLR, 2017.
[53] Adi Shamir. A polynomial time algorithm for breaking the basic merkle-hellman cryptosystem. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 145-152. IEEE, 1982.
13

---

[54] Ohad Shamir. Distribution-specin hardness of learning neural networks. J. Mach. Learn. Res., 13(5):1135-1163, 2018.
[55] Denis Simon. Selected Applications of LLL in Number Theory, pages 265-282. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
[56] Mahdi Soltanolkotabi. Learning relus via gradient descent, 2017.
[57] Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural networks. In I. Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[58] Balázs Szörényi. Characterizing statistical query learning: Simplified notions and proofs. In Ricard Gavaldà, Gábor Lugosi, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory, pages 186-200, Berlin, Heidelherg, 2009. Springer Berlin Heidelberg.
[59] Martin J. Wainwright. Sharp thresholds for gighndimensional and noisy sparsity recovery using l -constrained quadratic programming (lasso). IEEE Transactions on Information Theory, 55 (5):2183-2200 2009.
[60] Ilias Zadik and David Gamarnik. High dimensional linear regression using lattice basis reduction. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[61] Kai Zhong, Zhao Song, Prateek Jain, Peter Bartlett, and Inderjit Dhillon. Recovery guarantees for oaeehiddenll neural networks, 2017.
14


Reviews:
[{"review_id": "uun3-WRkB5n", "reviewer": "Reviewer_Dpoz", "summary": "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:\n- 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.\n- In the \"small noise\" $\\beta = \\exp(-d)$ regime, a novel efficient learning algorithm using LLL-based integer relation detection.\n\nAs one consequence, the hardness profile of this problem with respect to the noise rate $\\beta$ exhibits interesting computational-to-statistical phase traditions / gaps.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There has been a lot of work on learning deep learning primitives such as single neurons in various models recently, especially distribution-specific SQ and gradient-based methods. While such methods are quite general, it has been often noted that they technically exclude approaches such as SGD. This paper finds a new and interesting place in this landscape by showing cryptographic lower bounds that hold against arbitrary poly-time learners under a benign input distribution, namely the Gaussian. The proof of the cryptographic lower bound is clean and elegant, and the use of continuous LWE for the reduction is novel and may prove to be a technique of further interest in this area.\n\nRegarding the class of periodic neurons, while it is true that they have been considered in prior works such as Song et al 2017 and have interesting theoretical properties, I still find them a little artificial from a practical point of view (at the least, one tends to want an increasing activation).  But this is a minor shortcoming considering this is still a new and strong result, and one would hope that results such as this will lead to better understanding of the landscape for more usual neurons. The authors do note that the cosine neuron is well-approximated by one-layer ReLU networks. The cryptographic lower bounds that one would obtain as a corollary for such one-layer networks (with additive noise) are against poly-time learners, and hence nominally weaker than (although technically incomparable with) known exp(n) SQ lower bounds in the realizable setting (e.g., Diakonikolas et al, 2020). I would be interested to see a short discussion of such a quantitative comparison, especially as someone unfamiliar with the hard regime for CLWE.\n\nThe LLL-based learning algorithm is also novel and an important technical contribution. It would appear that the periodicity makes some such technique essential. If space permits, I would be interested to see a brief comparison with existing approaches for non-periodic activations and GLMs at least at a high level.\n\nOverall I think this is a significant and original contribution to the literature. The paper is well-written and clearly organized. Some of the proofs (esp the supporting lemmas in Appendix D) are somewhat technical and I did not verify them in full detail, but they appear correct to me.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors are clear about the scope and limitations of this result. In the main review, I've mentioned a couple of points I would be interested to see some further discussion of, space permitting. I am not aware of any potential negative societal impact of this work.\n\nNit: In the statement of the cryptographic lower bound in some places in the text and e.g. Cor 4.4, I think it confuses matters a bit to speak of quantum attacks. The reduction shows that a classical poly-time learner of periodic neurons would yield a classical poly-time algorithm for CLWE. As one cares primarily about classical learners of such neurons, hardness for such learners holds under the assumption that CLWE is classically hard, which is of course a _weaker_ assumption than that it is quantum hard. That is, the headline lower bound of this paper really holds under a weaker assumption than some places in the text make it sound. If one did care about quantum learners of periodic neurons, then quantum attacks against CLWE would be of interest, but then one gets a little bit into the weeds of the representation of the data the quantum learner is given, etc. I understand the intent is probably to provide evidence for the weaker assumption (classical hardness of CLWE) by saying people actually believe the stronger one (quantum hardness of CLWE), but the wording could perhaps be tweaked in some places.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "_6TyqFr2QfL", "reviewer": "Reviewer_sRgS", "summary": "The authors consider learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise. The authors connect single periodic neurons with lattice basis reduction algorithms and CLWE, and discuss noise level regions where estimation is impossible, crypto-hard or easy.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Originality\n\nThe task is not new but the method is new. The connection between this problem with CLWE for establishing cryptographic hardness under moderate noise is interesting. Related work is adequately cited and well discussed.\n\n2. Quality\n\nThe submission is technically sound and claims are well supported. Weaknesses are not addressed in depth, and some questions are raised in (Section 3. Clarity). Overall the paper is well-written and easy to follow. Some sentences seem to appear several times throughout the paper, but it does not affect the flow of reading.\n\n3. Clarity\n\nThe paper is clearly written and well organized. The history and motivations of discussing this problem is also given.\n\nSome minor questions regarding the work:\n\n(a) Considering the gaps between impossible, crypto hard and easy regions, is it possible to strengthen the result to reduce the gaps? For example, the information theoretic bound of 1 versus the crypto hard bound of omega(1) could be quite large. It would be interesting to see if the techniques can be modified or strengthened to reduce this gap. The same goes for the gap between the crypto hard region and easy region: the gap between poly(d) and exp((dlog d)^3) is quite large and it would be interesting to see if there is any discussion about these gaps.\n\n(b) It would be nice to see some more discussion about practical implications of such a result for applications, particularly for readers not familiar with hardness of learning. Readers not within the community may find it hard to justify the importance or interestingness of the result, since intuitively speaking it is quite natural to have regions of the noise level where it is easy or hard to estimate the underlying vector w. I think it would be beneficial to add some more discussion relating practical implications of this work.\n\n4. Significance: \n\nThe results are interesting and benefit the learning community. The methodologies can bring impact to a range of other problems.\n\nUpdate after reviewing comments: Increased score to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussions on societal impact are available.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "WY2gN-bQhkL", "reviewer": "Reviewer_Pqda", "summary": "The first line of the abstract nicely summarises the work and I cannot summarise this any better. \n\"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\".\n\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper adds to the understanding of learning simple neural networks. The paper is well written in my opinion and uses allowed space to provide discussion of all relevant issues.  The cryptographic reduction give strong guarantees against \"any\" polynomial time learning algorithm.\n\n- This additional comment is to acknowledge reading author response. There is no other changes.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical in nature.", "review_text": "", "extra_scores": {"ethical_concerns": "This work is theoretical in nature. There are no serious ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BloeAt3w7Hj", "reviewer": "Reviewer_CDi6", "summary": "\nThe 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper’s context is lower bounds for neural networks and computational to statistical gaps. The particular kind of functions studied here were previously proved to be hard for SQ algorithms. While the authors emphasize that they prove hardness for all algorithms rather than just the restricted class of SQ algorithms, I would say that the two kinds of results are not quite directly comparable, as the SQ lower bounds are information theoretic, while here we have hardness under crypto assumptions.\n\nMore specifically, the problem studies learning a periodic cosine functions with a hidden d-dimensional direction, from a number of samples distributed according to an isotropic Gaussian distribution, in the squared loss setting. \n\nThe results essentially characterize the complexity of the problem (in fact the computational to statistical gaps) as a function of the signal to noise ratio.\n\nThe first algorithm is a simple learning algorithm that runs in exponential time and learns from a constant amount of noise. The idea is to construct an eps-net of the d-dimensional sphere, sample enough examples, and output the hypothesis in the net that is closest to the empirical value (where rounding is performed to the nearest integer).\n\nThe 2nd result is the reduction from the problem of Continuous Learning with Errors (CLWE) to the current learning task with polynomial amount of noise. In fact, this step is also based on a clean observation that one can immediately transform samples from the first problem into samples of the 2nd problem.\n\nFinally, they show an efficient algorithm that only uses linearly many samples (in the dimension) and learns in the presence of inverse exponentially amounts of noise. The problem here becomes that of solving a linear system of equations (which brings up the non-SQ aspect) , and it is solved using the LLL-latice basis reduction algorithm. (To me it also appears similar, at least at a high-level, to the BKW algorithm for solving noisy parities). The result initially is shown for the no-noise case, and hence computations reduce to solving systems of equations over integers. Then the authors observe that the granulation of the equations is coarse enough to be able to tolerate an exponential amounts of noise.\n\nThe paper is significant in the fact that it studies the entire SNR range for a natural learning problem. I don’t believe any of the results are particularly difficult to prove – in fact I would say that their approach is the first approach someone familiar with the literature would try.  However, the paper is exceptionally well-written, and the results are elegant and clean.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work establishes computational hardness for the problem of learning periodic functions with a small amount of adversarial additive noise added to each example. This problem was recently considered in a work by (Song et al., 2017) who established hardness in the Statistical Query model. The current work provides a reduction from the computationally hard problem of Continuous Learning with Errors (CLWE) -- a continuous analogue of LWE that was introduced in a recent work (where its computational hardness was established). A second contribution of the paper is an efficient algebraic algorithm solving the underlying learning problem when the additive noise is very small. 
The reviewers uniformly agreed that this is an interesting contribution that should appear in NeurIPS.
Decision: Accept (Poster)