Computational Barriers For Learning Some Generalized Linear Models

In this talk, I will present two computational hardness results for the problem of learning generalized linear models with noisy labels, focussing on ReLUs. The first result is based on a reduction from a conjecturally hard problem and holds for any learning algorithm. The second result does not need an underlying hard problem but instead holds against a special class of algorithms, specifically the Statistical Query (SQ) model.