Andrew Chee

Sébastien Loustau

Sébastien Loustau Sparsity

Sparsity Regret bounds for XNOR-nets++

come

Introduction

Deep learning is nowadays the most used technique to address the problem of supervised learning. It is extensively developed in Computer Vision, Natural Language Processing or communication networks, where very often the architecture of the deep net is based on a cascade of convolutions and non-linear activations. Indeed, CNNs are based on a very reduced set of computations (essentially convolutions and activations), and can be used to cover numerous application domains (e.g., audio, video, biosignals). Many tasks can be automated by convolutional neural networks, from the vanilla image classification problem (see [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]) to more complex tasks such as text classification (see [START_REF] Zhang | Character-level convolutional networks for text classification[END_REF]), long-range temporal dependencies such as speech generation (see [START_REF] Van Den Oord | Wavenet: A generative model for raw audio[END_REF]), or even in unsupervised task such as object detection (see [START_REF] Shaoqing Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF]) or graph embeddings (see [START_REF] Thomas | Semi-supervised classification with graph convolutional networks[END_REF]). Despite the attractive qualities of CNNs, and the universality of architectures emerging now to solve a broad range of tasks (see [START_REF] Kokkinos | Ubernet: Training a universal convolutional neural network for low-, mid-, and high-level vision using diverse datasets and limited memory[END_REF]), CNNs are still prohibitively expensive to deploy in a tight constrained environment such as micro-computer, in the context of high-resolution datasets or more generally on low-power devices since they need power-hungry General Purpose -Graphic Processing Units (GP-GPUs). In the recent literature, a natural approach for reducing the computational effort of CNNs (training of smaller and faster models) is through binarized networks.

The idea behind binarized neural network is to approximate real-valued convolutions with low bitwidth operations. In [START_REF] Courbariaux | Binaryconnect: Training deep neural networks with binary weights during propagations[END_REF] (or more recently in [START_REF] Tang | How to train a compact binary neural network with high accuracy[END_REF]), CNNs are trained with binary weights during the forward and backward propagations, while retaining precision of the stored weights in which gradients are accumulated, whereas in [START_REF] Courbariaux | Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1[END_REF][START_REF] Rastegari | Xnor-net: Imagenet classification using binary convolutional neural networks[END_REF], or more recently in [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF], both filters and signal activations are binarized, leading to the so-called XNOR-nets where convolutions are approximated using primarily binary operations. The latter results in 58x faster convolutional operations and offer the possibility of running state-of-the-art networks on CPUs (rather than GPUs) in real-time. Moreover, binarizing the input signals also provide a significant gain in the overall memory consumption, especially for large batch sizes. Finally, since binarized networks can lead to poor approximations of real-valued convolutions, [START_REF] Li | Ternary weight networks[END_REF] proposes to use ternary weight networks whereas [START_REF] Zhou | Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients[END_REF] proposes a more flexible low bitwidth approach using different bitwidth weights for weights (1-bit weights), activations (2-bit activations), and gradients (see below). [START_REF] Sung | Resiliency of deep neural networks under quantization[END_REF] studies the effects of quantization for convolutional neural networks when the network complexity is changed. It shows a better resilience of deep nets when the number of layers is big. Finally, as low bitwidth convolutions can be implemented efficiently in standard CPU or GPU, but also on tight constrained field-programmable gate arrays (FPGAs) or even on Application Specific Integrated Circuits (ASICs), binarized networks are exploited on each specialized computer hardware. It leads in [START_REF] Andri | Yodann: An architecture for ultralow power binary-weight cnn acceleration[END_REF] to a energy-efficient and scalable CNN accelerator on ASICs, whereas [START_REF] Shawahna | Fpga-based accelerators of deep learning networks for learning and classification: A review[END_REF] proposes a recent survey on hardware accelerators that uses FPGAs.

It is also important to notice the recent growing interest for other main approaches to alleviate the computation of deep neural networks. Standard pruning methods (see [START_REF] Michael | Skeletonization: A technique for trimming the fat from a network via relevance assessment[END_REF] for the original paper, or more recently [START_REF] Yang | Deep fried convnets[END_REF]) first train a feedforward or a convolutional neural network to convergence, and then network connections and / or neurons are pruned only subsequently. These techniques are applied and fined-tuned after training the entire network. Recent advances propose two different strategies in order to avoid the training of the entire network.

It leads to significant improvements and accelerate both training and inference since the overall skeletonization is estimated before or during the training. One can prune the network at initialization, by estimating the important weights for a given task (see [START_REF] Lee | Snip: Singleshot network pruning based on connection sensitivity[END_REF][START_REF] Wang | Picking winning tickets before training by preserving gradient flow[END_REF] for moderate pruning levels up to 95%, or more recently [START_REF] Pau De | Progressive skeletonization: Trimming more fat from a network at initialization[END_REF] for higher level of compression, up to 99.5%). Another promising strategy is to select the connectivity of the network during the training. Interestingly, theoretical guarantees are proposed in [START_REF] Bellec | Deep rewiring: Training very sparse deep networks[END_REF] for an adaptive procedure selecting the architecture during training. It could be seen as a form of architecture designing, from the most general purpose of automated machine learning (AutoML, see [START_REF] He | Automl: A survey of the stateof-the-art[END_REF]) to the problem of aggregation and design of efficient neural networks in terms of latency, memory size or carbon footprint, which lead finally to search for device-specific CNNs. As a seminal example, [START_REF] Wu | Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search[END_REF] proposes a neural architecture search called FBNet to construct hardware efficient CNNs for mobile phones (see also [START_REF] Tan | Mnasnet: Platform-aware neural architecture search for mobile[END_REF]). The so-called Neural Architecture Search (NAS) uses a stochastic generator of architectures (that is a recurrent neural network named the controller) and train the proposed network with Reinforcement Learning (see for instance [START_REF] Zoph | Neural architecture search with reinforcement learning[END_REF] for a nice introduction). Another approach is proposed in [START_REF] Veniat | Learning time/memory-efficient deep architectures with budgeted super networks[END_REF] where several budgeted super networks are selected to predict well in less than 100 milliseconds or to learn efficient models in terms of memory (for instance models that fit in a 50mb memory). More recently, [START_REF] Wan | Fbnetv2: Differentiable neural architecture search for spatial and channel dimensions[END_REF] expends the search space to number of filters and channels dimension without prohibitive memory and computational cost with FBNetv2. Finally, [START_REF] Ruiz | Distilled hierarchical neural ensembles with adaptive inference cost[END_REF] uses another approach based on a hierarchical neural ensemble to aggregate neural network blocks efficiently and control dynamically the inference latency depending on external constraints. However, despite a growing interest, the study of computational-efficient deep neural networks is a work in progress in the community and affects several aspects of CNNs processing (i.e., training versus inference) as well as different key metrics and concepts to compare the various architectures, design and hardware (see [START_REF] Sze | Efficient processing of deep neural networks: A tutorial and survey[END_REF] for a survey of deep nets processing). In this processing, power and energy consumption account for all aspects of the system including the size of the network, the hardware itself (such as CPUs, GPUs, FPGAs or ASICs) and the potentially external memory access. Recently open sources libraries have been proposed in order to evaluate globally the carbon footprint of deep learning algorithms as well as specific studies of particular algorithms. It has been shown for instance in [START_REF] Parcollet | The Energy and Carbon Footprint of Training End-to-End Speech Recognizers[END_REF] that significant gain in carbon emmission could be done without endowing the generalization performances. However, open sources available librairies in [START_REF] Lacoste | Quantifying the carbon emissions of machine learning[END_REF][START_REF] Henderson | Towards the systematic reporting of the energy and carbon footprints of machine learning[END_REF][START_REF] Lannelongue | Green algorithms: Quantifying the carbon emissions of computation[END_REF][START_REF] Anthony | Carbontracker: Tracking and predicting the carbon footprint of training deep learning models[END_REF][START_REF] Patterson | Carbon emissions and large neural network training[END_REF] are designed for massive usage of a large community of researchers and then constrain the estimations with strong hypothesis.

As a consequence, we loose the specific impact of different hardware platform, as well as the cooling technique of the data center used for extensive computations. Moreover, carbon footprint are usually based on national coefficient.

Finally, as discussed in [START_REF] Cao | Towards accurate and reliable energy measurement of NLP models[END_REF], electric consumption based on a software estimation do not reflect the entire consumption of the system. Some contributions (see [START_REF] Crefeda | Synergy: An energy measurement and prediction framework for convolutional neural networks on jetson tx1[END_REF][START_REF] Cao | Towards accurate and reliable energy measurement of NLP models[END_REF]) propose to conduct energy measurement experiments but are limited to a particular hardware distributor and specific algorithms.

With this in mind, we have the long term objective to train algorithms that reach a theoretical-based trade-off between accuracy of the network and power or energy consumption. For that purpose, we need to design penalties that cover precise attributes of the network such as -of course -the network architecture (including number of layers, number of filters, filter sizes, and number of channels), the number of non-zero weights (mainly for storage requirements) or the number of MACs (multiply-accumulate operations), but also metrics from the hardware design, depending on the number of cores or the amount of on-chip storage, the latency and throughput (depending on the batch size), the memory access and finally the power and energy consumption.

Finally, it is important to note that continuous weights are required for Stochastic Gradient Descent (SGD) to work at all since SGD computes small mooves and explores a real-valued space of parameters. Therefore, it is hard to promote low bitwidth for gradient updates (see a 6-bits attempt in [START_REF] Zhou | Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients[END_REF]). In this paper, as well as in the companion paper [START_REF] Chee | Learning with bot -bregman and optimal transport divergences[END_REF], we use the PAC-Bayesian paradigm to learn distribution over a set of deep nets. It changes drastically the optimization procedure and lead to alternative to stochastic gradient updates for trainingbinarized -architectures. In the present paper, we use standard Kullback-Leibler divergences to get penalties proportional to the size of the network in terms of non-zero weights. In the companion paper [START_REF] Chee | Learning with bot -bregman and optimal transport divergences[END_REF] one offers more flexibility thanks to the introduction of Bregman divergences and optimal transport. It gives a new extension of the usual PAC-Bayesian theory presented in this paper and can be applied to deep learning with convolutional architectures in order to explore new strategies for penalizing training and/or inference complexity related with environmental impact. These theoretical based approaches could be applied to several data sources (images, time series, and graphs) and both generic and low bitwidth convolutional neural networks (see below), in order to design adaptive algorithms that fits dynamically to the size of the data, the difficulty of the problem and the desire environmental constraints.

Context and notations 2.1 Deep nets architectura

In this paper, we are interested in convolutional neural networks. From the learning perspective, a CNN is uniquely determined by a potentially huge set of p weights w ∈ W p ⊂ R p , where W depends on the bitwidth of the system. In what follows, we consider W = R for standard deep nets, as well as W = {-1, 1} for binary XNOR-nets (the intermediate case W = {-b, . . . , b} for some integer b > 1 is not considered for simplicity). Then, we introduce a parametric set of decisions

G := {g w : X → Y, w ∈ W p },
where X is the input of the neural network (also called the input space of descriptors, such as images, time series, or graphs, see below), and Y is the output of the network (for instance a vector of probabilities in classification, or a scalar in a regression framework). We want to learn a set of weights w := (w l , b l ) k l=1 , where each couple (w l , b l ) denotes the weights of layer l of the convolutional neural network g w (•) defined as:

g w (x) = softmax ((w k * σ(w k-1 * • • • * σ(w 1 * x + b 1 ) • • • ) + b k )) , (1)
where w * x is a linear transformation described precisely below as a matrix multiplication and σ(•) is an element-wise non-linear activation such as a rectified linear unit (ReLU in the sequel) defined as σ(x) = max(0, x). In (1), we arbitrarily choose a softmax(•) since we deal in the main theoretical bounds with classification with cross-entropy loss function. Of course other activations at the head of the CNN could be considered, for other learning tasks. In what follows, thanks to the general algorithm presented below, we can choose automatically the number of layers k, as well as the number and size of filters or matrices involved in the linear transformation at each layer. For the sake of simplicity, we fix the number and size of filters at each layer and consider the space of candidate architectures W as the following union:

W := L k=1 N i=1 F j=1 W k(i+1)j , (2)
where L ≥ 1 is the maximal number of layers for g w , N ≥ 1 is the maximum number of filters and F ≥ 2 is the maximum size of filters. We can easily extend the main theoretical results to more complex decision spaces.

In the context of Computer Vision, x ∈ R m represents a m = r 1 × r 2 image (we restrict the number of channels to 1 for simplicity) and given a set of i filters (f u ) i u=1 of size j = s × s, the convolution w * x in (1) corresponds to the matrix product of the filters and a relaxed form of the Toeplitz matrix of input signal x as follows:

w * x :=   w 11 w 12 w 13 w 14 w 21 w 22 w 23 w 24           x 11 x 12 x 21 x 22 x 12 x 13 x 22 x 23 x 21 x 22 x 31 x 32 x 22 x 23 x 32 x 33         ∈ R i×4 ,
where we stand s = 2, d = 2, vertical and horizontal stride is let to 1 with no padding, and r 1 = r 2 = 3 for the sake of simplicity. Note that this representation could be extend to multiple channels and filters with redundant Toeplitz matrices.

Of course this matrix multiplication above corresponds to convolutional layers and could be replaced by a standard matrix multiplication for fully connected layers. Moreover, concerning convolutions, it is also possible to consider similarly time series processing. If the input signal x is a univariate time serie of size m and we have at hand a set of filters, the one-dimensional convolution of x with filters (f u ) i u=1 with i = 2 can be written as a matrix product w * x as follows:

w * x :=   w 11 w 12 w 21 w 22     x 1 x 2 x 3 x 2 x 3 x 4   ∈ R i×3
where m = 4, stride is let to 1 with no padding. Finally, for completeness, we can also mention extensions of CNNs to graph real-world applications (see [START_REF] Bruna | Spectral networks and locally connected networks on graphs[END_REF],

[42], [START_REF] Thomas | Semi-supervised classification with graph convolutional networks[END_REF] or more recently [START_REF] Hamilton | Inductive representation learning on large graphs[END_REF]). In this framework, we observe a graph G = (V, E)

where V = {1, . . . , N } is the set of vertices and E ⊂ {(i, j), i, j ∈ {1, . . . , m} 2 } is the set of edges, and a feature matrix X of size m × m where each line i of X describes node i with m features. Graph Convolutional Networks (GCNs) corresponds to an universal architecture able to process these inputs. It could be written as follows:

H l+1 = f (H l , A),
where A is the adjacency matrix of G = (V, E), H 0 = X is the input matrix of feature, and H L = Y is the output of the GCN. Then, the result of the present paper could be applied to the architectura presented in [START_REF] Thomas | Semi-supervised classification with graph convolutional networks[END_REF] where the layer-wise propagation rule has the following form:

H l+1 = σ(D -1/2 * A * D -1/2 * H l * W l ),
where D is the diagonal node degree matrix, W l is the weight matrix of the l-th layer and σ is a non-linear activation function like the ReLU, and * stands for the classical matrix product. This propagation could be described intuitively as follows. Multiplication with A means that, for every node, we sum up all the feature vectors of all neighbor nodes. It extends the localization ensured by convolution to the graph topology. The presence of the diagonal node degree matrix arises technically to normalize the scale of the feature vectors for high degrees nodes.

Finally, in this paper, we also consider significant computational gain in convolution operations by considering XNOR-nets, where both parameters and activations are binary in the matrix multiplications considered above. In binarized CNNs, full precision weights and activations are binarized into 1 bit, so the multiplications and additions of the convolution are transformed into simple bitwise operations (XNOR-bitcounting operations), resulting in significant storage and computation requirements reduction. However, since much information has been discarded during binarization, the accuracy degradation is high. For that purpose, different techniques has been introduced to improve the approximation power of binary or low bitwidth convolutions. In [START_REF] Rastegari | Xnor-net: Imagenet classification using binary convolutional neural networks[END_REF], real-valued weights and activations are approximated by re-scaling the output of the binary convolution using realvalued positive scale factors. Whereas these scaling parameters are computed analytically in [START_REF] Rastegari | Xnor-net: Imagenet classification using binary convolutional neural networks[END_REF], [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF] proposes to learn these factors directly via backpropagation. It leads to the following approximation of convolutions w * x defined above:

w * x ≈ w bin sign(x) w scale , (3)
where stands for the bitwise convolution and defines the element-wise product of the output of the binary convolution w bin * sign(x) and the scaling factor w scale . In [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF], the set of parameters that is learnt during the training at a given layer is given by the couple (w bin , w scale ), where the dimension of w scale is varying. In this work, we adopt this strategy and consider (3) where w scale corresponds to a sparse rank-1 tensor (see Section 3.2 and the proof of Theorem 3.2 for a precise description of the approximation, and [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF] for details about this choice).

PAC-Bayesian Theory

PAC-Bayesian machine learning theory can be traced back to the work of Mac

Allester and the first so-called Pac-Bayesian bounds ( [START_REF] David | Some pac-bayesian theorems[END_REF] and [START_REF] David | Pac-bayesian stochastic model selection[END_REF]). It was first introduced in learning theory to give a theoretical framework for proving generalization abilities of algorithms that combine the advantages of both PAC, that is generalization bounds, and Bayesian statistics (that is, the introduction of a prior domain knowledge on the set of candidate models). The main objective of PAC-Bayesian bounds is to extract a procedure that optimizes a tradeoff between complexity, or structure, such as sparsity of the candidate learners, with a goodness of fit, or likelihood of the observed sample. In [START_REF] David | Some pac-bayesian theorems[END_REF], the first theoretical bound claims that with high probabilities over the sample distribution, there exists an optimal posterior distribution that realizes this trade-off, whereas [START_REF] David | Pac-bayesian stochastic model selection[END_REF] extends the previous result to an uncountable set of decisions, thanks to the introduction of the Kullback-Leibler divergence as an upper bound. It also shown that the optimal posterior is actually a Gibbs distribution. More recently, many authors have used these ingredients in the high dimensional setting to get interesting alternatives to standard sparsity-induced penalized empirical risk procedures such as lasso estimators. It leads to sparsity oracle inequalities for different aggregating procedures based on exponential weighted averages, with significant weaker assumptions over the gram matrix of the predictors, as well as augmented stability in the procedures. For instance, in the i.i.d. setting, [START_REF] Arnak S Dalalyan | Mirror averaging with sparsity priors[END_REF] extends to an infinite set of weak learners the previous results stated in [START_REF] Juditsky | Learning by mirror averaging[END_REF]. [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF] goes one step further considering a deterministic setting, tits the online learning setting, where no assumption are provided over the data mechanism. Thanks to similar argues, namely convex duality and a cancellation argument originated in [START_REF] Andrew R Barron | Are bayes rules consistent in information?[END_REF],

regret bounds are stated for recursive algorithm inspired from the previous cited litterature. Sparsity regret bounds for exponential weighted averages are then derived in [START_REF] Gerchinovitz | Sparsity regret bounds for individual sequences in online linear regression[END_REF] in an online regression setting, as well as in online clustering in [START_REF] Li | A quasi-bayesian perspective to online clustering[END_REF]. In this paper, we focus on the sparsity scenario and apply the PAC-Bayesian theory to different families of CNNs whereas the companion paper [START_REF] Chee | Learning with bot -bregman and optimal transport divergences[END_REF] proposes a more ambitious theory where Kullback-Leibler divergence is replaced by Bregman or optimal transport divergences and give rise to more flexible penalties for revisited optimization procedures.

Supervised online learning

In the online supervised learning scenario1 , we observe sequentially a set of couples {(x t , y t ) ∈ X × Y, t = 1, . . . , T }. At each round t ≥ 1, the data mechanism and the learning machine interact as follows:

• the environment reveals an new input (or mini-batch) x t ∈ X ,

• a stochastic algorithm proposes w t ∈ W drawn from a suitable distribution π t over the space of candidate architectures (2) and predicts g wt (x t ),

• the environment reveals the true output y t ∈ Y and the stochastic algorithm computes π t+1 .

Based on the deep nets architecture introduced in Section 2.1, and the usual online PAC-Bayesian theory introduced in Section 2.2, the construction of the sequence of distributions {π t } T t=1 expects to minimize the following notion of regret:

T t=1 E πt (y t , g wt (x t )) -inf w∈W T t=1 (y t , g w (x t )) + pen(w) λ , (4)
where : Y × Y → R + is a task-dependent loss function, W is the space of candidate weights defined above and pen(w) depends on the network size and the number of non-zero weights. Parameter λ > 0 governs the trade-off between complexity of the solution and accuracy with respect to the training set. To prove regret bounds such as (4), we consider the standard PAC-Bayesian theory with sparsity priors introduced in [START_REF] Arnak | Sparse regression learning by aggregation and langevin monte-carlo[END_REF] (see also [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF][START_REF] Gerchinovitz | Sparsity regret bounds for individual sequences in online linear regression[END_REF][START_REF] Li | A quasi-bayesian perspective to online clustering[END_REF]) and lead to 1 and 0 penalties. Depending on the choice of λ > 0 and the penalty above, our procedure reaches automatically the desire trade-off. In the same spirit, we can mention several papers dealing with neural networks sparsity (see [START_REF] Taheri | Statistical guarantees for regularized neural networks[END_REF] and the references therein). Several authors also use reinforcement learning to conduct Neural Architecture Search (NAS, see [START_REF] Zoph | Neural architecture search with reinforcement learning[END_REF]), such as in FBNets (see [START_REF] Wu | Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search[END_REF][START_REF] Wan | Fbnetv2: Differentiable neural architecture search for spatial and channel dimensions[END_REF][START_REF] Dai | Fbnetv3: Joint architecture-recipe search using predictor pretraining[END_REF]).

Others techniques are presented in [START_REF] Veniat | Learning time/memory-efficient deep architectures with budgeted super networks[END_REF] or [START_REF] Ruiz | Distilled hierarchical neural ensembles with adaptive inference cost[END_REF].

Algorithm 1 General Algorithm init. λ > 0, π = π 1 a prior distribution on W and t = 1. Let h 0 ≡ 0.

Observe x 1 and draw ŵ1 from π 1 . Predict y 1 according to g ŵ1 (x 1 ).

repeat Observe y t and compute 2 , for all w ∈ W.

h t (w) = h t-1 (w) + (y t , g w (x t )) + λ 2 ( (y t , g w (x t )) -(y t , g ŵt (x t )))
return π t+1 = Gibbs λ (h t ) where:

dGibbs λ (h t )(w) := Z λ exp {-λh t (w)} dπ(w),
for Z λ the normalizing constant.

Draw ŵt+1 from π t+1 and predict y t+1 according to g ŵt+1 (x t+1 ).

t = t + 1 until t = T + 1
3 Sparsity regret bounds for CNNs

In this section, we state regret bounds for convolutional neural networks (CNNs) described above. The main agenda is to show how theoretical results can be applied to convolutional architectures in order to get sparsity regret bounds for Algorithm 1 and control the training and/or inference complexity of the solution.

In Section 3.1, we apply the general PAC-Bayesian paradigm to choose automatically the architecture of a generic CNN. We penalize the size of the network in terms of magnitude and non-zero weights. In Section 3.2, we apply these results to a particular low bitwidth architectura, where a precise bitwise approximation is used for the convolutional layers. It leads to a sparse and Bayesian version of the XNOR-nets described in [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF].

Sparsity Regret bound for Classification

We state regret bounds in the context of classification. In this case, considering a set of weights w ∈ W and the associated convolutional neural network g w (•) defined in (1), we define the last k-th layer by:

softmax(w k * x k-1 + b k ) =         e x k (1) C k e x k (2) C k . . . e x k (K) C k         ∈ [0, 1] K , (5)
where

x k-1 is the output of layer k -1, x k = w k * x k-1 + b k , w k ∈ W p k is the weight matrix of last layer k, C k = K j=1 e x k,j
, K is the number of classes, * is the standard matrix multiplication and x k (j) stands for the j-th coordinate of

vector x k .
In what follows, we state a first regret bound considering the cross-entropy between the output of the CNNs and y t = e t the orthonormal vector of R K with coordinate 1 at y t . Theorem 3.1. Consider Algorithm 1 with prior π ∈ P(W) defined as:

π(w) = L k=1 α k N i=1 β i F j=1 γ j π ijk (w)1 w ∈ R k(i+1)j , (6)
where α (respectively β and γ) is the prior probability on the number of layers {1, . . . , L} (respectively on the number of filters and the size of the filters) and π ijk is a sparsity prior for a given architecture of k layers, i filters of size j whose density is given by:

π ijk (w) = p u=1 c R,τ (1 + |w u |/τ ) 4 1 (|w u | ≤ R) , w ∈ R p , where constant c R,τ := 3 2τ 1 - 1 (1+R/τ ) 3 -1
and with a slight abuse of notations w = (w 1 , . . . , w p ) for p = k(i + 1)j.

Let {(x t , y t ), t = 1, . . . , T } a deterministic sequence and (π t ) T t=1 the sequence of distribution defined in Algorithm 1 with prior π. Then, for any λ, τ > 0, we have:

T t=1 E πt H(y t , g wt (x t )) ≤ inf w∈W(R) T t=1
H (y t , g w (x t )) + pen λ (w) ,

where pen λ (w) = 2 pen 1 (w, τ ) T t=1 x t +2T pen 2 (w, τ )+λT C(R) 2 + pen 3 (gw)

λ for pen 1 (w, τ ) = k l=1 ( w l + τ C 1 n l ) - k l=1 w l , pen 2 (w, τ ) = τ ˙ k-1 l=1 k l =l+2 w l C 1 n l+1 ( ReLU(b * l ) + 2 n l ) + C 2 n l+1 , pen 3 (g w ) = 4 w 0 log 1 + w 1 τ w 0 -log(α k β i γ j ), ( 8
)
where k is the number of layer of w and C 1,2 l,τ are constants depending on the distribution π w in its layer l and:

W(R) = {w ∈ W : |w u | ≤ R, ∀u ∈ {1, . . . , p}}.
The proof uses the general PAC-Bayesian theory with several computations related with the definition of CNNs architecture in (2) gathered with Kullback-Leibler divergences with sparsity prior (6) (see Section 4 for the proof). Remark 1. Theorem 3.1 allows to reach the usual rates of convergence of order √ T when we choose λ := 1/ √ T and τ ≤ 1/ √ T in order to minimize the upper bound.

Remark 2. Theorem 3.1 can lead to usual statistical risk bounds for deep nets by slightly modifying Algorithm 1 with a mirror averaging (see [START_REF] Arnak S Dalalyan | Mirror averaging with sparsity priors[END_REF]). Then, generalization bounds relying on the Froebenius norm of the weights at each layer can be proposed and compared with the recent literature (see [START_REF] Golowich | Size-independent sample complexity of neural networks[END_REF][START_REF] Peter L Bartlett | Spectrallynormalized margin bounds for neural networks[END_REF][START_REF] Behnam Neyshabur | A pacbayesian approach to spectrally-normalized margin bounds for neural networks[END_REF][START_REF] Taheri | Statistical guarantees for regularized neural networks[END_REF]).

Remark 3. We can state the same result for more general prior involving different filter size inside each layer by considering:

π(w) = L k=1 α k N k i=1 β ik F ki j=1 γ ijk π ijk (w). ( 9
)
We omit this case for concision.

Application to sparse XNOR-Nets

In this section we propose to extend the previous result to a binarized network.

Following in particular [START_REF] Rastegari | Xnor-net: Imagenet classification using binary convolutional neural networks[END_REF] and [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF], we propose to reduce drastically the realvalued operations involved in standard CNNs. Moreover we alleviate high quantization errors thanks to the introduction of sparse scaling factors in our bitwise approximations. Inspired by [START_REF] Courbariaux | Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1[END_REF], we first keep the first convolutional layer and the last fully connected layer with sparse real-valued weights and activations.

Then, scaling factors are learned by the learning procedure itself for intermediate layers, where sparsity is also enforced for these scaling parameters at each binary layer. In order to define properly the prior distribution, we now detail the approximation used for the intermediate layer. In the sequel, we denote by x l-1 the input of the l th -layer, w bin l the binary set of weights involved in layer l and w scale l the scaling factors of layer l. Then, following [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF], the output of a binarized layer l is given by the following approximation:

x l = w bin l sign • BNorm (x l-1 ) w scale l ,
where stands for the bitwise convolution, BNorm is the Batch Normalization, is the element-wise product between the tensor

B l := w bin l sign • BNorm (x l-1 ) ∈ {0, 1} h (l) 1 ×h (l) 2 ×h (l) 3
and the scaling tensor

w scale l = (w scale l,1 , w scale l,2 , w scale l,3 ) ∈ R h (l) 1 +h (l) 2 +h (l) 3 +
given by:

x l (i, j, k) = B l (i, j, k)w scale l,1 (i)w scale l,2 (j)w scale l,3 (k), ∀ i = 1, . . . h (l) 1 , j = 1, . . . h (l) 2 , k = 1, . . . h (l) 3 . ( 10
)
Note that different choices of scaling tensor w scale l are discussed in [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF]. It leads to the resulting binarized network:

g w (x) = softmax w real L * x L-1 + b L ,
where x L-1 is given by:

x L-1 = w bin L-1 sign • BNorm (x L-2 ) w scale L-1 = w bin L-1 sign • BNorm w bin L-2 sign • BNorm (x L-3 ) w scale L-2 w scale L-1 = w bin L-1 • • • sign • BNorm w real 1 * x + b 1 w scale L-1
Then we can state the following theorem.

Theorem 3.2. Consider a prior π related with the particular architecture described above, based on the triplet of priors (π real , π bin , π scale ) as follows:

π(w) = π real (w real )π bin (w bin )π scale (w scale ). ( 11
)
Let us consider a sparsity prior π real for the real-valued weights w real as above:

π real (w real ) := p real r=1 c τ,R (1 + |w real r |/τ ) 4 1 |w real r | ≤ R ,
where c τ,R > 0 is defined in Theorem 3.1. For w bin we consider π bin as a product of independent Rademacher distribution defined as:

R({w bin r = 1}) = R({w bin r = -1}) = 1 2
, ∀r = 1, . . . , p bin .

Then, w scale contains the p scale scaling factors with associated prior:

π scale (w scale ) := p scale r=1 c τ,R (1 + w scale r /τ ) 4 1 0 ≤ w scale r ≤ R ,
where c τ,R = 3/τ 1 -

1 (1+R/τ ) 3 -1 .
Let {(x t , y t )} T t=1 a deterministic sequence and {π t } T t=1 the sequence of distribution defined in Algorithm 1 with prior π defined in [START_REF] Courbariaux | Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1[END_REF] with standard deviation τ > 0. Then, for some R > 0, by denoting W(R) := {w = (w real , w bin , w scale ) : ∀w ∈ w real ∪ w scale , |w| ≤ R}, we have for any λ > 0:

T t=1 E πt H(y t , g wt (x t )) ≤ inf w∈W(R) T t=1 H (y t , g w (x t )) + pen XNOR (w) λ + res λ,τ (T ),
where:

pen XNOR (w) = 4

w∈{w real ,w scale } w 0 log 1 + w 1 τ w 0 + p bin log 2, and res λ,τ (T ) is a residual term of order √ T for particular choices of hyperparameter (λ, τ ) in Algorithm 1 and prior [START_REF] Courbariaux | Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1[END_REF].

Remark 5. Theorem 3.2 allows to bound the cumulative loss of the PAC-Bayesian version of XNOR-nets presented in [START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF]. Interestingly, the RHS in Theorem 3.2 depends on the sparsity of the set of real-valued parameters of the XNOR-nets.

It gives some insights to construct sparse versions of classical binarized networks

where continuous weights are used to approximate real-valued convolutions.

Remark 6. However, this sparsity-induced penalty scales linearly with the dimension of the binary weights. As in [START_REF] Anthony | Neural Network Learning: Theoretical Foundations[END_REF], this unconstrained bound strongly depends on the network size, and can be trivial when the number of parameters exceeds the sample size. This dependence is not considered here where we focus on a sparse version of XNOR-Nets in its real-valued weights. The proof is based on the online PAC-Bayesian bound stated in [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF] as follows:

Theorem 4.1. [48, Theorem 4.6] Let (x t , y t ),t = 1, . . . , T a deterministic sequence of data and (π t ) T t=1 a sequence of distributions based on Algorithm 1. Then we have the following bound:

T t=1 E πt (y t , ĝt (x t )) ≤ min ρ∈P(W) E w∼ρ T t=1 ¯ (y t , g w (x t )) + K(ρ, π) λ ,
where ¯ (y t , g w (x t ) = (y t , g w (x t ) + λ 2 ( (y t , g(x t )) -(y t , ĝt (x t )) 2 .

In what follows, we use this bound with a particular measure ρ in the RHS.

Let

w * ∈ W = L k=1 N i=1 F j=1 W k(i+1)j
a specific set of weights in architecture a * . Without loss of generality, we denote by L the number of layers of w * . Then, for a fixed parameter τ > 0, consider π w * the translation of the sparsity prior π ijL defined in Theorem 3.1 as follows:

π w * (dw) = dπ ijL dw (w -w * )dw. ( 12
)
Lemma 4.2 below is useful to control the first term in the RHS of Theorem 4.1, whereas Lemma 4.6 below controls the Kullback-Leibler divergence K(π w * , π).

Lemma 4.2. Let w * = (w * l , b * l ) k l=1 ∈ W for some k ∈ {2, . . . , L}. Then we have for any parameter τ > 0:

E π w * T t=1 H (y t , g w (x t )) ≤ T t=1 H (y t , g w * (x t ))+2 pen 1 (w * , τ ) T t=1 x t +2T pen 2 (w * , τ ),
where

pen 1 (w * , τ ) = k l=1 ( w * l + C 1 n l ,τ ) - k l=1 w * l , pen 2 (w * , τ ) = k-1 l=1 k l =l+2 w * l C 1 n l+1 ,τ ( ReLU(b * l ) + C 2 n l ,τ ) + C 2 n l+1 ,τ
and C 1,2 l,τ are constants depending on the distribution π w * in its layer l.

Proof. Observe that it suffices to obtain the estimate at each time t. Then, for each (x, y) ∈ X × Y, we need to proove the following bound:

E π w * H(y, g w (x)) ≤ H(y, g w * (x)) + 2 pen 1 (w * , τ ) x + 2 pen 2 (w * , τ ).
Let x 0 = x the input data and k = L without loss of generality. From the choice of π w * in (12), we denote the output of layer 1 ≤ l ≤ L -1 by

x l = ReLU((w l + w * l ) * x l-1 + b l + b * l ),
where w = (w l ) L l=1 has law π. Moreover, we denote in the sequel E l := E (w 1 ,...,w l )∼π the expectation with respect to the distribution π in the first l layers.

We start by unpacking the interaction of the cross entropy loss with the softmax activation function in the final layer. For the weights (w l , b l ) in layer l, w l,i and b l (i) denote their i th row and i th entry, respectively. Under the previous notations, the final output is: i) . Without loss of generality, suppose that y t = e 1 = (1, 0, ..., 0). Then, by definition of the cross entropy:

g w * (x 0 ) = softmax(x L ) = e x L (1) C L , • • • , e x L (K) C L T , where x L = w L * x L-1 + b L and C L = K i=1 e x L (
E w∼π w * H(y, g(x)) = -E w∼π w * log e x L (1) C L = -E w∼π w * x L (1) + E w∼π w * log C L .
We bound the two above terms separately. For the first term, by symmetry of the distribution π w * , one has:

-E w∼π w * x L,1 = = -E w∼π w * ((w * L,1 + w L,1 ) * x L-1 + b L (1) * + b L (1)) = -(w * L,1 x * L-1 + b L (1) * ) -E L (w L,1 x L-1 + b L (1)) -w * L,1 E L-1 (x L-1 -x * L-1 ) ≤ -x * L,1 + W * L E L-1 x L-1 -x * L-1 .
On the other hand, for any i = 1, ..., K, using the same computations:

x L (i) = (w * L,i + w L,i ) * x L-1 + b L (i) * + b L (i) = (w * L,i x * L-1 + b L (i) * ) + w * L,i (x L-1 -x * L-1 ) + W L,i x L-1 + b L,i ≤ x * L,i + w * L,i x L-1 -x * L-1 + ReLU(W L,i x L-1 ) + ReLU(b L (i)) ≤ x L (i) * + w * L x L-1 -x * L-1 + ReLU(w L x L-1 ) + ReLU(b L ) ,
where we adopt the notation that for a vector x ∈ R k , ReLU(x) = (ReLU(x 1 ), ..., ReLU(x k )) T .

Then,

E w∼π w * log C L = E w∼π w * log K i=1 e x L (i) ≤ E w∼π log K i=1 e x L (i) * exp w * L x L-1 -x * L-1 + ReLU(W L x L-1 ) + ReLU(b L ) = log K i=1 e x * L (i) + E w∼π w * L x L-1 -x * L-1 + ReLU w L x L-1 x L-1 x L-1 + ReLU(b L ) ≤ log C L + w * L E L-1 x L-1 -x * L-1 + C 1 L,τ E L-1 x L-1 + C 2 L,τ ,
where

C 1 l,τ = max x =1 E l ReLU(w l x) C 2 l,τ = E l ReLU(b l )
In summary:

E w∼π w * H(y, g w (x)) ≤ H(y, g w * (x)) + C 1 L,τ E L-1 x L-1 + 2 W * L E L-1 x L-1 -x * L-1 + C 2 L,τ + E L-1 ReLU (w L x L-1 ) + E L-1 ReLU (b L ) ≤ H(y, g w * (x)) + 2 C 1 L,τ E L-1 x L-1 + W * L E L-1 x L-1 -x * L-1 + C 2 L,τ .
Finally, by inducting with Lemma 4.3 and Lemma 4.4 below, we have:

C 1 L,τ E L-1 x L-1 + w * L E L-1 x L-1 -x * L-1 + C 2 L,τ ≤ L-1 l=1 L k=l+2 w * k (C 1 l+1,τ E x l + C 2 l+1,τ ) ≤ L l=1 ( w * l + C 1 l,τ ) - L l=1 w * l x 0 + L-1 l=1 L k=l+2 w * k C 1 l+1,τ ( ReLU(b * l ) + C 2 l,τ ) + C 2 l+1,τ
= pen 1 (w * , τ ) x 0 + pen 2 (w * , τ ).

Lemma 4.3. For l = 1, ..., L -1.

E l x l -x * l ≤ w * l E l-1 x l-1 -x * l-1 + C 1 l,τ E x l-1 + C 2 l,τ . (13)
Proof. We use the following facts:

• ReLU(a + b) ≤ ReLU(a) + ReLU(b)

• ReLU(a) ≤ a

• ReLU(a) = ReLU a a a .

Then, we have:

E l x l -x * l = E l ReLU((w * l + w l )x l-1 + b * l + b l ) -ReLU(w * l x * l-1 + b * l ) ≤ E l ReLU(w * l (x l-1 -x * l-1 )) + E l ReLU(w l x l-1 ) + E l ReLU(b l ) ≤ w * l E l-1 x l-1 -x * l-1 + E l ReLU w l x l-1 x l-1 x l-1 + C 2 l,τ ≤ w * l E l-1 x l-1 -x * l-1 + E l-1 E w l ∼π 1 A,τ,l ReLU w l x l-1 x l-1 x l-1 + C 2 l,τ ≤ w * l E l-1 x l-1 -x * l-1 + C 1 l,τ E l-1 x l-1 + C 2 l,τ .
Lemma 4.4. For l = 1, ..., L -1.

E l x l ≤ w * l E l-1 x l-1 + C 1 l,τ E x l-1 + C 2 l,τ + ReLU(b * l ) . (14)
Proof. From a similar computation as in the proof of the previous lemma, one gets:

E l x l = E l ReLU((w * l + w l )x l-1 + b * l + b l ) ≤ E l ReLU(w * l x l-1 ) + ReLU(b * l ) + E l ReLU(w l x l-1 ) + E l ReLU(b l ) ≤ w * l E l-1 x l-1 + ReLU(b * l ) + +C 1 n l ,τ E l-1 x l-1 + C 2 n l ,τ ,
Lemma 4.5. For any l ∈ {1, . . . , L}, the constants C 1 l,τ and C 2 l,τ are linear in τ as follows:

C 1 l,τ = τ C 1 l , C 2 l,τ = τ C 2 l ,
where

C 1 l := C 1 l,1 and C 2 l := C 2 l,τ .
Proof. The proof follows from working with the sparsity prior directly and substitution.

Let x ∈ R n l-1 and x = 1. We use the substitution W 1 → W l /τ . Then,

E W l ∼π 1 A,τ,l ReLU(W l x) = n l i=1 ReLU(W l,i x) 2 1/2   n l i=1 n l-1 j=1 (3/τ ) dW l;ij 2(1 + |W l;ij |/τ ) 4   = τ n l i=1 ReLU W l,i τ x 2 1/2   n l i=1 n l-1 j=1 (3/τ ) dW l;ij 2(1 + |W l;ij |/τ ) 4   = τ n l i=1 ReLU (W l,i x) 2 1/2   n l i=1 n l-1 j=1 3 dW l;ij 2(1 + |W l;ij |) 4   = τ E W l ∼π 1 A,1,l ReLU(W l x) .
The homogeneity of order 1 in τ is preserved when taking the max over all

x = 1. C 1 l,τ = max x =1 E W l ∼π 1 A,τ,l ReLU(W l x) = τ max x =1 E W l ∼π 1 A,1,l ReLU(W l x) = τ C 1 l .
The result for C 2 l,τ follows from a similar computation.

We are now on time to bound the quadratic term in Theorem 4.1. Using the previous computations, by noting that w * ∈ W(R) for some positive R > 0, and since π has a bounded support, we have for any (x, y) ∈ X × Y:

(H(y, g w (x)) -H(y, g w (x))) 2 ≤ min 1, max (H(y, g w (x)), H(y, g w (x))) 2 = min (1, x + L (y) -log C + L 2 ≤ min   x L-1 , w L,y + b L,y -log K k=1 e x L,k 2   ≤ ( ReLU(w L-1 * x L-2 + b L-1 ) w L + 2R) 2 ≤ ( w L-1 * x L-2 + b L-1 w L + 2R) 2 . . . ≤ C(R).
We then get the result by using Lemma 4.2 and the following lemma.

Lemma 4.6. Let w * ∈ W and ρ w * given by [START_REF] Rastegari | Xnor-net: Imagenet classification using binary convolutional neural networks[END_REF]. Then we have:

K(ρ w * , π) ≤ 4 w * 0 log 1 + w * 1 τ w * 0 -log(α k β i γ j ).
Let w * ∈ W. Then we have denoting ρ = ρ w * :

K(ρ, π) = log ρ π dρ = log ρ π ijk π ijk π dρ, = K(ρ, π ijk ) + R k(i+1)j log π ijk α k β i γ j π ijk dρ, = p u=1 log (1 + |w u |/τ ) 4 (1 + |w u -w * u |/τ ) 4 ρ(w) dw -log(α k β i γ j ), = 4 p u=1 log 1 + |w u | τ -log(α k β i γ j ), ≤ 4 w 0 log 1 + w 1 τ w 0 -log(α k β i γ j ),
where we use Jensen inequality to the concave function x → log(1 + x) in last line.

Proof of Theorem 3.2

Let w 0 = (w real 0 , w bin 0 , w scale 0 ) ∈ W a particular set of weights of the particular XNORNets++ architectura defined in Section 3. In what follows, with a slight abuse of notations, for any , we denote x (w 0 ) the output of the -th layer with particular weights w 0 until it does not depend on weights of layers k, for k > .

We also denote by x (w 0,l ) the output of the -th layer with particular weights w 0,l at layer l. Moreover, given the prior π introduced in (11), we introduce a particular measure ρ 0 based on w 0 as follows:

ρ 0 (w) := π real (w real 0 -w real )δ w bin 0 (w bin )π 0 scale (w scale ),
where δ w (•) stands for the dirac distribution at weight w and π 0 scale is based on the prior π scale and the set of weights w 0 as follows:

π 0 scale (w scale ) = Π p scale r=1 c τ,R,w 0 r (1 + |w r -w 0 r |/τ ) 4 1 {0 ≤ w r ≤ R} , where c τ,R,w 0 r = 3/τ 2 - 1 (1+w 0 r /τ ) 3 - 1 (1+(R-w 0 r )/τ ) 3 -1
.

With a slight abuse of notation, we also denote by E w l 1 ∼ρ 0 the expectation with respect to the first l layers of ρ 0 whereas E w l ∼ρ 0 denotes the conditoinal expectation of layer l given layers 1, . . . , l -1. To prove Theorem 3.2, we follow the same line as the proof of Theorem 3.1 and adapt the computations to the particular XNOR Nets defined in Section 3.2. The first step is to apply Theorem 4.1 to distribution ρ 0 defined above to get:

T t=1 E πt H (y t , g wt (x t )) ≤ E w∼ρ 0 T t=1 H (y t , g w (x t )) + E w∼ρ 0 E π T -1 0 T t=1 δ λ (x t , y t , w, ŵt-1 ) + K(ρ 0 , π) λ .
To study the first term in the upper bound, we perform the same computations as above. For a given (x, y), we have:

E w∼ρ 0 H (y, g w (x)) = -E w∼ρ 0 w real L,y , x L-1 + b L,y + E w∼ρ 0 log(C L ) (15)
= -w real 0,L,y , E w∼ρ L-1

0 x L-1 + b 0,L,y + E w∼ρ 0 log(C L ). (16)
Then we need the following lemma:

Lemma 4.7. Let w 0 ∈ W and ρ 0 a shifted version of prior π defined in [START_REF] Courbariaux | Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1[END_REF] with mean w 0 . Then we have ∀l ∈ {2, . . . , L -1}, if Var w scale = cr T Id: , there exists a binary filter w r l ∈ {0, 1} s 1 s 2 s 3 , r ∈ {1, . . . , N }, and integers i, j, k such that:

E w l 1 ∼ρ 0 x l (u) -E w l-1 1 ∼ρ 0 x l (w 0,l )(u) ≤ c √ T + c T , ∀u = 1, . . . , h (l)
E w l 1 ∼ρ 0 x l (u) = E w l 1 ∼ρ 0   s 1 f 1 =1 s 2 f 2 =1 s 3 f 3 =1 w r l (f 1 , f 2 , f 3 )x(f 1 , f 2 , f 3 )α k β i γ j   1(Ω ijk α,β,γ ) + 1( Ωijk α,β,γ ) = E w l-1 1 ∼ρ 0   f 1 ,f 2 ,f 3 w r (f 1 , f 2 , f 3 )x(f 1 , f 2 , f 3
√ T + c 2 λT K(ρ 0 , π) λ ,
where c 1 > 0 is a positive constant depending on the previous computations.

Moreover, using the boundness assumption on w 0 and the same computations as in Theorem 3.1, we arrive at:

T t=1 E πt H (y t , g wt (x t )) ≤

Remark 4 .

 4 In[START_REF] Chee | Learning with bot -bregman and optimal transport divergences[END_REF], we derive similar results in a more general case where the Gibbs measure in Algorithm 1 is replaced by a new optimization procedure based on a convex conjugate of Bregman divergences or optimal transport. It gives rise to more flexible penalties than in Theorem 3.1 and Theorem 3.2.

3 ,

 3 where c, c > 0 are absolute constant depending on R and the dimension of the network.Proof : Let l ∈ {2, L -1}.The proof uses a standard decomposition of the expectation and uses Tchebychev inequality. Let us denote w scale l = (α, β, γ) ∈ R a+b+c + the triplet of scaling factors according to[START_REF] Bulat | Xnor-net++: Improved binary neural networks[END_REF], where a, b, c are the dimensions of the output tensor at layer l defined in[START_REF] Tang | How to train a compact binary neural network with high accuracy[END_REF]. Consider the eventΩ α,β,γ := {∀k = 1, . . . a, |α k -α 0,k | ≤ δ 1 } {∀i = 1, . . . b, |β i -β 0,i | ≤ δ 2 } {∀j = 1, . . . , c, |γ j -γ 0,j | ≤ δ 3 }.Then we have by definition of x l in[START_REF] Tang | How to train a compact binary neural network with high accuracy[END_REF], and notingx = sign • BN(x L-2 ) ∈ {-1, +1} abc : E w l 1 ∼ρ 0 x l = E w l 1 ∼ρ 0 (w bin l ⊕ x) w scale l = E w l 1 ∼ρ 0 (w bin l ⊕ x) w scale l 1(Ω α,β,γ ) + 1( Ωα,β,γ )Then, for any u ∈ 1, . . . , h

≤ 1 1 ∼ρ 0   f 1 ,f 2 ,f 3 w≥

 1013 )(α 0,k + δ 1 )(β 0,i + δ 2 )(γ 0,j + δ 3 ) E w l-11 ∼ρ 0 x L-1 (w 0,l )(u) + c √ T + P (|X -µ| ≥ δ i |) ≤ E w l-1 1 ∼ρ 0 x L-1 (w 0,l )(u) + c √ T + c T ,where last two lines follows from Tchebychev by choosing δ i ∼ 1/ √ T , the assumption on the variance of w scale and the boundness of w scale . It leads to the RHS upper bound. For the RLS, we have using the same notations as above:E w l 1 ∼ρ 0 x l (u) = E w l-r (f 1 , f 2 , f 3 )x(f 1 , f 2 , f 3 )(α 0,k + δ 1 )(β 0,i + δ 2 )(γ 0,j + δ 3 ) E w l-1 1 ∼ρ 0 x L-1 (w 0,l )(u)in last line the decomposition as above and noting that on Ω ijk α,β,γ , we have α = α 0 + with > -δ, and on the complementary, ≥ -w scale ∞ .Now we need to control the second term in the previous inequality. As in the proof of Theorem 3.1, we have, for any i = 1, ..., K, under the shifted distribution,x L (i) = (w real 0,L (i) + w L |(i) * x L-1 + b 0,L (i) + b L (i) = w real 0,L (i) * x L-1 (w 0 ) + b 0,L (i) + w real 0,L (i) * (x L-1 -x L-1 (w 0 )) + w L (i) * x L-1 + b L (i) = x L (w 0 )(i) + w real 0,L (i) * (x L-1 -x L-1 (w 0 )) + w L (i) * x L-1 + b L (i).Then we have:E w∼ρ 0 log(C L ) = E w∼ρ 0 log K i=1 e x L (w 0 )| i exp w real 0,L | i * (x L-1 -x L-1 (w 0 )) + w L | i * x L-1 + b L | i ≤ log C L (w 0 ) + E w∼ρ 0 max i=1,...K w real 0,L | i * (x L-1 -x L-1 (w 0 )) + w L | i * x L-1 + b L | i ≤ log C L (w 0 ) + c 3 √ T ,where we use Lemma 4.7 in the last inequality. Then, applying L-3 times Lemma 4.7 for discrete layers and the same computations as in the proof Theorem 3.1 for the first and last layer, we have finally, gathering with the last inequality:

H 1 √ T + c 2 + p bin log 2 :

 122 (y t , g w 0 (x t )) + c λT + K(ρ 0 , π) λ ,where c 2 := c 2 (R) > 0. Finally, by the definition of ρ 0 and the sparsity prior π, we can bound the Kullback-Leibler divergence as follows:K(ρ 0 , π) = log ρ 0 (w) |w real r |/τ ) 4 (1 + |w real r -w real 0,r |/τ ) 4 ρ 0 (w) dw + p bin r=1log 2δ w 0,r (w r ) ρ 0 (w)dw + = pen XNOR (w 0 ).

  (H(y t , g w (x t )) -H(y t , ĝt (x t )) 2 + K(ρ 0 , π) λ

	√
	T
	T t=1 E w∼ρ 0 ≤ λ + E π T -1 0 2 T H (y
	t=1

T t=1 E πt H (y t , g wt (x t )) ≤ T t=1 H (y t , g w 0 (x t )) + c t , g w 0 (x t )) + c 1

In the sequel, we study the online learning paradigm to avoid any assumption about the data mechanism. It is important to note that thanks to[START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF], our procedure in Algorithm 1 could be slightly modified (by introducing a mirror averaging, see[START_REF] Arnak S Dalalyan | Mirror averaging with sparsity priors[END_REF]) in order to get risk bounds in a classical statistical i.i.d. framework.