Demystifying and Generalizing BinaryConnect
Authors: Tim Dockhorn
Yaoliang Yu
Eyyub Sari
Mahdi Zolnouri
Vahid Partovi Nia
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural network quantization
binary connect
generalized conditional gradient
proximal connect

Abstract: BinaryConnect (BC) and its many variations have become the de facto standard for neural network quantization. However, our understanding of the inner workings of BC is still quite limited. We attempt to close this gap in four different aspects: (a) we show that existing quantization algorithms, including post-training quantization, are surprisingly similar to each other; (b) we argue for proximal maps as a natural family of quantizers that is both easy to design and analyze; (c) we refine the observation that BC is a special case of dual averaging, which itself is a special case of the generalized conditional gradient algorithm; (d) consequently, we propose ProxConnect (PC) as a generalization of BC and we prove its convergence properties by exploiting the established connections. We conduct experiments on CIFAR-10 and ImageNet, and verify that PC achieves competitive performance.

Demystifying and Generalizing BinaryConnect
Tim Dockhorn University Waterloo
Yaoliang Yu University of Waterloo
Eyyüb Sari Huawei Noah's Ark Lab
Mahdi Zolnouri
Vahid Partovi Nia Huawei Noah's Ark Lab
Huawei Noah's s Ark Lab
Abstract
BinaryConnect (BC) and its many variations have become the facto standard for neural network quantization. However, our understanding of the inner workings BC is still quite limited. We attempt to close this gap four different aspects: (a) show that existing quantization algorithms,, including post-training quan- tization, are surprisingly similar to each other; (b) we argue for proximal maps natural family of quantizers that is both easy to design and analyze; (c) we refine the observation that BC a special case of dual averaging, which itself a special case of the generalized conditional gradient algorithm: (d) consequently, we propose ProxConnect (PC) as a generalization properties by exploiting the established connections. We conduct experiments CIFAR-10 and ImageNet, and verify that PC achieves competitive performance.
BC and we prove its convergence
Introduction
Scaling up extremely large datasets and models has been main ingredient for the success of deep learning. Indeed, with the availability of big data, more computing power, convenient software, and bag of training tricks well algorithmic innovations. the size of models that we routinely train in order to achieve state-of-the-art performance has exploded, e.g., to billions of parameters in recent language models [9]. However, high memory usage and computational cost at inference time has made it difficult to deploy these models in real-time or on resource-limine limited devices [28]. The environmental impact of training and deploying these large models has also been recognized [40]. A common approach to tackle these problems is to compress large model through quantization, i.., replacing high-pree precision parameters with lower-precision ones. For example, we may constrain subset of the weights to be binary [1. 5, 11, 29. 33, 37, 45] ternary [26, 53]. Quantization can drastically decrease the carbon footprint of training and inference of neural networks, however, may come at the cost of increased bias [21].
One of the main methods to obtain quantized neural networks is to encourage quantized parameters during gradient training using explicit or implicit regularization techniques, however, other methods are possible [16-18, 20, 25, 32, 51]. Besides the memory benefits, the structure of the quantization can speed up inference using, for example, faster inference can be made even more efficient by also quantizing the activations [37] or gradients
products [18, 23]. Training and
[52]. Impressive performance has been achieved with quantized networks, for example, on object detection [44] and natural language processing [43] tasks. The theoretical underpinnings of quantized neural networks, such as when and why their performance remains reasonably well, have been actively studied [3, 13, 22, 41, 46].
'Work done during an internship at Huawei Noah's tim. www.dockhorn@wwwtrrroooooo
Ark
Lab.
Correspondence to
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

BinaryConnec [BC, 11] and its many variations [10, 37, 53] are considered the gold standard for neural network quantization. Compared to plain (stochastic) gradient descent, BC does not evaluate the gradient at the current iterate but rather at (close-by) quantization point using the Straight Through Estimator [6]. Despite its empirical success, BC has largely remained a "training trick" [1] and rigorous understanding of its inner workings has yet to be found, with some preliminary steps taken in Li et al. [27] for the convex setting and in Yin et al. [45] for a particular quantization set. As pointed out in Bai et al. [5]. BC only evaluates gradients at the finite set of quantization points, and therefore does not exploit the rich information carried in the continuous weights network. Bai et al. [5] also observed that BC is formally equivalent to the dual averaging algorithm [31, 42], while some similarity to the mirror descent algorithm was found in Ajanthan et al. [1].
The main goal of this work is to significantly improve our understanding of BC, by connecting it with well-established theory and algorithms. In doing so we not only simplify and improve existing results but also obtain novel generalizations. We summarize our main contributions in more details:
In Section 2, we show that existing gradient-based quantization algorithms are surprisingly similar each other: the only high-level difference is at what points we evaluate the gradient and perform the update.
In Section 3, we present principled theory for constructing proximal quantizers. Our results unify previous efforts, remove tedious calculations, and bring theoretical convenience. We illustrate our theory by effortlessly designing new quantizer that can be computed in one-pass, works for different quantization sets (binary or multi-bit), and includes previous attempts as special cases [5, 11, 45, 53].
In Section 4, we significantly extend the observation of Bai al. [5] that the updates of BC are the same as the dual averaging algorithm [31, 42]: BC is nonconvex counterpart of dual averaging, and more importantly, dual averaging itself is simply the generalized conditional gradient algorithm applied to smoothened dual problem. The latter fact, even in the convex case, does not appear to be widely recognized to the best of our knowledge.
In Section 5, making use of the above established results, we propose ProxConnect (PC) as a family of algorithms that generalizes BC and we prove its convergence properties for both the convex and the nonconvex setting. We rigorously justify the diverging parameter in proximal quantizers and resolve a discrepancy between theory and practice in the literature [1, 45).
Section 6, we verify that PC outperforms BC and ProxQuant [5] on CIFAR-10 10 for both fine- tuning pretrained models well as end-to-end training. On the more challenging ImageNet dataset, PC yields competitive performance despite of minimal hyperparameter tuning.
2 Background
We consider the usual (expected) objective f(w) Ef(w, .), where & represents random sampling. For instance, E(w) = 1 thereof), w are the weights of a neural network and 6, may be the cross-entropy loss (of the i-th training sample). We denote sample (sub)gradient of & at and & as V((w) Vl(w, E) so that EV((w) = Vl(w). Throughout, we use the starred notation w for continuous weights and reserve w for (semi )discreee ones.
n Σm= ((()) where & is uniform over n training samples (or minibatches
We are interested in solving the following (nonconvex) problem:
min ((w),
WEQ
where Q C _d is a discrete, nonconvex quantization set. For instance, certain low-resource devices it may be useful or even mandatory to employ binary weights, i.c., Q = (+1]d Importantly, our goal to compete against the non-quantized, continuous weights network (i.e. Q = Rd). In other words, we do not necessarily aim to solve (the hard, combinatorial) problem (1) globally and optimally. Instead, we want to find discrete weights w E Q that remain satisfactory when compared to the non-quantized continuous weights. This is how we circumvent the difficulty in (1) and more importantly how the structure of could come into aid. If is reasonably smooth, close-by quantized weight of a locally, or even globally, optimal continuous weight will likely yield similar performance.

---

Tremendous progress has been made on quantizing and compressing neural networks. While it is not possible discuss all related work, below we recall a few families of gradient-based quantization algorithms that directly motivate our work; more methods can be found in recent surveys [15, 36].
BinaryConner (BC). Courbariaux et al. [11] considered binary networks where Q {+11] and proposed the BinaryConnect algorithm:
Wi+1 = w 7/e (())(w)))
where P is projector that quantizes the continuous weights w either deterministically (by taking the sign) or stochastically. Note that the (sample) gradient is evaluated at the quantized weights Wt ((w)), 1, while its continuous output, after scaled by the step size f,s is added to the continuous weights w For later comparison, it is useful to break the BC update into the following two pieces:
Wt P(w?);
Wi+1 w; T/. V((w.).
(3)
Other choices of P [1, 45] and Q [44, 53] in this framework have also been experimented with. ProxQuant (PQ). Bai et al. [5] applied the usual proximal gradient to solve (1):
W++1 P(w, 7/e Ve(w:)),
(4)
which can be similarly decomposed into:
W, P(w?), W = W. Ve(w.).
(5)
Thus, the only high-level difference between BC and PQ is that the former updates the continuous weights w while the latter updates the quantized weights w,. This seemingly minor difference turns cause drastically different behaviors of the two algorithms. For example, choosing P to be the Euclidean projection to Q works well for BinaryConnect but not at all for ProxQuant.
Reversing BinaryConnect. The above comparison naturally suggests reversed variant of BC:
W. P(w,),
W w. T/t Ve(w;),
which amounts to switching the continuous and quantized weights in the BC update. Similar to PQ, the choice of P is critical in this setup. To the best of our knowledge, this variant has not been formally studied before. Reversing BinaryConnect may not be intuitive, however, it serves as a general method (see Section 5).
starting point for
Post- -ast-Trinnig Quantization. Lastly, we can also rewrite the naive post-training quantization scheme in similar form:
Wr = P(wi), w = w (W(
where we simply train the continuous network as usual and then quantize at the end. Note that the quantized weights w, do not affect the update of the continuous weights wt.
3 What Makes Good Quantizer?
As we have seen in Section 2, the choice of the quantizer P turns out to be a crucial element for solving (1). Indeed, if P Pq is the projector onto the diserete quantization set Q, then BC (and ProxQuant) only evaluate the gradient of at (the finite set of) points in Q. As a result, the methods will be able to exploit the rich information carried in the continuous weights network, which can lead to non-convergence [Fig. lb, 5]. Since then, many semi-discrete quantizers, that turn continuous weights into more and more discrete ones, have been proposed [1, 5, 33, 45J. In this section, we present a principled way to construct quantizers that unifies previous efforts, removes tedious calculations, and also brings theoretical convenience when it comes down to analyzing the convergence of the algorithms in Section 2.
Our construction is based the proximal map PK: Rd = Rdd of (closed) function
Pf((w") arg arg min Zy w w + r(w).
(8)
w
where μ > 0 a smoothing parameter. The proximal map well-defined as long as the function r is lower bounded by quadratic function, in particular, when r is bounded from below. If is proper and (closed) convex, then the minimizer on the right-hand side of (8) is uniquely attained, while for general (nonconvex) functions the proximal map may be multi-valued (hence the notation =). If = lq is the indicator function (see (15) below), then Pa reduces to the familiar projector Po (for any μ)). Remarkably, complete characterization of such maps the real line is available:
3

---

Theorem 3.1 ([Proposition 3, 48]. A (possibly multi-valued) map P: R = is a proximal map (of some function r) iff it is (nonempty) compact-valuest monotone and has closed graph. The underlying function r is unique (up to addition of constants) iff P is convex-valued while is convex iff P is nonexpansive (i.e. 1-LLipschitz continuous).
The sufficient and necessary conditions of Theorem 3.1 allow one to design proximal maps P directly, without needing to know the underlying function at all (even though it is possible integrate version of r from P). The point is that, as far as quantization algorithms are concerned, having P is enough, and hence one is excused from the tedious calculations in deriving P from as is typical in existing works.
For example, the (univariate) mirror maps constructed in Ajanthan et al. [Theorem 1, 1], such as tanh, are proximal maps according to Theorem 1: In our notation, the (Mirror Descent) updates of Ajanthan et al. [1] are the same (3) with P (VΦ)- for some mirror map t. Since & is taken to strictly convex Ajanthan et al. [T], is easy to verify that satisfies all conditions of Theorem 3.1.²
The next result allows us employ stochastic quantizers, where in each iteration we randomly choose one of P. to quantize the weights". We may also apply different quantizers to different layers of neural network.
Theorem 3.2. Let P. Rd Rd i [k:]. be proximal maps. Then, the averaged map
P= Σ i= P., where a 2 0, E as =
(9)
is also a proximal map. Similarly, the product map
P P1 P2 x Pk, w (wi...., "w.....,w)).... (((W)) a proximal map (from dh to Rd
(10)
.....
(The proof of Theorem 3.2 and all other omitted proof' can be found in Appendix A.)
Example 3.3. Let Q be quantization set (e.g. Q = {-1, 0, 1))) Clearly, the identity map id and the projector Pq are proximal maps. Therefore, their convex combination P id+uPo also a proximal map, which is exactly the quantizer used in Yin et al. [45].
2 0, is 1+
Lastly, we mention that it is intuitively desirable have P + PQ when j increases indefinitely, so that the quantizer eventually settles on bona bode discrete values in Q. This is easily achieved by letting minimizers of the underlying function r, or the (possibly larger set of) fixed points of P approach Q. We give one such construction by exploiting Theorem 3.1 and Theorem 3.2.
3.1 General Piecewise Linear Quantizers
Let Q, = {gg,x (with G.1 ... S 9j.b,) be the quantization set for the j-th weight group* w/ E Rdd, Let Pj,++1 battg,tt1 k [b, 1], be the middle points. We introduce two parameters e 2 O and define
horizontal shifts:
" V (gat p), T/a= PJ A (Bi + p), PJA41 = lio V (Dj - e), P)A+1 == gi+t1 A (Pi.+1 + +2),
(11)
vertical shifts:
(12)
with 97,1 gj and Gj.4, Vi,h.- Then, define Lg as the piece-wise linear map (that simply
connects the points by straight lines):
9j.k:
if JJ S w- S $Oft if 1 I w² < Pj.k+1
) Pi Bink 9i + (w* - (j,kk Psck+1 -9
L Lg(w*)= =
(13)
P) + (w" PEA++)
Bo PPoet
if if < w0 S g7,+1
"The above reasoning hinges on & being univariate. More generally, a multivariate mirror map 1 I-strongly convex (as is typical in Mirror Descent), then it follows from Moreau [Corollaire 10.c, 30j that P (V being nonexpansion. is again a proximal map (of some convex function).
"This form of stochasticity still leads to determinisite networks, and is therefore conceptually different from probabilistic (quantized) networks [35, 39].
In this section, time subscripts not needed. Instead, use subscripts to indicate weight groups

---

(uo"))
P8
P8
=1
-1
-1
41
41
(a) = 0, = 0.2.
(b) = == 0.2.
(c) p 0.2,
Figure 1: Different instantiations of the proximal map LE in (13) for Q (-1,0,1).
for all w" E wj. At the middle points, L8()).+11 may take any value within the two limits. Following the commonly used weight clipping BC [11], we may set Lg(w*) ) = qú,1 for w" < 9, and Lg(w*)= 9j for w* > qiod. however, other choices may also work well. The proximal map Lg of an example ternary component is visualized in Figure for different choices of and
The (horizontal) parameter p controls the discretization vicinity within which continuous weight will be pulled exactly into the discrete set Qj. while the (vertical) parameter 0 controls the slope (i.e. expansiveness) of each piece. It follows map. In particular, setting 0 (hence continuous weights are only discretized in the limit) and 2(1+#) we recover Example 3.3 (assuming w.l.o.g. that 0j 0j.k 1). On the other hand, setting p e leads a generalization the (binary) quantizer Bai et al. [5], which keeps the slope to the constant (while introducing jumps at middle points) and happens to be the proximal map of the distance function to Q2 [5]. Of course, setting P = = yields the identity map and allows us to skip quantizing certain weights (as is common practice), while letting p, 2 + co recovers the projector Pay.
from Theorem 3.1 that Lg is indeed proximal
Needless to say, we may adapt the quantization set Q, and the parameters and for different weight groups, creating multitude of quantization schemes. By Theorem 3.2, the overall operator remains a proximal map.
Demystifying GinaryConned (BC)
Bai et al. [5] observed that the updates of BC are formally the same as the dual averaging (DA) algorithm [31, 42], even though the latter algorithm was originally proposed and analyzed only for convex problems. A lesser known fact is that (regularized) dual averaging itself is special case of the generalized conditional gradient (GCG) algorithm. this section, we first present the aforementioned fact, refine the observation of Bai et al. [5], and set up the stage for generalizing BC.
4.1 Generalized Conditional Gradient is Primal-
We first present the generalized conditional gradient (GCG) algorithm [8, 49] and point out its ability to solve simultaneously the primal and dual problems.
Let us consider the following "regularized" problem:
min f(w) == f(w) + r(w), wERd
(14)
where is general (nonconvex) regularizer. Setting to the indicator function of Q, i...
r(w) (Q(w) 0, if w EQ
(15)
oo, otherwise
reduces (14) to the original problem (1). As we will see, incorporating an arbitrary r does not add any complication but will allow us immediately generalize BC.
Introducing the Fenchel conjugate function Ha (resp. r") (resp. r): E (w") sup (w,w") - [(w),
(16)
5

---

which is always (closed) convex even when é itself is nonconvex, we state the Manchel-Rockafellae dual problem [38]:
min ERR
(-ww") +w"(
(17)
which, unlike the original problem (14), is always a convex problem.
We apply the generalized conditional gradient algorithm [8, 49] to solving the dual problem (17):
Given wi, we linearize the function r* and solve
z arg min (-ww"" + (w", wi) --VE"((E,) Wt Vr (w7),
(18)
where we used the fact that (V V mm Then, take the convex combination
W = (1 - >r)w? + Aez; where Ae E [0, 1]. The following theorem extends Bach [Proposition 4.2, 4] and Yu (TThorrm 4.6, 47] to any X Theorem 4.1. Suppose r" is L-smooth (i.c. Vr is L-Lipschitz continuous), then for any w:
(19)
(e (w+) (f + (*)) (w)) S (1 Ao) ( Wo)
X² [[| 2; (20)
2n,
where W, Vr'(w;) TH = -I= X7), and To A(W, w.)
r*a (ww) r**(w)
(w Wr. wi) is the Bregman divergence induced by the convex function P**
While the convergence of w the minimum of (17) is well-known (see e.g. Yu et [49]), the above result also implies that a properly averaged iterate w, also converges to the minimum of the dual problem of (17):
Corollary 4.2. Let W. = Er= Ae. Wy, where A = T. He and He Σt= have for any w:
d
Then, we
( - (e* +r") S (1 Ao)A(W, wo)
L Σ 2
A, Iw; 2
(21)
H₂
Assuming {z,} is bounded (e.g. when *** is Lipschitz continuous), right-hand side (21) dimin-
ishes X - 0 and Σ, A = co. Setting X = . recovers ergodic averaging w, =+1 Σt Wr for which the right-hand side of (21) diminishes at the rate O(log 1/1); see Appendix A.2 for details. Thus, GCG solves problem (17) and its dual simultancously.
4.2
BC C DA C GCG
We are now in position to reveal the relationships among BinaryConnect (BC), (regularized) dual averaging (DA) and the generalized conditional gradient (GCG), Since Theorem 4.1 requires r" to be L-smooth, in the event that it is not we resort to smooth approximation known as the Moreau envelope [30]:
(w*) = min
24 w 2011 +z()),
(22)
where the minimizer is (by definition) exactly P. (w*). ). It is well-known that Art is (1/p) and (AW)" ** + [30]. We then apply GCG the approximate dual problem:
min (-w-") Ar, (w"), ERd
(23)
whose own Mannhel-RRckferr dual is:
min (**(w) + (AF) wERd
= min weRd
(**(w) + r (w)
(w)+ ||
(24)
5GCG usually applied solving the primal problem (14) directly. choice dual problem here facilitate later comparison with dual averaging and BinaryConnect.
'The log factor can be removed by setting, for example, X 24r instead.
2

---

The updates of GCG applied to the approximate problem (23) are thus:
We = V.M. (w)) = (w?7 (see Proposition A.2 for derivation)
(25)
Wi+1 - Aw A,22 where zi ----" (w,),
(26)
which is exactly the updates of (regularized) dual averaging [42] for convex problems where? r" = and h** f. Nesterov [31] motivated dual averaging by the natural desire of non-decreasing step sizes, whereas conventional subgradient algorithms "counter-intuitvvll"" assign smaller step sizes to more recent iterates instead. Based on our explanation, we conclude this is possible because dual averaging solves an (approximate) smoothened dual problem, hence we can afford to use constant (rather than a dimirishing//decresinngg step size.
Defining Te. IT'_1(1 (1 Aα)) for 1, mo T- (1- Xo) -1 and setting wi We/ we have:
W.
W241 w³
de (we) n
(27)
Let us now reparameterize
d -1 and 1 1 Er=1 Mrrs
(28)
for t > 1. If we also allow μ Me to change adaptively from iteration to iteration (as in dual averaging), in particular, if f = Mt-1, we obtain the familiar update:
Wy P (w?),
W = W 7/8 V (wi).
(29)
For nonconvex problems, we may replace r"* and 8* with their nonconvex counterparts and f, respectively. We remark that (resp. (**) the largest convex function that is (pointwise) majorized by r (resp. E). In particular, with r = LQ and P!/" = Po (for any μm) we recover the BinaryConnedd update (3). While the parameter /a plays no role when is indicator function, we emphasize that for general we should use the quantizer p!/mm- where importantly 1/ + oc hence the quantizer converges to minimizers of asymptoticallyy Neglecting this crucial detail may lead to suboptimality as is demonstrated in the following example:
Example 4.3. Bai et al. [5] constructed the following intriguing example:
((w) = 2 3 Q = (+1), PM/((w) = sign(w) c/ul+ for |w|| 11
(30)
and they showed non-convergence of the algorithm w + w (p (w)), where μ a fixed constant. If we use p///t-1 with some diverging 1/T instead, the resulting BinaryConnect, with diminishing 7) or ergodic averaging, would actually converge (since p!/-t-1 - sign).
5 ProxConnect (PC): A Generalization of BinaryConnect
We are now ready to generalize BC by combining the results from Section 3 and Section 4. Replacing the convex envelopes, *** and r**, with their nonconvex counterpauts and replacing deterministic gradients with stochastic gradients (as well as the saanee-of-varibbee w² - w)), we obtain from (29) family of algorithms which we term ProxConnect (PC):
W: 1/== p.//==((w/)) (w?), w/+1 W 7pp Ve(w:),
(31)
where the quantizer p!/ may be designed directly by following Section We have already seen in Section 4 that BC belongs to PC by choosing P./ p//me-1 = Pq (in which case Ti plays no role).
The analysis in Section 4, initially tailored to convex functions, immediately generalizes to the nonconvex algorithm PC (for nonconvex nonconvex r, and stochastic gradients V():
That is, if we set A 1/t and allow for time-dependent μ Xiao [Algorithm 1, 42).
7

---

Theorem 5.1. Fix any w, the iterates in (31) satisfy:
Σ n=((w, -ww,,w,,
& - + Σ 4- (Wr),
(32)
7
where (.( = T (w()) (w
Wr+1, w is the Bregman divergence induced by the (possibly nonconvex) function r-(w) (w) w l
The summand on the left-hand side of (32) is related to the duality gap in Yu et al. [49]. which is natural measure of stationarity for the nonconvex problem (14). Indeed, it reduces to the familiar ones when convexity is present:
Corollary 5.2. For convex l and any w, the iterates (31) satisfy:
min B f(w)] 5 E:sa
EE[A-1(w) (()))( Σ. Ar(w+)].
(33)
If r is also convex, then
min BiJ((=)-J(w)) s Σize I[A+-I(W)+ | 11)
(34)
and
E E[f(w))-ffre S Sx._ E._, E EEAa-I Σ
y FI (w., )|
(35)
where W.-
Σ._, W=
The right-hand sides of (34) and (35) diminish iff 77 - and E. T) (assuming boundedness of the stochastic gradient). We note some trade-off in choosing the step size 7/r both the numerator and denominator of the right-hand sides of (34) and (35) increasing can be drawn for (33) and (32), where A, also depends on Л, (through the accumulated magnitude of w w1+)). A detailed analysis may need to take specific properties of P into account [45].
7)., The same conclusion
ProxQuant vs ProxConnect. It is worthwhile to point out one important difference between Prox- Quant and ProxConnect: Bai et al. [5] proved convergence (to some notion of stationarity) of ProxQuant for a fixed quantizer (see Bai al. [Theorem 5.1, 5]), i.e., PV for fixed μ4, but their experiments relied on incrementing μ that their quantizer approaches the projector Pq. This creates some discrepancy between theory and practice. The same comment also applies to [1]. In contrast, ProxConness is derived from rigorous theory that automatically justifies diverging μ. In particular, choosing a constant step size 7 = To would lead to 1/ 1/T,-1 x t, matching the current practice that is now justifiable if r strongly convex; Appendix A.3.1 for details.
Connection Existing Algorithms. Besides the obvious BC, ProxConnect generalizes many other quantization algorithms. As it turns out, many of these algorithms can also be realized using our proposed proximal quantizer Lg from Section 3; see Table for sample summary.
In Section 2, we discussed the idea of reversing BinaryConnect. As Prox- Connect generalizes BC, we also present reverserroxConned (rPC) generalization reversing BinaryConnect:
W, = P!/ (wi), W
- W) Ve(W?),
(36)
In contrast to reversing BinnaryConnect, rPC is not completely without merit: it evaluates the gradient the continuous weights w and hence is able to exploit richer landscape the loss. Even when stuck at fixed discrete weight w.. rPC may still accumulate sizable updates (as long as the step size and the gradient remain sufficiently large) allow eventually jump out of w;: note that the continuous weights wž still get updated. Finally, for constant step size v and æ, we note that fixed points of rPC, when existent, satisfy:
w P!! (w") - n)Ve(w") = w" = (id + -2 (id + [ 1) (w")
(37)
=: B n1 Vl, 8r कक (w*).
(38)

---

Table 1: sample summary of existing quantization algorithms. The PC column indicates the method is a special case of our proposed ProxConnect algorithm. The Le-column indicates if the method uses a quantizer which is a special case of our general quantizer L3 introduced in Section If so, the P, g-column states how p and were chosen (in practice): increasing S, fixed to 0, or fixed to co. Other than ProxQuant- Ternary, all methods can compute their quantizers in a single neural network pass. t: TrainedTermary methods might use quantizer different than Lg to improve performance.
Method
PC
One-pass
Learnable parameters
Lg
Ps 2
FroxQuant-Binary [5]
x
X
/
7, 7
Prox Suauutuuneeaaaat [5]
x
X
x
BinaryConnect [11]
d
X
V
00,00
BinaryRelax [45]
/
X
/ 0,
Binary Weight [37]
X
MirrorDescent [1]
X
X
TraineddTernary' [53]
V
00,00
Ternary Weight [26]
X
ProxConnect (ours)
/ 7.7
where for simplicity we assumed deterministic gradients Ve and be convex such that P!/" (id (id+Or/m)=+ The operator B is known as the backward-backward update (as opposed to the forward- backward update Prox FroxQuant), and it is known that when v/ - slowly, backward-backwerd converge to a stationary point [34]. Thus, despite of our current limited understanding of rPC, there is some reason (and empirical evidence as shown in Section 6) to believe it might still be interesting.
updates
Importance of GCG framework: Deriving PC from the GCG framework may let us transfer recent advances on GCG [7, 14, 50] neural network quantization. Furthermore, it is the cornerstone in justifying the widely-adopted diverging smoothing parameter.
6
Experiments
6.1
Classification on CIFAR-10
We perform image classification CIFAR-10 [24] using ResNet20 and ResNet56 [19], comparing BinaryConnect [11] with ProxQuant [5] and (reverse)ProxCCnnee) using our proposed proximal operator Lg. For fair comparison,
set e in Lg as this resembles the quantizer (for binary quantization) used in the original ProxQuant algorithm. Similar to Bai et al. [5], we increase the
parameter o (or equivalently @) linearly: P: (1 + t/ t/B) po- In contrast to Bai et al. [5], however, we increase P after every gradient step rather than after every epoch as this is more in line with analysis. We treat Po a hyperparameter for which we conduct small grid search. We consider binary (Q = { f-1. 1)), ternary (Q = (-1,0, 13) and quaternary (Q quantization. Details for all CIFAR- experiments can be found in Appendix B.1.
00.3, 1))
Fine- Fine-Tuning Pretrained Models. In this experiment, all quantization algorithms are initialized with pretrained ResNet. The test accuracies of the pretrained ResNet20 and ResNet56 are 92.01 and 93.01, respectively. Table 2 shows the final test accuracies for the different models. For ProxQuant and (reverse)Proxoomeee be found in Appendix B.1.7. (Reverse)ProxCome settings.
respectively picked the best Po values; results for all Po values can
outperforms the other two methods on all six
End-To-End Training. To save computational costs, important that quantization algorithms also perform well when they are not initialized with pretrained full preciireoiioon model. We therefore compare the four methods for randomly initialized models; see Table for the results. ProxConnect outperforms all other methods on all six tasks. Interestingly, ProxQuant and reverseProxConneet perform considerably worse for all six tasks when compared to fine-tuning. The performance drop of BinaryConnect and ProxConnect when compared to fine-tuning is only significant for ternary

---

Table Fine-tuning pretrained ResNets. Final test aceuracy; mean and standard deviation runs.
Model
Quantization
BC [11]
PQ [5]
rPC (ours)
PC (ours)
Binary
90.31 (0.00)
89.94 (0.10)
89,98 (0.17)
90.31 (0.21)
ResNet20
Ternary
74.95 (0.16)
91.46 (0.06)
91.47 (0.19)
91.37 (0.18)
Quaternary
91.43 (0.07)
91.43 (0.21)
91.43 (0.06)
91.81 (0.14)
Binary
92.22 (0.12)
92.33 (0.06)
92,47 (0.29)
92.65 (0.16)
ResNet56
Ternary
74.68 (1.4)
93.07 (0.02)
92.84 (0.11)
93.25 (0.12)
Quaternary
93.20 (0.06)
92.82 (0.16)
92.91 (0.26)
93,42 (0.12)
Table 3: End-to-end training of ResNets. Final test aceuracy: and standard deviation in 3 runs.
Model
Quantization
BC [11]
PQ [5]
rPC (ours)
PC (ours)
Binary
87.51 (0.21)
81.59 (0.75)
81.82 (0.32)
89.92 (0.65)
ResNet20
Ternary
27.10 (0.21)
47.98 (1.30)
47.17 (1.94)
84.09 (0.16)
Quaternary
89.91 (0.09)
85.29 (0.09)
85.05 (0.27)
90.17 (0.14)
Binary
89.79 (0.45)
86.13 (1.71)
86.25 (1.50)
91.26 (0.59)
ResNet56
Ternary
30.31 (7.79)
50.54 (3.68)
42.95 (1.57)
84.36 (0.75)
Quaternary
90.69 (0.57)
87.81 (1.60)
87.30 (1.02)
91.70 (0.14)
quantization. We found that Prox and reversetroxConnect can be quite sensitive to the choice of po. whereas ProxConnect stable in this regard; Appendix B.1.7.
6.2 Classification ImageNet
We perform a small study on ImageNet [12] using ResNet18 [19]. As can be seen in Table 4, BC performs slightly better for fine-tuning whereas PC performs slightly better for end-to-end training. This is not an exhaustive study, but rather a first indication that PC can yield competitive performance on large scale datasets. For more details on the experiments see Appendix B.2.
Table Fine-tuning (left) and end-to-end training (right). Final test accuracy: mean and standard deviation over three runs.
PC (ours)
PC (ours)
BC [11]
BC [11]
Po
2e-2
Pb 4e-2
Po 2.5e-3
Pn 5e-3
65.84 (0.04)
65.44 (0.13)
65.70 (0.04)
63.79 (0.12)
63.89 (0.14)
63.67 (0.12)
7
Conclusion
Capitalizing principled approach for designing quantizers and surprising connection between and the generalized conditional gradient (GCG) algorithm, we proposed ProxConnect as unification and generalization of existing neural network quantization algorithms. Our analysis refines prior convergence guarantees and our experiments confirm the competitiveness of ProxConnect. In future work, we plan apply ProxConnect to training other models such transformers. The connection with GCG also opens the possibility for further acceleration.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their constructive comments as well as the area chair and the senior area chair for overseeing the review process. YY thanks NSERC for funding support. We thank Jingjing Wang for some early discussions.
10

---

References
[1] Thalaiyasingam Ajanthan, Kartik Gupta, Philip Torr, Richard Hartle, and Puneet Dokania. Mirror Descent View for Neural Network Quantization. In International Conference on Artificial Intelligence and Statistics, 2021.
[2] Milad Alizadeh, Javier Germández-Marqueee Nicholas D. Lane, and Yarin Gal. An Empirical study of Binary Neural Networks' Optimisation. In International Conference on Learning Representations, 2019.
[3] Alexander G. Anderson and Cory P. Berg. The High- DigeenDimmsiional Geometry of Binary Neural Networks. In International Conference on Learning Representations, 2018.
[4] Francis Bach. Duality Between Subgradient and Conditional Gradient Methods. SIAM Journal on Optimization, 25 2015.
[5] Yu Bai, Yu-Xiang Wang, and Edo Liberty. ProxQuant: Operators. In International Conference Learning Representations, 2018.
Quantized Neural Networks via Proximal
[6] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating Propagating Gradients Through Stochastic Neurons for Conditional Computation. arXiv:1308. 3432, 2013.
[7] Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Deep Frank- Frank-Wolfe For Neural Network Optimization. In International Conference on Learning Representations, 2019.
[8] Kristian Bredies and Dirk A. Lorenz. Iterated Hard Shrinkage for Minimization Problems with Sparsity Constraints. SIAM Journal on Scientific Computing, 30(2))657-6683 2008.
[9] Tom Brown and al. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems, pages 1877-1901, 2020.
[10] Shangyu Chen, Wenya Wang. and Sinno Jialin Pan. MetaQuant: Learning to Quantize by Learning to Penetrate con-differentiable Quantization. In Advances in Neural Information Processing Systems, 2019.
[11] Matthieu Courbariaux, Yoshua Bengio, and Neural Networks with binary weights during propagations. In Advances in Neural Information Processing Systems, volume 28, pages 3123-3131, 2015.
David. BinaryConnect: Training Deep
[12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In JEEE Conference Computer Vision and Pattern Recognition, pages 248-24882 200,22552222 2009.
[13] Yukun Ding, Jinglan Liu, Jinjun Xiong, and Yiyu Shi. On the Universal Approximability and Complexity Bounds of Quantized ReLU Neural Networks. International Conference on Learning Representationss 2019.
[14] Pavel Dvurechensky, Petr Ostroukhov, Kamil Safin, Shimrit Shtern, and Mathias Staudigl. Self-Concordant Analysis of Frank-Wolfe Algorithms. In International Conference on Machine Learning, 2020.
[15] Yunhui Guo. A Survey on Methods and Theories of Quantized Neural Networks. 1808 04752, 2018.
[16] Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep Learning with Limited Numerical Precision. International Conference on Machine Learning, 2015.
[17] Kai Han, Yunhe Wang, Yixing Xu, Chunjing Xu, Enhua Wu, and Chang Xu. Training Binary Neural Networks through Learning with Noisy Supervision. In International Conference Machine Learning, 2020.
[18] Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A Horowitz, and William J Dally. EIE: Efficient Inference Engine on Compressed Deep Neural Network, ACM SIGARCH Computer Architecture News, 14(3):243-254 2016.

---

[19] Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
[20] Koen Helwegen, James Widdicombe, Lukas Geiger, Zechun Liu, Kwang-Ting Cheng, and Roeland Nusselder. Latent Weights Do Not Exist: Rethinking Binarized Neural Network Optimization. In Advances in Neural Information Processing Systems, 2019.
[21] Sara Hooker, Nyalleng Moorosi, Gregory Clark, Samy Bengio, and Emily Denton. Characteris- ing Bias in Compressed Models. arXiv:2010.03058, 2020.
[22] Lu Hou, Ruiliang Zhang, and James Kwok. Analysis of Quantized Models. International Conference Learning Representations, 2019.
[23] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Quan- tized Neural Networks: Training Neural Networks with Low Precision Weights and Activations. Journal of Machine Learning Research, 18(1):6869-688) 2017.
[24] Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images, 2009, The MIT License.
[25] Cong Leng, Zesheng Dou, Hao Li, Shenghuo Zhu, and Rong Jin. Extremely Low Bit Neural Network: Squeeze the Last Bit Out With ADMM. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[26] Fengfu Li, Bo Zhang, and Bin Liu. Terary Weight Networks. arXiv:1605.04711 2016.
[27] Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training Quantized Nets: Deeper Understanding. In Advances in Neural Information Processing Systems, 2017.
[28] Ji Lin, Wei-Ming Chen, Yujun Lin, Chuang Gan, and Song Han. MCUNet: Tiny Deep Learning on IoT Devices. Advances Neural Information Processing Systems, 2020.
[29] Brais Martinez, Jing Yang, Adrian Bulat, and Georgios Tzimiropoulos. Training binary neural networks with real-to-binary convolutions. In International Conference on Learning Represen- tations, 2020.
[30] Jean-Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273-299, 1965.
[31] Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Program- ming, 120(1):221-255)) 2009.
[32] E. Park, J. Ahn, and S. Yoo. Weighted- Entrooy
Entropy-Based Basedd Quantization for Deep Neural Networks. In IEEE Conference on Computer Vision and Patlern Recognition (CVPR), pages 7197-7205, 2017.
[33] Vahid Partovi Nia and Mouloud Belbahri. Binary Quantizer. Journal of Computational Vision and Imaging Systems, 4(1):3, 2018
[34] Gregory B Passty. Ergodic Convergence a Zero of the Sum of Monotone Operators in Hilbert Space. Journal of Mathematical Analysis and Applications, 72(2):383-390, 1979.
[35] Jom WT Peters and Max Welling. Probabilistic Binary Neural Networks. arXiv: 2018.
[36] Haotong Qin, Ruihao Gong, Xianglong Liu, Xiao Bai, Jingkuan Song, and Nicu Sebe. Binary Neural Networks: A Survey. Pattern Recognition, 105:107281, 2020.
[37] Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. XNOR-Net Ima- geNet Classification Using Binary Convolutional Neural Networks. In European Conference on Computer Vision, 2016.
[38] R. Tyrrell Rockafellar and Roger J-B Wets. Variational Analysis. Springer, 1998.
12

---

[39] Oran Shayer, Dan Levi, and Ethan Fetaya. Learning Discrete Weights Using the Local Repa- rameterization Trick. In International Conference on Learning Representations, 2018.
[40]
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and Policy Considerations for Deep Learning in NLP. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3645-3650, 2019.
[41] Yanzhi Wang, Zheng Zhan, Liang Zhao, Jian Tang, Siyue Wang. Jiayu Li, Bo Yuan, Wujie Wen, and Xue Lin. Universal Approximation Property and Equivalence of Stochastic Computing- Based Neural Networks and Binary Neural Networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019.
[42] Lin Xiao. Dual Averaging Methods for Regularized Stochastic Learning and Online Optimiza- tion. Journal of Machine Learning Research, 11:2543-2555 2596, 2010.
[43] Chen Xu, Jianqiang Yao, Zhouchen Lin, Wenwu Ou, Yuanbin Cao, Zhirong Wang, and Hongbin Zha. Alternating Multi-bit Quantization for Recurrent Neural Networks. International Conference Learning Representations, 2018.
[44] P Yin, S Zhang, YY Qi, and Xin. Quantization and Training of Low Bit-Width Convolutional Neural Networks for Object Detection. Journal of Computational Mathematics, 37(3), 2019.
[45] Penghang Yin, Shuai Zhang, Jiancheng Lyu, Stanley Osher, Yingyong Qi, and Jack Xin. BilaryRelax: A Relaxation Approach for Training Deep Neural Networks with Quantized Weights. SIAM Journal on Imaging Sciences, 2242 2018.
[46] Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley J. Osher, Yingyong Qi, and Jack Xin. Understanding Fraaight-Througee Estimator Training Activation Quantized Neural Nets. In International Conference on Learning Representutions, 2019.
[47] Yaoliang Yu. Fast Gradient Methods for Structured Sparsity. PhD thesis, University of Alberta, 2013.
[48] Yaoliang Yu, Xun Zheng, Micol Marchetti-Bowick, and Eric Xing. Minimizing Nonconvex Separabee Functions. In Artificial Intelligence and Statistics, 2015.
[49] Yaoliang Yu, Xinhua Zhang, and Dale Schuurmans. Generalized Conditional Gradient for Structured Sparse Estimation. Journal of Machine Learning Research, 18:1-46, 2017.
[50] Mingrui Zhang, Lin Chen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Quantized Frank-Wae Wolfe: Faster Optimization, Lower Communication, and Projection Free. In Interna- lional Conference on Artificial Intelligence and Statistics, 2020.
[51] Aojun Zhou, Anbang Yao, Yiwen Guo, Lin Xu, and Yurong Chen. Incremental Network Quan- tization: Towards Lossless CNNs with Low Low-precision Weights. In International Conference on Learning Representations, 2017.
[52] Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou. DoReFa- Net: Training low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients. arXiv:1606.06160. 2016.
[53] Chenzhuo Zhu, Song Han, Huizi Mao, and William J Dally. Trained Ternary Quantization. In International Conference on Learning Representations, 2018.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] As discussed, the goal of our paper is to improve the understanding of BinaryConenct [11] and obtain novel generalizations. We therefore focus more on theory than empirical results. As a result, we only did extensive experiments on one dataset (CIFAR-10 10) with one architecture (ResNet20/56). As discussed in Section 6.2, our experiments on ImageNet are not exhaustive; both due to environmental reasons well as limited availability of compute. In the future, we aim to do more exhaustive testing of ProxConnect (different architectures and problems), while keeping in mind the carbon footprint that comes with it.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the first paragraph of Section I: quantization leads to decreased carbon footprint for training and inference (positive societal impact), however, it may come at the cost of increased bias (negative societal impact).
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are provided in the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No] We will provide
the code once it has been approved by our internal process. We only ran experiments on publicly available datasets.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6, Appendix B. and Appendix B.2.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] All experiments are over three random seeds; we provide mean and standard deviation for all results.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] The amount of compute in the exploration stage of our project was insignificant compared to the experiments reported in this work. See Appendix 1.6 and Appendix B.8 for the total amount of compute we used for the experiments reported in this work.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 6. and Section 6.2.
(b) Did you mention the license of the assets? [Yes] Yes, the license of CIFAR- 10 (MIT license) is included in the bibliography entry. The ImageNet dataset "is available for free to researchers for non non-commercial use".
(c) Did you include any new assets either in the supplemental material or as a URL? [No] We will provide the code once it has been approved by our internal process.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, if applicable? [N/A]
14

---

(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "9v-6FWjHldr", "reviewer": "Reviewer_Ub8c", "summary": "This paper proposes a generalized conditional gradient (GCG) framework for training weight-quantized neural networks. The framework extends existing BinaryConnect and ProxQuant. Convergence bound is established for general, non-convex problem. Compared to ProxQuant, the proposed theory supports evolving quantizers. The paper also proposes a family of smooth quantizers, parameterized by the horizontal and vertical shift. The proposed ProxConnect outperforms existing approaches on end-to-end training of ResNets.", "questions": "", "limitations": "", "rating": 7, "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": "Principled training methods for quantized neural networks is a important problem to study. This paper generalizes existing theory on training weight-quantized neural networks with a generalized conditional gradient (GCG) framework. The unified view of existing methods in Sec. 2 is interesting.\n\nHowever, I think the contribution of this paper is somewhat incremental, as the convergence is already established for smooth and non-convex problems in Bai et al.. The generalization of dual averaging under the GCG framework is one of the main contribution of this paper. However, the advantage of GCG over DA is not sufficiently demonstrated. There lacks a strong showcase to explain why the general theoretical result (Theorem 5.1) is useful. If the authors want to emphasize time-dependent quantizers, I think more explanations should be included. Can we theoretically justify why the proposed quantizers can achieve better results, e.g., through a better convergence bound?\n\nThe paper is somewhat hard to read and understand. I am particularly confused on the role of Sec. 4. If my understanding is correct, in the non-convex setting, the dual problem (17) is only a lower bound of the original problem (14). In this case, why is Theorem 4.1 and Corollary 4.2 useful, as they don't directly discuss the original problem? If these theorems are not directly applicable, I would suggest to put more effort on the more relevant Sec. 5. For example, I think Theorem 5.1 needs more explanations. What does the term Delta_tau looks like if r(w) is an indicator function? Can Theorem 5.1 reduces to Theorem 5.1 in the ProxQuant paper if the quantizer is fixed?\n\nFigure 2 and Table 1 are too messy to read. Please consider replacing the random symbols with text. \n\nPost Rebuttal\n====\n\nAfter reading the authors' response and spent several more hours in reading relevant papers I am convinced that the submission made a non-trivial contribution upon existing works (Li et al., Bai et al.), in the sense that it formally shows the convergence for BinaryConnect for non-convex problems. The natural treatment of increasingly \"discrete\" proximal map is also interesting. Therefore I increased my rating from 5 to 7 and the confidence from 2 to 3.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work doesn't have any foreseeable potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "72h519LMWuL", "reviewer": "Reviewer_5Fsk", "summary": "The paper presents a refined theoretical understanding of binary connect via relating the dual-averaging method to generalized conditional gradient descent. Then, a general proximal connect algorithm is presented. Experiments on image classification datasets show marginal improvements over the comparable methods.", "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": "## Post-rebuttal Update\nI thank the authors for clarifying the questions. I would strongly encourage them to include the discussion related to MD and [1] clearly in the main paper to clarify the main contributions of the paper. Upon this condition, I increase the score to 7.\n\n## Strengths\n- The summarization of different quantization methods under one umbrella is interesting and useful.\n- Even though there are many attempts to provide a wholesome theory for binary connect previously, this paper refines the understanding by including the annealing hyperparameter into the theoretical framework.\n- The connection to generalized conditional gradient descent seems interesting.\n\n## Weaknesses\n- Not clear mirror descent (MD) would be a special case of proximal connect: In my understanding, dual averaging is a special case of MD [a] and generalizing dual averaging does not mean MD would be a special case of the proposed method. Furthermore, MD supports nonlinear projections (such as tanh or softmax [1]) whereas the proposed formulation supports piecewise linear projections. So I'm not sure PC would be a generalization of the methods discussed in [1]. Please clarify.\n\n- The main idea of this paper is in Eq. 8 (and Eq. 31, if I understand correctly) where the regularizer $r$ is parametrized as opposed to ProxQuant [5]. May be this interpretation should be mentioned early so as to simplify the understanding of the final PC algorithm.\n\n\n## References\n- [a] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends R in\nMachine Learning, 2015.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "5t9Y5UmIlO1", "reviewer": "Reviewer_bjiL", "summary": "This paper seeks to give a theoretical grounding to the study of the quantisers used in the training of neural networks. The authors use proximal maps as the foundation to construct quantisers, and demonstrate that a host of known quantisation techniques can be cast in this manner.\n\nThe authors show that BinaryConnect is a special case of the GCG algorithm, and use this as motivation to construct their own more general version - Proximal Connect - which contains BinaryConnect as a special case.\n\nResults are shown on classification of CIFAR-10, and demonstrate that the proposed method improves performance on this task over BinaryConnect and ProxQuant (the main methods this work focuses on).", "questions": "", "limitations": "", "rating": 7, "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": "This work has two types of contribution - the theoretical understanding given about already existing quantisers, and the proposal of a new quantiser (PC) which the authors show has advantages over existing techniques.\n\nI think in general the theoretical contributions are valuable to the community, since the quantisation techniques used in training quantised neural networks are somewhat poorly understood. Although the casting of the quantisation problem in the language of proximal maps is not novel, the relation to the various known quantisers in ML is useful.\n\nThe authors then show that BinaryConnect (the main quantiser used for binary weights) is a special case of the GCG algorithm. It was already known that BC was a special case of the regularised dual averaging problem, but the GCG does generalise it further. It is not clear to me exactly how valuable this realisation is. At the least, the authors use it to motivate the construction of their PC quantiser, and perhaps there could be more developments that are enabled by this knowledge. \n\nThe new PC quantiser is then demonstrated to improve results on a fine-tuning task for image classification. Although this is a relatively limited evaluation (there is only one experiment, CIFAR-10, considered) there is enough theoretical meat to justify this in my eyes. The improvements are seemingly significant, in that BC and PQ each have failure cases in the given experiments, that PC does not have. Although these failure cases (for example end-to-end training of ternary weights for PQ) could be resolved by other existing techniques, it seems that the entire points of this work is to try and provide a more solid and reliable quantiser by examining overarching theory, rather than developing brittle quantisers for special cases. The PC quantiser itself seems to be relatively straightforward, after all is said and done, in that it is just a linear piecewise function of varying slopes and level intervals around quantisation points. I would say that simplicity is a good thing though, if such a technique is going to be adopted by the community.\n\nI also find in general the work very well-written, although at points it can be dense in notation and a bit tricky to follow through the more involved sections.\n\nSome small points:\n * the authors mention that stochastic quantisation can be cast in the proximal mapping framework. Do they have any thoughts about how the class of methods for training stochastic quantisers might relate to their framework? For example [1] and [2].\n* the authors talk about the reverse BC and reverse PC algorithms, giving experimental results for the latter. Although this is clearly a scheme that we can write down, and it is motivated by the PQ algorithm, it does not seem intuitive to me. Why would we want to update the continuous parameters starting from the locations of the current quantised parameters? Perhaps this is just a gap in my optimisation intuition.\n\n[1] LEARNING DISCRETE WEIGHTS USING THE LOCAL REPARAMETERIZATION TRICK\nOran Shayer et al. ICLR 2018\n\n[2] Probabilistic Binary Neural Networks\nJorn W.T. Peters et al. 2018", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any societal impact of the work, since it is a primarily theoretical work focused on quantisation.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't see any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After the discussion, all reviewers recommend accept (7). For example, one reviewers emphasized "the submission made a non-trivial contribution upon existing works (Li et al., Bai et al.), in the sense that it formally shows the convergence for BinaryConnect for non-convex problems.". I find this alone sufficient novel. Also, the unification and extension of previously suggested algorithms are quite interesting, and the empirical results are not bad for a theoretical paper. The only concern raising from the reviews seems to be that the paper is dense, and I hope the authors can improve improve readability, if possible.
Decision: Accept (Poster)