ICLR17论文On Large-Batch Training for Deep Learning- Generalization Gap and Sharp Minima

D O D EEP C ONVOLUTIONAL N ETS R EALLY N EED TO BE D EEP AND C ONVOLUTIONAL?Gregor Urban1,Krzysztof J.Geras2,Samira Ebrahimi Kahou3,Ozlem Aslan4,Shengjie Wang5, Abdelrahman Mohamed6,Matthai Philipose6,Matt Richardson6,Rich Caruana61UC Irvine,USA2University of Edinburgh,UK3Ecole Polytechnique de Montreal,CA4University of Alberta,CA5University of Washington,USA6Microsoft Research,USAA BSTRACTYes,they do.This paper provides thefirst empirical demonstration that deepconvolutional models really need to be both deep and convolutional,even whentrained with methods such as distillation that allow small or shallow models ofhigh accuracy to be trained.Although previous research showed that shallowfeed-forward nets sometimes can learn the complex functions previously learnedby deep nets while using the same number of parameters as the deep models theymimic,in this paper we demonstrate that the same methods cannot be used to trainaccurate models on CIFAR-10unless the student models contain multiple layersof convolution.Although the student models do not have to be as deep as theteacher model they mimic,the students need multiple convolutional layers to learnfunctions of comparable accuracy as the deep convolutional teacher.1I NTRODUCTIONCybenko(1989)proved that a network with a large enough single hidden layer of sigmoid units can approximate any decision boundary.Empirical work,however,suggests that it can be difficult to train shallow nets to be as accurate as deep nets.Dauphin and Bengio(2013)trained shallow netson SIFT features to classify a large-scale ImageNet dataset and found that it was difficult to train large,high-accuracy,shallow nets.A study of deep convolutional nets suggests that for vision tasks deeper models are preferred under a parameter budget(e.g.Eigen et al.(2014);He et al.(2015); Simonyan and Zisserman(2014);Srivastava et al.(2015)).Similarly,Seide et al.(2011)and Geraset al.(2015)show that deeper models are more accurate than shallow models in speech acoustic modeling.More recently,Romero et al.(2015)showed that it is possible to gain increases in accuracyin models with few parameters by training deeper,thinner nets(FitNets)to mimic much wider nets. Cohen and Shashua(2016);Liang and Srikant(2016)suggest that the representational efficiency of deep networks scales exponentially with depth,but it is unclear if this applies only to pathological problems,or is encountered in practice on data sets such as TIMIT and CIFAR.Ba and Caruana(2014),however,demonstrated that shallow nets sometimes can learn the functions learned by deep nets,even when restricted to the same number of parameters as the deep nets.Theydid this byfirst training state-of-the-art deep models,and then training shallow models to mimicthe deep models.Surprisingly,and for reasons that are not well understood,the shallow models learned more accurate functions when trained to mimic the deep models than when trained on the original data used to train the deep models.In some cases shallow models trained this way were as accurate as state-of-the-art deep models.But this demonstration was made on the TIMIT speech recognition benchmark.Although their deep teacher models used a convolutional layer,convolutionis less important for TIMIT than it is for other domains such as image classification.Ba and Caruana(2014)also presented results on CIFAR-10which showed that a shallow model could learn functions almost as accurate as deep convolutional nets.Unfortunately,the results on CIFAR-10are less convincing than those for TIMIT.To train accurate shallow models on CIFAR-10they had to include at least one convolutional layer in the shallow model,and increased the number of parameters in the shallow model until it was30times larger than the deep teacher model.Despite this,the shallow convolutional student model was several points less accurate than a teacher model that was itself several points less accurate than state-of-the-art models on CIFAR-10.In this paper we show that the methods Ba and Caruana used to train shallow students to mimic deep teacher models on TIMIT do not work as well on problems such as CIFAR-10where multiple layers of convolution are required to train accurate teacher models.If the student models have a similar number of parameters as the deep teacher models,high accuracy can not be achieved without multiple layers of convolution even when the student models are trained via distillation.To ensure that the shallow student models are trained as accurately as possible,we use Bayesian optimization to thoroughly explore the space of architectures and learning hyperparameters.Although this combination of distillation and hyperparameter optimization allows us to train the most accurate shallow models ever trained on CIFAR-10,the shallow models still are not as accurate as deep models.Our results clearly suggest that deep convolutional nets do,in fact,need to be both deep and convolutional,even when trained to mimic very accurate models via distillation(Hinton et al.,2015). 2T RAINING S HALLOW N ETS TO M IMIC D EEPER C ONVOLUTIONAL N ETSIn this paper,we revisit the CIFAR-10experiments in Ba and Caruana(2014).Unlike in that work, here we compare shallow models to state-of-the-art deep convolutional models,and restrict the number of parameters in the shallow student models to be comparable to the number of parameters in the deep convolutional teacher models.Because we anticipated that our results might be different, we follow their approach closely to eliminate the possibility that the results differ merely because of changes in methodology.Note that the goal of this paper is not to train models that are small or fast as in Bucila et al.(2006),Hinton et al.(2015),and Romero et al.(2015),but to examine if shallow models can be as accurate as deep convolutional models given the same parameter budget.There are many steps required to train shallow student models to be as accurate as possible:train state-of-the-art deep convolutional teacher models,form an ensemble of the best deep models,collect and combine their predictions on a large transfer set,and then train carefully optimized shallow student models to mimic the teacher ensemble.For negative results to be informative,it is important that each of these steps be performed as well as possible.In this section we describe the experimental methodology in detail.Readers familiar with distillation(model compression),training deep models on CIFAR-10,data augmentation,and Bayesian hyperparameter optimization may wish to skip to the empirical results in Section3.2.1M ODEL C OMPRESSION AND D ISTILLATIONThe key idea behind model compression is to train a compact model to approximate the function learned by another larger,more complex model.Bucila et al.(2006)showed how a single neural net of modest size could be trained to mimic a much larger ensemble.Although the small neural nets contained1000×fewer parameters,often they were as accurate as the large ensembles they were trained to mimic.Model compression works by passing unlabeled data through the large,accurate teacher model to collect the real-valued scores it predicts,and then training a student model to mimic these scores. Hinton et al.(2015)generalized the methods of Bucila et al.(2006)and Ba and Caruana(2014) by incorporating a parameter to control the relative importance of the soft targets provided by the teacher model to the hard targets in the original training data,as well as a temperature parameter that regularizes learning by pushing targets towards the uniform distribution.Hinton et al.(2015)also demonstrated that much of the knowledge passed from the teacher to the student is conveyed as dark knowledge contained in the relative scores(probabilities)of outputs corresponding to other classes, as opposed to the scores given to just the output for the one correct class.Surprisingly,distillation often allows smaller and/or shallower models to be trained that are nearly as accurate as the larger,deeper models they are trained to mimic,yet these same small models are not as accurate when trained on the1-hot hard targets in the original training set.The reason for this is not yet well understood.Similar compression and distillation methods have also successfullybeen used in speech recognition (e.g.Chan et al.(2015);Geras et al.(2015);Li et al.(2014))and reinforcement learning Parisotto et al.(2016);Rusu et al.(2016).Romero et al.(2015)showed that distillation methods can be used to train small students that are more accurate than the teacher models by making the student models deeper,but thinner,than the teacher model.2.2M IMIC L EARNING VIA L2R EGRESSION ON L OGITSWe train shallow mimic nets using data labeled by an ensemble of deep teacher nets trained on the original 1-hot CIFAR-10training data.The deep teacher models are trained in the usual way using softmax outputs and cross-entropy cost function.Following Ba and Caruana (2014),the student mimic models are not trained with cross-entropy on the ten p values where p k =e z k / j e z j output by the softmax layer from the deep teacher model,but instead are trained on the un-normalized log probability values z (the logits)before the softmax activation.Training on the logarithms of predicted probabilities (logits)helps provide the dark knowledge that regularizes students by placing emphasis on the relationships learned by the teacher model across all of the outputs.As in Ba and Caruana (2014),the student is trained as a regression problem given training data {(x (1),z (1)),...,(x (T ),z (T ))}:L (W )=1T t ||g (x (t );W )−z (t )||22,(1)where W represents all of the weights in the network,and g (x (t );W )is the model prediction on the t th training data sample.2.3U SING A L INEAR B OTTLENECK TO S PEED U P T RAININGA shallow net has to have more hidden units in each layer to match the number of parameters in a deep net.Ba and Caruana (2014)found that training these wide,shallow mimic models with backpropagation was slow,and introduced a linear bottleneck layer between the input and non-linear layers to speed learning.The bottleneck layer speeds learning by reducing the number of parameters that must be learned,but does not make the model deeper because the linear terms can be absorbed back into the non-linear weight matrix after learning.See Ba and Caruana (2014)for details.To match their experiments we use linear bottlenecks when training student models with 0or 1convolutional layers,but did not find the linear bottlenecks necessary when training student models with more than 1convolutional layer.2.4B AYESIAN H YPERPARAMETER O PTIMIZATIONThe goal of this work is to determine empirically if shallow nets can be trained to be as accurate as deep convolutional models using a similar number of parameters in the deep and shallow models.If we succeed in training a shallow model to be as accurate as a deep convolutional model,this provides an existence proof that shallow models can represent and learn the complex functions learned by deep convolutional models.If,however,we are unable to train shallow models to be as accurate as deep convolutional nets,we might fail only because we did not train the shallow nets well enough.In all our experiments we employ Bayesian hyperparameter optimization using Gaussian process regression to ensure that we thoroughly and objectively explore the hyperparameters that govern learning.The implementation we use is Spearmint (Snoek et al.,2012).The hyperparameters we optimize with Bayesian optimization include the initial learning rate,momentum,scaling of the initial random weights,scaling of the inputs,and terms that determine the width of each of the network’s layers (i.e.number of convolutional filters and neurons).More details of the hyperparameter optimization can be found in Sections 2.5,2.7,2.8and in the Appendix.2.5T RAINING D ATA AND D ATA A UGMENTATIONThe CIFAR-10(Krizhevsky,2009)data set consists of a set of natural images from 10different object classes:airplane,automobile,bird,cat,deer,dog,frog,horse,ship,truck.The dataset is a labeled subset of the 80million tiny images dataset (Torralba et al.,2008)and is divided into 50,000train and10,000test images.Each image is32×32pixels in3color channels,yielding input vectors with3072 dimensions.We prepared the data by subtracting the mean and dividing by the standard deviation of each image vector.We train all models on a subset of40,000images and use the remaining 10,000images as the validation set for the Bayesian optimization.Thefinal trained models only used80%of the theoretically available training data(as opposed to retraining on all of the data after hyperparameter optimization).We employ the HSV-data augmentation technique as described by Snoek et al.(2015).Thus we shift hue,saturation and value by uniform random values:∆h∼U(−D h,D h),∆s∼U(−D s,D s),∆v∼U(−D v,D v).Saturation and value values are scaled globally:a s∼U(11+A s ,1+A s),a v∼U(11+A v,1+A v).Thefive constants D h,D s,D v,A s,A v are treatedas additional hyperparameters in the Bayesian hyperparameter optimization.All training images are mirrored left-right randomly with a probability of0.5.The input images are further scaled and jittered randomly by cropping windows of size24×24up to32×32at random locations and then scaling them back to32×32.The procedure is as follows:we sample an integer value S∼U(24,32)and then a pair of integers x,y∼U(0,32−S).The transformed resulting image is R=f spline,3(I[x:x+S,y:y+S])with I denoting the original image and f spline,3 denoting the3rd order spline interpolation function that maps the2D array back to32×32(applied to the three color channels separately).All data augmentations for the teacher models are computed on thefly using different random seeds. For student models trained to mimic the ensemble(see Section2.7for details of the ensemble teacher model),we pre-generated160epochs worth of randomly augmented training data,evaluated the ensemble’s predictions(logits)on these samples,and saved all data and predictions to disk.All student models thus see the same training data in the same order.The parameters for HSV-augmentation in this case had to be selected beforehand;we chose to use the settings found with the best single model (D h=0.06,D s=0.26,D v=0.20,A s=0.21,A v=0.13).Pre-saving the logits and augmented data is important to reduce the computational cost at training time,and to ensure that all student models see the same training dataBecause augmentation allows us to generate large training sets from the original50,000images,we use augmented data as the transfer set for model compression.No extra unlabeled data is required.2.6L EARNING-R ATE S CHEDULEWe train all models using SGD with Nesterov momentum.The initial learning rate and momentum are chosen by Bayesian optimization.The learning rate is reduced according to the evolution of the model’s validation error:it is halved if the validation error does not drop for ten epochs in a row.It is not reduced within the next eight epochs following a reduction step.Training ends if the error did not drop for30epochs in a row or if the learning rate was reduced by a factor of more than2000in total. This schedule provides a way to train the highly varying models in a fair manner(it is not feasible to optimize all of the parameters that define the learning schedule).It also decreases the time spent to train each model compared to using a hand-selected overestimate of the number of epochs to train, thus allowing us to train more models in the hyperparameter search.2.7S UPER T EACHER:A N E NSEMBLE OF16D EEP C ONVOLUTIONAL CIFAR-10M ODELS One limitation of the CIFAR-10experiments performed in Ba and Caruana(2014)is that the teacher models were not state-of-the-art.The best deep models they trained on CIFAR-10had only88% accuracy,and the ensemble of deep models they used as a teacher had only89%accuracy.The accuracies were not state-of-the-art because they did not use augmentation and because their deepest models had only three convolutional layers.Because our goal is to determine if shallow models can be as accurate as deep convolutional models,it is important that the deep models we compare to(and use as teachers)are as accurate as possible.We train deep neural networks with eight convolutional layers,three intermittent max-pooling layers and two fully-connected hidden layers.We include the size of these layers in the hyperparameter optimization,by allowing thefirst two convolutional layers to contain from32to96filters each,the next two layers to contain from64to192filters,and the last four convolutional layers to containfrom128to384filters.The two fully-connected hidden layers can contain from512to1536neurons. We parametrize these model-sizes by four scalars(the layers are grouped as2-2-4)and include the scalars in the hyperparameter optimization.All models are trained using Theano(Bastien et al.,2012; Bergstra et al.,2010).We optimize eighteen hyperparameters overall:initial learning rate on[0.01,0.05],momentum on [0.80,0.91],l2weight decay on[5·10−5,4·10−4],initialization coefficient on[0.8,1.35]which scales the initial weights of the CNN,four separate dropout rates,five constants controlling the HSV data augmentation,and the four scaling constants controlling the networks’layer widths.The learning rate and momentum are optimized on a log-scale(as opposed to linear scale)by optimizing the exponent with appropriate bounds,e.g.LR=e−x optimized over x on[3.0,4.6].See the Appendix for more details about hyperparameter optimization.We trained129deep CNN models with Spearmint.The best model obtained an accuracy of92.78%; thefifth best achieved92.67%.See Table1for the sizes and architectures of the three best models. We are able to construct a more accurate model on CIFAR-10by forming an ensemble of multiple deep convolutional neural nets,each trained with different hyperparameters,and each seeing slightly different training data(as the augmentation parameters vary).We experimented with a number of ensembles of the many deep convnets we trained,using accuracy on the validation set to select the best combination.Thefinal ensemble contained16deep convnets and had an accuracy of94.0%on the validation set,and93.8%on thefinal test set.We believe this is among the top published results for deep learning on CIFAR-10.The ensemble averages the logits predicted by each model before the softmax layers.We used this very accurate ensemble model as the teacher model to label the data used to train the shallower student nets.As described in Section2.2,the logits(the scores just prior to thefinal softmax layer)from each of the CNN teachers in the ensemble model are averaged for each class,and the average logits are used asfinal regression targets to train the shallower student neural nets.2.8T RAINING S HALLOW S TUDENT M ODELS TO M IMIC AN E NSEMBLE OF D EEPC ONVOLUTIONAL M ODELSWe trained student mimic nets with1,3.161,10and31.6million trainable parameters on the pre-computed augmented training data(Section2.5)that was re-labeled by the teacher ensemble (Section2.7).For each of the four student sizes we trained shallow fully-connected student MLPs containing1,2,3,4,or5layers of non-linear units(ReLU),and student CNNs with1,2,3or4 convolutional layers.The convolutional student models also contain one fully-connected ReLU layer. Models with zero or only one convolutional layer contain an additional linear bottleneck layer to speed up learning(cf.Section2.3).We did not need to use a bottleneck to speed up learning for the deeper models as the number of learnable parameters is naturally reduced by the max-pooling layers. The student CNNs use max-pooling and Bayesian optimization controls the number of convolutional filters and hidden units in each layer.The hyperparameters we optimized in the student models are: initial learning rate,momentum,scaling of the initially randomly distributed learnable parameters, scaling of all pixel values of the input,and the scale factors that control the width of all hidden and convolutional layers in the model.Weights are initialized as in Glorot and Bengio(2010).We intentionally do not optimize and do not make use of weight decay and dropout when training student models because preliminary experiments showed that these consistently reduced the accuracy of student models by several percent.Please refer to the Appendix for more details on the individual architectures and hyperparameter ranges.3E MPIRICAL R ESULTSTable1summarizes results after Bayesian hyperparameter optimization for models trained on the original0/1hard CIFAR-10labels.All of these models use weight decay and are trained with the dropout hyperparameters included in the Bayesian optimization.The table shows the accuracy of the best three deep convolutional models we could train on CIFAR-10,as well as the accuracy of13.16≈Sqrt(10)falls halfway between1and10on log scale.Table1:Accuracy on CIFAR-10of shallow and deep models trained on the original0/1hard class labels using Bayesian optimization with dropout and weight decay.Key:c=convolution layer;mp =max-pooling layer;fc=fully-connected layer;lfc=linear bottleneck layer;exponents indicate repetitions of a layer.The last two models(*)are numbers reported by Ba and Caruana(2014).The models with1-4convolutional layers at the top of the table are included for comparison with student models of similar architecture in Table2.All of the student models in Table2with1,2,3,and4 convolutional layers are more accurate than their counterparts in this table that are trained on the original0/1hard targets—as expected distillation yields shallow models of higher accuracy than shallow models trained on the original training data.Model Architecture#parameters Accuracyyer c-mp-lfc-fc10M84.6%yer c-mp-c-mp-fc10M88.9%yer c-mp-c-mp-c-mp-fc10M91.2%yer c-mp-c-c-mp-c-mp-fc10M91.75% Teacher CNN1st76c2-mp-126c2-mp-148c4-mp-1200fc2 5.3M92.78% Teacher CNN2nd96c2-mp-171c2-mp-128c4-mp-512fc2 2.5M92.77% Teacher CNN3rd54c2-mp-158c2-mp-189c4-mp-1044fc2 5.8M92.67% Ensemble of16CNNs c2-mp-c2-mp-c4-mp-fc283.4M93.8% Teacher CNN(*)128c-mp-128c-mp-128c-mp-1k fc 2.1M88.0% Ensemble,4CNNs(*)128c-mp-128c-mp-128c-mp-1k fc8.6M89.0%Table2:Comparison of student models with varying number of convolutional layers trained to mimic the ensemble of16deep convolutional CIFAR-10models in Table1.The best performing student models have3–4convolutional layers and10M–31.6M parameters.The student models in this table are more accurate than the models of the same architecture in Table1that were trained on the original0/1hard targets—shallow models trained with distillation are more accurate than shallow models trained on0/1hard targets.The student model trained by Ba and Caruana(2014)is shown in the last line for comparison;it is less accurate and much larger than the student models trained here that also have1convolutional layer.1M 3.16M10M31.6M70M Bottleneck,1hidden layer65.8%68.2%69.5%70.2%–2hidden layers66.2%70.9%73.4%74.3%–3hidden layers66.8%71.0%73.0%73.9%–4hidden layers66.7%69.5%71.6%72.0%–5hidden layers66.4%70.0%71.4%71.5%–yer,1max-pool,Bottleneck84.5%86.3%87.3%87.7%–yers,2max-pool87.9%89.3%90.0%90.3%–yers,3max-pool90.7%91.6%91.9%92.3%–yers,3max-pool91.3%91.8%92.6%92.6%–SNN-ECNN-MIMIC-30k128c-p-1200L-30k––––85.8%trained on ensemble(Ba and Caruana,2014)Figure 1:Accuracy of student models with differ-ent architectures trained to mimic the CIFAR10ensemble.The average performance of the five best models of each hyperparameter-optimization experiment is shown,together with dashed lines indicating the accuracy of the best and the fifth best model from each setting.The short horizontal lines at 10M parameters are the accuracy of mod-els trained without compression on the original 0/1hard targets.layers.Also,it is clear that there is a huge gapbetween the convolutional student models at thetop of the figure,and the non-convolutional stu-dent models at the bottom of the figure:the mostaccurate student MLP has accuracy less than75%,while the least accurate convolutional stu-dent model with the same number of parametersbut only one convolutional layer has accuracyabove 87%.And the accuracy of the convolu-tional student models increases further as morelayers of convolution are added.Interestingly,the most accurate student MLPs with no convo-lutional layers have only 2or 3hidden layers;the student MLPs with 4or 5hidden layers arenot as paring the student MLP with only one hidden layer (bottom of the graph)to the student CNN with 1convolutional layer clearly suggests that convolution is critical for this problem even when models are trained via distillation,and that it is very unlikely that a shallow non-convolutional model with 100million parameters or less could ever achieve accuracy comparable to a convolutional model.It appears that if convolution is critical for teacher models trained on the original 0/1hard targets,itis likely to be critical for student models trained to mimic these teacher models.Adding depth to the student MLPs without adding convolution does not significantly close this“convolutional gap”. Furthermore,comparing student CNNs with1,2,3,and4convolutional layers,it is clear that CNN students benefit from multiple convolutional layers.Although the students do not need as many layers as teacher models trained on the original0/1hard targets,accuracy increases significantly as multiple convolutional layers are added to the model.For example,the best student with only one convolutional layer has87.7%accuracy,while the student with the same number of parameters(31M) and4convolutional layers has92.6%accuracy.Figure1includes short horizontal lines at10M parameters indicating the accuracy of non-student models trained on the original0/1hard targets instead of on the soft targets.This“compression gap”is largest for shallower models,and as expected disappears as the student models become architecturally more similar to the teacher models with multiple layers of convolution.The benefits of distillation are most significant for shallow models,yielding an increase in accuracy of3%or more. One pattern that is clear in the graph is that all student models benefit when the number of parameters increases from1million to31million parameters.It is interesting to note,however,that the largest student(31M)with a one convolutional layer is less accurate than the smallest student(1M)with two convolutional layers,further demonstrating the value of depth in convolutional models.In summary,depth-constrained student models trained to mimic a high-accuracy ensemble of deep convolutional models perform better than similar models trained on the original hard targets(the “compression”gaps in Figure1),student models need at least3-4convolutional layers to have high accuracy on CIFAR-10,shallow students with no convolutional layers perform poorly on CIFAR-10, and student models need at least3-10M parameters to perform well.We are not able to compress deep convolutional models to shallow student models without significant loss of accuracy.We are currently running a reduced set of experiments on ImageNet,though the chances of shallow models performing well on a more challenging problem such as ImageNet appear to be slim.4D ISCUSSIONAlthough we are not able to train shallow models to be as accurate as deep models,the models trained via distillation are the most accurate models of their architecture ever trained on CIFAR-10.For example,the best single-layer fully-connected MLP(no convolution)we trained achieved an accuracy of70.2%.We believe this to be the most accurate shallow MLP ever reported for CIFAR-10(in comparison to63.1%achieved by Le et al.(2013),63.9%by Memisevic et al.(2015)and64.3%by Geras and Sutton(2015)).Although this model cannot compete with convolutional models,clearly distillation helps when training models that are limited by architecture and/or number of parameters. Similarly,the student models we trained with1,2,3,and4convolutional layers are,we believe, the most accurate convnets of those depths reported in the literature.For example,the ensemble teacher model in Ba and Caruana(2014)was an ensemble of four CNNs,each of which had3 convolutional layers,but only achieved89%accuracy,whereas the single student CNNs we train via distillation achieve accuracies above90%with only2convolutional layers,and above92%with3 convolutional layers.The only other work we are aware of that achieves comparable high accuracy with non-convolutional MLPs is recent work by Lin et al.(2016).They train multi-layer Z-Lin networks,and use a powerful form of data augmentation based on deformations that we did not use. Interestingly,we noticed that mimic networks perform consistently worse when trained using dropout. This surprised us,and suggests that training student models on the soft-targets from a teacher provides significant regularization for the student models obviating the need for extra regularization methods such as dropout.This is consistent with the observation made by Ba and Caruana(2014)that student mimic models did not seem to overfit.Hinton et al.(2015)claim that soft targets convey more information per sample than Boolean hard targets.The also suggest that the dark knowledge in the soft targets for other classes further helped regularization,and that early stopping was unnecessary. Romero et al.(2015)extend distillation by using the intermediate representations learned by the teacher as hints to guide training deep students,and teacher confidences further help regularization by providing a measure of sample simplicity to the student,akin to curriculum learning.In other work,Pereyra et al.(2017)suggest that the soft targets provided by a teacher provide a form of confidence penalty that penalizes low entropy distributions and label smoothing,both of which improve regularization by maintaining a reasonable ratio between the logits of incorrect classes.。

论⽂笔记：CNN经典结构2（WideResNet，FractalNet，DenseNet，。

前⾔在中主要讲了2012-2015年的⼀些经典CNN结构。

本⽂主要讲解2016-2017年的⼀些经典CNN结构。

CIFAR和SVHN上，DenseNet-BC优于ResNeXt优于DenseNet优于WRN优于FractalNet优于ResNetv2优于ResNet，具体数据见。

ImageNet上，SENet优于DPN优于ResNeXt优于WRN优于ResNet和DenseNet。

WideResNet( WRN )1. motivation：ResNet的跳连接，导致了只有少量的残差块学到了有⽤信息，或者⼤部分残差块只能提供少量的信息。

于是作者探索⼀种新的⽹络WideResNet（在ResNet的基础上减⼩深度，增加宽度）。

2. ⽹络结构：在ResNetv2的基础上改进，增⼤每个残差块中的卷积核数量。

如下两个图所⽰。

其中B(3,3)表⽰⼀个两个3x3卷积，k表⽰⼀个宽度因⼦，当k为1时卷积核个数和ResNetv2相等，k越⼤⽹络越宽。

另外WRN在卷积层之间加⼊dropout（下⼀个卷积层之前的bn和relu之后），如下第⼀个图的图(d)所⽰（在ResNetv2中把dropout放在恒等映射中实验发现效果不好于是放弃了dropout）。

⽤WRN-n-k来表⽰⼀个⽹络，n表⽰卷积层的总数，k表⽰宽度因⼦。

3. 训练配置：SGD，momentum为0.9，学习率为0.1，权重衰减为0.0005，batch size为128。

4. 实验：在CIFAR，SVHN，COCO数据集上取得了state-of-the-art的结果，同时在ImageNet上也表现优秀（⽐某些ResNet表现好，并没有超越ResNet的最优结果）。

作者根据实验结果认为ResNet的主要能⼒来⾃于残差块，⽽深度的效果只是⼀个补充。

FractalNet1. motivation：WideResNet通过加宽ResNet得到state-of-the-art的表现，推测ResNet的主要能⼒来⾃于残差块，深度不是必要的。

Under review as a conference paper at ICLR 2017
D ESIGNING N EURAL N ETWORK A RCHITECTURES USING R EINFORCEMENT L EARNING
Bowen Baker, Otkrist Gupta, Nikhil Naik & Ramesh Raskar Media Laboratory Massachusetts Institute of Technology Cambridge MA 02139, USA {bowen, otkrist, naik, raskar}@
1
I NTRODUCTION
Deep convolutional neural networks (CNNs) have seen great success in the past few years on a variety of machine learning problems (LeCun et al., 2015). A typical CNN architecture consists of several convolution, pooling, and fully connected layers. While constructing a CNN, a network designer has to make numerous design choices: the number of layers of each type, the ordering of layers, and the design parameters for each type of layer, e.g., the receptive field size, stride, and number of receptive fields for a convolution layer. The number of possible choices makes the design space of CNN architectures extremely large and hence, infeasible for an exhaustive manual search. While there has been some work (Pinto et al., 2009; Bergstra et al., 2013; Domhan et al., 2015) on automated or computer-aided neural network design, new CNN architectures or network design elements are still primarily developed by researchers using new theoretical insights or intuition gained from experimentation. In this paper, we seek to automate the process of CNN architecture selection through a metamodeling procedure based on reinforcement learning. We construct a novel Q-learning agent whose goal is to discover CNN architectures that performs well on a given machine learning task with no human intervention. The learning agent is given the task of sequentially picking layers of a CNN model. By discretizing and limiting the layer parameters to choose from, the agent is left with a finite but large space of model architectures to search from. The agent learns through random exploration and slowly begins to exploit its findings to select higher performing models using the greedy strategy (Mnih et al., 2015). The agent receives the validation accuracy on the given machine learning task as the reward for selecting an architecture. We expedite the learning process through repeated memory sampling using experience replay (Lin, 1993). We refer to this Q-learning based meta-modeling method as MetaQNN, which is summarized in Figure 1. We conduct experiments with a space of model architectures consisting of only standard convolution, pooling, and fully connected layers using three standard image classification datasets: CIFAR-10, SVHN, and MNIST. The learning agent discovers CNN architectures that beat all existing networks 1

Large-Scale Machine Learningwith Stochastic Gradient DescentL´e on BottouNEC Labs America,Princeton NJ08542,USAleon@Abstract.During the last decade,the data sizes have grown faster than the speed of processors.In this context,the capabilities of statistical machine learning meth-ods is limited by the computing time rather than the sample size.A more pre-cise analysis uncovers qualitatively different tradeoffs for the case of small-scale and large-scale learning problems.The large-scale case involves the computational complexity of the underlying optimization algorithm in non-trivial ways.Unlikely optimization algorithms such as stochastic gradient descent show amazing perfor-mance for large-scale problems.In particular,second order stochastic gradient and averaged stochastic gradient are asymptotically efficient after a single pass on the training set.Keywords:Stochastic gradient descent,Online learning,Efficiency1IntroductionThe computational complexity of learning algorithm becomes the critical limiting factor when one envisions very large datasets.This contribution ad-vocates stochastic gradient algorithms for large scale machine learning prob-lems.Thefirst section describes the stochastic gradient algorithm.The sec-ond section presents an analysis that explains why stochastic gradient algo-rithms are attractive when the data is abundant.The third section discusses the asymptotical efficiency of estimates obtained after a single pass over the training set.The last section presents empirical evidence.2Learning with gradient descentLet usfirst consider a simple supervised learning setup.Each example z is a pair(x,y)composed of an arbitrary input x and a scalar output y.We consider a loss function (ˆy,y)that measures the cost of predictingˆy when the actual answer is y,and we choose a family F of functions f w(x)parametrized by a weight vector w.We seek the function f∈F that minimizes the loss Q(z,w)= (f w(x),y)averaged on the examples.Although we would like to average over the unknown distribution dP(z)that embodies the Laws of2L´e on BottouNature,we must often settle for computing the average on a sample z1...z n.E(f)=(f(x),y)dP(z)E n(f)=1nni=1(f(x i),y i)(1)The empirical risk E n(f)measures the training set performance.The expected risk E(f)measures the generalization performance,that is,the expected performance on future examples.The statistical learning theory(Vapnik and Chervonenkis,1971)justifies minimizing the empirical risk instead of the expected risk when the chosen family F is sufficiently restrictive.2.1Gradient descentIt has often been proposed(e.g.,Rumelhart et al.,1986)to minimize the empirical risk E n(f w)using gradient descent(GD).Each iteration updates the weights w on the basis of the gradient of E n(f w),w t+1=w t−γ1nni=1∇w Q(z i,w t),(2)whereγis an adequately chosen gain.Under sufficient regularity assumptions, when the initial estimate w0is close enough to the optimum,and when the gainγis sufficiently small,this algorithm achieves linear convergence(Dennis and Schnabel,1983),that is,−logρ∼t,whereρrepresents the residual error.Much better optimization algorithms can be designed by replacing the scalar gainγby a positive definite matrixΓt that approaches the inverse of the Hessian of the cost at the optimum:w t+1=w t−Γt 1nni=1∇w Q(z i,w t).(3)This second order gradient descent(2GD)is a variant of the well known Newton algorithm.Under sufficiently optimistic regularity assumptions,and provided that w0is sufficiently close to the optimum,second order gradient descent achieves quadratic convergence.When the cost is quadratic and the scaling matrixΓis exact,the algorithm reaches the optimum after a single iteration.Otherwise,assuming sufficient smoothness,we have−log logρ∼t.2.2Stochastic gradient descentThe stochastic gradient descent(SGD)algorithm is a drastic simplification. Instead of computing the gradient of E n(f w)exactly,each iteration estimates this gradient on the basis of a single randomly picked example z t:w t+1=w t−γt∇w Q(z t,w t).(4)Large-Scale Machine Learning 3The stochastic process {w t ,t =1,...}depends on the examples randomly picked at each iteration.It is hoped that (4)behaves like its expectation (2)despite the noise introduced by this simplified procedure.Since the stochastic algorithm does not need to remember which examples were visited during the previous iterations,it can process examples on the fly in a deployed system.In such a situation,the stochastic gradient descent directly optimizes the expected risk,since the examples are randomly drawn from the ground truth distribution.The convergence of stochastic gradient descent has been studied exten-sively in the stochastic approximation literature.Convergence results usuallyrequire decreasing gains satisfying the conditions t γ2t <∞and t γt =∞.The Robbins-Siegmund theorem (Robbins and Siegmund,1971)provides the means to establish almost sure convergence under mild conditions (Bottou,1998),including cases where the loss function is not everywhere differentiable.The convergence speed of stochastic gradient descent is in fact limited by the noisy approximation of the true gradient.When the gains decrease too slowly,the variance of the parameter estimate w t decreases equally slowly.When the gains decrease too quickly,the expectation of the parameter es-timate w t takes a very long time to approach the optimum.Under suffi-cient regularity conditions (e.g.Murata,1998),the best convergence speed is achieved using gains γt ∼t −1.The expectation of the residual error then decreases with similar speed,that is,E ρ∼t −1.The second order stochastic gradient descent (2SGD)multiplies the gradi-ents by a positive definite matrix Γt approaching the inverse of the Hessian :w t +1=w t −γt Γt ∇w Q (z t ,w t ).(5)Unfortunately,this modification does not reduce the stochastic noise and therefore does not significantly improve the variance of w t .Although con-stants are improved,the expectation of the residual error still decreases like t −1,that is,E ρ∼t −1,(e.g.Bordes et al.,2009,appendix).2.3Stochastic gradient examplesTable 1illustrates stochastic gradient descent algorithms for a number of classic machine learning schemes.The stochastic gradient descent for the Perceptron,for the Adaline,and for k -Means match the algorithms proposed in the original papers.The SVM and the Lasso were first described with traditional optimization techniques.Both Q svm and Q lasso include a regular-ization term controlled by the hyperparameter λ.The K-means algorithm converges to a local minimum because Q kmeans is nonconvex.On the other hand,the proposed update rule uses second order gains that ensure a fast convergence.The proposed Lasso algorithm represents each weight as the difference of two positive variables.Applying the stochastic gradient rule to these variables and enforcing their positivity leads to sparser solutions.4L´e on BottouTable 1.Stochastic gradient algorithms for various learning systems.Loss Stochastic gradient algorithmAdaline (Widrow and Hoff,1960)Q adaline =12 y −w Φ(x ) 2Φ(x )∈R d ,y =±1w ←w +γt y t −w Φ(x t ) Φ(x t )Perceptron (Rosenblatt,1957)Q perceptron =max {0,−y w Φ(x )}Φ(x )∈R d ,y =±1w ←w +γt y t Φ(x t )if y t w Φ(x t )≤00otherwise K-Means (MacQueen,1967)Q kmeans =min k 1(z −w k )2z ∈R d ,w 1...w k ∈R dn 1...n k ∈N ,initially 0k ∗=arg min k (z t −w k )2n k ∗←n k ∗+1w k ∗←w k ∗+1n k∗(z t −w k ∗)SVM (Cortes and Vapnik,1995)Q svm =λw 2+max {0,1−y w Φ(x )}Φ(x )∈R d ,y =±1,λ>0w ←w −γt λw if y t w Φ(x t )>1,λw −y t Φ(x t )sso (Tibshirani,1996)Q lasso =λ|w |1+12 y −w Φ(x ) 2w =(u 1−v 1,...,u d −v d )Φ(x )∈R d ,y ∈R ,λ>0u i ← u i −γt λ−(y t −w Φ(x t ))Φi (x t ) +v i ← v i −γt λ+(y t −w t Φ(x t ))Φi (x t ) +with notation [x ]+=max {0,x }.3Learning with large training setsLet f ∗=arg min f E (f )be the best possible prediction function.Since we seek the prediction function from a parametrized family of functions F ,let f ∗F =arg min f ∈F E (f )be the best function in this family.Since we optimize the empirical risk instead of the expected risk,let f n =arg min f ∈F E n (f )be the empirical optimum.Since this optimization can be costly,let us stop the algorithm when it reaches an solution ˜f n that minimizes the objective function with a predefined accuracy E n (˜f n )<E n (f n )+ρ.3.1The tradeoffs of large scale learningThe excess error E =E E (˜f n)−E (f ∗) can be decomposed in three terms (Bottou and Bousquet,2008):E =E E (f ∗F )−E (f ∗) +E E (f n )−E (f ∗F ) +E E (˜f n )−E (f n ) .(6)•The approximation error E app =E E (f ∗F )−E (f ∗) measures how closelyfunctions in F can approximate the optimal solution f ∗.The approxima-tion error can be reduced by choosing a larger family of functions.•The estimation error E est =E E (f n )−E (f ∗F ) measures the effect of minimizing the empirical risk E n (f )instead of the expected risk E (f ).Large-Scale Machine Learning 5The estimation error can be reduced by choosing a smaller family of functions or by increasing the size of the training set.•The optimization error E opt =E (˜f n )−E (f n )measures the impact of the approximate optimization on the expected risk.The optimization error can be reduced by running the optimizer longer.The additional computing time depends of course on the family of function and on the size of the training set.Given constraints on the maximal computation time T max and the maximal training set size n max ,this decomposition outlines a tradeoffinvolving the size of the family of functions F ,the optimization accuracy ρ,and the number of examples n effectively processed by the optimization algorithm.min F ,ρ,nE =E app +E est +E opt subject to n ≤n max T (F ,ρ,n )≤T max (7)Two cases should be distinguished:•Small-scale learning problems are first constrained by the maximal num-ber of examples.Since the computing time is not an issue,we can reduce the optimization error E opt to insignificant levels by choosing ρarbitrarily small,and we can minimize the estimation error by chosing n =n max .We then recover the approximation-estimation tradeoffthat has been widely studied in statistics and in learning theory.•Large-scale learning problems are first constrained by the maximal com-puting time.Approximate optimization can achieve better expected risk because more training examples can be processed during the allowed time.The specifics depend on the computational properties of the chosen op-timization algorithm.3.2Asymptotic analysisSolving (7)in the asymptotic regime amounts to ensuring that the terms of the decomposition (6)decrease at similar rates.Since the asymptotic conver-gence rate of the excess error (6)is the convergence rate of its slowest term,the computational effort required to make a term decrease faster would be wasted.For simplicity,we assume in this section that the Vapnik-Chervonenkis dimensions of the families of functions F are bounded by a common constant.We also assume that the optimization algorithms satisfy all the assumptions required to achieve the convergence rates discussed in section 2.Similar anal-yses can be carried out for specific algorithms under weaker assumptions (e.g.Shalev-Shwartz and Srebro,2008).A simple application of the uniform convergence results of (Vapnik and Chervonenkis,1971)gives then the upper bound E =E app +E est +E opt =E app +O log n n+ρ .6L´e on BottouTable 2.Asymptotic equivalents for various optimization algorithms:gradient descent(GD,eq.2),second order gradient descent(2GD,eq.3),stochastic gradient descent(SGD,eq.4),and second order stochastic gradient descent(2SGD,eq.5). Although they are the worst optimization algorithms,SGD and2SGD achieve the fastest convergence speed on the expected risk.They differ only by constant factors not shown in this table,such as condition numbers and weight vector dimension.GD2GD SGD2SGD Time per iteration:n n11Iterations to accuracyρ:log1ρlog log1ρ1ρ1ρTime to accuracyρ:n log1ρn log log1ρ1ρ1ρTime to excess error E:1E1/αlog21E1E1/αlog1Elog log1E1E1EUnfortunately the convergence rate of this bound is too pessimistic.Faster convergence occurs when the loss function has strong convexity properties (Lee et al.,2006)or when the data distribution satisfies certain assumptions (Tsybakov,2004).The equivalenceE=E app+E est+E opt∼E app+log nnα+ρ,for someα∈1,1,(8)provides a more realistic view of the asymptotic behavior of the excess er-ror(e.g.Massart,2000,Bousquet,2002).Since the three component of the excess error should decrease at the same rate,the solution of the tradeoffproblem(7)must then obey the multiple asymptotic equivalencesE∼E app∼E est∼E opt∼log nnα∼ρ.(9)Table2summarizes the asymptotic behavior of the four gradient algo-rithm described in section2.Thefirst three rows list the computational cost of each iteration,the number of iterations required to reach an optimization accuracyρ,and the corresponding computational cost.The last row provides a more interesting measure for large scale machine learning purposes.Assum-ing we operate at the optimum of the approximation-estimation-optimization tradeoff(7),this line indicates the computational cost necessary to reach a predefined value of the excess error,and therefore of the expected risk.This is computed by applying the equivalences(9)to eliminate n andρfrom the third row results.Although the stochastic gradient algorithms,SGD and2SGD,are clearly the worst optimization algorithms(third row),they need less time than the other algorithms to reach a predefined expected risk(fourth row).Therefore, in the large scale setup,that is,when the limiting factor is the computing time rather than the number of examples,the stochastic learning algorithms performs asymptotically better!Large-Scale Machine Learning 74Efficient learningLet us add an additional example z t to a training set z 1...z t −1.Since the new empirical risk E t (f )remains close to E t −1(f ),the empirical minimum w ∗t +1=arg min w E t (f w )remains close to w ∗t =arg min w E t −1(f w ).With sufficient regularity assumptions,a first order calculation gives the resultw ∗t +1=w ∗t −t −1Ψt ∇w Q (z t ,w ∗t )+O t −2 ,(10)where Ψt is the inverse of the Hessian of E t (f w )in w ∗t .The similarity be-tween this expression and the second order stochastic gradient descent rule(5)has deep consequences.Let w t be the sequence of weights obtained by performing a single second order stochastic gradient pass on the randomly shuffled training set.With adequate regularity and convexity assumptions,we can prove (e.g.Bottou and LeCun,2004)lim t →∞t E (f w t )−E (f ∗F ) =lim t →∞t E (f w ∗t )−E (f ∗F ) =I >0.(11)Therefore,a single pass of second order stochastic gradient provides a pre-diction function f w t that approaches the optimum f ∗Fas efficiently as the empirical optimum f w ∗t .In particular,when the loss function is the log like-lihood,the empirical optimum is the asymptotically efficient maximum like-lihood estimate,and the second order stochastic gradient estimate is also asymptotically efficient.Unfortunately,second order stochastic gradient descent is computation-ally costly because each iteration (5)performs a computation that involves the large dense matrix Γt .Two approaches can work around this problem.•Computationally efficient approximations of the inverse Hessian trade asymptotic optimality for computation speed.For instance,the SGDQN algorithm (Bordes et al.,2009)achieves interesting speeds using a diag-onal approximation.•The averaged stochastic gradient descent (ASGD)algorithm (Polyak and Juditsky,1992)performs the normal stochastic gradient update (4)and recursively computes the average ¯w t =1tt i =1w t :w t +1=w t −γt ∇w Q (z t ,w t ),¯w t +1=t t +1¯w t +1t +1w t +1.(12)When the gains γt decrease slower than t −1,the ¯w t converges with the optimal asymptotic speed (11).Reaching this asymptotic regime can take a very long time in practice.A smart selection of the gains γt helps achieving the promised performance (Xu,2010).8L´e on BottouAlgorithm Time Test ErrorHinge loss SVM,λ=10−4.SVMLight 23,642s. 6.02%SVMPerf 66s. 6.03%SGD 1.4s. 6.02%Log loss SVM,λ=10−5.TRON (-e0.01)30s. 5.68%TRON (-e0.001)44s. 5.70%SGD 2.3s. 5.66%Optimization accuracy (trainingCost−optimalTrainingCost)Fig.1.Results achieved with a linear SVM on the RCV1task.The lower half of the plot shows the time required by SGD and TRON to reach a predefined accuracy ρon the log loss task.The upper half shows that the expected risk stops improving long before the superlinear TRON algorithm overcomes SGD.0.300.320.340.360.380.400 1 2 34 5E x p e c t e d r i s k Number of epochs SGD SGDQN ASGD 21.022.023.024.025.026.027.0 0 1 2 3 4 5T e s t E r r o r (%)Number of epochsSGD SGDQN ASGD paraison of the test set performance of SGD,SGDQN,and ASGD for a linear squared hinge SVM trained on the ALPHA task of the 2008Pascal Large Scale Learning Challenge.ASGD nearly reaches the optimal expected risk after a single pass.44004500460047004800490050005100520053005400epochs epochsparison of the test set performance of SGD,SGDQN,and ASGD on a CRF trained on the CONLL Chunking task.On this task,SGDQN appears more attractive because ASGD does not reach its asymptotic performance.Large-Scale Machine Learning9 5ExperimentsThis section briefly reports experimental results illustrating the actual per-formance of stochastic gradient algorithms on a variety of linear systems. We use gainsγt=γ0(1+λγ0t)−1for SGD and,following(Xu,2010),γt=γ0(1+λγ0t)−0.75for ASGD.The initial gainsγ0were set manually by observing the performance of each algorithm running on a subset of the training examples.Figure1reports results achieved using SGD for a linear SVM trained for the recognition of the CCAT category in the RCV1dataset(Lewis et al.,2004)using both the hinge loss(Q svm in table1),and the log loss, (Q logsvm=λw2+log(1+exp(−y w Φ(x)))).The training set contains781,265 documents represented by47,152relatively sparse TF/IDF features.SGD runs considerably faster than either the standard SVM solvers SVMLight and SVMPerf(Joachims,2006)or the superlinear optimization algorithm TRON(Lin et al.,2007).Figure2reports results achieved using SGD,SGDQN,and ASGD for a linear SVM trained on the ALPHA task of the2008Pascal Large Scale Learning Challenge(see Bordes et al.,2009)using the squared hinge loss (Q sqsvm=λw2+max{0,1−y w Φ(x)}2).The training set contains100,000 patterns represented by500centered and normalized variables.Performances measured on a separate testing set are plotted against the number of passes over the training set.ASGD achieves near optimal results after one pass.Figure3reports results achieved using SGD,SGDQN,and ASGD for a CRF(Lafferty et al.,2001)trained on the CONLL2000Chunking task (Tjong Kim Sang and Buchholz,2000).The training set contains8936sen-tences for a1.68×106dimensional parameter space.Performances measured on a separate testing set are plotted against the number of passes over the training set.SGDQN appears more attractive because ASGD does not reach its asymptotic performance.All three algorithms reach the best test set per-formance in a couple minutes.The standard CRF L-BFGS optimizer takes 72minutes to compute an equivalent solution.ReferencesBORDES.A.,BOTTOU,L.,and GALLINARI,P.(2009):SGD-QN:Careful Quasi-Newton Stochastic Gradient Descent.Journal of Machine Learning Research, 10:1737-1754.With Erratum(to appear).BOTTOU,L.and BOUSQUET,O.(2008):The Tradeoffs of Large Scale Learning, In Advances in Neural Information Processing Systems,vol.20,161-168. BOTTOU,L.and LECUN,Y.(2004):On-line Learning for Very Large Datasets.Applied Stochastic Models in Business and Industry,21(2):137-151 BOUSQUET,O.(2002):Concentration Inequalities and Empirical Processes The-ory Applied to the Analysis of Learning Algorithms.Th`e se de doctorat,Ecole Polytechnique,Palaiseau,France.10L´e on BottouCORTES, C.and VAPNIK,V.N.(1995):Support Vector Networks,Machine Learning,20:273-297.DENNIS,J.E.,Jr.,and SCHNABEL,R.B.(1983):Numerical Methods For Un-constrained Optimization and Nonlinear Equations.Prentice-Hall JOACHIMS,T.(2006):Training Linear SVMs in Linear Time.In Proceedings of the12th ACM SIGKDD,ACM Press.LAFFERTY,J.D.,MCCALLUM,A.,and PEREIRA,F.(2001):Conditional Ran-dom Fields:Probabilistic Models for Segmenting and Labeling Sequence Data.In Proceedings of ICML2001,282-289,Morgan Kaufman.LEE,W.S.,BARTLETT,P.L.,and WILLIAMSON,R.C.(1998):The Importance of Convexity in Learning with Squared Loss.IEEE Transactions on Informa-tion Theory,44(5):1974-1980.LEWIS,D.D.,YANG,Y.,ROSE,T.G.,and LI,F.(2004):RCV1:A New Bench-mark Collection for Text Categorization Research.Journal of Machine Learn-ing Research,5:361-397.LIN,C.J.,WENG,R.C.,and KEERTHI,S.S.(2007):Trust region Newton methods for large-scale logistic regression.In Proceedings of ICML2007,561-568,ACM Press.MACQUEEN,J.(1967):Some Methods for Classification and Analysis of Multi-variate Observations.In Fifth Berkeley Symposium on Mathematics,Statistics, and Probabilities,vol.1,281-297,University of California Press. MASSART,P.(2000):Some applications of concentration inequalities to Statistics, Annales de la Facult´e des Sciences de Toulouse,series6,9,(2):245-303. MURATA,N.(1998):A Statistical Study of On-line Learning.In Online Learning and Neural Networks,Cambridge University Press.POLYAK,B.T.and JUDITSKY,A.B.(1992):Acceleration of stochastic approx-imation by averaging.SIAM J.Control and Optimization,30(4):838-855. ROSENBLATT,F.(1957):The Perceptron:A perceiving and recognizing automa-ton.Technical Report85-460-1,Project PARA,Cornell Aeronautical Lab. RUMELHART,D.E.,HINTON,G.E.,and WILLIAMS,R.J.(1986):Learning internal representations by error propagation.In Parallel distributed processing: Explorations in the microstructure of cognition,vol.I,318-362,Bradford Books. SHALEV-SHWARTZ,S.and SREBRO,N.(2008):SVM optimization:inverse de-pendence on training set size.In Proceedings of the ICML2008,928-935,ACM. TIBSHIRANI,R.(1996):Regression shrinkage and selection via the Lasso.Journal of the Royal Statistical Society,Series B,58(1):267-288.TJONG KIM SANG E. F.,and BUCHHOLZ,S.(2000):Introduction to the CoNLL-2000Shared Task:Chunking.In Proceedings of CoNLL-2000,127-132. TSYBAKOV,A.B.(2004):Optimal aggregation of classifiers in statistical learning, Annals of Statististics,32(1).VAPNIK,V.N.and CHERVONENKIS,A.YA.(1971):On the Uniform Con-vergence of Relative Frequencies of Events to Their Probabilities.Theory of Probability and its Applications,16(2):264-280.WIDROW, B.and HOFF,M. E.(1960):Adaptive switching circuits.IRE WESCON Conv.Record,Part4.,96-104.XU,W.(2010):Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent.Journal of Machine Learning Research(to ap-pear).。