# WRPN: Wide Reduced-Precision Networks

Asit Mishra Eriko Nurvitadhi Jeffrey J Cook Debbie Marr
Accelerator Architecture Lab, Intel

###### Abstract

For computer vision applications, prior works have shown the efficacy of
reducing numeric precision of model parameters (network weights) in deep
neural networks. Activation maps, however, occupy a large memory footprint
during both the training and inference step when using mini-batches of inputs.
One way to reduce this large memory footprint is to reduce the precision of
activations. However, past works have shown that reducing the precision of
activations hurts model accuracy. We study schemes to train networks from
scratch using reduced-precision activations without hurting accuracy. We
reduce the precision of activation maps (along with model parameters) and
increase the number of filter maps in a layer, and find that this scheme
matches or surpasses the accuracy of the baseline full-precision network. As a
result, one can significantly improve the execution efficiency (e.g. reduce
dynamic memory footprint, memory bandwidth and computational energy) and speed
up the training and inference process with appropriate hardware support. We
call our scheme WRPN - wide reduced-precision networks. We report results and
show that WRPN scheme is better than previously reported accuracies on
ILSVRC-12 dataset while being computationally less expensive compared to
previously reported reduced-precision networks.

##  1 Introduction

A promising approach to lower the compute and memory requirements of
convolutional deep-learning workloads is through the use of low numeric
precision algorithms. Operating in lower precision mode reduces computation as
well as data movement and storage requirements. Due to such efficiency
benefits, there are many existing works which propose low-precision deep
neural networks (DNNs) [25, 13, 15, 7, 22], even down to 2-bit ternary mode
[27, 12, 23] and 1-bit binary mode [26, 4, 17, 5, 21]. However, the majority
of existing works in low-precision DNNs sacrifice accuracy over the baseline
full-precision networks. Further, most prior works target reducing the
precision of the model parameters (network weights). This primarily benefits
the inference step only when batch sizes are small.

To improve both execution efficiency and accuracy of low-precision networks,
we reduce both the precision of activation maps and model parameters and
increase the number of filter maps in a layer. We call networks using this
scheme wide reduced-precision networks (WRPN) and find that this scheme
compensates or surpasses the accuracy of the baseline full-precision network.
Although the number of raw compute operations increases as we increase the
number of filter maps in a layer, the compute bits required per operation is
now a fraction of what is required when using full-precision operations (e.g.
going from FP32 AlexNet to 4-bits precision and doubling the number of filters
increases the number of compute operations by 4x, but each operation is 8x
more efficient than FP32).

WRPN offers better accuracies, while being computationally less expensive
compared to previously reported reduced-precision networks. We report results
on AlexNet [11], batch-normalized Inception [9], and ResNet-34 [8] on
ILSVRC-12 [11] dataset. We find 4-bits to be sufficient for training deep and
wide models while achieving similar or better accuracy than baseline network.
With 4-bit activation and 2-bit weights, we find the accuracy to be at-par
with baseline full-precision. Making the networks wider and operating with
1-bit precision, we close the accuracy gap between previously report binary
networks and show state-of-the art results for ResNet-34 (69.85% top-1 with 2x
wide) and AlexNet (48.04% top-1 with 1.3x wide). To the best of our knowledge,
our reported accuracies with binary networks (and even 4-bit precision) are
highest to date.

Our reduced-precision quantization scheme is hardware friendly allowing for
efficient hardware implementations. To this end, we evaluate efficiency
benefits of low-precision operations (4-bits to 1-bits) on Titan X GPU,
Arria-10 FPGA and ASIC. We see that FPGA and ASIC can deliver significant
efficiency gain over FP32 operations (6.5x to 100x), while GPU cannot take
advantage of very low-precision operations.

##  2 Motivation for reduced-precision activation maps

Figure 1: Memory footprint of activations (ACTs) and weights (W) during
training and inference for mini-batch sizes 1 and 32.

While most prior works proposing reduced-precision networks work with low
precision weights (e.g. [4, 27, 26, 23, 12, 5, 21]), we find that activation
maps occupy a larger memory footprint when using mini-batches of inputs. Using
mini-batches of inputs is typical in training of DNNs and cloud-based batched
inference [10]. Figure 1 shows memory footprint of activation maps and filter
maps as batch size changes for 4 different networks (AlexNet, Inception-
Resnet-v2 [19], ResNet-50 and ResNet-101) during the training and inference
steps.

Figure 2: Memory requirements of a feed forward convolutional deep neural
network. Orange boxes denote weights (W), blue boxes are activations (ACT) and
green boxes are gradient-maps (Grad).

As batch-size increases, because of filter reuse across batches of inputs,
activation maps occupy significantly larger fraction of memory compared to the
filter weights. This aspect is illustrated in Figure 2 which shows the memory
requirements of a canonical feed-forward DNN for a hardware accelerator based
system (e.g. GPU, FPGA, PCIe connected ASIC device, etc.). During training,
the sum of all the activation maps (ACT) and weight tensors (W) are allocated
in device memory for forward pass along with memory for gradient maps during
backward propagation. The total memory requirements for training phase is the
sum of memory required for the activation maps, weights and the maximum of
input gradient maps ($\delta$Z) and maximum of back-propagated gradients
($\delta$X). During inference, memory is allocated for input (IFM) and output
feature maps (OFM) required by a single layer, and these memory allocations
are reused for other layers. The total memory allocation during inference is
then the maximum of IFM and maximum of OFM required across all the layers plus
the sum of all W-tensors. At batch sizes 128 and more, activations start to
occupy more than 98% of total memory footprint during training.

Overall, reducing precision of activations and weights reduces memory
footprint, bandwidth and storage while also simplifying the requirements for
hardware to efficiently support these operations.

##  3 WRPN scheme and studies on AlexNet

Based on the observation that activations occupy more memory footprint
compared to weights, we reduce the precision of activations to speed up
training and inference steps as well as cut down on memory requirements.
However, a straightforward reduction in precision of activation maps leads to
significant reduction in model accuracy [26, 17].

We conduct a sensitivity study where we reduce precision of activation maps
and model weights for AlexNet running ILSVRC-12 dataset and train the network
from scratch. Table 2 reports our findings. Top-1 single-precision (32-bits
weights and activations) accuracy is 57.2%. The accuracy with binary weights
and activations is 44.2%. This is similar to what is reported in [17]. $32bA$
and $2bW$ data-point in this table is using TTQ technique [27]. All other data
points are collected using our quantization scheme (described later in Section
5), all the runs have same hyper-parameters and training is carried out for
the same number of epochs as baseline network. To be consistent with results
reported in prior works, we do not quantize weights and activations of the
first and last layer.

We find that, in general, reducing the precision of activation maps and
weights hurts model accuracy. Further, reducing precision of activations hurts
model accuracy much more than reducing precision of the filter parameters. We
find TTQ to be quite effective on AlexNet in that one can lower the precision
of weights to 2b (while activations are still FP32) and not lose accuracy.
However, we did not find this scheme to be effective for other networks like
ResNet or Inception.

floatrowsep=qquad, captionskip=2pt [2]  32b A 8b A 4b A 2b A 1b A 32b W 57.2
54.3 54.4 52.7 – 8b W – 54.5 53.2 51.5 – 4b W – 54.2 54.4 52.4 – 2b W 57.5
50.2 50.5 51.3 – 1b W 56.8 – – – 44.2 32b A 8b A 4b A 2b A 1b A 32b W 60.5
58.9 58.6 57.5 52.0 8b W – 59.0 58.8 57.1 50.8 4b W – 58.8 58.6 57.3 – 2b W –
57.6 57.2 55.8 – 1b W – – – – 48.3

Table 1: AlexNet top-1 validation set accuracy % as precision of activations
(A) and weight(W) changes. All results are with end-to-end training of the
network from scratch. $-$ is a data-point we did not experiment for. Table 2:
AlexNet 2x-wide top-1 validation set accuracy % as precision of activations
(A) and weights (W) changes.

To re-gain the model accuracy while working with reduced-precision operands,
we increase the number of filter maps in a layer. Although the number of raw
compute operations increase with widening the filter maps in a layer, the bits
required per compute operation is now a fraction of what is required when
using full-precision operations. As a result, with appropriate hardware
support, one can significantly reduce the dynamic memory requirements, memory
bandwidth, computational energy and speed up the training and inference
process.

Our widening of filter maps is inspired from Wide ResNet [24] work where the
depth of the network is reduced and width of each layer is increased (the
operand precision is still FP32). Wide ResNet requires a re-design of the
network architecture. In our work, we maintain the depth parameter same as
baseline network but widen the filter maps. We call our approach WRPN - wide
reduced-precision networks. In practice, we find this scheme to be very simple
and effective \- starting with a baseline network architecture, one can change
the width of each filter map without changing any other network design
parameter or hyper-parameters. Carefully reducing precision and simultaneously
widening filters keeps the total compute cost of the network under or at-par
with baseline cost.111Compute cost is the product of the number of FMA
operations and the sum of width of the activation and weight operands.

Table 2 reports the accuracy of AlexNet when we double the number of filter
maps in a layer. With doubling of filter maps, AlexNet with 4-bits weights and
2-bits activations exhibits accuracy at-par with full-precision networks.
Operating with 4-bits weights and 4-bits activations surpasses the baseline
accuracy by 1.44%. With binary weights and activations we better the accuracy
of XNOR-NET [17] by 4%.

When doubling the number of filter maps, AlexNet’s raw compute operations grow
by 3.9x compared to the baseline full-precision network, however by using
reduced-precision operands the overall compute complexity is a fraction of the
baseline. For example, with 4b operands for weights and activations and 2x the
number of filters, reduced-precision AlexNet is just 49% of the total compute
cost of the full-precision baseline (compute cost comparison is shown in Table
3).

floatrowsep=qquad, captionskip=2pt  32b A 8b A 4b A 2b A 1b A 32b W 3.9x 2.4x
2.2x 2.1x 2.0x 8b W 2.4x 1.0x 0.7x 0.6x 0.6x 4b W 2.2x 0.7x 0.5x 0.4x 0.3x 2b
W 2.1x 0.6x 0.4x 0.2x 0.2x 1b W 2.0x 0.6x 0.3x 0.2x 0.1x

Table 3: Compute cost of AlexNet 2x-wide vs. 1x-wide as precision of
activations (A) and weights (W) changes.

We also experiment with other widening factors. With 1.3x widening of filters
and with 4-bits of activation precision one can go as low as 8-bits of weight
precision while still being at-par with baseline accuracy. With 1.1x wide
filters, at least 8-bits weight and 16-bits activation precision is required
for accuracy to match baseline full-precision 1x wide accuracy. Further, as
Table 3 shows, when widening filters by 2x, one needs to lower precision to at
least 8-bits so that the total compute cost is not more than baseline compute
cost. Thus, there is a trade-off between widening and reducing the precision
of network parameters.

In our work, we trade-off higher number of raw compute operations with
aggressively reducing the precision of the operands involved in these
operations (activation maps and filter weights) while not sacrificing the
model accuracy. Apart from other benefits of reduced precision activations as
mentioned earlier, widening filter maps also improves the efficiency of
underlying GEMM calls for convolution operations since compute accelerators
are typically more efficient on a single kernel consisting of parallel
computation on large data-structures as opposed to many small sized kernels
[24].

##  4 Studies on deeper networks

We study how our scheme applies to deeper networks. For this, we study
ResNet-34 [8] and batch-normalized Inception [9] and find similar trends,
particularly that 2-bits weight and 4-bits activations continue to provide at-
par accuracy as baseline. We use TensorFlow [2] and tensorpack [1] for all our
evaluations and use ILSVRC-12 train and val dataset for analysis.222We will
open-source our implementation of reduced-precision AlexNet, ResNet and batch-
normalized Inception networks.

###  4.1 ResNet

ResNet-34 has 3x3 filters in each of its modular layers with shortcut
connections being 1x1. The filter bank width changes from 64 to 512 as depth
increases. We use the pre-activation variant of ResNet and the baseline top-1
accuracy of our ResNet-34 implementation using single-precision 32-bits data
format is 73.59%. Binarizing weights and activations for all layers except the
first and the last layer in this network gives top-1 accuracy of 60.5%. For
binarizing ResNet we did not re-order any layer (as is done in XNOR-NET). We
used the same hyper-parameters and learning rate schedule as the baseline
network. As a reference, for ResNet-18, the gap between XNOR-NET (1b weights
and activations) and full-precision network is 18% [17]. It is also
interesting to note that top-1 accuracy of single-precision AlexNet (57.20%)
is lower than the top-1 accuracy of binarized ResNet-34 (60.5%).

floatrowsep=qquad, captionskip=2pt  Width Precision Top-1 Acc. % Compute cost
1x wide 32b A, 32b W 73.59 1x 1b A, 1b W 60.54 0.03x 2x wide 4b A, 8b W 74.48
0.74x 4b A, 4b W 74.52 0.50x 4b A, 2b W 73.58 0.39x 2b A, 4b W 73.50 0.39x 2b
A, 2b W 73.32 0.27x 1b A, 1b W 69.85 0.15x 3x wide 1b A, 1b W 72.38 0.30x

Table 4: ResNet-34 top-1 validation accuracy % and compute cost as precision
of activations (A) and weights (W) varies.

We experimented with doubling number of filters in each layer and reduce the
precision of activations and weights. Table 4 shows the results of our
analysis. Doubling the number of filters and 4-bits precision for both weights
and activations beats the baseline accuracy by 0.9%. 4-bits activations and
2-bits (ternary) weights has top-1 accuracy at-par with baseline. Reducing
precision to 2-bits for both weights and activations degrades accuracy by only
0.2% compared to baseline.

Binarizing the weights and activations with 2x wide filters has a top-1
accuracy of 69.85%. This is just 3.7% worse than baseline full-precision
network while being only 15% of the cost of the baseline network. Widening the
filters by 3x and binarizing the weights and activations reduces this gap to
1.2% while the 3x wide network is 30% the cost of the full-precision baseline
network.

Although 4-bits precision seems to be enough for wide networks, we advocate
for 4-bits activation precision and 2-bits weight precision. This is because
with ternary weights one can get rid of the multipliers and use adders
instead. Additionally, with this configuration there is no loss of accuracy.
Further, if some accuracy degradation is tolerable, one can even go to binary
circuits for efficient hardware implementation while saving 32x in bandwidth
for each of weights and activations compared to full-precision networks. All
these gains can be realized with simpler hardware implementation and lower
compute cost compared to baseline networks.

To the best of our knowledge, our ResNet binary and ternary (with 2-bits or
4-bits activation) top-1 accuracies are state-of-the-art results in the
literature including unpublished technical reports (with similar data
augmentation [14]).

###  4.2 Batch-normalized Inception

We applied WRPN scheme to batch-normalized Inception network [9]. This network
includes batch normalization of all layers and is a variant of GoogleNet [20]
where the 5x5 convolutional filters are replaced by two 3x3 convolutions with
up to 128 wide filters. Table 5 shows the results of our analysis. Using
4-bits activations and 2-bits weight and doubling the number of filter banks
in the network produces a model that is almost at-par in accuracy with the
baseline single-precision network (0.02% loss in accuracy). Wide network with
binary weights and activations is within 6.6% of the full-precision baseline
network.

floatrowsep=qquad, captionskip=2pt  Width Precision Top-1 Acc. % Compute cost
1x wide 32b A, 32b W 71.64 1x 2x wide 4b A, 4b W 71.63 0.50x 4b A, 2b W 71.61
0.38x 2b A, 2b W 70.75 0.25x 1b A, 1b W 65.02 0.13x

Table 5: Batch-normalized Inception top-1 validation accuracy % and compute
cost as precision of activations (A) and weights (W) varies.

##  5 Hardware friendly quantization scheme

We adopt the straight-through estimator (STE) approach in our work [3]. When
quantizing a real number to $k$-bits, the ordinality of the set of quantized
numbers is $2^{k}$. Mathematically, this small and finite set would have zero
gradients with respect to its inputs. STE method circumvents this problem by
defining an operator that has arbitrary forward and backward operations.

Prior works using the STE approach define operators that quantize the weights
based on the expectation of the weight tensors. For instance, TWN [12] uses a
threshold and a scaling factor for each layer to quantize weights to ternary
domain. In TTQ [27], the scaling factors are learned parameters. XNOR-NET
binarizes the weight tensor by computing the sign of the tensor values and
then scaling by the mean of the absolute value of each output channel of
weights. DoReFa uses a single scaling factor across the entire layer. For
quantizing weights to $k$-bits, where $k>1$, DoReFa uses:

$w^{k}=2*quantize_{k}(\frac{tanh(w_{i})}{2*max(\mid
tanh(w_{i})\mid)}+\frac{1}{2})-1)$ (1)

Here $w_{k}$ is the k-bit quantized version of inputs $w_{i}$ and quantizek is
a quantization function that quantizes a floating-point number $w_{i}$ in the
range $[0,1]$ to a $k$-bit number in the same range. The transcendental $tanh$
operation constrains the weight value to lie in between $-1$ and $+1$. The
affine transformation post quantization brings the range to $[-1,1]$.

We build on these approaches and propose a much simpler scheme. For quantizing
weight tensors we first hard constrain the values to lie within the range
$[-1,1]$ using min-max operation (e.g. tf.clip$\\_$by$\\_$val when using
Tensorflow [2]). For quantizing activation tensor values, we constrain the
values to lie within the range $[0,1]$. This step is followed by a
quantization step where a real number is quantized into a $k$-bit number. This
is given as, for $k>1$:

$w_{k}=\frac{1}{2^{k-1}-1}round((2^{k-1}-1)*w_{i})\hskip
8.53581pt\quad\text{and}\quad\hskip
8.53581pta_{k}=\frac{1}{2^{k}-1}round((2^{k}-1)*a_{i})$ (2)

Here $w_{i}$ and $a_{i}$ are input real-valued weights and activation tensor
and $w_{k}$ and $a_{k}$ are their quantized versions. One bit is reserved for
sign-bit in case of weight values, hence the use of $2^{k-1}$ for these
quantized values. Thus, weights can be stored and interpreted using signed
data-types and activations using un-signed data-types. With appropriate affine
transformations, the convolution operations (the bulk of the compute
operations in the network during forward pass) can be done using quantized
values (integer operations in hardware) followed by scaling with floating-
point constants (this scaling operation can be done in parallel with the
convolution operation in hardware). When $k=1$, for binary weights we use the
BWN approach [5] where the binarized weight value is computed based on the
sign of input value followed by scaling with the mean of absolute values. For
binarized activations we use the formulation in Eq. 2. We do not quantize the
gradients and maintain the weights in reduced precision format.

For convolution operation when using WRPN, the forward pass during training
(and the inference step) involves matrix multiplication of $k$-bits signed and
$k$-bits unsigned operands. Since gradient values are in 32-bits floating-
point format, the backward pass involves a matrix multiplication operation
using 32-bits and $k$-bits operand for gradient and weight update.

When $k>1$, the hard clipping of tensors to a range maps efficiently to min-
max comparator units in hardware as opposed to using transcendental operations
which are long latency operations. TTQ and DoRefa schemes involve division
operation and computing a maximum value in the input tensor. Floating-point
division operation is expensive in hardware and computing the maximum in a
tensor is an $O(n)$ operation. Additionally, our quantization parameters are
static and do not require any learning or involve back-propagation like TTQ
approach. We avoid each of these costly operations and propose a simpler
quantization scheme (clipping followed by rounding).

###  5.1 Efficiency improvements of reduced-precision operations on GPU, FPGA
and ASIC

In practice, the effective performance and energy efficiency one could achieve
on a low-precision compute operation highly depends on the hardware that runs
these operations. We study the efficiency of low-precision operations on
various hardware targets – GPU, FPGA, and ASIC.

For GPU, we evaluate WRPN on Nvidia Titan X Pascal and for FPGA we use Intel
Arria-10. We collect performance numbers from both previously reported
analysis [16] as well as our own experiments. For FPGA, we implement a DNN
accelerator architecture shown in Figure 3(a). This is a prototypical
accelerator design used in various works (e.g., on FPGA [16] and ASIC such as
TPU [10]). The core of the accelerator consists of a systolic array of
processing elements (PEs) to perform matrix and vector operations, along with
on-chip buffers, as well as off-chip memory management unit. The PEs can be
configured to support different precision – (FP32, FP32), (INT4, INT4), (INT4,
TER2), and (BIN1, BIN1). The (INT4, TER2) PE operates on ternary (+1,0,-1)
values and is optimized to include only an adder since there is no need for a
multiplier in this case. The binary (BIN1, BIN1) PE is implemented using XNOR
and bitcount. Our RTL design targets Arria-10 1150 FPGA. For our ASIC study,
we synthesize the PE design using Intel 14 nm process technology to obtain
area and energy estimates.

Figure 3: Efficiency improvements from low-precision operations on GPU, FPGA
and ASIC.

Figure 3(b) - (g) summarize our analysis. Figure 3(b) shows the efficiency
improvements using first-order estimates where the efficiency is computed
based on number of bits used in the operation. With this method we would
expect (INT4, INT4) and (BIN1, BIN1) to be 8x and 32x more efficient,
respectively, than (FP32, FP32). However, in practice the efficiency gains
from reducing precision depend on whether the underlying hardware can take
advantage of such low-precisions.

Figure 3(c) shows performance improvement on Titan X GPU for various low-
precision operations relative to FP32. In this case, GPU can only achieve up
to $\sim$4x improvements in performance over FP32 baseline. This is because
GPU only provides first-class support for INT8 operations, and is not able to
take advantage of the lower INT4, TER2, and BIN1 precisions. On the contrary,
FPGA can take advantage of such low precisions, since they are amenable for
implementations on the FPGA’s reconfigurable fabric.

Figure 3(d) shows that the performance improvements from (INT4, INT4), (INT4,
TER2), and (BIN1, BIN1) track well with the first-order estimates from Figure
3(b). In fact, for (BIN1, BIN1), FPGA improvements exceed the first-order
estimate. Reducing the precision simplifies the design of compute units and
lower buffering requirements on FPGA board. Compute-precision reduction leads
to significant improvement in throughput due to smaller hardware designs
(allowing more parallelism) and shorter circuit delay (allowing higher
frequency). Figure 3(e) shows the performance and performance/Watt of the
reduced-precision operations on GPU and FPGA. FPGA performs quite well on very
low precision operations. In terms of performance/watt, FPGA does better than
GPU on (INT4, INT4) and lower precisions.

ASIC allows for a truly customized hardware implementation. Our ASIC study
provides insights to the upper bound of the efficiency benefits possible from
low-precision operations. Figure 3(f) and 3(g) show improvement in performance
and energy efficiency of the various low-precision ASIC PEs relative to
baseline FP32 PE. As the figures show, going to lower precision offers 2 to 3
orders of magnitude efficiency improvements.

In summary, FPGA and ASIC are well suited for our WRPN approach. At 2x wide,
our WRPN approach requires 4x more total operations than the original network.
However, for INT4 or lower precision, each operation is 6.5x or better in
efficiency than FP32 for FPGA and ASIC. Hence, WRPN delivers an overall
efficiency win.

##  6 Related work

Reduced-precision DNNs is an active research area. Reducing precision of
weights for efficient inference pipeline has been very well studied. Works
like Binary connect (BC) [5], Ternary-weight networks (TWN) [12], fine-grained
ternary quantization [14] and INQ [25] target reducing the precision of
network weights while still using full-precision activations. Accuracy is
almost always degraded when quantizing the weights. For AlexNet on Imagenet,
TWN loses 5% top-1 accuracy. Schemes like INQ, [18] and [14] do fine-tuning to
quantize the network weights and do not sacrifice accuracy as much but are not
applicable for training networks from scratch. INQ shows promising results
with 5-bits of precision.

XNOR-NET [17], BNN [4], DoReFa [26] and TTQ [27] target training as well.
While TTQ targets weight quantization only, most works targeting activation
quantization hurt accuracy. XNOR-NET approach reduces top-1 accuracy by 12%
and DoReFa by 8% when quantizing both weights and activations to 1-bit (for
AlexNet on ImageNet). Further, XNOR-NET requires re-ordering of layers for its
scheme to work. Recent work in [6] targets low-precision activations and
reports accuracy within 1% of baseline with 5-bits precision and logarithmic
(with base $\sqrt{2}$) quantization. With fine-tuning this gap can be narrowed
to be within 0.6% but not all layers are quantized.

Non-multiples of two for operand values introduces hardware inefficiency in
that memory accesses are no longer DRAM or cache-boundary aligned and end-to-
end run-time performance aspect is unclear when using complicated quantization
schemes. We target end-to-end training and inference, using very simple
quantization method and aim for reducing precision without any loss in
accuracy. To the best of our knowledge, our work is the first to study
reduced-precision deep and wide networks, and show accuracy at-par with
baseline for as low a precision as 4-bits activations and 2-bits weights. We
report state of the art accuracy for wide binarized AlexNet and ResNet while
still being lower in compute cost.

##  7 Conclusions

We present the Wide Reduced-Precision Networks (WRPN) scheme for DNNs. In this
scheme, the numeric precision of both weights and activations are
significantly reduced without loss of network accuracy. This result is in
contrast to many previous works that find reduced-precision activations to
detrimentally impact accuracy; specifically, we find that 2-bit weights and
4-bit activations are sufficient to match baseline accuracy across many
networks including AlexNet, ResNet-34 and batch-normalized Inception. We
achieve this result with a new quantization scheme and by increasing the
number of filter maps in each reduced-precision layer to compensate for the
loss of information capacity induced by reducing the precision.

We motivate this work with our observation that full-precision activations
contribute significantly more to the memory footprint than full-precision
weight parameters when using mini-batch sizes common during training and
cloud-based inference; furthermore, by reducing the precision of both
activations and weights the compute complexity is greatly reduced (40% of
baseline for 2-bit weights and 4-bit activations).

The WRPN quantization scheme and computation on low precision activations and
weights is hardware friendly making it viable for deeply-embedded system
deployments as well as in cloud-based training and inference servers with
compute fabrics for low-precision. We compare Titan X GPU, Arria-10 FPGA and
ASIC implementations using WRPN and show our scheme increases performance and
energy-efficiency for iso-accuracy across each. Overall, reducing the
precision allows custom-designed compute units and lower buffering
requirements to provide significant improvement in throughput.

## References

  * [1] https://github.com/ppwwyyxx/tensorpack.

  * [2] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  Software available from tensorflow.org.
  * [3] Y. Bengio, N. Léonard, and A. C. Courville.  Estimating or propagating gradients through stochastic neurons for conditional computation.  CoRR, abs/1308.3432, 2013.
  * [4] M. Courbariaux and Y. Bengio.  Binarynet: Training deep neural networks with weights and activations constrained to +1 or -1.  CoRR, abs/1602.02830, 2016.
  * [5] M. Courbariaux, Y. Bengio, and J. David.  Binaryconnect: Training deep neural networks with binary weights during propagations.  CoRR, abs/1511.00363, 2015.
  * [6] B. Graham.  Low-precision batch-normalized activations.  CoRR, abs/1702.08231, 2017.
  * [7] S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan.  Deep learning with limited numerical precision.  CoRR, abs/1502.02551, 2015.
  * [8] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  CoRR, abs/1512.03385, 2015.
  * [9] S. Ioffe and C. Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  CoRR, abs/1502.03167, 2015.
  * [10] N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, R. Boyle, P.-l. Cantin, C. Chao, C. Clark, J. Coriell, M. Daley, M. Dau, J. Dean, B. Gelb, T. Vazir Ghaemmaghami, R. Gottipati, W. Gulland, R. Hagmann, C. R. Ho, D. Hogberg, J. Hu, R. Hundt, D. Hurt, J. Ibarz, A. Jaffey, A. Jaworski, A. Kaplan, H. Khaitan, A. Koch, N. Kumar, S. Lacy, J. Laudon, J. Law, D. Le, C. Leary, Z. Liu, K. Lucke, A. Lundin, G. MacKean, A. Maggiore, M. Mahony, K. Miller, R. Nagarajan, R. Narayanaswami, R. Ni, K. Nix, T. Norrie, M. Omernick, N. Penukonda, A. Phelps, J. Ross, M. Ross, A. Salek, E. Samadiani, C. Severn, G. Sizikov, M. Snelham, J. Souter, D. Steinberg, A. Swing, M. Tan, G. Thorson, B. Tian, H. Toma, E. Tuttle, V. Vasudevan, R. Walter, W. Wang, E. Wilcox, and D. H. Yoon.  In-Datacenter Performance Analysis of a Tensor Processing Unit.  ArXiv e-prints, Apr. 2017.
  * [11] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1097–1105. Curran Associates, Inc., 2012.
  * [12] F. Li and B. Liu.  Ternary weight networks.  CoRR, abs/1605.04711, 2016.
  * [13] Z. Lin, M. Courbariaux, R. Memisevic, and Y. Bengio.  Neural networks with few multiplications.  CoRR, abs/1510.03009, 2015.
  * [14] N. Mellempudi, A. Kundu, D. Mudigere, D. Das, B. Kaul, and P. Dubey.  Ternary Neural Networks with Fine-Grained Quantization.  ArXiv e-prints, May 2017.
  * [15] D. Miyashita, E. H. Lee, and B. Murmann.  Convolutional neural networks using logarithmic data representation.  CoRR, abs/1603.01025, 2016.
  * [16] E. Nurvitadhi, G. Venkatesh, J. Sim, D. Marr, R. Huang, J. Ong Gee Hock, Y. T. Liew, K. Srivatsan, D. Moss, S. Subhaschandra, and G. Boudoukh.  Can fpgas beat gpus in accelerating next-generation deep neural networks?  In Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA ’17, pages 5–14, New York, NY, USA, 2017\. ACM.
  * [17] M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi.  Xnor-net: Imagenet classification using binary convolutional neural networks.  CoRR, abs/1603.05279, 2016.
  * [18] W. Sung, S. Shin, and K. Hwang.  Resiliency of deep neural networks under quantization.  CoRR, abs/1511.06488, 2015.
  * [19] C. Szegedy, S. Ioffe, and V. Vanhoucke.  Inception-v4, inception-resnet and the impact of residual connections on learning.  CoRR, abs/1602.07261, 2016.
  * [20] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. E. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich.  Going deeper with convolutions.  CoRR, abs/1409.4842, 2014.
  * [21] Y. Umuroglu, N. J. Fraser, G. Gambardella, M. Blott, P. H. W. Leong, M. Jahre, and K. A. Vissers.  FINN: A framework for fast, scalable binarized neural network inference.  CoRR, abs/1612.07119, 2016.
  * [22] V. Vanhoucke, A. Senior, and M. Z. Mao.  Improving the speed of neural networks on cpus.  In Deep Learning and Unsupervised Feature Learning Workshop, NIPS 2011, 2011.
  * [23] G. Venkatesh, E. Nurvitadhi, and D. Marr.  Accelerating deep convolutional networks using low-precision and sparsity.  CoRR, abs/1610.00324, 2016.
  * [24] S. Zagoruyko and N. Komodakis.  Wide residual networks.  CoRR, abs/1605.07146, 2016.
  * [25] A. Zhou, A. Yao, Y. Guo, L. Xu, and Y. Chen.  Incremental network quantization: Towards lossless cnns with low-precision weights.  CoRR, abs/1702.03044, 2017.
  * [26] S. Zhou, Z. Ni, X. Zhou, H. Wen, Y. Wu, and Y. Zou.  Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  CoRR, abs/1606.06160, 2016.
  * [27] C. Zhu, S. Han, H. Mao, and W. J. Dally.  Trained ternary quantization.  CoRR, abs/1612.01064, 2016.


# Improving Offline Contextual Bandits with Distributional Robustness

Otmane Sakhi<EMAIL_ADDRESS>,  Louis Faury<EMAIL_ADDRESS>and
Flavian Vasile  Criteo AI LabParisFrance.

(2020)

###### Abstract.

This paper extends the Distributionally Robust Optimization (DRO) approach for
offline contextual bandits laid out in (Faury et al., 2020). Specifically, we
leverage this framework to introduce a _convex_ reformulation of the
Counterfactual Risk Minimization principle introduced in (Swaminathan and
Joachims, 2015a). Besides relying on convex programs, our approach is
compatible with stochastic optimization, and can therefore be readily adapted
to the large data regime. Our approach relies on the construction of
asymptotic confidence intervals for offline contextual bandits through the DRO
framework. By leveraging known asymptotic results of robust estimators, we
also show how to automatically calibrate such confidence intervals, which in
turn removes the burden of hyper-parameter selection for policy optimization.
We present preliminary empirical results supporting the effectiveness of our
approach.

††copyright: none††conference: the ACM RecSys Workshop on Reinforcement
Learning and Robust Estimators for Recommendation Systems; ; ††journalyear:
2020

##  1\. Introduction

##### Contextual Bandits.

The Contextual Bandit (CB) framework is a formalization of an important
sequential decision making problem, with notorious applications in recommender
systems (Li et al., 2010; Valko et al., 2014), mobile health (Tewari and
Murphy, 2017) and clinical trials (Villar et al., 2015). It describes a
repeated game between a decision-maker and an environment. The latter
sequentially reveal sets of available actions to the former, along with some
additional side information (or _context_). Such additional information is
assumed to carry informative signal about the intrinsic values (or _rewards_)
of the actions. Informally, the goal of the decision-maker is to discover an
efficient strategy (or _policy_) to select, given a context, a nearly optimal
action.

##### Batch Learning from Bandit Feedback.

The CB optimization literature can be divided into two streams. The first
studies its _online_ formulation, where the focus lies on the
exploration/exploitation trade-off for _regret_ minimization. This paper is
concerned with the second, known as Batch Learning from Bandit Feedback
(Swaminathan and Joachims, 2015a) (BLBF) and arguably better suited for
applications in real-life situations. The optimization is performed _offline_
and based on historical data, typically obtained by logging the interactions
between an older version of the current policy and the environment. The
learning problem consists in leveraging this data (necessarily biased towards
actions favored by the logged policy) to discover new strategies of greater
performance.

##### Prior work and limitations.

The first step in addressing the BLBF learning problem is to remove the
intrinsic bias introduced by the logging policy (Bottou et al., 2013). This
however can come at the price of building high-variance estimates (Swaminathan
and Joachims, 2015a) for the performance of the current policy, which in turns
can lead to high _post-decision_ regret. To address such challenges, the
authors of (Swaminathan and Joachims, 2015a) introduced the Counterfactual
Risk Minimization (CRM) principle. It combines debiasing through importance
re-weighting (Swaminathan and Joachims, 2015a) with a modified policy-
selection process that penalizes policies with high-variance estimates.
Recently, (Faury et al., 2020) proposed a generalization of the CRM principle
through the Distributionally Robust Optimization (DRO) framework. This led
them to the development of a new BLBF algorithm, obtained through a
specialization of this general framework . However, while the methods
introduced in both (Swaminathan and Joachims, 2015a) and (Faury et al., 2020)
offer some desirable theoretical guarantees for off-line policy optimization,
their respective implementation suffer from important caveats. Namely, they
rely on optimizing _non-convex_ objectives which is notably hard from a
theoretical perspective. Further, these objective are not well-suited for
stochastic optimization (useful when the logged data is large and cannot fit
in memory), as obtaining unbiased stochastic gradients for these objective is
not straight-forward. Finally, they rely on the selection of rather sensitive
hyper-parameters, of which the (approximate) automatic calibration (through
asymptotic arguments, for instance) is unknown.

##### Contributions.

In this paper, we further investigate the DRO framework for offline CB
introduced in (Faury et al., 2020). This leads to a reformulation of the CRM
principle that boils down to solving a convex problem. Further, we exploit
some recent results from the stochastic optimization literature (Namkoong and
Duchi, 2016) to show how to efficiently solve this objective for large logged
datasets. Our approach relies on the construction of asymptotic confidence
intervals for offline CB through the DRO framework. Leveraging known
asymptotic results for DRO we show how to automatically calibrate such
confidence intervals, which in turns remove the need for hyper-parameter
optimization for policy optimization. We validate our approach through
extensive simulations on standard datasets for this task.

##  2\. Preliminaries

##### Notations

In the following $\varphi$ is a real-valued convex function. The notation
$d_{\varphi}$ refers to the f-divergence associated to $\varphi$, and we
denote $\varphi^{\star}(s)=\sup_{x\in\mathbb{R}}(xs-\varphi(x))$ the Fenchel
conjugate of $\varphi$. We will write $1_{n}$ to be the $n$-dimensional vector
which entries are all equal to $1/n$. For any positive integer $m$,
$\Delta_{m}$ denotes the $m$-dimensional simplex.

##### Setting

In the following, we will use $x\in\mathcal{X}$ to denote a context and
$a\in[K]$ an action, where $K$ denotes the number of available actions. Given
a context $x$, each action is associated with a cost111We make this assumption
for ease of exposition. It can be explicitly enforced by re-scaling the cost
function. $c(x,a)\in[-1,0]$, with the convention that better actions have
smaller cost. The cost function $c$ is unknown. A decision maker is
represented by its policy $\pi$ which maps each context $x\in\mathcal{X}$ to
$\Delta_{K}$. Assuming that the contexts are stochastic and follow a unknown
distribution $\nu$, we define the _risk_ of the policy $\pi$ as the expected
cost one suffers when playing actions according to $\pi$:

$\displaystyle\textnormal{Risk}(\pi)=\mathbb{E}_{x\sim\nu,a\sim\pi(x)}\left[c(x,a)\right].$

The learning problem is to find a policy $\pi$ with smallest risk. In most
real world problems, it is not reasonable to expect having the luxury of
testing out several policies to compare their empirical risk and retain
whichever policy has the smallest. This issue is usually circumvented by
forecasting the risk of a given policy thanks to some existing interaction
data. This is formalized through a _logging policy_ $\pi_{0}$ which has
already been deployed in the environment (e.g a previous version of a
recommender system that the practitioner is trying to improved) for which we
assume we have the history
$\mathcal{H}_{n}=\left\\{x_{i},a_{i}\sim\pi_{0}(x_{i}),\pi_{0}(x_{i},a_{i}),c(a_{i},x_{i})\right\\}_{i\in[n]}$.
Based on this data, one can build an unbiased (under mild assumptions)
estimator of the risk of any policy $\pi$ through the use of importance
weights (Rosenbaum and Rubin, 1983):

$\displaystyle\textnormal{Risk}_{n}(\pi):=\frac{1}{n}\sum_{i=1}^{n}\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})\quad\text{where
}\quad w_{\pi}(x,a):=\pi(x,a)/\pi_{0}(x,a),$

commonly referred to as the IPS (Inverse Propensity Scoring) risk.

##### Counterfactual Risk Minimization

Unfortunately, the IPS estimator has potentially high variance, depending on
the disparity between $\pi$ and $\pi_{0}$ (Swaminathan and Joachims, 2015a,
Section 4). Hence, directly sorting candidate policies thanks to their IPS
risk is hazardous (as it boils down to comparing estimators with potentially
high and different variances) and is known to be sub-optimal. To avoid this
caveat, (Swaminathan and Joachims, 2015a) proposed to add an _empirical
variance_ term to the IPS risk in order to penalize policies with high-
variance estimates. Coined Counterfactual Risk Minimization (CRM), this
principle suggest optimizing for the policy which minimizes:

(1)
$\displaystyle\textnormal{Risk}_{n}^{\lambda}(\pi)=\textnormal{Risk}_{n}(\pi)+\lambda\sqrt{\frac{\widehat{\text{Var}}_{n}(\pi)}{n}}\,,$

where $\lambda$ is a tunable hyper-parameter and
$\widehat{\text{Var}}_{n}(\pi)=\frac{1}{n-1}\sum_{i=1}^{n}\Big{(}\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})-\textnormal{Risk}_{n}(\pi)\Big{)}^{2}$
is the empirical variance of $\textnormal{Risk}_{n}(\pi)$. This policy
selection process is based on _variance-sensitive_ confidence intervals for
the true risk obtained via empirical Bernstein bounds (Maurer and Pontil,
2009).

##### Generalization through DRO

Based on a similar intuition, (Faury et al., 2020) recently introduced the
idea of using Distributionally Robust Optimization (DRO) tools for this policy
optimization problem. Formally, they showed that for a particular class of
$\varphi$-divergence, the robust risk:

(2)
$\displaystyle\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\epsilon):=\sup_{q\in\Delta_{n}}\left\\{\sum_{i=1}^{n}q_{i}\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})\quad\text{s.t}\quad
d_{\varphi}(q,1_{n})\leq\epsilon\right\\}$

is a variance-sensitive (asymptotic) upper-bound for the true risk. It is
therefore well-suited for the policy optimization task, and actually
generalizes (in some sense) the CRM approach (Faury et al., 2020, Lemma 3).
For the KL-divergence, the robust risk has a closed-formed which can be
directly minimized (Faury et al., 2020, Lemma 4):

$\displaystyle\textnormal{RobustRisk}_{n}^{\text{KL}}(\pi,\epsilon)=\sum_{i=1}^{n}\frac{\exp(\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})/\gamma)}{\sum_{j}\exp(\omega_{\pi}(x_{j},a_{j})c(x_{j},a_{j})/\gamma)}\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})$

with $\gamma$ being a tunable hyper-parameter.

##### Limitations and contributions

The variance penalization of the IPS objective and its DRO generalization
benefit from solid theoretical justifications, and result in better policy
optimization algorithms. These algorithms, that were proven to outperform the
simple IPS objective (Swaminathan and Joachims, 2015a; Faury et al., 2020) can
still be improved as they suffer from important limitations: (1) Contrary to
the IPS objective, which is linear (and therefore convex) in $\pi$, both the
initial CRM objective (adding a square root variance penalization) and the DRO
objective (as it was introduced in (Faury et al., 2020)) break this convexity.
This results in ill-posed optimization programs, which potentially hinders the
statistical benefits brought by such methods. (2) Another important limitation
of such objectives is their scalability to large datasets. Both formulations
are not well-adapted to stochastic gradient descent algorithms, as obtaining
unbiased stochastic gradients of their related objectives is not-
straightforward. For instance, the algorithm introduced in (Faury et al.,
2020) works only in the batch setting as the adversary distribution needs all
the data to be normalized. (Swaminathan and Joachims, 2015a) suggested a
relaxation of the CRM objective amenable to stochastic gradients, however only
applicable in the case of exponential policies. Their approach consists in a
majorization-minimization strategy, and still requires to go through the whole
logged dataset once in a while. (3) These algorithms also come with hyper-
parameters that need careful tuning as their choice drastically impact the
performance of the obtained policy, making the whole optimization procedure
even harder. (Swaminathan and Joachims, 2015a) treats $\lambda$, the weight of
the variance penalty, as a hyper-parameter, while (Faury et al., 2020) treat
$\epsilon$, the maximum distance between the adversarial and the nominal
distribution as a hyper-parameter as well. To sum-up, both algorithms are
deemed rather impractical in real life, as they have a non convex loss surface
to optimize, are not applicable to huge datasets and need consequent hyper-
parameter tuning. This work tries to circumvent these limitations through a
more careful treatment of the DRO formulation, leading to general algorithms
that treat all these caveats in a well defined and unified framework.

##  3\. Policy Evaluation and Optimization

###  3.1. Policy Evaluation: Confidence Intervals

Divergence | $\boldsymbol{\varphi(t)}$ | $\boldsymbol{D_{\varphi}(q||p)}$ | $\boldsymbol{\varphi^{*}(s)}$
---|---|---|---
Chi-Square | $(t-1)^{2}$ | $\sum_{i=1}^{n}\frac{(q_{i}-p_{i})^{2}}{p_{i}}$ | $\left\\{\begin{aligned} &s+s^{2}/4\quad&s\geq-2\\\ &-1\quad&s\leq-2\end{aligned}\right.$
Kullback-Leibler | $t\log t-t+1$ | $\sum_{i=1}^{n}q_{i}\log(q_{i}/p_{i})$ | $e^{s}-1$
Burg entropy | $-\log t+t-1$ | $\sum_{i=1}^{n}p_{i}\log(p_{i}/q_{i})$ |  $-\log(1-s)$, $s<1$
Hellinger distance | $(\sqrt{t}-1)^{2}$ | $\sum_{i=1}^{n}\left(\sqrt{p_{i}}-\sqrt{q_{i}}\right)^{2}$ |  $\frac{s}{1-s}$, $s\leq 1$
Table 1. Some coherent $\varphi$-divergences and their characterizations.

In this section, we briefly review and discuss how the robust risk can lead to
the construction of confidence intervals for the true risk. This is a crucial
step for policy optimization, as the latter will consist in minimizing the
high-probability upper-bound on the true risk provided by the policy
evaluation procedure. Designing tight confidence interval for the risk can
also be a goal in itself, in order to fully evaluate the potential
benefits/risks of deploying a given policy (e.g provide an offline metric for
A/B testing). In the following, we follow (Faury et al., 2020) and consider
_coherent_ $\varphi$-divergence - i.e we will assume that $\varphi$ satisfies
the conditions of Assumption 1 in (Faury et al., 2020). We provide some
examples of such functions (and their associated divergence measure) in Table
1.

Under such conditions, one can show that the robust risk accounts for the
variance of the IPS risk estimator (Faury et al., 2020, Lemma 2). Further, DRO
can be further leveraged to build asymptotic confidence intervals for the
robust-risk. Indeed, let us introduce the following problem, converse to (2):

(3)
$\displaystyle\textnormal{OptimisticRisk}_{n}^{\varphi}(\pi,\epsilon):=\inf_{q\in\Delta_{n}}\left\\{\sum_{i=1}^{n}q_{i}\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})\quad\text{s.t}\quad
d_{\varphi}(q,1_{n})\leq\epsilon\right\\}.$

We have the following result, extending Lemma 1 of (Faury et al., 2020) and
easily extracted from (Duchi et al., 2016).

###### Proposition 1.

[Asymptotic Confidence Interval] Let $\delta\in[0,1)$. For $\alpha\in(0,1)$
denote $\rho_{\alpha}$ the $(1-\alpha)$-quantile of the one-dimensional
$\chi^{2}$ distribution. Then:

(4)
$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\textnormal{OptimisticRisk}_{n}^{\varphi}(\pi,\frac{\rho_{\delta}}{n})\leq\textnormal{Risk}(\pi)\leq\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\frac{\rho_{\delta}}{n})\right)\geq
1-\delta\,.$

This result states that the interval
$[\textnormal{OptimisticRisk}_{n}^{\varphi}(\pi,\epsilon),\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\epsilon)]$
is a asymptotic $(1-\delta)$ confidence interval for the true risk, when the
size of the ambiguity-set $\epsilon$ is set to $\rho_{\delta}/n$. We will show
in Section 4.1 that despite being asymptotic, this interval is empirically
_tight_ and displays satisfying coverage, motivating its use in real-life
applications. It turns out that the programs for computing the robust and
optimistic risk (Equation (2) and (3), respectively) can be efficiently
solved. We will only review here the computation of the robust risk, however a
similar reasoning holds for the optimistic risk. Notice that the objective in
Equation (2) is linear in the variable $q$, which acts as a re-weighting for
the counterfactual costs. Further, the constraint set
$\\{q\in\Delta_{n}\,|\,d_{\varphi}(q,1_{n})\leq\epsilon\\}$ is convex. The
program is therefore _convex_ and can henceforth be solved efficiently. In
this paper, we will rely on its dual formulation, which is easily solvable and
well-adapted to the stochastic setting. Formally, we rely on the following
result to characterize the robust risk.

###### Lemma 0.

[Dual program for the robust risk] Let:

(5) $\displaystyle
g_{\pi}(\beta,\gamma)=\beta+\gamma\epsilon+\frac{1}{n}\sum_{s=1}^{n}(\gamma\varphi)^{\star}\left(\omega_{\pi}(x_{i},a_{i})c(a_{i},x_{i})-\beta\right)\,,$

where $(\gamma\varphi)^{\star}(s)=\gamma\varphi^{\star}(s/\gamma)$, with the
convention that $(0\varphi)^{\star}(s)=+\infty$ is $s>0$ and $0$ otherwise.
The function $(\pi,\beta,\gamma)\to g_{\pi}(\beta,\gamma)$ is convex and:

(DRO-PE)
$\displaystyle\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\epsilon)=\inf_{\beta,\gamma\geq
0}g_{\pi}(\beta,\gamma)\,.$

This robust program characterization can be extracted from more general
results - see for instance (Ben-Tal et al., 2013, Section 4). We provide a
detailed proof in Appendix A for the sake of completeness. In a few words,
Lemma 3.1 states the the robust risk can be efficiently computed by solving a
two-dimensional convex program. When $n$ is reasonably small (in other words,
when the dataset $\mathcal{H}_{n}$ fits in memory), coordinate descent (with
exact line search) or two-dimensional bisection provide efficient, principled
tools for computing the robust risk. The program (DRO-PE) is also well-suited
for the large-data regime (_e.g_ large $n$) as it naturally adapts to
stochastic optimization. Indeed, the function $g$ (Equation (5)) is composite
and unbiased gradients of this objective are easily obtainable. Stochastic
gradient descent methods (see (Ruder, 2016) for a modern overview) therefore
provide efficient and flexible solutions for this problem (up to some mild
modifications to account for the fact that the $g$ is not smooth for $\gamma$
in a neighborhood of $0$).

To sum-up, we showed here how the DRO method could be used to build confidence
intervals for the true risk, by simply relying on solving convex programs.
This confidence intervals are however asymptotic; we will show in Section 4
that, still, they provide sufficient coverage, while being much tighter than
their finite-time counterparts.

###  3.2. Policy Optimization: Towards a Convex Objective

####  3.2.1. General principle

The CRM principle casts policy optimization in a theoretically sound
framework, and interestingly enough is closely related to the robust risk
defined throughout the paper. Relying on (Duchi et al., 2016), (Faury et al.,
2020) namely showed that the robust risk provides an asymptotic approximation
to the variance regularized empirical risk. The original CRM principle for
policy optimization (Equation (1)) can therefore be rethought as the
minimization of a $\varphi$-robust risk. Using the dual formulation of the
robust risk given in Equation (DRO-PE), the policy optimization objective
becomes:

(DRO-PO)
$\displaystyle\inf_{\pi}\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\epsilon)=\inf_{\pi,\beta,\gamma\geq
0}g_{\pi}(\beta,\gamma)\,.$

Note that as a consequence of Lemma 3.1, this objective is _convex_. It can
therefore be minimized in principled ways, while enjoying similar guarantees
as the original CRM objective. Intuitively, one can expect such an important
transformation of the optimization properties of the policy improvement
objective to lead to greater practical performances. The most natural way to
solve the policy improvement objective (DRO-PO) is through plain gradient
descent. Indeed, a valid strategy consists in feeding gradients of the
function $(\beta,\gamma,\pi)\to g_{\pi}(\beta,\gamma)$ to a gradient
optimizer. In our experiments, we found that applying the L-BFGS solver to
this dual program to work best. As for the policy evaluation, the policy
optimization objective (DRO-PO) is particularly adapted when the historic data
is large (i.e $n\gg 1$) and only stochastic gradients can be obtained. For
stochastic optimization, stochastic gradients methods can encounter some
issues (linked to the possible unboundedness of the gradients) which can be
alleviate thanks to specialized methods (Namkoong and Duchi, 2016).

####  3.2.2. Extensions

In the following, we discuss how different estimators can be used and
robustified in the same way as the IPS, for improved performances and without
sacrificing convexity.

##### Variance Reduction

The methods presented so far rely on vanilla IPS. It is well known that this
estimator suffers from large variance which can lead to poor performances -
whatever the policy optimization algorithm used. Fortunately, our method
easily extend to other estimators, so long that they remain convex in $\pi$.
Still, it would be useful to extend our method to estimators that actively
reduce variance. A candidate for this task is the self-normalized importance
sampling estimator of (Swaminathan and Joachims, 2015b). This estimator is
unfortunately not convex in $\pi$, which goes against the efforts undertaken
in this paper to maintain well-behaved optimization tasks. We provide here an
alternative which uses a simple additive control variate (instead of a
multiplicative one). Formally, we rely on the following estimator:

$\displaystyle\text{Risk}_{n,\rho}(\pi)=\frac{1}{n}\sum_{i=1}^{n}\left(c(x_{i},a_{i})-\rho\right)\omega_{\pi}(x_{i},a_{i})+\rho\,.$

A robust version of this estimator easily follows, and enjoys the same convex
properties of the IPS robust risk. The variance-reduction property of the
additive control variate is presented in the following Lemma.

###### Lemma 0.

[Propensity weights as an additive control variate] For all $\rho$,
$\textnormal{Risk}_{n,\rho}(\pi)$ is an unbiased estimator of
$\textnormal{Risk}(\pi)$, achieving a better variance than naive IPS whenever
$0\leq\rho\leq
2\frac{\text{Cov}(\ell_{\pi},\omega_{\pi})}{\mathbb{\mathbf{V}}(\omega_{\pi})}$.
In addition, if the cost is independent of the propensity weights, we obtain
$\rho^{*}=\operatorname{\mathbb{E}}[c]$.

In practice, we do not know how to derive $\rho^{*}$ analytically, however one
can directly use the cost’s empirical mean under $\pi_{0}$.

##### Parametric Policies.

In practice, the actions/contexts space is extremely large and directly
optimizing the objective with respect to the policy (as a
$\mathbb{R}^{|\mathcal{X}|\times K}$ matrix) is unreasonable. In such cases,
policies are parametrized to drastically reduce the complexity of the problem.
This usually breaks convexity, even in the simplest case of log-linear
policies - that is, policies of the form
$\pi_{\theta}(a|x)\propto\exp(\theta^{T}f(x,a))$ for $f(x,a)$ a given joint
feature map. In this case, the objective becomes a negative sum of log-concave
functions resulting in a non-convex optimization surface. Following (Le Roux,
2016), one can bypass this non-convexity by constructing a _tight_ convex
upper bound of the original objective.

###### Lemma 0.

[Convex upper-bound for log-concave policies] Let $\pi_{\theta}$ be a log-
concave (w.r.t $\theta$) policy. For a given $\theta_{0}$, let:

$\displaystyle\textnormal{Risk}_{n}^{\text{up}}(\pi_{\theta})=\frac{1}{n}\sum_{i=1}^{n}\frac{\pi_{\theta_{0}}(a_{i},x_{i})}{\pi_{0}(a_{i},x_{i})}(1+\log[\frac{\pi_{\theta}(a_{i},x_{i})}{\pi_{\theta_{0}}(a_{i},x_{i})}])c(a_{i},x_{i})\,.$

$\textnormal{Risk}_{n}^{\text{up}}(\pi_{\theta})$ is a _convex_ upper bound of
the IPS risk. The closer $\theta_{0}$ to $\theta$, the tighter the upper
bound, with equality at $\theta_{0}=\theta$.

We can use Lemma 3.3 to obtain a proxy of our initial objective, building on
an iterative procedure that only uses convex losses throughout the whole
optimization process. Once again, we can build a robust version of this
estimator which can be efficiently optimized. Note that here, the robust
estimator will be convex w.r.t the parametrization $\theta$ as soon as the
policy in log-concave.

##  4\. Preliminary Results

We here describe some preliminary experimental results, backing up the idea
that an improved optimization landscape for policy optimization naturally
leads to improved practical performances. We work with the four
$\varphi$-divergence presented in Table 1. We employ the classical supervised
to bandit conversion (Agarwal et al., 2014). Formally, denote
$x\in\mathcal{X}$ a given input vector and $y\in\\{0,1\\}^{L}$ its label, and
$\mathcal{D}^{\star}=\\{(x_{1},t_{1}),\ldots,(x_{m},t_{m})\\}$ a given multi-
label dataset. We create the logging policy by training it on a fraction of
$\mathcal{D}^{\star}$. We then create the historic data $\mathcal{H}_{n}$ by
going repeating $P$ times the following procedure: for every $(x_{i},t_{i})$
in the supervised dataset, sample $a_{i}\sim\pi_{0}(x)$ and log the cost
$c(a_{i},x_{i})=\lVert a_{i}-t_{i}\rVert_{1}$. Following (Swaminathan and
Joachims, 2015a), we call $P$ the _replay count_.

###  4.1. DRO Confidence Intervals

We start this experimental section by performing a _sanity check_ on the
(asymptotic) confidence intervals that we based our policy optimization method
on. Formally, we evaluate the finite-time validity of Equation (4). Being
asymptotic, we can safely expect DRO-based confidence intervals to be smaller
than their finite-time counterparts - i.e confidence intervals based on
Hoeffding or empirical Bernstein tail inequalities (see (Thomas et al., 2015)
for their application to policy evaluation). We however wish to check that
they provide reasonable coverage in non-asymptotic regimes. To do so, we train
a policy $\pi$ on a random subset of $\mathcal{D}^{\star}$ and evaluate the
empirical mean coverage and width of DRO-based intervals. In Figure 1, we
present such results on two datasets: Yeast and Scene, taken from the LibSVM
repository and standard for the policy optimization task (Swaminathan and
Joachims, 2015a). The empirical coverageis reported for increasing values of
the replay count $P$, or equivalently for increasing values of the historic
data size $n$. The failure level is set to $\delta=0.95$ in all experiments.
We observe that the DRO- ased confidence interval provide almost exact
$(1-\delta)$ coverage, and it is therefore safe to use them even in the small
data regime. As a side comment, we observe that all four $\varphi$-divergence
lead to very similar results. Finally, we check experimentally that as
expected, the asymptotic DRO-based confidence intervals are by orders of
magnitude smaller than finite-time ones.

(a) Empirical coverage of the true risk for different confidence intervals on
the Yeast dataset.

(b) Empirical coverage of the true risk for different confidence intervals on
the Scene dataset.

Figure 1. Finite-time evaluation (coverage) for asymptotic DRO-based
confidence intervals.

###  4.2. Policy Optimization

We report here some preliminary results for the policy optimization, for which
we strictly follow the experimental procedure of (Swaminathan and Joachims,
2015a). The supervised dataset $\mathcal{D}^{\star}$ is split into three parts
(train, validation and test). A logging policy is train on a random fraction
($=0.1$) of $\mathcal{D}_{*}$ and used to collect the history
$\mathcal{H}_{n}$ by running it through the training data $P=4$ times. For
DRO-based algorithms, the validation set is not used, since no hyper-parameter
needs to be tuned (we use the value recommended by the asymptotic analysis for
$\varepsilon$, with a fixed confidence level at $\delta=0.05$). For POEM and
its stochastic approximation, the parameter $\lambda$ is selected by cross-
validation on the validation data. We report in Figure 2 the risks of the
policy (and their greedy versions) returned by the different algorithms. As in
(Swaminathan and Joachims, 2015a), all policies are parametrized linearly,
with a softmax output activation layer. We present results for both batch
algorithms ($\mathcal{B})$ and their stochastic versions ($\mathcal{S})$.
Results are average over 20 random repetitions.

Algorithm | Risk | Greedy-Risk
---|---|---
POEM-$\mathcal{B}$ | 0.93 (0.06) | 0.91 (0.06)
DRO-$\mathcal{B}$-$\chi^{2}$ |  0.89 (0.06) | 0.87 (0.06)
DRO-$\mathcal{B}$-KL | 0.90 (0.06) | 0.88 (0.06)
DRO-$\mathcal{B}$-Burg | 1.06 (0.06) |  0.85 (0.05)
DRO-$\mathcal{B}$-Hellinger | 1.06 (0.06) | 0.85 (0.05)
POEM-$\mathcal{S}$ |  1.0 (0.05) |  0.97 (0.05)
DRO-$\mathcal{S}$-$\chi^{2}$ | 1.05 (0.06) | 1.02 (0.06)
DRO-$\mathcal{S}$-KL | 1.06 (0.07) | 1.04 (0.07)
DRO-$\mathcal{S}$-Burg | 1.12 (0.05) | 1.08 (0.05)
DRO-$\mathcal{S}$-Hellinger | 1.3 (0.08) | 1.18 (0.07)
(a) Scene dataset. The quantity in parenthesis represent one standard
deviation of the aggregated results.

Algorithm | Risk | Greedy-Risk
---|---|---
POEM-$\mathcal{B}$ | 5.15 (0.07) | 4.34 (0.13)
DRO-$\mathcal{B}$-$\chi^{2}$ | 5.21 (0.05) | 4.38 (0.12)
DRO-$\mathcal{B}$-KL | 5.32 (0.04) | 5.29 (0.11)
DRO-$\mathcal{B}$-Burg |  4.77 (0.07) |  3.74 (0.13)
DRO-$\mathcal{B}$-Hellinger |  4.77 (0.07) |  3.74 (0.13)
POEM-$\mathcal{S}$ |  5.16 (0.05) |  4.62 (0.1)
DRO-$\mathcal{S}$-$\chi^{2}$ | 5.17 (0.06) | 4.71 (0.11)
DRO-$\mathcal{S}$-KL | 5.17 (0.06) | 4.72 ( 0.12)
DRO-$\mathcal{S}$-Burg | 5.17 (0.06) | 4.72 (0.1)
DRO-$\mathcal{S}$-Hellinger | 5.27 (0.06) | 4.71 (0.1)
(b) Yeast dataset. The quantity in parenthesis represent one standard
deviation of the aggregated results.

Figure 2. Policy optimization results.

##  5\. Discussion

For batch algorithms, one can notice that DRO-based methods provide either
similar or better empirical results than POEM on both considered datasets,
while being hyper-parameter free (which is not the case of POEM). On the Yeast
dataset, the improvement is quite significative for two of the four
$\varphi$-divergence (Burg and Hellinger). On the negative side, it seems
there is no consistency in the relative performance of the different
divergences. This is quite troublesome in practice, as to the best of our
knowledge there is no obvious nor preferable choice of divergences given a
dataset. A solution to this problem is probably to cross-validate this choice,
potentially over a continuous parametrization of the divergence considered
here (such as the parameter of a Cressie-Read divergence). Finally, we note
that POEM-$\mathcal{S}$ dominates among the stochastic algorithm considered.
This is however to be nuanced, as this algorithm still needs to load in memory
the entire dataset at every epoch (_e.g._ every time an upper-bound on the
true objective is constructed). This is not the case for DRO-based algorithms.
We also believe that the nonetheless good performances reported here for
stochastic DRO algorithms will turn to be decisive when considering more
complex policies (_e.g_ parametrized by a neural network, where
POEM-$\mathcal{S}$ have been reported to fail). We plan on investigating this
in future work, along with the performance of other robustified estimators
(cf. Lemma 3.2 and 3.3.)

## References

  * (1)
  * Agarwal et al. (2014) Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. 2014\.  Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits. In _International Conference on Machine Learning_. 1638–1646.
  * Ben-Tal et al. (2013) Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. 2013\.  Robust solutions of optimization problems affected by uncertain probabilities.  _Management Science_ 59, 2 (2013), 341–357.
  * Bottou et al. (2013) Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X. Charles, D. Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. 2013\.  Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising.  _Journal of Machine Learning Research_ 14, 65 (2013), 3207–3260.  http://jmlr.org/papers/v14/bottou13a.html
  * Combettes (2018) Patrick L Combettes. 2018\.  Perspective Functions: Properties, Constructions, and Examples.  _Set-Valued and Variational Analysis_ 26, 2 (2018), 247–264.
  * Duchi et al. (2016) John Duchi, Peter Glynn, and Hongseok Namkoong. 2016.  Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach.  _arXiv preprint arXiv:1610.03425_ (2016).
  * Faury et al. (2020) Louis Faury, Ugo Tanielan, Flavian Vasile, Elena Smirnova, and Elvis Dohmatob. 2020\.  Distributionally Robust Counterfactual Risk Minimization. In _Thirty-Fourth AAAI Conference on Artificial Intelligence_.
  * Le Roux (2016) Nicolas Le Roux. 2016\.  Tighter bounds lead to improved classifiers.  _CoRR_ abs/1606.09202 (2016).  arXiv:1606.09202 http://arxiv.org/abs/1606.09202
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010\.  A contextual-bandit approach to personalized news article recommendation. In _Proceedings of the 19th international conference on World Wide Web_. 661–670.
  * Maurer and Pontil (2009) Andreas Maurer and Massimiliano Pontil. 2009.  Empirical Bernstein Bounds and Sample Variance Penalization. In _Proceedings of the 22nd Conference on Learning Theory_.
  * Namkoong and Duchi (2016) Hongseok Namkoong and John C Duchi. 2016.  Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences. In _Advances in Neural Information Processing Systems_. 2208–2216.
  * Rosenbaum and Rubin (1983) Paul R Rosenbaum and Donald B Rubin. 1983.  The central role of the propensity score in observational studies for causal effects.  _Biometrika_ 70, 1 (1983), 41–55.
  * Ruder (2016) Sebastian Ruder. 2016\.  An overview of gradient descent optimization algorithms.  _arXiv preprint arXiv:1609.04747_ (2016).
  * Swaminathan and Joachims (2015a) Adith Swaminathan and Thorsten Joachims. 2015a.  Batch Learning from Logged Bandit Feedback through Counterfactual Risk Minimization.  _Journal of Machine Learning Research_ 16, 52 (2015), 1731–1755.  http://jmlr.org/papers/v16/swaminathan15a.html
  * Swaminathan and Joachims (2015b) Adith Swaminathan and Thorsten Joachims. 2015b.  The Self-Normalized Estimator for Counterfactual Learning. In _Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2_ _(NIPS’15)_. MIT Press, Cambridge, MA, USA, 3231–3239.
  * Tewari and Murphy (2017) Ambuj Tewari and Susan A Murphy. 2017.  From Ads to Interventions: Contextual Bandits in Mobile Health.  In _Mobile Health_. Springer, 495–517.
  * Thomas et al. (2015) Philip S Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. 2015\.  High-Confidence Off-Policy Evaluation. In _Twenty-Ninth AAAI Conference on Artificial Intelligence_.
  * Valko et al. (2014) Michal Valko, Rémi Munos, Branislav Kveton, and Tomáš Kocák. 2014\.  Spectral Bandits for Smooth Graph Functions. In _International Conference on Machine Learning_. 46–54.
  * Villar et al. (2015) Sofía S Villar, Jack Bowden, and James Wason. 2015\.  Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges.  _Statistical science: a review journal of the Institute of Mathematical Statistics_ 30, 2 (2015), 199.

##  Appendix A Proof of Lemma 3.1

See 3.1

###### Proof.

Recall the definition of the robust risk:

(P)
$\displaystyle\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\epsilon):=\sup_{q\in\Delta_{n}}\left\\{\sum_{i=1}^{n}q_{i}\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})\quad\text{s.t}\quad
d_{\varphi}(q,1_{n})\leq\epsilon\right\\}$

where:

$\left\\{\begin{aligned}
&\Delta_{n}=\left\\{p\in\mathbb{R}_{n}^{+}\,\middle|\sum_{i=1}^{n}p_{i}=1\right\\}\\\
&1_{n}=\frac{1}{n}(1\ldots 1)^{\transp}\in\mathbb{R}^{n}\\\
&d_{\varphi}(q,p)=\sum_{i=1}^{n}p_{i}\varphi\left(\frac{q_{i}}{p_{i}}\right)\quad\forall
q\ll p\in\Delta_{n}\end{aligned}\right.$

Note that the program (P) optimizes a linear objective under convex
constraints (since $\varphi$ is convex). Further, when $\epsilon>0$, the
candidate $q=1_{n}$ is _strictly_ feasible. Therefore, Slater’s condition
holds and (P) enjoys strong duality. Writing down its Lagrangian, we obtain
the following equivalence:

$\displaystyle\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\epsilon)$
$\displaystyle=\sup_{q\succeq 0}\inf_{\beta,\gamma\geq
0}\sum_{i=1}^{n}q_{i}\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})+\beta\left(1-\sum_{i=1}^{n}q_{i}\right)+\gamma\left(\epsilon-\frac{1}{n}\sum_{i=1}^{n}\varphi(nq_{i})\right)$
$\displaystyle=\inf_{\beta,\gamma\geq 0}\sup_{q\succeq
0}\sum_{i=1}^{n}q_{i}\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})+\beta\left(1-\sum_{i=1}^{n}q_{i}\right)+\gamma\left(\epsilon-\frac{1}{n}\sum_{i=1}^{n}\varphi(nq_{i})\right)$
(6) $\displaystyle=\inf_{\beta,\gamma\geq
0}\beta+\gamma\epsilon+\frac{1}{n}\sum_{i=1}^{n}\sup_{q_{i}\geq
0}\left\\{(nq_{i})\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})-\gamma\varphi(nq_{i})\right\\}$

where the first equality is a consequence of strong duality, and the second is
obtained through simple re-arranging. If $\gamma\neq 0$, easy computations
lead to:

$\displaystyle\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\epsilon)$
$\displaystyle=\inf_{\beta,\gamma\geq
0}\beta+\gamma\epsilon+\frac{\gamma}{n}\sum_{i=1}^{n}\sup_{q_{i}\geq
0}\left\\{(nq_{i})\frac{\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})}{\gamma}-\varphi(nq_{i})\right\\}$
$\displaystyle=\inf_{\beta,\gamma\geq
0}\beta+\gamma\epsilon+\frac{\gamma}{n}\sum_{i=1}^{n}\varphi^{\star}\left(\frac{\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})}{\gamma}\right)$

by using the definition of $\varphi^{\star}$. The limit conditions announced
in the Lemma are easily checked by computing the dual function when
$\gamma=0$. We therefore obtain the equality announced by using the definition
of $g_{\pi}$:

$\displaystyle\textnormal{RobustRisk}_{n}^{\varphi}(\pi,\epsilon)=\inf_{\beta,\gamma\geq
0}g_{\pi}(\beta,\gamma)$

The convexity of $g_{\pi}$ can be obtained two ways; (1) by noticing that
$g_{\pi}$ is obtained through convexity-transforming transformations of a
_perspective_ function (Combettes, 2018), or (2) by noticing thanks to
Equation (A) that:

$\displaystyle(\pi,\beta,\gamma)\to\sum_{i=1}^{n}\sup_{q_{i}\geq
0}\left\\{(nq_{i})\omega_{\pi}(x_{i},a_{i})c(x_{i},a_{i})-\gamma\varphi(nq_{i})\right\\}$

is convex as a sum of supremum of linear (and hence convex) functions. ∎