Newton’s Method - CMU Statistics

1 newton s MethodRyan TibshiraniConvex Optimization 10-725/36-7251 Last time: dual correspondencesGiven a functionf:Rn R, we define its conjugatef :Rn R,f (y) = maxxyTx f(x)Properties and examples: Conjugatef is always convex (regardless of convexity off) Whenfis a quadratic inQ 0,f is a quadratic inQ 1 Whenfis a norm,f is the indicator of the dual norm unitball Whenfis closed and convex,x f (y) y f(x)Relationship to duality:Primal:minxf(x) +g(x)Dual:maxu f (u) g ( u)2 newton s methodGiven unconstrained, smooth convex optimizationminf(x)wherefis convex, twice differentable, anddom(f) =Rn. Recallthat gradient descent chooses initialx(0) Rn, and repeatsx(k)=x(k 1) tk f(x(k 1)), k= 1,2,3,..In comparison, newton s Method repeatsx(k)=x(k 1) ( 2f(x(k 1))) 1 f(x(k 1)), k= 1,2,3,..Here 2f(x(k 1))is the Hessian matrix offatx(k 1)3 newton s Method interpretationRecall the motivation for gradient descent step atx: we minimizethe quadratic approximationf(y) f(x) + f(x)T(y x) +12t y x 22overy, and this yields the updatex+=x t f(x) newton s Method uses in a sense a better quadratic approximationf(y) f(x) + f(x)T(y x) +12(y x)T 2f(x)(y x)and minimizes overyto yieldx+=x ( 2f(x)) 1 f(x)4 Forf(x) = (10x21+x22)/2 + 5 log(1 +e x1 x2), compare gradientdescent (black) to newton s Method (blue), where both take stepsof roughly same length 20 1001020 20 1001020lllllllllllllllllllllllllllllllll lllllllllllllllllllllllllll(For our example we needed to consider a nonquadratic.)

2 Why?)5 OutlineToday: Interpretations and properties Backtracking line search Convergence analysis Equality-constrained newton Quasi- newton methods6 Linearized optimality conditionAternative interpretation of newton step atx: we seek a directionvso that f(x+v) = 0. Now consider linearizing this optimalitycondition0 = f(x+v) f(x) + 2f(x)vand solving forv, which again yieldsv= ( 2f(x)) 1 f(x)4869 Unconstrained minimizationf f (x,f (x))(x+ xnt,f (x+ xnt))Figure solid curve is the derivativef of the functionfshown infigure f is the linear approximation off xntis the difference between the root of f and the zero-crossing of the derivativef ,whichismonotonicallyincreasingsincefisc onvex. Given our current approximationxof the solution, we form a first-orderTaylor approximation off approximation isthenx+ invariance of the newton stepAn important feature of the newton step is that it is independent of linear (oraffine) changes of coordinates.

3 SupposeT Rn nis nonsingular, and define f(y)=f(Ty). Then we have f(y)=TT f(x), 2 f(y)=TT 2f(x)T,wherex= fatyis therefore ynt= (TT 2f(x)T) 1(TT f(x))= T 1 2f(x) 1 f(x)=T 1 xnt,where xntis the newton step farerelated by the same linear transformation, andx+ xnt=T(y+ ynt).The newton decrementThe quantity (x)=( f(x)T 2f(x) 1 f(x))1/2is called an important role in the analysis of newton s Method , and is also useful(From B & V page 486)For us xnt=vHistory: work of newton (1685)and Raphson (1690) originally fo-cused on finding roots of (1740) ap-plied this idea to general nonlin-ear equations, and minimizationby setting the gradient to zero7 Affine invariance of newton s methodImportant property newton s Method : affine invariance. Givenf,nonsingularA Rn n. Letx=Ay, andg(y) =f(Ay). Newtonsteps ongarey+=y ( 2g(y)) 1 g(y)=y (AT 2f(Ay)A) 1AT f(Ay)=y A 1( 2f(Ay)) 1 f(Ay)HenceAy+=Ay ( 2f(Ay)) 1 f(Ay) ,x+=x ( 2f(x)) 1f(x)So progress is independent of problem scaling; recall that this isnot true of gradient descent8 newton decrementAt a pointx, we define the newton decrement as (x) =( f(x)T( 2f(x)) 1 f(x))1/2 This relates to the difference betweenf(x)and the minimum of itsquadratic approximation:f(x) miny(f(x) + f(x)T(y x) +12(y x)T 2f(x)(y x))=f(x) (f(x) 12 f(x)T( 2f(x)) 1 f(x))=12 (x)2 Therefore can think of 2(x)/2as an approximate bound on thesuboptimality gapf(x) f?

4 9 Another interpretation of newton decrement: if newton directionisv= ( 2f(x)) 1 f(x), then (x) =(vT 2f(x)v)1/2= v 2f(x) , (x)is the length of the newton step in the norm defined bythe Hessian 2f(x)Note that the newton decrement, like the newton steps, are affineinvariant; , if we definedg(y) =f(Ay)for nonsingularA, then g(y)would match f(x)atx=Ay10 Backtracking line searchWe have seen pure newton s Method , which need not converge. Inpractice, we instead use damped newton s Method ( , newton smethod), which repeatsx+=x t( 2f(x)) 1 f(x)Note that the pure Method usest= 1 Step sizes here typically are chosen by backtracking search, withparameters0< 1/2,0< <1. At each iteration, we startwitht= 1and whilef(x+tv)> f(x) + t f(x)Tvwe shrinkt= t, else we perform the newton update. Note thatherev= ( 2f(x)) 1 f(x), so f(x)Tv= 2(x)11 Example: logistic regressionLogistic regression example, withn= 500,p= 100: we comparegradient descent and newton s Method , both with backtracking0102030405060701e 131e 091e 051e 011e+03kf fstarGradient descentNewton's methodNewton s Method seems to have a different regime of convergence!

5 12 Convergence analysisAssume thatfconvex, twice differentiable, havingdom(f) =Rn,and additionally fis Lipschitz with parameterL fis strongly convex with parameterm 2fis Lipschitz with parameterMTheorem: newton s Method with backtracking line search sat-isfies the following two-stage convergence boundsf(x(k)) f? (f(x(0)) f?) kifk k02m3M2(12)2k k0+1ifk > k0 Here = 2 2m/L2, = min{1,3(1 2 )}m2/M, andk0isthe number of steps until f(x(k0+1)) 2< 13In more detail, convergence analysis reveals >0,0< m2/Msuch that convergence follows two stages Damped phase: f(x(k)) 2 , andf(x(k+1)) f(x(k)) Pure phase: f(x(k)) 2< , backtracking selectst= 1, andM2m2 f(x(k+1)) 2 (M2m2 f(x(k)) 2)2 Note that once we enter pure phase, we won t leave, because2m2M(M2m2 )2< when m2/M14 Unraveling this result, what does it say? To reachf(x(k)) f?

6 , we need at mostf(x(0)) f? + log log( 0/ )iterations, where 0= 2m3/M2 This is called quadratic convergence. Compare this to linearconvergence (which, recall, is what gradient descent achievesunder strong convexity) The above result is a local convergence rate, , we are onlyguaranteed quadratic convergence after some number of stepsk0, wherek0 f(x(0)) f? Somewhat bothersome may be the fact that the above bounddepends onL,m,M, and yet the algorithm itself does not15 Self-concordanceA scale-free analysis is possible for self-concordant functions: onR,a convex functionfis called self-concordant if|f (x)| 2f (x)3/2for allxand onRnis called self-concordant if its projection onto every linesegment is so. ,f(x) = log(x)is self-concordantTheorem (Nesterov and Nemirovskii): newton s methodwith backtracking line search requires at mostC( , )(f(x(0)) f?)

7 + log log(1/ )iterations to reachf(x(k)) f? , whereC( , )is a constantthat only depends on , 16 Comparison to first-order methodsAt a high-level: Memory: each iteration of newton s Method requiresO(n2)storage (n nHessian); each gradient iteration requiresO(n)storage (n-dimensional gradient) Computation: each newton iteration requiresO(n3)flops(solving a densen nlinear system); each gradient iterationrequiresO(n)flops (scaling/addingn-dimensional vectors) Backtracking: backtracking line search has roughly the samecost, both useO(n)flops per inner backtracking step Conditioning: newton s Method is not affected by a problem sconditioning, but gradient descent can seriously degrade Fragility: newton s Method may be empirically more sensitiveto bugs/numerical errors, gradient descent is more robust17 Back to logistic regression example.

8 Now x-axis is parametrized interms of time taken per 131e 091e 051e 011e+03 Timef fstarGradient descentNewton's methodEach gradient descent step isO(p), but each newton step isO(p3)18 Sparse, structured problemsWhen the inner linear systems (in Hessian) can be solved efficientlyand reliably, newton s Method can , if 2f(x)is sparse and structured for allx, say banded, thenboth memory and computation areO(n)with newton iterationsWhat functions admit a structured Hessian? Two examples: Ifg( ) =f(X ), then 2g( ) =XT 2f(X )X. Hence ifXis a structured predictor matrix and 2fis diagonal, then 2gis structured If we seek to minimizef( ) +g(D ), where 2fis diagonal,gis not smooth, andDis a structured penalty matrix, thenthe Lagrange dual function is f ( DTu) g ( u). Often D 2f ( DTu)DTcan be structured19 Equality-constrained newton s methodConsider now a problem with equality constraints, as inminf(x) subject toAx=bSeveral options: Eliminating equality constraints: writex=Fy+x0, whereFspans null space ofA, andAx0=b.

9 Solve in terms ofy Deriving the dual: can check that the Lagrange dual functionis f ( ATv) bTv, and strong duality holds. With luck, wecan expressx?in terms ofv? Equality-constrained newton : in many cases, this is the moststraightforward option20In equality-constrained newton s Method , we start withx(0)suchthatAx(0)=b. Then we repeat the updatesx+=x+tv,wherev= argminAz=0 f(x)T(z x) +12(z x)T 2f(x)(z x)This keepsx+in feasible set, sinceAx+=Ax+tAv=b+ 0 =bFurthermore,vis the solution to minimizing a quadratic subject toequality constraints. We know from KKT conditions thatvsatisfies[ 2f(x)ATA0][vw]=[ f(x)0]for somew. Hence newton directionvis again given by solving alinear system in the Hessian (albeit a bigger one)21 Quasi- newton methodsIf the Hessian is too expensive (or singular), then a quasi-Newtonmethod can be used to approximate 2f(x)withH 0, and weupdate according tox+=x tH 1 f(x) Approximate HessianHis recomputed at each step.

10 Goal isto makeH 1cheap to apply (possibly, cheap storage too) Convergence is fast: superlinear, but not the same as of quasi- newton make same progress as oneNewton step Very wide variety of quasi- newton methods ; common themeis to propogate computation ofHacross iterations22 Davidon-Fletcher-Powell or DFP: UpdateH,H 1via rank 2 updates from previous iterations;cost isO(n2)for these updates Since it is being stored, applyingH 1is simplyO(n2)flops Can be motivated by Taylor series expansionBroyden-Fletcher-Goldfarb-Shann o of BFGS: Came after DFP, but BFGS is now much more widely used Again, updatesH,H 1via rank 2 updates, but does so in a dual fashion to DFP; cost is stillO(n2) Also has a limited-memory version, L-BFGS: instead of lettingupdates propogate over all iterations, only keeps updates fromlastmiterations; storage is nowO(mn)instead ofO(n2)23 References and further reading S.