Adaptive Proximal Gradient Methods for Structured Neural Networks
Authors: Jihun Yun
Aurelie Lozano
Eunho Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Proximal Gradient Descent for Adaptive Methods
Stochastic Optimization
Non-convex Optimization

Abstract: We consider the training of structured neural networks where the regularizer can be non-smooth and possibly non-convex. While popular machine learning libraries have resorted to stochastic (adaptive) subgradient approaches, the use of proximal gradient methods in the stochastic setting has been little explored and warrants further study, in particular regarding the incorporation of adaptivity. Towards this goal, we present a general framework of stochastic proximal gradient descent methods that allows for arbitrary positive preconditioners and lower semi-continuous regularizers. We derive two important instances of our framework: (i) the first proximal version of \textsc{Adam}, one of the most popular adaptive SGD algorithm, and (ii) a revised version of ProxQuant for quantization-specific regularizers, which improves upon the original approach by incorporating the effect of preconditioners in the proximal mapping computations. We provide convergence guarantees for our framework and show that adaptive gradient methods can have faster convergence in terms of constant than vanilla SGD for sparse data. Lastly, we demonstrate the superiority of stochastic proximal methods compared to subgradient-based approaches via extensive experiments. Interestingly, our results indicate that the benefit of proximal approaches over sub-gradient counterparts is more pronounced for non-convex regularizers than for convex ones.

Adaptive Proximal Gradient Methods for Structured Neural Networks
Jihun Yun
Aurélie C. Lozano IBM T.J. Watson Research Center aclozanokus ibm. com
Eunho Yang KAIST, AITRICS eunhoy@kaist. ac.
KAIST
areprine@kaist.aac
Abstract
We consider the training of structured neural networks where the regularizer be non-smooth and possibly non-convex. While popular machine learning libraries have resorted stochastic (adaptive) subgradient approaches, the use of proximal gradient methods in the stochastic setting has been little explored and warrants further study, in particular regarding the incorporation of adaptivity. Towards this goal, we present a general framework of stochastic proximal gradient descent meth- ods that allows for arbitrary positive preconditioners and lower semi-continuous regularizers. We derive two important instances of our framework: (i) the first prox- imal version of ADAM, one of the most popular adaptive SGD algorithm, and (ii) a revised version of PROXQUANT [1] for quantization-speclll improves upon the original approach by incorporating the effect of preconditioners in the proximal mapping computations. We provide convergence guarantees for our framework and show that adaptive gradient methods can have faster convergence in terms of constant than vanilla SGD for sparse data. Lastly, we demonstrate the superiority of stochastic proximal methods compared to subgradient- based approaches via extensive experiments. Interestingly, results indicate that the benefit of proximal approaches over sub- gradient counterparts more pronounced for non-convex regularizers than for convex ones.
regularizers, which
Introduction
We study the regularized training of neural networks, which can be formulated the following (stochastic) optimization problem
f(0)
minimize F(6) Eç-r [B: +R(()
where 0 Rdd represents the network parameter, is the random variable representing mini-batch data samples, and R(-) is regularizer encouraging low-dimensional structural constraints on 0.
The technique of regularization is ubiquitous in machine learning as it can effectively prevent overfitting and yield better generalization. The Errreuularized training for Lasso estimators/sparse Gaussian graphical model (GMRF) estimation [2, 3] and & weight decay [4] parameters prototypical examples. In the context of deep learning, important instances include network pruning [5, 6], which induces sparse network structure, and network quantization [7, 8, 1], which gives hard constraints so that parameters have only discrete values.
For the unregularized case, i.e., when R(0) O, stochastic gradient descent (SGD) has been prevalent approach to solve the optimization problem stated in (I), At each iteration, SGD evaluates the gradient on randomly chosen subset of training samples (mini-batch). While vanilla SGD employs a uniform learning rate for coordinates, several adaptive variants have been proposed to
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Comparison among stochastic (or online) PGD for solving the problem in (1).
Non-convex Loss
Non-convex Regularizer
Arbitrary Preconditioner
Convergence
Algorithm
Momentum
Guarantee
ADAGRAD [9]
(ADAGRAD)
[10]
X
[11]
X
[12]
[13]
[14]
/
X
[15]
/
A
(ADAGRAD)
Prox-SGD [16]
X
[17]
PROXGEN (Ours)
dynamically take advantage of the data geometry by scaling the learning rate for each coordinate by its gradient history. Prime examples of such approaches include ADAGRAD [9], which adjusts the learning rate by the sum of all the past squared gradients, and exponential moving average (EMA) approaches such as RMSPROP [18] and ADAM [19]. which scale down the gradients by square roots of exponential moving averages of squared past gradients to essentially limit the scope of the adaptation to only few recent gradients. In terms of theory, convergence analyses of these unregularized SGD methods, whether adaptive or not, have been well studied both for convex [19, 20] and non-convex [21, 22] loss cases.
For the regularized case, since the regularizer is often non-smooth around some region (e.g. the I norm), modern machine learning libraries such as TensorFlow [23] and PyTorch [24] therefore resort to using the subgradient of the objective function F(0) in (1), Such strategy is problematic as it may slow down convergence and result in oscillations.
A simple idea to bypass the non-smoothness of a regularizer is via its proximal operator. This idea is the basis of proximal gradient descent (PGD) methods, which first update the parameter using the gradient of the loss function f() and then perform a proximal mapping of (()). In the non-stochastic case, PGD with both convex and non-convex regularizers has been extensively studied in the literature [25, 26, 11, 12, 27]. Another work, VMFB [28], analyzes the preconditioned gradient descent on convex regularized problems with non-convex loss but does not consider the first-order momentum. In contrast, PGD in the stochastic setting has been little explored. [9, 10] consider PGD to solve the stochastic objectives with convex regularizers. Recently, [15] studies non-convex and mon-smooth regularized problems for DC (difference of convex) functions and [14, 17] present non-asymptotic analysis for non-convex smooth loss and non-convex regularizers, which the most general setting, but do not consider the preconditioner in the update rule.
All the aforementioned studies of the stochastic case, however, focus either on limited settings (e.g. [9] only covers the update rule of AdAGRAD) with convex regularizers only, or on pure vanilla gradient descent for non-convex regularizers. Hence, they cannot accommodate all advanced modern optimization algorithms with preconditioners, such as adaptive gradient methods. The only exception PROX-SGD [16], with the caveat that PROX-SGD update rule is not a pure PGD. Moreover, the theory in [16] only guarantees convergence, not how fast Prox-SGD converges, and the analysis is performed without considering preconditioners.
In this paper, we propose an exact framework for stochastic proximal gradient methods with arbitrary positive preconditioners and lower semi-continuous (possibly non-convex) regularizers. With framework, our goal is to provide theoretical and empirical understanding of stochastic proximal gradient methods for training structured neural networks. Our main contributions can be summarized as follows:
We propose the first general family of stochastic proximal gradient methods, which we term PROXGEN. We introduce two important instances stemming from our approach: (i) the first proximal version of ADAM [19] and (ii) revised version of PROXQUANT [1] that improves upon the original approach for quantization- specific regularizers by incorporating the effect of preconditioners when computing proximal mappings.

---

Algorithm PROXGEN: A General Stochastic Proximal Gradient Method
1: Input: Stepsize ot, {p= [0, 1), regularization parameter A, and small constant <
2: Initialize: 01 E IRd mo = 0 Rd and Co O E [d
3: for trtt- 1, do
4: Draw minibatch sample& from P
5: 9t < f((;;
> Stochastic gradient
6:
m. P= (1 pe)g
1sth ordord momentum
7: C. 4 Preconditioner construction
1 (0 (0-00) (C))(C++))))) (0) 0.3}
8:
Oct1 E argmin (m.. + XR(O) + 204
Di Update rule
BE
9:
end for
We analyze the convergence of the general PROXGEN family and identify essential conditions for convergence. We show that in general PROXGEN enjoys the same convergence rate vanilla SGD, but more importantly that the adaptive methods can have faster convergence in terms of constant than vanilla SGD for sparse data. Our convergence guarantee encompasses several existing approaches as special cases.
terms of practice, we demonstrate the superiority of proximal methods over subgradient-ban methods with various non-convex regularizers which have not yet been studied in deep learning. Interestingly, our experiments indicate that the benefit of proximal methods over subgradient approaches is more pronounced with non-convex regularizers than with convex regularizers for learning sparse deep models.
Table 1 summarizes the previous studies and our work in terms of stochastic PGD.
2 A Unified Framework of Adaptive Proximal Gradient Methods
In this section, we present PROXGEN, general family of stochastic proximal gradient methods, and present both existing and novel instances showcase examples in family. Algorithm 1 describes the details of PROXGEN. The update rule on line 8 of Algorithm can be written more compactly:
a argmin (me, 0) XR(() + AEn
(0 0.) O.) (C++ 0.)
20
Cc+ól (0. (C, + 51) mi) prox a R.))())
where the proximal operator in (2) is defined as prox (z) argmin, (((()) + - = In PROXGEN, allow both the loss and the regularizer to be non-convex. Now, introduce possible examples according to the proper combinations of preconditioners C, and regularizers R(-).
Existing Instances of PROXGEN. We briefly recover some known examples in PROXGEN family.
) ADAGRAD [9] is the first key instance of adaptive gradient methods where C₁ (E==1199") and R(0)= = ||0|]- Any convex regularizer R.-)) allowed.
The proximal Newton methods [29] employ the exact Hessian C, = (2, and R(0) = |||| In addition, we can approximate the exact Hessian, which yield proximal Newton-type methods such as quasi-Newton approximation [30], L-BFGS approximation [31], and adding a multiple of the identity to the Hessian.
Although the above examples enjoy good theoretical properties in convex settings, many of the modern practical optimization problems involve non-convex loss functions such as learning deep models. Moreover, is known that non-convex regularizers yield better performance (also in terms of theory) than convex penalties in some applications (see [32, 33, 34, 35] and references therein). Considering this motivation and recent advanced optimizers, we arrive at the following new examples.
Novel Instances of PROXGEN. Beyond the well-known methods above, PROXGEN naturally introduces proximal versions of standard SGD techniques developed for solving unregularized problems for deep learning. The following examples are just few instances that have not been
3

---

explored so far, and PROXGEN can cover a broader range of new examples depending on the combinations of preconditioners and regularizers.
The proximal version of ADAM [19] with by regularization is possible example where C, = VBC (1 ")9; with 3 E (0,1) and R(0) = |10|| la for S S 1. We validate empirically the superiority of our novel proximal version of ADAM over the usual subgradient- based counterpart in Section 4.
We can also consider the proximal version of KFAC [36]. For an L-layer neural network, KFAC approximates the Fisher information matrix with layer-wise block diagonal structure where I- th diagonal block Cr corresponds to Kronecker-factoree approximation with respect to the parameters at I-th layer. The proximal version of KFAC corresponds to Cz.jg E[6,6,| & E|a--aa711 and R() ||0]1, where is the gradient with respect to the outputs of (-th layer and 0:-1 is the activation of 1)-th layer.
Examples of Proximal Mappings for PROXGEN. We provide update rules for PROXGEN with & regularization (0 < q S 1) and diagonal preconditioners, for which closed-form updates are available. Diagonal preconditioners are used by popular adaptive gradient methods such ADAM. Note, however, that our framework and convergence analysis are not limited to diagonal preconditioners and apply general positive preconditioners. Specifically, for 0 E IP with diagonal preconditioner matrix Ct. Note that for C, I (i.e. vanilla gradient descent), is known that closed-fore solutions exist for proximal mappings for E {0. 1 2: 3: 1) [37].
consider regularizer R()) À Σド= 0
We denote the i-th coordinate of the vector 0; as ot,; and the diagonal entry [Celis as Ct,;
ε regularization. The proximal mappings for the case of & regularization with preconditioner can be computed efficiently via soft-thresholding as
Ma,i
P1-1, sign (0..)) (1Bu.l
and Ct + 8
0 0e,s at Ci + 8'
(3)
l regularization. In of & regularization, can compute the closed-form solutions via hard-thresholding as
10,.1
20, Ce,ttō
V
0 00,; 04 Ct,i 8' Oc11,1
0,
10r,1
2ard
(4)
V
Ce,+o
{0, O.,),
10r.11
201
Ce,tto
The closed- form proximal mappings for f and 2233 regularization are provided in the Appendix.
Revised PROx QUANT [1]. The recently pro- posed PROXQUANT proposes novel regular- izations for network quantization. Especially for binary quantization, W-shaped regular- izer is defined as (f) = ||0 sign(f)]l [I) where sign(() )) is applied on an element- wise manner. Using this regularizer, the main difference between PROXQUANT and our PROXGEN approach is shown in Table 2.
Table 2: PROXQUANT versus revised PROXQUANT
PROXQUANT
prox proX (0. ar, 81) me
Revised PROXQUANT
prox Ci+61 (
(0. ou (C, 81)
Note that PROXQUANT (top in Table 2) does not consider the effect of preconditioners when comput- ing proximal mappings. Therefore, we revise the proximal update in preconditioners in proximal mappings with PROXGEN (bottom in Table 2). Moreover, we also propose generalized regularizers motivated by lg regularization for 0 < q < 1: R" (0) ||@ sign(O)) (f)]l In terms of theory, [1] prove the convergence of PROXQUANT only for the the full- gradient with differentiable regularizers, which is also guaranteed only for vanilla gradient descent. In contrast, using our revised PROXQUANT, we can completely bridge the gap in theory (via Theorem I in Section 3, which is stated for stochastic optimization). and we provide the exact update rule for solving the problem in (1). We also investigate the empirical differences of PROXQUANT and our revised PROXQUANT in Section 4.
by considering

---

3 Convergence Analysis
In this section, we provide convergence guarantees for the PROXGEN family, Our goal is find an e-stationary point for the problem in (1) where is the required precision. For notational convenience, we assume that the regularization parameter À incorporated into R(0) in (1). To guarantee the convergence under this setting, we should deal with the subdifferentials defined as:
Definition (Fréchet Subdifferential). Let be a real-valued function. The Fréchet subdifferential of p at 0 with (p(()] < oc is defined by
0 = 10- E E lim (00) pp()) -6" 0 8) 0-+0
0}.
10 01
Definition (Limiting Subdifferential), Let 0i((0) be the Fréchet subdifferential in Definition The limiting subdifferential of ip at 0 is defined by
0e((0)= {u Rº 30 S 0, ux E @.((0s), un + uu.
where 02 S 0 means 0₂ + with (00,) + c(())
To derive the convergence bound, we make the following mild conditions:
(C-1) (L-smoothness) The loss function ʃ is differentiable, L-smooth, and lower-bounded: Vx, y. [[) ff(y)) - L|| - yll and f(x") > -oo for the optimal solution x².
(C-2) (Bounded variance) The stochastic gradient gr = (.(( {) unbiased and has the bounded
variance: Eg {)] = ff.)).)
111 [f()) =²a
(C-3) (i) final step-vector finite, (ii) the stochastic gradient is bounded, and (iii) the momentum
parameter should be exponentially decaying: (i) ||0/+1 0.l - D, (ii) lIaell I G, (iii) Pe
popt-1 with D, G and po. μ E [0, 1).
(C-4) (Sufficiently positive-definite The minimum eigenvalue of effective spectrums should be uniformly lower bounded over all time t: VI,, Amin (a+(Ca 51)-1) 2 7 >
(C-1) and (C-2) are very standard in convergence analysis for optimization algorithms designed for deep learning such as ADAM, YOGI, and many others [21, 38, 39, 40, 41]. In addition, (C- 3) is extensively studied in previous literature for analysis of general non-convex optimization [19, 20, 42, 40, 41]. Lastly, similar condition to (C-4) is also considered in [39, 42]. We note that (C-3) and (C-4) are reasonable conditions: It is well-known that the parameter of an overparametrized neural network hardly changes from the initial point during training [43, 44, 45], so one can expect that the diameter D of parameter space and the bound for the size of gradient G have very small values and can be understood as constants in rates of the results. To validate this for real cases, we train ResNet-34 on CIFAR- 10 dataset. In Figure- I-(a), the difference of parameters ||0++1 Blll and the size of stochastic gradients l|9el12 attain just 1 3 while the parameter dimension d of ResNet-34 is about 10?. Hence, the constants D and G in (C-3) are negligible compared to the problem dimension d in practice. The exponentially decaying momentum parameter assumption P: Poy1"=1 could be relaxed to P. Po/t sacrificing the logarithmic factor in our analysis. Also, (C-4) indeed easily satisfied both theoretically and empirically. This condition holds in theory for most of the popular optimization algorithms for deep learning such ADAGRAD, ADAM, and KFAC (the constant y is irrelevant to the problem dimension d for each algorithm, and we defer the derivations to Appendix D). In order to investigate whether these conditions could be satisfied in real problems, we revisit the experiments of training ResNet-34. In Figure 1-(b), we can see the minimum eigenvalue of (C(C, + 5I) tends to increase, the condition (C-4) is also satisfied empirically.
Since the loss function f is assumed be differentiable in (C-1) and it is known that (vp()) C a0)( we have, at stationary points, E (F(0) = V (0) + OR(0), so the convergence criterion is slightly different from that of general non-convex optimization. Hence, we use the following convergence criterion Eldist(O. OF({))] < for c-stationary point where dist (r, A) denotes the distance between a vector & and a set A. no regularizer is considered (R = 0), this criterion boils down the one usually used in non-convex optimization, E[I ([IV((() (0)]] S..
Challenges specific to the analysis of PROXGEN. The most challenging issue in the analysis of PROXGEN compared to previous studies [14, 21] is that should handle the momentum m, and
5

---

Diameter Parameter Space
Gradient Norm
Condition (C-4)
Am--la,C (a,, +.50-))
10:+1 0:12
loll
2
10-22
1
6-10
10-
0
1
2
3
2.5 Iterationn,
5.0
Iterations,
x10*
Iterations,
x10*
(a) Bounded domain and bounded gradients
(b) Minimum eigenvalue
Figure 1: Empirical results for (a) condition (C-3) and (b) condition (C-4) using ResNet-34.
non-trivial preconditioner Ct. In terms of adaptive gradient methods, [21] guarantees the convergence of a family of adaptive methods (but without proximal mapping) using the changes of effective learning rate (I', = a4/ VV.- 01+1/ VV++ 2 where V, is an adaptation matrix), which is key quantity in their theory. [21] define
sequence {=t} involving the quantity T3 and exploit the simple closed-form of the quantity 2++1 2; to derive the convergence with coordinate wise analysis. However, this proof technique amenable anymore to compute in a simple closed-form due to the proximal mapping. On the other hand, proof directly solves the quadratic subproblem w.r.t. O, at line 8 in Algorithm 1 to handle a regularizer term. It should also be emphasized that our proof skill can handle arbitrary positive curvatures (hence including more general non-diagonal one) that were not acceptable in [21]. In the context of proximal gradient descent, our proof is totally different from [14] which is only for vanilla SGD. Due the existence of m, highly non non-trivial to bound the term || (f(,))ll
not available the regularized problems since 2141 2, is not
without suitable assumptions whereas l1. v (f(=))llz in [14] can be easily bounded using (C-2).
Also, we need to deal with quadratic approximation term (0 - 0,) T (C, + 60)(0- - 0z) in Algorithm 1
which is not problematic in [14] simply because C, is trivially I. We could successfully bypass those difficulties using mild conditions (C-3) and (C-4), respectively.
We are ready to state theorem for general convergence.
Theorem 1. Let Og denote an iterate uniformly randomly chosen from (01,...,00) Under the conditions (C-1), (C-2), (C-3), (C-4) with the initial stepsize Org S 3L and non-increasing stepsize og PROXGEN, Algorithm I, is guaranteed yield
Q10² T
Q2 T
Q3 T
Eg (0
t=
where A f()- ff with optimal point 6", and by is the minibatch size at time t. The constants {Q.)3_ 3 on the right-hand hand side depend on the constants {ag, 8, D.D.G. G. Po. μ. 7) but not on T.
Note that the constants {Q1)2 in Theorem are completely independent of the problem dimension d. From Theorem 1, the appropriate minibatch size is important ensure good convergence. Various settings for the minibatch size could be employed for convergence guarantee, but considering practical cases, we provide the following important corollary for constant minihatch.
Under the same assumptions in Theorem I with sample size and constant minibatch size b, b (T)), we have E,, [dist(O, (F.))) < (1/TT) and the total complexity is (1)AA) in order to have E.,, [dist (0, OF (0.))) <.
Corollary (Constant
Here we make several remarks on our results and relationship with prior work.
On Convergence Results. Note that our Corollary achieves the optimal complexity O(1/ct) of SGD to find c-stationary points under the standard assumptions (C-1) ~ (C-4). Recent studies [46, 47] show faster rate, but under additional stronger assumptions such as second-order smoothness (i.e., the smoothness of Hessian matrix). Also, we could relax the exponentially decaying momentum Pope-1 in (C-3) to P. = po/t /t as mentioned in [48] with the logarithm factor as Q3 = O(log T"), which in result still ensures (1/e4).

---

Leaming
Leaming
100
Proxoen 10urs)
Prxx 560 OCLS 20201
Sub-Acam
Tect Pecurcccccyy (N))
10"
Frodtct (00/s) Sub:Adam
Test Accurascy
R5.5
F18t -8)
95,0
95.0
10-4
94.5
10-1
94.5
75
150 Epochs
225
300
75
80
65
90
95
75
150
225
300
80
90
95
Pruned Ratio 1751
Epochs
Pruncd Ratio 135
(a) & regularization
(b) 22/3 regularization
Leaminng Curve for 34
Performance for ResNet:
Restiett 344 CBAR-10
Preeden (Ounc)
F10) -10 2000
Sub-Atam
95.5
94
Te4t Accunacy
95.0
Accuracy
94.5
90
94.0
75
150
Z25
300
80
85
90
100
Epochs
Pruned
(c) f122 regularization
(d) Eu regularization
Figure 2: Comparison for sparse ResNet-34 on CIFAR-10 dataset with step-decay stepsize scheduling.
Advantages of using adaptive gradient methods in Theorem 1. We discuss how the constant in (C-4) affects the convergence in terms of theory. According to our proof'. depends on the algorithmic details and the constants Q1, Q2 and Q3 Theorem are proportional convergence rate depends on these constants and the benefit of preconditioners can be found here. To view this more clearly, we consider the diagonal matrix adaptation of ADAM [19], i.. constant
1/7. The
stepsize a = a and C = / (1 3) Ei= Br- Or @ 9r. with 3 E [0, 1) and the total iteration T. In this setting, the 1/7 can be computed as
8 11 1 - (1- Qi x 7
+
G +
where 9r is the gradient at time 7 and 8 is a small constant while the vanilla SGD (C, 0 and 5 = 1) satisfies 1/r = 1/a. Here, we can clearly see the advantages of udaptive methods (i.c., using preconditioners) since 1/7 could be dramatically smaller if [19-||2 < holds roughly with small constant 6, which corresponds to sparse gradients ||ø-||2 (the data features are sparse). This coincides with the convex regret theory for adaptive gradient methods [9, 19, 48], which also holds our theory with non-convex smooth loss and non-convex regularizers.
Implications of condition (C-4) on theory. Our analysis relies on (C-4), the lower bound for the minimum eigenvalue of I' = (C, + 51)-1. This means that Theorem guarantees E, [dist(O. 0, (0.))) < O(L/VT) (in case of b O(T)) in Corollary 1) for any change of basis of Tr, so in that sense, we provide a worst-case analysis and there is room for more optimistic bounds.
On minibatch in Corollary 1. The conditions b = (T) is considered as standard in many previous literature [38, 14] and is not stringent. terms of stochastic optimization, it is natural in practice to choose the batch size b and the number of epochs in advance. Then, the total number of iterations T' satisfies the following relation: T e x oh = X क(τ). In this sense, the total iterations
T should be an order of (VvT) in practice. For example, this condition sets minibatch size of approximately 200 and 1000 for CIFAR-10 and ImageNet dataset respectively, which is practical.
Connections to second-order methods. Our analysis can provide guarantees for positive second- order preconditioners as long as (C-4) satisfied (The empirical Fisher information [36] one example). Although second-order solvers generally enjoy very fast convergence under strongly convex loss [29, 49], can be understood that our theory guarantees least a sublinear rate for such second-order curvatures with less stringent conditions.
7

---

Table 3: Comparison for binary neural networks. The best performance in value is highlighted.
Test Error (%)
Baselines
PROXGEN (Ours)
Full Precision (32-bit)
Revised Prox Quant &
Revised ProxQuant E2/a
Revised Prox ProxQuant
BinaryConnect [8]
PROXQUANT [1]
Model
f1/2
Re
8.06
9.54 + 0.03
9.35 + 0.13
9.50
0.12
9.72 + 0.06
9.78 + 0.18
ResNet-32
7.25
8.61 + 0.27
8.53 + 0.15
8.29 + 0.07
8.22 + 0.05
8,43 + 0.15
ResNet-44
6.96
8.23 + 0.23
7.95 + 0.05
7.68 + 0.07
7.91
+ 0.08
7.90
+ 0.13
ResNet-56
6.54
7.97 + 0.22
7.70 + 0.06
7.52 0.18
7.60
0 0.09
7.61 + 0.12
4
Experiments
We consider two important tasks for regularized training in deep learning communities: (1) training sparse neural networks and (ii) network quantization. Throughout our experiments, we consider ADAM as representative of PROXGEN where m, = - + (1 - pe)g.. with constant decaying parameter P 0.9 and C. = /3 (1 -3gq with ,3 0.999 in Algorithm 1. The details on other hyperparaaetter/expprimeen settings are provided in the Appendix.
Training Sparse Neural Networks. Motivated by the lottery ticket hypothesis [50], we consider training VGG-16 16 [51] and ResNet-34 [52] on CIFAR-I0 dataset using sparsity encouraging regu- larizers. Toward this, we consider the following objective function with possibly non-convex & regularization: F(0)= == (0; + X E 10,19 where S q S 1. We train the network parameters with the closed-form proximal mappings introduced in Section The results on VGG-16
are provided in Appendix.
We compare PROXGEN with subgradient methods and also include PROX-SGD [16] as a baseline especially for & regularization since PROX-SGD considers only convex regularizers. In PROX-SGD, the hand-crafted fine-tuned scheduling on a and Pt is essential for fast convergence and good performance, but in our experiments we use standard settings Pt = 0.9. We first validate our theory in practice using constant stepsize in order to purely see the effect of proximal approaches (the results on this setting are provided in the Appendix). Then the step-decay learning rate scheduling is employed to consider standard training schemes for the state-of-the-arr performance, which also satisfies the non-increasing stepsize condition in our Theorem 1. For fo regularization, the problem in (1) cannot be optimized in a subgradient manner, so we compare PROXGEN with another popular baseline, tow. [6] which approximates the fo-morm via hard-concrete distributions.
Figures 2 illustrates the results for ResNet-34. In terms of convergence, PROXGEN shows faster convergence than PROX-SGD for & case in Figure 2-(a), but there is no difference between PROXGEN and subgradient methods as in Figure 2-))). However, there are notable differences in convergence decreases. We believe this might be
for non-convex regularizers f1/ and f2/3. which get bigger
because the fy-norm derivative, //|0|1-9 is very large for non-zero tiny 0 for g E (0. 1). Meanwhile, a|0|/00 is merely the sign value regardless of size of so the large gradient of [@] may hinder convergence. The learning curves in Figure 2-(b,c) empirically corroborate this phenomenon.
In terms of performance, can see that PROXGEN consistently achieves better performance than baselines for ResNet-34 with similar or even better sparsity level. Importantly, PROXGEN with t, outperforms lo.. baseline by great margin. This might be due the design of lo... which approximates ||0||o = Σ I10, * 0} with binary mask 2j parameterized by learnable probability Ty for each coordinate. Thus, the number of parameters to be optimized is doubled, which might make optimization harder. In constrast, PROXGEN does not introduce additional parameters.
More results for other famous non-convex regularizers MCP [53] and SCAD [54] are in Appendix.
Training Group-Sparse Neural Networks. In the Appendix, we consider training Statistical Recurrent Units where f group-norm penalty imposed on the input layer weights to detect non-linear Granger Causality [55]. As the proximal mappings for PROXGEN with group sparsity are not available in closed-form, we develop an efficient procedure for computation, whose derivations are also provided in the Appendix.
8

---

True Parameter
ProxGen (Ours)
ProX-SGD (ICLR 2020)
2
Signals
Signals
Signals
-2
-2
0
500
0
500
500
Features
Features
Features
(a) Random initialization
True Parameter
ProxGen (Ours)
SGD (ICLR 2020)
2
Signals
Signals
Signals
-2
-2
-2
0
500
0
500
0
500
Features
Features
Features
(b) Zero initialization
Figure 3: Lasso simulations with different initialization schemes.
Training Binary Neural Networks. We consider the network quantization constraining the pa- rameters to some set discrete values which is key approach for model compression. We evaluate our revised PROXQUANT in Table 2 with extended regularization R% in Section 2. We consider the following objective function with quantization-specife regularizers: F(A) = [g-r[f((: Ez 10 sign(0,))* where weight parameters (except bias and activations) CIFAR-10 and ImageNet dataset.
S 1. For comparisons, we quantize ResNet
Table 3 presents the results. For all q values, revised PROXQUANT consistently outperforms the baselines except for ResNet-20, which implies PROXGEN may work better for larger networks. As such, our gen- eralized regularizers R.y... contribute one of the state-of-the-an optimization-baaee methods in net- work quantization. Notably, revised PROXQUANT l greatly outperforms P PROXQUE QUANT baseline while these two approaches differ only in update rules (see Table 2). Hence, we can conclude that revised PROX- QUANT based on PROXGEN provides an exact prox- imal update and also yields lutions. our experience, revised PROX QUANT Eo shows little degradation in performance, so do not include this result. However, revised PROXQUANT to shows superiority baselines for language modeling, whose preliminary results are in Appendix.
Table 4: Comparison for binary neural net- works for ImageNet. means the first and last layer not quantized.
ResNet-18
Top-1 Error (%)
Top-5 Error (%)
Full precision
30.46
10.81
BWN [56]
39.20
17.00
LR-Net [S7]
40.10
17.70
generalizable so-
ELQ [58]
35.28
13.96
PROXQUANT [1]
36.24
14.23
Revised
34.85
12.38
PROXQUANT & (Ours)
Table 4 illustrates T/p-1/Top-5 error (%) for training ResNet on ImageNet with binary quantization. The most important thing is that our revised PROXQUANT shows great improvements performance over the original PROXQUANT. Furthermore, PROXGEN shows superior performance various baselines for weight quantization.
A Closer Look into Prox-SGD [16] vs. PROXGEN
Prox-SGD [16] the approach closest to our PROXGEN method. However, PROX-SGD is not an exact proximal approach and is significantly different from PROXGEN. PROXGEN's update rule

---

involves directly solving the quadratic subproblem (2). In contrast, PROX-SGD's 's update rule consists of two stages: (i) solving the quadratic subproblem without learning rate (5), then (ii) updating the parameters with the computed direction (i.e. 8₂ - 8τ) by the learning rate 0₁ (6).
C.+81 0. prox XR()) (or (C,+ (1)+
(5)
no learning rate
O2+1 = O2 + or (0, 0c)
(6)
To clearly see the differences between both approaches, we conduct two studies.
Lasso Support Recovery. For this task, the two-stage update scheme of PROX-SGD might have some potential issues. For example, for f1-regularized problems, the updated parameter 0141 (6) might not achieve exact zero (while 0, can) whereas 0.+-1 for PROXGEN (2) can attain exact zero value according to the update rule (3) in Section 2. Another potential caveat is that PROX-SGD might overestimale the sparsity level. In view of the above, we run Lasso simulations with different two initialization schemes; (i) random initialization and (ii) zero initialization. For random initialization, can be seen Figure 3-(a) that PROX-SGD could not achieve exact zero value, which corroborates our first observation. More interestingly, for zero initialization. we can see Figure 3-(b) that the estimates using PROX-SGD are exactly zeros for all coordinates, which supports our second observation. This might be because 0, (5) is always zero since the quadratic subproblem does not consider the learning rate, which might overestimate the sparsity level. Hence, the subsequent iterate 8(+1 would be always zero since we initialize the parameters with zeros, but PROXGEN recovers the correct support in both cases.
Study I:
Study DenseNet-201 on CIFAR-100 Dataset. To validate the supe- riority of PROXGEN upon PROX-SGD, we revisit the largest experiments in [16]. We train 201 architecture on CIFAR-I00 dataset with l regularization since PROX-SGD only consider convex regularizers. For both methods, we use the same hyperparameter settings for fair com- parison. Figure 4 illustrates the training learning curves, and it can be seen that our PROxGEN achieves faster convergence as well as lower objective values. For our experience, the learning curves show the similar dynamics for different À values.
DenseMett2201 en CIFAR-100
1lat (017- 2
ProxGon (Ours)
Prox 560 IICLR 2020)
100
200
300
Epochs
Comparison of Theoretical Contributions. [16] guarantees the con- vergence of PROX-SGD, but not how fast converges. Moreover, this is proved without considering preconditioners. In contrast, our analysis for the PROXGEN framework appropriately incorporates the first-order momentum and arbitrary positive preconditioner with detailed non-asymplotic convergence.
Figure Learning curve.
6 Conclusion
In this work, we proposed PROXGEN, the first general family of stochastic proximal gradient methods. Within our framework, we presented novel examples of proximal versions of standard SGD approaches, including a proximal version of ADAM. We analyzed the convergence of the whole PROXGEN family and showed that PROXGEN can encompass the results several previous studies. We also demonstrated that PROXGEN empirically outperforms subgradient-based methods for popular deep learning problems. As future work, we plan further study efficient procedures to compute the proximal mappings for structured regularizers such as L E1/yy-nomms nooms with preconditioners.
Acknowledgement
This work was supported by the National Research Foundation of Korea (NRF) grants (2018RIAS ASA 2019RIC1C1009192) and Institute Information & Communications Tech- nology Planning& & Evaluation (ITTP) grants (No.2019-0-0133 Development of brain-inspired AI with human-like intelligence, No.2019-0-00075, Artificial Intelligence Graduate School Program (KAIST)) funded by the Korca government (MSIT).
10

---

References
[1] Yu Bai, Yu-Xiang Wang, and Edo Liberty. Proxquant: Quantized neural networks via proximal operators. In International Conference Learning Representations, 2019.
[2] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58(1):267-2888 1996.
[3] Ravikumar, M. Wainwright, Raskutti, and B. Yu. High-dimensional covariance estima- tion by minimizing & fi-penalized log-determinant divergence. Electronic Journal of Statistics, 3:935-980 2011.
[4] A. N. Tychonoff. On the stability of inverse problems. Doklady Akademii Nauk SSSR, 39(5):195- 198, 1943.
[5] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Advances in neural information processing systems, pages 2074-2082, 2016.
[6] Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through lo regularization. In International Conference on Learning Representations, 2018.
[7] Jiwei Yang, Xu Shen, Jun Xing, Xinmei Tian, Houqiang Li, Bing Deng, Jianqiang Huang, and Xian-sheng Hua. Quantization networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7308-7316, 2019.
[8] Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David, Binaryconnect: Training deep neural networks with binary weights during propagations. In Advances in neural information processing systems, pages 3123-3131, 2015.
[9] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Journal of Machine Learning Research (JMLR), 2011.
[10] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming. 155(1- 2):267-305, 2016.
[11] Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost: A class of faster variance-reduces algorithms for nonconvex optimization. arXiv preprint 2018.
[12] Nhan H Pham, Lam M Nguyen, Dzung Phan, and Quoc Tran-Dinh. Proxsarah: effi- cient algorithmic framework for stochastic composite nonconvex optimization. arXiv preprint arXiv:1902.05679, 2019.
[13] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1) (921)2277239, 2019.
[14] Yi Xu, Rong Jin, and Tianbao Yang. Non-asymptotic analysis of stochastic methods for non- smooth non-convex regularized problems. In Advances in Neural Information Processing Systems, pages 2626-2636, 2019.
[15] Yi Xu, Qi Qi. Qihang Lin, Rong Jin, and Tianbao Yang. Stochastic optimization for DC functions and non-smooth non-convex regularizers with non-asymptotic convergence. In International conference on machine learning, 2019.
[16] Yang Yang. Yaxiong Yuan, Avraam Chatzimichailidis, Ruud JG van Sloun, Lei Lei, and Symeon Chatzinotas. Proxsgd: Training structured neural networks under regularization and constraints. In International Conference on Learning Representations, 2020.
[17] Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, 20(1): 191 154, 2020.
19
11

---

[18] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26- 31, 2012.
[19] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- lional Conference on Learning Representation (ICLR), 2015.
[20] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
[21] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam- type algorithms for non-convex optimization. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
[22] Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE Transactions on Neural Networks and Learning Systems, 2019.
[23] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. In 12th [USENIX] Symposium on Operating Systems Design and Implementation ((OSDI) 16), pages 283,283, 2016.
[24] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style,
deep learning library. In Advances in Neural Information Processing Systems, pages 8024-8035, 2019.
[25] Sashank J Reddi, Suvrit Sra, Bamabas Poczos, and Alexander Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. In Advances in Neural Information Processing Systems, pages 1 145-1113, 2016.
[26] Zeyuan Allen-Zhu. Natasha: Faster non-convex stochastic optimization via strongly non-convex parameter. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 89-97. JMLR. org, 2017.
[27] Tianyi Chen, Tianyu Ding, Bo Ji, Guanyi Wang, Yixin Shi, Sheng Yi, Xiao Tu, and Zhihui Zhu. Orthant based proximal stochastic gradient method for (.1-regularized optimization. arXiv preprint arXiv:2004.03639, 2020.
[28) Emilie Chouzenoux, Jean- Christophe Pesquet, and Audrey Repetti. Variable metric forward- backward algorithm for minimizing the sum of a differentiable function and a convex function. Journal of Optimization Theory and Applications, 162(1):107-133) 2014.
[29] Jason D Lee, Yuekai Sun, and Michael Saunders. Proximal newton-type methods for convex optimization. In Advances in Neural Information Processing Systems, pages 827-835, 2012.
[30] Stephen Becker, Jalal Fadili, and Peter Ochs. On quasi-newton forward-backward splitting: Proximal calculus and convergence. SIAM Journal on Optimization, 29(4):2445-2481, 2019.
[31] Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 45(1-3):503-528, 1989.
[32] Wenjiang J Fu. Penalized regressions: the bridge versus the lasso. Journal of computational and graphical statistics, 7(3):977-416, 1998.
[33] Cheolwoo Park and Young Joo Yoon. Bridge regression: adaptivity and group selection. Journal of Statistical Planning and Inference, 141(11) 3519, 2011.
[34] Eunho Yang and Aurélie C Lozano. Sparse+ group-sparse dirty models: Statistical guarantees without unreasonable conditions and a case for non-convexity. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 3911-3920. JMLR. org,
2017.
12

---

[35] Jihun Yun, Peng Zheng, Eunho Yang, Aurelie Lozano, and Aleksandr Aravkin. Trimming the L regularizer: Statistical analysis, optimization, and applications deep learning. In International Conference Machine Learning, pages 7242-7251, 2019.
[36] James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored ap- proximate curvature. International conference on machine learning, pages 2408-2417, 2015.
[37] Wenfei Cao, Jian Sun, and Zongben Xu. Fast image deconvolution using closed-form thresh- olding formulas of lq (q= 12, 23) regularization. Journal of visual communication and image representation. 24(1):31-44 2013.
[38] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in neural information processing systems, pages 9793-9803, 2018.
[39] Jihun Yun, Aurelie C. Lozano, and Eunho Yang. Stochastic gradient methods with block diagonal matrix adaptation. arXiv preprint
2019.
[40] Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianbao Yang. Universal stagewise learning for non-convex problems with convergence on averaged solutions. In International Conference on Learning Representations, 2019.
[41] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conference on Machine Learning, pages 6677-6686. PMLR, 2019.
[42] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019.
[43] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[44] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019.
[45] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
[46] Zeyuan Allen-Zhu. Natasha 2:
Faster non-convex optimization than sgd. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[47] Zeyuan Allen- Zhu and Yuanzhi Li. Neon2:
Finding local minima via first-order oracles. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[48] Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprini /0040009000093377 2019.
[49] Guodong Zhang, James Martens, and Roger B Grosse. Fast convergence of natural gradient descent for over-parameterizeed neural networks. In Advances in Neural Information Processing Systems, pages 8080-8099 2019.
[50] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: neural networks. In International Conference on Learning Representations, 2019.
Finding sparse, trainable
[51] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 100.v:1409.1556, 2014.
13

---

[52] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[53] Cun-Hui Zhang et al. Nearly unbiased variable selection under minimax concave penalty. The Annals of statistics, 38(2):894 942, 2010.
[54] Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 134456))3348--0 1360, 2001.
[55] Saurabh Khanna and Vincent F. Tan. Economy statistical recurrent units for inferring nonlinear granger causality. In International Conference on Learning Representations, 2020.
[56] Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. European conference on computer vision, pages 325-542. Springer, 2016.
[57] Oran Shayer, Dan Levi, and Ethan Fetaya. Learning discrete weights using the local reparame- terization trick. International Conference on Learning Representations, 2018.
[58] Aojun Zhou, Anbang Yao, Kuan Wang. and Yurong Chen. Explicit loss eess-error-wware quantization for low-bit deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 9426-9435, 2018
14


Reviews:
[{"review_id": "yhvpWMdudO4", "reviewer": "Reviewer_3MNN", "summary": "This paper proposes adaptive proximal gradient methods for nonconvex optimization where the regularizer can be nonsmooth and nonconvex. The paper also provides extensive experiments to show that the proposed approach outperform existing SGD methods for stochastic optimization.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "I feel that the theoretical contribution as well as the novelty of this paper is quite limited, and this paper did not broaden our understanding of adaptive methods for sparse optimization. The main weakness of this paper is that the convergence analysis is not technically sound. A potential limitation is that the stepsize of the proposed algorithm  virtually has nothing to do with the adaptive metric. In fact, by using some nonstandard assumption C3, C4, the convergence analysis is nearly identical to the standard analysis of stochastic PGD. \n\nFurthermore, I feel that some of the theoretical results are incorrect or at least have obvious limitations. \n- The stepsize is the main tuning parameter for ProxGen.  A close look at the convergence analysis reveals that the tuning parameter has nothing to do with the adaptive metric at all. It is somewhat strange that the stepsize solely depends on the free parameter $\\delta$ which is only a small to term to ensure the posititive definiteness of the metric. So how should the algorithm choose $\\delta$?\n- Line 236 the paper claims the advantage of ProxGen. However, this bound on $1/\\gamma$ is different from the bound derived in appendix line 733. Is there a typo? It is also bothering that  $1/\\gamma$ depends on $1/\\delta$, which can be arbitrarily small, this goes back to the previous question on how to select $ delta$.\n- This paper considers $\\ell_0$ penalty as a motivated example. However, it seems inappropriate for the theory. Specifically, Definition 1 (Frechet subdifferential) is not well-defined for the proposed $\\ell_0$ regularizer. Taking $R(\\theta)=\\||\\theta\\||_0$ in the 1-d case, if $\\theta=0$, then  $\\partial R(0)=\\[\\theta^*, |\\liminf  \\frac{1-\\langle \\theta^*, x-0\\rangle}{|x|} \\ge 0\\]=\\mathbb{R}$. Therefore, the subdifferential of the objective always contains zero. \n- The author proposes C3 in which the difference between iterates is bounded by $D$. This appears to be unnecessary. In the proof (line 763) one can subtract $(L+\\rho_0G)\\||\\theta_{t+1}-\\theta_{t}\\||^2$ on both sides. Then using quadratic bound, one can easily remove the term $\\||\\theta_{t+1}-\\theta_{t}\\||$. It suffices to impose a slightly tighter bound on $\\alpha_0$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The choice of stepsize is unclear.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "pjWawbWtSy-", "reviewer": "Reviewer_PpkK", "summary": "This paper gives a proximal gradient method for optimizing nonsmooth and possibly nonconvex regularizers. It could be applied to impose structure on neural networks such as binary quantization.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The papers reasonably propose proximal methods to handle these regularizers. As proximal mapping is more progressive than subgradient descent, so it should be straightforward.\n\nOne of my questions is about the technical difficulty in developing the theory of proof, as to determine whether it qualifies to be in Neurips. The paper is more of an experimental study overall.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some additional questions: Figure 2 shows the constant factors in the assumptions C1-C4, is it possible to compare with the convergence, i.e. |\\nabla F| side by side to show whether the convergence theory is tight?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "aHPXak0-sn2", "reviewer": "Reviewer_REN2", "summary": "The paper presents a framework for adaptive proximal stochastic methods. The general algorithm provided, ProxGen, is a variation on traditional proximal gradient descent in which the gradient is multiplied by the inverse of some $C_t+ \\delta I$, and the norm in the prox operator is given by $\\|x\\| = x^{\\top} (C_t+ \\delta I) x$. They give a convergence result which matches the optimal rate for SGD, and they show experiments with sparse, group-sparse, and binary neural networks in which they show improvements over existing algorithms.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The algorithm presented is not that novel in itself, as it is very close to Prox-Quant (differing only in the norm used for the prox-operator), and to Prox-SGD (differing on the fact that Prox-SGD is a two step algorithm, so it seems that ProxGen is a “simplification” of Prox-SGD). Despite that, the authors generally do a good job in arguing the empirical and theoretical advantages of the proposed method w.r.t. the existing two. \n\nQuestion: In lines 93-94, there is the statement that Adagrad is an instance of ProxGen with a certain choice of $C_t$ and $\\mathcal{R}(\\theta) = \\|\\theta\\|_1$. Is that accurate? To my understanding, “vanilla” Adagrad does not include any proximal step. Should it say “proximal” Adagrad instead?\n\nAs to the proof of Theorem 1, is the proof structure based on any previous work, or is it completely new? I think it would be useful to give some pointers. \nAlthough the steps to get Corollary 1 from Theorem 1 are not too involved, they are not a one-liner, and should be included either in the main text or the appendix. Also, add citation for the $O(1/\\epsilon^4)$ optimal rate: this is relevant.\n\nRegarding the experiments, the plots in Figure 2 should be uniformed: Why is Prox-SGD only in some plots (it does not look good)? Some plots have legends, some do not, and the legend for the last one is cryptic. \n\nTypos: The paper needs to be proofread for typos. Line 64: “arbitrat”. Line 72: “approacwstygh”.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed. There is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "K6O06TLX6Vd", "reviewer": "Reviewer_Uvqk", "summary": "This work introduces a proximal algorithm for training neural networks. Specifically, the method allows the use of non-convex regularization functions and general PSD pre-conditioners  in the objective, while guaranteeing convergence to a stationary point. Empirical results are provided for training sparse neural networks on CIFAR and ImageNet.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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\nThis is a well-motivated and well-executed work that demonstrates the effectiveness of its proposed proximal algorithm when employing  non-convex regularizers to train sparse or quantized neural networks.\n\n### Strengths\n1. This work is well-motivated, and provides an interesting method especially in the context of training sparse or quantized neural networks.\n2. The convergence analysis provided in Theorem 1 seems to provide powerful results. The proof looks correct to me, although I have not checked all details.\n3. The assumptions made for the theoretical results are diligently checked in practice through dedicated experiments.\n4. The submission conducts convincing experiments that demonstrate the usefulness of the approach, including on the large-scale task of training a binary ResNet-18 on ImageNet.\n\n### (Minor) Weaknesses\n1. The paper is not easy to read and follow, perhaps due to its high density throughout.\n2. Experiments are \"only\" conducted for training quantized / sparse neural networks, which are interesting topics by themselves, but perhaps special cases only compared to what the reader might expect from the generality of the method suggested by the title and abstract. \n\n### Comments\n1. In the proof of Theorem 1, L.777 should be an inequality rather than an equality (distance from set to 0 is $\\leq$ norm of one element of the set).\n2. Can the authors detail why the method converges with constant mini-batch size? It is not obvious how the the first term of the RHS (from Theorem 1) converges to zero when the batch-size is constant?\n\n### Typos\n1. L.44 Strategic -> strategy\n2. l.64: arbitrat -> arbitrary\n3. l.72 approachstygh\n4. in caption of Table 4, “first” misspelled\n\n----\n\n### Updated Review\n\nThanks for the authors for engaging in a detailed discussion. It is slightly disappointing that Corollary 1 ends up requiring the assumption $b = \\Theta(T)$ since it is less elegant than the initial assumption $b = \\Theta(\\sqrt{n})$, but that is not a major issue.\n\nI am keeping my initial rating of 7. Whether the submission gets accepted or is resubmitted to other venues, I would encourage the authors to take the time and effort to improve clarity of the submission (potentially making space for expanding on the most important points by deferring lower level-details to the appendix).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No need for societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviews were initially highly polarized: while Uvqk and REN2 give a positive score and qualify this as "well-executed" and "authors generally do a good job in arguing the empirical and theoretical advantages of the proposed method", reviewer 3MNN argues that "the convergence analysis is not technically sound". The authors provided a strong rebuttal that increased the score of reviewer 3MNN. 

After the discussion period, the reviewers agree that this is a contribution that can be of high interest to the NeurIPS community, and as such my recommendation is to accept for publication. However, reviewer 3MNN raises some valid points regarding comparison of constants with existing results and regarding clarity of the statements that I encourage the authors to incorporate into the final version.
Decision: Accept (Poster)