Demystifying and Generalizing BinaryConnect
Year: 2022

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.

heading: 1 Introduction
text: Scaling up to extremely large datasets and models has been a main ingredient for the success of deep learning. Indeed, with the availability of big data, more computing power, convenient software, and a bag of training tricks as well as 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-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 a large model through quantization, i.e., replacing high-precision parameters with lower-precision ones. For example, we may constrain a subset of the weights to be binary [1, 5, 11, 29, 33, 37, 45] or ternary [26, 53]. Quantization can drastically decrease the carbon footprint of training and inference of neural networks, however, it 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 matrix-vector products [18, 23]. Training and inference can be made even more efficient by also quantizing the activations [37] or gradients [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 Ark Lab. Correspondence to tim.dockhorn@uwaterloo.ca.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
BinaryConnect [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 a (close-by) quantization point using the Straight Through Estimator [6]. Despite its empirical success, BC has largely remained a “training trick” [1] and a 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 to each other: the only high-level difference is at what points we evaluate the gradient and perform the update.
• In Section 3, we present a 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 a 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 et al. [5] that the updates of BC are the same as the dual averaging algorithm [31, 42]: BC is a nonconvex counterpart of dual averaging, and more importantly, dual averaging itself is simply the generalized conditional gradient algorithm applied to a 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, 5, 45].
• In Section 6, we verify that PC outperforms BC and ProxQuant [5] on CIFAR-10 for both finetuning pretrained models as well as end-to-end training. On the more challenging ImageNet dataset, PC yields competitive performance despite of minimal hyperparameter tuning.

heading: 2 Background
text: We consider the usual (expected) objective `(w) = E`(w, ξ), where ξ represents random sampling. For instance, `(w) = 1n ∑n i=1 `i(w) where ξ is uniform over n training samples (or minibatches thereof), w are the weights of a neural network and `i may be the cross-entropy loss (of the i-th training sample). We denote a sample (sub)gradient of ` at w and ξ as ∇̃`(w) = ∇`(w, ξ) so that E∇̃`(w) = ∇`(w). Throughout, we use the starred notation w∗ for continuous weights and reserve w for (semi)discrete ones.
We are interested in solving the following (nonconvex) problem:
min w∈Q `(w), (1)
where Q ⊆ Rd is a discrete, nonconvex quantization set. For instance, on certain low-resource devices it may be useful or even mandatory to employ binary weights, i.e., Q = {±1}d. Importantly, our goal is 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 ∈ 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, a 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 to 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].
BinaryConnect (BC). Courbariaux et al. [11] considered binary networks where Q = {±1}d and proposed the BinaryConnect algorithm:
w∗t+1 = w ∗ t − ηt∇̃`(P(w∗t )), (2)
where P is a projector that quantizes the continuous weights w∗t either deterministically (by taking the sign) or stochastically. Note that the (sample) gradient is evaluated at the quantized weights wt := P(w ∗ t ), while its continuous output, after scaled by the step size ηt, is added to the continuous weights w∗t . For later comparison, it is useful to break the BC update into the following two pieces:
wt = P(w ∗ t ), w ∗ t+1 = w ∗ t − ηt∇̃`(wt). (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): wt+1 = P(wt − ηt∇̃`(wt)), (4)
which can be similarly decomposed into:
wt = P(w ∗ t ), w ∗ t+1 = wt − ηt∇̃`(wt). (5)
Thus, the only high-level difference between BC and PQ is that the former updates the continuous weights w∗t while the latter updates the quantized weights wt. This seemingly minor difference turns out to 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 a reversed variant of BC: wt = P(w ∗ t ), w ∗ t+1 = wt − ηt∇̃`(w∗t ), (6)
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 starting point for a more general method (see Section 5).
Post-Training Quantization. Lastly, we can also rewrite the naive post-training quantization scheme in a similar form:
wt = P(w ∗ t ), w ∗ t+1 = w ∗ t − ηt∇̃`(w∗t ), (7)
where we simply train the continuous network as usual and then quantize at the end. Note that the quantized weights wt do not affect the update of the continuous weights w∗t .

heading: 3 What Makes a Good Quantizer?
text: 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 discrete 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 not be able to exploit the rich information carried in the continuous weights network, which can lead to non-convergence [Fig. 1b, 5]. Since then, many semi-discrete quantizers, that turn continuous weights into more and more discrete ones, have been proposed [1, 5, 33, 45]. 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 on the proximal map Pµr : Rd ⇒ Rd of a (closed) function r: Pµr (w
∗) = arg min w 1 2µ‖w −w ∗‖22 + r(w), (8)
where µ > 0 is a smoothing parameter. The proximal map is well-defined as long as the function r is lower bounded by a quadratic function, in particular, when r is bounded from below. If r 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 r = ιQ is the indicator function (see (15) below), then Pµr reduces to the familiar projector PQ (for any µ). Remarkably, a complete characterization of such maps on the real line is available:
Theorem 3.1 ([Proposition 3, 48]). A (possibly multi-valued) map P : R ⇒ R is a proximal map (of some function r) iff it is (nonempty) compact-valued, monotone and has a closed graph. The underlying function r is unique (up to addition of constants) iff P is convex-valued, while r is convex iff P is nonexpansive (i.e. 1-Lipschitz 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 r at all (even though it is possible to integrate a 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 r 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 3.1: In our notation, the (Mirror Descent) updates of Ajanthan et al. [1] are the same as (3) with P = (∇Φ)−1 for some mirror map Φ. Since Φ is taken to be strictly convex in Ajanthan et al. [1], it is easy to verify that P satisfies all conditions of Theorem 3.1.2
The next result allows us to employ stochastic quantizers, where in each iteration we randomly choose one of Pi to quantize the weights3. We may also apply different quantizers to different layers of a neural network. Theorem 3.2. Let Pi : Rd ⇒ Rd, i = [k], be proximal maps. Then, the averaged map
P := ∑k i=1 αiPi, where αi ≥ 0, ∑k i=1 αi = 1, (9)
is also a proximal map. Similarly, the product map P := P1 × P2 × · · · × Pk, w∗ = (w∗1, . . . ,w∗k) 7→ ( P1(w ∗ 1), . . . ,Pk(w ∗ k) )
(10)
is a proximal map (from Rdk to Rdk).
(The proof of Theorem 3.2 and all other omitted proofs can be found in Appendix A.) Example 3.3. Let Q be a 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+µPQ 1+µ , µ ≥ 0, is also a proximal map, which is exactly the quantizer used in Yin et al. [45].
Lastly, we mention that it is intuitively desirable to have Pµ → PQ when µ increases indefinitely, so that the quantizer eventually settles on bona fide 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.

heading: 3.1 General Piecewise Linear Quantizers
text: Let Qj = {qj,k} bj k=1 (with qj,1 ≤ · · · ≤ qj,bj ) be the quantization set for the j-th weight group4 w∗j ∈ Rdj . Let pj,k+1 := qj,k+qj,k+1
2 , k ∈ [bj − 1], be the middle points. We introduce two parameters ρ, % ≥ 0 and define
horizontal shifts: q−j,k := pj,k ∨ (qj,k − ρ), q + j,k := pj,k+1 ∧ (qj,k + ρ), (11) vertical shifts: p−j,k+1 := qj,k ∨ (pj,k+1 − %), p + j,k+1 := qj,k+1 ∧ (pj,k+1 + %), (12)
with q−j,1 = qj,1 and q + j,bj = qj,bj . Then, we define L % ρ as the piece-wise linear map (that simply connects the points by straight lines):
L%ρ(w ∗) :=  qj,k, if q−j,k ≤ w∗ ≤ q + j,k qj,k + (w ∗ − q+j,k) p−j,k+1−qj,k pj,k+1−q+j,k , if q+j,k ≤ w∗ < pj,k+1
p+j,k+1 + (w ∗ − pj,k+1) qj,k+1−p+j,k+1 q−j,k+1−pj,k+1 , if pj,k+1 < w∗ ≤ q−j,k+1,
(13)
2The above reasoning hinges on Φ being univariate. More generally, if a multivariate mirror map Φ is 1-strongly convex (as is typical in Mirror Descent), then it follows from Moreau [Corollaire 10.c, 30] that P = (∇Φ)−1, being a nonexpansion, is again a proximal map (of some convex function).
3This form of stochasticity still leads to determinisitc networks, and is therefore conceptually different from probabilistic (quantized) networks [35, 39].
4In this section, time subscripts are not needed. Instead, we use subscripts to indicate weight groups.
for all w∗ ∈ w∗j . At the middle points, L%ρ(pj,k+1) may take any value within the two limits. Following the commonly used weight clipping in BC [11], we may set L%ρ(w
∗) = qj,1 for w∗ < qj,1 and L%ρ(w ∗) = qj,bj for w ∗ > qj,bj , however, other choices may also work well. The proximal map L%ρ of an example ternary component is visualized in Figure 1 for different choices of ρ and %.
The (horizontal) parameter ρ controls the discretization vicinity within which a continuous weight will be pulled exactly into the discrete set Qj , while the (vertical) parameter % controls the slope (i.e. expansiveness) of each piece. It follows at once from Theorem 3.1 that L%ρ is indeed a proximal 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 qj,k+1 − qj,k ≡ 1). On the other hand, setting ρ = % leads to a generalization of the (binary) quantizer in Bai et al. [5], which keeps the slope to the constant 1 (while introducing jumps at middle points) and happens to be the proximal map of the distance function to Qj [5]. Of course, setting ρ = % = 0 yields the identity map and allows us to skip quantizing certain weights (as is common practice), while letting ρ, %→∞ recovers the projector PQj .
Needless to say, we may adapt the quantization set Qj and the parameters % and ρ for different weight groups, creating a multitude of quantization schemes. By Theorem 3.2, the overall operator remains a proximal map.

heading: 4 Demystifying BinaryConnect (BC)
text: 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 a special case of the generalized conditional gradient (GCG) algorithm. In this section, we first present the aforementioned fact, refine the observation of Bai et al. [5], and set up the stage for generalizing BC.

heading: 4.1 Generalized Conditional Gradient is Primal-Dual
text: 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 w∈Rd f(w) := `(w) + r(w), (14)
where r is a general (nonconvex) regularizer. Setting r to the indicator function of Q, i.e.,
r(w) = ιQ(w) = { 0, if w ∈ Q ∞, otherwise , (15)
reduces (14) to the original problem (1). As we will see, incorporating an arbitrary r does not add any complication but will allow us to immediately generalize BC.
Introducing the Fenchel conjugate function `∗ (resp. r∗) of ` (resp. r): `∗(w∗) := supw 〈w,w∗〉 − `(w), (16)
which is always (closed) convex even when ` itself is nonconvex, we state the Fenchel–Rockafellar dual problem [38]:
min w∗∈Rd
`∗(−w∗) + r∗(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 problem5 (17): Given w∗t , we linearize the function r ∗ and solve
z∗t =
[ arg min
w∗ `∗(−w∗) + 〈w∗,wt〉
] = −∇`∗∗(wt), wt := ∇r∗(w∗t ), (18)
where we used the fact that (∇`∗)−1 = ∇`∗∗. Then, we take the convex combination w∗t+1 = (1− λt)w∗t + λtz∗t , where λt ∈ [0, 1]. (19)
The following theorem extends Bach [Proposition 4.2, 4] and Yu [Theorem 4.6, 47] to any λt: Theorem 4.1. Suppose r∗ is L-smooth (i.e. ∇r∗ is L-Lipschitz continuous), then for any w:
t∑ τ=0 λτ πτ [(`∗∗ + r∗∗)(wτ )− (`∗∗ + r∗∗)(w)] ≤ (1− λ0)∆(w,w0) + t∑ τ=0 λ2τ 2πτ L‖w∗τ − z∗τ‖22, (20)
where wt := ∇r∗(w∗t ), πt := ∏t τ=1(1 − λτ ), and π0 := 1. ∆(w,wt) := r∗∗(w) − r∗∗(wt) − 〈w −wt,w∗t 〉 is the Bregman divergence induced by the convex function r∗∗.
While the convergence of w∗t to the minimum of (17) is well-known (see e.g. Yu et al. [49]), the above result also implies that a properly averaged iterate w̄t also converges to the minimum of the dual problem of (17):
Corollary 4.2. Let w̄t := ∑t τ=0 Λt,τwτ , where Λt,τ := λτ πτ /Ht and Ht := ∑t τ=0 λτ πτ
. Then, we have for any w:
(`∗∗ + r∗∗)(w̄t)− (`∗∗ + r∗∗)(w) ≤ (1− λ0)∆(w,w0) Ht + L 2 t∑ τ=0 λτΛt,τ‖w∗τ − z∗τ‖22. (21)
Assuming {z∗τ} is bounded (e.g. when `∗∗ is Lipschitz continuous), the right-hand side of (21) diminishes if λt → 0 and ∑ t λt =∞. Setting λt = 1 t+1 recovers ergodic averaging w̄t = 1 t+1 ∑t τ=0 wτ for which the right-hand side of (21) diminishes at the rate6 O(log t/t); see Appendix A.2 for details.
Thus, GCG solves problem (17) and its dual simultaneously.

heading: 4.2 BC ⊆ DA ⊆ GCG
text: We are now in a 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 a smooth approximation known as the Moreau envelope [30]:
M µr∗(w ∗) = min z∗ 1 2µ‖w ∗ − z∗‖22 + r∗(z∗), (22)
where the minimizer is (by definition) exactly Pµr∗(w ∗). It is well-known that M µr∗ is (1/µ)-smooth and (M µr∗) ∗ = r∗∗ + µ2 ‖ · ‖ 2 2 [30]. We then apply GCG to the approximate dual problem:
min w∗∈Rd
`∗(−w∗) + M µr∗(w∗), (23)
whose own Fenchel–Rockfellar dual is:[ min w∈Rd `∗∗(w) + (M µr∗) ∗(w) ] = min w∈Rd `∗∗(w) + r∗∗(w) + µ2 ‖w‖ 2 2. (24)
5GCG is usually applied to solving the primal problem (14) directly. Our choice of the dual problem here is to facilitate later comparison with dual averaging and BinaryConnect.
6The log factor can be removed by setting, for example, λt = 22+t instead.
The updates of GCG applied to the approximate problem (23) are thus:
wt := ∇M µr∗(w∗t ) = P 1/µ r∗∗ (w ∗ t /µ) (see Proposition A.2 for derivation) (25) w∗t+1 = (1− λt)w∗t + λtz∗t , where z∗t = −∇`∗∗(wt), (26)
which is exactly the updates of (regularized) dual averaging [42] for convex problems where7 r∗∗ = r and `∗∗ = `. Nesterov [31] motivated dual averaging by the natural desire of non-decreasing step sizes, whereas conventional subgradient algorithms “counter-intuitively” 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 a constant (rather than a diminishing/decreasing) step size.
Defining πt := ∏t s=1(1− λs) for t ≥ 1, π0 := 1, π−1 := (1− λ0)−1, and setting w∗t = w∗t /πt−1, we have:
wt = P 1/µ r∗∗ (πt−1w ∗ t /µ), w ∗ t+1 = w ∗ t − λtπt∇` ∗∗(wt). (27)
Let us now reparameterize
ηt := λt πt =⇒ λt = ηt1+∑tτ=1 ητ and 1πt = 1 + ∑t τ=1 ητ , (28)
for t ≥ 1. If we also allow µ = µt to change adaptively from iteration to iteration (as in dual averaging), in particular, if µt = πt−1, we obtain the familiar update:
wt = P 1/πt−1 r∗∗ (w ∗ t ), w ∗ t+1 = w ∗ t − ηt∇`∗∗(wt). (29)
For nonconvex problems, we may replace r∗∗ and `∗∗ with their nonconvex counterparts r and `, respectively. We remark that r∗∗ (resp. `∗∗) is the largest convex function that is (pointwise) majorized by r (resp. `). In particular, with r = ιQ and P 1/µ r = PQ (for any µ) we recover the BinaryConnect update (3). While the parameter µ plays no role when r is an indicator function, we emphasize that for general r we should use the quantizer P1/πt−1r , where importantly 1/πt−1 →∞ hence the quantizer converges to minimizers of r asymptotically. 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) = 12w 2, Q = {±1}, P1/µr (w) = sign(w) |w|+ 1µ +
1 µ
for |w| ≤ 1 , (30)
and they showed non-convergence of the algorithm w ← w − η∇`(P1/µr (w)), where µ is a fixed constant. If we use P1/πt−1r with some diverging 1/πt−1 instead, the resulting BinaryConnect, with diminishing ηt or ergodic averaging, would actually converge to 0 (since P 1/πt−1 r → sign).

heading: 5 ProxConnect (PC): A Generalization of BinaryConnect
text: 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 counterparts and replacing deterministic gradients with stochastic gradients (as well as the change-of-variable w∗t → w∗t ), we obtain from (29) a family of algorithms which we term ProxConnect (PC):
wt = P 1/πt−1 r (w∗t ), w ∗ t+1 = w ∗ t − ηt∇̃`(wt), (31)
where the quantizer P1/πt−1r may be designed directly by following Section 3. We have already seen in Section 4 that BC belongs to PC by choosing P1/πt−1r = PQ (in which case πt−1 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 ∇̃`):
7That is, if we set λt = 1/t and allow for time-dependent µt = t; see Xiao [Algorithm 1, 42].
Theorem 5.1. Fix any w, the iterates in (31) satisfy: t∑
τ=s
ητ [〈wτ−w, ∇̃`(wτ )〉+r(wτ )−r(w)] ≤ ∆s−1(w)−∆t(w)+ t∑
τ=s
∆τ (wτ ), (32)
where ∆τ (w) := rτ (w)− rτ (wτ+1)− 〈 w −wτ+1,w∗τ+1 〉 is the Bregman divergence induced by the (possibly nonconvex) function rτ (w) := 1πτ r(w) + 1 2‖w‖ 2 2.
The summand on the left-hand side of (32) is related to the duality gap in Yu et al. [49], which is a 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 ` and any w, the iterates in (31) satisfy:
min τ=s,...,t E[f(wτ )−f(w)] ≤ 1∑t τ=s ητ
·E [ ∆s−1(w)−∆t(w)+ ∑t τ=s ∆τ (wτ ) ] . (33)
If r is also convex, then
min τ=s,...,t E[f(wτ )−f(w)] ≤ 1∑t τ=s ητ
·E [ ∆s−1(w)+ ∑t τ=s η2τ 2 ‖∇̃`(wτ )‖ 2 2 ] , (34)
and
E [ f(w̄t)−f(w) ] ≤ 1∑t τ=s ητ ·E [ ∆s−1(w)+ ∑t τ=s η2τ 2 ‖∇̃`(wτ )‖ 2 2 ] , (35)
where wt = ∑t τ=s ητwτ∑t τ=s ητ .
The right-hand sides of (34) and (35) diminish iff ηt → 0 and ∑ t ηt =∞ (assuming boundedness of the stochastic gradient). We note some trade-off in choosing the step size ητ : both the numerator and denominator of the right-hand sides of (34) and (35) are increasing w.r.t. ητ . The same conclusion can be drawn for (33) and (32), where ∆τ also depends on ητ (through the accumulated magnitude of w∗τ+1). A detailed analysis may need to take specific properties of r or P into account [45].
ProxQuant vs ProxConnect. It is worthwhile to point out one important difference between ProxQuant and ProxConnect: Bai et al. [5] proved convergence (to some notion of stationarity) of ProxQuant for a fixed quantizer (see Bai et al. [Theorem 5.1, 5]), i.e., Pµr for a fixed µ, but their experiments relied on incrementing µ so that their quantizer approaches the projector PQ. This creates some discrepancy between theory and practice. The same comment also applies to [1]. In contrast, ProxConnect is derived from a rigorous theory that automatically justifies a diverging µ. In particular, choosing a constant step size ητ ≡ η0 would lead to 1/πt−1 ∝ t, matching the current practice that is now justifiable if r is strongly convex; see Appendix A.3.1 for details.
Connection to 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 L%ρ from Section 3; see Table 1 for a sample summary.
reverseProxConnect. In Section 2, we discussed the idea of reversing BinaryConnect. As ProxConnect generalizes BC, we also present reverseProxConnect (rPC) as a generalization of reversing BinaryConnect:
wt = P 1/πt−1 r (w∗t ), w ∗ t+1 = wt − ηt∇̃`(w∗t ), (36)
In contrast to reversing BinnaryConnect, rPC is not completely without merit: it evaluates the gradient at the continuous weights w∗t and hence is able to exploit a richer landscape of the loss. Even when stuck at a fixed discrete weight wt, rPC may still accumulate sizable updates (as long as the step size and the gradient remain sufficiently large) to allow it to eventually jump out of wt: note that the continuous weights w∗t still get updated. Finally, for constant step size η and π, we note that fixed points of rPC, when existent, satisfy:
w∗ = P1/πr (w ∗)− η∇`(w∗) ⇐⇒ w∗ = (id + η∇`)−1
( id + η [ ∂r πη ])−1 (w∗) (37)
=: B ( η,∇`, ∂rπη ) (w∗), (38)
Importance of GCG framework: Deriving PC from the GCG framework may let us transfer recent advances on GCG [7, 14, 50] to neural network quantization. Furthermore, it is the cornerstone in justifying the widely-adopted diverging smoothing parameter.

heading: 6 Experiments

heading: 6.1 Classification on CIFAR-10
text: We perform image classification on CIFAR-10 [24] using ResNet20 and ResNet56 [19], comparing BinaryConnect [11] with ProxQuant [5] and (reverse)ProxConnect using our proposed proximal operator L%ρ. For fair comparison, we set ρ = % in L % ρ as this resembles the quantizer (for binary quantization) used in the original ProxQuant algorithm. Similar to Bai et al. [5], we increase the parameter ρ (or equivalently %) linearly: ρt = (1 + t/B) ρ0. In contrast to Bai et al. [5], however, we increase ρ after every gradient step rather than after every epoch as this is more in line with our analysis. We treat ρ0 as a hyperparameter for which we conduct a small grid search. We consider binary (Q = {−1, 1}), ternary (Q = {−1, 0, 1}) and quaternary (Q = {−1,−0.3, 0.3, 1}) quantization. Details for all CIFAR-10 experiments can be found in Appendix B.1.
Fine-Tuning Pretrained Models. In this experiment, all quantization algorithms are initialized with a 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)ProxConnect we respectively picked the best ρ0 values; results for all ρ0 values can be found in Appendix B.1.7. (Reverse)ProxConnect outperforms the other two methods on all six settings.
End-To-End Training. To save computational costs, it is important that quantization algorithms also perform well when they are not initialized with pretrained full-precision model. We therefore compare the four methods for randomly initialized models; see Table 3 for the results. ProxConnect outperforms all other methods on all six tasks. Interestingly, ProxQuant and reverseProxConnect 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
quantization. We found that ProxQuant and reverseProxConnect can be quite sensitive to the choice of ρ0, whereas ProxConnect is stable in this regard; see Appendix B.1.7.

heading: 6.2 Classification on ImageNet
text: 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.

heading: 7 Conclusion
text: Capitalizing on a principled approach for designing quantizers and a surprising connection between BinaryConnect and the generalized conditional gradient (GCG) algorithm, we proposed ProxConnect as a 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 to apply ProxConnect to training other models such as 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.

Review summaries:
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.

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.

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.  The 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.  Results 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).