In this paper, we consider the problem of training neural networks (NN). To promote a NN with specific structures, we explicitly take into consideration the nonsmooth regularization (such as L1-norm) and constraints (such as interval constraint). This is formulated as a constrained nonsmooth nonconvex optimization problem, and we propose a convergent proximal-type stochastic gradient descent (Prox-SGD) algorithm. We show that under properly selected learning rates, momentum eventually resembles the unknown real gradient and thus is crucial in analyzing the convergence. We establish that with probability 1, every limit point of the sequence generated by the proposed Prox-SGD is a stationary point. Then the Prox-SGD is tailored to train a sparse neural network and a binary neural network, and the theoretical analysis is also supported by extensive numerical tests. In this paper, we consider the problem of training neural networks (NN) under constraints and regularization. It is formulated as an optimization problem where x is the parameter vector to optimize, y i is the i-th training example which consists of the training input and desired output, and m is the number of training examples. The training loss f is assumed to be smooth (but nonconvex) with respect to x, the regularization r is assumed to be convex (but nonsmooth), proper and lower semicontinuous, and the constraint set X is convex and compact (closed and bounded). When r(x) = 0 and X = R n , stochastic gradient descent (SGD) has been used to solve the optimization problem (1). At each iteration, a minibatch of the m training examples are drawn randomly, and the obtained gradient is an unbiased estimate of the true gradient. Therefore SGD generally moves along the descent direction, see Bertsekas & Tsitsiklis (2000) . SGD can be accelerated by replacing the instantaneous gradient estimates by a momentum aggregating all gradient in past iterations. Despite the success and popularity of SGD with momentum, its convergence had been an open problem. Assuming f is convex, analyzing the convergence was first attempted in Kingma & Ba (2015) and later concluded in Reddi et al. (2018) . The proof for a nonconvex f was later given in Chen et al. (2019) ; Lei et al. (2019) . In machine learning, the regularization function r is typically used to promote a certain structure in the optimal solution, for example sparsity as in, e.g., feature selection and compressed sensing, or a zero-mean-Gaussian prior on the parameters (Bach et al., 2011; Boyd et al., 2010) . It can be interpreted as a penalty function since at the optimal point x of problem (1), the value r(x ) will be small. One nominant example is the Tikhonov regularization r(x) = µ x 2 2 for some predefined constant µ, and it can be used to alleviate the ill-conditioning and ensure that the magnitude of the weights will not become exceedingly large. Another commonly used regularization, the 1 -norm where r(x) = µ x 1 = µ n j=1 |x j | (the convex surrogate of the 0 -norm), would encourage a sparse solution. In the context of NN, it is used to (i) promote a sparse neural network (SNN) to alleviate overfitting and to allow a better generalization, (ii) accelerate the training process, and (iii) prune the network to reduce its complexity, see Louizos et al. (2018) and Gale et al. (2019) . Technically, it is difficult to analyze the regularizations as some commonly used convex regularizers are nonsmooth, for example, 1 -norm. In current implementations of Tensorflow, the gradient of |x| is simply set to 0 when x = 0. This amounts to the stochastic subgradient descent method and usually exhibits slow convergence. Other techniques to promote a SNN includes magnitude pruning and variational dropout, see Gale et al. (2019) . Although regularization can be interpreted as a constraint from the duality theory, sometimes it may still be more desirable to use explicit constraints, for example, x 2 j ≤ α, where the summation is over the weights on the same layer. This is useful when we already know how to choose α. Another example is the lower and upper bound on the weights, that is, l ≤ w ≤ u for some predefined l and u. Compared with regularization, constraints do not encourage the weights to stay in a small neighborhood of the initial weight, see Chapter 7.2 of Goodfellow et al. (2016) for more details. The set X models such explicit constraints, but it poses an additional challenge for stochastic gradient algorithms as the new weight obtained from the SGD method (with or without momentum) must be projected back to the set X to maintain its feasibility. However, projection is a nonlinear operator, so the unbiasedness of the random gradient would be lost. Therefore the convergence analysis for constrained problems is much more involved than unconstrained problems. In this paper, we propose a convergent proximal-type stochastic gradient algorithm (Prox-SGD) to train neural networks under nonsmooth regularization and constraints. It turns out momentum plays a central role in the convergence analysis. We establish that with probability (w.p.) 1, every limit point of the sequence generated by Prox-SGD is a stationary point of the nonsmooth nonconvex problem (1). This is in sharp contrast to unconstrained optimization, where the convergence of the vanilla SGD method has long been well understood while the convergence of the SGD method with momentum was only settled recently. Nevertheless, the convergence rate of Prox-SGD is not derived in the current work and is worth further investigating. To test the proposed algorithm, we consider two applications. The first application is to train a SNN, and we leverage 1 -regularization, that is, The second application is to train a binary neural network (BNN) where the weights (and activations) are either 1 or -1 (see Courbariaux et al. (2015; ; Hou et al. (2017) ; Yin et al. (2018) ; Bai et al. (2019) for more details). To achieve this, we augment the loss function with a term that penalizes the weights if they are not +1 or -1: where µ is a given penalty parameter. The binary variable a j can be interpreted as a switch for weight x j : when a j = 0, (1 − a j )(x j − 1) 2 is activated, and there is a strong incentive for x j to be 1 (the analysis for a j = 1 is similar). Since integer variables are difficult to optimize, we relax a j to be a continuous variable between 0 and 1. To summarize, a BNN can be obtained by solving the following regularized optimization problem under constraints with respect to x and a If µ is properly selected (or sufficiently large), the optimal a j will be exactly or close to 0 or 1. Consequently, regularization and constraints offer interpretability and flexibility, which allows us to use more accurate models to promote structures in the neural networks, and the proposed convergent Prox-SGD algorithm ensures efficient training of such models.
We propose a convergent proximal-type stochastic gradient descent algorithm for constrained nonsmooth nonconvex optimization problems This paper proposes Prox-SGD, a theoretical framework for stochastic optimization algorithms shown to converge asymptotically to stationarity for smooth non-convvex loss + convex constraint/regularizer. The paper proposes a new gradient-based stochastic optimization algorithm with gradient averaging by adapting theory for proximal algorithms to the non-convex setting.