Computational Barriers For Learning Some Generalized Linear Models
summary
Shows two concrete hardness results for ReLU GLMs: a conditional lower bound from Densest-kappa-subgraph hardness proving no poly(d) · 2^{Ω(1/ε^2)} time algorithm for proper ReLU regression to additive ε (matches a brute‑force sign‑pattern upper bound and yields a proper vs improper separation), and an unconditional SQ lower bound for agnostic learning under Gaussian marginals giving super‑polynomial query/tolerance requirements (bounds scale like D^{Ω(1/ε^c)}), obtained via a reduction using Frank‑Wolfe on function space and a convex surrogate.
AI-written summary · about
chapters (7)
- 0:00Computational barriers in GLMs
- 2:27Generalized linear models setup
- 7:44Proper vs improper learning
- 10:33Hardness for ReLU regression
- 15:54Hardness for Gaussian inputs
- 24:41Summary of results
- 26:31Q&A
related talks
19mOn the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks
32mTight Hardness Results for Training Depth-2 ReLU Networks
56mSparsifying Generalized Linear Models
01h 12mRecent Progress in High-Dimensional Learning
01h 30mAnalytic Methods for Supervised Learning IV
45mTractability And Overparametrization In Some Simple Models
01h 03mUnderstanding ReLU Networks Through Graph Problems and Polyhedra
37mEfficient Algorithms for Reliable Machine Learning