Xuhong Li

Yves Grandvalet

Franck Davoine

Explicit Inductive Bias for Transfer Learning with Convolutional Networks

In inductive transfer learning, fine-tuning pretrained convolutional networks substantially outperforms training from scratch. When using finetuning, the underlying assumption is that the pretrained model extracts generic features, which are at least partially relevant for solving the target task, but would be difficult to extract from the limited amount of data available on the target task. However, besides the initialization with the pre-trained model and the early stopping, there is no mechanism in fine-tuning for retaining the features learned on the source task. In this paper, we investigate several regularization schemes that explicitly promote the similarity of the final solution with the initial model. We show the benefit of having an explicit inductive bias towards the initial model, and we eventually recommend a simple L 2 penalty with the pre-trained model being a reference as the baseline of penalty for transfer learning tasks.

Introduction

It is now well known that modern convolutional neural networks (e.g. [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][START_REF] He | Deep residual learning for image recognition[END_REF][START_REF] Szegedy | Rethinking the inception architecture for computer vision[END_REF]) can achieve remarkable performance on large-scale image databases, e.g. ImageNet [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]) and Places 365 [START_REF] Zhou | Places: A 10 million image database for scene recognition[END_REF]), but it is really dissatisfying to see the vast amounts of data, computing time and power consumption that are necessary to train deep networks. Fortunately, such convolutional networks, once trained on a large database, can be refined to solve related but different visual tasks by means of transfer learning, using fine-tuning [START_REF] Yosinski | How transferable are features in deep neural networks?[END_REF][START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF].

learning from the large-scale database of the source task and this knowledge is then transferred to the target task by initializing the network with the pre-trained parameters. However, we will show in the experimental section that some parameters may be driven far away from their initial values during fine-tuning. This leads to important losses of the initial knowledge that is assumed to be relevant for the targeted problem.

In order to help preserve the knowledge embedded in the initial network, we consider a series of other parameter regularization methods during fine-tuning. We argue that the standard L 2 regularization, which drives the parameters towards the origin, is not adequate in the framework of transfer learning, where the initial values provide a more sensible reference point than the origin. This simple modification keeps the original control of overfitting, by constraining the effective search space around the initial solution, while encouraging committing to the acquired knowledge. We show that it has noticeable effects in inductive transfer learning scenarios.

This paper copes with the inconsistency that still prevails in transfer learning scenarios, where the model is initialized with some parameters, while the abuse of L 2 regularization encourages departing from these initial values. We thus advocate for a coherent parameter regularization approach, where the pre-trained model is both used as the starting point of the optimization process and as the reference in the penalty that encodes an explicit inductive bias. This type of penalty will be designated with SP to recall that they encourage similarity with the starting point of the fine-tuning process. We evaluate regularizers based on the L 2 , Lasso and Group-Lasso penalties, which can freeze some individual parameters, or groups of parameters, to the pre-trained parameters. Fisher information is also taken into account when we test L 2 -SP and Group-Lasso-SP approaches. Our experiments indicate that all tested parameter regularization methods using the pre-trained parameters as a reference get an edge over the standard L 2 weight decay approach. We eventually recommend using L 2 -SP as the standard baseline for solving transfer learning tasks and benchmarking new algorithms.

Related Work

In this section, we recall the approaches to inductive transfer learning in convolutional networks. We focus on approaches that also encourage similarity (of features or parameters) on different models. Our proposal departs either by the goal pursued or by the type of model used.

Shrinking Toward Chosen Parameters

Regularization has been a means to build shrinkage estimators for decades. Shrinking towards zero is the most common form of shrinkage, but shrinking towards adaptively chosen targets has been around for some time, starting with Stein shrinkage (see e.g. Lehmann & Casella 1998, chapter 5), where it can be related to empirical Bayes arguments.

In transfer learning, it has been used in maximum entropy models [START_REF] Chelba | Adaptation of maximum entropy capitalizer: Little data can help a lot[END_REF] or SVM [START_REF] Yang | Adapting svm classifiers to data with shifted distributions[END_REF][START_REF] Aytar | Tabula rasa: Model transfer for object category detection[END_REF][START_REF] Tommasi | Learning categories from few examples with multi model knowledge transfer[END_REF]. These approaches were shown to outperform standard L 2 regularization with limited labeled data in the target task [START_REF] Aytar | Tabula rasa: Model transfer for object category detection[END_REF][START_REF] Tommasi | Learning categories from few examples with multi model knowledge transfer[END_REF].

These relatives differ from the application to deep networks in several respects, the more important one being that they consider a fixed representation, where transfer learning aims at producing similar classification parameters in that space, that is, similar classification rules. For deep networks, transfer usually aims at learning similar representations upon which classification parameters will be learned from scratch. Hence, even though the techniques we discuss here are very similar regarding the analytical form of the regularizers, they operate on parameters having a very different role.

Transfer Learning for Deep Networks

Regarding transfer learning, we follow here the nomenclature of [START_REF] Pan | A survey on transfer learning[END_REF], who categorized several types of transfer learning according to domain and task settings during the transfer. A domain corresponds to the feature space and its distribution, whereas a task corresponds to the label space and its conditional distribution with respect to features. The initial learning problem is defined on the source domain and source task, whereas the new learning problem is defined on the target domain and the target task.

In the typology of Pan & Yang, we consider the inductive transfer learning setting, where the target domain is identical to the source domain, and the target task is different from the source task. We furthermore focus on the case where a vast amount of data was available for training on the source problem, and some limited amount of labeled data is available for solving the target problem. Under this setting, we aim at improving the performance on the target problem through parameter regularization methods that explicitly encourage the similarity of the solutions to the target and source prob-lems. Note that, though we refer here to problems that were formalized or popularized after [START_REF] Pan | A survey on transfer learning[END_REF], such as lifelong learning, Pan & Yang's typology remains valid. [START_REF] Donahue | A deep convolutional activation feature for generic visual recognition[END_REF] repurposed features extracted from different layers of the pre-trained AlexNet of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and plugged them into an SVM or a logistic regression classifier. This approach outperformed the state of the art of that time on the Caltech-101 database [START_REF] Fei-Fei | One-shot learning of object categories[END_REF]. Later, [START_REF] Yosinski | How transferable are features in deep neural networks?[END_REF] showed that finetuning the whole AlexNet resulted in better performance than using the network as a static feature extractor. Finetuning pre-trained VGG [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] on the image classification task of VOC-2012 [START_REF] Everingham | The Pascal visual object classes (VOC) challenge[END_REF]) and Caltech 256 [START_REF] Griffin | Caltech-256 object category dataset[END_REF]) achieved the best results of that time.

REPRESENTATION TRANSFER

Ge & Yu (2017) proposed a scheme for selecting a subset of images from the source problem that have similar local features to those in the target problem and then jointly finetuned a pre-trained convolutional network. Besides image classification, many procedures for object detection [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF][START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF][START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF] and image segmentation (Long et al. 2015a[START_REF] Chen | Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected CRFs[END_REF][START_REF] Zhao | Pyramid scene parsing network[END_REF]) have been proposed relying on fine-tuning to improve over training from scratch. These approaches showed promising results in a challenging transfer learning setup, as going from classification to object detection or image segmentation requires rather heavy modifications of the architecture of the network.

The success of transfer learning with convolutional networks relies on the generality of the learned representations that have been constructed from a large database like ImageNet. [START_REF] Yosinski | How transferable are features in deep neural networks?[END_REF] also quantified the transferability of these pieces of information in different layers, e.g. the first layers learn general features, the middle layers learn highlevel semantic features and the last layers learn the features that are very specific to a particular task. That can be also noticed by the visualization of features [START_REF] Zeiler | Visualizing and understanding convolutional networks[END_REF]. Overall, the learned representations can be conveyed to related but different domains and the parameters in the network are reusable for different tasks.

REGULARIZERS IN RELATED LEARNING SETUPS

In lifelong learning [START_REF] Thrun | Lifelong robot learning[END_REF][START_REF] Pentina | Lifelong learning with non-iid tasks[END_REF], where a series of tasks is learned sequentially by a single model, the knowledge extracted from the previous tasks may be lost as new tasks are learned, resulting in what is known as catastrophic forgetting. In order to achieve a good performance on all tasks, [START_REF] Li | Learning without forgetting[END_REF] proposed to use the outputs of the target examples, computed by the original network on the source task, to de-fine a learning scheme preserving the memory of the source tasks when training on the target task. They also tried to preserve the pre-trained parameters instead of the outputs of examples but they did not obtain interesting results. [START_REF] Kirkpatrick | Overcoming catastrophic forgetting in neural networks[END_REF] developed a similar approach with success. They get sensible improvements by measuring the sensitivity of the parameters of the network learned on the source data thanks to the Fisher information. The Fisher information matrix defines a metric in parameter space that is used in their regularizer to preserve the representation learned on the source data, thereby retaining the knowledge acquired on the previous tasks. This scheme, named elastic weight consolidation, was shown to avoid forgetting, but fine-tuning with plain stochastic gradient descent was more effective than elastic weight consolidation for learning new tasks. Hence, elastic weight consolidation may be thought as being inadequate for transfer learning, where performance is only measured on the target task. We will show that this conclusion is not appropriate in typical transfer learning scenarios with few target examples.

In domain adaptation (Long et al. 2015b), where the target domain differs from the source domain whereas the target task is identical to the source task and no (or few) target examples are labeled, most approaches are searching for a common representation space for source and target domains to reduce domain shift. [START_REF] Rozantsev | Beyond sharing weights for deep domain adaptation[END_REF] proposed a parameter regularization scheme for encouraging the similarity of the representations of the source and the target domains. Their regularizer encourages similar source and target parameters, up to a linear transformation. Still in domain adaptation, besides vision, encouraging similar parameters in deep networks has been proposed in speaker adaptation problems [START_REF] Liao | Speaker adaptation of context dependent deep neural networks[END_REF][START_REF] Ochiai | Speaker adaptive training using deep neural networks[END_REF]) and neural machine translation [START_REF] Barone | Regularization techniques for fine-tuning in neural machine translation[END_REF], where it proved to be helpful.

The L 2 -SP regularizer was used independently by [START_REF] Grachten | Strategies for conceptual change in convolutional neural networks[END_REF] for transfer in vision application, but where they used a random reinitialization of parameters. For convex optimization problems, this is equivalent to finetuning with L 2 -SP, but we are obviously not in that situation. [START_REF] Grachten | Strategies for conceptual change in convolutional neural networks[END_REF] conclude that their strategy behaves similarly to learning from scratch. We will show that using the starting point as an initialization of the fine-tuning process and as the reference in the regularizer improves results consistently upon the standard fine-tuning process.

Regularizers for Fine-Tuning

In this section, we detail the penalties we consider for finetuning. Parameter regularization is critical when learning from small databases. When learning from scratch, regularization is aimed at facilitating optimization and avoiding overfitting, by implicitly restricting the capacity of the network, that is, the effective size of the search space. In transfer learning, the role of regularization is similar, but the starting point of the fine-tuning process conveys information that pertains to the source problem (domain and task). Hence, the network capacity has not to be restricted blindly: the pre-trained model sets a reference that can be used to define the functional space effectively explored during finetuning.

Since we are using early stopping, fine-tuning a pre-trained model is an implicit form of inductive bias towards the initial solution. We explore here how a coherent explicit inductive bias, encoded by a regularization term, affects the training process. Section 4 shows that all such schemes get an edge over the standard approaches that either use weight decay or freeze part of the network for preserving the low-level representations that are built in the first layers of the network.

Let w ∈ R n be the parameter vector containing all the network parameters that are to be adapted to the target task. The regularized objective function J that is to be optimized is the sum of the standard objective function J and the regularizer Ω(w). In our experiments, J is the negative log-likelihood, so that the criterion J could be interpreted in terms of maximum a posteriori estimation, where the regularizer Ω(w) would act as the log prior of w. More generally, the minimizer of J is a trade-off between the data-fitting term and the regularization term.

L 2 penalty The current baseline penalty for transfer learning is the usual L 2 penalty, also known as weight decay, since it drives the weights of the network to zero:

Ω(w) = α 2 w 2 2 , ( 1
)
where α is the regularization parameter setting the strength of the penalty and • p is the p-norm of a vector.

L 2 -SP Let w 0 be the parameter vector of the model pretrained on the source problem, acting as the starting point (-SP) in fine-tuning. Using this initial vector as the reference in the L 2 penalty, we get:

Ω(w) = α 2 w -w 0 2 2 .
(2)

Typically, the transfer to a target task requires some modifications of the network architecture used for the source task, such as on the last layer used for predicting the outputs. Then, there is no one-to-one mapping between w and w 0 , and we use two penalties: one for the part of the target network that shares the architecture of the source network, denoted w S , the other one for the novel part, denoted w S .

The compound penalty then becomes:

Ω(w) = α 2 w S -w 0 S 2 2 + β 2 w S 2 2 .
(3)

L 2 -SP-Fisher Elastic weight consolidation [START_REF] Kirkpatrick | Overcoming catastrophic forgetting in neural networks[END_REF]) was proposed to avoid catastrophic forgetting in the setup of lifelong learning, where several tasks should be learned sequentially. In addition to preserving the initial parameter vector w 0 , it consists in using the estimated Fisher information to define the distance between w S and w 0 S . More precisely, it relies on the diagonal of the Fisher information matrix, resulting in the following penalty:

Ω(w) = α 2 j∈S Fjj w j -w 0 j 2 + β 2 w S 2 2 , ( 4
)
where Fjj is the estimate of the jth diagonal element of the Fisher information matrix. It is computed as the average of the squared Fisher's score on the source problem, using the inputs of the source data:

Fjj = 1 m m i=1 K k=1 f k (x (i) ; w 0 ) ∂ ∂w j log f k (x (i) ; w 0 ) 2 ,
where the outer average estimates the expectation with respect to inputs x and the inner weighted sum is the estimate of the conditional expectation of outputs given input x (i) , with outputs drawn from a categorical distribution of parameters (f 1 (x (i) ; w), . . . , f k (x (i) ; w), . . . , f K (x (i) ; w)).

L 1 -SP We also experiment the L 1 variant of L 2 -SP:

Ω(w) = α w S -w 0 S 1 + β 2 w S 2 2 .
(5)

The usual L 1 penalty encourages sparsity; here, by using w 0 S as a reference in the penalty, L 1 -SP encourages some components of the parameter vector to be frozen, equal to the pre-trained initial values. The penalty can thus be thought as intermediate between L 2 -SP (3) and the strategies consisting in freezing a part of the initial network. We explore below other ways of doing so.

Group-Lasso-SP (GL-SP) Instead of freezing some individual parameters, we may encourage freezing some groups of parameters corresponding to channels of convolution kernels. Formally, we endow the set of parameters with a group structure, defined by a fixed partition of the index set

I = {1, . . . , p}, that is, I = G g=0 G g , with G g ∩ G h = ∅ for g = h.
In our setup, G 0 = S, and for g > 0, G g is the set of fan-in parameters of channel g. Let p g denote the cardinality of group g, and w Gg ∈ R pg be the vector (w j ) j∈Gg . Then, the GL-SP penalty is:

Ω(w) = α G g=1 s g w Gg -w 0 Gg 2 + β 2 w S 2 2 , ( 6
)
where w 0 G0 = w 0 S = 0, and, for g > 0, s g is a predefined constant that may be used to balance the different cardinalities of groups. In our experiments, we used s g = p 1/2 g .

Our implementation of Group-Lasso-SP can freeze feature extractors at any depth of the convolutional network, to preserve the pre-trained feature extractors as a whole instead of isolated pre-trained parameters. The group G g of size p g = h g × w g × d g gathers all the parameters of a convolution kernel of height h g , width w g , and depth d g . This grouping is done at each layer of the network, for each output channel, so that the group index g corresponds to two indexes in the network architecture: the layer index l and the output channel index at layer l. If we have c l such channels at layer l, we have a total of G = l c l groups.

Group-Lasso-SP-Fisher (GL-SP-Fisher) Following the idea of L 2 -SP-Fisher, the Fisher version of GL-SP is:

Ω(w) = α G g=1 s g j∈Gg Fjj w j -w 0 j 2 1/2 + β 2 w G0 2 2 .

Experiments

We evaluate the aforementioned parameter regularizers on several pairs of source and target tasks. We use ResNet [START_REF] He | Deep residual learning for image recognition[END_REF]) as our base network, since it has proven its wide applicability on transfer learning tasks. Conventionally, if the target task is also a classification task, the training process starts by replacing the last layer with a new one, randomly generated, whose size depends on the number of classes in the target task.

Source and Target Databases

For comparing the effect of similarity between the source problem and the target problem on transfer learning, we chose two source databases: ImageNet (

Training Details

Most images in those databases are color images. If not, we create a three-channel image by duplicating the grayscale data. All images are pre-processed: we resize images to 256×256 and subtract the mean activity computed over the training set from each channel, then we adopt random blur, random mirror and random crop to 224×224 for data augmentation. The network parameters are regularized as described in Section 3. Cross validation is used for searching the best regularization hyperparameters α and β: α differs across experiments, and β = 0.01 is consistently picked by cross-validation for regularizing the last layer. Figure 1 illustrates that the test accuracy varies smoothly according to the regularization strength, and that there is a sensible benefit in penalizing the last layer (that is, β ≥ 0) for the best α values. When applicable, the Fisher information matrix is estimated on the source database. The two source databases (ImageNet or Places 365) yield different estimates.

Regarding testing, we use central crops as inputs to compute the classification accuracy.

Stochastic gradient descent with momentum 0.9 is used for optimization. We run 9000 iterations and divide the learning rate by 10 after 6000 iterations. The initial learning rates are 0.005, 0.01 or 0.02, depending on the tasks. Batch size is 64. Then, under the best configuration, we repeat five times the learning process to obtain an average classification accuracy and standard deviation. All the experiments are performed with Tensorflow [START_REF] Abadi | TensorFlow: Large-scale machine learning on heterogeneous systems[END_REF].

Results

FINE-TUNING FROM A SIMILAR SOURCE

Table 2 displays the results of fine-tuning with L 2 -SP and L 2 -SP-Fisher, which are compared to the current baseline of fine-tuning with L 2 . We report the average accuracies and their standard deviations on 5 different runs. Since we use the same data and the same starting point, runs differ only due to the randomness of stochastic gradient descent and to the weight initialization of the last layer. We can observe that L 2 -SP and L 2 -SP-Fisher always improve over L 2 , and that when less training data are available for the target problem, the improvement of L 2 -SP and L 2 -SP-Fisher compared to L 2 are more important. Meanwhile, no large difference is observed between L 2 -SP and L 2 -SP-Fisher.

We can boost the performance and outperform the state of the art [START_REF] Ge | Borrowing treasures from the wealthy: Deep transfer learning through selective joint fine-tuning[END_REF] in some cases by exploiting more training techniques and post-processing methods, which are described in the supplementary material.

BEHAVIOR ACROSS PENALTIES, SOURCE AND TARGET DATABASES

A comprehensive view of our experimental results is given in Figure 2. Each plot corresponds to one of the four target databases listed in Table 1. The light red points mark the accuracies of transfer learning when using Places 365 as the source database, whereas the dark blue points correspond to the results obtained with ImageNet. As expected, the results of transfer learning are much better when source and target are alike: the scene classification target task MIT Indoor 67 (top left) is better transferred from the scene classification source task Places 365, whereas the object recognition target tasks benefit more from the object recognition source task ImageNet. It is however interesting to note that the trends are similar for the two source databases: all the fine-tuning strategies based on penalties using the starting point -SP as a reference perform consistently better than standard finetuning (L 2 ). There is thus a benefit in having an explicit bias towards the starting point, even when the target task is not too similar to the source task.

This benefit is comparable for L 2 -SP and L 2 -SP-Fisher penalties; the strategies based on L 1 and Group-Lasso penalties behave rather poorly in comparison. They are even less accurate than the plain L 2 strategy on Caltech 256 -60 when the source problem is Places 365. Stochastic gradient descent does not handle well these penalties whose gradient is discontinuous at the starting point where the optimization starts. The stochastic forward-backward splitting algorithm of [START_REF] Duchi | Efficient online and batch learning using forward backward splitting[END_REF], which is related to proximal methods, leads to substandard results, presumably due to the absence of a momentum term. In the end, we used plain stochastic gradient descent on a smoothed version of the penalties eliminating the discontinuities of their gradients, but some instability remains.

Finally, the variants using the Fisher information matrix behave like the simpler variants using a Euclidean metric on parameters. We believe that this is due to the fact that, contrary to lifelong learning, our objective does not favor solutions that retain accuracy on the source task. The metric defined by the Fisher information matrix may thus be less relevant for our actual objective that only relates to the target task. Table 3 confirms that L 2 -SP-Fisher is indeed a better approach in the situation of lifelong learning, where accuracies on the source tasks matter. It reports the drop in performance when the fine-tuned models are applied on the source task, without any retraining, simply using the original classification layer instead of the classification layer learned for the target task. The performance drop is smaller for L 2 -SP-Fisher than for L 2 -SP. In comparison, L 2 fine-tuning results in catastrophic forgetting: the performance on the source task is considerably affected by fine-tuning.

FINE-TUNING vs. FREEZING THE NETWORK

Freezing the first layers of a network during transfer learning is another way to ensure a very strong inductive bias, 2, where no layers are frozen. ResNet-101 begins with one convolutional layer, then stacks 3-layer blocks. The three layers in one block are either frozen or trained altogether.

letting less degrees of freedom to transfer learning. Figure 3 shows that this strategy, which is costly to implement if one looks for the optimal number of layers to be frozen, can improve L 2 fine-tuning considerably, but that it is a rather inefficient strategy for L 2 -SP fine-tuning. Among all possible choices, L 2 fine-tuning with partial freezing is dominated by the plain L 2 -SP fine-tuning. Note that L 2 -SP-Fisher (not displayed) behaves similarly to L 2 -SP.

Analysis and Discussion

Among all -SP methods, L 2 -SP and L 2 -SP-Fisher always reach a better accuracy on the target task. We expected L 2 -SP-Fisher to outperform L 2 -SP, since Fisher information helps in lifelong learning, but there is no significant difference between the two options. Since L 2 -SP is simpler than L 2 -SP-Fisher, we recommend the former, and we focus on the analysis of L 2 -SP, although most of the analysis and the discussion would also apply to L 2 -SP-Fisher.

COMPUTATIONAL EFFICIENCY

The -SP penalties introduce no extra parameters, and they only increase slightly the computational burden. L 2 -SP increases the number of floating point operations required for a learning step of ResNet-101 by less than 1%. Hence, at a negligible computational cost, we can obtain significant improvements in classification accuracy, and no additional cost is experienced at test time.

THEORETICAL INSIGHTS

Analytical results are very difficult to obtain in the deep learning framework. Under some (highly) simplifying assumptions, we show in supplementary material that the optimum of the regularized objective function with L 2 -SP is a compromise between the optimum of the unregularized objective function and the pre-trained parameter vector, precisely an affine combination along the directions of eigenvectors of the Hessian matrix of the unregularized objective function. This contrasts with L 2 that leads to a compromise between the optimum of the unregularized objective function and the origin. Clearly, searching for a solution in the vicinity of the pre-trained parameters is intuitively much more appealing, since it is the actual motivation for using the pre-trained parameters as the starting point of the fine-tuning process.

Using L 2 -SP instead of L 2 can also be motivated by an analogy with shrinkage estimation (see e.g. Lehmann & Casella 1998, chapter 5). Although it is known that shrinking toward any reference is better than raw fitting, it is also known that shrinking towards a value that is close to the "true parameters" is more effective. The notion of "true parameters" is not readily applicable to deep networks, but the connection with Stein shrinking effect may be inspiring by surveying the literature considering shrinkage towards other references, such as linear subspaces. In particular, it is likely that manifolds of parameters defined from the pre-trained network would provide a more relevant reference than the single parameter value provided by the pre-trained network.

LAYER-WISE ANALYSIS

We complement our experimental results by an analysis relying on the activations of the hidden units of the network, to provide another view on the differences between L 2 and L 2 -SP fine-tuning. Activation similarities are easier to interpret than parameter similarities, and they provide a view of the network that is closer to the functional perspective we are actually pursuing. Matching individual activations makes sense, provided that the networks slightly differ before and after tuning so that few roles are switched between units or feature maps.

The dependency between the pre-trained and the fine-tuned Each boxplot summarizes the distribution of the R 2 coefficients of the activations after fine-tuning with respect to the activations of the pre-trained network, for all the units in one layer. ResNet-101 begins with one convolutional layer, then stacks 3-layer blocks. For legibility, we only display here the R 2 at the first layer and at the outputs of some 3-layer blocks.

activations throughout the network is displayed in Figure 4, with boxplots of the R 2 coefficients, gathered layer-wise, of the fine-tuned activations with respect to the original activations. This figure shows that, indeed, the roles of units or feature maps have not changed much after L 2 -SP and L 2 -SP-Fisher fine-tuning. The R 2 coefficients are very close to 1 on the first layers, and smoothly decrease throughout the network, staying quite high, around 0.6, for L 2 -SP and L 2 -SP-Fisher at the greatest depth. In contrast, for L 2 regularization, some important changes are already visible in the first layers, and the R 2 coefficients eventually reach quite low values at the greatest depth. This illustrates in details how the roles of the network units is remarkably retained with L 2 -SP and L 2 -SP-Fisher fine-tuning, not only for the first layers of the networks, but also for the last high-level representations before classification.

Conclusion

We described and tested simple regularization techniques for inductive transfer learning. They all encode an explicit bias towards the solution learned on the source task, resulting in a compromise with the pre-trained parameter that is coherent with the original motivation for fine-tuning. All the regularizers evaluated here have been already used for other purposes or in other contexts, but we demonstrated their relevance for inductive transfer learning with deep convolutional networks.

We show that a simple L 2 penalty using the starting point as a reference, L 2 -SP, is useful, even if early stopping is used. This penalty is much more effective than the standard L 2 penalty that is commonly used in fine-tuning. It is also more effective and simpler to implement than the strategy consisting in freezing the first layers of a network. We provide theoretical hints and strong experimental evidence showing that L 2 -SP retains the memory of the features learned on the source database. We thus believe that this simple L 2 -SP scheme should be considered as the standard baseline in inductive transfer learning, and that future improvements of transfer learning should rely on this baseline.

Besides, we tested the effect of more elaborate penalties, based on L 1 or Group-L 1 norms, or based on Fisher information. None of the L 1 or Group-L 1 options seem to be valuable in the context of inductive transfer learning that we considered here, and using the Fisher information with L 2 -SP does not improve accuracy on the target task. Different approaches, which implement an implicit bias at the functional level, alike [START_REF] Li | Learning without forgetting[END_REF], remain to be tested: being based on a different principle, their value should be assessed in the framework of inductive transfer learning.

A. Effect of L 2 -SP Regularization on Optimization

The effect of L 2 regularization can be analyzed by doing a quadratic approximation of the objective function around the optimum (see, e.g. Goodfellow et al. 2017, Section 7.1.1). This analysis shows that L 2 regularization rescales the parameters along the directions defined by the eigenvectors of the Hessian matrix. This scaling is equal to λi λi+α for the i-th eigenvector of eigenvalue λ i . A similar analysis can be used for the L 2 -SP regularization.

We recall that J(w) is the unregularized objective function, and J(w) = J(w) + α ww 0 2 2 is the regularized objective function. Let w * = argmin w J(w) and w = argmin w J be their respective minima. The quadratic approximation of J(w * ) gives

H( w -w * ) + α( w -w 0 ) = 0 , ( 7
)
where H is the Hessian matrix of J w.r.t. w, evaluated at w * . Since H is positive semidefinite, it can be decomposed as H = QΛQ T . Applying the decomposition to Equation ( 7), we obtain the following relationship between w and w * :

Q T w = (Λ + αI) -1 ΛQ T w * + α(Λ + αI) -1 Q T w 0 . (8)
We can see that with L 2 -SP regularization, in the direction defined by the i-th eigenvector of H, w is a convex combination of w * and w 0 in that direction since λi λi+α and α λi+α sum to 1.

B. Matching the State of the Art in Image Classification

The main objective of this paper is to demonstrate that -SP regularization in general, and L 2 -SP in particular, provides a baseline for transfer learning that is significantly superior to the standard fine-tuning technique. We do not aim at reaching the state of the art solely with this simple technique. However, as shown here, with some training tricks and postprocessing methods, which have been proposed elsewhere but were not used in the paper, we can reach or even exceed the state of the art performances, simply by changing the regularizer to L 2 -SP.

Aspect Ratio. During training, respecting or ignoring the aspect ratio of images will give different results, and usually it would be better to keep the original aspect ratio. In the paper, the classification experiments are all under the preprocessing of resizing all images to 256×256, i.e. ignoring the aspect ratio. Here we perform an ablation study to analyze the difference between keeping and ignoring the ratio. For simplicity, we use the same hyperparameters as before except that the aspect ratio is kept and images are resized with the shorter edge being 256.

Post-Processing for Image Classification. A common post-processing method for image classification is 10-crop testing (averaging the predictions of 10 cropped patches, the four corner patches and the center patch as well as their horizontal reflections).

We apply the aspect ratio and 10-crop testing techniques to improve our results, but we believe the performance can be improved but using additional tricks, such as random rotation or scaling during training, more crops, multi scales for test, etc. We add Foods 101 [START_REF] Bossard | Food-101mining discriminative components with random forests[END_REF] to supplement our experiments. Foods 101 is a database that collects photos of 101 food categories and is a much larger database than the three we already presented, yet rough in terms of image quality and class labels in the training set.

C. Application of L 2 -SP to Semantic Image Segmentation

The paper compares different regularization approaches for transfer in image classification. In this section, we examine the versatility of L 2 -SP by applying it to image segmentation. Although the image segmentation target task, which aims at labeling each pixel of an image with the category of the object it belongs to, differs from the image classification source task, it still benefits from fine-tuning.

We evaluate the effect of fine-tuning with L 2 -SP on Cityscapes [START_REF] Cordts | The Cityscapes dataset for semantic urban scene understanding[END_REF]), a dataset with an evaluation benchmark for pixel-wise segmentation of real-world urban street scenes. It consists of 5000 images with high quality pixel-wise labeling, which are split into a training set (2975 images), a validation set (500 images) and a test set (1525 images), all with resolution 2048×1024 pixels. ImageNet [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]) is used as source.

As for the networks, we consider two architectures of convolutional networks: the standard ResNet [START_REF] He | Deep residual learning for image recognition[END_REF]), which can be used for image segmentation by removing the global pooling layer, and DeepLab-V2 [START_REF] Chen | Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected CRFs[END_REF], which stayed top-ranked for some time on the Cityscapes benchmark and is one of the most favored structures. We 2017) and the base learning rate is set to 0.0005. For testing, we use the whole image.

Table 5 reports the results on Cityscapes validation set. We reproduce the experiments of ResNet and DeepLab that use the standard L 2 fine-tuning, and compare with L 2 -SP finetuning, all other setup parameters being unchanged. We readily observe that fine-tuning with L 2 -SP in place of L 2 consistently improves the performance in mean IoU score, for both networks.

Figure 1 .

 1 Figure1. Classification accuracy (in %) on Stanford Dogs 120 for L 2 -SP, according to the two regularization hyperparameters α and β respectively applied to the layers inherited from the source task and the last classification layer (see Equation3).

Figure 2 .

 2 Figure 2. Classification accuracies (in %) of the tested fine-tuning approaches on the four target databases, using ImageNet (dark blue dots) or Places 365 (light red dots) as source databases. MIT Indoor 67 is more similar to Places 365 than to ImageNet; Stanford Dogs 120 and Caltech 256 are more similar to ImageNet than to Places 365.

Figure 3 .

 3 Figure 3. Classification accuracies (in %) of fine-tuning with L 2 and L 2 -SP on Stanford Dogs 120 (top) and Caltech 256-30 (bottom) when freezing the first layers of ResNet-101. The dashed lines represent the accuracies reported in Table2, where no layers are frozen. ResNet-101 begins with one convolutional layer, then stacks 3-layer blocks. The three layers in one block are either frozen or trained altogether.

Figure 4 .

 4 Figure4. R 2 coefficients of determination with L 2 and L 2 -SP regularizations for Stanford Dogs 120. Each boxplot summarizes the distribution of the R 2 coefficients of the activations after fine-tuning with respect to the activations of the pre-trained network, for all the units in one layer. ResNet-101 begins with one convolutional layer, then stacks 3-layer blocks. For legibility, we only display here the R 2 at the first layer and at the outputs of some 3-layer blocks.

Table 1 .

 1 Characteristics of the target databases: name and type, numbers of training and test images per class, and number of classes.

	Database	task category	# training # test # classes
	MIT Indoors 67	scene classification	80	20	67
	Stanford Dogs 120 specific object recog.	100	∼ 72	120
	Caltech 256 -30	generic object recog.	30	20	257
	Caltech 256 -60	generic object recog.

Table 2 .

 2 Average classification accuracies (in %) of L 2 , L 2 -SP and L 2 -SP-Fisher on 5 different runs. The source database is Places 365 for MIT Indoors 67 and ImageNet for Stanford Dogs 120 and Caltech 256.

			MIT Indoors 67 Stanford Dogs 120 Caltech 256 -30 Caltech 256 -60
		L 2	79.6±0.5	81.4±0.2	81.5±0.2	85.3±0.2
		L 2 -SP	84.2±0.3	85.1±0.2	83.5±0.1	86.4±0.2
		L 2 -SP-Fisher	84.0±0.4	85.1±0.2	83.3±0.1	86.0±0.1
	L 2	L 2 -S P

Table 3 .

 3 Classification accuracy drops (in %) on the source tasks due to fine-tuning based on L 2 , L 2 -SP and L 2 -SP-Fisher regularizers. The source database is Places 365 for MIT Indoors 67 and ImageNet for Stanford Dogs 120 and Caltech 256. The classification accuracies of the pre-trained models are 54.7% and 76.7% on Places 365 and ImageNet respectively.

		L 2	L 2 -SP L 2 -SP-Fisher
	MIT Indoors 67	-24.1	-5.3	-4.9
	Stanford Dogs 120 -14.1	-4.7	-4.2
	Caltech 256 -30	-15.4	-4.2	-3.6
	Caltech 256 -60	-16.9	-3.6	-3.2

  Table 4 shows our results. Caltech 256 -30 outperforms the state of the art; our results in MIT Indoors 67 and Stanford Dogs 120 are very close to the state of the art, noting that the best performing approach (Ge & Yu 2017) used many training examples from source domain to improve performance. On our side, we did not use any other examples and simply changed the regularization approach from L 2 to L 2 -SP.

Table 4 .

 4 Average classification accuracies (in %) for L 2 and L 2 -SP using the training tricks presented in Section B. The source database is Places 365 for MIT Indoors 67 and ImageNet for Caltech 256, Stanford Dogs and Foods. References for the state of the art are taken from[START_REF] Ge | Borrowing treasures from the wealthy: Deep transfer learning through selective joint fine-tuning[END_REF], except for Foods-101 where it is taken from[START_REF] Martinel | Wide-slice residual networks for food recognition[END_REF].

		Caltech 256 -30 Caltech 256 -60 MIT Indoors 67 Stanford Dogs 120 Foods 101
	L 2	82.7±0.2	86.5±0.4	80.7±0.9	83.1±0.2	86.7±0.2
	L 2 -SP	84.9±0.1	87.9±0.2	85.2±0.3	89.8±0.2	87.1±0.1
	Reference	83.8±0.5	89.1±0.2	85.8	90.3	90.3

Table 5 .

 5 Mean IoU scores on Cityscapes validation set. Finetuning with L 2 , Chen et al. (2017) obtained 66.6 and 70.4 for ResNet-101 and DeepLab respectively.reproduce them with L 2 and L 2 -SP on Cityscapes under the same setting.Most of the training tricks used for classification apply to segmentation, and we precise here the difference. Images are randomly cropped to 800×800, 2 examples are used in a batch, and batch normalization layers are frozen to keep pre-trained statistics. We use the polynomial learning rate policy as inChen et al. (

	Method	L 2	L 2 -SP
	ResNet-101 68.1 68.7
	DeepLab	72.0 73.2

Acknowledgments

This work was carried out with the supports of the China Scholarship Council and of a PEPS grant through the DESSTOPT project jointly managed by the National Institute of Mathematical Sciences and their Interactions (IN-SMI) and the Institute of Information Science and their Interactions (INS2I) of the CNRS, France. We acknowledge the support of NVIDIA Corporation with the donation of GPUs used for this research.


Aurélien Garivier
email: aurelien.garivier@math.univ-toulouse.fr

Pierre Ménard
email: pierre.menard@math.univ-toulouse.fr

Laurent Rossi
email: laurent.rossi@math.univ-toulouse.fr

Thresholding Bandit for Dose-ranging: The Impact of Monotonicity

Keywords: thresholding bandits, multi-armed bandits, best arm identification, unimodal regression, isotonic regression

published or not. The documents may come

Introduction

The phase 1 of clinical trials is devoted to the testing of a drug on healthy volunteers for dose-ranging. The first goal is to determine the maximum tolerable dose (MTD), that is the maximum amount of the drug that can be given to a person before adverse effects become intolerable or dangerous. A target tolerance level is chosen (typically 33%), and the trials aim at identifying quickly which is the dose entailing the toxicity coming closest to this level. Classical approaches are based on dose escalation, and the most well-known is the "traditional 3+3 Design": see Le [START_REF] Le Tourneau | Dose escalation methods in phase i cancer clinical trials[END_REF]; [START_REF] Mark C Genovese | Efficacy and safety of secukinumab in patients with rheumatoid arthritis: a phase ii, dose-finding, double-blind, randomised, placebo controlled study[END_REF] for and references therein for an introduction.

We propose in this chapter a complexity analysis for a simple model of phase 1 trials, which captures the essence of this problem. We assume that the possible doses are x 1 < . . . < x K , for some positive integer K. The patients are treated in sequential order, and identified by their rank. When the patient number t is assigned a dose x k , we observe a measure of toxicity X k,t which is assumed to be an independent random variable. Its distribution ν k characterizes the toxicity level of dose x k . To avoid obfuscating technicalities, we treat here the case of Gaussian laws with known variance and unknown mean, but some results can easily be extended to other one-parameter exponential families such as Bernoulli distributions. The goal of the experiment is to identify as soon as possible the dose x k which has the toxicity level µ k closest to the target admissibility level S, with a controlled risk δ to make an error.

Content. This setting is an instance of the thresholding bandit problem: we refer to [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF] for an important contribution and a nice introduction in the fixed budget setting. Contrary to previous work, we focus here on identifying the exact sample complexity of the problem: we want to understand precisely (with the correct multiplicative constant) how many samples are necessary to take a decision at risk δ. We prove a lower bound which holds for all possible algorithms, and we propose an algorithm which matches this bound asymptotically when the risk δ tends to 0.

But the classical thresholding bandit problem does not catch a key feature of phase 1 clinical trials: the fact that the toxicity is known in hindsight to be increasing with the assigned dose. In other words, we investigate how many samples can be spared by algorithms using the fact that µ 1 < µ 2 < . . . < µ K . Under this assumption, we prove another lower bound on the sample complexity, and provide an algorithm matching it. The sample complexity does not take a simple form (like a sum of inverse squares), but identifying it exactly is essential even in practice, since it is the only way known so far to construct an algorithm which reaches the lower bound.

We are thus able to quantify, for each problem, how many samples can be spared when means are sorted, at the cost of a slight increase in the computation cost of the algorithm.

Connections to the State of the Art. Phase 1 clinical trials have been an intense field of research in the statistical community (see Le [START_REF] Le Tourneau | Dose escalation methods in phase i cancer clinical trials[END_REF] and references therein), but not considered as a sequential decision problem using the tools of the bandit literature. The important progress made in the recent years in the understanding of bandit models has made it possible to shed a new light on this issue, and to suggest very innovative solutions. The closest contribution are the works of [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF] and Chen et al. (2014), which provides a general framework for combinatorial pure exploration bandit problems. This work tackles the more specific issue of phase 1 trials. It aims at providing strong foundations for such solutions: it does not yet tackle all the ethical and practical constraints. Observe that it might also be relevant to look for the highest dose with toxicity below the target level: we discuss this variant in Section 4; however, it seems that practitioners do not consider this alternative goal in priority.

From a technical point the view, the approach followed here extends the theory of Best-Arm Identification initiated by [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF] to a different setting. Building on the mathematical tools of that paper, we analyze the characteristic time of a thresholding bandit problem with and without the assumptions that the means are increasing. Computing the complexity with such a structural constraint on the means is a challenging task that had never been done before. It induces significant difficulties in the theory, but (by using isotonic regression) we are still able to provide a simple algorithm for computing the complexity term, which is of fundamental importance in the implementation of the algorithm. The computational complexity of the resulting algorithm is discussed in Section 3.1.

Organization. These lower bounds are presented in Section 2. We compare the complexities of the non-monotonic case versus the increasing case. This comparison is particularly simple and enlightening when K = 2, a setting often referred to as A/B testing. We discuss this case in Section 2.1, which furnishes a gentle introduction to the general case. We present in Section 3 an algorithm and show that it is asymptotically optimal when the risk δ goes to 0. The implementation of this algorithm requires, in the increasing case, an involved optimization which relies on constraint sub-gradient ascent and unimodal regression: this is detailed in Section 3.1. Section 3.2 shows the results of some numerical experiments for different strategies with high level of risk that complement the theoretical results. Section 4 discusses the interesting, but simpler variant of the problem where the goal is to identify the arm with mean closest, but also below the threshold. Section 5 summarizes further possible developments, and precedes most of the technical proofs which are given in appendix.

Notation and Setting

For K 2, we consider a Gaussian bandit model N (µ 1 , 1), . . . , N (µ K , 1) , which we unambiguously refer to by the vector of means µ = µ 1 , . . . , µ K . Let P µ and E µ be respectively the probability and the expectation under the Gaussian bandit model µ. A threshold S ∈ R is given, and we denote by a * µ ∈ arg min 1 a K |µ a -S| any optimal arm. Let M be the set of Gaussian bandit models with an unique optimal arm and I = {µ ∈ M : µ 1 < ... < µ K } be the subset of models with increasing means.

Definition of a δ-correct algorithm.

A risk level δ ∈ (0, 1) is fixed. At each step t ∈ N * an agent chooses an arm A t ∈ {1, . . . , K} and receives a conditionally independent reward Y t ∼ N (µ At , 1). Let F t = σ(A 1 , Y 1 , . . . , A t , Y t ) be the information available to the player at step t. Her goal is to identify the optimal arm a * µ while minimizing the number of draws τ . To this aim, the agent needs:

• a sampling rule

(A t ) t 1 , where A t is F t-1 -measurable,
• a stopping rule τ δ , which is a stopping time with respect to the filtration (F t ) t 1 ,

• a F τ δ -measurable decision rule a τ δ .

For any setting S ∈ {M, I} (the non-monotonic or the increasing case), an algorithm is said to be δ-correct on S if for all µ ∈ S it holds that P µ (τ δ < +∞) = 1 and P µ ( a τ δ = a * µ ) δ.

Lower Bounds

For S ∈ {M, I}, we define the set of alternative bandit problems of the bandit problem µ ∈ M by Alt(µ, S) := {λ ∈ S :

a * λ = a * µ } , ( 1
)
and the probability simplex of dimension K -1 by Σ K . The first result of this chapter is a lower bound on the sample complexity of the thresholding bandit problem, which we show in the sequel to be tight when δ is small enough.

Theorem 1 Let S ∈ {M, I} and δ ∈ (0, 1/2]. For all δ-correct algorithm on S and for all bandit models µ ∈ S,

E µ [τ δ ] T * S (µ) kl(δ, 1 -δ) , ( 2
)
where the characteristic time T * S (µ) is given by

T * S (µ) -1 = sup ω∈Σ K inf λ∈Alt(µ,S) K a=1 ω a (µ a -λ a ) 2 2 . ( 3
)
In particular, this implies that

lim inf δ→0 E µ [τ δ ] log(1/δ) T * S (µ) .
This result is a generalization of Theorem 1 of [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]: the classical Best Arm Identification problem is a particular case of our non-monotonic setting S = M with an infinite threshold S = +∞. It is proved along the same lines. As [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], one proves that the supremum and the infimum are reached at a unique value, and in the sequel we denote by ω * (µ) the optimal weights ω * (µ) := arg max

ω∈Σ K inf λ∈Alt(µ,S) K a=1 ω a (µ a -λ a ) 2 2 . ( 4
)

The Two-armed Bandit Case

As a warm-up, we treat in the section the case K = 2. Here (only), one can find an explicit formula for the characteristic times.

Proposition 2 When K = 2,

T * I (µ) -1 = (2S -µ 1 -µ 2 ) 2 8 , ( 5
)
T * M (µ) -1 = min (2S -µ 1 -µ 2 ) 2 , (µ 1 -µ 2 ) 2 8 . ( 6
)
Proof The Equality ( 6) is a simple consequence of Lemma 3 proved in Section A.2. It remains to treat the first Equality (5). Let µ ∈ I and suppose, without loss of generality, that arm 2 is optimal. Let m = (µ 1 + µ 2 )/2 be the mean of two arms and ∆ = µ 2 -µ 1 be the gap. Noting that

{arm 1 is optimal} ⇔ m > S and {arm 2 optimal} ⇔ m < S ,
we obtain

T * I (µ) -1 = sup ω∈[0,1] inf µ 1 <µ 2 , |S-µ 1 |<|S-µ 2 | ω 2 (µ 1 -µ 1 ) 2 + 1 -ω 2 (µ 2 -µ 2 ) 2 = sup ω∈[0,1] A(ω) ,
where m = (µ 1 + µ 2 )/2, ∆ = µ 2 -µ 1 and we denote by A(ω) the function

A(ω) := inf {∆ >0, m >S} ω 2 m -m -(∆ -∆ )/2 2 + 1 -ω 2 m -m + (∆ -∆ )/2 2 .
Writing χ = S -m, easy computations lead to

A(ω) = 2ω(1 -ω)χ 2 if ∆ + 2(2ω -1)χ > 0 , χ 2 + (∆/2) 2 + (2ω -1)χ∆ /2 else.
Thus, since the maximum of A is attained at ω = 1/2, we just proved that T * I (µ) -1 = χ 2 /2.

Note that for both alternative sets the optimal weights defined in Equation ( 4) are uniform:

ω * = [1/2, 1/2].
If the alternative set is I, the optimal alternative, i.e. the element λ of Alt(µ, I) (the closure of Alt(µ, I)) which reaches the infimum in (3) for the optimal weights ω * , is λ = [S -(µ 2 -µ 1 )/2, S + (µ 2 -µ 1 )/2]. In words, in the optimal alternative the arms are translated in such a way that the mean of the two mean values is moved to the threshold S. If the alternative set is M and µ ∈ I, the optimal alternatives can be of two different forms. If the threshold is between the two mean values, then the optimal alternative is the same as for the increasing case. Otherwise, the optimal alternative is identical to the one of Best Arm Identification (see [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]): λ = [(µ 1 + µ 2 )/2, (µ 1 + µ 2 )/2]. Thus, if µ 1 S µ 2 , the two characteristic times coincide, as can be seen in Figure 2. (6,8,11,14). Top: inverse of the characteristic time as a function of the threshold S; red solid line: non-monotonic case S = M; blue dotted line: increasing case S = I. Middle: how to move the means to get from the initial bandit model to the optimal alternative in M.

Bottom: the optimal weights in function of the threshold S.

1 2 3 4 5 S 0.0 0.2 0.4 0.6 0.8 1.0 1.2 T * M ( ) 1 T * I ( ) 1

On the Characteristic Time and the Optimal Proportions

We now illustrate, compare and comment the different complexities for a general bandit model µ ∈ I with K 2 (see Figure 1). Since I ⊂ M, it is obvious that

T * I (µ) T * M (µ). The difference T * M (µ) -T * I (µ)
is almost everywhere positive, and can be very large. Both T * I (µ) and T * M (µ) tend to +∞ as S tends to middle of two consecutive arms. On the structure of the optimal weights in the non-monotonic case.

Lemma 3 For all µ ∈ M,

T * M (µ) -1 = max ω∈Σ K min b =a * ω a * µ ω b 2(ω a * µ + ω b ) min (µ a * µ -µ b ) 2 , (2S -µ a * µ -µ b ) 2 .
In the non-monotonic case S = M, there are two types of optimal alternatives (as in Section 2.1). Indeed, the proof of Lemma 3 in Appendix A.2 shows that the best alternative takes one of the two following forms. Either the optimal arm µ a * µ and its challenger µ b are moved to a pondered mean (by the optimal weights ω * ) of the two arms (just like in the Best Arm Identification problem), leading to a constant (µ a * µ -µ b ) 2 in Equation ( 7). Or, as in the increasing case S = I (see the proof of Proposition 2), both arms µ a * µ and µ b are translated in the same direction, leading to the constant (2S -µ a * µ -µ b ) 2 . Figure 1 summarizes the different possibilities on a simple example with K = 4 arms, for different values of the threshold S. According to the value of S, the best alternative is shown in the second plot from the top.

On the structure of the optimal weights in the increasing case. In the increasing case S = I, one can show the remarkable property that the optimal weights ω * (µ) put mass only on the optimal arm and its two closest arms. This strongly contrasts with the non-monotonic case, as illustrated at the bottom of Figure 1. For simplicity we assume that 1 < a * µ < K. Let ω be some weights in Σ 3 . Let D + (θ, ω) be the cost, with weights ω, for moving from the initial bandit problem µ to a bandit problem λ + where arm a * µ has mean θ S and S is halfway between µ a * µ and µ a * µ +1 ,

λ + a =        µ a if a > a * µ + 1 , 2S -θ if a = a * µ + 1 , θ if a = a * µ , min(θ, µ a ) if a a * µ -1 .
The explicit formula for D + (θ, ω) is

D + (θ, ω) = ω -1 µ a * µ -1 -min(µ a * µ -1 , θ) 2 2 + ω 0 (µ a * µ -θ) 2 2 + ω 1 µ a * µ +1 -(2S -θ) 2 2 .
Similarly we can do the same with arm a * µ -1: moving from µ to a bandit problem λ -, defined for θ S by

λ - a =        µ a if a < a * µ -1 , 2S -θ if a = a * µ -1 , θ if a = a * µ , max(θ, µ a ) if a a * µ + 1
, where both arms a * µ -1 and a * µ are optimal. For this alternative the cost is

D -(θ, ω) = ω -1 µ a * µ -1 -(2S -θ) 2 2 + ω 0 (µ a * µ -θ) 2 2 + ω 1 µ a * µ +1 -max(µ a * µ +1 , θ) 2 2 .
It appears, see the proof of Proposition 4 in Appendix A.1, that these two types of alternative λ + and λ -are the optimal one. Note that they are also in Alt(µ, I), the closure of the set of alternatives of µ.

Proposition 4 For all µ ∈ I,

T * I (µ) -1 = sup ω∈Σ 3 min min {2S-µ a * µ +1 θ S} D + (θ, ω), min {S θ 2S-µ a * µ -1 } D -(θ, ω) . ( 7
)
The intuition behind this proposition is that if we try to transform µ into an alternative λ with b > a * µ + 1 as optimal arm we have to pass by an alternative with optimal arm a * µ + 1 since we impose to the means to be increasing. It remains to see that this intermediate alternative has always a smaller cost. The cases with a * µ = 1 or K are similar considering only the the alternatives λ + if a * µ = 1 and λ -if a * µ = K. We can also derive bounds on the characteristic time to see that the dependence in K disappear. It is important to note that this property is really asymptotic when δ goes to zero and it is not clear at all that the dependence of the complexity in K would also disappear for moderate value of δ, we think it is not the case.

Proposition 5 For all µ ∈ I such that 1 < a * µ < K, considering the gaps:

∆ 2 -1 = (2S -µ a * µ -1 -µ a * µ ) 2 /8, ∆ 2 1 = (2S -µ a * µ +1 -µ a * µ ) 2 /8 and ∆ 2 0 = min(∆ 2 -1 , ∆ 2 1 ), 1 ∆ 2 0 T * I (µ) 1 k=-1 1 ∆ 2 k 3 ∆ 2 0 . ( 8
)

An Asymptotically Optimal Algorithm

We present in this section an asymptotically optimal algorithm inspired by the Directtracking procedure of [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] (which borrows the idea of tracking from GAFS-MAX algorithm of [START_REF] Antos | Active learning in multi-armed bandits[END_REF]). At any time t 1 let h(t) = ( √ t -K/2) + (where (x) + stands for the positive part of x) and U t = {a : N a (t) < h(t)} be the set of "abnormally rarely sampled" arms. After t rounds the empirical mean of arm a is

µ a (t) = µ a,Na(t) = 1 N a (t) t s=1 Y s 1 {As=a} ,
where N a (t) = t s=1 1 {As=a} denotes the number of draws of arm a up to and including time t.

Algorithm 1: Algorithme (Direct-tracking).

Sampling rule

A t+1 ∈    argmin a∈Ut N a (t) if U t = ∅ (forced exploration) argmax 1 a K t w * a ( µ(t)) -N a (t) (direct tracking)
Stopping rule

τ δ = inf t ∈ N * : µ(t) ∈ M and inf λ∈Alt µ(t),S K a=1 N a (t) ( µ a (t) -λ a ) 2 2 > β(t, δ) . ( 9
)
Decision rule

a τ δ ∈ arg min 1 a K µ a (τ δ ) -S . When L := Card{arg min 1 a K | µ a (t)-S|} > 1, we adopt the convention that T * S µ(t) -1 = 0 and w * a ( µ(t)) = 1/L if a ∈ arg min 1 a K | µ a (t) -S| , 0 otherwise.

Theorem 6 (Asymptotic optimality)

For S ∈ {I, M}, for the constant

C = e K+1 2 K K 2(3K + 2) 3K 4
log(3) and for β(t, δ) = log(tC/δ)+(3K+2) loglog(tC/δ), Algorithm 1 is δ-correct on S and asymptotically optimal, in the sense that lim sup

δ→0 E µ [τ δ ] log(1/δ) T * S (µ) . ( 10
)
The analysis of Algorithm 1 is the same in both the increasing case S = I and the nonmonotonic case S = M. It is deferred to Appendix B. However, the practical implementations are quite specific to each case, and we detail them in the next section.

On the Implementation of Algorithm 1

The implementation of Algorithm 1 requires to compute efficiently the optimal weights w * (µ) given by Equation (4). For the non-monotonic case S = M, one can follow the lines of [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], Section 2.2 and replace their Lemma 3 by Lemma 3 above.

In the increasing case S = I, however, implementing the algorithm is more involved. It is not sufficient to simply use Proposition 4, since µ(t) is not necessarily in I. Let I b := {λ ∈ I, a * λ = b} be the set of alternatives with b as optimal arm. Noting that the function

F : w → inf λ∈Alt(µ,I) K a=1 ω a (µ a -λ a ) 2 2 = min b =a * µ inf λ∈I b K a=1 ω a (µ a -λ a ) 2 2 (11)
is concave (since it is the infimum of linear functions), one may access to its maximum by a sub-gradient ascent on the probability simplex Σ K (see e.g. [START_REF] Boyd | Subgradient methods[END_REF]). Let I b denote the closure of I b , and let

λ b := arg min λ∈I b K a=1 ω a (µ a -λ a ) 2 2 (12)
be the argument of the second infimum in Equation ( 11). The sub-gradient of F at ω is

∂F (ω) = Conv b∈B Opt (µ a -λ b a ) 2 2 a∈{1,••• ,K}
, where Conv denotes the convex hull operator and where B Opt is the set of arms that reach the minimum in (11). Thus, performing the sub-gradient ascent simply requires to solve efficiently the minimization program (12). It appears that this problem boils down to unimodal regression (a problem closely related to isotonic regression, see for example [START_REF] Barlow | Statistical inference under order restrictions[END_REF] and Robertson et al. (1988)). Indeed, we can rewrite the set

{λ ∈ I : a * λ = b} = {λ ∈ M : λ 1 < . . . < λ b-1 < min(λ b , 2S -λ b ) max(λ b , 2S -λ b ) < λ b+1 < . . . < λ K } .
Assume that µ b S (the other case is similar). Then λ b b < S, since λ b and 2S -λ b play a symmetric role in the constraints. Thus, in this case, one may only consider the set

{λ ∈ M :λ 1 < . . . < λ b-1 < λ b , 2S -λ K < . . . < 2S -λ b+1 < λ b , λ b S} .
Let λ be the new variables such that

λ a = λ a if 1 a b , 2S -λ a else . ( 13
)
Then λ b is the solution of the following minimization program

λ b = arg min λ 1 ... λ b λ K ... λ b λ b S K a=1 ω a (µ a -λ a ) 2 2 . ( 14
)
Thanks to Lemma 12 in Appendix C, it holds that

λ b a = min( λ b a , S) for all a ∈ {1, . . . , K} ,
where

λ b := arg min λ 1 ... λ b λ K ... λ b K a=1 ω a (µ a -λ a ) 2 2 ,
is the unimodal regression of µ with weights ω and with a mode located at b. It is efficiently computed via isotonic regressions (e.g. [START_REF] Frisén | Unimodal regression[END_REF], [START_REF] Geng | Algorithm as 257: isotonic regression for umbrella orderings[END_REF], Mureika et al. ( 1992)) with a computational complexity proportional to the number of arms K. From λ b , one can go back to λ b by reversing Equation ( 13). Since we need to compute λ b for each b = a * µ , the overall cost of an evaluation of the sub-gradient is proportional to K 2 .

Numerical Experiments

Table 1 presents the results of a numerical experiment of an increasing thresholding bandit.

In addition to Algorithm 1 (DT), we tried the Best Challenger (BC) algorithm with the finely tuned stopping rule given by (9). We also tried the Racing algorithm (R), with the elimination criterion of (9). For a description of all those algorithms, see [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] and references therein. Finally, in order to allow comparison with the state of the art, we added the sampling rule of algorithm APT (Anytime Parameter-free Thresholding algorithm) from [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF] in combination with the stopping rule (9). We chose to set the parameter ε of APT to be roughly equal to a tenth of the gap. It appears that the exploration function β prescribed in Theorem 6 is overly pessimistic. On the basis of our experiments, we recommend the use of β(t, δ) = log log(t) + 1 /δ instead. It does, experimentally, satisfy the δ-correctness property. For each algorithm, the final letter in Table 1 indicates whether the algorithm is aware (I) or not (M) that the means are increasing. We consider two frameworks: in the first one, knowing that the means are increasing provides much information and gives a substantial edge: it permits to spare a large portion of the trials for the same level of risk. In the second, the complexities of the non-monotonic setting is very close to that of the increasing setting. We chose a value of the risk δ which is relatively high (10%), in order to illustrate that in this regime, the most important feature for efficiency is a finely tuned stopping rule. This shows that, even without an optimal sampling strategy, the stopping rule of ( 9) is a key feature of an efficient procedure. When the risk goes down to 0, however, optimality really requires a sampling rule which respects the proportions of Equation ( 4), as shown by Theorem 6. The poor performances of APT can be explained by the crude adaptation of this algorithm to the fixed confidence setting. This possibly comes from the fact that it was originally designed for the fixed budget setting and it appears that these two frameworks are fundamentally different, as argued by [START_REF] Carpentier | Tight (lower) bounds for the fixed budget best arm identification bandit problem[END_REF].

BC-M R-M DT-M APT-M T * M (µ)

Closest mean below the threshold

In this section we briefly discuss a variant of the previous problem: finding the arm with the closest mean below the threshold, i.e. a * µ ∈ arg min 1 a K : µa S |µ a -S|, still under the assumption that the means are increasing. Surprisingly this new problem is simpler than the previous one and it is possible to compute exactly, in this case, the optimal weights and the characteristic time.

Let µ ∈ I be a bandit problem such that the optimal arm a * µ for this new setting is unique (with 1 < a * µ < K for the sake of clarity). As in Section 2.2, we only need to consider alternative bandit problems such that arm a µ -1 or a µ + 1 is optimal. But only one arm needs to be moved: the optimal alternative λ -(resp. λ + ) where a µ -1 (resp. a µ + 1) is optimal are defined by

λ - a = S if a = a * µ , µ a else, and λ + a = S if a = a * µ + 1 , µ a else. ( 15
)
With the same arguments used to prove Proposition 4, one obtains that

T * I (µ) -1 = sup ω∈Σ 2 min ω -(S -µ a * µ ) 2 2 , ω + (µ a * µ +1 -S) 2 2 = 1 2 (S -µ a * µ ) 2 + 2 (µ a * µ +1 -S) 2 , ( 16
)
and that the associated optimal weights ω * (µ) are defined by

ω * (µ) a =            2 (S-µ a * µ ) 2 2 (S-µ a * µ ) 2 + 2 (µ a * µ +1 -S) 2 -1 if a = a * µ , 2 (µ a * µ +1 -S) 2 2 (S-µ a * µ ) 2 + 2 (µ a * µ +1 -S) 2 -1 if a = a * µ + 1 , 0 else.
In some way, this problem is closer to the classical threshold bandit problem [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF] with two arms since we are testing if the mean of arms a µ and a µ + 1 is below or above the threshold.

For an optimal strategy, Algorithm 1 can be adapted to this new setting, as well as the Theorem 6 and its asymptotic optimality proof. The only point that needs to be discussed is how to implement this algorithm in practice. One may follow the procedure described in Section 3.1: perform an gradient ascent on the simplex to compute the maximum of F defined in (11). The main difficulty is to compute the sub-gradient of F at ω ∈ Σ K and in particular the projection given by ( 12), that rewrites in this setting

λ b = arg min λ 1 ... λ b S S λ b+1 ... λ K K a=1 ω a (µ a -λ a ) 2 2 . ( 17
)
But this projection can also be easily computed using two isotonic regressions under bound restrictions, see for example [START_REF] Hu | Maximum-likelihood estimation under bound restriction and order and uniform bound restrictions[END_REF].

Conclusion

We provided a tight complexity analysis of the dose-ranging problem considered as a thresholding bandit problem with, and without, the assumption that the means of the arms are increasing. We proved that, surprisingly, the complexity terms can be computed almost as easily as in the best-arm identification case, despite the important constraints of our setting. We proposed a lower bound on the expected number of draws for any δ-correct algorithm and adapted the Direct-Tracking algorithm to asymptotically reach this lower bound. We also compared the complexities of the non-monotonic and the increasing cases, both in theory and on an illustrative example. We showed in Section 3.1 how to compute the optimal weights thanks to a sub-gradient ascent in the increasing case, a new and non-trivial task relying on unimodal isotonic regression. In order to complement the theoretical results, we presented some numerical experiments involving different strategies in a regime of high risk. In fact, despite the asymptotic nature of the results presented here, the procedure proposed here appears to be the most efficient in practice even when the number of trials implied is rather low (which is often the case in clinical trials).

In the case where several arms are simultaneously closest to the threshold, the complexity of the problem is infinite. This suggests to extend the results presented here to the PAC setting, where the goal is to find any ε-closest arm with probability at least 1 -δ. This extension, and extensions to the non-Gaussian case, are left for future investigation since they induce significant technical difficulties.

As a possibility of improvement, we can also mention the possible use of the unimodal regression algorithm of Stout (2000) in order to compute directly (11) with a complexity of order O K). We treated here mostly the case of Gaussian distributions with known variance. While the general form of the lower bound may easily be extended to other settings (including Bernoulli observations), the computation of the complexity terms is more involved and requires further investigations (in particular due to heteroscedasticity effects). The asymptotic optimality of Algorithm 1, however, can be extended directly. It remains important but very challenging tasks to make a tight analysis for moderate values of δ, to measure precisely the sub-optimality of Racing and Best Challenger strategies, and to develop a more simple and yet asymptotically optimal algorithm.

2 + ω 0 (µ a * -θ) 2 2 .
Proof [of Proposition 4] We just treat here the case 1 < a * < K, the two other limit cases are very similar. We begin by proving that for all ω ∈ Σ K inf λ∈Alt(µ,S)

K a=1 ω a (µ a -λ a ) 2 2 = min b∈{a * -1,a * +1} inf {λ∈I : a * λ =b} K a=1 ω a (µ a -λ a ) 2 2 . ( 20
)
Indeed, let λ ∈ I such that a * λ / ∈ {a * -1, a * + 1}. Suppose for example that a * λ < a * -1. Let λ α be the family of bandit problems defined for α ∈ [0, 1] by

λ α = αλ + (1 -α)µ .
For all α ∈ [0, 1], we have λ ∈ I. For ν ∈ I and a ∈ {0, .., K}, let m a (ν) = (ν a +ν a+1 )/2 be the average of two consecutive means with the convention m 0 (ν) = -∞ and m K (ν) = +∞. As in the case of two arms we have that a * ν = a is equivalent to m a (ν) > S and m a (ν) < S. Therefore we have the following inequalities

m a * λ -1 (µ) < m a * λ (µ) m a * -2 (µ) < m a * -1 (µ) < S < m a * (µ) and m a * λ -1 (λ) < S < m a * λ (λ) m a * -2 (λ) < m a * -1 (λ) < m a * (λ) .
Thus, by continuity of the applications α → m a (λ α ) there exits α 0 ∈ (0, 1) such that

m a * λ -1 (λ α 0 ) < m a * λ (λ α 0 ) m a * -2 (λ α 0 ) < S < m a * -1 (λ α 0 ) < m a * (λ α 0 ) , i.e. a * λ α 0 = a * -1. But α → K a=1 ω a (µa-λ α a ) 2 2
is an increasing function, and thus

K a=1 ω a (µ a -λ α 0 a ) 2 2 < K a=1 ω a (µ a -λ a ) 2 2 .
This holds for all λ, therefore inf λ∈Alt(µ,S)

K a=1 ω a (µ a -λ a ) 2 2 min b∈{a * -1,a * +1} inf {λ∈I : a * λ =b} K a=1 ω a (µ a -λ a ) 2 2 .
The reverse inequality follows from the inclusion

b∈{a * -1,a * +1} {λ ∈ I : a * λ = b} ⊂ Alt(µ, I) .
Fix ω ∈ Σ K and let λ ∈ I be such that, say, a * λ = a * +1 (the other case is similar). Then it implies λ a * S and we can suppose, without loss of generality, that

λ a * 2S -µ a * +1 since it holds inf {λ∈I : a * λ =a * +1} K a=1 ω a (µ a -λ a ) 2 2 = inf {λ∈I : a * λ =a * +1, λ a * 2S-µ a * +1 } K a=1 ω a (µ a -λ a ) 2 2 . ( 21
)
Let λ be such that

λ a =        µ a if a > a * + 1 , 2S -λ a * if a = a * + 1 , λ a * if a = a * , min(λ a * , µ a ) if a a * -1 . By construction we have λ ∈ {λ ∈ I : a * λ = a * + 1}. As λ a * +1 2S -λ a * and µ a * +1 2S -λ a * hold, we get ( λ a * +1 -µ a * +1 ) 2 (λ a * +1 -µ a * +1 ) 2 .
Similarly, for a a * -1 we have thanks to the fact that λ a λ a * the inequality

( λ a * +1 -µ a * +1 ) 2 (λ a * +1 -µ a * +1 ) 2 .
Therefore, combining these two inequalities and using the definition of λ, one obtains

K a=1 ω a (µ a -λ a ) 2 2 K a=1 ω a (µ a -λ a ) 2 2 ,
and we can rewrite the infimum in Equation 21, indexing the alternative λ by θ the mean of arm a, as follows:

inf {λ∈I : a * λ =a * +1} K a=1 ω a (µ a -λ a ) 2 2 = min 2S-µ a * +1 θ S a a * -1 ω a (µ a -min θ, µ a ) 2 2 + ω a * (µ a * -θ) 2 2 + ω a * +1 (µ a * +1 -2S + θ) 2 2 = min 2S-µ a * +1 θ S a<a * -1 ω a (µ a -min θ, µ a ) 2 2 (22) + D + (θ, [ω a * -1 , ω a * , ω a * +1 ]) .
Similarly, if the optimal arm of the alternative is a * -1, we get inf

{λ∈I : a * λ =a * -1} K a=1 ω a (µ a -λ a ) 2 2 = min S θ 2S-µ a * -1 a>a * +1 ω a (µ a -max θ, µ a ) 2 2 (23) + D -(θ, [ω a * -1 , ω a * , ω a * +1 ]) .
Then, by noting that

(µ a -max θ, µ a ) 2 (µ a * +1 -max θ, µ a * +1 ) 2 ∀a a * + 1 (µ a -min θ, µ a ) 2 (µ a * -1 -min θ, µ a * -1 ) 2 ∀a a * -1
and by using the new weights ω defined by

ω a =        b a * -1 w b if a = a * -1 ω a if a = a * b a * +1 w b if a = a * + 1 0 else ,
we obtain thanks to Equation ( 20) and to the fact that ω depends only on ω:

inf λ∈Alt(µ,S) K a=1 ω a (µ a -λ a ) 2 2 min min {2S-µ a * +1 θ S} D + (θ, ω), min {S θ 2S-µ a * -1 } D -(θ, ω) , ( 24
)
where we identified ω to an element of Σ 3 . Taking the supremum on each side of (24), one obtains:

T * I (µ) -1 sup ω∈Σ 3 min min {2S-µ a * +1 θ S} D + (θ, ω), min {S θ 2S-µ a * -1 } D -(θ, ω) .
In order to prove the reverse inequality and thus (7), we just need to use ( 23), ( 22) and restrict the weight ω to have a support included in {a * -1, a * , a * + 1}.

Proof [of Proposition 5] We recall the definitions of the gaps: ∆

2 -1 = (2S -µ a * -1 -µ a * ) 2 /8, ∆ 2 1 = (2S -µ a * +1 -µ a * ) 2 /8 and ∆ 2 0 = min(∆ 2 -1 , ∆ 2 1 )
. For the lower bound we consider the particular weights ω ∈ Σ 3 defined by

ω i = 1/∆ 2 i 1 k=-1 1/∆ 2 k for -1 i 1 .
Thanks to the Proposition 4, we know that

T * I (µ) -1 min min {2S-µ a * +1 θ S} D + (θ, ω), min {S θ 2S-µ a * -1 } D -(θ, ω) .
Then we can lower bound the two terms that appear in the minimum. Indeed, we have, denoting the mean

θ = ω 0 µ a * + ω 1 (2S -µ a * +1 ), min {2S-µ a * +1 θ S} D + (θ, ω) min {2S-µ a * +1 θ S} ω 0 (µ a * -θ) 2 2 + ω 1 (2S -µ a * +1 ) -θ) 2 2 = ω 0 (µ a * -θ) 2 2 + ω 1 (2S -µ a * +1 ) -θ) 2 2 min(ω 1 , ω 0 )∆ 2 1 1 1 k=-1 1/∆ 2 k ,
where we used the definition of the weights ω for the last inequality and the fact that either

(µ a * -θ) 2 /2 ∆ 2 1 or (2S -µ a * +1 ) -θ) 2 /2
∆ 2 1 since by definition θ belongs to the interval with bounds 2S -µ a * +1 and µ a * for the one before. Similarly one can prove the same inequality with the second term:

min {S θ 2S-µ a * -1 } D -(θ, ω) 1 1 k=-1 1/∆ 2 k ,
therefore we obtain the lower bound

T * I (µ) -1 1 1 k=-1 1/∆ 2 k .
For the upper bound we just need to choose a particular θ in order to bound one of the two terms that appears in the expression of T * I (µ) -1 . Thus, with the choice

θ 1 = (2S -µ a * +1 )/2 + µ a * /2, we get min {2S-µ a * +1 θ S} D + (θ, ω) D + (θ 1 , ω) ( ω -1 + ω 0 + ω 1 ) (2S -µ a * +1 -µ a * ) 2 8 = ∆ 2 1 ,
where we used that µ a * -1 -min(µ a * -1 , θ 1 ) 2 /2 (2S -µ a * +1 -µ a * ) 2 /8 since θ 1 is at the middle between 2S -µ a * +1 and µ a * . In the same way with θ -1 = (2S -µ a * -1 )/2 + µ a * /2 one can obtain min

{2S-µ a * +1 θ S} ∆ 2 -1 .
Combining these two inequalities with Proposition 4 leads to

T * I (µ) -1 ∆ 2 0 .

A.2 Expression of the

K a=1 ω a (µ a -λ a ) 2 2 = min b =a * ω a * ω b 2(ω a * + ω b ) min (µ a * -µ b ) 2 , (2S -µ a * -µ b ) 2 . Using that Alt(µ, M) = b =a * {λ ∈ M : |λ b -S| < |λ a * -S|} , one has inf λ∈Alt(µ,S) K a=1 ω a (µ a -λ a ) 2 2 = min b =a * inf |λ b -S|<|λ a * -S| K a=1 ω a (µ a -λ a ) 2 2 = min b =a * inf |λ b -S|<|λ a * -S| ω a * (µ a * -λ a * ) 2 2 + ω b (µ b -λ b ) 2 2 .
Since at the infimum it holds

|λ b -S| = |λ a * -S|, denoting x = λ b -S, we have λ a * -S = x or -x. Therefore, one obtains inf |λ b -S|<|λ a * -S| ω a * (µ a * -λ a * ) 2 2 + ω b (µ b -λ b ) 2 2 = min inf x ω * a (µ a * -S -x) 2 2 + ω b (µ b -S -x) 2 2 , inf x ω a * (µ a * -S + x) 2 2 + ω b (µ b -S -x) 2 2 . Noting that inf x ω a * (µ a * -S -x) 2 2 + ω b (µ b -S -x) 2 2 = ω a * ω b 2(ω a * + ω b ) (µ a * -µ b ) 2 , inf x ω a * (µ a * -S -x) 2 2 + ω b (µ b -S + x) 2 2 = ω a * ω b 2(ω a * + ω b ) (2S -µ a * -µ b ) 2 ,
permits to conclude.

Appendix B. Correctness and Asymptotic Optimality of Algorithm 1

Proof [of Proposition 6] We follow and slightly adapt the proof of Theorem 14 of [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF]. We fix a bandit problem µ ∈ S and the constant

C := e K+1 2 K K 2(3K + 2) 3K 4 log(3) . ( 25
)
We begin by proving that Algorithm 1 is δ-correctness on S, then we show that it is asymptotically optimal. δ-correctness on S We will prove in the second part of proof that τ is almost surely finite, confer (28). By definition of τ , the probability that the predicted arm is the wrong one is upper-bounded by

P µ ( a τ = a * µ ) P µ ∃t ∈ N * , K a=1 N a (t) ( µ a (t) -µ a ) 2 2 > β(t, δ) , ( 26
)
where we used that µ ∈ Alt µ(t), S since a τ = a * µ . Using the union bound then Theorem 11 (note that β(t, δ) K + 1 thanks to the choice of C ) we have

P µ ( a τ = a * µ ) +∞ t=1 P µ K a=1 N a (t) ( µ a (t) -µ a ) 2 2 > β(t, δ) +∞ t=1 e K+1 2 K K β(t, δ) log(t)β(t, δ) + 1 K e -β(t,δ) e K+1 2 K K +∞ t=1 2(3K + 2) 3K log(tC/δ) 2 δ tC e K+1 2 K K 2(3K + 2) 3K +∞ t=1 1 t log(3t) 2 δ C e K+1 2 K K 2(3K + 2) 3K 2 log(3) δ C δ ,
where in the third inequality we replaced β(t, δ) by its value and used in the fourth inequality, for C 3, the following upper-bound

+∞ t=1 1 t log(3t) 2 1 log(3) 2 + +∞ t=1 1 t log(3t) 2 dt 2 log(3)
.

Asymptotic Optimality

We begin by remarking that the function µ → ω * (µ) is continuous on the sets S b = {µ ∈ S : a * µ = b} for b ∈ {1, . . . , K}. Indeed it is a consequence of Lemma 3 if S = M and Proposition 4 if S = I and the Maximum theorem from [START_REF] Berge | Topological Spaces: including a treatment of multi-valued functions, vector spaces, and convexity[END_REF]. Let ε be a real in (0, 1). From the continuity of w * in µ, there exists α = α(ε) such that the neighbourhood of µ:

I ε := [µ 1 -α, µ 1 + α] × • • • × [µ K -α, µ K + α] is such that for all µ ∈ I ε , µ ∈ S, a * µ = a * µ and max a |w * a (µ ) -w * a (µ)| ε .
Let T ∈ N * and define the typical event where µ(t) is not too far from µ

E T (ε) = T t=T 1/4 ( µ(t) ∈ I ε ) .
The two following Lemmas are extracted from [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF].

Lemma 7 There exists two constants B, C (that depend on µ and ε) such that

P µ (E c T ) BT exp(-CT 1/8 ) .
Lemma 8 There exists a constant T ε such that for T T ε , it holds that on E T ,

∀t √ T , max a N a (t) t -w * a (µ) 2(K -1)ε
We now assume that T T ε . Introducing the constant

C * ε (µ) = inf µ :||µ -µ|| α(ε) w :||w -w * (µ)|| 2(K-1)ε inf λ∈Alt µ ,S K a=1 w a (µ a (t) -λ a ) 2 2 ,
thanks to Lemma 8, on the event E T it holds that for every t √ T ,

t inf λ∈Alt µ(t),S K a=1 N a (t) t ( µ a (t) -λ a ) 2 2 tC * ε (µ) . ( 27
)
Thus, combining ( 27) and the definition of the stopping rule (9), we have on the event

E T max(τ δ , T ) √ T + T t= √ T 1 (τ δ >t) √ T + T t= √ T 1 tC * ε (µ) β(T,δ) √ T + β(T, δ) C * ε (µ) . Introducing T 0 (δ) = inf T ∈ N : √ T + β(T, δ) C * ε (µ) T ,
for every T max(T 0 (δ), T ε ), one has E T ⊆ {τ δ T }, therefore thanks to Lemma 7

P µ (τ δ > T ) P(E c T ) BT exp(-CT 1/8 ) and E µ [τ δ ] T 0 (δ) + T ε + ∞ T =1
BT exp(-CT 1/8 ). ( 28)

We now provide an upper bound on T 0 (δ). Introducing the constant Using technical Lemma 10, for δ small enough to have C * ε (µ)δ / (1 + ε) 2 C e, we get

H(ε) = inf{T ∈ N : T - √ T T /(1 + ε)}
T 0 (δ) C(ε) + δ C max g C * ε (µ)δ (1 + ε) 2 C , exp g ε 3K + 2 C(ε) + max (1 + ε) 2 C * ε (µ) log e(1 + ε) 2 C C * ε (µ)δ log (1 + ε) 2 C C * ε (µ)δ , δ C exp g ε 3K + 2 .
This last upper bound yields, for every ε > 0, lim sup Proof Since log(x) g(ε/B) thanks to Lemma 9 we have B loglog(x) ε log(x). Therefore , still using Lemma 9 with x g A/(1 + ε) , log(x) + B loglog(x) (1 + ε) log(x)

Ax .

C.1.1 A Deviation Bound

We recall here for self-containment the Theorem 2 of [START_REF] Magureanu | Lipschitz bandits: Regret lower bound and optimal algorithms[END_REF].

Theorem 11 For all δ (K + 1) and t ∈ N * we have

P K a=1
N a (t) ( µ a (t) -µ a ) 2 2 δ e K+1 2δ(δ log(t) + 1)

K K e -δ . ( 32
)
The factor 2 that differs from Theorem 2 of [START_REF] Magureanu | Lipschitz bandits: Regret lower bound and optimal algorithms[END_REF] comes from the fact that we consider deviation at the right and left of the mean.

C.1.2 Unimodal Regression under Bound Restriction

) 36
We have, as in the case of isotonic regression (see [START_REF] Hu | Maximum-likelihood estimation under bound restriction and order and uniform bound restrictions[END_REF]), the following simple relation between λ * and λ Lemma 12 It holds that λ * a = min( λ a , S) for all a ∈ {1, . . . , K} . To prove Lemma 12 we need the following properties on λ.

Lemma 13 Let c -k < . . . < c 0 > . . . > c l be real numbers and (A -k , . . . , A 0 , . . . , A k ) be integer intervals forming a partition of {1, . . . , K} be such that λ is constant on the sets A i equals to c i for all -k i l and b ∈ A 0 . Then, for all -k i l and λ ∈ U Fix λ ∈ U and -k i l and suppose, for example, that i < 0. The other cases i = 0 and i > 0 are similar. Introduce, for |ε| < min |c i -c i-1 |, |c i+1 -c i | , the vector λ ε such that

λ ε a = c i -ε if a ∈ A i , λ a else.
By construction λ ε ∈ U and thanks to (39) we have Taking ε positive or negative proves (37). Let x, y ∈ {1, . . . , K} be such that A i = {x, x + 1, . . . , y -1, y} and λ be such that

λ a =    λ a if a ∈ A i , λ x if a < x , λ y if a > y .
By construction λ ∈ U and thanks to (39) we have

Figure 1 :

 1 Figure 1: The complexity terms in the bandit model µ =(6, 8, 11, 14). Top: inverse of the characteristic time as a function of the threshold S; red solid line: non-monotonic case S = M; blue dotted line: increasing case S = I. Middle: how to move the means to get from the initial bandit model to the optimal alternative in M. Bottom: the optimal weights in function of the threshold S.

Figure 2 :

 2 Figure 2: Inverse of the characteristic times as a function of the threshold S, for µ = [2, 4].Solid red: general thresholding case (S = M). Dotted blue: increasing case (S = I).

  Complexity in the Non-monotonic Case Proof [of Lemma 3] To simplify the notations we note a * µ = a * . Thanks to the definition of the characteristic time, we just have to prove that inf λ∈Alt(µ,M)

  ) + inf T ∈ N : log(T C/δ) + (3K + 2) loglog(T C/δ

For

  µ ∈ M, ω ∈ ΣK (where ΣK stands for the interior of Σ K ) and b ∈ {1, • • • , K}, let U be the set of unimodal vector with maximum localized at bU = {λ : λ 1 • • • λ b λ b+1 • • • λ K } , (33)and U S be the same set with an additional bound restriction on λ bU S = {λ : λ 1 • • • λ b λ b+1 • • • λ K , λ b S} .

  -λ a )ω a λ a 0 . (38)Proof Since λ is the projection of µ on the closed convex U we know that for all λ in U A∈{1,...,K} (µ a -λ a )( λ a -λ a )ω a 0 .(39)

  A∈{1,...,K} (µ a -λ a )( λ a -λ ε a )ω a = ε a∈A i (µ a -λ a )ω a 0 .

  A∈{1,...,K} (µ a -λ a )( λ a -λ a )ω a = a∈A i (µ a -λ a )(c i -λ a )ω a +λ x j<i a∈A j (µ a -λ a )ω a + λ y j>i a∈A j (µ a -λ a )ω a = -a∈A i (µ a -λ a )λ a ω a ,

Acknowledgments

The authors thank Wouter Koolen for suggesting a key ingredient in the proof of Proposition 4. The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR), under grants ANR-13-BS01-0005 (project SPADRO) and ANR-13-CORD-0020 (project ALICIA).

Appendix A. Proofs for the Lower Bounds

A.1 Expression of the Complexity in the Increasing Case

Fix µ ∈ I and let a * be the optimal arm a * := a * µ . We recall the definitions of D + (θ, ω) and D -(θ, ω) two functions defined over R × Σ 3 by

Appendix C. Some Technical Lemmas

We regroup in this Appendix some technical lemmas used in the asymptotic analysis of Algorithm 1.

C.1 An Inequality

For 0 < y 1/e let g be the function

Lemma 9 Let A > 0 such that 1/A > e, then for all x g(A)

Proof Since g(A)

1/A, the function x → A -1/x is non-decreasing, we just need to prove (30) for x = g(A). It remains to remark that log g(A)

as log(x) x/e.

Lemma 10 Let A, B > 0, then for all ε ∈ (0, 1) such that (1 + ε)/A < e and B/ε > e, for all x max g A/(1

where we used (37). Equation ( 39) allows us to prove (38).

We now adapt the proof of [START_REF] Hu | Maximum-likelihood estimation under bound restriction and order and uniform bound restrictions[END_REF] to the case of unimodal regression. Proof [of Lemma 12] Since U S is a closed convex we just need to check that for all λ ∈ U S a∈{1,...,K} µ a -min( λ a , S) min( λ a , S) -λ a ω a 0 .

We have, using the same notation of Lemma 13, a∈{1,...,K}

where we used the Lemma 13 for the two first sums and the fact that λ a < S for the last sum.