ProxSGD: Training Structured Neural Networks under Regularization and Constraints
Authors: Yang Yang
Yaxiong Yuan
Avraam Chatzimichailidis
Ruud JG van Sloun
Lei Lei
Symeon Chatzinotas
Venue:  (2020)
Keywords: stochastic gradient descent
regularization
constrained optimization
nonsmooth optimization

Abstract: 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.

Published as a conference paper at ICLR 2020
PROXSGD: TRAINING STRUCTURED NEURAL NET- WORKS UNDER REGULARIZATION AND CONSTRAINTS
Yang Yang Fraunhofer ITWM
Yaxiong Yuan University of Luxembourg yaxiong yuan@uni. .u
Fraunhofer Center Machine Learning
yang. yang-yange twm. Fraunhofer.de
Avraam Chatzimichailidis
Fraunhofer ITWM
TU Kaiserslautem avraam. wtw.iiiicaiiiiiiiiii ci2aannnchatttiiiihcaaaaaaieaeia htw.::wwww.aaaaaff......
Ruud JG van Sloun
Lei Lei, Symeon Chatzinotas
Eindhoven University of Technology
University of Luxembourg
r.j.g.v. w.g.v.soou@tue
{lei.lei, symeon chatzinotas Buni.
ABSTRACT
this paper, we consider the problem training structured neural networks (NN) with nonsmooth regularization (e.g. é fn-norm) and constraints (e.g. interval con- straints). We formulate training as a constrained nonsmooth nonconvex optimiza- tion problem, and propose convergent proximal-type stochastic gradient descent (ProxSGD) algorithm. We show that under properly selected learning rates, with probability every limit point of the sequence generated by the proposed Prox- SGD algorithm is a stationary point. Finally, to support the theoretical analysis and demonstrate the flexibility of ProxSGD, we show by extensive numerical tests how ProxSGD can be used to train either sparse or binary neural networks through adequate selection of the regularization function and constraint set.
INTRODUCTION
In this paper, we consider the problem training neural networks (NN) under constraints and reg- ularization. It is formulated as an optimization problem
1 Y
minimize #EXCR L
(( tr(x),
(1)
f(x)
where æ the parameter vector to optimize, yi is the i-th training example which consists of the training input and desired output, and is the number of training examples. The training loss 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", stochastic gradient descent (SGD) has been used to solve the optimiza- tion problem (T. 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 momentum aggregating all gradient in past it- erations. Despite the success and popularity of SGD with momentum, its convergence had been an open problem. Assuming is convex, analyzing the convergence first attempted in Kingma & (2015) and later concluded in Reddi et al. (2018). The proof for a nonconvex f was later given in Chen al. (2019): Lei et al. (011)).

---

Published as a conference paper at ICLR 2020
In machine learning, the regularization function r is typically used to promote certain structure in the optimal solution, for example sparsity as in, c.g., feature selection and compressed sensing, or zero-mean- aueannGaussiin 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(#*) will be small. One nominant example is the Tikhonov regularization r(æ) |u|| 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 -n-rrmm where r(x) = μl|az|la = μ Ei== |زzل (the convex surrogate of the fo-norm), would encourage sparse solution. In the context of NN, it is used to (i) promote a sparse neural network (SNN) to alleviate overfitting and to allow better generalization, (ii) accelerate the training process. and (ii) 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 some commonly used convex regularizers are nonsmooth, for example, f nnoormm 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. Σ 2² S a, where the summation is over the weights on the same layer. This is useful when we already know how to choose a. Another example is the lower and upper bound on the weights, that is, I S w S u for some predefined I 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 GGoofellow al. (2016) for more details.
The set X models such explicit constraints, but it poses additional challenge for stochastic gradient algorithms as the new weight obtained from the SGD method (with or without momentum) must be projected back the set X to maintain its feasibility. However, projection 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 convergent proximal-type stochastic gradient algorithm (ProxSGD) 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 ProxSGD is stationary point of the nonsmooth nonconvex problem (T. 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 ProxSGD 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 train a SNN, and we leverage & t-rreuularization, that is,
m
minimize
fa y.) + #||=||11
m
The second application is to train a binary neural network (BNN) where the weights (and activations) are either 1 or (see Courbariaux al. (2015) 2016); Hou et al. (2017); (Yn et al. (2018); [aii 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
m
minimize 2,a
Σ MM vi) + (a, + 1)2 (11 a,,((, - 1)2) 4 j=1
m
subject to 0j = 0 or 1, = 1,,,., 1,...,n.
where μ is given penalty parameter. The binary variable a, can be interpreted as switch for weight zy: when a, 0, (1 az) 1)2 is activated, and there is strong incentive for xy to be (the analysis for a, = is similar). Since integer variables are difficult to optimize, we relax aj to be continuous variable between 0 and 1. To summarize, BNN can be obtained by solving the
2

---

Published as a conference paper at ICLR 2020
following regularized optimization problem under constraints with respect to and
minimize
Sx y:) + M Σ 4 1
(a
+ 1)2 az) - 1)2)
1=1 subject to 0 a5 S 1,1=,,,,
If is properly selected (or sufficiently large), the optimal aj 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 ProxSGD algorithm ensures efficient training of such models.
THE PROPOSED PROXSGD ALGORITHM
In this section, we describe the ProxSGD algorithm to solve Background and setup. We make the following blanket assumptions problem !
fı( (0) Wa ()) is Lipschitz continuous with finite constant Lę for any y. Thus Vf(x)) is
( is smooth (continuously differentiable) but not necessarily convex.
Lipschitz continuous with constant L - Σ L4-
r(z) is convex, proper and lower semicontinuous (not necessarily smooth).
X is convex and compact.
We interested in algorithms that can find stationary point of (T) A stationary point xt satisfies the optimality condition: at xx,
(ar x (((x))))++ r(x) r((#)) 2 0, Va E X.
(4)
When r(x:) and X RRn the deterministic optimization problem I can be solved by the (batch) gradient descent method. When m, the number of training examples, is large, it is computationally expensive to calculate the gradient. Instead, we estimate the gradient by a minibatch of m(t) training examples. We denote the minibatch by M():: its elements are drawn uniformly from {1, 21,2.... .... m} and there are m(t) elements. Then the estimated gradient is
9(1) - m(t (EM())
9(1)
Σ v)(((((),))))
(5)
and it is an unbiased estimate of the true gradient.
The proposed algorithm. The instantancous gradient g(t) is used to form aggregate gradient (momentum) v(t), which is updated recursively as follows
et)) (1 p(t))((t - + p(tg((t,
(6)
where p(t) is the stepsize (learning rate) for the momentum and p(t) (0.
At iteration we propose solve an approximation subproblem and denote its solution as ((x(t), utt), (()), or simply @(t)
{ ( (m= a(t)) { (ia((()))((((=== m0()) + r(m))
(tt) argmin aEE
(7)
A quadratic regularization term is incorporated so that the subproblem (7) is strongly convex and its modulus the minimum element of the vector Ttt), denoted as r(t) and z(t) = min Ty (t). Note that I(t) should be lower bounded by positive constant that is strictly larger than so that the quadratic regularization in (7) will not vanish.
The difference between two vectors @(t) and æ(t) specifies direction starting at (t)) and ending (t). This update direction used refine the weight vector
xt 1) (1) (()(((()) a=))),
(8)

---

Published as a conference paper at ICLR 2020
algorithm
momentum
weight F(t)
quadratic gain in subproblem
regularization convex
constraint
ProxSGD
p(t)
T (t)
convex, compact
SGD (w. momentum)
1(p)
1
R"
AdaGrad
v r(t) + 61
R"
RMSProp
r(t) + 61
R
ADAM
1-art + 81
r(t)
R
I=pp
v (t))
AMSGrad
P F(t) = max (F(t (t 1), rt)))
R"
ADABound
R
clip(((1) (oortt///(()))) (+())mm000 (0)mm
Table 1:
Connection between the proposed framework and existing methods, where p. B, and 8 are some predefined constants. Ir(t) = r(t - 1) + g(t) g()). fr(t) = 3r(t 1) + (1)))
where c(t) is stepsize (learning rate) for the weight and c(t) E (0, 1]. Note that x 1) is feasible as long as (t) is feasible, as it is the convex combination of two feasible points æ<()) and @(() while the set X is convex.
The above steps () are summarized Algorithm [] which is termed proximal-tyye -yype Stochastic Gradient Descent (ProxSGD), for the reason that the explicit constraint x X in 7 can also be formulated implicitly as a regularization function, more specifically, the indicator function &g (a:). all elements of T (t) are equal, then @(t) is exactly the proximal operator
(+))= argmin {
1
[1
(a(a)) - T(t) -(0)0(1 v(1)
|:- (
(a(1)
1
)()))
12 + -(0) r())(())) + 8x 8x(())
(m(1)) =(t) m(1)
A Prox POay (())+82(1))
Algorithm Proximal-type Stochastic Gradient Descent (ProxSGD) Method
Input: x00) X, v(-1) = 0, t = 0, T, (p(t))==o(() (c(t))=v(().
for f = 0: do
1. Compute the instantaneous gradient g()) based on the minibatch M((():
g(t)
Σ
Vafi((())) ()).
m(t) iEM(()
2. Update the momentum: vtt) = (1 p(t))v(t - 1) + (())
3. Compute (t) by solving the approximation subproblem:
@(t) = arg min (x- (0))(())()o(()) + = x - diag)))))))) x(t)) + r(m))
4. Update the weight: æ(t + 1) = xtt) + ((t)()(t) - (tt))
end for
ProxSGD in Algorithm bears a similar structure as several SGD algorithms, without and with momentum, see Table [ and it allows to interpret some existing algorithms as special cases of the proposed framework. For example, no momentum used in SGD, and this amounts to setting p(t) = 1 in Algorithm In ADAM, the learning rate for momentum is constant p and the learning rate for the weight vector is given by e/(1 - p¹) for some c, and this simply amounts to setting p(t) = p and c(t) c/(1
(1-p')-)) p²) in Algorithm 1 This interpretation also implies that the convergence conditions to be proposed shortly later are also suffeient for existing algorithms (although they are meant be the weakest conditions available in literature).
4

---

Published as a conference paper at ICLR 2020
Solving the approximation subproblem 77 Since 7 is strongly convex, z(t) is unique. Gener- ally æ(t in 7 does not admit a closed-form expression and should be solved by a generic solver. However, some important special cases that are frequently used in practice can be solved efficiently.
The trivial case
I² and r 0, where
v(t)
a(t) - xx))
(9)
(t))
where the vector division is understood to be element-wise. When X = R and r(x)) = 1||2=111, (tt) has a glosed-form expression that is known as the soft oof-thheesholding operator
v(()
(
ml F(3)
axtt)
T(t)
(10)
where Sa (b) A max(b a, 0) max( b 0) Baach et al.
2011
If R and r(x) /1| and (t)) = II for some т, then Parikkh & Boyd 2014)
.(t) = (1 p/ f/ll (1)ll2) (x(t) (88/T), if (t= et)ll2 2 μ.
(11)
0,
otherwise.
If is divided into blocks æ2, ... the & regeaulaaiizttion is commonly used to promote block sparsity (rather than element sparsity by & E1-regularizatoon.
When there is a bound constraint S x S u, (tt) can simply be obtained by first solving the approximation subproblem (7) without the bound constraint and then projecting the optimal point onto the interval [t, u.. For example, when X = 1²" and r O,
v(t)
((t)= x(t) [
(12)
with [æ]]] = clip(æ, I, u) A min (max(x:;)))) u).
If the constraint function is quadratic: X = {x ||>1 < 1), E(t) has a semi-analytical expression (up to scalar Lagrange multiplier which can be found efficiently by the bisection method).
Approximation subproblem. We explain why we update the weights by solving an approxi- First, we denote f as the smooth part of the objective function in 7. Clearly it depends on xxt) and v(t) (and thus M())), while xxt) and v(t) depend on old weights
mation subproblem
arl 1) and momentum and v0),...., v(l - 1)- Define IF(I) - (a(00).... .., ((),, M(O), M((1) as a shorthand notation for the trajectory generated by ProxSGD.
We formally write f
j(w: (F))) A (a - (ot=)())TTt(( v()) + 2 dia)))(((7)) xx(())))))))))).
(13)
It follows from the optimality of ((t) that
f(=(t): + r(x(()) 2 F()());(()) +()())).
After inserting (33 and reorganizing the terms, the above inequality becomes
(a(t) (t)) r(a(t) ((()) r(x(t)) S -T())(((t) (t))
(14)
Since fx) is Lipschitz continuous with constant L, we have
f(x(t + 1)) + + 1)) r(z(t)))))()))))
< + 11 -))(++)))(())))(/(//// + | ||a(t + - + r(x(t + 1)) - -r(((t))
(15)
+ r(((t)) ((())))(((())))))))))))))))))))) ( L (t) -
- x())1
(16)
where the first inequality follows from the descent lemma (applied to f) and the second inequality follows from the Jensen's inequality of the convex function and the update rule R8
5

---

Published as a conference paper at ICLR 2020
If ( V f(x(t) (which is true asymptotically show shortly later), by replacing f
in 16 by (t) and inserting (14) into (16). we obtain
f(x(t + 1)) + r(=lt 1)) (f(=(()) + +r((()))))))) S <(t)) (1)
|a( x<t) (17)
The right hand side (RHS) will be negative when e(t) < 2010 this will eventually be satisfied as shall use decaying c(t). This implies that the proposed update (8) will decrease the objective value of (T) after each iteration.
Momentum and algorithm convergence. It turns out that the momentum (gradient averaging step) in 66) is essential for the convergence of ProxSGD. Under some mild technical assumptions we outline now, the aggregate gradient v(t) will converge to the true (unknown) gradient V fxx()) This remark is made rigorous in the following theorem.
Theorem 1. Assume that the unbiased gradient gtt) has bounded second moment
E [llg(t) & [F(()] S C,
(18)
for some finite and positive constant C, and the sequence of stepsizes {p(t)} and {<(t)} satisfy
(t)
c(t) Σ p(t)) = 00, Σ p()) < <0,, =x
<
0o, lim
t-000 p(t) = 0.
(19)
t=0
t=0
t=0
Then lim, 000 [|((1) point of w.p.l.
(=(((())) 0, and every limit point of the sequence (æ{(1} is stationary
Proof. Under the assumptions 18 and 19p. it follows from Lemma of Ruszczyúski (980) that
v(t) + (=)(())) Since the descent direction ((t) xxt) a descent direction in view of (14). the convergence of the ProxSGD algorithm can be obtained by generalizing the line of analysis in
Theorem 1 of Yang et al. (2016) for smooth optimization problems. The detailed proof is included in the appendix make the paper self-contained.
We draw some comments on the convergence analysis in Theorem
The bounded second moment assumption on the gradient g in (18) and decreasing stepsizes in (19) are standard assumptions in stochastic optimization and SGD. What is noteworthy is that e(t) should decrease faster than p(t) to ensure that v(t) + f()(()). But this is more of an interest from the theoretical perspective, and in practice, we observe that c(t)/p(t) smaller than 1 usually yields satisfactory performance, as we show numerically in the next section.
a for some constant that
According to Theorem the momentum vtt) converges to the (unknown) true gradient fz(((t)), so the ProxSGD algorithm eventually behaves similar to the (deterministic) gradient descent algo- rithm. This property is essential guarantee the convergence of the ProxSGD algorithm.
To guarantee the theoretical convergence, the quadratic gain z(f) the approximation subproblem 7 should be lower bounded by some positive constant (and it does not even have to be time- varying). practice, there are various rationales to define (see Table Tb. and they lead to different empirical convergence speed and generalization performance.
The technical assumptions in Theorem I may not always be fully satisfied by the neural networks deployed in practice, due to, e.g., the nonsmooth ReLU activation function, batch normalization and dropout. Nevertheless, Theorem still provides valuable guidance the algorithm's 's practical performance and the choice of the hyperparameters.
SIMULATION RESULTS
In this section, we perform numerical experiments to test the proposed ProxSGD algorithm In particular, we first train two SNN to compare ProxSGD with ADAM (Kingma & Ba 2015), AMS- Grad (Reddi et al. 2018), ADABound (Luo et al. 2019 and SGD with momentum. Then we train
'The simulations in Setion 3.1 and 3.3 are implemented in TensorFlow and available at Intpps:/ httph//...omoppyyag///rrrooeeeee The simulations in Section 3.2 are implemented in PyTorch and avail- able at httptttssgttthbb..omm hhc-chhhppiii ttt/ twm/proxsgd

---

Published as a conference paper at ICLR 2020
a BNN to illustrate the merit regularization and constraints. To ensure a fair comparison, the hyperparameters of all algorithms are chosen according to either the inventors' recommendations or a hyperparameter search. Furthermore, in all simulations, the quadratic gain T(t) in ProxSGD is updated in the same way ADAM, with 0.999 (see Table D
3.1 SPARSE NEURAL NETWORK: TRAINING CONVOLUTION NEURAL NETWORKS ON CIFAR-10
We first consider the multiclass classification problem on CIFAR-10 dataset (Krizhevsky) 2009) with convolution neural network (CNN). The network has convolutional layers and each of them is followed by batch normalization layer; the exact setting is shown in Table 2
Table 2: CNN Settings
parameter
value
data sct
CIFAR-10 10
number of convolution layers size convolution kerness
3x3
number output filters in convolution layers 1-2, 3-4, 5-6
32, 64,
operations after convolution layers 1-2, 3-4, 5-6 kernel size, stride, padding of maxing pooling activation function for convolution/output layer loss function regularization function
max pooling, dropout (rate=0.2)
2x2, 2, valid
elu/softmax
cross entropy and & norm
Following the parameter configurations of ADAM in Kingma & Ba (2155) AMSGrad in Reddi ct al. (2018), and ADABound in Luo et al. (019), we set p = 0.1, 3 0.999 and e = 0.001 (see Table D. which are uniform for all the algorithms and commonly used in practice. Note that we have also activated & (-regularrzztton for these algorithms in the built-in function TensorFlow/Py Torch, which amounts to adding the subgradient of the l nnoor to the gradient of the loss function. For the proposed ProxSGD, e(t) and p(t) decrease over the iterations as follows,
0.06
0.9
(1)
(t + 4)0.5' p(1) + 4)0.5
(20)
Recall that the 4--nrrm in the approximation subproblem naturally leads to the soft-thresholding proximal mapping, see (1O). The regularization parameter 4 in the toet-hhresholding then permits
controlling the sparsity of the parameter variable æ;; in this experiment we set 5 10-5
14
AUM
1,00
Welgero Xaloo
(a) Training Loss
(b) Test Accuracy
(c) CDF of Weights
Figure
Performance comparison for CNN CIFAR-10.
In Figure [ we compare the four algorithms (ProxSGD, ADAM, AMSGrad, ADABound) in terms of three metrics, namely, the training loss, the accuracy and the achieved sparsity. On the one hand, Figure aa) shows that ProxSGD outperforms ADAM, AMSGrad and ADABound in the achieved loss value. On the other hand, the achieved accuracy is comparable, see Figure Ib).
The sparsity of the trained model is measured by the cumulative distribution function (CDF) of the weights' value, which specifies the percentage of weights helow any given value. For the proposed

---

Published as a conference paper at ICLR 2020
ProxSGD Figure [)), we can observe at the x-axis the abrupt change of the CDF in the y-axis, which implies that more than 90% of the weights are exactly zero. By comparison, only 40%-50% are exactly zero by the other algorithms. What more, for this experiment, the soft- thresholding proximal operator in ProxSGD does not increase the computation time: ADAM 17.24s (per epoch), AMSGrad 17.44s, ADABound 16.38s, ProxSGD 16.04s. Therefore, in this experi- ment, the proposed ProxSGD with soft-threshldding proximal mapping has clear and substantial advantage than other stochastic subgradient-base based algorithms.
3.2 SPARSE NEURAL NETWORK: TRAINING DENSENET-201 ON CIFAR-100
In this subsection, the performance of ProxSGD is evaluated by a much more complex network and dataset. In particular, we train the DenseNet-201 network (Huang al. 2017) for CIFAR-100 (Krizhevsky) 2009). DenseNet-201 is the deepest topology of the DenseNet family and belongs to the state of the art networks image classification tasks. We train the network using Prox- SGD, ADAM and SGD with momentum. To ensure a fair comparison among these algorithms, the learning rate not explicitly decayed during training for all algorithms. Furthermore, the ideal hy- perparameters for each algorithm were computed by grid-search and the curves averaged over five runs. batch-size of 128 is adopted. For ProxSGD, the regularization parameter = 10-5 the learning rate for the weight and momentum is, respectively.
0.15 (t + 4)u.5 p(t)
0.9
<(t)
(t 4)0.5
For ADAM, = 6 10-1 and p = 0.1. SGD with momentum uses a learning rate of = 6 10-3 and momentum of 0.9 (so p 0.1). The regularization parameter for both ADAM and SGD with momentum is 10-4
1000
Pree 501
Accuracy
Pre 510
54D nomwn.u
0.
Epochs
-0.0
6.0
127
(a) Training Loss
(b) Test Accuracy
CDF of Weights
Figure 2: Performance comparison for DenseNet-201 on CIFAR-100.
Figure shows the performance of ProxSGD and other algorithms for DenseNet-201 trained on CIFAR-10K 100. We see from Figure ((a) that ProxSGD achieves the lowest training loss after Epoch 10. The test accuracy in Figure 2bb shows that all algorithms achieve similar accuracy and ProxSGD outperforms the other two during the early stage of training. We remark that this is achieved with a much sparser network as shown in Figure ([c) In particular, we can see from the zoomed-in part of Figure 2(c) that SGD with momentum has approximately 70% of their weights zero, while most weights learned by ADAM are not exactly zero (although they are very small). In contrast, ProxSGD reaches the sparsity of 92-94%.
In Figure 3 we demonstrate that ProxSGD much more efficient in generating a SNN, irrespective of the hyperparameters (related to the learning rate). In particular, we try many different initial learning rate of the weight vector <(0) for ProxSGD and test their performance. From Figure 3 a)- (b) we see that, as expected, the hyperparameters affect the achieved training loss and test accuracy, and many lead to a worse training loss and/or test accuracy than ADAM and SGD with momentum. However, Figure (e) shows that most of them (except when they too small: e(0) 0.01 and 0.001) generate a much sparser NN than both ADAM and SGD with momentum. These observations also consistent with the theoretical framework in Section 2: interpretating ADAM and SGD with
8

---

Published as a conference paper at ICLR 2020
Accuro
Pre m5r
Nee.30 e6-63
Pe65 66-435
No0000 08-444
No0 08:42.0
300 1w.ee
300 sumerbur
Epocha
Epochs
Weights value
(a) Training Loss
(b) Test Aecuracy
(c) CDF of Weights
Figure 3: Hyperparameters and sparsity for DenseNet-201 on CIFAR 100.
momentum special cases of ProxSGD implies that they have the same convergence rate, and the sparsity due to the explicit use of the nonsmooth & -norm regularization.
For this experiment, the soft-thresholding proximal operator in ProxSGD increases the training time: the average time per epoch for ProxSGD is 3.5 min, SGD with momentum 2.8 min and ADAM 2.9 min. view of the higher level of sparsity achieved by ProxSGD, this increase in computation time reasonable and affordable.
3.3 BINARY NEURAL NETWORKS: TRAINING DEEP NEURAL NETWORKS ON MNIST
In this subsection, evaluate the proposed algorithm ProxSGD in training the BNN by solving problem (3). We train a 6-layer fully-connected deep neural network (DNN) for the MNIST dataset, and we use the tanh activation function to promote a binary activation output; see Table 3 The algorithm parameters are the same as Sec. 3.1 except that = 2 10-4 The chosen setup is particularly suited to evaluate the merit of proposed method, since MNIST a simple dataset and it allows us investigate soly the effect of the proposed model and training algorithm.
Table 3: DNN Settings
parameter
Value MNIST
dataset number of hidden layers number nodes per hidden layer activation function in hidden/output layer loss function
200 tanh/softmax cross entropy
After customizing Algorithm to problem
the approximation subproblem is
(a - vt (t) + {x =t))² diag (f))(x= +(a att)) (t) + {a diag))tt) a(t)) ]
(t()),((t)) = arg min 03a51
Both Z(t) and @(t) have closed-form expression (cf. 9 and 12
(t) and @(t) a(t) (t)))
att) xxt)
(21)
T (t)
(t)
where vn (1) and (1) the momentum updated in the spirit of 66. with the gradients given by
(t) mtt) (EM(()
Σ fi(w(t)) ( 1 (a(() + 2a(t) 1), and gt = par(t).
The training loss is shown Figure a). We remark that during the training process of ProxSGD, the weights are not binarized, for the reason that the penalty should regularize the problem in way such that the optimal weights (to which ProxSGD converges) are exactly or close to or -1. After training is completed, the CDF of the learned weights is summarized in Figure 4c., and then the

---

Published as a conference paper at ICLR 2020
AAaurnee 0.5
40
PCC
of
Weight
(a) Training Loss
(b) Test Accuracy
(c) CDF of Weights
Figure 4: Performance comparison for BNN on MNIST
learned weights are binarized to generate full BNN whose test accuracy is in Figure (b). On the one hand, we see from Figure 4 a)-(b) that the achieved training loss and test accuracy by BNN is worse than the standard full-precision DNN (possibly with soft-thresholding), This is expected as BNN imposes regularization and constraints on the optimization problem and reduces the search space. However, the difference in test accuracy is quite small. On the other hand, we see from Figure (c that the regularization
the proposed formulation (3) is very effective promoting binary weights: 15% of weights are in the range (-1,-0.5) and 15% of weights are in the range (0.5,1), and all the other weights are either - or 1. As all weights are exactly or close to or -1, we could just binarize the weights to exactly or -1 only once by hard thresholding, after the training completed, and thus the incurred performance loss is small (98% versus 95% for test accuracy). In contrast, the weights generated by the full-precision DNN (that is, without regularization) smoothly distributed in [- 2].
Even though the proposed formulation 3) doubles the number of parameters to optimize (from æ in full full-precision DNN to (ær, a) in BNN ProxSGD), the convergence speed equally fast terms of the number of iterations. The computation time is also roughly the same: full-precision DNN 13.06s (per epoch) and ProxSGD 12.21s. We remark that ga (t), the batch gradient w.r.t. a, has closed- form expression and it does not involve the back propagatio.. In comparison with the algorithm in Courbariaux et al. (216)). the proposed ProxSGD converges much faster and achieves a much better training loss and test accuracy (95% versus 89%, the computation time per epoch for Courbariaux et al. (2016) is 13.56s). The notable performance improvement is due to the regularization and constraints. Naturally but this effort is very well paid off. Furthermore, we observe in the simulations that the performance sensitive the exact value of μ. as long as it is in appropriate range.
should make effort of searching for proper regularization parameter js,
CONCLUDING REMARKS
In this paper, we proposed ProxSGD, proximal-type stochastic gradient descent algorithm with momentum, for constrained optimization problems where the smooth loss function is augmented by nonsmooth and convex regularization. We considered two applications, namely the stochastic training of SNN and BNN, to show that regularization and constraints can effectively promote struc- tures the learned network. More generally, incorporating regularization and constraints allows us to use more accurate and interpretable model for the problem at hand and the proposed convergent ProxSGD algorithms ensures efficient training. Numerical tests showed that ProxSGD outperforms state-of-the-arr algorithms, in terms of convergence speed, achieved training loss and/or the desired structure in the learned neural networks.
ACKNOWLEDGEMENT
The work of Yang is supported by DFG Project DeTol. The work of van Sloun is part of the research programme Rubicon ENW 2018-3 with project number 019.183EN.014, which is financed by the Dutch Research Council (NWO). The work of Yuan, Lei and Chatzinotas supported by ERC AGNOSTIC, FNR CORE ASWELL and FNR-AFR LARGOS.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Sparsity-nduccing Inducing Penalties. Foundations and Trends Machine Learning. 4(1):1-106, 2011.
Optimization with
doi: 10.1561/22000000155 URLbttp://azxe .rg. httgg//b///ao wttaabssoooo 1108. 0775
Yu Bai, Yu-Xiang Wang, and Edo Liberty. Proxquant: Quantized neural networks via proximal operators. In International Conference on Learning Representations, 2019. URL https://
openreview Ryyayyyaay
Dimitri P. Bertsekas and John N. Tsitsiklis. Gradient convergence in gradient methods with errors.
Journal on Optimizatiion, 10(3):677-642 2000. doi: 10.1137//10053664497316666 URL
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1), 2010. doi: 10. 10.1561/2200000016 URL http: /wwww nowpublishers wwt.poowoostccccccooccooottotcee aspx www.:ouucc..spppppooddcccc.. MAL J
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the Convergence of A Class of Adam- Type Algorithms for Non-Convex Optimization. In International Conference on Learning Repre- sentations, 2019, hww.tttp://axx...rr////
.29941
Matthieu Courbariaux, Yoshua Bengio, and Jean- David. Binaryconnect: Training deep neural networks with binary weights during propagations. In Advances in Neural Information Processing Systems 28, pp. 3123-3131, 2015.
Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El- Yamiv, and Yoshua Bengio. Bina- rized Neural Networks. In Advances in Neural Information Processing Systems 29, 2016. URL https://papers: nips aat..ccc/paper/77--iiiaaaa-a-ee -ewa--iiiiiiiidd-u-a----------e- wwwwwwoss.......ss......... pdf
Trevor Gale, Erich Elsen, and Sara Hooker. The State of Sparsity in Deep Neural Networks. 2019. URL
htrpg//bs/1992. 09574
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Lu Hou, Quamming Yao, and James T. Kwok. Loss-aware binarization of deep networks. In Interna- tional Conference Learning Representations, 2017. URL /ttps:://penrrvveew wwt.irreeiieeee///////
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. The Conference on Computer Vision and Pattern Recognition, 2017.
URL htttp:://axxi..oot http:iii.orrga//////oo/ abs/1608. 06993
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In Inter- national Conference on Learning Representations, 2015. URL http::tpp///i...ooo/ abs/
1412. 6980
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009. URL https 7/www. cs. toronto. wdw/ http:///wiiiieeaaaannaaaaataeeee 2009- TR.
Yunwen Lei, Ting Hu, and Ke Tang. Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions. to appear in IEEE Trunsactions on Neural Networks and Learn ing Systems, 2019. URL URL wtt.httts//// htt:://eeeeeppplro feee. www.or////wooon.ttoo 89300994
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning Sparse Neural Networks through Ly Regularization. In International Conference Learning Representations, 2018.
Liangchen Luo, Yuanhao Xiong. Yan Liu, and Xu Sun. Adaptive Gradient Method with Dynamic Bound of Learning Rate. In International Conference on Learning Representations, 2019. URL
http::/arxiin www. wwtp:r/g/a//.....///.//

---

Published as a conference paper at ICLR 2020
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, (3):127-239 2014. doi: 10.1561/2400000003. URL/attp://ww..notett articles/
com/
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of ADAM and beyond. In International Conference on Learning Representations, 2018. URL http::/arxiv.com org/
abs/1904, 09237
Andrzej Ruszezyúski.
Feasible direction methods for stochastic programming problems. Math-
ematical Programming, 19())220-222, December 1980. doi: 10. 10.1007/FF01581443 URL
htttp://wwx http://wwwwss.ingeee/eemm www.sgeriiiinnnme www/indewwi...n..cccc 10000//FF0181666
Yang Yang, Gesualdo Scutari, Daniel P Palomar, and Marius Pesavento. A parallel decomposi- tion method for nonconvex stochastic multi-agent optimization problems. IEEE Transactions on Signal Processing, 64(11))2999-2964, June 2016. doi: 10. 10.109979P20011236677, URL
http://ieeexploore ieee. org/ /ttp.//ccoocccmme//////////////
Penghang Yin. Shuai Zhang, Jiancheng Lyu, Stanley Osher, Yingyong Qi, and Jack Xin. Bina- ryRelax: A Relaxation Approach for Training Deep Neural Networks with Quantized Weights.
SIAM Journal on Imaging Sciences, ((4):2205-2223, January 2018. URLhttpps :/ap:ps:///pb.../////
siam. wwt./orgg//o/ooooooo 1ew.111111111 8M1 666334
12

---

Published as a conference paper at ICLR 2020
A APPENDIX: PROOF OF THEOREM 1
Proof. The claim li (( = 0 is a consequence of [Ruszczyúskii 1980 Lemma
1). To see this, we just need verify that all the technical conditions therein are satisfied by the problem at hand. Specifically, Condition (a) of (Ruszczyński 1980 Lemma 1) is satisfied because
X is closed and bounded. Condition (b) of (Ruszczyúski 1980 Lemma 1) exactly (18). Con-
ditions (c)-(d) of (Ruszczyússki 1980 Lemma 1) come from the stepsize rules in (19) of Theorem Condition (e) of (Ruszczyáski) 1980. Lemma 1) comes from the Lipschitz property of V and
stepsize rule in (19) of Theorem]
We need the following intermediate result prove the limit point of the sequence az(t) is stationary point of
Lemma 1. There exists a constant L such that
[[(()(()). ((())))) & L [|x(4) - a=22) |l + e(((,
and lime, 12 c(t1, 12) w.p.
Proof. We assume without loss of generality (w.l.o.g.) that T(t) r1, and the approximation subproblem (7) reduces to
a(t)
argmin { ((t==(t))=ou)) v(t) " 1110 1e--an -=(x)))) r(a))
-
It is further equivalent to
{ (aa-xrk -a())( vt)) + 2 x1)113 + m
min =xX,r(m)Sv
(22)
where the (unique) optimal æ and y is (a(t) and r(t(t)) respectively.
We assume w.l.o.g. that t2 t1. It follows from first-order optimality condition that
(x =t,)) (m(ti) + r = =(t+))) r(((t)))))))))) 2 0, Ya, such that r(x:) S y (x (c-)(tz)) ((()))) =(t2)) (+(t)((t)) Ya, such that r(x:) S y. (23b)
(23a)
Setting (x, y) =
in 23a and (x. v) = (. r((t)) 23b). and adding
them up, obtain
--((()) a(12) -- (24)
The term the left hand side can be lower bounded follows:
(a(1)) (()) - ((((((22))
+ (ā(tz) - a(t2), -f(a((t))))(((((())))) ((((t) - =(t2), x(11) - =x(t2)
2 - ||a(t,) - a(t2) ((((t) + +((2) (L++)]| - -
- =x(2)) (25)
where the inequality comes from the Lipschitz continuity of Vf(z). with e(t) 4
[[o((]) - (/(x(()
Combining the inequalities 24 and 225 we have
||((1)) ((z)) < +)+ - [|
x0(22|l + + a(()l +e(l2))
which leads to the desired (asymptotic) Lipschitz property:
||a(ti) ((t2)|| < Dl(0(tt)= sa(ta)l + e(t1,
with ī a 7- + 7) and e(t,, t2) ع -- (E(tr) + E(t2)), and -im e(t), = w.p.
13

---

Published as a conference paper at ICLR 2020
Define U(x) - f()) + r()). Following the line of analysis from 15) to 166, we obtain
U(z(t+ (x((t))
(26)
(00))) x(t)
I <<(t)((((t)
((t)( - =(t)) - v(t) + u(t) + r(t(t) - r(((t))) + L - ((())) - (t)]l
x())]
2
- cc(t) (T マ ct)) [(t)) =(())² + (t)) - ((t) ff(x(t)) e(t)l
(27)
where in the last inequality we used 14 and the Cauchy-Schwaal inequality.
Let us show by contradiction that lim inf ( (((())==(()))) (()
0 w.p.1. Suppose lim inf; ||((1)
||](-)=<|@(((--
x<t||| 2 with a positive probability. Then
find realization such that at the same time
(tt) -(t)| 2 X > for all t and limy-+oo (f(((t)) xt)) O; we focus next on such
realization. Using (t) - (t)]l 2 x > 0, the incquality 27 is equivalent to
1)) (xx(t)) s -e(t) ( (-- L (<0) - Vf(((()) ((()() || =t)) (28)
Since lom; v((((()) | - =t)] = 0, there exists a to sufficiently large such that
7 (t) 1 ((()
= 2
Vtz to
(29)
X
Therefore, follows from 28 and 299 that
((x(()) - (x S - -xx (1=
(30)
which, in view of Ea e+1 oc, contradicts the boundedness of {U (x(())) Therefore must be lim inf [+(1) (1)]l = 0 w.p.1.
Let us show by contradiction that lim (()(() xt))
w.p.1. Suppose
lim sup [t=(t) - xx(|]] > O with a positive probability. We focus next on a realization along with lim sup, [((1) x()] > 0, lime-voo/V
v(Ill o, lim inf [t))
ax|||| 0, and lim 2(4,42) O, where ((4 is defined in Lemmal It follows from lim sup, [[) =(t)l| > 0 and lim iiminf [(()) x<t)]| that there exists a 5 > 0 such that ||4x(()] 2 (with (t & @(t) a=t)) for infinitely many and also [[])]) <
for infinitely many t. Therefore,
can always find infinite set of indexes, say T. having the following properties: for any & E 'T, there exists an integer i, > t such that
|(x(t)| 6, ||a((+))) 28, 8 < || s 28, < n < 4.
(31)
Given the above bounds, the following holds: for all & TT
_ | - ||4x(()]
[aa(i))) - Az((1) = (@
- (a(() x(1I)
@((i) - -0(t)]l + |||=(it)) - xx(t
$ (1 + 1.) (0((=(())) - x + t(
(1 i>> ((n) [x())) + t(i,,t)
< 25(1 + D
1 (n) + +((r,
(32)
implying that
lim inf Σi-1 ((n) 2 81 ع 100
>0
(33)
2(1 + 1.)
Proceeding as in
b2.. we also have: for all t E T,
|| + +1]l |Aa(((]] s ||Ax(1 11 Ar(()) (1 ())((()) (|A((()) + -01, 1),
14

---

Published as a conference paper at ICLR 2020
which leads to
(1 + (1 + ()e(t) [t)) + e(t,++
A + 1)1l 2 8,
(34)
where the second inequality follows from 31 follows from 34 that there exists a 82 > 0 such that for sufficiently large E T.
8 - ((,tt+
| >
2 82 0.
(35)
1+ (1 D)e(t)
Here after we assume w.l.o.g. that (35) holds for all t E T (in fact one can always restrict (a(t))et to proper subsequence).
We show now that (33) is in contradiction with the convergence of (U(z(t))) Invoking 27 we have for all t E T.
L U(x(1 + 1)) - (zx(t)) S -e(t)
ze-)(( |0(1)- =x(1]] + +((()))) -())
L <(t)
V ( -
S -e(()
7 -- e(t)
- |=(1)=<(1)|]
8
+ + v(0)3
(36)
and for t < n < it.
Vf(x(n)) v(n)l]
U(x(n + 1)) - U(x(n)) $ -c(n)
r - (n)
||((n) - =<n)]²
2
[ =(n)]
Vf(((n)) v((i)]
S -e(n)
--
(n)
||ā(m) a=())1
2
(37)
where the last inequality follows from Adding 36 and over I,..., 1 1
and, for E T sufficiently large (so that 7 [f(((tt) - v(t)ll 782/8), we have
Le(t)/ 8 f()(n)) v(n)]
8 > 0 and
U(x(ie)) - (x)(t)) (0)
- 7 EΣE (n) - x(n)]| + ct)) vf((((()) - =()ll
-78 Eh c()) c(t) (785 {l(()(z(t)) - =(t)
3
-783 cx=tte(n))
(38)
where (a) follows from Tc(1)/2 8-1 ( w(n)] 7 (b) is due (35
and in (c) we used [=x((t)) vt) < 75. 5. Since (U(x(t))) converges, it must be
lim inf E = 0, which contradicts (33). Therefore, it must be lim sup a(t) Tet-10
a0Ol| = W.p.1.
Finally, let prove that every limit point of the sequence (a(()) is a stationary solution of (1. Let x" be the limit point of the convergent subsequence (a(t))eT Taking the limit of 23a over the index set T (and replacing w.l.o.g. y by r(æ)), we have
lim (xc ((t)) + (a(1) - xx)))) + r(x) - r()(t))
= (a (Z') - r(xx) 20, Vx E X,
where the last equality follows from: i) lim, ())((()) -(() || = O. and ii) lim (-000 at)] = 0. This is the desired first-order optimality condition and x² is a stationary point of I
((1)
15


Reviews:
[{"review_id": "Skx2lGd6Kr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n[Summary]\nThis paper proposes Prox-SGD, a theoretical framework for stochastic optimization algorithms that (1) incorporates momentum and coordinate-wise scaling as in Adam, and (2) can handle constraint and (non-smooth) regularizers through the proximal operator. With proper choices of hyperparameters, the algorithm is shown to converge asymptotically to stationarity, for smooth non-convex loss + convex constraint/regularizer. The algorithm is empirically tested on training binary and sparse neural nets on MNIST and CIFAR-10.\n\n[Pros]\nThe theoretical framework that incorporates most of the commonly used tweaks in stochastic optimization for deep learning, and a convergence result that establishes broadly the asymptotic convergence to stationarity.\n\n[Cons]\nThe result of Theorem 1 sounds rather a straightforward application of classical results; important sub-cases such as Adam violates the assumption (Adam has \\rho_t = \\rho so \\sum \\rho_t^2 = \\infty) and thus are not contained in this case. From this it seems to me Theorem 1 says things mostly about the “easier” sub-cases, and thus is perhaps not very surprising and a bit limited in bringing in new messages. \n\nThe experiments are mostly done on simple problems --- 3 of the 4 figures are on MNIST. The specific tasks (training sparse / binary neural nets with MLP / vanilla CNN architectures) considered in the experiments are all very extensively studied in prior work, and the results in this paper says at most that the proposed Prox-SGD works for these tasks.\n\nOverall, I like the idea in this paper that we can put together a unified framework for stochastic optimization algorithms and incorporate things like momentums and regularizations that were previously treated separately. However, beyond proposing such a framework, it seems that contributions on both the theoretical and empirical side are a bit limited at this point.\n\n***\n\nThank the authors for the response and the efforts in revising the paper. I am glad to see the additional experiments for training sparse networks on CIFAR-100 (a much harder task than MNIST and also CIFAR-10) in which the proposed method works well. This largely resolved my concerns on the experimental side. \n\nHowever, I'd still like to hold my evaluation on the theoretical side, in that approaches for handling constraints / non-smoothness / momentums are fairly well understood in the optimization literature. The present result (Theorem 1) conveys the message that these approaches can be combined to work (give an algorithm that converges to stationary points if it converges), but is not really a result that gives us new understandings / novel proof techniques beyond that.\n\nI have slightly improved my rating to reflect my updated evaluation.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxQie4LcS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new gradient-based stochastic optimization algorithm (with gradient averaging) by adapting theory for proximal algorithms (originally developed for convex problems) to the non-convex setting. The main idea is to first use an averaged gradient plus a quadratic term to locally approximate the non-convex function with a convex smooth function before applying the proximal operator on it. As a result, the algorithm will be able to solve non-smooth (e.g., l1-regularized) and constrained non-convex problems, which will be very useful for optimization problems arising from deep learning.\n\nI think this is a potentially good paper that proposes an algorithm for wide applicability. But I still see some issues that prompts me to ask the following questions:\n\n1. What is the time complexity of solving the sub convex problem at every iteration? The authors did not discuss this in the experiments, but this is very important in evaluating the applicability of the proposed algorithm especially on large-scale problems.\n2. The authors should provide more explanation on the term \\tau (t): It seems it is only used as an auxiliary parameter in the quadratic approximation of f, and that it doesn't affect the convergence asymptotically. But I would imagine it would affect the practical convergence at the beginning of the algorithm?\n3. The authors have repeatedly mentioned that using the averaged gradient v(t) is very important for the convergence analysis of the algorithm. But I did not see how this is the case from the analysis discussed in the paper (I didn't check the proof in reference Ruszczynski (1980)). As this is important in justifying the algorithm, I think the authors should include a discussion to provide some intuition on this in the paper.\n4. Line (15): should vx(t) be x(t) instead? If not, where does the term come from?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byx3w9ePqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper introduces and analyzes a training algorithm for neural networks with non smooth regularization and weight constraints (such as sparsity or binarization). The analysis shows that, under assumptions, the proposed algorithm converges almost surely to a stationary point. Experimental results show that the proposed algorithm can train both sparse and binary neural networks.\n\nMajor comments:\n\nThis paper presents an interesting combination of theoretical analysis and experiments demonstrating the benefits of the proposed training algorithm. Because the setting considered is fairly general, it is likely to be widely useful in a variety of settings that have up to now been approached with case-specific algorithms (eg training binary NNs). \n\nIt should be noted that objective functions for many NNs are not smooth (eg ReLU-based networks, which are used in the experiments) and the convergence argument does not apply directly to these. \n\nThe paper could be improved by more extensively optimizing hyper parameters of all algorithms in the experimental evaluation. From the current experiments, it is not possible to evaluate whether performance differences are coming from differences in learning rate schedules, etc, or from the proposed algorithm specifically. For instance, the competitor algorithms are run with fixed momentum and learning rate parameters, while the proposed algorithm is run with a handcrafted decay in these parameters. Ideally, the hyperparameters should be optimized out such that each algorithm uses its best settings. At minimum, the choice of hyperparameter schedule for the algorithm should be justified. \n\nThe paper could also be strengthened by comparing the runtime of the proposed algorithm to prior methods. Prox SGD trains faster in terms of iterations (hyper parameter differences aside), but how about wall clock time? This is particularly important in the binary case where additional optimization parameters are added and updated in each iteration.\n\nThe main theoretical result is presented with a sketch of a proof, and I did not attempt to reconstruct the argument from the named sources. It could be useful to provide a full proof (perhaps in an appendix) to allow the work to be self-contained.\n\nThe paper is clearly written and easy to follow.\n\n\nTypos:\nIn general more care should be taken with the equations:\nEq. 7 x^t should be x(t)\nEq. 7 differs slightly from Alg. 1 step 3 because of the \\mu term in step 3. I would remove \\mu \nPg 3, the indicator function is introduced as \\sigma_X then put in the equation as \\delta_X", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new gradient-based stochastic optimization algorithm by adapting theory for proximal algorithms to the non-convex setting. 

The majority of reviewers voted for accept. The authors are encouraged to revise with respect to reviewer comments.
Decision: Accept (Poster)