Tight Hardness Results for Training Depth-2 ReLU Networks

on YouTube ↗32m

" summary

Proves concrete limits and matching algorithms for depth-2 ReLU training: shows single-ReLU NP-hard (agnostic) and NP-hardness for any K≥2 in the realizable case, gives additive-error algorithms running in time roughly exp(K^5/epsilon^2) (agnostic) and exp(K^3/epsilon) (realizable) with sample bounds ~K^4/epsilon^2 and ~K^2/epsilon, and establishes tight ETH/GAP-ETH lower bounds: exp(1/epsilon) tight (realizable) and, under a DkS gap hypothesis, exp(1/epsilon^2) lower bound (agnostic). Assumptions and reductions are explicit and constructive.

AI-written summary · about

" chapters (9)

1. 0:00Intro
2. 2:19Depth-2 Neural Networks
3. 4:44Training/Learning Depth-2 ReLU Networks
4. 8:19Our Results
5. 13:33Hypotheses
6. 15:54Algorithms
7. 18:55NP-Hardness
8. 24:48Running Time Lower Bounds
9. 28:56Conclusion

" related talks

• 30mComputational Barriers For Learning Some Generalized Linear ModelsSurbhi Goel · Rigorous Evidence for Information-Computation Trade-offs
• 01h 03mUnderstanding ReLU Networks Through Graph Problems and PolyhedraChristoph Hertrich · Graph Learning Meets Theoretical Computer Science 2025
• 33mProvably Efficient Algorithms for Training Deep NetworksShai Shalev-Shwartz · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 14mApproximation PowerMatus Telgarsky · Deep Learning Boot Camp 2019
• 01h 04mRandomized Embeddings and Neural NetworksMert Pilanci · Sketching and Algorithm Design 2023
• 45mIs Deeper Better Only When Shallow Is Good?Shai Shalev-Shwartz · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 19mOn the Cryptographic Hardness of Learning One-Hidden Layer Neural NetworksIlias Zadik · Deep Learning Theory Symposium 2021
• 59mTutorial: Statistical Learning Theory and Neural Networks ISpencer Frei · Deep Learning Theory Workshop and Summer School 2022