Information Theoretic Lower Bounds for Feed-Forward Fully-Connected Deep Networks
In this paper, we study the sample complexity lower bounds for the exact recovery of parameters and for a positive excess risk of a feed-forward, fully-connected neural network for binary classification, using information-theoretic tools. We prove these lower bounds by the existence of a generative network characterized by a backwards data generating process, where the input is generated based on the binary output, and the network is parametrized by weight parameters for the hidden layers. The sample complexity lower bound for the exact recovery of parameters is $\Omega(d r \log(r) + p )$ and for a positive excess risk is $\Omega(r \log(r) + p )$, where $p$ is the dimension of the input, $r$ reflects the rank of the weight matrices and $d$ is the number of hidden layers. To the best of our knowledge, our results are the first information theoretic lower bounds.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationSimilar Papers 제목 키워드 기반
A Renderer-Enabled Framework for Computing Parameter Estimation Lower Bounds in Plenoptic Imaging Systems
This work focuses on assessing the information-theoretic limits of scene parameter estimation in plenoptic imaging systems. A general framework to compute lower bounds on the parameter estimation error from noisy plenopt…
Object LocalizationRegret Bounds for Noise-Free Cascaded Kernelized Bandits
We consider optimizing a function network in the noise-free grey-box setting with RKHS function classes, where the exact intermediate results are observable. We assume that the structure of the network is known (but not …
Bounds on the Approximation Power of Feedforward Neural Networks
The approximation power of general feedforward neural networks with piecewise linear activation functions is investigated. First, lower bounds on the size of a network are established in terms of the approximation error …
Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems
TWe establish regret lower bounds for adaptively controlling an unknown linear Gaussian system with quadratic costs. We combine ideas from experiment design, estimation theory and a perturbation bound of certain informat…
A general approximation lower bound in $L^p$ norm, with applications to feed-forward neural networks
We study the fundamental limits to the expressive power of neural networks. Given two sets $F$, $G$ of real-valued functions, we first prove a general lower bound on how well functions in $F$ can be approximated in $L^p(…
Open-Ended Question Answering