On sample complexity of neural networks
We consider functions defined by deep neural networks as definable objects in an o-miminal expansion of the real field, and derive an almost linear (in the number of weights) bound on sample complexity of such networks.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Sample Complexity Measure with Applications to Learning Optimal Auctions
We introduce a new sample complexity measure, which we refer to as split-sample growth rate. For any hypothesis $H$ and for any sample $S$ of size $m$, the split-sample growth rate $\hat{\tau}_H(m)$ counts how many diffe…
Learning Privately with Labeled and Unlabeled Examples
A private learner is an algorithm that given a sample of labeled individual examples outputs a generalizing hypothesis while preserving the privacy of each individual. In 2008, Kasiviswanathan et al. (FOCS 2008) gave a g…
Active LearningSample Complexity Bounds on Differentially Private Learning via Communication Complexity
In this work we analyze the sample complexity of classification by differentially private algorithms. Differential privacy is a strong and well-studied notion of privacy introduced by Dwork et al. (2006) that ensures tha…
PAC learningAn invitation to the sample complexity of quantum hypothesis testing
Quantum hypothesis testing (QHT) has been traditionally studied from the information-theoretic perspective, wherein one is interested in the optimal decay rate of error probabilities as a function of the number of sample…
LEMMAInformation-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise
We study the problem of PAC learning $\gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem a…
PAC learning