A case where a spindly two-layer linear network decisively outperforms any neural network with a fully connected input layer
Mar 9, 2021
Speakers
Manfred K. Warmuth
Speaker · 0 followers
Wojciech Kotłowski
Speaker · 0 followers
Ehsan Amid
Speaker · 0 followers
About
It was conjectured that any neural network of any structure and arbitrary differentiable transfer functions at the nodes cannot learn the following problem sample efficiently when trained with gradient descent: The instances are the rows of a $d$-dimensional Hadamard matrix and the target is one of the features, i.e. very sparse. We essentially prove this conjecture: We show that after receiving a random training set of size $k < d$, the expected squared loss is still $1-\frac{k}{(d-1)}$. The only requirement needed is that the input layer is fully connected and the initial weight vectors of the input nodes are chosen from a rotation invariant distribution. Surprisingly the same type of problem can be solved drastically more efficient by a simple 2-layer linear neural network in which the $d$ inputs are connected to the output node by chains of length 2 (Now the input layer has only one edge per input). When such a network is trained by gradient descent, then it has been shown that its expected squared loss is $\frac{\log d}{k}$. Our lower bounds essentially show that a sparse input layer is needed to sample efficiently learn sparse targets with gradient descent.It was conjectured that any neural network of any structure and arbitrary differentiable transfer functions at the nodes cannot learn the following problem sample efficiently when trained with gradient descent: The instances are the rows of a $d$-dimensional Hadamard matrix and the target is one of the features, i.e. very sparse. We essentially prove this conjecture: We show that after receiving a random training set of size $k < d$, the expected squared loss is still $1-\frac{k}{(d-1)}$. Th…
Categories
AI & Data Science
Category · 10.8k presentations
About ALT 2021
The 32nd International Conference on Algorithmic Learning Theory
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time
Watch later
Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
Watch later
Last Round Convergence and No-Dynamic Regret in Asymmetric Repeated Games
Watch later
Le Cong Dinh, …
A Deep Conditioning Treatment of Neural Networks
Watch later
Precise Minimax Regret for Logistic Regression with Categorical Feature Values
Watch later
