First Fully Polynomial-Time Algorithm Learns Positive ReLU Combinations

Researchers present the first fully polynomial-time PAC algorithm for learning positive linear combinations of k ReLUs under Gaussian inputs and L2 loss. Unlike prior methods, it needs neither super-polynomial time nor strong conditioning assumptions.

• Algorithm is polynomial in dimension, k and inverse error
• Prior methods required super-polynomial time or strong conditioning
• Result is theoretical; practical implementability is unproven
• Open question: extension to signed combinations and deeper networks