Convergence of a Relaxed Variable Splitting Method for Learning Sparse Neural Networks via ℓ₁, ℓ₀, and transformed-ℓ₁ Penalties

2018/12/13 by Dinh, Thu, Xin, Jack
#68T05 #90C26 #97R40 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1812.05719

Abstract

Sparsification of neural networks is one of the effective complexity reduction methods to improve efficiency and generalizability. We consider the problem of learning a one hidden layer convolutional neural network with ReLU activation function via gradient descent under sparsity promoting penalties. It is known that when the input data is Gaussian distributed, no-overlap networks (without penalties) in regression problems with ground truth can be learned in polynomial time at high probability. We propose a relaxed variable splitting method integrating thresholding and gradient descent to overcome the lack of non-smoothness in the loss function. The sparsity in network weight is realized during the optimization (training) process. We prove that under ℓ₁, ℓ₀; and transformed-ℓ₁ penalties, no-overlap networks can be learned with high probability, and the iterative weights converge to a global limit which is a transformation of the true weight under a novel thresholding operation. Numerical experiments confirm theoretical findings, and compare the accuracy and sparsity trade-off among the penalties.

Related

• Convergence of a Relaxed Variable Splitting Coarse Gradient Descent\n Method for Learning Sparse Weight Binarized Activation Neural Networks
• Learning Sparse Neural Networks via ℓ₀ and Tℓ₁ by a Relaxed Variable Splitting Method with Application to Multi-scale Curve Classification
• ℓ₀ Regularized Structured Sparsity Convolutional Neural Networks
• Differentiable Sparsification for Deep Neural Networks
• Global Minimizers of ℓ^p-Regularized Objectives Yield the Sparsest ReLU Neural Networks