Title: ANYTIME NEURAL NETWORK: A VERSATILE TRADE-OFF BETWEEN COMPUTATION AND ACCURACY

Abstract: We present an approach for anytime predictions in deep neural networks (DNNs). For each test sample, an anytime predictor produces a coarse result quickly, and then continues to refine it until the test-time computational budget is depleted. Such predictors can address the growing computational problem of DNNs by automatically adjusting to varying test-time budgets. In this work, we study a general augmentation to feed-forward networks to form anytime neural networks (ANNs) via auxiliary predictions and losses. Specifically, we point out a blindspot in recent studies in such ANNs: the importance of high final accuracy. In fact, we show on multiple recognition data-sets and architectures that by having near-optimal final predictions in small anytime models, we can effectively double the speed of large ones to reach corresponding accuracy level. We achieve such speed-up with simple weighting of anytime losses that oscillate during training. We also assemble a sequence of exponentially deepening ANNs, to achieve both theoretically and practically near-optimal anytime results at any budget, at the cost of a constant fraction of additional consumed budget.

1. INTRODUCTION:

In recent years, the accuracy in visual recognition tasks has been greatly improved by increasingly complex convolutional neural networks, from AlexNet (Krizhevsky et al., 2012) and VGG (Simonyan & Zisserman, 2015) , to ResNet (He et al., 2016) , ResNeXt (Xie et al., 2017) , and DenseNet (Huang et al., 2017b) . However, the number of applications that require latency sensitive responses is growing rapidly. Furthermore, their test-time computational budget can often. E.g., autonomous vehicles require real-time object detection, but the required detection speed depends on the vehicle speed; web servers need to meet varying amount of data and user requests throughput through out a day. Thus, it can be difficult for such applications to choose between slow predictors with high accuracy and fast predictors with low accuracy. In many cases, this dilemma can be resolved by an anytime predictor (Horvitz, 1987; Boddy & Dean, 1989; Zilberstein, 1996) , which, for each test sample, produces a fast and crude initial prediction and continues to refine it as budget allows, so that at any test-time budget, the anytime predictor has a valid result for the sample, and the more budget is spent, the better the prediction is.

In this work1 , we focus on the anytime prediction problem in neural networks. We follow the recent works (Lee et al., 2015; Xie & Tu, 2015; Zamir et al., 2017; Huang et al., 2017a) to append auxiliary predictions and losses in feed-forward networks for anytime predictions, and train them jointly end-to-end. However, we note that the existing methods all put only a small fraction of the total weightings to the final prediction, and as a result, large anytime models are often only as accurate as much smaller non-anytime models, because the accuracy gain is so costly in DNNs, as demonstrated in Fig. 1a . We address this problem with a novel and simple oscillating weightings of the losses, and will show in Sec. 3 that our small anytime models with near-optimal final predictions can effectively speed up two times large ones without them, on multiple data-sets, including ILSVRC (Russakovsky et al., 2015) , and on multiple models, including the very recent Multi-Scale-DenseNets (MSDnets) (Huang et al., 2017a) . Observing that the proposed training techniques lead to ANNs that are near-optimal in late predictions but are not as accurate in the early predictions, we assemble ANNs of exponentially increasing depths to dedicate early predictions to smaller networks, while only delaying large networks by a constant fraction of additional test-time budgets.

2. METHODS:

As illustrated in Fig. 1b , given a sample (x, y) ∼ D, the initial feature map x 0 is set to x, and the subsequent feature transformations f 1 , f 2 , ..., f L generate a sequence of intermediate features

x i = f i (x i-1 ; θ i ) for i ≥ 1 using parameter θ i .

Each feature map x i can then produce an auxiliary prediction ŷi using a prediction layer g i : ŷi = g i (x i ; w i ) with parameter w i . Each auxiliary prediction ŷi then incurs an expected loss i := E (x,y)∼D [ (y, ŷi ) ]. We call such an augmented network as an Anytime Neural Network (ANN). Let the parameters of the full ANN be θ = (θ 1 , w 1 , ..., θ L , w L ).

The most common way to optimize these losses, 1 , ..., L , end-to-end is to optimize them in a weighted sum min θ L i=1 B i i (θ), where {B i } i form the weight scheme for the losses. Alternating SIEVE weights. Three experimental observations lead to our proposed SIEVE weight scheme. First, the existing weights, CONST (Lee et al., 2015; Xie & Tu, 2015; Huang et al., 2017a), and LINEAR (Zamir et al., 2017) both incur more than 10% relative increase in final test errors, which effectively slow down anytime models multiple times. Second, we found that a large weight can improve a neighborhood of losses thanks to the high correlation among neighboring losses. Finally, keeping a fixed weighting may lead to solutions where the sum of the gradients are zero, but the individual gradients are non-zero.

The proposed SIEVE scheme has half of the total weights in the final loss, so that the final gradient can outweigh other gradients when all loss gradients have equal two-norms. It also have uneven weights in early losses to let as many losses to be near large weights as possible. Formally for L losses, we first add to B L 2 one unit of weight, where • means rounding. We then add one unit to each B kL 4 for k = 1, 2, 3, and then to each B kL 8 for k = 1, 2, ..., 7, and so on, until all predictors have non-zero weights. We finally normalize B i so that L-1 i=1 B i = 1, and set B L = 1. During each training iteration, we also sample proportional to the B i a layer i, and add temporarily to the total loss B L i so as to oscillate the weights to avoid spurious solutions. We call ANNs with alternating weights as alternating ANNs (AANNs). Though the proposed techinques are heuristics, they effectively speed up anytime models multiple times as shown in Sec. 3. We hope our experimental results can inspire, and set baselines for, future principled approaches.

EANN. Since AANNs put high weights in the final layer, they trade early accuracy for the late ones. We leverage this effect to improving early predictions of large ANNs: we propose to form a sequence of ANNs whose depths grow exponentially (EANN). By dedicating early predictions to small networks, EANN can achieve better early results. Furthermore, if the largest model has L depths, we only compute log L small networks before the final one, and the total cost of the small networks is only a constant fraction of the final one. Hence, we only consume a constant fraction of additional test-time budget. Fig 1c shows how an EANN of the exponential base b = 2 works at test-time. The EANN sequentially computes the ANNs, and only outputs an anytime result if the current result is better than previous ones in validation. Formally, if we assume that each ANN has near-optimal results after 1 b of its layers, then we can prove that for any budget B, the EANN can 

3. KEY EXPERIMENTS:

We present two key results: (1) small anytime models with SIEVE can outperform large ones with CONST, and (2) EANNs can improve early accuracy, but cost a constant fraction of extra budgets.

SIEVE vs. CONST of double costs. In Fig. 2a and Fig. 2b , we compare SIEVE and CONST on ANNs that are based on ResNets on CIFAR100 (Krizhevsky, 2009) and ILSVRC (Russakovsky et al., 2015) . The networks with CONST have double the depths as those with SIEVE. We observe that SIEVE to the same final error rates as CONST of double the costs, but does so much faster. The two schemes also have similar early performance. Hence, SIEVE effectively speed up the predictions of CONST by about two times. In Fig. 2c , we experiment with the very recent Multi-Scale-DenseNets (MSDNets) (Huang et al., 2017a) , which are specifically modified from the recently popular DenseNets (Huang et al., 2017b) to produce the state-of-the-art anytime predictions. We again observe that by improving the final anytime prediction of the smallest MSDNet26 without sacrificing too much early predictions, we make MSDNet26 effectively a sped-up version of MSDNet36 and MSDNet41.

EANN vs. ANNs and OPT. In Fig. 2d , we assemble ResNet-ANNs of 45, 81 and 153 conv layers to form EANNs. We compare the EANNs against the parallel OPT, which is from running regular networks of various depths in parallel. We observe that EANNs are able to significantly reduce the early errors of ANNs, but reach the final error rate later. Furthermore, ANNs with more accurate final predictions using SIEVE and EXP-LIN2 are able to outperform CONST and LINEAR, since whenever an ANN completes in an EANN, the final result is the best one for a long period of time.

:

For the full paper, see https://arxiv.org/abs/1708.06832

EXP-LIN is another proposed scheme that focuses more on the final loss. See the full paper for details.

Figures and Tables:

Figure 1: (a) By ensuring near-optimal final anytime predictions, our ANN (red) achieves the same error rates 2-5 times faster than a large existing one (purple). (b) ANN illustration. (c) EANN illustration.

Figure 2: (a,b) On CIFAR100 and ILSVRC, ResNets using SIEVE achieves the same accuracy as those of twice the depths but using CONST, so that the small nets (blue) effectively speed up the large nets (orange). (c) Similar effects on ILSVRC with MSDNets: the small MSDNet26 with SIEVE (blue) is a better anytime predictor than MSDNet36 and MSDNet41 with CONST (green and red). (d) Using EANN, we greatly reduces the early error rates, at the cost of achieving the final predictions later. achieve near-optimal predictions for budget B after spending C × B total budgets. Furthermoe, for large b, E B∼unif orm(1,L) [C] ≤ 1 -1 2b + 1+ln(b) b-1 → 1, and sup B C = 2 + 1 b-1 → 2.

Peer review (iclr2018):
 1. Paper Summary This paper adds a separate network at every layer of a residual network that performs classification. They minimize the loss of every classifier using two proposed weighting schemes. They also ensemble this model. 2. High level paper The organization of this paper is a bit confusing. Two weighing schemes are introduced in Section 3.1, then the ensemble model is described in Section 3.2, then the weighing schemes are justified in Section 4.1. Overall this method is essentially an cascade where each cascade classifier is a residual block. Every input is passed through as many stages as possible until the budget is reached. While this model is likely quite useful in industrial settings, I don*t think the model itself is wholly original. The authors have done extensive experiments evaluating their method in different settings. I would have liked to see a comparison with at least one other anytime method. I think it is slightly unfair to say that you are comparing with Xie & Tu, 2015 and Huang et al., 2017 just because they use the CONSTANT weighing schemes. 3. High level technical I have a few concerns: - Why does AANN+LINEAR nearly match the accuracy of EANN+SIEVE near 3e9 FLOPS in Figure 4b but EANN+LINEAR does not in Figure 4a? Shouldn*t EANN+LINEAR be strictly better than AANN+LINEAR? - Why do the authors choose these specific weighing schemes? Section 4.1 is devoted to explaining this but it is still unclear to me. They talk about there being correlation between the predictors near the end of the model so they don*t want to distribute weight near the final predictors but this general observation doesn*t obviously lead to these weighing schemes, they still seem a bit adhoc. A few other comments: - Figure 3b seems to contain strictly less information than Figure 4a, I would remove Figure 3b and draw lines showing the speedup you get for one or two accuracy levels. Questions: - Section 3.1: "Such an ideal θ* does not exist in general and often does not exist in practice." Why is this the case? - Section 3.1: " In particular, spreading weights evenly as in (Lee et al., 2015) keeps all i away from their possible respective minimum" Why is this true? - Section 3.1: "Since we will evaluate near depth b3L/4e, and it is the center of L/2 low-weight layers, we increase it weight by 1/8." I am completely lost here, why do you do this? 4. Review summary Ultimately because the model itself resembles previous cascade models, the selected weighings have little justification, and there isn*t a comparison with another anytime method, I think this paper isn*t yet ready for acceptance at ICLR.