Gradient Descent - CMU Statistics

← Back to document page

Gradient DescentRyan TibshiraniConvex Optimization 10-725Last time: canonical convex programs Linear program (LP): takes the formminxcTxsubject toDx dAx=b Quadratic program (QP): like LP, but with quadratic criterion Semidefinite program (SDP): like LP, but with matrices Conic program: the most general form of all2Gradient descentConsider unconstrained, smooth convex optimizationminxf(x)That is,fis convex and differentiable withdom(f) =Rn. Denoteoptimal criterion value byf?= minxf(x), and a solution byx? Gradient Descent : choose initial pointx(0) Rn, repeat:x(k)=x(k 1) tk f(x(k 1)), k= 1,2,3,...Stop at some point3lllll4lllll5Gradient Descent interpretationAt each iteration, consider the expansionf(y) f(x) + f(x)T(y x) +12t y x 22Quadratic approximation, replacing usual Hessian 2f(x)by1tIf(x) + f(x)T(y x)linear approximation tof12t y x 22proximity term tox, with weight1/(2t)Choose next pointy=x+to minimize quadratic approximation:x+=x t f(x)6llBlue point isx, red point isx+= argminyf(x) + f(x)T(y x) +12t y x 227OutlineToday: How to choose step sizes Convergence analysis Nonconvex functions Gradient boosting8Fixed step sizeSimply taketk=tfor allk= 1,2,3.

Ryan Tibshirani Convex Optimization 10-725. Last time: canonical convex programs Linear program (LP): takes the form min x cTx subject to Dx d Ax= b Quadratic program (QP): like LP, but with quadratic criterion Semide nite program (SDP): like LP, but with matrices Conic program: the most general form of all

  Yarn, Descent, Tibshirani, Ryan tibshirani