Optimization Methods: Understanding Gradient Descent and Second Order Techniques

This content delves into the concepts of gradient descent and second-order methods in optimization. Gradient descent is a first-order method utilizing the first-order Taylor expansion, while second-order methods consider the first three terms of the multivariate Taylor series. Second-order methods like Newton's Method, Gauss-Newton, Quasi-Newton, BFGS, and LBFGS offer more accurate approximations by incorporating curvature information. The discussion covers the working principles, advantages, and applications of these optimization techniques.

• Optimization Methods
• Gradient Descent
• Second Order Techniques
• Newtons Method
• Multivariate Taylor Series

vaughn Follow

Uploaded on Aug 07, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Lecture 7: Second Order Methods Nicholas Ruozzi University of Texas at Dallas

2. Gradient Descent Gradient Descent Algorithm: Pick an initial point ?0 Iterate until convergence ??+1= ?? ????(??) where ??is the ?? step size (sometimes called learning rate) 2

3. Gradient Descent At a high level, gradient descent uses the first order Taylor expansion to approximate the function locally Does not take into account the curvature of the function, i.e., how quickly the gradient is changing This means that it can dramatically overshoot the optimum with a fixed step size 3

4. Second Order Methods Instead of using only the first derivatives, second order methods use the first three terms of the multivariate Taylor series expansion ?? ?0 +1 2?????0? ? ? ? ?0 + ? ?0 ?2? ??1 ?2? ??1??? 2 ? ? ?? ? = ?2? ?????1 ?2? ??? ? 2 ? 4

5. Second Order Methods Instead of using only the first derivatives, second order methods use the first three terms of the multivariate Taylor series expansion ?? ?0 +1 ????0 ? ?0 ? ? ? ?0 + ? ?0 2? ?0 ?2? ??1 ?2? ??1??? 2 ? ? ?? ? = ?2? ?????1 ?2? ??? ? 2 ? Sometimes written 2?( ?) 5

6. Second Order Methods Instead of using only the first derivatives, second order methods use the first three terms of the multivariate Taylor series expansion ?? ?0 +1 ????0 ? ?0 ? ? ? ?0 + ? ?0 2? ?0 ???? = ??????? ?,? 6

7. Second Order Methods Instead of using only the first derivatives, second order methods use the first three terms of the multivariate Taylor series expansion ?? ?0 +1 ????0 ? ?0 ? ? ? ?0 + ? ?0 2? ?0 There are a variety of second order methods Newton Gauss-Newton Quasi-Newton BFGS LBFGS 7

8. Newtons Method Again, let s start with the univariate case, ?: Newton s method is a root-finding algorithm, i.e., it seeks a solution to the equation ? ? = 0 How it works: Compute the first order approximation at ?? ? ? ? ?? + ? ?? ? ?? Solve ? ?? + ? ?? ? ?? = 0 for ? Set ??+1= ?? ?(??)/? (??) 8

9. Newtons Method 9

10. Newtons Method 10

11. Newtons Method 11

12. Newtons Method 12

13. Newtons Method 13

14. Newtons Method I thought we were talking about second order methods? We are: Newton s method for optimization applies the previous strategy to find the zeros of the first derivative Approximate: ? ? ? ?? + ? ?? ? ?? Update: ??+1= ?? ? (??)/? (??) This is equivalent to minimizing the second order approximation! 14

15. Multivariate Newtons Method 1 ?(??) Update: ??+1= ?? ???? Recall the inverse of a matrix ?, written ? 1, is the matrix such that ?? 1= ?, the identity matrix Inverses do not always exist, if the inverse doesn t exist, then there may be no solution or infinitely many solutions Computing the inverse can be expensive: requires ?(?3) operations for an ? ? matrix Computing the Hessian matrix itself can be computationally expensive Can converge faster than gradient methods, but is less robust in general 15

16. Gradient Descent ? ?,? = .1?4+ ? 22 (? 2)(? 2) + .5 ? 22 with diminishing step size rule 16

17. Newtons Method ? ?,? = .1?4+ ? 22 (? 2)(? 2) + .5 ? 22 17

18. Newton Direction If ?is convex, then the direction specified by Newton s method is a descent direction! Recall that the Hessian matrix of a convex function is positive semidefinite everywhere A matrix ? is positive semidefinite if ???? 0 for all ? 1 ?(??) Newton direction: ???? ????? 1 ? ?? 0 ? ?? 18

19. Newton Direction If ?is convex, then the direction specified by Newton s method is a descent direction! Recall that the Hessian matrix of a convex function is positive semidefinite everywhere A matrix ? is positive semidefinite if ???? 0 for all ? 1 ?(??) Newton direction: ???? ????? 1 ? ?? 0 ? ?? ????? 1 ? ?? ? Can be used a stopping criteria: ? ?? 19

20. Convergence Because Newton s method specifies a descent direction, we can use the same kinds of convergence criteria that we used for gradient descent! We could choose different step sizes, use line search methods, etc. with this direction One computational note: the inverse is often not computed explicitly Most numerical methods packages have a special routine to solve linear systems of the form ?? = ? For example, numpy.linalg.solve() in Python 20

21. Equality Constrained Newton Two different approaches: One based on duality One based on quadratic programming Aim is just to make sure that the step taken via Newton s method stays inside the constraint set 21

22. Equality Constrained Newton with Duality min ? ?0(?) subject to ?? = ? Dual problem: ?0? + ??(?? ?) ?0? + ???? ?0? + ????? ? ? = inf = ??? + inf = ??? sup ? ? ? 22

23. Equality Constrained Newton with Duality min ? ?0(?) subject to ?? = ? Dual problem: ?0? + ??(?? ?) ?0? + ???? ?0? + ????? ? ? = inf = ??? + inf = ??? sup ? ? ? This function comes up frequently in convex optimization, gets a special name 23

24. The Convex Conjugate The convex conjugate ? of a function ? is defined by ? ? = sup ??? ?(?) ? The convex conjugate is always a convex function, even if ? is not a convex function (it is a pointwise supremum of convex functions) The conjugate is a special case of Lagrange duality If ?: ? is convex, then ? = ? 24

25. Equality Constrained Newton with Duality min ? ?0(?) subject to ?? = ? Dual problem: ?0? + ??(?? ?) ?0? + ???? ?0? + ????? = ??? ? ??? ? ? = inf = ??? + inf = ??? sup ? ? ? If this function is twice differentiable, we can apply Newton s method to solve the dual 25

26. Equality Constrained Newton via QP/KKT Instead of constructing the dual problem, we can directly modify Newton s method so that it never takes a step outside the set of constraints Recall that Netwon s method steps to a minimum of the second order approximation at a point ?? ?? ?? +1 ????? ? ?? + ? ?? 2? ?? ? ?? 26

27. Equality Constrained Newton via QP/KKT Instead of constructing the dual problem, we can directly modify Newton s method so that it never takes a step outside the set of constraints Recall that Netwon s method steps to a minimum of the second order approximation at a point ?? ?? ?? +1 ????? ? ?? + ? ?? 2? ?? ? ?? Instead, solve the optimization problem ?? +1 2?????? ? ??. ??=0? ?? + ? ?? min ? 27

28. Equality Constrained Newton via QP/KKT Pick an initial point ?0 such that ??0= ? Solve the optimization problem ?? +1 ? argmin ? ??. ??=0 2?????? ? ?? + ? ?? ? Update ??+1= ??+ ?? 28

29. Equality Constrained Newton via QP/KKT Pick an initial point ?0 such that ??0= ? Solve the optimization problem ?? +1 ? argmin ? ??. ??=0 2??????(?) ? ?? + ? ?? Update ??+1= ??+ ?? Note that A??+1= ???+ ??? = ???= = ??0= ? 29

30. Equality Constrained Newton via QP/KKT ?? +1 2?????? ? ??. ??=0 ? ?? min ? The solution to this optimization problem can be written in almost closed form As long as there is at least on feasible point, Slater s condition implies strong duality holds KKT conditions are then necessary and sufficient 30

31. Equality Constrained Newton via QP/KKT ?? +1 2?????? ? ??. ??=0 ? ?? min ? ?? +1 ? + ? ??? ?? ? ,? = ? ? ?? 2? ????? = 0 ?? = 0 31

32. Equality Constrained Newton via QP/KKT ?? +1 2?????? ? ??. ??=0 ? ?? min ? ?? ? ,? = ? ?? + ????(? ) + ??? = 0 ?? = 0 32

33. Equality Constrained Newton via QP/KKT ?? +1 2?????? ? ??. ??=0 ? ?? min ? ?? ? ,? = ? ?? + ????(? ) + ??? = 0 ?? = 0 ?? 0 ? ? = ?(??) ??(??) ? 0 Again, existing tools can be applied to solve these kinds of linear systems 33

34. Approximate Newton Computing the Hessian matrix is computationally expensive and may be difficult in closed form (or maybe even not invertible!) Idea: can we approximate the Hessian the same way that we did the derivatives on HW 1, i.e., using the secant method? For univariate functions ? ? ? ? + ? ? (? ?) 2? 34

35. Approximate Newton Computing the Hessian matrix is computationally expensive and may be difficult in closed form (or maybe even not invertible!) Idea: can we approximate the Hessian the same way that we did the derivatives on HW 1, i.e., using the secant method? For univariate functions ? ?? ? ??+1 ? (??) ??+1 ?? Use the sequence of iterates to approximate the 2nd derivative! 35

36. Approximate Newton Computing the Hessian matrix is computationally expensive and may be difficult in closed form (or maybe even not invertible!) Idea: can we approximate the Hessian the same way that we did the derivatives on HW 1, i.e., using the secant method? For multivariate functions ???? ??+1 ?? ? ??+1 ?(??) Use the sequence of iterates to approximate the 2nd derivative! 36

37. Approximate Newton Computing the Hessian matrix is computationally expensive and may be difficult in closed form (or maybe even not invertible!) Idea: can we approximate the Hessian the same way that we did the derivatives on HW 1, i.e., using the secant method? For multivariate functions ???? ??+1 ?? ? ??+1 ?(??) Key idea is to replace ??(??) with a good approximation that yields equality in this expression, but is much easier to compute 37

38. Approximate Newton Computing the Hessian matrix is computationally expensive and may be difficult in closed form (or maybe even not invertible!) Idea: can we approximate the Hessian the same way that we did the derivatives on HW 1, i.e., using the secant method? For multivariate functions ???? ??+1 ?? = ? ??+1 ?(??) Note that this a system of ? equations for an ? ? Hessian, so this system is underdetermined: there could be many possible substitutions for ?? 38

39. Quasi-Newton Methods Using the previous approximation, the Quasi-Newton methods seek to generate a series of approximate Hessian matrices ?0,?1, such that the ?? matrix only depends on the ? 1? matrix and satisfies the constraint ??+1 ??+1 ?? = ? ??+1 ?(??) 39

40. Quasi-Newton Methods Using the previous approximation, the Quasi-Newton methods seek to generate a series of approximate Hessian matrices ?0,?1, such that the ?? matrix only depends on the ? 1? matrix and satisfies the constraint ??+1 ??+1 ?? = ? ??+1 ?(??) A wide variety of methods have been proposed to accomplish this The most popular in practice are BFGS and its lower memory counterpart L-BFGS 40

41. Broyden-Fletcher-Goldfarb-Shanno (BFGS) Choose ??+1 to be a symmetric positive definite matrix whose inverse ??+1satisfies ??+1 ?? = ??+1 ? ??+1 ?(??) 2 is as small as possible and ??+1 ?? ? 41

42. Broyden-Fletcher-Goldfarb-Shanno (BFGS) 2 ??+1 ? ???+1 ?? ? min such that T ??+1= ??+1 ??+1 ?? = ??+1 ? ??+1 ? ?? ????+1? 0 for all ? This is a convex optimization problem! (note that the solution may not be strictly positive definite: if this happens, reinitialize ??+1 to be a nice positive definite matrix like ?) 42

43. Broyden-Fletcher-Goldfarb-Shanno (BFGS) 2 ??+1 ? ???+1 ?? ? min such that T ??+1= ??+1 ??+1 ?? = ??+1 ? ??+1 ? ?? ????+1? 0 for all ? Its solution is... messy... 43

44. Broyden-Fletcher-Goldfarb-Shanno (BFGS) 2 ??+1 ? ???+1 ?? ? min such that T ??+1= ??+1 ??+1 ?? = ??+1 ? ??+1 ? ?? ????+1? 0 for all ? ??+1= ? ??+1 ? ??? ? ? ??+1 ? ?? ? ??+1 ?? ??+1 ?? ? ??+1 ? ?? ??+1 ?? ??+1 ?? ? ?? ? ? ? ??+1 ? ?? ? ??+1 ?? ??+1 ?? + ? ? ??+1 ? ?? ??+1 ?? 44