2019/10/13 by Amit Daniely, Daniely, Amit, Elad Granot +1 · 2 citations
Computer Science · Engineering · Materials Science · Mathematics · #Advanced Memory and Neural Computing #Bounded function #Combinatorics #Computer science #Discrete mathematics #FOS: Computer and information sciences #Function (biology) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and ELM #Machine Learning in Materials Science #Mathematical analysis #Mathematics #Neural Networks and Applications #Norm (philosophy) #Physics #Sample complexity #Stochastic Gradient Optimization Techniques #Upper and lower bounds #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1910.05697
published in arXiv (Cornell University) 32, 12988-12996 (Cornell University) · To appear in NeurIPS
arxiv created 2019/10/13 · openalex publication_date 2019/10/13 · arxiv updated 2019/10/15 · openalex created_date 2019/10/18 · openalex updated_date 2026/07/28
We investigate the sample complexity of networks with bounds on the magnitude\nof its weights. In particular, we consider the class nH=
left
Wt
circ
rho
circ
ldots
circ
rho
circ W1 :W1,
ldots,Wt-1
in\nMd, d, Wt
in M1,d
right
where the spectral norm of each Wi is\nbounded by O(1), the Frobenius norm is bounded by R, and \ρ is the\nsigmoid function \(ex)/(1+ex) or the smoothened ReLU function \ln\n(1+ex). We show that for any depth t, if the inputs are in [-1,1]d, the\nsample complexity of H is O\(\(dR2)/(\ε2)\).\nThis bound is optimal up to log-factors, and substantially improves over the\nprevious state of the art of O\(\(d2R2)/(\ε2)\).\n We furthermore show that this bound remains valid if instead of considering\nthe magnitude of the Wi's, we consider the magnitude of Wi - Wi0, where\nWi0 are some reference matrices, with spectral norm of O(1). By taking\nthe Wi0 to be the matrices at the onset of the training process, we get\nsample complexity bounds that are sub-linear in the number of parameters, in\nmany typical regimes of parameters.\n To establish our results we develop a new technique to analyze the sample\ncomplexity of families H of predictors. We start by defining a new notion of\na randomized approximate description of functions f:X\→\ℝd. We then\nshow that if there is a way to approximately describe functions in a class H\nusing d bits, then d/\ε2 examples suffices to guarantee uniform\nconvergence. Namely, that the empirical loss of all the functions in the class\nis \ε-close to the true loss. Finally, we develop a set of tools for\ncalculating the approximate description length of classes of functions that can\nbe presented as a composition of linear function classes and non-linear\nfunctions.\n