“Interesting to compare this with [1], which shows that for some concept classes neural networks trained with SGD are much easier to train (i.e., require less data). In other words, even though these two types of model are in a way equivalent, one can be much easier to train than the other for certain concepts (no free lunch). [1] https://arxiv.org/abs/2…”
Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning
Deep learning is also known as hierarchical learning, where the learner _learns_ to represent a complicated target function by decomposing it into a sequence of simpler functions to reduce sample and time complexity. This paper formally analyzes how multi-layer neural networks can perform such hierarchical learning _efficiently_ and _automatically_ by SGD on the training objective. On the conceptual side, we present a theoretical characterizations of how certain types of deep (i.e. super-constant layer) neural networks can still be sample and time efficiently trained on some hierarchical tasks, when no existing algorithm (including layerwise training, kernel method, etc) is known to be efficient. We establish a new principle called "backward feature correction", where the errors in the lower-level features can be automatically corrected when training together with the higher-level layers. We believe this is a key behind how deep learning is performing deep (hierarchical) learning, as opposed to layerwise learning or simulating some non-hierarchical method. On the technical side, we show for every input dimension $d > 0$, there is a concept class of degree $ω(1)$ multi-variate polynomials so that, using $ω(1)$-layer neural networks as learners, SGD can learn any function from this class in $\mathsf{poly}(d)$ time to any $\frac{1}{\mathsf{poly}(d)}$ error, through learning to represent it as a composition of $ω(1)$ layers of quadratic functions using "backward feature correction." In contrast, we do not know any other simpler algorithm (including layerwise training, applying kernel method sequentially, training a two-layer network, etc) that can learn this concept class in $\mathsf{poly}(d)$ time even to any $d^{-0.01}$ error. As a side result, we prove $d^{ω(1)}$ lower bounds for several non-hierarchical learners, including any kernel methods.
候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“To add on: Zeyuan Allen-Zhu and Yuanzhi Li had a great theoretical paper earlier last year proving a fundamental discrepancy between the concept classes learnable by kernel methods and deep learning models. https://arxiv.org/abs/2001.04413”
“This is basically adversarial training, which is a typical (& very practical) benchmark heuristic defense for this problem. An ongoing question is to precisely characterize when and how AT works. The line of work has also proved to be very fruitful for the theoretical community & has produced very general results about problems which can be solved by neur…”