Proximal Gradient Descent - CMU Statistics

1 Proximal Gradient Descent (and Acceleration)Ryan TibshiraniConvex Optimization 10-725 Last time: subgradient methodConsider the problemminxf(x)withfconvex, anddom(f) =Rn. Subgradient method: choosean initialx(0) Rn, and repeat:x(k)=x(k 1) tk g(k 1), k= 1,2,3,..whereg(k 1) f(x(k 1)). We use pre-set rules for the step sizes( , diminshing step sizes rule)Iffis Lipschitz, then subgradient method has a convergence rateO(1/ 2)Upside: very generic. Downside: can be slow addressed today2 OutlineToday: Proximal Gradient Descent Convergence analysis ISTA, matrix completion Special cases Acceleration3 Composite functionsSupposef(x) =g(x) +h(x) gis convex, differentiable,dom(g) =Rn his convex, not necessarily differentiableIffwere differentiable, then Gradient Descent update would be:x+=x t f(x)Recall motivation: minimize quadratic approximation tofaroundx, replace 2f(x)by1tI,x+= argminzf(x) + f(x)T(z x) +12t z x 22 ft(z)4In our casefis not differentiable, butf=g+h, don t we make quadratic approximation tog, leavehalone?

2 That is, updatex+= argminz gt(z) +h(z)= argminzg(x) + g(x)T(z x) +12t z x 22+h(z)= argminz12t z (x t g(x)) 22+h(z)12t z (x t g(x)) 22stay close to Gradient update forgh(z)also makehsmall5 Proximal Gradient descentDefine Proximal mapping:proxh,t(x) = argminz12t x z 22+h(z) Proximal Gradient Descent : choose initializex(0), repeat:x(k)= proxh,tk(x(k 1) tk g(x(k 1))), k= 1,2,3,..To make this update step look familiar, can rewrite it asx(k)=x(k 1) tk Gtk(x(k 1))whereGtis the generalized Gradient off,Gt(x) =x proxh,t(x t g(x))t6 What good did this do?You have a right to be suspicious .. may look like we just swappedone minimization problem for anotherKey point is thatproxh,t( )has a closed-form for many importantfunctionsh. Note: Mappingproxh,t( )doesn t depend ongat all, only onh Smooth partgcan be complicated, we only need to computeits gradientsConvergence analysis: will be in terms of the number of iterations,and each iteration evaluatesproxh,t( )once (this can be cheap orexpensive, depending onh)7 Example: ISTAG iveny Rn,X Rn p, recall the lasso criterion:f( ) =12 y X 22 g( )+.

3 1 h( ) Proximal mapping is nowproxt( ) = argminz12t z 22+ z 1=S t( )whereS ( )is the soft-thresholding operator,[S ( )]i= i if i> 0if i i+ if i< , i= 1,..,n8 Recall g( ) = XT(y X ), hence Proximal Gradient update is: +=S t( +tXT(y X ))Often called the iterative soft-thresholding algorithm (ISTA).1 Verysimple algorithmExample of proximalgradient (ISTA) methodconvergence fstarSubgradient methodProximal gradient1 Beck and Teboulle (2008), A fast iterative shrinkage-thresholdingalgorithm for linear inverse problems 9 Backtracking line searchBacktracking for prox Gradient Descent works similar as before (ingradient Descent ), but operates ongand notfChoose parameter0< <1. At each iteration, start att=tinit,and whileg(x tGt(x))> g(x) t g(x)TGt(x) +t2 Gt(x) 22shrinkt= t, for some0< <1.

4 Else perform Proximal gradientupdate(Alternative formulations exist that require less computation, ,fewer calls to prox)10 Convergence analysisFor criterionf(x) =g(x) +h(x), we assume: gis convex, differentiable,dom(g) =Rn, and gis Lipschitzcontinuous with constantL >0 his convex,proxt(x) = argminz{ x z 22/(2t) +h(z)}canbe evaluatedTheorem: Proximal Gradient Descent with fixed step sizet 1/Lsatisfiesf(x(k)) f? x(0) x? 222tkand same result holds for backtracking, withtreplaced by /LProximal Gradient Descent has convergence rateO(1/k)orO(1/ ).Matches Gradient Descent rate! (But remember prox cost ..)11 Example: matrix completionGiven a matrixY Rm n, and only observe entriesYij,(i,j) .Suppose we want to fill in missing entries ( , for a recommendersystem), so we solve a matrix completion problem:minB12 (i,j) (Yij Bij)2+ B trHere B tris the trace (or nuclear) norm ofB, B tr=r i=1 i(B)wherer= rank(B)and 1(X) r(X) 0are the singularvalues12 DefineP , projection operator onto observed set:[P (B)]ij={Bij(i,j) 0(i,j)/ Then the criterion isf(B) =12 P (Y) P (B) 2F g(B)+.}

5 B tr h(B)Two ingredients needed for Proximal Gradient Descent : Gradient calculation: g(B) = (P (Y) P (B)) Prox function:proxt(B) = argminZ12t B Z 2F+ Z tr13 Claim:proxt(B) =S t(B), matrix soft-thresholding at the level .HereS (B)is defined byS (B) =U VTwhereB=U VTis an SVD, and is diagonal with( )ii= max{ ii ,0}Proof: note thatproxt(B) =Z, whereZsatisfies0 Z B+ t Z trHelpful fact: ifZ=U VT, then Z tr={UVT+W: W op 1, UTW= 0, WV= 0}Now plug inZ=S t(B)and check that we can get014 Hence Proximal Gradient update step is:B+=S t(B+t(P (Y) P (B)))Note that g(B)is Lipschitz continuous withL= 1, so we canchoose fixed step sizet= 1. Update step is now:B+=S (P (Y) +P (B))whereP projects onto unobserved set,P (B) +P (B) =BThis is the soft-impute algorithm2, simple and effective method formatrix completion2 Mazumder et al.

6 (2011), Spectral regularization algorithms for learninglarge incomplete matrices 15 Special casesProximal Gradient Descent also called composite Gradient Descent ,or generalized Gradient descentWhy generalized ? This refers to the several special cases, whenminimizingf=g+h: h= 0: Gradient Descent h=IC: projected Gradient Descent g= 0: Proximal minimization algorithm16 Projected Gradient descentGiven closed, convex setC Rn,minx Cg(x) minxg(x) +IC(x)whereIC(x) ={0x C x / Cis the indicator function ofCHenceproxt(x) = argminz12t x z 22+IC(z)= argminz C x z 22 That is,proxt(x) =PC(x), projection operator ontoC17 Therefore Proximal Gradient update step is:x+=PC(x t g(x))That is, perform usual Gradient update and then project back ontoC. Called projected Gradient Descent ()ll18 Proximal minimization algorithmConsider forhconvex (not necessarily differentiable),minxh(x) Proximal Gradient update step is just:x+= argminz12t x z 22+h(z)Called Proximal minimization algorithm.}

7 Faster than subgradientmethod, but not implementable unless we know prox in closed form19 What happens if we can t evaluate prox?Theory for Proximal Gradient , withf=g+h, assumes that proxfunction can be evaluated, , assumes the minimizationproxt(x) = argminz12t x z 22+h(z)can be done exactly. In general, not clear what happens if we justminimize this approximatelyBut, if you can precisely control the errors in approximating theprox operator, then you can recover the original convergence rates3In practice, if prox evaluation is done approximately, then it shouldbe done to decently high accuracy3 Schmidt et al. (2011), Convergence rates of inexact Proximal -gradientmethods for convex optimization 20 AccelerationTurns out we can accelerate Proximal Gradient Descent in order toachieve the optimalO(1/ )convergence rate.

8 Four ideas (threeacceleration methods) by Nesterov: 1983: original acceleration idea for smooth functions 1988: another acceleration idea for smooth functions 2005: smoothing techniques for nonsmooth functions, coupledwith original acceleration idea 2007: acceleration idea for composite functions4We will follow Beck and Teboulle (2008), an extension of Nesterov(1983) to composite functions54 Each step uses entire history of previous steps and makes two prox calls5 Each step uses information from two last steps and makes one prox call21 Accelerated Proximal Gradient methodAs before, consider:minxg(x) +h(x)wheregconvex, differentiable, andhconvex. Accelerated proximalgradient method: choose initial pointx(0)=x( 1) Rn, repeat:v=x(k 1)+k 2k+ 1(x(k 1) x(k 2))x(k)= proxtk(v tk g(v))fork= 1,2,3.

9 First stepk= 1is just usual Proximal Gradient update After that,v=x(k 1)+k 2k+1(x(k 1) x(k 2))carries some momentum from previous iterations Whenh= 0we get accelerated Gradient method22 Momentum weights:llllllllllllllllllllllllllllllll llllllllllllllllllllllllllllllllllllllll llllllllllllllllllllllllllll020406080100 (k 2)/(k + 1)23 Back to lasso example: acceleration can really help! fstarSubgradient methodProximal gradientNesterov accelerationNote: accelerated Proximal Gradient is not a Descent method24 Backtracking line searchBacktracking under with acceleration in different ways. Simpleapproach: fix <1,t0= 1. At iterationk, start witht=tk 1,and whileg(x+)> g(v) + g(v)T(x+ v) +12t x+ v 22shrinkt= t, and letx+= proxt(v t g(v)). Else keepx+Note that this strategy forces us to take decreasing step sizes.

10 (more complicated strategies exist which avoid this)25 Convergence analysisFor criterionf(x) =g(x) +h(x), we assume as before: gis convex, differentiable,dom(g) =Rn, and gis Lipschitzcontinuous with constantL >0 his convex,proxt(x) = argminz{ x z 22/(2t) +h(z)}canbe evaluatedTheorem:Accelerated Proximal Gradient method with fixed stepsizet 1/Lsatisfiesf(x(k)) f? 2 x(0) x? 22t(k+ 1)2and same result holds for backtracking, withtreplaced by /LAchieves optimal rateO(1/k2)orO(1/ )for first-order methods26 FISTABack to lasso problem:min 12 y X 22+ 1 Recall ISTA (Iterative Soft-thresholding Algorithm): (k)=S tk( (k 1)+tkXT(y X (k 1))), k= 1,2,3,..S ( )being vector soft-thresholding. Applying acceleration gives usFISTA (F is for Fast):6fork= 1,2,3,..,v= (k 1)+k 2k+ 1( (k 1) (k 2)) (k)=S tk(v+tkXT(y Xv)),6 Beck and Teboulle (2008) actually call their general acceleration technique(for generalg, h) FISTA, which may be somewhat confusing27 Lasso regression: 100 instances (withn= 100,p= 500):020040060080010001e 041e 031e 021e 011e+00kf(k) fstarISTAFISTA28 Lasso logistic regression: 100 instances (n= 100,p= 500):020040060080010001e 041e 031e 021e 011e+00kf(k) fstarISTAFISTA29Is acceleration always useful?