Transcription of Gradient Descent - CMU Statistics
{{id}} {{{paragraph}}}
Example: marketing
Gradient Descent - CMU Statistics
Gradient DescentRyan TibshiraniConvex Optimization 10-725 Last 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 all2 Gradient 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 point3lllll4lllll5 Gradient Descent interpretationAt each iteration, consider the expansionf(y) f(x) + f(x)T(y x) +12t y x 22 Quadratic 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 227 OutlineToday: How to choose step sizes Convergence analysis Nonconvex functions Gradient boosting8 Fixed 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
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: