Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: 
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.

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.

More 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. 

The results essentially characterize the complexity of the problem (in fact the computational to statistical gaps) as a function of the signal to noise ratio.

The 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).

The 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.

Finally, 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.

The 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.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 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.
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.

- This additional comment is to acknowledge reading author response. There is no other changes.
limitations_and_societal_impact: This work is theoretical in nature.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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:
- 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.
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.

Regarding 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.

The 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.

Overall 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.
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.

Nit: 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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: 1. Originality

The 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.

2. Quality

The 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.

3. Clarity

The paper is clearly written and well organized. The history and motivations of discussing this problem is also given.

Some minor questions regarding the work:

(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.

(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.

4. Significance: 

The results are interesting and benefit the learning community. The methodologies can bring impact to a range of other problems.

Update after reviewing comments: Increased score to 7.

limitations_and_societal_impact: No discussions on societal impact are available.
review_title: null

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)