QP algorithms with guaranteed accuracy and run tim

JournalofMachineLearningResearch7(2006)733–769Submitted12/05;Revised4/06;Published5/06QPAlgorithmswith[e-mail]@[e-mail]@LANL.GOVModeling,AlgorithmsandInformaticsGroup,CCS-3,MSB265LosAlamosNationalLaboratoryLosAlamos,NM87545USAEditor:BernhardSch¨olkopfAbstractWedescribepolynomial–timealgorithmsthatproduceapproximatesolutionswithguaranteedac-curacyforaclassofQPproblemsthatareusedinthedesignofsupportvectormachineclassifiers.Thesealgorithmsemployatwo–stageprocesswherethefirststageproducesanapproximateso-lutiontoadualQPproblemandthesecondstagemapsthisapproximatedualsolutiontoanap-proximateprimalsolution.ForthesecondstagewedescribeanO(nlogn)algorithmthatmapsanapproximatedualsolutionwithaccuracy(2√2Kn+8√λ)−2λε2ptoanapproximateprimalsolutionwithaccuracyεpwherenisthenumberofdatasamples,Knisthemaximumkernelvalueoverthedataandλ0istheSVMregularizationparameter.Forthefirststagewepresentnewresultsfordecompositionalgorithmsanddescribenewdecompositionalgorithmswithguaranteedaccu-racyandruntime.Inparticular,forτ–ratecertifyingdecompositionalgorithmsweestablishtheoptimalityofτ=1/(n−1).Inadditionweextendtherecentτ=1/(n−1)algorithmofSimon(2004)toformtwonewcompositealgorithmsthatalsoachievetheτ=1/(n−1)iterationboundofListandSimon(2005),butyieldfasterruntimesinpractice.Wealsoexploittheτ–ratecertifyingpropertyofthesealgorithmstoproducenewstoppingrulesthatarecomputationallyefficientandthatguaranteeaspecifiedaccuracyfortheapproximatedualsolution.Furthermore,forthedualQPproblemcorrespondingtothestandardclassificationproblemwedescribeoperationalconditionsforwhichtheSimonandcompositealgorithmspossessanupperboundofO(n)onthenumberofiterations.Forthissameproblemwealsodescribegeneralconditionsforwhichamatchinglowerboundexistsforanydecompositionalgorithmthatusesworkingsetsofsize2.FortheSimonandcompositealgorithmswealsoestablishanO(n2)boundontheoverallruntimeforthefirststage.CombiningthefirstandsecondstagesgivesanoverallruntimeofO(n2(ck+1))whereckisanupperboundonthecomputationtoperformakernelevaluation.Pseudocodeispresentedforacompletealgorithmthatinputsanaccuracyεpandproducesanapproximatesolutionthatsatisfiesthisaccuracyinloworderpolynomialtime.ExperimentsareincludedtoillustratethenewstoppingrulesandtocomparetheSimonandcompositedecompositionalgorithms.Keywords:quadraticprogramming,decompositionalgorithms,approximationalgorithms,sup-portvectormachinesc2006DonHush,PatrickKelly,ClintScovelandIngoSteinwart.HUSH,KELLY,SCOVELANDSTEINWART1.IntroductionSolvingaquadraticprogramming(QP)problemisamajorcomponentofthesupportvectormachine(SVM)trainingprocess.Inpracticeitiscommontoemployalgorithmsthatproduceapproximatesolutions.Thisintroducesatrade-offbetweencomputationandaccuracythathasnotbeenthor-oughlyexplored.Theaccuracy,asmeasuredbythedifferencebetweenthecriterionvalueoftheapproximatesolutionandtheoptimalcriterionvalue,isimportantforlearningbecauseithasadi-rectinfluenceonthegeneralizationerror.Forexample,sincetheoptimalcriterionvalueplaysakeyroleinestablishingtheSVMperformanceboundsin(SteinwartandScovel,2004,2005;Scoveletal.,2005b)theinfluenceoftheaccuracycanbeseendirectlythroughtheproofsofthesebounds.SincetheprimalQPproblemcanbeprohibitivelylargeanditsWolfedualQPproblemisconsider-ablysmalleritiscommontoemployatwo–stagetrainingprocesswherethefirststageproducesanapproximatesolutiontothedualQPproblemandthesecondstagemapsthisapproximatedualso-lutiontoanapproximateprimalsolution.ExistingalgorithmsforthefirststageoftenallowtheusertotradeaccuracyandcomputationforthedualQPproblemthroughthechoiceofatolerancevaluethatdetermineswhentostopthealgorithm,butitisnotknownhowtochoosethisvaluetoachieveadesiredaccuracyorruntime.Furthermoreexistingalgorithmsforthesecondstagehavebeendevelopedlargelywithoutconcernforaccuracyandthereforelittleisknownabouttheaccuracyoftheapproximateprimalsolutionstheyproduce.InthispaperwedescribealgorithmsthataccepttheaccuracyεpoftheprimalQPproblemasaninputandareguaranteedtoproduceanapproximatesolutionthatsatisfiesthisaccuracyinloworderpolynomialtime.ToourknowledgethesearethefirstalgorithmsofthistypeforSVMs.Inadditionourruntimeanalysisrevealstheeffectoftheaccuracyontheruntime,therebyallowingtheusertomakeaninformeddecisionregardingthetrade–offbetweencomputationandaccuracy.AlgorithmicstrategiesforthedualQPproblemmustaddressthefactthatwhenthenumberofdatasamplesnislargethestoragerequirementsforthekernelmatrixcanbeexcessive.Thisbar-riercanbeovercomebyinvokingalgorithmicstrategiesthatsolvealargeQPproblembysolvingasequenceofsmallerQPproblemswhereeachofthesmallerQPproblemsisobtainedbyfixingasubsetofthevariablesandoptimizingwithrespecttotheremainingvariables.Algorithmicstrate-giesthatsolveaQPprobleminthiswayarecalleddecompositionalgorithmsandanumberhavebeendevelopedfordualQPproblems:(Balcazaretal.,2001;Chenetal.,2005,2006;Cristian-iniandShawe-Taylor,2000;HsuandLin,2002;HushandScovel,2003;Joachims,1998;Keerthietal.,2000,2001;Laskov,2002;Liaoeta