13Duality and auxiliary functions for Bregman dist

DualityandAuxiliaryFuntionsforBregmanDistanesStephenDellaPietra,VinentDellaPietra,andJohnLaertyFebruary10,2002CMU-CS-01-109RShoolofComputerSieneCarnegieMellonUniversityPittsburgh,PA15213AbstratWeformulateandproveaonvexdualitytheoremforBregmandistanesandpresentatehniquebasedonauxiliaryfuntionsforderivingandprovingonvergeneofiterativealgorithmstominimizeBregmandistanesubjettolinearonstraints.ThisresearhwaspartiallysupportedbytheAdvanedResearhandDevelopmentAtivityinInformationTehnology(ARDA),ontratnumberMDA904-00-C-2106,andbytheNationalSieneFoundation(NSF),grantCCR-9805366.TheviewsandonlusionsontainedinthisdoumentarethoseoftheauthorsandshouldnotbeinterpretedasrepresentingtheoÆialpoliies,eitherexpressedorimplied,ofARDA,NSF,ortheU.S.government.Keywords:Bregmandistane,onvexduality,Legendrefuntions,auxiliaryfuntionsI.IntrodutionConvexityplaysaentralroleinawidevarietyofmahinelearningandstatistialinfereneprob-lems.Astandardparadigmistodistinguishapreferredmemberfromasetofandidatesbaseduponaonveximpuritymeasureorlossfuntiontailoredtothespeiproblemtobesolved.Examplesinludeleastsquaresregression,deisiontrees,boosting,onlinelearning,maximumlike-lihoodforexponentialmodels,logistiregression,maximumentropy,andsupportvetormahines.SuhproblemsanoftenbenaturallyastasonvexoptimizationproblemsinvolvingaBregmandistane,whihanleadtonewalgorithms,analytialtools,andinsightsderivedfromthepowerfulmethodsofonvexanalysis.InthispaperweformulateandproveaonvexdualitytheoremforminimizingagenerallassofBregmandistanessubjettolinearonstraints.Thedualityresultisthenusedtoderiveiterativealgorithmsforsolvingtheassoiatedoptimizationproblem.OurpresentationismotivatedbythereentworkofCollins,Shapire,andSinger(2001),whoshowedhowertainboostingalgorithmsandmaximumlikelihoodlogistiregressionanbeuniedwithintheframeworkofBregmandistanes.Inpartiular,speiinstanesoftheresultsgivenhereareusedbyCollinsetal.(2001)toshowtheonvergeneofafamilyiterativealgorithmsforminimizingtheexponentialorlogistiloss.Whileinvokingmethodsfromonvexanalysisanunifyandlarifytherelationshipbetweendier-entmethods,thehigherlevelofabstrationoftenomesataprie,sinethereanbeonsiderabletehnialities.Forexample,insometreatmentstheassumptionsontheonvexfuntionsthatanbeusedtodeneBregmandistanesareverytehnialanddiÆulttoverify.HerewetradeogeneralityforrelativesimpliitybyworkingwitharestritedlassofBregmandistanes,whihhoweverinludesmanyoftheexamplesthatariseinmahinelearning.OurtreatmentofdualityandauxiliaryfuntionsforBregmandistanesloselyparallelstheresultspresentedbyDellaPietraetal.(1997)fortheKullbak-Leiblerdivergene.Inpartiular,thestatementandproofofthedualitytheoremgivenin(DellaPietraetal.,1997)arriesoverwithonlyafewhangestothelassofBregmandistanesweonsider.Ourapproahdiersfrommuhoftheliteratureinonvexanalysisinseveralways.First,weworkprimarilywiththeargumentatwhihaonvexonjugatetakesonitsvalue,ratherthanthevalueofthefuntionitself.Thereasonforthisisthattheargumentorrespondstoastatistialmodel,whihisthemainobjetofinterestinstatistialormahinelearningappliations,whilethevalueorrespondstoalikelihoodorlossfuntion.Seond,whileBregmandistanesaretypiallydenedonlyontheinteriorofthedomainoftheunderlyingonvexfuntion,weassumethatthereisaontinuousextensiontotheentiredomain.Thismakesitpossibletoformulateaverynaturaldualitytheoremthatalsoinludesmanyasesrequiredinpratie,whenthedesiredmodelmaylieontheboundaryofthedomain.Thefollowingsetionreallsthestandarddenitionsfromonvexanalysisthatwillberequired,andpresentsthetehnialassumptionsmadeonthelassofBregmandistanesthatweworkwith.Wealsointroduesomenewterminology,usingthetermsLegendre-BregmanonjugateandLegendre-BregmanprojetiontoextendthelassialnotionoftheLegendreonjugateandtransformtoBregmandistanes.Setion3ontainsthestatementandproofofthedualitytheoremthatonnetstheprimalproblemwithitsdual,showingthatthesolutionisharaterizedingeometrialterms1byaPythagoreanequality.Setion4denesthenotionofanauxiliaryfuntion,whihisusedtoonstrutiterativealgorithmsforsolvingonstrainedoptimizationproblems.ThissetionshowshowonvexityanbeusedtoderiveanauxiliaryfuntionforBregmandistanesbasedonseparablefuntions.Thelastsetionsummarizesthemainresultsofthepaper.II.BregmanDistanesandLegendre-BregmanProjetionsInthissetionwebeginbyestablishingournotationandreallingtherelevantnotionsfromonvexanalysisthatwerequire;thelassitext(Rokafellar,1970)remainsoneofthebestreferenesforthismaterial.WethendeneBregmandistanesandtheirassoiatedonjugatefuntionsandprojetions,andderivevariousrelationsbetweenthesethatwillbeimportantinprovingthedualitytheorem.NextwestateourassumptionsontheunderlyingonvexfuntionthatenableustoderivethesepropertiesfortheontinousextensionoftheBregmandistanetotheentiredomain.A.NotationandBasiDenitionsWewillusenotationthatissuggestiveofourmainappliations:ratherthan(x)wewillwrite(p)or(q),havinginmindprobabilitydistributionsporq.Aonvexfuntion:SRm![1;+1℄isproperifthereisnoq2Swith(q)=1andthereissomeqwith(q)6=1.Theeetivedomainof,denoted,isthesetofpointswhereisnite:=fq2Sj(q)1g;for