We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form $x \rightarrow \max(0, w \cdot x)$ with $w \in S^{nā1}$. Our algorithm works in the challenging Reliable Agnostic learning ā¦