VC dimension of partially quantized neural networks in the overparametrized regime

Abstract

Vapnik-Chervonenkis (VC) theory has so far been unable to explain the small generalization error of overparametrized neural networks. Indeed, existing applications of VC theory to large networks obtain upper bounds on VC dimension that are proportional to the number of weights, and for a large class of networks, these upper bound are known to be tight. In this work, we focus on a class of partially quantized networks that we refer to as hyperplane arrangement neural networks (HANNs). Using a sample compression analysis, we show that HANNs can have VC dimension significantly smaller than the number of weights, while being highly expressive. In particular, empirical risk minimization over HANNs in the overparametrized regime achieves the minimax rate for classification with Lipschitz posterior class probability. We further demonstrate the expressivity of HANNs empirically. On a panel of 121 UCI datasets, overparametrized HANNs match the performance of state-of-the-art full-precision models.

References in corpus (10)

• Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
• Binary Neural Networks: A Survey
• Fast learning rates for plug-in classifiers
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets
• Neural Kernels Without Tangents
• BinaryDuo: Reducing Gradient Mismatch in Binary Activation Network by Coupling Binary Activations
• On the rate of convergence of fully connected very deep neural network regression estimates
• Regularized Binary Network Training