# Demystifying and Generalizing BinaryConnect

Tim Dockhorn
University of Waterloo
&Yaoliang Yu
University of Waterloo
&Eyyüb Sari
Huawei Noah’s Ark Lab
&Mahdi Zolnouri
Huawei Noah’s Ark Lab
&Vahid Partovi Nia
Huawei Noah’s Ark Lab
Work done during an internship at Huawei Noah’s Ark Lab. Correspondence to
<EMAIL_ADDRESS>
###### 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.

##  1 Introduction

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 [11, 37, 45, 5, 33, 29, 1] 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, 51,
32, 25, 20, 17]. 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].

BinaryConnect [BC, 11] and its many variations [37, 53, 10] 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 [11, 45, 5, 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 [5, 45, 1].

  * •

In Section 6, we verify that PC outperforms BC and ProxQuant [5] on CIFAR-10
for both fine-tuning pretrained models as 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
$\ell({\mathbf{w}})=\mathbf{E}\ell({\mathbf{w}},\bm{\xi})$, where $\bm{\xi}$
represents random sampling. For instance,
$\ell({\mathbf{w}})=\frac{1}{n}\sum_{i=1}^{n}\ell_{i}({\mathbf{w}})$ where
$\bm{\xi}$ is uniform over $n$ training samples (or minibatches thereof),
${\mathbf{w}}$ are the weights of a neural network and $\ell_{i}$ may be the
cross-entropy loss (of the $i$-th training sample). We denote a sample
(sub)gradient of $\ell$ at ${\mathbf{w}}$ and $\bm{\xi}$ as
$\widetilde{\nabla}\ell({\mathbf{w}})=\nabla\ell({\mathbf{w}},\bm{\xi})$ so
that
$\mathbf{E}\widetilde{\nabla}\ell({\mathbf{w}})=\nabla\ell({\mathbf{w}})$.
Throughout, we use the starred notation ${\mathbf{w}}^{*}$ for continuous
weights and reserve ${\mathbf{w}}$ for (semi)discrete ones.

We are interested in solving the following (nonconvex) problem:

$\displaystyle\min_{{\mathbf{w}}\in Q}~{}\ell({\mathbf{w}}),$ (1)

where $Q\subseteq\mathbb{R}^{d}$ 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=\\{\pm 1\\}^{d}$. Importantly,
our goal is to compete against the non-quantized, continuous weights network
(i.e. $Q=\mathbb{R}^{d}$). 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 ${\mathbf{w}}\in 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
$\ell$ could come into aid. If $\ell$ 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 [36, 15].

BinaryConnect (BC). Courbariaux et al. [11] considered binary networks where
$Q=\\{\pm 1\\}^{d}$ and proposed the BinaryConnect algorithm:

$\displaystyle{\mathbf{w}}_{t+1}^{*}$
$\displaystyle={\mathbf{w}}_{t}^{*}-\eta_{t}\widetilde{\nabla}\ell({\mathsf{P}}({\mathbf{w}}_{t}^{*})),$
(2)

where ${\mathsf{P}}$ is a projector that quantizes the continuous weights
${\mathbf{w}}_{t}^{*}$ either deterministically (by taking the sign) or
stochastically. Note that the (sample) gradient is evaluated at the quantized
weights ${\mathbf{w}}_{t}\coloneqq{\mathsf{P}}({\mathbf{w}}_{t}^{*})$, while
its continuous output, after scaled by the step size $\eta_{t}$, is added to
the continuous weights ${\mathbf{w}}_{t}^{*}$. For later comparison, it is
useful to break the BC update into the following two pieces:

$\displaystyle{\mathbf{w}}_{t}={\mathsf{P}}({\mathbf{w}}_{t}^{*}),\qquad{\mathbf{w}}_{t+1}^{*}={\mathbf{w}}_{t}^{*}-\eta_{t}\widetilde{\nabla}\ell({\mathbf{w}}_{t}).$
(3)

Other choices of ${\mathsf{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):

$\displaystyle{\mathbf{w}}_{t+1}$
$\displaystyle={\mathsf{P}}({\mathbf{w}}_{t}-\eta_{t}\widetilde{\nabla}\ell({\mathbf{w}}_{t})),$
(4)

which can be similarly decomposed into:

$\displaystyle{\mathbf{w}}_{t}={\mathsf{P}}({\mathbf{w}}_{t}^{*}),\qquad{\mathbf{w}}_{t+1}^{*}={\mathbf{w}}_{t}-\eta_{t}\widetilde{\nabla}\ell({\mathbf{w}}_{t}).$
(5)

Thus, the only high-level difference between BC and PQ is that the former
updates the continuous weights ${\mathbf{w}}_{t}^{*}$ while the latter updates
the quantized weights ${\mathbf{w}}_{t}$. This seemingly minor difference
turns out to cause drastically different behaviors of the two algorithms. For
example, choosing ${\mathsf{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:

$\displaystyle{\mathbf{w}}_{t}={\mathsf{P}}({\mathbf{w}}_{t}^{*}),\qquad{\mathbf{w}}_{t+1}^{*}={\mathbf{w}}_{t}-\eta_{t}\widetilde{\nabla}\ell({\mathbf{w}}_{t}^{*}),$
(6)

which amounts to switching the continuous and quantized weights in the BC
update. Similar to PQ, the choice of ${\mathsf{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:

$\displaystyle{\mathbf{w}}_{t}={\mathsf{P}}({\mathbf{w}}_{t}^{*}),\qquad{\mathbf{w}}_{t+1}^{*}$
$\displaystyle={\mathbf{w}}_{t}^{*}-\eta_{t}\widetilde{\nabla}\ell({\mathbf{w}}_{t}^{*}),$
(7)

where we simply train the continuous network as usual and then quantize at the
end. Note that the quantized weights ${\mathbf{w}}_{t}$ do not affect the
update of the continuous weights ${\mathbf{w}}_{t}^{*}$.

##  3 What Makes a Good Quantizer?

As we have seen in Section 2, the choice of the quantizer ${\mathsf{P}}$ turns
out to be a crucial element for solving (1). Indeed, if
${\mathsf{P}}={\mathsf{P}}_{Q}$ is the projector onto the discrete
quantization set $Q$, then BC (and ProxQuant) only evaluate the gradient of
$\ell$ 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, 45, 5, 33]. 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
${\mathsf{P}}_{\mathsf{r}}^{\mu}\colon\mathbb{R}^{d}\rightrightarrows\mathbb{R}^{d}$
of a (closed) function $\mathsf{r}$:

$\displaystyle{\mathsf{P}}_{\mathsf{r}}^{\mu}({\mathbf{w}}^{*})=\operatorname*{arg\,min}_{{\mathbf{w}}}~{}\tfrac{1}{2\mu}\|{\mathbf{w}}-{\mathbf{w}}^{*}\|_{2}^{2}+\mathsf{r}({\mathbf{w}}),$
(8)

where $\mu>0$ is a smoothing parameter. The proximal map is well-defined as
long as the function $\mathsf{r}$ is lower bounded by a quadratic function, in
particular, when $\mathsf{r}$ is bounded from below. If $\mathsf{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 $\rightrightarrows$). If
$\mathsf{r}=\iota_{Q}$ is the indicator function (see (15) below), then
${\mathsf{P}}_{\mathsf{r}}^{\mu}$ reduces to the familiar projector
${\mathsf{P}}_{Q}$ (for any $\mu$). Remarkably, a complete characterization of
such maps on the real line is available:

######  Theorem 3.1 ([Proposition 3, 48]).

A (possibly multi-valued) map
${\mathsf{P}}\colon\mathbb{R}\rightrightarrows\mathbb{R}$ is a proximal map
(of some function $\mathsf{r}$) iff it is (nonempty) compact-valued, monotone
and has a closed graph. The underlying function $\mathsf{r}$ is unique (up to
addition of constants) iff ${\mathsf{P}}$ is convex-valued, while $\mathsf{r}$
is convex iff ${\mathsf{P}}$ is nonexpansive (i.e. $1$-Lipschitz continuous).

The sufficient and necessary conditions of Theorem 3.1 allow one to design
proximal maps ${\mathsf{P}}$ directly, without needing to know the underlying
function $\mathsf{r}$ at all (even though it is possible to integrate a
version of $\mathsf{r}$ from ${\mathsf{P}}$). The point is that, as far as
quantization algorithms are concerned, having ${\mathsf{P}}$ is enough, and
hence one is excused from the tedious calculations in deriving ${\mathsf{P}}$
from $\mathsf{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 ${\mathsf{P}}=(\nabla\Phi)^{-1}$ for some mirror map $\Phi$.
Since $\Phi$ is taken to be strictly convex in Ajanthan et al. [1], it is easy
to verify that ${\mathsf{P}}$ satisfies all conditions of Theorem 3.1.111The
above reasoning hinges on $\Phi$ being univariate. More generally, if a
multivariate mirror map $\Phi$ is 1-strongly convex (as is typical in Mirror
Descent), then it follows from Moreau [Corollaire 10.c, 30] that
${\mathsf{P}}=(\nabla\Phi)^{-1}$, being a nonexpansion, is again a proximal
map (of some convex function).

The next result allows us to employ _stochastic_ quantizers, where in each
iteration we randomly choose one of ${\mathsf{P}}_{i}$ to quantize the
weights222This form of stochasticity still leads to _determinisitc networks_ ,
and is therefore conceptually different from _probabilistic_ (quantized)
networks [35, 39].. We may also apply different quantizers to different layers
of a neural network. theoremproxmap Let
${\mathsf{P}}_{i}:\mathbb{R}^{d}\rightrightarrows\mathbb{R}^{d},i=[k]$, be
proximal maps. Then, the averaged map

$\displaystyle\textstyle{\mathsf{P}}\coloneqq\sum_{i=1}^{k}\alpha_{i}{\mathsf{P}}_{i},\qquad\mbox{
where }\alpha_{i}\geq 0,~{}~{}\sum_{i=1}^{k}\alpha_{i}=1,$ (9)

is also a proximal map. Similarly, the product map

$\displaystyle\textstyle{\mathsf{P}}\coloneqq{\mathsf{P}}_{1}\times{\mathsf{P}}_{2}\times\cdots\times{\mathsf{P}}_{k},~{}~{}{\mathbf{w}}^{*}=({\mathbf{w}}_{1}^{*},\ldots,{\mathbf{w}}_{k}^{*})\mapsto\big{(}{\mathsf{P}}_{1}({\mathbf{w}}_{1}^{*}),\ldots,{\mathsf{P}}_{k}({\mathbf{w}}_{k}^{*})\big{)}$
(10)

is a proximal map (from $\mathbb{R}^{dk}$ to $\mathbb{R}^{dk}$). (The proof of
Footnote 2 and all other omitted proofs can be found in Appendix A.)

######  Example 3.2.

Let $Q$ be a quantization set (e.g. $Q=\\{-1,0,1\\}$). Clearly, the identity
map $\mathsf{id}$ and the projector ${\mathsf{P}}_{Q}$ are proximal maps.
Therefore, their convex combination
${\mathsf{P}}^{\mu}=\tfrac{\mathsf{id}+\mu{\mathsf{P}}_{Q}}{1+\mu},\mu\geq 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
${\mathsf{P}}^{\mu}\to{\mathsf{P}}_{Q}$ when $\mu$ 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
$\mathsf{r}$, or the (possibly larger set of) fixed points of
${\mathsf{P}}^{\mu}$, approach $Q$. We give one such construction by
exploiting Theorem 3.1 and Footnote 2.

###  3.1 General Piecewise Linear Quantizers

Let $Q_{j}=\\{q_{j,k}\\}_{k=1}^{b_{j}}$ (with $q_{j,1}\leq\cdots\leq
q_{j,b_{j}}$) be the quantization set for the $j$-th weight group333In this
section, time subscripts are not needed. Instead, we use subscripts to
indicate weight groups. ${\mathbf{w}}_{j}^{*}\in\mathbb{R}^{d_{j}}$. Let
$p_{j,k+1}\coloneqq\tfrac{q_{j,k}+q_{j,k+1}}{2}$, $k\in[b_{j}-1]$, be the
middle points. We introduce two parameters $\rho,\varrho\geq 0$ and define

horizontal shifts: $\displaystyle q_{j,k}^{-}\coloneqq
p_{j,k}\vee(q_{j,k}-\rho),~{}~{}$ $\displaystyle q_{j,k}^{+}\coloneqq
p_{j,k+1}\wedge(q_{j,k}+\rho),$ (11) vertical shifts: $\displaystyle
p_{j,k+1}^{-}\coloneqq q_{j,k}\vee(p_{j,k+1}-\varrho),~{}~{}$ $\displaystyle
p_{j,k+1}^{+}\coloneqq q_{j,k+1}\wedge(p_{j,k+1}+\varrho),$ (12)

with $q_{j,1}^{-}=q_{j,1}$ and $q_{j,b_{j}}^{+}=q_{j,b_{j}}$. Then, we define
${\mathsf{L}}^{\varrho}_{\rho}$ as the piece-wise linear map (that simply
connects the points by straight lines):

$\displaystyle{\mathsf{L}}^{\varrho}_{\rho}(w^{*})\coloneqq\begin{cases}q_{j,k},&\mbox{
if }q_{j,k}^{-}\leq w^{*}\leq q_{j,k}^{+}\\\
q_{j,k}+(w^{*}-q_{j,k}^{+})\tfrac{p_{j,k+1}^{-}-q_{j,k}}{p_{j,k+1}-q_{j,k}^{+}},&\mbox{
if }q_{j,k}^{+}\leq w^{*}<p_{j,k+1}\\\
p_{j,k+1}^{+}+(w^{*}-p_{j,k+1})\tfrac{q_{j,k+1}-p_{j,k+1}^{+}}{q_{j,k+1}^{-}-p_{j,k+1}},&\mbox{
if }p_{j,k+1}<w^{*}\leq q_{j,k+1}^{-},\end{cases}$ (13)

for all $w^{*}\in{\mathbf{w}}_{j}^{*}$. At the middle points,
${\mathsf{L}}^{\varrho}_{\rho}(p_{j,k+1})$ may take any value within the two
limits. Following the commonly used weight clipping in BC [11], we may set
${\mathsf{L}}^{\varrho}_{\rho}(w^{*})=q_{j,1}$ for $w^{*}<q_{j,1}$ and
${\mathsf{L}}^{\varrho}_{\rho}(w^{*})=q_{j,b_{j}}$ for $w^{*}>q_{j,b_{j}}$,
however, other choices may also work well. The proximal map
${\mathsf{L}}^{\varrho}_{\rho}$ of an example ternary component is visualized
in Figure 1 for different choices of $\rho$ and $\varrho$.

$-1$$1$$-1$$1$$p_{2}^{-}$$p_{2}^{+}$$p_{3}^{-}$$p_{3}^{+}$$w^{*}$${\mathsf{L}}^{\varrho}_{\rho}(w^{*})$
(a) $\rho=0,\varrho=0.2$.

$-1$$1$$-1$$1$$q_{1}^{+}$$p_{2}^{-}$$p_{2}^{+}$$q_{2}^{-}$$q_{2}^{+}$$p_{3}^{-}$$p_{3}^{+}$$q_{3}^{-}$$w^{*}$${\mathsf{L}}^{\varrho}_{\rho}(w^{*})$
(b) $\rho=\varrho=0.2$.

$-1$$1$$-1$$1$$q_{1}^{+}$$q_{2}^{-}$$q_{2}^{+}$$q_{3}^{-}$$w^{*}$${\mathsf{L}}^{\varrho}_{\rho}(w^{*})$
(c) $\rho=0.2,\varrho=0$.

Figure 1: Different instantiations of the proximal map
${\mathsf{L}}^{\varrho}_{\rho}$ in (13) for $Q=\\{-1,0,1\\}$.

The (horizontal) parameter $\rho$ controls the discretization vicinity within
which a continuous weight will be pulled _exactly_ into the discrete set
$Q_{j}$, while the (vertical) parameter $\varrho$ controls the slope (i.e.
expansiveness) of each piece. It follows at once from Theorem 3.1 that
${\mathsf{L}}^{\varrho}_{\rho}$ is indeed a proximal map. In particular,
setting $\rho=0$ (hence continuous weights are only discretized in the limit)
and $\varrho=\tfrac{\mu}{2(1+\mu)}$ we recover Example 3.2 (assuming w.l.o.g.
that $q_{j,k+1}-q_{j,k}\equiv 1$). On the other hand, setting $\rho=\varrho$
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 $Q_{j}$ [5]. Of
course, setting $\rho=\varrho=0$ yields the identity map and allows us to skip
quantizing certain weights (as is common practice), while letting
$\rho,\varrho\to\infty$ recovers the projector ${\mathsf{P}}_{Q_{j}}$.

Needless to say, we may adapt the quantization set $Q_{j}$ and the parameters
$\varrho$ and $\rho$ for different weight groups, creating a multitude of
quantization schemes. By Footnote 2, the overall operator remains a proximal
map.

##  4 Demystifying BinaryConnect (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 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.

###  4.1 Generalized Conditional Gradient is Primal-Dual

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:

$\displaystyle\min_{{\mathbf{w}}\in\mathbb{R}^{d}}~{}f({\mathbf{w}})\coloneqq\ell({\mathbf{w}})+\mathsf{r}({\mathbf{w}}),$
(14)

where $\mathsf{r}$ is a general (nonconvex) regularizer. Setting $\mathsf{r}$
to the indicator function of $Q$, i.e.,

$\displaystyle\mathsf{r}({\mathbf{w}})=\iota_{Q}({\mathbf{w}})=\begin{cases}0,&\mbox{
if }{\mathbf{w}}\in Q\\\ \infty,&\mbox{ otherwise }\end{cases},$ (15)

reduces (14) to the original problem (1). As we will see, incorporating an
arbitrary $\mathsf{r}$ does not add any complication but will allow us to
immediately generalize BC.

Introducing the Fenchel conjugate function $\ell^{*}$ (resp. $\mathsf{r}^{*}$)
of $\ell$ (resp. $\mathsf{r}$):

$\displaystyle\textstyle\ell^{*}({\mathbf{w}}^{*})\coloneqq\sup_{{\mathbf{w}}}~{}\left\langle{\mathbf{w}},{\mathbf{w}}^{*}\right\rangle-\ell({\mathbf{w}}),$
(16)

which is always (closed) convex even when $\ell$ itself is nonconvex, we state
the Fenchel–Rockafellar dual problem [38]:

$\displaystyle\min_{{\mathbf{w}}^{*}\in\mathbb{R}^{d}}~{}\ell^{*}(-{\mathbf{w}}^{*})+\mathsf{r}^{*}({\mathbf{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 problem444GCG 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. (17): Given
${\mathbf{w}}_{t}^{*}$, we linearize the function $\mathsf{r}^{*}$ and solve

$\displaystyle{\mathbf{z}}_{t}^{*}=\left[\operatorname*{arg\,min}_{{\mathbf{w}}^{*}}~{}\ell^{*}(-{\mathbf{w}}^{*})+\left\langle{\mathbf{w}}^{*},{\mathbf{w}}_{t}\right\rangle\right]=-\nabla\ell^{**}({\mathbf{w}}_{t}),~{}~{}{\mathbf{w}}_{t}\coloneqq\nabla\mathsf{r}^{*}({\mathbf{w}}_{t}^{*}),$
(18)

where we used the fact that $(\nabla\ell^{*})^{-1}=\nabla\ell^{**}$. Then, we
take the convex combination

$\displaystyle{\mathbf{w}}_{t+1}^{*}=(1-\lambda_{t}){\mathbf{w}}_{t}^{*}+\lambda_{t}{\mathbf{z}}_{t}^{*},~{}~{}\mbox{
where }\lambda_{t}\in[0,1].$ (19)

The following theorem extends Bach [Proposition 4.2, 4] and Yu [Theorem 4.6,
47] to any $\lambda_{t}$: theoremgcg Suppose $\mathsf{r}^{*}$ is $L$-smooth
(i.e. $\nabla\mathsf{r}^{*}$ is $L$-Lipschitz continuous), then for any
${\mathbf{w}}$:

$\displaystyle\sum_{\tau=0}^{t}\tfrac{\lambda_{\tau}}{\pi_{\tau}}[(\ell^{**}+\mathsf{r}^{**})({\mathbf{w}}_{\tau})-(\ell^{**}+\mathsf{r}^{**})({\mathbf{w}})]\leq(1-\lambda_{0})\Delta({\mathbf{w}},{\mathbf{w}}_{0})+\sum_{\tau=0}^{t}\tfrac{\lambda_{\tau}^{2}}{2\pi_{\tau}}L\|{\mathbf{w}}_{\tau}^{*}-{\mathbf{z}}_{\tau}^{*}\|_{2}^{2},$
(20)

where ${\mathbf{w}}_{t}\coloneqq\nabla\mathsf{r}^{*}({\mathbf{w}}_{t}^{*})$,
$\pi_{t}\coloneqq\prod_{\tau=1}^{t}(1-\lambda_{\tau})$, and $\pi_{0}\coloneqq
1$.
$\Delta({\mathbf{w}},{\mathbf{w}}_{t})\coloneqq\mathsf{r}^{**}({\mathbf{w}})-\mathsf{r}^{**}({\mathbf{w}}_{t})-\left\langle{\mathbf{w}}-{\mathbf{w}}_{t},{\mathbf{w}}_{t}^{*}\right\rangle$
is the Bregman divergence induced by the convex function $\mathsf{r}^{**}$.
While the convergence of ${\mathbf{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 $\bar{\mathbf{w}}_{t}$ also converges to the minimum
of the dual problem of (17): corcorfourtwo Let
$\bar{\mathbf{w}}_{t}\coloneqq\sum_{\tau=0}^{t}\Lambda_{t,\tau}{\mathbf{w}}_{\tau}$,
where $\Lambda_{t,\tau}\coloneqq\tfrac{\lambda_{\tau}}{\pi_{\tau}}/H_{t}$ and
$H_{t}\coloneqq\sum_{\tau=0}^{t}\tfrac{\lambda_{\tau}}{\pi_{\tau}}$. Then, we
have for any ${\mathbf{w}}$:

$\displaystyle(\ell^{**}+\mathsf{r}^{**})(\bar{\mathbf{w}}_{t})-(\ell^{**}+\mathsf{r}^{**})({\mathbf{w}})\leq\frac{(1-\lambda_{0})\Delta({\mathbf{w}},{\mathbf{w}}_{0})}{H_{t}}+\frac{L}{2}\sum_{\tau=0}^{t}\lambda_{\tau}\Lambda_{t,\tau}\|{\mathbf{w}}_{\tau}^{*}-{\mathbf{z}}_{\tau}^{*}\|_{2}^{2}.$
(21)

Assuming $\\{{\mathbf{z}}_{\tau}^{*}\\}$ is bounded (e.g. when $\ell^{**}$ is
Lipschitz continuous), the right-hand side of (21) diminishes if
$\lambda_{t}\to 0$ and $\sum_{t}\lambda_{t}=\infty$. Setting
$\lambda_{t}=\tfrac{1}{t+1}$ recovers ergodic averaging
$\bar{\mathbf{w}}_{t}=\tfrac{1}{t+1}\sum_{\tau=0}^{t}{\mathbf{w}}_{\tau}$ for
which the right-hand side of (21) diminishes at the rate555The log factor can
be removed by setting, for example, $\lambda_{t}=\tfrac{2}{2+t}$ instead.
$O(\log t/t)$; see Section A.2 for details.

Thus, GCG solves problem (17) and its dual simultaneously.

###  4.2 BC $\subseteq$ DA $\subseteq$ GCG

We are now in a position to reveal the relationships among BinaryConnect (BC),
(regularized) dual averaging (DA) and the generalized conditional gradient
(GCG). Since Section 4.1 requires $\mathsf{r}^{*}$ to be $L$-smooth, in the
event that it is not we resort to a smooth approximation known as the Moreau
envelope [30]:

$\displaystyle\mathscr{M}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}^{*})=\min_{{\mathbf{z}}^{*}}~{}\tfrac{1}{2\mu}\|{\mathbf{w}}^{*}-{\mathbf{z}}^{*}\|_{2}^{2}+\mathsf{r}^{*}({\mathbf{z}}^{*}),$
(22)

where the minimizer is (by definition) exactly
${\mathsf{P}}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}^{*})$. It is well-known that
$\mathscr{M}_{\mathsf{r}^{*}}^{\mu}$ is $(1/\mu)$-smooth and
$(\mathscr{M}_{\mathsf{r}^{*}}^{\mu})^{*}=\mathsf{r}^{**}+\tfrac{\mu}{2}\|\cdot\|_{2}^{2}$
[30]. We then apply GCG to the approximate dual problem:

$\displaystyle\min_{{\mathbf{w}}^{*}\in\mathbb{R}^{d}}~{}\ell^{*}(-{\mathbf{w}}^{*})+\mathscr{M}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}^{*}),$
(23)

whose own Fenchel–Rockfellar dual is:

$\displaystyle\left[\min_{{\mathbf{w}}\in\mathbb{R}^{d}}~{}\ell^{**}({\mathbf{w}})+(\mathscr{M}_{\mathsf{r}^{*}}^{\mu})^{*}({\mathbf{w}})\right]=\min_{{\mathbf{w}}\in\mathbb{R}^{d}}~{}\ell^{**}({\mathbf{w}})+\mathsf{r}^{**}({\mathbf{w}})+\tfrac{\mu}{2}\|{\mathbf{w}}\|_{2}^{2}.$
(24)

The updates of GCG applied to the approximate problem (23) are thus:

$\displaystyle{\mathbf{w}}_{t}$
$\displaystyle\coloneqq\nabla\mathscr{M}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}_{t}^{*})={\mathsf{P}}_{\mathsf{r}^{**}}^{1/\mu}({\mathbf{w}}_{t}^{*}/\mu)\quad(\text{see~{}\lx@cref{creftypecap~refnum}{prop:gcg-
dual} for derivation})$ (25) $\displaystyle{\mathbf{w}}_{t+1}^{*}$
$\displaystyle=(1-\lambda_{t}){\mathbf{w}}_{t}^{*}+\lambda_{t}{\mathbf{z}}_{t}^{*},~{}~{}\mbox{
where }~{}~{}{\mathbf{z}}_{t}^{*}=-\nabla\ell^{**}({\mathbf{w}}_{t}),$ (26)

which is exactly the updates of (regularized) dual averaging [42] for convex
problems where666That is, if we set $\lambda_{t}=1/t$ and allow for time-
dependent $\mu_{t}=t$; see Xiao [Algorithm 1, 42].
$\mathsf{r}^{**}=\mathsf{r}$ and $\ell^{**}=\ell$. 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 $\pi_{t}\coloneqq\prod_{s=1}^{t}(1-\lambda_{s})$ for $t\geq 1$,
$\pi_{0}\coloneqq 1$, $\pi_{-1}\coloneqq(1-\lambda_{0})^{-1}$, and setting
$\mathsf{w}_{t}^{*}={\mathbf{w}}_{t}^{*}/\pi_{t-1}$, we have:

$\displaystyle{\mathbf{w}}_{t}={\mathsf{P}}_{\mathsf{r}^{**}}^{1/\mu}(\pi_{t-1}\mathsf{w}_{t}^{*}/\mu),\qquad\mathsf{w}_{t+1}^{*}=\mathsf{w}_{t}^{*}-\tfrac{\lambda_{t}}{\pi_{t}}\nabla\ell^{**}({\mathbf{w}}_{t}).$
(27)

Let us now reparameterize

$\displaystyle\textstyle\eta_{t}\coloneqq\frac{\lambda_{t}}{\pi_{t}}\implies\lambda_{t}=\frac{\eta_{t}}{1+\sum_{\tau=1}^{t}\eta_{\tau}}\mbox{
and }\frac{1}{\pi_{t}}=1+\sum_{\tau=1}^{t}\eta_{\tau},$ (28)

for $t\geq 1$. If we also allow $\mu=\mu_{t}$ to change adaptively from
iteration to iteration (as in dual averaging), in particular, if
$\mu_{t}=\pi_{t-1}$, we obtain the familiar update:

$\displaystyle{\mathbf{w}}_{t}={\mathsf{P}}_{\mathsf{r}^{**}}^{1/\pi_{t-1}}(\mathsf{w}_{t}^{*}),\qquad\mathsf{w}_{t+1}^{*}=\mathsf{w}_{t}^{*}-\eta_{t}\nabla\ell^{**}({\mathbf{w}}_{t}).$
(29)

For nonconvex problems, we may replace $\mathsf{r}^{**}$ and $\ell^{**}$ with
their nonconvex counterparts $\mathsf{r}$ and $\ell$, respectively. We remark
that $\mathsf{r}^{**}$ (resp. $\ell^{**}$) is the largest convex function that
is (pointwise) majorized by $\mathsf{r}$ (resp. $\ell$). In particular, with
$\mathsf{r}=\iota_{Q}$ and
${\mathsf{P}}_{\mathsf{r}}^{1/\mu}={\mathsf{P}}_{Q}$ (for any $\mu$) we
recover the BinaryConnect update (3). While the parameter $\mu$ plays no role
when $\mathsf{r}$ is an indicator function, we emphasize that for general
$\mathsf{r}$ we should use the quantizer
${\mathsf{P}}_{\mathsf{r}}^{1/\pi_{t-1}}$, where importantly
$1/\pi_{t-1}\to\infty$ hence the quantizer converges to minimizers of
$\mathsf{r}$ asymptotically. Neglecting this crucial detail may lead to
suboptimality as is demonstrated in the following example:

######  Example 4.1.

Bai et al. [5] constructed the following intriguing example:

$\displaystyle\ell(w)=\tfrac{1}{2}w^{2},~{}~{}Q=\\{\pm
1\\},~{}~{}{\mathsf{P}}_{\mathsf{r}}^{1/\mu}(w)=\operatorname{sign}(w)\tfrac{\epsilon|w|+\tfrac{1}{\mu}}{\epsilon+\tfrac{1}{\mu}}\mbox{
for $|w|\leq 1$ },$ (30)

and they showed non-convergence of the algorithm $w\leftarrow
w-\eta\nabla\ell({\mathsf{P}}_{\mathsf{r}}^{1/\mu}(w)),$ where $\mu$ is a
fixed constant. If we use ${\mathsf{P}}^{1/\pi_{t-1}}_{\mathsf{r}}$ with some
diverging $1/\pi_{t-1}$ instead, the resulting BinaryConnect, with diminishing
$\eta_{t}$ or ergodic averaging, would actually converge to 0 (since
${\mathsf{P}}^{1/\pi_{t-1}}_{\mathsf{r}}\to\operatorname{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, $\ell^{**}$ and $\mathsf{r}^{**}$,
with their nonconvex counterparts and replacing deterministic gradients with
stochastic gradients (as well as the change-of-variable
$\mathsf{w}_{t}^{*}\to{\mathbf{w}}_{t}^{*}$), we obtain from (29) a _family_
of algorithms which we term ProxConnect (PC):

$\displaystyle\textstyle{\mathbf{w}}_{t}={\mathsf{P}}_{\mathsf{r}}^{1/\pi_{t-1}}({\mathbf{w}}_{t}^{*}),\quad{\mathbf{w}}_{t+1}^{*}={\mathbf{w}}_{t}^{*}-\eta_{t}\widetilde{\nabla}\ell({\mathbf{w}}_{t}),$
(31)

where the quantizer ${\mathsf{P}}_{\mathsf{r}}^{1/\pi_{t-1}}$ may be designed
directly by following Section 3. We have already seen in Section 4 that BC
belongs to PC by choosing
${\mathsf{P}}_{\mathsf{r}}^{1/\pi_{t-1}}={\mathsf{P}}_{Q}$ (in which case
$\pi_{t-1}$ plays no role).

The analysis in Section 4, initially tailored to convex functions, immediately
generalizes to the nonconvex algorithm PC (for nonconvex $\ell$, nonconvex
$\mathsf{r}$, and stochastic gradients $\widetilde{\nabla}\ell$): theorempc
Fix any ${\mathbf{w}}$, the iterates in (31) satisfy:

$\displaystyle\sum_{\tau=s}^{t}\eta_{\tau}[\langle{\mathbf{w}}_{\tau}\\!-\\!{\mathbf{w}},\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\rangle\\!+\\!\mathsf{r}({\mathbf{w}}_{\tau})\\!-\\!\mathsf{r}({\mathbf{w}})]\leq\Delta_{s-1}({\mathbf{w}})\\!-\\!\Delta_{t}({\mathbf{w}})\\!+\\!\sum_{\tau=s}^{t}\Delta_{\tau}({\mathbf{w}}_{\tau}),$
(32)

where
$\Delta_{\tau}({\mathbf{w}})\coloneqq\mathsf{r}_{\tau}({\mathbf{w}})-\mathsf{r}_{\tau}({\mathbf{w}}_{\tau+1})-\left\langle{\mathbf{w}}-{\mathbf{w}}_{\tau+1},{\mathbf{w}}_{\tau+1}^{*}\right\rangle$
is the Bregman divergence induced by the (possibly nonconvex) function
$\mathsf{r}_{\tau}({\mathbf{w}})\coloneqq\tfrac{1}{\pi_{\tau}}\mathsf{r}({\mathbf{w}})+\tfrac{1}{2}\|{\mathbf{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: corcorpc For convex $\ell$ and any ${\mathbf{w}}$, the iterates in
(31) satisfy:

$\displaystyle\\!\\!\min_{\tau=s,\ldots,t}~{}\mathbf{E}[f({\mathbf{w}}_{\tau})\\!-\\!f({\mathbf{w}})]\leq\tfrac{1}{\sum_{\tau=s}^{t}\eta_{\tau}}\cdot\mathbf{E}\big{[}\Delta_{s-1}({\mathbf{w}})\\!-\\!\Delta_{t}({\mathbf{w}})\\!+\\!\sum\nolimits_{\tau=s}^{t}\Delta_{\tau}({\mathbf{w}}_{\tau})\big{]}.$
(33)

If $\mathsf{r}$ is also convex, then

$\displaystyle\min_{\tau=s,\ldots,t}~{}\mathbf{E}[f({\mathbf{w}}_{\tau})\\!-\\!f({\mathbf{w}})]\leq\tfrac{1}{\sum_{\tau=s}^{t}\eta_{\tau}}\cdot\mathbf{E}\big{[}\Delta_{s-1}({\mathbf{w}})\\!+\\!\sum\nolimits_{\tau=s}^{t}\tfrac{\eta_{\tau}^{2}}{2}\|\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\|_{2}^{2}\big{]},$
(34)

and

$\displaystyle\mathbf{E}\big{[}f(\bar{\mathbf{w}}_{t})\\!-\\!f({\mathbf{w}})\big{]}\leq\tfrac{1}{\sum_{\tau=s}^{t}\eta_{\tau}}\cdot\mathbf{E}\big{[}\Delta_{s-1}({\mathbf{w}})\\!+\\!\sum\nolimits_{\tau=s}^{t}\tfrac{\eta_{\tau}^{2}}{2}\|\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\|_{2}^{2}\big{]},$
(35)

where
${\mathbf{w}}_{t}=\tfrac{\sum_{\tau=s}^{t}\eta_{\tau}{\mathbf{w}}_{\tau}}{\sum_{\tau=s}^{t}\eta_{\tau}}$.
The right-hand sides of (34) and (35) diminish iff $\eta_{t}\to 0$ and
$\sum_{t}\eta_{t}=\infty$ (assuming boundedness of the stochastic gradient).
We note some trade-off in choosing the step size $\eta_{\tau}$: both the
numerator and denominator of the right-hand sides of (34) and (35) are
increasing w.r.t. $\eta_{\tau}$. The same conclusion can be drawn for (33) and
(32), where $\Delta_{\tau}$ also depends on $\eta_{\tau}$ (through the
accumulated magnitude of ${\mathbf{w}}_{\tau+1}^{*}$). A detailed analysis may
need to take specific properties of $\mathsf{r}$ or ${\mathsf{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.,
${\mathsf{P}}_{\mathsf{r}}^{\mu}$ for a fixed $\mu$, but their experiments
relied on incrementing $\mu$ so that their quantizer approaches the projector
${\mathsf{P}}_{Q}$. 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 $\mu$. In
particular, choosing a constant step size $\eta_{\tau}\equiv\eta_{0}$ would
lead to $1/\pi_{t-1}\propto t$, matching the current practice that is now
justifiable if $\mathsf{r}$ is strongly convex; see Section 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
${\mathsf{L}}^{\varrho}_{\rho}$ from Section 3; see Table 1 for a sample
summary.

Table 1: A sample summary of existing quantization algorithms. The PC column indicates if the method is a special case of our proposed ProxConnect algorithm. The ${\mathsf{L}}^{\varrho}_{\rho}$-column indicates if the method uses a quantizer which is a special case of our general quantizer ${\mathsf{L}}^{\varrho}_{\rho}$ introduced in Section 3. If so, the $\rho,\varrho$-column states how $\rho$ and $\varrho$ were chosen (in practice): increasing $\mathrel{\text{\rotatebox[origin={c}]{45.0}{$\vrule height=0.0pt,width=0.0pt\shortrightarrow$}}}$, fixed to $0$, or fixed to $\infty$. Other than ProxQuant-Ternary, all methods can compute their quantizers in a single neural network pass. †: TrainedTernary methods might use a quantizer different than ${\mathsf{L}}^{\varrho}_{\rho}$ to improve performance. Method | PC | One-pass | Learnable parameters | ${\mathsf{L}}^{\varrho}_{\rho}$ | $\rho,\varrho$
---|---|---|---|---|---
ProxQuant-Binary-$L_{1}$ [5] | ✗ | ✓ | ✗ | ✓ |  $\mathrel{\text{\rotatebox[origin={c}]{45.0}{$\vrule height=0.0pt,width=0.0pt\shortrightarrow$}}}$, $\mathrel{\text{\rotatebox[origin={c}]{45.0}{$\vrule height=0.0pt,width=0.0pt\shortrightarrow$}}}$
ProxQuant-Ternary [5] | ✗ | ✗ | ✗ | ✗ | -
BinaryConnect [11] | ✓ | ✓ | ✗ | ✓ |  $\infty$,$\infty$
BinaryRelax [45] | ✓ | ✓ | ✗ | ✓ | $0,\mathrel{\text{\rotatebox[origin={c}]{45.0}{$\vrule height=0.0pt,width=0.0pt\shortrightarrow$}}}$
BinaryWeight [37] | ✓ | ✓ | ✓ | ✗ | -
MirrorDescentView [1] | ✓ | ✓ | ✗ | ✗ | -
TrainedTernary† [53] | ✓ | ✓ | ✓ | ✓ |  $\infty$,$\infty$
TernaryWeight [26] | ✓ | ✓ | ✓ | ✗ | -
ProxConnect (ours) | - | ✓ | ✓ | ✓ |  $\mathrel{\text{\rotatebox[origin={c}]{45.0}{$\vrule height=0.0pt,width=0.0pt\shortrightarrow$}}}$,$\mathrel{\text{\rotatebox[origin={c}]{45.0}{$\vrule height=0.0pt,width=0.0pt\shortrightarrow$}}}$

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:

$\displaystyle\textstyle{\mathbf{w}}_{t}={\mathsf{P}}_{\mathsf{r}}^{1/\pi_{t-1}}({\mathbf{w}}_{t}^{*}),\quad{\mathbf{w}}_{t+1}^{*}={\mathbf{w}}_{t}-\eta_{t}\widetilde{\nabla}\ell({\mathbf{w}}_{t}^{*}),$
(36)

In contrast to reversing BinnaryConnect, rPC is not completely without merit:
it evaluates the gradient at the continuous weights ${\mathbf{w}}_{t}^{*}$ and
hence is able to exploit a richer landscape of the loss. Even when stuck at a
fixed discrete weight ${\mathbf{w}}_{t}$, 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 ${\mathbf{w}}_{t}$: note that the
continuous weights ${\mathbf{w}}_{t}^{*}$ still get updated. Finally, for
constant step size $\eta$ and $\pi$, we note that fixed points of rPC, when
existent, satisfy:

$\displaystyle{\mathbf{w}}^{*}={\mathsf{P}}_{\mathsf{r}}^{1/\pi}({\mathbf{w}}^{*})-\eta\nabla\ell({\mathbf{w}}^{*})\iff{\mathbf{w}}^{*}$
$\displaystyle=(\mathsf{id}+\eta\nabla\ell)^{-1}\left(\mathsf{id}+\eta\left[\tfrac{\partial\mathsf{r}}{\pi\eta}\right]\right)^{-1}({\mathbf{w}}^{*})$
(37)
$\displaystyle=:{\mathcal{B}}\left(\eta,\nabla\ell,\tfrac{\partial\mathsf{r}}{\pi\eta}\right)({\mathbf{w}}^{*}),$
(38)

where for simplicity we assumed deterministic gradients $\nabla\ell$ and
$\mathsf{r}$ to be convex such that
${\mathsf{P}}^{1/\pi}_{\mathsf{r}}=(\mathsf{id}+\partial\mathsf{r}/\pi)^{-1}$.
The operator ${\mathcal{B}}$ is known as the backward-backward update (as
opposed to the forward-backward update in ProxQuant), and it is known that
when $\eta\to 0$ slowly, backward-backward updates 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.

Importance of GCG framework: Deriving PC from the GCG framework may let us
transfer recent advances on GCG [7, 50, 14] to 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 on CIFAR-10 [24] using ResNet20 and ResNet56
[19], comparing BinaryConnect [11] with ProxQuant [5] and (reverse)ProxConnect
using our proposed proximal operator ${\mathsf{L}}^{\varrho}_{\rho}$. For fair
comparison, we set $\rho=\varrho$ in ${\mathsf{L}}^{\varrho}_{\rho}$ as this
resembles the quantizer (for binary quantization) used in the original
ProxQuant algorithm. Similar to Bai et al. [5], we increase the parameter
$\rho$ (or equivalently $\varrho$) linearly:
$\rho_{t}=\left(1+t/B\right)\rho_{0}$. In contrast to Bai et al. [5], however,
we increase $\rho$ after every gradient step rather than after every epoch as
this is more in line with our analysis. We treat $\rho_{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 Section 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 $\rho_{0}$ values;
results for all $\rho_{0}$ values can be found in Section B.1.7.
(Reverse)ProxConnect outperforms the other two methods on all six settings.

Table 2: Fine-tuning pretrained ResNets. Final test accuracy: mean and standard deviation in 3 runs. Model | Quantization | BC [11] | PQ [5] | rPC (ours) | PC (ours)
---|---|---|---|---|---
ResNet20 | Binary |  90.31 (0.00) | 89.94 (0.10) | 89.98 (0.17) |  90.31 (0.21)
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)
ResNet56 | Binary | 92.22 (0.12) | 92.33 (0.06) | 92.47 (0.29) |  92.65 (0.16)
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)

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
$\rho_{0}$, whereas ProxConnect is stable in this regard; see Section B.1.7.

Table 3: End-to-end training of ResNets. Final test accuracy: mean and standard deviation in 3 runs. Model | Quantization | BC [11] | PQ [5] | rPC (ours) | PC (ours)
---|---|---|---|---|---
ResNet20 | Binary | 87.51 (0.21) | 81.59 (0.75) | 81.82 (0.32) |  89.92 (0.65)
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)
ResNet56 | Binary | 89.79 (0.45) | 86.13 (1.71) | 86.25 (1.50) |  91.26 (0.59)
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)

###  6.2 Classification on 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 Section B.2.

Table 4: Fine-tuning (left) and end-to-end training (right). Final test
accuracy: mean and standard deviation over three runs.

BC [11] | PC (ours)
---|---
$\rho_{0}=$210-2$$ | $\rho_{0}=$410-2$$
65.84 (0.04) | 65.44 (0.13) | 65.70 (0.04)

BC [11] | PC (ours)
---|---
$\rho_{0}=$2.510-3$$ | $\rho_{0}=$510-3$$
63.79 (0.12) |  63.89 (0.14) | 63.67 (0.12)

##  7 Conclusion

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.

## Acknowledgement

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 (partial) funding support.

## References

  * Ajanthan et al. [2021] Thalaiyasingam Ajanthan, Kartik Gupta, Philip Torr, Richard Hartley, and Puneet Dokania.  Mirror Descent View for Neural Network Quantization.  In _International Conference on Artificial Intelligence and Statistics_ , 2021.
  * Alizadeh et al. [2019] Milad Alizadeh, Javier Fernández-Marqués, Nicholas D. Lane, and Yarin Gal.  An Empirical study of Binary Neural Networks’ Optimisation.  In _International Conference on Learning Representations_ , 2019.
  * Anderson and Berg [2018] Alexander G. Anderson and Cory P. Berg.  The High-Dimensional Geometry of Binary Neural Networks.  In _International Conference on Learning Representations_ , 2018.
  * Bach [2015] Francis Bach.  Duality Between Subgradient and Conditional Gradient Methods.  _SIAM Journal on Optimization_ , 25(1):115–129, 2015.
  * Bai et al. [2018] Yu Bai, Yu-Xiang Wang, and Edo Liberty.  ProxQuant: Quantized Neural Networks via Proximal Operators.  In _International Conference on Learning Representations_ , 2018.
  * Bengio et al. [2013] Yoshua Bengio, Nicholas Léonard, and Aaron Courville.  Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation.  _arXiv:1308.3432_ , 2013.
  * Berrada et al. [2019] Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar.  Deep Frank–Wolfe For Neural Network Optimization.  In _International Conference on Learning Representations_ , 2019.
  * Bredies and Lorenz [2008] Kristian Bredies and Dirk A. Lorenz.  Iterated Hard Shrinkage for Minimization Problems with Sparsity Constraints.  _SIAM Journal on Scientific Computing_ , 30(2):657–683, 2008.
  * Brown and et al. [2020] Tom Brown and et al.  Language Models are Few-Shot Learners.  In _Advances in Neural Information Processing Systems_ , pages 1877–1901, 2020.
  * Chen et al. [2019] Shangyu Chen, Wenya Wang, and Sinno Jialin Pan.  MetaQuant: Learning to Quantize by Learning to Penetrate Non-differentiable Quantization.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Courbariaux et al. [2015] Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David.  BinaryConnect: Training Deep Neural Networks with binary weights during propagations.  In _Advances in Neural Information Processing Systems_ , volume 28, pages 3123–3131, 2015.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  ImageNet: A large-scale hierarchical image database.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pages 248–255, 2009.
  * Ding et al. [2019] Yukun Ding, Jinglan Liu, Jinjun Xiong, and Yiyu Shi.  On the Universal Approximability and Complexity Bounds of Quantized ReLU Neural Networks.  In _International Conference on Learning Representations_ , 2019.
  * Dvurechensky et al. [2020] 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.
  * Guo [2018] Yunhui Guo.  A Survey on Methods and Theories of Quantized Neural Networks.  _arXiv:1808.04752_ , 2018.
  * Gupta et al. [2015] Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan.  Deep Learning with Limited Numerical Precision.  In _International Conference on Machine Learning_ , 2015.
  * Han et al. [2020] 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 on Machine Learning_ , 2020.
  * Han et al. [2016] 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_ , 44(3):243–254, 2016.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016.
  * Helwegen et al. [2019] 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.
  * Hooker et al. [2020] Sara Hooker, Nyalleng Moorosi, Gregory Clark, Samy Bengio, and Emily Denton.  Characterising Bias in Compressed Models.  _arXiv:2010.03058_ , 2020.
  * Hou et al. [2019] Lu Hou, Ruiliang Zhang, and James T. Kwok.  Analysis of Quantized Models.  In _International Conference on Learning Representations_ , 2019.
  * Hubara et al. [2017] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations.  _Journal of Machine Learning Research_ , 18(1):6869–6898, 2017.
  * Krizhevsky [2009] Alex Krizhevsky.  Learning Multiple Layers of Features from Tiny Images, 2009.  The MIT License.
  * Leng et al. [2018] 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.
  * Li et al. [2016] Fengfu Li, Bo Zhang, and Bin Liu.  Ternary Weight Networks.  _arXiv:1605.04711_ , 2016.
  * Li et al. [2017] Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein.  Training Quantized Nets: A Deeper Understanding.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Lin et al. [2020] Ji Lin, Wei-Ming Chen, Yujun Lin, Chuang Gan, and Song Han.  MCUNet: Tiny Deep Learning on IoT Devices.  _Advances in Neural Information Processing Systems_ , 2020.
  * Martinez et al. [2020] Brais Martinez, Jing Yang, Adrian Bulat, and Georgios Tzimiropoulos.  Training binary neural networks with real-to-binary convolutions.  In _International Conference on Learning Representations_ , 2020.
  * Moreau [1965] Jean-Jacques Moreau.  Proximité et dualité dans un espace hilbertien.  _Bulletin de la Société Mathématique de France_ , 93:273–299, 1965.
  * Nesterov [2009] Yurii Nesterov.  Primal-dual subgradient methods for convex problems.  _Mathematical Programming_ , 120(1):221–259, 2009\.
  * Park et al. [2017] E. Park, J. Ahn, and S. Yoo.  Weighted-Entropy-Based Quantization for Deep Neural Networks.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 7197–7205, 2017.
  * Partovi Nia and Belbahri [2018] Vahid Partovi Nia and Mouloud Belbahri.  Binary Quantizer.  _Journal of Computational Vision and Imaging Systems_ , 4(1):3, 2018.
  * Passty [1979] Gregory B Passty.  Ergodic Convergence to a Zero of the Sum of Monotone Operators in Hilbert Space.  _Journal of Mathematical Analysis and Applications_ , 72(2):383–390, 1979.
  * Peters and Welling [2018] Jorn WT Peters and Max Welling.  Probabilistic Binary Neural Networks.  _arXiv:1809.03368_ , 2018.
  * Qin et al. [2020] Haotong Qin, Ruihao Gong, Xianglong Liu, Xiao Bai, Jingkuan Song, and Nicu Sebe.  Binary Neural Networks: A Survey.  _Pattern Recognition_ , 105:107281, 2020.
  * Rastegari et al. [2016] Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi.  XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks.  In _European Conference on Computer Vision_ , 2016.
  * Rockafellar and Wets [1998] R. Tyrrell Rockafellar and Roger J-B Wets.  _Variational Analysis_.  Springer, 1998.
  * Shayer et al. [2018] Oran Shayer, Dan Levi, and Ethan Fetaya.  Learning Discrete Weights Using the Local Reparameterization Trick.  In _International Conference on Learning Representations_ , 2018.
  * Strubell et al. [2019] 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.
  * Wang et al. [2019] 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.
  * Xiao [2010] Lin Xiao.  Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization.  _Journal of Machine Learning Research_ , 11:2543–2596, 2010\.
  * Xu et al. [2018] Chen Xu, Jianqiang Yao, Zhouchen Lin, Wenwu Ou, Yuanbin Cao, Zhirong Wang, and Hongbin Zha.  Alternating Multi-bit Quantization for Recurrent Neural Networks.  In _International Conference on Learning Representations_ , 2018.
  * Yin et al. [2019a] P Yin, S Zhang, YY Qi, and J Xin.  Quantization and Training of Low Bit-Width Convolutional Neural Networks for Object Detection.  _Journal of Computational Mathematics_ , 37(3), 2019a.
  * Yin et al. [2018] Penghang Yin, Shuai Zhang, Jiancheng Lyu, Stanley Osher, Yingyong Qi, and Jack Xin.  BinaryRelax: A Relaxation Approach for Training Deep Neural Networks with Quantized Weights.  _SIAM Journal on Imaging Sciences_ , 11(4):2205–2223, 2018.
  * Yin et al. [2019b] Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley J. Osher, Yingyong Qi, and Jack Xin.  Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets.  In _International Conference on Learning Representations_ , 2019b.
  * Yu [2013] Yaoliang Yu.  _Fast Gradient Methods for Structured Sparsity_.  PhD thesis, University of Alberta, 2013.
  * Yu et al. [2015] Yaoliang Yu, Xun Zheng, Micol Marchetti-Bowick, and Eric Xing.  Minimizing Nonconvex Non-Separable Functions.  In _Artificial Intelligence and Statistics_ , 2015.
  * Yu et al. [2017] Yaoliang Yu, Xinhua Zhang, and Dale Schuurmans.  Generalized Conditional Gradient for Structured Sparse Estimation.  _Journal of Machine Learning Research_ , 18:1–46, 2017\.
  * Zhang et al. [2020] Mingrui Zhang, Lin Chen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi.  Quantized Frank–Wolfe: Faster Optimization, Lower Communication, and Projection Free.  In _International Conference on Artificial Intelligence and Statistics_ , 2020.
  * Zhou et al. [2017] Aojun Zhou, Anbang Yao, Yiwen Guo, Lin Xu, and Yurong Chen.  Incremental Network Quantization: Towards Lossless CNNs with Low-precision Weights.  In _International Conference on Learning Representations_ , 2017.
  * Zhou et al. [2016] 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.
  * Zhu et al. [2018] Chenzhuo Zhu, Song Han, Huizi Mao, and William J Dally.  Trained Ternary Quantization.  In _International Conference on Learning Representations_ , 2018.

##  Appendix A Proofs

In this section we include all proofs omitted in the main paper, and supply
some additional comments.

###  A.1 Proofs for Section 3

*

###### Proof.

Define
${\mathsf{P}}({\mathbf{w}})=\sum_{i}\alpha_{i}{\mathsf{P}}_{i}({\mathbf{w}})$
if each ${\mathsf{P}}_{i}({\mathbf{w}})$ is single-valued. It is known that
any proximal map ${\mathsf{P}}_{i}$ is almost everywhere single-valued [38],
thus ${\mathsf{P}}$ is almost everywhere defined. Then, if necessary we take
the closure of the graph of ${\mathsf{P}}$ so that it is defined everywhere.
(This last step can be omitted if we always take the upper or lower limits at
any jump of ${\mathsf{P}}_{i}$.) With this interpretation of the average in
(9), the rest of the first claim then follows from [Proposition 4, 48].

For the second claim about the product map in (10), let ${\mathsf{P}}_{i}$ be
the proximal map of $f_{i}({\mathbf{w}}_{i}^{*})$. Then, it follows
immediately from the definition (8) that the product map ${\mathsf{P}}$ is the
proximal map of the sum function
$f({\mathbf{w}}^{*}):=\sum_{i}f_{i}({\mathbf{w}}_{i}^{*})$, where
${\mathbf{w}}^{*}=({\mathbf{w}}_{1}^{*},\ldots,{\mathbf{w}}_{k}^{*})$. ∎

###  A.2 Proofs for Section 4

Let us first record a general result for iterates of the following type:

$\displaystyle\mathsf{w}_{t+1}^{*}=\mathsf{w}_{t}^{*}+\eta_{t}{\mathbf{z}}_{t}^{*},$
(39)

where $\mathsf{w}_{0}^{*}$ is given and ${\mathbf{z}}_{t}^{*}$ may be
arbitrary.

######  Lemma A.1.

For any ${\mathbf{w}}$, any sequence of ${\mathbf{w}}_{t}$, and arbitrary
function $g$, the iterates (39) satisfy:

$\displaystyle\sum_{\tau=s}^{t}\eta_{\tau}[\left\langle{\mathbf{w}}_{\tau}\\!-\\!{\mathbf{w}},-{\mathbf{z}}^{*}_{\tau}\right\rangle\\!+\\!g({\mathbf{w}}_{\tau})\\!-\\!g({\mathbf{w}})]=\delta_{s-1}({\mathbf{w}})\\!-\\!\delta_{t}({\mathbf{w}})\\!+\\!\sum_{\tau=s}^{t}\delta_{\tau}({\mathbf{w}}_{\tau}),$
(40)

where
$\delta_{\tau}({\mathbf{w}})\coloneqq\tfrac{1}{\pi_{\tau}}g({\mathbf{w}})-\tfrac{1}{\pi_{\tau}}g({\mathbf{w}}_{\tau+1})-\left\langle{\mathbf{w}}-{\mathbf{w}}_{\tau+1},\mathsf{w}_{\tau+1}^{*}\right\rangle$
and $\tfrac{1}{\pi_{t}}=1+\sum_{\tau=1}^{t}\eta_{\tau}$.

###### Proof.

The proof is simple algebra (and was discovered by abstracting the original,
tedious proof of Section 4.1). For any ${\mathbf{w}}$, we verify:

$\displaystyle\sum_{\tau=s}^{t}\eta_{\tau}$
$\displaystyle[\left\langle{\mathbf{w}}_{\tau}\\!-\\!{\mathbf{w}},-{\mathbf{z}}^{*}_{\tau}\right\rangle\\!+\\!g({\mathbf{w}}_{\tau})\\!-\\!g({\mathbf{w}})]$
(41)
$\displaystyle=\sum_{\tau=s}^{t}\left\langle{\mathbf{w}}_{\tau}-{\mathbf{w}},\mathsf{w}_{\tau}^{*}-\mathsf{w}_{\tau+1}^{*}\right\rangle+\eta_{\tau}[g({\mathbf{w}}_{\tau})-g({\mathbf{w}})]$
(42)
$\displaystyle=\sum_{\tau=s}^{t}\left\langle{\mathbf{w}}_{\tau}-{\mathbf{w}},\mathsf{w}_{\tau}^{*}-\mathsf{w}_{\tau+1}^{*}\right\rangle+(\tfrac{1}{\pi_{\tau}}-\tfrac{1}{\pi_{\tau-1}})[g({\mathbf{w}}_{\tau})-g({\mathbf{w}})]$
(43)
$\displaystyle=\sum_{\tau=s}^{t}-\left\langle{\mathbf{w}}_{\tau}\\!-\\!{\mathbf{w}}_{\tau+1},\mathsf{w}_{\tau+1}^{*}\right\rangle\\!+\\!\left\langle{\mathbf{w}}\\!-\\!{\mathbf{w}}_{\tau+1},\mathsf{w}_{\tau+1}^{*}\right\rangle\\!-\\!\left\langle{\mathbf{w}}\\!-\\!{\mathbf{w}}_{\tau},\mathsf{w}_{\tau}^{*}\right\rangle\\!+\\!(\tfrac{1}{\pi_{\tau}}\\!-\\!\tfrac{1}{\pi_{\tau-1}})[g({\mathbf{w}}_{\tau})\\!-\\!g({\mathbf{w}})]$
(44)
$\displaystyle=\sum_{\tau=s}^{t}\delta_{\tau}({\mathbf{w}}_{\tau})\\!-\\!\delta_{\tau}({\mathbf{w}})\\!+\\!\delta_{\tau-1}({\mathbf{w}}).$
(45)

Telescoping completes the proof. ∎

*

###### Proof.

We first expand the recursion

$\displaystyle{\mathbf{w}}_{t+1}^{*}$
$\displaystyle=(1-\lambda_{t}){\mathbf{w}}_{t}^{*}+\lambda_{t}{\mathbf{z}}_{t}^{*}$
(46)
$\displaystyle=(1-\lambda_{t})(1-\lambda_{t-1}){\mathbf{w}}_{t-1}^{*}+\lambda_{t}{\mathbf{z}}_{t}^{*}+(1-\lambda_{t})\lambda_{t-1}{\mathbf{z}}_{t-1}^{*}$
(47) $\displaystyle=\dots$ (48)
$\displaystyle=(1-\lambda_{0})\pi_{t}{\mathbf{w}}_{0}^{*}+\sum_{\tau=0}^{t}\tfrac{\pi_{t}}{\pi_{\tau}}\lambda_{\tau}{\mathbf{z}}_{\tau}^{*},$
(49)

where $\pi_{t}\coloneqq\prod_{\tau=1}^{t}(1-\lambda_{\tau})$ for $t\geq 1$
while $\pi_{0}\coloneqq 1$ and $\lambda_{t}\in[0,1]$. We deduce (by, for
instance, setting ${\mathbf{z}}_{t}^{*}={\mathbf{w}}_{t}^{*}\equiv 1$, for all
$t\geq 0$, in (49)) that

$\displaystyle\frac{1}{\pi_{t}}=(1-\lambda_{0})+\sum_{\tau=0}^{t}\frac{\lambda_{\tau}}{\pi_{\tau}}=1+\sum_{\tau=1}^{t}\frac{\lambda_{\tau}}{\pi_{\tau}}.$
(50)

Define $\tfrac{1}{\pi_{-1}}\coloneqq 1-\lambda_{0}$ and
${\mathbf{z}}_{t}^{*}=-\nabla\ell^{**}({\mathbf{w}}_{t})$. We apply the
convexity of $\ell^{**}$ to the LHS of (20):

$\displaystyle\mathrm{LHS}$
$\displaystyle=\sum_{\tau=0}^{t}\tfrac{\lambda_{\tau}}{\pi_{\tau}}[\ell^{**}({\mathbf{w}}_{\tau})\\!+\\!\mathsf{r}^{**}({\mathbf{w}}_{\tau})\\!-\\!\ell^{**}({\mathbf{w}})\\!-\\!\mathsf{r}^{**}({\mathbf{w}})]$
(51)
$\displaystyle\leq\sum_{\tau=0}^{t}\tfrac{\lambda_{\tau}}{\pi_{\tau}}[\left\langle{\mathbf{w}}_{\tau}-{\mathbf{w}},-{\mathbf{z}}_{\tau}^{*}\right\rangle+\mathsf{r}^{**}({\mathbf{w}}_{\tau})-\mathsf{r}^{**}({\mathbf{w}})].$
(52)

Next, we identify $\eta_{\tau}\coloneqq\tfrac{\lambda_{\tau}}{\pi_{\tau}}$,
$g=\mathsf{r}^{**}$,
$\mathsf{w}^{*}_{\tau+1}\coloneqq{\mathbf{w}}^{*}_{\tau+1}/\pi_{\tau}=\mathsf{w}^{*}_{\tau}+\eta_{\tau}{\mathbf{z}}_{\tau}^{*}$,
and $\delta_{\tau}=\tfrac{1}{\pi_{\tau}}\Delta$ so that we can apply Lemma
A.1:

$\displaystyle\mathrm{LHS}$
$\displaystyle\leq\sum_{\tau=0}^{t}\tfrac{\lambda_{\tau}}{\pi_{\tau}}[\left\langle{\mathbf{w}}_{\tau}-{\mathbf{w}},-{\mathbf{z}}_{\tau}^{*}\right\rangle+\mathsf{r}^{**}({\mathbf{w}}_{\tau})-\mathsf{r}^{**}({\mathbf{w}})]$
(53)
$\displaystyle\leq(1-\lambda_{0})\Delta({\mathbf{w}},{\mathbf{w}}_{0})-\tfrac{1}{\pi_{t}}\Delta({\mathbf{w}},{\mathbf{w}}_{t+1})+\sum_{\tau=0}^{t}\tfrac{1}{\pi_{\tau}}\Delta({\mathbf{w}}_{\tau},{\mathbf{w}}_{\tau+1})$
(54)
$\displaystyle\leq(1-\lambda_{0})\Delta({\mathbf{w}},{\mathbf{w}}_{0})+\sum_{\tau=0}^{t}\tfrac{1}{\pi_{\tau}}\tfrac{L}{2}\|{\mathbf{w}}_{\tau+1}^{*}\\!-\\!{\mathbf{w}}_{\tau}^{*}\|_{2}^{2},$
(55)

where in the last step we applied the nonnegativity of the Bregman divergence
$\Delta$ (when induced by a convex function such as $\mathsf{r}^{**}$) as well
as the following inequality:

$\displaystyle\Delta({\mathbf{w}}_{\tau},{\mathbf{w}}_{\tau+1})$
$\displaystyle=\mathsf{r}^{**}({\mathbf{w}}_{\tau})-\mathsf{r}^{**}({\mathbf{w}}_{\tau+1})-\left\langle{\mathbf{w}}_{\tau}-{\mathbf{w}}_{\tau+1},{\mathbf{w}}_{\tau+1}^{*}\right\rangle$
(56)
$\displaystyle=\mathsf{r}^{**}({\mathbf{w}}_{\tau})-\mathsf{r}^{**}({\mathbf{w}}_{\tau+1})-\left\langle{\mathbf{w}}_{\tau}-{\mathbf{w}}_{\tau+1},\nabla\mathsf{r}^{**}({\mathbf{w}}_{\tau+1})\right\rangle\quad({\mathbf{w}}_{t}=\nabla\mathsf{r}^{*}({\mathbf{w}}_{t}^{*})\iff{\mathbf{w}}_{t}^{*}=\nabla\mathsf{r}^{**}({\mathbf{w}}_{t}))$
(57)
$\displaystyle=\mathsf{r}^{***}({\mathbf{w}}_{\tau+1}^{*})-\mathsf{r}^{***}({\mathbf{w}}_{\tau}^{*})-\left\langle{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*},\nabla\mathsf{r}^{***}(\nabla\mathsf{r}^{**}({\mathbf{w}}_{\tau}))\right\rangle\quad(\text{by
duality of Bregman divergence})$ (58)
$\displaystyle=\mathsf{r}^{*}({\mathbf{w}}_{\tau+1}^{*})-\mathsf{r}^{*}({\mathbf{w}}_{\tau}^{*})-\left\langle{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*},\nabla\mathsf{r}^{*}(\nabla\mathsf{r}^{**}({\mathbf{w}}_{\tau}))\right\rangle\quad(\text{by
convexity of}\,\mathsf{r}^{***})$ (59)
$\displaystyle=\mathsf{r}^{*}({\mathbf{w}}_{\tau+1}^{*})-\mathsf{r}^{*}({\mathbf{w}}_{\tau}^{*})-\left\langle{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*},{\mathbf{w}}_{\tau}\right\rangle\quad\left(\mbox{since
}\nabla\mathsf{r}^{**}=\left(\nabla\mathsf{r}^{*}\right)^{-1}\right)$ (60)
$\displaystyle\leq\left\langle{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*},\nabla\mathsf{r}^{*}({\mathbf{w}}_{\tau}^{*})\right\rangle+\tfrac{L}{2}\|{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*}\|_{2}^{2}-\left\langle{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*},{\mathbf{w}}_{\tau}\right\rangle\quad(\text{by
smoothness of}\,\mathsf{r}^{*})$ (61)
$\displaystyle=\tfrac{L}{2}\|{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*}\|_{2}^{2}\quad(\mbox{since
}{\mathbf{w}}_{\tau}\coloneqq\nabla\mathsf{r}^{*}({\mathbf{w}}_{\tau}^{*})).$
(62)

Applying (46) completes the proof. ∎

*

###### Proof.

By the convexity of $\mathsf{r}^{**}$ and $\ell^{**}$ as well as the fact that
the sum of two convex functions is convex, we have:

$\displaystyle(\ell^{**}+\mathsf{r}^{**})(\bar{\mathbf{w}}_{t})\leq\sum_{\tau=0}^{t}\Lambda_{t,\tau}(\ell^{**}+\mathsf{r}^{**})({\mathbf{w}}_{\tau}).$
(63)

Inserting the above in Section 4.1 (multiplied $1/H_{t}$) and noting that
$\sum_{\tau=0}^{t}\Lambda_{t,\tau}=1$, we have

$\displaystyle(\ell^{**}+\mathsf{r}^{**})(\bar{\mathbf{w}}_{t})-(\ell^{**}+\mathsf{r}^{**})({\mathbf{w}})$
$\displaystyle\leq\sum_{\tau=0}^{t}\Lambda_{t,\tau}\left[(\ell^{**}+\mathsf{r}^{**})({\mathbf{w}}_{\tau})-(\ell^{**}+\mathsf{r}^{**})({\mathbf{w}})\right]$
(64)
$\displaystyle\leq\tfrac{(1\\!-\\!\lambda_{0})\Delta({\mathbf{w}},{\mathbf{w}}_{0})}{H_{t}}\\!+\\!\tfrac{L}{2}\sum_{\tau=0}^{t}\lambda_{\tau}\Lambda_{t,\tau}\|{\mathbf{w}}_{\tau}^{*}\\!-\\!{\mathbf{z}}_{\tau}^{*}\|_{2}^{2}.$
(65)

∎

The following instantiation of Section 4.1 is notable: setting
$\lambda_{t}=\tfrac{1}{t+1}$ implies $\pi_{t}=\lambda_{t}$, $H_{t}=t+1$, and
therefore $\bar{\mathbf{w}}_{t}$ is simply ergodic averaging, i.e.,

$\displaystyle\bar{\mathbf{w}}_{t}=\frac{1}{t+1}\sum_{s=0}^{t}{\mathbf{w}}_{t}.$
(66)

The right-hand side of (21) diminishes at the rate of $O(\tfrac{\log t}{t})$
since

$\displaystyle\sum_{\tau=0}^{t}\lambda_{t}\Lambda_{t,\tau}=\frac{1}{t+1}\sum_{\tau=0}^{t}\frac{1}{\tau+1},~{}~{}\mbox{and}~{}~{}\sum_{\tau=0}^{t}\frac{1}{\tau+1}=O(\log
t).$ (67)

We remark that the log factor can be removed if we set
$\lambda_{t}=\tfrac{2}{t+2}$ instead, for which we have

$\displaystyle\pi_{t}$
$\displaystyle=\prod_{\tau=1}^{t}\frac{\tau}{\tau+2}=\frac{2}{(t+1)(t+2)},$
(68) $\displaystyle H_{t}$
$\displaystyle=\sum_{\tau=0}^{t}\frac{\lambda_{\tau}}{\pi_{\tau}}=\sum_{\tau=0}^{t}\frac{2}{\tau+2}\frac{(\tau+1)(\tau+2)}{2}=\frac{1}{2}(t+1)(t+2),$
(69) $\displaystyle\sum_{\tau=0}^{t}\lambda_{t}\Lambda_{t,\tau}$
$\displaystyle=\frac{4}{(t+1)(t+2)}\sum_{\tau=0}^{t}\frac{\tau+1}{\tau+2},~{}~{}\mbox{and}~{}~{}\sum_{\tau=0}^{t}\frac{\tau+1}{\tau+2}={\mathcal{O}}(t).$
(70)

######  Proposition A.2.

$\displaystyle\nabla\mathscr{M}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}_{t}^{*})={\mathsf{P}}_{\mathsf{r}^{**}}^{1/\mu}({\mathbf{w}}_{t}^{*}/\mu)$
(71)

###### Proof.

By the envelope theorem, we have
$\nabla\mathscr{M}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}_{t}^{*})=\tfrac{{\mathbf{w}}_{t}^{*}-{\mathsf{P}}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}_{t}^{*})}{\mu}$.
Furthermore, using the Moreau decomposition, we have

$\displaystyle{\mathbf{w}}_{t}^{*}$
$\displaystyle={\mathsf{P}}_{\mu\mathsf{r}^{*}}^{1}({\mathbf{w}}_{t}^{*})+{\mathsf{P}}_{\left(\mu\mathsf{r}^{*}\right)^{*}}^{1}({\mathbf{w}}_{t}^{*})$
(72)
$\displaystyle={\mathsf{P}}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}_{t}^{*})+{\mathsf{P}}_{\mathsf{s}}^{\mu}({\mathbf{w}}_{t}^{*}),$
(73)

where $\mathsf{s}({\mathbf{w}})\coloneqq\mathsf{r}^{**}({\mathbf{w}}/\mu)$.
Combining the two results, we have

$\displaystyle\nabla\mathscr{M}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}_{t}^{*})$
$\displaystyle=\frac{{\mathbf{w}}_{t}^{*}-{\mathsf{P}}_{\mathsf{r}^{*}}^{\mu}({\mathbf{w}}_{t}^{*})}{\mu}$
(74)
$\displaystyle=\frac{{\mathsf{P}}_{\mathsf{s}}^{\mu}({\mathbf{w}}_{t}^{*})}{\mu}$
(75)
$\displaystyle=\tfrac{1}{\mu}\operatorname*{arg\,min}_{\mathbf{w}}\tfrac{1}{2\mu}\|{\mathbf{w}}-{\mathbf{w}}_{t}^{*}\|_{2}^{2}+\mathsf{s}({\mathbf{w}})$
(76)
$\displaystyle=\operatorname*{arg\,min}_{\mathbf{w}}\tfrac{1}{2\mu}\|\mu{\mathbf{w}}-{\mathbf{w}}_{t}^{*}\|_{2}^{2}+\mathsf{s}(\mu{\mathbf{w}})$
(77)
$\displaystyle=\operatorname*{arg\,min}_{\mathbf{w}}\tfrac{\mu}{2}\|{\mathbf{w}}-\tfrac{{\mathbf{w}}_{t}^{*}}{\mu}\|_{2}^{2}+\mathsf{r}^{**}({\mathbf{w}})$
(78)
$\displaystyle={\mathsf{P}}_{\mathsf{r}^{**}}^{1/\mu}({\mathbf{w}}_{t}^{*}/\mu).$
(79)

∎

###  A.3 Proofs for Section 5

In fact, Section 5 is a special case of a more general result: theorempcg
Given ${\mathbf{w}}_{0}^{*}$, $\eta_{t}\geq 0$ and
$\tfrac{1}{\pi_{t}}=1+\sum_{\tau=1}^{t}\eta_{\tau}$, consider the iterates
defined as

$\displaystyle{\mathbf{w}}_{t}={\mathsf{P}}_{\mathsf{r}}^{1/\mu_{t}}(\pi_{t-1}{\mathbf{w}}_{t}^{*}/\mu_{t}),\qquad{\mathbf{w}}_{t+1}^{*}={\mathbf{w}}_{t}^{*}-\eta_{t}\widetilde{\nabla}\ell({\mathbf{w}}_{t}).$
(80)

Then, for any ${\mathbf{w}}$,

$\displaystyle\sum_{\tau=s}^{t}\eta_{\tau}[\langle{\mathbf{w}}_{\tau}\\!-\\!{\mathbf{w}},\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\rangle\\!+\\!\mathsf{r}({\mathbf{w}}_{\tau})\\!-\\!\mathsf{r}({\mathbf{w}})]$
$\displaystyle\leq\Delta_{s-1}({\mathbf{w}})\\!-\\!\Delta_{t}({\mathbf{w}})\\!+\\!\sum_{\tau=s}^{t}\Delta_{\tau}({\mathbf{w}}_{\tau})+$
(81)
$\displaystyle\qquad+\sum_{\tau=s}^{t}\tfrac{1}{2}(\tfrac{\mu_{\tau+1}}{\pi_{\tau}}-\tfrac{\mu_{\tau}}{\pi_{\tau-1}})(\|{\mathbf{w}}\|_{2}^{2}-\|{\mathbf{w}}_{\tau}\|_{2}^{2}),$
(82)

where
$\Delta_{\tau}({\mathbf{w}})\coloneqq\mathsf{r}_{\tau}({\mathbf{w}})-\mathsf{r}_{\tau}({\mathbf{w}}_{\tau+1})-\left\langle{\mathbf{w}}-{\mathbf{w}}_{\tau+1},{\mathbf{w}}_{\tau+1}^{*}\right\rangle$
is the Bregman divergence induced by the (possibly nonconvex) function
$\mathsf{r}_{\tau}({\mathbf{w}})\coloneqq\tfrac{1}{\pi_{\tau}}\mathsf{r}({\mathbf{w}})+\tfrac{\mu_{\tau+1}}{2\pi_{\tau}}\|{\mathbf{w}}\|_{2}^{2}$.

###### Proof.

We simply apply Lemma A.1 with
${\mathbf{z}}_{\tau}^{*}\coloneqq-\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})$,
$\mathsf{w}_{\tau}^{*}={\mathbf{w}}_{\tau}^{*}$ and $g\coloneqq\mathsf{r}$,
and note that

$\displaystyle\delta_{\tau}({\mathbf{w}})=\Delta_{\tau}({\mathbf{w}})-\tfrac{\mu_{\tau+1}}{2\pi_{\tau}}(\|{\mathbf{w}}\|_{2}^{2}-\|{\mathbf{w}}_{\tau+1}\|_{2}^{2}).$
(83)

To see that $\Delta_{\tau}$ is the Bregman divergence of $\mathsf{r}_{\tau}$,
we apply the (sub)differential optimality condition to

$\displaystyle{\mathbf{w}}_{\tau+1}\coloneqq{\mathsf{P}}_{\mathsf{r}}^{1/\mu_{\tau+1}}(\pi_{\tau}{\mathbf{w}}_{\tau+1}^{*}/\mu_{\tau+1})=\operatorname*{arg\,min}_{{\mathbf{w}}}~{}~{}\tfrac{1}{2}\|{\mathbf{w}}-\pi_{\tau}{\mathbf{w}}_{\tau+1}^{*}/\mu_{\tau+1}\|_{2}^{2}+\tfrac{1}{\mu_{\tau+1}}\mathsf{r}({\mathbf{w}}),$
(84)

so that

$\displaystyle{\mathbf{w}}_{\tau+1}^{*}\in\tfrac{\mu_{\tau+1}}{\pi_{\tau}}{\mathbf{w}}_{\tau+1}+\tfrac{1}{\pi_{\tau}}\nabla\mathsf{r}({\mathbf{w}}_{\tau+1})=\nabla\mathsf{r}_{\tau}({\mathbf{w}}_{\tau+1})$
(85)

and hence

$\displaystyle\Delta_{\tau}({\mathbf{w}})=\mathsf{r}_{\tau}({\mathbf{w}})-\mathsf{r}_{\tau}({\mathbf{w}}_{\tau+1})-\left\langle{\mathbf{w}}-{\mathbf{w}}_{\tau+1},\nabla\mathsf{r}_{\tau}({\mathbf{w}}_{\tau+1})\right\rangle.$
(86)

Clearly, $\mathsf{r}_{\tau}$ is convex if $\mathsf{r}$ is convex, in which
case $\Delta_{\tau}\geq 0$. ∎

*

###### Proof.

Simply set $\mu_{t}=\pi_{t-1}$ in Section A.3 above. ∎

*

###### Proof.

We first apply the expectation with respect to random sampling to (32) which
reduces the left hand side to

$\displaystyle\mathbf{E}\left[\sum_{\tau=s}^{t}\eta_{\tau}[\langle{\mathbf{w}}_{\tau}\\!-\\!{\mathbf{w}},\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\rangle\\!+\\!\mathsf{r}({\mathbf{w}}_{\tau})\\!-\\!\mathsf{r}({\mathbf{w}})]\right]$
$\displaystyle=\mathbf{E}\left[\sum_{\tau=s}^{t}\eta_{\tau}[\langle{\mathbf{w}}_{\tau}\\!-\\!{\mathbf{w}},\nabla\ell({\mathbf{w}}_{\tau})\rangle\\!+\\!\mathsf{r}({\mathbf{w}}_{\tau})\\!-\\!\mathsf{r}({\mathbf{w}})]\right]$
(87)
$\displaystyle\geq\mathbf{E}\left[\sum_{\tau=s}^{t}\eta_{\tau}[\ell({\mathbf{w}}_{\tau})\\!-\\!\ell({\mathbf{w}})\\!+\\!\mathsf{r}({\mathbf{w}}_{\tau})\\!-\\!\mathsf{r}({\mathbf{w}})]\right]$
(88)
$\displaystyle=\mathbf{E}\left[\sum_{\tau=s}^{t}\eta_{\tau}[f({\mathbf{w}}_{\tau})\\!-\\!f({\mathbf{w}})]\right],$
(89)

where we used the convexity of $\ell$. We then obtain (33) by using

$\displaystyle\\!\\!\min_{\tau=s,\ldots,t}~{}\mathbf{E}\left[f({\mathbf{w}}_{\tau})\\!-\\!f({\mathbf{w}})\right]\leq\frac{1}{\sum_{\tau=s}^{t}\eta_{\tau}}\mathbf{E}\left[\sum_{\tau=s}^{t}\eta_{\tau}[f({\mathbf{w}}_{\tau})\\!-\\!f({\mathbf{w}})]\right].$
(90)

The right-hand sides of (34) and (35) are obtained by setting
$\mu_{\tau}=\pi_{\tau-1}$ and upper bounding the Bregman divergence:

$\displaystyle\Delta_{\tau}({\mathbf{w}}_{\tau})$
$\displaystyle=\mathsf{r}_{\tau}({\mathbf{w}}_{\tau})-\mathsf{r}_{\tau}({\mathbf{w}}_{\tau+1})-\left\langle{\mathbf{w}}_{\tau}-{\mathbf{w}}_{\tau+1},{\mathbf{w}}_{\tau+1}^{*}\right\rangle$
(91)
$\displaystyle=\mathsf{r}^{*}_{\tau}({\mathbf{w}}_{\tau+1}^{*})-\mathsf{r}^{*}_{\tau}({\mathbf{w}}_{\tau}^{*})-\left\langle{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*},{\mathbf{w}}_{\tau}\right\rangle\quad(\text{by
duality of Bregman divergence})$ (92)
$\displaystyle\leq\frac{1}{2}\|{\mathbf{w}}_{\tau}^{*}-{\mathbf{w}}_{\tau+1}^{*}\|_{2}^{2}\quad(\text{by
1-smoothness of}\,\mathsf{r}^{*})$ (93)
$\displaystyle=\frac{\eta_{t}^{2}}{2}\|\widetilde{\nabla}\ell({\mathbf{w}}_{t})\|_{2}^{2},$
(94)

where we have used the well-known fact that the Fenchel conjugate of a
$(1/L)$-strongly convex function is $L$-smooth (in our case $L=1$). Lastly,
the left-hand side of (35) is obtained by applying the convexity of $f$:

$\displaystyle\left[{\sum_{\tau=s}^{t}\eta_{\tau}}\right]f(\bar{\mathbf{w}}_{t})\leq{\sum_{\tau=s}^{t}\eta_{\tau}f({\mathbf{w}}_{\tau})},~{}~{}\mbox{where}~{}~{}\bar{\mathbf{w}}_{t}=\tfrac{\sum_{\tau=s}^{t}\eta_{\tau}{\mathbf{w}}_{\tau}}{\sum_{\tau=s}^{t}\eta_{\tau}}.$
(95)

∎

####  A.3.1 Discussion of Section A.3

Recall the Bregman divergence from Section A.3:

$\displaystyle\Delta_{\tau}({\mathbf{w}})=\mathsf{r}_{\tau}({\mathbf{w}})-\mathsf{r}_{\tau}({\mathbf{w}}_{\tau+1})-\left\langle{\mathbf{w}}-{\mathbf{w}}_{\tau+1},{\mathbf{w}}_{\tau+1}^{*}\right\rangle,\quad\mathsf{r}_{\tau}({\mathbf{w}})=\tfrac{1}{\pi_{\tau}}\mathsf{r}({\mathbf{w}})+\tfrac{\mu_{\tau+1}}{2\pi_{\tau}}\|{\mathbf{w}}\|_{2}^{2}.$
(96)

When $\mathsf{r}$ is $\sigma_{0}$-strongly convex, $\mathsf{r}_{\tau}$ is
$\tfrac{\sigma_{0}+\mu_{\tau+1}}{\pi_{\tau}}$-strongly convex, and hence

$\displaystyle\Delta_{\tau}({\mathbf{w}}_{\tau})\leq\tfrac{\pi_{\tau}}{2(\sigma_{0}+\mu_{\tau+1})}\|{\mathbf{w}}_{\tau+1}^{*}-{\mathbf{w}}_{\tau}^{*}\|_{2}^{2}=\tfrac{\pi_{\tau}\eta_{\tau}^{2}}{2(\sigma_{0}+\mu_{\tau+1})}\|\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\|_{2}^{2},$
(97)

where we used the duality of the Bregman divergence and the smoothness of
$\mathsf{r}_{\tau}^{*}$. Dividing both sides of (81) by
$\sum_{\tau=s}^{t}\eta_{\tau}$ we obtain the upper bound:

$\displaystyle\mathrm{UB}\coloneqq\frac{\tfrac{\pi_{s-1}}{\sigma_{0}+\mu_{s}}\|{\mathbf{w}}^{*}-{\mathbf{w}}_{s}^{*}\|_{2}^{2}+\sum_{\tau=s}^{t}\big{[}\tfrac{\pi_{\tau}\eta_{\tau}^{2}}{\sigma_{0}+\mu_{\tau+1}}\|\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\|_{2}^{2}+(\tfrac{\mu_{\tau+1}}{\pi_{\tau}}-\tfrac{\mu_{\tau}}{\pi_{\tau-1}})(\|{\mathbf{w}}\|_{2}^{2}-\|{\mathbf{w}}_{\tau}\|_{2}^{2})\big{]}}{2\sum_{\tau=s}^{t}\eta_{\tau}},$
(98)

where ${\mathbf{w}}^{*}\coloneqq\nabla\mathsf{r}_{s-1}({\mathbf{w}})$ and we
have dropped the non-positive term $-\Delta_{t}({\mathbf{w}})$. Suppose777This
assumption can be easily satisfied. In fact, we can just set
$\mu_{t+1}=\pi_{t}$ (as in the main paper), which would simplify the
discussion quite a bit. $\tfrac{\mu_{t+1}}{\pi_{t}}$ is non-decreasing w.r.t.
$t$, we can thus drop some non-positive terms to further simplify:

$\displaystyle\mathrm{UB}\leq\frac{\tfrac{\pi_{s-1}}{\sigma_{0}+\mu_{s}}\|{\mathbf{w}}^{*}-{\mathbf{w}}_{s}^{*}\|_{2}^{2}+\tfrac{\mu_{t+1}}{\pi_{t}}\|{\mathbf{w}}\|_{2}^{2}+\sum_{\tau=s}^{t}\big{[}\tfrac{\pi_{\tau}\eta_{\tau}^{2}}{\sigma_{0}+\mu_{\tau+1}}\|\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\|_{2}^{2}\big{]}}{2\sum_{\tau=s}^{t}\eta_{\tau}},$
(99)

To minimize the upper bound, we consider two cases:

  * •

$\sigma_{0}=0$, in which case let us choose
$\mu_{\tau+1}=c\sqrt{\eta_{\tau}\pi_{\tau}}=c\sqrt{\lambda_{\tau}}$ (recall
that we reparameterized $\eta_{\tau}=\lambda_{\tau}/\pi_{\tau}$ from GCG),
where $c$ is an absolute constant. Then, the upper bound reduces to

$\displaystyle\frac{\tfrac{\pi_{s-1}}{\mu_{s}}\|{\mathbf{w}}^{*}-{\mathbf{w}}_{s}^{*}\|_{2}^{2}+\tfrac{c\eta_{t}}{\sqrt{\lambda_{t}}}\|{\mathbf{w}}\|_{2}^{2}+\sum_{\tau=s}^{t}\eta_{\tau}\sqrt{\lambda_{\tau}}\|\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\|_{2}^{2}/c}{2\sum_{\tau=s}^{t}\eta_{\tau}},$
(100)

where recall that $\pi_{t}=\tfrac{1}{1+\sum_{\tau=1}^{t}\eta_{\tau}}$. When
the gradient $\nabla\ell$ is bounded, we may choose

$\displaystyle\lambda_{t}=\tfrac{\eta_{t}}{1+\sum_{\tau=1}^{t}\eta_{\tau}}=O(1/t)\mbox{
and }\tfrac{1}{\sum_{\tau=1}^{t}\eta_{\tau}}=O(1/\sqrt{t})$ (101)

so that the upper bound diminishes888Note that by choosing $s\propto t$, the
averaged sequence
$\tfrac{\sum_{\tau=s}^{t}\eta_{\tau}\sqrt{\lambda_{\tau}}}{\sum_{\tau=s}^{t}\eta_{\tau}}\leq\max\limits_{\tau=s,\ldots,t}\sqrt{\lambda_{\tau}}$
diminishes similarly in order as $\sqrt{\lambda_{t}}$. at the rate of
$O(1/\sqrt{t})$. This result makes intuitive sense, since we know the optimal
step size $\lambda_{t}$ in GCG is $\Theta(1/t)$. Also, it reveals that the
smoothing parameter $\mu_{t}=O(1/\sqrt{t})$, matching the rate of the upper
bound (i.e., progress on the original problem). Interestingly, the choice in
(101) can be realized in multiple ways. In fact, $\eta_{t}=\eta_{0}t^{-p}$ for
any $p\in[0,\tfrac{1}{2}]$ suffices, In particular, choosing $p=0$ leads to
the constant step size $\eta_{t}\equiv\eta_{0}$. However, note that these
choices are in some sense equivalent, since they all lead to
$\lambda_{t}=O(1/t)$ and $\mu_{t}=O(1/\sqrt{t})$ hence the underlying GCG
progresses similarly.

  * •

$\sigma_{0}>0$, in which case we can further relax the upper bound to:

$\displaystyle\mathrm{UB}\leq\frac{\tfrac{\pi_{s-1}}{\sigma_{0}+\mu_{s-1}}\|{\mathbf{w}}^{*}-{\mathbf{w}}_{s}^{*}\|_{2}^{2}+\tfrac{\mu_{t+1}}{\pi_{t}}\|{\mathbf{w}}\|_{2}^{2}+\sum_{\tau=s}^{t}\big{[}\tfrac{\pi_{\tau}\eta_{\tau}^{2}}{\sigma_{0}}\|\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\|_{2}^{2}\big{]}}{2\sum_{\tau=s}^{t}\eta_{\tau}},$
(102)

and now we may choose $\mu_{\tau+1}=c\eta_{\tau}\pi_{\tau}=c\lambda_{\tau}$,
which approaches 0 significantly faster than before. With this choice, the
upper bound reduces to

$\displaystyle\frac{\tfrac{\pi_{s-1}}{\sigma_{0}+\mu_{s-1}}\|{\mathbf{w}}^{*}-{\mathbf{w}}_{s}^{*}\|_{2}^{2}+c\eta_{t}\|{\mathbf{w}}\|_{2}^{2}+\sum_{\tau=s}^{t}\eta_{\tau}\lambda_{\tau}\big{[}\|\widetilde{\nabla}\ell({\mathbf{w}}_{\tau})\|_{2}^{2}/\sigma_{0}\big{]}}{2\sum_{\tau=s}^{t}\eta_{\tau}}.$
(103)

Again, we may set $\lambda_{t}$ as in (101), and we can choose constant
$\eta_{t}\equiv\eta_{0}$. The major difference is that we may now decrease the
smoothing parameter $\mu_{t}$ much more aggressively.

##  Appendix B Implementation and Experiment Details

###  B.1 CIFAR-10

####  B.1.1 Model and Quantization Details

Similar to Bai et al. [5], we use ResNets for which we quantize all weights.
BatchNormalization layers and activations are kept at full precision. The
basic ResNet implementation is taken from
https://github.com/akamaster/pytorch_resnet_cifar10/blob/master/resnet.py.

####  B.1.2 Data Augmentation

We follow the data augmentation strategy from Bai et al. [5]: padding by four
pixels on each side, randomly cropping to 32-by-32 pixels, horizontally
flipping with probability one half. Finally, the images are normalized by
subtracting $(0.4914,0.4822,0.4465)$ and subsequently dividing by
$(0.247,0.243,0.261)$.

####  B.1.3 Pretrained Full Precision Model Setup

We pretrain two single full precision models for 200 epochs using the standard
optimization setup: SGD with 0.9 momentum and $110-4$ weight decay. The
initial learning rate is $0.1$ which is multiplied by 0.1 at epoch 100 and
150. We use batch size 128.

####  B.1.4 Fine-Tuning Setup

All methods are initialized with the last checkpoint of the full precision
models.

For BinaryConnect, we train with the recommended strategy from Courbariaux et
al. [11]: Adam with learning rate 0.01 and multiplication of the learning rate
by $0.1$ at epoch 81 and 122. For ProxQuant we use Adam with fixed learning
rate of 0.01 as in Bai et al. [5]. We did not perform hyperparameter search
over the optimization setup for ProxConnect but rather just used the
optimization setup from BinaryConnect as the methods are very similar. We use
batch size 128.

Similar to Bai et al. [5], we perform a hard quantization at epoch 200: all
weights are projected to their closet quantization points. As in Bai et al.
[5], we then train BatchNormalization layers for another 100 epochs.

####  B.1.5 End-To-End Setup

For simplicity and to avoid an expensive hyperparameter search, we followed
the above full precision optimization setup for all methods. Similar to the
fine-tuning setup, we perform a hard quantization at epoch 200 and keep
training BatchNormalization layers for another 100 epochs. We use batch size
128.

####  B.1.6 Compute and Resources

We run all CIFAR-10 experiments on our internal cluster with GeForce GTX 1080
Ti. We use one GPU per experiment. The total amount of GPU hours is summarized
in Table 5.

Table 5: Compute for CIFAR-10 experiments measured in hours per single GeForce GTX 1080 Ti GPU. Architecture | Run time | # of total experiments | Total run time
---|---|---|---
ResNet20 | 1.5 | 181 | 271.5
ResNet56 | 3 | 181 | 543

####  B.1.7 Additional Results

As mentioned in Section 6.1, we perform a small grid search over $\rho_{0}$.
After an initial exploration stage, we found good regions of $\rho_{0}$ for
ProxQuant and ProxConnect. Since ProxQuant and reverseProxConnect are quite
similar, in particular in the small $\rho$ regime, we simply used the
$\rho_{0}$ from ProxQuant for reverseProxConnect. See below the results for
all $\rho_{0}$ settings.

ProxConnect is reasonably stable with respect to the choice of $\rho_{0}$ for
both fine-tuning and end-to-end training. ProxQuant and reverseProxConnect, on
the other hand, are very sensitive to the choice of $\rho_{0}$ for end-to-end
training. ProxConnect reduces to BinaryConnect for large $\rho$, and therefore
it is in line with our experiments that ProxConnect should be stable with
respect to $\rho_{0}$, particularly choosing $\rho_{0}$ too large should not
be an issue.

Table 6: Additional results for fine-tuning ProxQuant. Model | Quantization | $\rho_{0}=$510-7$$ | $\rho_{0}=$110-6$$ | $\rho_{0}=$210-6$$
---|---|---|---|---
ResNet20 | Binary | 89.68 (0.10) |  89.94 (0.10) | 89.34 (0.33)
Ternary | 91.03 (0.07) |  91.46 (0.05) | 91.11 (0.10)
Quaternary | 91.10 (0.06) | 91.13 (0.18) |  91.43 (0.17)
ResNet56 | Binary | 92.25 (0.08) |  92.33 (0.06) | 92.16 (0.14)
Ternary | 92.52 (0.90) |  93.07 (0.02) | 92.71 (0.16)
Quaternary | 92.49 (0.03) |  92.82 (0.13) | 92.80 (0.15)
Table 7: Additional results for fine-tuning reverseProxConnect. Model | Quantization | $\rho_{0}=$510-7$$ | $\rho_{0}=$110-6$$ | $\rho_{0}=$210-6$$
---|---|---|---|---
ResNet20 | Binary | 89.88 (0.23) |  89.98 (0.17) | 89.91 (0.24)
Ternary | 91.30 (0.05) | 91.36 (0.03) |  91.47 (0.15)
Quaternary | 91.05 (0.12) |  91.43 (0.05) | 91.42 (0.07)
ResNet56 | Binary | 92.18 (0.06) | 92.35 (0.02) |  92.47 (0.29)
Ternary |  92.84 (0.09) | 92.85 (0.12) | 92.84 (0.17)
Quaternary | 92.66 (0.20) | 92.88 (0.17) |  92.91 (0.22)
Table 8: Additional results for fine-tuning ProxConnect. Model | Quantization | $\rho_{0}=$510-3$$ | $\rho_{0}=$110-2$$ | $\rho_{0}=$210-2$$
---|---|---|---|---
ResNet20 | Binary | 89.63 (0.26) | 90.29 (0.07) |  90.31 (0.21)
Ternary | 91.31 (0.07) |  91.37 (0.18) | 91.13 (0.27)
Quaternary | 91.62 (0.21) | 91.55 (0.10) |  91.81 (0.14)
ResNet56 | Binary | 92.41 (0.13) | 92.62 (0.09) |  92.65 (0.16)
Ternary | 93.17 (0.04) |  93.25 (0.12) | 93.22 (0.06)
Quaternary | 93.41 (0.11) |  93.42 (0.12) | 93.28 (0.06)
Table 9: Additional results end-to-end training ProxQuant. Model | Quantization | $\rho_{0}=$110-7$$ | $\rho_{0}=$110-6$$ | $\rho_{0}=$110-5$$
---|---|---|---|---
ResNet20 | Binary |  81.59 (0.75) | 81.49 (0.41) | 71.90 (0.75)
Ternary | 28.22 (1.70) | 41.08 (2.95) |  47.98 (1.06)
Quaternary | 84.58 (0.15) |  85.29 (0.07) | 75.08 (0.16)
ResNet56 | Binary |  86.13 (1.71) | 80.25 (0.51) | 68.31 (2.21)
Ternary | 21.93 (2.43) | 41.11 (2.12) |  50.54 (3.01)
Quaternary |  87.81 (1.30) | 83.57 (1.70) | 72.58 (2.23)
Table 10: Additional results end-to-end training reverseProxConnect. Model | Quantization | $\rho_{0}=$110-7$$ | $\rho_{0}=$110-6$$ | $\rho_{0}=$110-5$$
---|---|---|---|---
ResNet20 | Binary |  81.82 (0.32) | 80.84 (0.40) | 72.10 (1.01)
Ternary | 26.49 (2.82) | 40.78 (0.39) |  47.17 (1.94)
Quaternary |  85.05 (0.27) | 84.82 (0.32) | 75.61 (0.54)
ResNet56 | Binary |  86.25 (1.50) | 81.58 (0.92) | 67.53 (2.74)
Ternary | 21.51 (1.12) |  42.95 (1.57) | 36.34 (18.68)
Quaternary |  87.30 (1.02) | 84.72 (1.31) | 73.36 (1.36)
Table 11: Additional results end-to-end training ProxConnect. Model | Quantization | $\rho_{0}=$510-3$$ | $\rho_{0}=$110-2$$ | $\rho_{0}=$210-2$$
---|---|---|---|---
ResNet20 | Binary | 89.72 (0.13) |  89.92 (0.26) | 89.65 (0.15)
Ternary |  84.09 (0.16) | 83.54 (0.36) | 82.84 (0.34)
Quaternary |  90.17 (0.14) | 90.12 (0.33) | 89.91 (0.09)
ResNet56 | Binary |  91.26 (0.59) | 90.45 (0.83) | 89.29 (0.45)
Ternary |  84.36 (0.75) | 83.46 (1.14) | 82.54 (1.38)
Quaternary | 91.00 (0.50) | 90.76 (0.54) |  91.70 (0.14)

###  B.2 ImageNet

###  B.3 Model and Quantization Details

We use ResNet18 as our model, for which we quantize all weights except for the
first convolutional layer and the last fully-connected layer. Other components
such as BatchNormalization layers, activations and biases are kept at full-
precision. The ResNet implementation is borrowed from PyTorch’s torchvision
package:
https://github.com/pytorch/vision/blob/882e11db8138236ce375ea0dc8a53fd91f715a90/torchvision/models/resnet.py.

###  B.4 Data Augmentation

Common data augmentation strategy is followed from
https://github.com/pytorch/examples/blob/c002856901eaf9be112feb9b14a9d5c3e779da74/imagenet/main.py#L204-L231.
At training time, the images are randomly resized and cropped to 224-by-224
pixels, followed by a random horizontal flip. At inference time, images are
first resized to 256-by-256 pixels, then center cropped to 224-by-224 pixels.
Finally, the images are normalized by subtracting $(0.485,0.456,0.406)$ and
subsequently dividing by $(0.229,0.224,0.224)$.

###  B.5 Pretrained Full Precision Model Setup

We use the ResNet18 checkpoint provided by torchvision as our pretrained
model: https://download.pytorch.org/models/resnet18-f37072fd.pth.

###  B.6 Fine-Tuning Setup

All fine-tuned models are initialized from the pretrained model described in
the previous section.

As advised by Alizadeh et al. [2], we use Adam as the optimizer to fine-tune
the models. We use Adam with default parameters, initial learning rate $110-4$
and batch size 256. The models are fine-tuned for 50 epochs. The learning rate
is divided by 10 at epoch 15 and 30. We perform hard quantization at epoch 45
and train the remaining full-precision layers for the last 5 epochs, mostly to
let BatchNormalization layers stabilize.

###  B.7 End-To-End Setup

For the end-to-end setup, the models are trained from scratch mimicking the
training setup of the full-precision pretrained model. The quantized ResNet18
is trained for 90 epochs using SGD with a starting learning rate of $0.1$,
momentum of $0.9$ and weight decay of $110-4$. The learning rate is multiplied
by $0.1$ at epoch 30 and 60. We use batch size 256. We perform hard
quantization at epoch 80 and train the remaining full-precision layers for the
last 10 epochs.

###  B.8 Compute and Resources

We run all experiments on our internal cluster with Tesla V100. We use one GPU
per experiment. The total amount of GPU hours is summarized in Table 12.

Table 12: Compute for ImageNet experiments measured in hours per single Tesla V100 GPU. Approach | Run time | # of total experiments | Total run time
---|---|---|---
End-To-End | 27 | 9 | 243
Fine-Tuning | 12 | 9 | 108