# Lecture 9: Gradient-based Numerical Optimization

[Recording](https://www.youtube.com/watch?v=UNb8KegjEZw)

Automatic transcript; technical terms and equations may contain recognition errors.

00:00:00 Okay, let's get started. Howdy. So we are going to continue the search in the

00:00:22 midnight zone for the protein structure prediction problem and algorithmically we are in the module of optimization.

00:00:34 So we're in the world of optimization we have seen how different kind of problems in different scenarios of protein structure prediction

00:00:43 could be formulated and solved as linear programming, dynamic programming, and numerical optimization. In this case non-convex numerical optimization.

00:00:55 So last time we already gave some, we finished the formulation part. We talked about what are the objective function, search space, and algorithm needs, right?

00:01:13 for this problem. Then we started talking about non-convex optimization, right? So we already talked about the basic concepts such as stationary points, minimums, and how to interpret these contours because we are going to use them later on as well.

00:01:33 Remember that we have introduced one new theoretical concept called convergence and convergence rate. This is specific to iterative algorithms, right? That update the sample step by step, right? So in this case, you of course still care about whether an algorithm is accurate. So you ask

00:02:03 in this case, it's an optimization algorithm that's iterative. You ask whether it converges to the desired minimum. But also you care about how fast it converges. So that's what the convergence rate defines. It's always comparing the distance to the global optimum or the local optimum. In the current step,

00:02:31 the current step compared to such distance in the previous step to the power of p. And you can ask whether this limit is zero or finite. Okay? So this is another concept, right? So can you remind me what are the aspects we care about for algorithms besides accuracy?

00:02:58 So what are the aspects we care about for algorithms?

00:03:02 Time and space?

00:03:03 Time and space?

00:03:05 Right? CPU and memory?

00:03:08 And also robustness, right?

00:03:10 So let's keep those in mind.

00:03:13 For those aspects of algorithms, what theoretical concepts can we rely on for sanity check?

00:03:25 When you design a new algorithm, when you analyze an existing algorithm, what are the concepts we can rely on?

00:03:35 For accuracy, if we are talking about optimization algorithms that are iterative, convergence is the theoretical concept for accuracy, right?

00:03:47 So we talked about convergence rate, which is specific to the iterative algorithms, right?

00:04:01 Because you're asking how fast does it converge, right? How many iterations does it need, right?

00:04:08 What's the theoretical concept for accuracy?

00:04:09 Right?

00:04:10 Anything else?

00:04:11 Something you have learned before?

00:04:15 Convergence rate only tells you roughly, right?

00:04:20 Like how fast could these iterative updates converge, right?

00:04:26 What else do you care about?

00:04:29 What about each iteration?

00:04:32 How much resource do you consume?

00:04:34 What concepts, what theoretical concept would you use in each iteration?

00:04:41 What would you look at?

00:04:48 The efficiency of every step, every iteration.

00:04:54 What is the theoretical concept?

00:04:57 What is the theoretical concept?

00:04:58 What is the theoretical concept?

00:04:59 What is the theoretical concept?

00:05:00 What is the theoretical concept?

00:05:02 What is the theoretical concept?

00:05:03 Complexity.

00:05:04 Time and space complexity.

00:05:06 Time and space complexity.

00:05:07 CPU memory.

00:05:08 Okay, so what would happen next is we will use these theoretical concepts.

00:05:18 Okay?

00:05:19 To guide our understanding of multiple algorithms.

00:05:24 Okay?

00:05:25 And we are also going to use these theoretical concepts to show how algorithmic innovation can be perceived

00:05:36 and pursued because we always ask how do I introduce some innovative ideas to your research, right?

00:05:42 This is one example to show you where the ideas are coming from, right?

00:05:46 Okay, let's start with the simplest gradient-based algorithm that is gradient descent.

00:05:57 So it's very simple.

00:05:59 You know, almost every iterative optimizer has this similar expression that is the next iteration

00:06:08 sample is equal to the current iteration sample plus something.

00:06:13 So basically, when you add them together, you're asking, you know, a vector sum.

00:06:20 This is a vector sum, which basically says that starting from the last iteration sample, I'm going to walk along the direction of p sub k, right?

00:06:29 I'm going to walk along the direction by lambda sub k.

00:06:33 So p sub k is the direction, and lambda sub k is the step size, okay?

00:06:42 If you choose this direction to be the negative gradient, right, gradient is the steepest ascent.

00:06:51 The negative gradient is the steepest ascent.

00:06:54 So if you are interested in minimizing, you're going to, you know, take a greedy approach and take the steepest descent.

00:07:01 Then once the direction is known, all it remains is how far, right?

00:07:06 This is a step size, also known as learning rate when you are training a deep learning model by minimizing its loss function, right?

00:07:17 So this is a tricky question, and we can show you why this is tricky, okay?

00:07:24 Let's consider this one-dimensional space of x, right?

00:07:31 x is a scalar, right?

00:07:33 And y is the function f of x.

00:07:36 This is a very simple quadratic function, okay?

00:07:39 So let's pretend that we don't know the analytical solution, and we have to numerically solve the global optimum.

00:07:44 And you may start from here.

00:07:46 So by starting from here, I know I put a point here.

00:07:49 What I mean is that in your search space, which is one dimension, x0 is like minus 1.5, okay?

00:07:56 So when I put a point here, keep in mind that the x-coordinate is the search space, okay?

00:08:03 All right, so starting from here, what does the steepest descent tell you?

00:08:08 Remember, you are in the one-dimensional space.

00:08:11 You can only go left or right.

00:08:13 So would you go left or right?

00:08:14 You are going to go right, right?

00:08:18 Because that is the steepest descent telling you, right?

00:08:21 So you are going to go right, and let's say you, you know, depending on how far, right?

00:08:28 So if I move from minus 1.5 to minus 0.5, right?

00:08:33 I am going to reach search space x here, but I am going to put the sample point here with the y-coordinate so that you can see it clearly.

00:08:41 So that would be ideal.

00:08:42 So I directly glide down from this rim to close to the bottom.

00:08:48 So that is great, right?

00:08:50 But what if I overshoot?

00:08:52 So I overshoot.

00:08:53 So I start from minus 1.5.

00:08:55 I know I am going to go right, but I go all the way to plus 1.2.

00:09:00 So I reach this one.

00:09:02 So x0 is minus 1.5, and x1 is 1.2.

00:09:09 So I overshoot, right?

00:09:11 So once I reach x1, should I go left or right now following the steepest descent at the local region?

00:09:19 Should I go left or right now?

00:09:24 You should go left.

00:09:25 Okay, what if I take a large step size and overshoot again?

00:09:29 From 1.2 I reached minus 1.2.

00:09:33 So you can see that if I follow this trajectory with a large step size, what I see is like,

00:09:40 I'm like, you know, bumping left and right just slowly toward the global optimum.

00:09:49 But it's like bumping left and right, right?

00:09:51 It's like some computer games you played, right?

00:09:54 These balls are, you know, pinned left and right, left and right, keeps bouncing, bouncing.

00:09:59 But that may be idea for the computer program because you can keep bouncing the balls and get the reward.

00:10:06 But here, don't forget, our goal is to reach the global minimum as soon as possible.

00:10:14 Okay?

00:10:15 If the step size is too small, is that safe?

00:10:18 Well, again, let's start from here.

00:10:21 And the steepest descent tells me I should go left.

00:10:24 I take a very small step size.

00:10:26 So I start from 1.5 and I then take a left and reach to 1.3.

00:10:33 Okay?

00:10:34 And then next step, I'm supposed to take a left again.

00:10:37 So I reached a small, I took a small step size and reached x equal to about 1.1.

00:10:44 So you can see that if I connect these sample points in the x, y coordinate, what you see is that I'm, yes, I am always following that correct direction, right?

00:10:59 But I'm taking so small steps that it will take forever to converge as well.

00:11:04 So neither is a good idea.

00:11:06 So if the step size is too large or too small, neither is a good idea.

00:11:11 So what is a good idea then, right?

00:11:14 So there are some guidelines, there are some guidelines, you know, for the choice of the step size, right?

00:11:21 For instance, one of the guidelines is that, you know, you want to choose, for instance, a constant step size that is not too large and not too small.

00:11:34 This one is a little bit tricky though.

00:11:36 I mean, it's hard for you to actually do that.

00:11:39 And also choosing a constant step size, no matter how appropriate you think it is, you know, in general, it's not a good idea, right?

00:11:49 So that's why you see sometimes in training deep learning models, people have a schedule for the learning rate, right?

00:11:58 The learning rate is not like, I know you're treating learning rate as a hyperparameter,

00:12:03 and the search agreed that that's what people do.

00:12:07 It's like trying multiple constant learning rate or step sizes, right?

00:12:12 But a lot of the successful optimizers, right, like Adam or other optimizers, if you want to train deep learning model user in a good, you know, good enough learning rate,

00:12:24 usually you have a starting value of the learning rate, but then there is also a schedule of the learning rate, right?

00:12:30 So how this learning rate changes over time.

00:12:34 So that schedule is also part of the algorithm.

00:12:37 So in other words, constant step size is not a good idea.

00:12:42 Don't think that you can get the appropriate step size over all the k, over all the iterations.

00:12:50 That's not going to happen.

00:12:53 What is a good idea is that your step size want to start with something like finite, but then gradually approaches zero.

00:13:02 So in other words, you know, you want to gradually approach the global optimum and stay there, okay?

00:13:09 One of the rule is called the Armidius rule, that is trying to diminish the step size by considering a rho to the power of k.

00:13:18 If rho is between zero and one, then rho to the power of k is decreasing with the increase of k, right?

00:13:25 If you multiply rho to the power of k times lambda zero, right, then that is your rule, right?

00:13:34 So it's a decreasing rule.

00:13:36 So what does the choice of the step size affect?

00:13:41 What theoretical concept is affected by the choice of the step size?

00:13:54 Is any theoretical concept we talked about before, convergence, convergence rate, time complexity, space complexity, any of them affected by the choice of step size, lambda sub k?

00:14:10 So like I said before, if the step size is too large, so it will bump off the curve, but the step size is too small, I think maybe we can stop in some local limit, so...

00:14:38 So you think it affects the number of iterations.

00:14:41 Correspondingly, it's a convergence rate.

00:14:44 Good.

00:14:45 Any other thoughts?

00:14:47 We're trying to save time.

00:14:52 We're trying to save time, so the time here is the number of iterations times the time spent over every iteration.

00:15:02 So, Ru-Jie talked about the number of iterations by looking at the convergence rate.

00:15:07 So now you're saying time, that means you are looking at the time spent in each iteration, is that right?

00:15:13 So that's time complexity.

00:15:15 So depending on how you do the line search, okay, you could have a very sophisticated algorithm to do the line search at each iteration.

00:15:27 And then that affects your time and space complexity in every iteration, right?

00:15:33 So, but isn't convergence itself also affected?

00:15:39 Just like what you said, sometimes if I use a wrong constant step size, for instance, it may never converge.

00:15:47 So all of these theoretical concepts are affected actually.

00:15:51 So let's look at a very high level summary of the pros and cons of the steepest descent.

00:16:00 There's no order, no high order derivatives, just the first order.

00:16:04 Easy to understand, easy to implement.

00:16:06 In each iteration, we have the linear time complexity and the linear data complexity.

00:16:14 Why?

00:16:15 Let's look at the expression.

00:16:20 Why is it linear time and the linear space complexity in every iteration?

00:16:27 In each iteration, what do we have to calculate?

00:16:30 The gradients and the sum, right?

00:16:38 So, right, so if x is in the dimension of n, then this is linear in n, right?

00:16:44 The space complexity is also linear because we have to store x, which is n dimensional, right?

00:16:54 X sub k.

00:16:56 We also have to store p sub k, which is n dimensional, right?

00:17:00 So both the time and space complexity are linear in n, right?

00:17:10 So that's very simple.

00:17:12 But the problem is that if you say that, well, it seems like it's great because it's a linear time complexity and a linear space complexity in every iteration,

00:17:25 and you know that, you know, I really don't dream about global convergence for non-convex optimization.

00:17:32 Anyway, all I care is the local convergence, convergence to the local optimum.

00:17:37 So that sounds great already.

00:17:38 What else do I worry about it?

00:17:41 Why don't I just keep using it?

00:17:42 Well, you forgot about the convergence rate, even if you think convergence is there, right?

00:17:47 So the convergence rate is actually just a linear, if you recall, what's the definition of the convergence rate, right?

00:17:54 It just means that if you compare the distances between two consecutive iterations, right, this p equal to one and beta is less than one.

00:18:07 So, right?

00:18:09 So it's a fraction, the distance decreases, it's like a fraction of the last iterations distance, right, to the global optimum, and it's just a linear convergence.

00:18:23 Okay?

00:18:24 So that's not fast enough.

00:18:26 So then, if you do care about it, you say that, well, how should I improve the algorithm?

00:18:32 I want to make it faster.

00:18:34 I want to run less iterations.

00:18:36 So it sounds like, what would you do then?

00:18:40 You would have to use more information then, right?

00:18:43 Because you want to make a faster convergence rate.

00:18:46 You're going to have to use more information to help it.

00:18:48 So what information could potentially help the convergence rate?

00:18:55 What information have you used so far?

00:18:59 The zeroes order and the first order information, isn't it?

00:19:04 F of x and the gradient of f of x.

00:19:07 What other information can you use to improve the convergence?

00:19:15 That's right.

00:19:16 One of the idea is, why don't I use higher order information, right?

00:19:20 Second order.

00:19:21 So, the gradient descent algorithm is simple but slow.

00:19:26 So simple is in the time and space complexity in every iteration.

00:19:30 Slow in the sense of the convergence rate, right?

00:19:33 It's linear convergence.

00:19:35 Newton's method on the other, you know, end of the spectrum is complicated and faster.

00:19:45 Okay?

00:19:46 As I said, you need additional information to make it faster.

00:19:49 If you really want to make it faster, right?

00:19:51 You need additional information, you know.

00:19:55 So you probably have to sacrifice the time and space complexity in every iteration.

00:19:59 But in the end, you get a faster convergence rate.

00:20:03 In this case, it's a quadratic convergence.

00:20:05 Okay?

00:20:06 What Newton's method is trying to do is the following.

00:20:09 Okay?

00:20:10 Look, we are trying to use up to the second order information, right?

00:20:15 So let's use a Taylor expansion, right?

00:20:18 Around any x bar.

00:20:20 This could be your last iterations sample, x sub k, for instance.

00:20:24 Okay?

00:20:25 Imagine that you are now at x sub k, and you are wondering what should be my next x sub k plus one.

00:20:34 What should be my next sample?

00:20:36 Okay?

00:20:37 So if that is the case, you know, of course, you want to find, you know, the global optimum or local optimum of f, right?

00:20:47 But the information you can use is only up to the second order.

00:20:51 So let's approximate this f by g.

00:20:56 I apologize for the notation.

00:20:58 Usually I use g for the gradient.

00:21:00 But here, only in this slide, g is the approximate form of x, okay?

00:21:06 So this g is a Taylor expansion of x around x bar or x sub k, you know, the starting point from the last iteration, right?

00:21:16 And then you expand it all the way up to the second order.

00:21:19 So this is a linear algebra expression, right?

00:21:21 Remember, without any introduction, whenever we look at a vector, we are usually looking at the column vector.

00:21:29 So that's why you have these, you know, transpose and everything, okay?

00:21:36 Okay, so our f is a scalar.

00:21:39 So you have the row, matrix, and the column.

00:21:42 So the product is a scalar, okay?

00:21:46 So now the question is the following, right?

00:21:50 So instead of minimizing f of x, I can minimize approximate f of x.

00:21:55 And one of the necessary but not sufficient condition for the local minimum is it has to be a stationary point, right?

00:22:05 So we need to make sure that this gradient of the approximate function is zero.

00:22:12 That is a necessary condition, right?

00:22:15 So then we can take the gradient for the g of x, right?

00:22:20 We did this practice before.

00:22:21 If you try to do the gradient of these three terms, the first term, gradient equal to zero.

00:22:27 Second term, gradient equals to what?

00:22:32 Just this nabla f of x bar, right?

00:22:37 Which is a column vector.

00:22:39 And the last one is, you know, Ryan said last time, right?

00:22:43 He is just the Hessian times the x minus x bar.

00:22:48 Okay?

00:22:49 So if you, you know, write down what I just said,

00:22:54 which is the gradient of the approximate equal to zero,

00:22:57 then you realize that x minus x bar equal to this expression,

00:23:02 which is minus the inverse of the Hessian around x bar times the gradient of,

00:23:12 the gradient at x bar, okay?

00:23:15 So again, you think of x bar as the last iteration sample, okay?

00:23:21 So if you write it down, then you realize that, oh, what this condition is telling me is that,

00:23:34 starting from x bar, where do I want to go next?

00:23:37 This direction is determined by the inverse of the Hessian times the minus the gradient.

00:23:44 So in other words, it's the inverse of the Hessian times the steepest descent, right?

00:23:49 So in other words, this is great.

00:23:52 This direction is called the Newton direction.

00:23:55 I don't even have to tell, you know, what's the step size.

00:23:58 I don't have to even ask how far I should walk along that direction, right?

00:24:03 So this is a Newton's direction.

00:24:05 Again, if you compare this to the steepest descent, which is minus the gradient,

00:24:10 what is here is it's multiplied to the inverse of the Hessian.

00:24:14 So this is the Newton's direction, okay?

00:24:17 Again, if you regard x bar as x sub k, and this x is x sub k plus 1.

00:24:23 So you already get an updated rule, right?

00:24:26 Right?

00:24:27 So this is exactly what I'm trying to say, right?

00:24:30 You know, starting from an initial sample, find the Newton's direction at iteration k, right?

00:24:37 And then just update it, right?

00:24:40 Every time you just add this Newton's direction to the last iteration sample, right?

00:24:45 So this is, this g sub k is a gradient you have seen before.

00:24:51 Again, I apologize.

00:24:52 The only time I use g for approximate is only in this slide, okay?

00:24:58 But you really, you know, my g here is a gradient.

00:25:01 So, so this is the only difference compared to the, you know, the steepest descent, okay?

00:25:08 Of course, you have to assume that, you know, like Solomon asked last time,

00:25:15 that the Hessian is not only available, right, around x sub k, but also it's invertible, right?

00:25:23 That means the Hessian cannot have zero eigenvalues, right?

00:25:28 In other words, it cannot be singular, right?

00:25:31 But also keep in mind that we are doing this, you know, approximate function and this necessary condition.

00:25:41 So there's really no guarantee that the next iterations sample will have a lower function value compared to the current iteration, okay?

00:25:50 There's no such guarantee for sure.

00:25:52 And the convergence rate, I told you directly, that is great, it's quadratic, right?

00:25:59 You know, we can see how it can be proven.

00:26:01 And then in each iteration, what, how much CPU and memory do we need, right?

00:26:07 We need to compare, can calculate the gradient, we need to calculate the Hessian, we need to calculate the inverse of the Hessian.

00:26:13 The question for you is what is the time and data complexity in every iteration?

00:26:18 What is the time complexity?

00:26:25 How many elements are there in the Hessian?

00:26:33 How many elements are there in the Hessian?

00:26:40 If X is in the n-dimensional space?

00:26:44 N-squared?

00:26:46 Okay.

00:26:47 What's the computational complexity of calculating the inverse of the m-by-m matrix?

00:27:00 Okay.

00:27:01 I give you the answer.

00:27:15 I would recommend you to take a look into it after the lecture, right?

00:27:19 It's n-cubed.

00:27:20 Okay.

00:27:21 So the time complexity of Newton's method is n-cubed because of the inverse of the Hessian.

00:27:31 The data complexity is only n-squared because, you know, inverse or not, you only have n-squared components or numbers, right, to store for the Hessian or inverse of the Hessian.

00:27:42 And then you have n-squared components or the gradient, right?

00:27:46 So n-squared plus n, which is basically n-squared, right?

00:27:50 So the data complexity is n-squared and time complexity is n-cubed.

00:27:55 And with such little bit sacrifice, not just a little bit, it's a lot of sacrifice if n is large, right?

00:28:05 So that's why you don't see people using Newton's method for training neural networks where n can be millions, right?

00:28:12 And the rate of convergence is pro.

00:28:17 That is quadratic, okay?

00:28:20 So now imagine that you live in that moment of the history.

00:28:26 We have seen two kinds of non-convex gradient-based algorithms so far.

00:28:31 One is gradient descent, simple and slow.

00:28:35 One is Newton's method, complicated and faster.

00:28:39 What would you do next to improve?

00:28:43 Combine them to do what?

00:28:46 For what purpose?

00:28:49 Maybe for some steps we can use new .

00:29:04 Depending upon the composition, we have time that .

00:29:13 So you're talking about like depending on what scenario I'm going to use one of them or maybe I can combine them, right?

00:29:22 But before you answer how do I accomplish something, my question is what do you want to accomplish first?

00:29:32 Not how you bring the innovation, but you know what kind of innovation you want to bring?

00:29:42 Great.

00:29:44 So you want to keep it simple.

00:29:46 You want to start with a gradient descent.

00:29:48 Keep it simple, but make it a little bit faster, right?

00:29:53 Good point.

00:29:54 Or you start with a Newton's method, right?

00:29:59 You make it as fast or you know slightly slower, but much, much simpler compared to the complicated Newton, right?

00:30:06 So both are possible, right?

00:30:08 Right?

00:30:09 So this is how you innovate, right?

00:30:11 As to how you accomplish that, that's a different question, okay?

00:30:15 But first you need to know what do you want to accomplish, okay?

00:30:19 Great.

00:30:20 As I said, gradient descent and Newton's methods are like two ends of a spectrum, right?

00:30:27 Now you know that there's no free lunch.

00:30:31 You cannot be good at every theoretical concept measures.

00:30:36 I'm sorry, measures.

00:30:37 So you have to sacrifice.

00:30:39 Somehow you have to have a sweet spot.

00:30:41 So you have to start from the Newtons, right, for instance, and then move a little bit toward the, you know, that sweet spot of the spectrum or starting from the gradient descent.

00:30:53 So let's start with the gradient descent and ask how can we keep it simple, right?

00:30:59 And but make it faster.

00:31:02 So we're going to talk about mostly the idea about the conjugate gradient and the quasi-Newton, okay?

00:31:09 As you can see, right, conjugate gradient from the name, conjugate gradient is some improvement to steepest descent.

00:31:19 And quasi-Newton is some improvement from Newton.

00:31:22 And you know exactly, you know, what they are improving, right, based on what we just talked about, okay?

00:31:28 All right, now let's continue.

00:31:30 Start with steepest descent and let's ask, you know, what is making it so slow, okay?

00:31:40 You remember I was introducing a two-dimensional contour and a three-dimensional mesh before, right?

00:31:47 So three-dimensional mesh has two-dimensional search space plus a one-dimensional function space, right?

00:31:52 So now let's look at the two-dimensional contour, okay?

00:31:56 Not the one-dimensional you have seen in the steepest descent.

00:32:00 Let's regard this as a contour of a quadratic function.

00:32:04 It's almost like, right, this ellipsoid, right?

00:32:07 This line means that x1 and x2 on those points are of the same function value, right?

00:32:13 And let's assume that this is like a convex function, so more to the center, the lower the function value, okay?

00:32:22 So we'd like to go to the global optimum here, okay?

00:32:26 Let's say we start from x0 here.

00:32:30 What is the direction of the gradient?

00:32:34 If I'm here, what is the direction of the gradient?

00:32:40 Gradient.

00:32:46 Gradient.

00:32:47 Gradient is the steepest ascent, right?

00:32:52 So it should be perpendicular to the tangent line at this point, right?

00:32:59 Right, if you draw a tangent, then something perpendicular to it, that's your g of x0, right?

00:33:07 Then you take the opposite direction, that's your minus g of x0, okay?

00:33:12 So let's say that we took this step size and then we reached here, okay?

00:33:21 Then the steepest descent, right, minus the gradient is now going this direction, right?

00:33:28 Because the gradient is the steepest ascent, as I said, more to the rim, less from the center, the function value is increasing, right?

00:33:36 So the gradient is perpendicular to the tangent and goes that direction.

00:33:40 So then if I take the minus, right, it goes this direction, right?

00:33:44 And then you keep going and keep going.

00:33:47 And then what problem do you see here?

00:33:50 You see that in a non-ideal case, remember, in this non-ideal case, our search trajectory in the two-dimensional space is zigzagging, right?

00:34:05 Zigzagging means what?

00:34:06 If you are driving, if you have to zigzag to your destination, what does that tell you?

00:34:13 Slow, right?

00:34:18 Low convergence rate, if your destination is your convergence point you want to be, right?

00:34:25 So how do you, if you think that zigzagging pattern, right, is part of the problem for the linear convergence rate,

00:34:36 how could you diminish the zigzagging?

00:34:41 How could you diminish zigzagging?

00:34:45 Well, let's ask what zigzagging means.

00:34:48 Zigzagging means, you know, in this case, if the two consecutive gradients are perpendicular to each other, right?

00:34:56 Right?

00:34:57 In the two-dimensional space, right?

00:34:58 So that means, that is what zigzagging means.

00:35:02 And then if you want to say that, okay, if zigzagging is a problem, I want to minimize zigzagging, and how do I do that?

00:35:09 I want the consecutive directions, p sub k, right?

00:35:15 Previously, p sub k is defined by minus g sub k, right?

00:35:19 So can I make sure that the consecutive directions are not so perpendicular, right?

00:35:29 Not so zigzagging.

00:35:30 And the best way to make them exactly not zigzagging is to take a straight line, to make, you know, this iterations direction to be exactly the same as last iterations direction.

00:35:44 But that straight line, although it's avoiding zigzagging, is not helping your minimization either, right?

00:35:50 So in other words, you do want to keep using the information, specifically the gradient in the local sample.

00:35:59 Also, you want to make sure that it's not perpendicular to the history, to the past iterations direction, right?

00:36:07 How do you do that?

00:36:08 What conjugate gradient is saying that, well, that's simple.

00:36:14 Let's just add these two directions together.

00:36:18 Let's say last iteration, you know, the direction is p sub k, right?

00:36:24 And without considering the zigzagging, my update in this current iteration would be the steepest descent, right?

00:36:31 Then if I add this direction, right?

00:36:34 Modify this direction by a fraction or a scaled p sub k, right?

00:36:41 Then the new direction p sub k minus one, right?

00:36:46 Is, you know, if you take the inner product of p sub k plus one and p sub k, right?

00:36:55 Because p sub k plus one already contains p sub k as one of the component,

00:37:00 now this inner product is not going to be close to zero.

00:37:04 It's going to be less zigzagging, right?

00:37:06 So this is what the conjugate gradient is doing.

00:37:09 So it's a very simple idea if you look at it, right?

00:37:12 So, of course, this beta is also tricky, right?

00:37:17 How to choose the beta is also tricky, right?

00:37:20 So this is the idea of a conjugate gradient, okay?

00:37:23 And the change here is the following, right?

00:37:29 So here, again, all we are trying to do is figure out the direction d sub k, okay?

00:37:35 And that contains the unit direction and the step size, okay?

00:37:41 So in the steepest descent case, the direction is minus g, right?

00:37:46 And the lambda k is by line search.

00:37:48 In the case of the Newton's method, p sub k is the Newton's direction, right?

00:37:53 And the lambda k is essentially one, right?

00:37:56 In the case of the conjugate gradient, as I said, all you are doing is to make sure that p sub k, right?

00:38:05 So the gradient is not only the steepest descent in the current iteration, but also, you know, summed to a fraction, or not a fraction, depending on what is the beta k, right?

00:38:19 Summed to the scaled version of the last iterations direction, okay?

00:38:26 So as I said that, you know, the choice of the beta is kind of tricky, right?

00:38:32 One method is an FR method, right?

00:38:36 So named after the initials of the scientist is using this kind of choice.

00:38:41 We'll see these kind of choices again.

00:38:43 The smart thing about this kind of choice is using the gradient in the current iteration and the last iteration,

00:38:50 use the inner product and the ratio between them and then calculate the beta.

00:38:55 It's like scaling, right?

00:38:58 Scaling the norms, right?

00:39:00 This is norm squared divided by norm squared, right?

00:39:03 So that's the choice here, okay?

00:39:06 So if you're interested in this more numerical optimization, chapter 5 has more information about it.

00:39:13 So as I said, with steepest descent, even for quadratic function, you may take

00:39:19 infinite number of iterations.

00:39:22 But with conjugate gradient, you can, you know, converge actually for the quadratic function, okay?

00:39:31 Very simple, quadratic convex function.

00:39:34 You can make sure that this can converge within n iterations when n is the dimension of the search space, okay?

00:39:41 So this is really great, right?

00:39:42 Of course, we are minimizing not a quadratic function, but a more non-convex function.

00:39:47 But this is really great, right?

00:39:50 Does anyone, so the convergence rate is great.

00:39:53 I haven't told you what's the convergence rate, right?

00:39:55 Right?

00:39:56 So I'm going to give a summary after I introduce the next method, right?

00:40:01 So the convergence rate is faster than linear, right?

00:40:05 But it's not quadratic, okay?

00:40:08 It's not as fast as Newton, right?

00:40:11 It's a super linear, right?

00:40:13 So what about the time and the space complexity here?

00:40:16 So if you look at this update rule, what's your conclusion of the time and the space complexity?

00:40:29 Pardon me?

00:40:32 We need?

00:40:33 We need to not space to store the previous direction.

00:40:36 Yes, we need to store, so you are talking about the space complexity, so we need to store the previous, yes.

00:40:44 And we need to store, right?

00:40:48 So we need to store GK, we need to store GK minus one, G sub K minus one, right?

00:40:57 And we need to store the last iterations, P.

00:40:59 So is that linear, quadratic in N?

00:41:02 Huh?

00:41:03 So you think the space complexity is linear in N, right?

00:41:16 Because of the vectors that, the size of the vectors, right?

00:41:20 We store the gradients.

00:41:22 What about the time complexity?

00:41:25 We need to do some inner products.

00:41:29 It's quadratic in N, okay.

00:41:34 So we have these two proposals.

00:41:37 We'll see whether the answer is correct in just a few slides.

00:41:40 Okay, let's keep that in mind.

00:41:42 Now let's go the other direction, okay?

00:41:45 So far we have made a steepest descent.

00:41:48 You know, starting from the steepest descent, we made things not so simple but faster, okay?

00:41:57 Another possibility is starting from the Newton's method, which is complicated but fast.

00:42:02 Let's make it less complicated but still, you know, fast enough, okay?

00:42:07 So how can we make it less complicated?

00:42:10 Let's look at the Newton's method again and why do we, you know, complain about the, you know, complexity?

00:42:20 The problem is the Newton's direction here.

00:42:23 We have to calculate the inverse of the Hessian times the gradient, which is computation and memory intensive, okay?

00:42:31 So if we cannot or we don't want to, you know, precisely calculate the inverse of the Hessian and everything, because that's computation and memory intensive, can we approximate them?

00:42:47 We can, can we approximate them iteratively?

00:42:50 So that's the idea of the quasi-Newton, okay?

00:42:54 So the quasi-Newton method basically asks, well, if we have to estimate, for instance, the Hessian, right?

00:43:01 Let's use B sub K to approximate the Hessian.

00:43:04 Then it has to satisfy this condition, the second condition, okay?

00:43:09 This condition is very easy to understand, right?

00:43:12 If you regard these as if they are scalars, not the gradient, then if you divide both sides by X sub K minus X sub K minus one, then you have gradient minus gradient divided by X minus X, which gives you the second order information, right?

00:43:28 Of course, what I said is, you know, like a scalar, right?

00:43:31 But remember here, X is a vector and B is a matrix, right?

00:43:37 But I hope that kind of approximate, not approximate, that kind of interpretation can help you understand the second condition, okay?

00:43:47 So it's nothing mysterious at all, okay?

00:43:50 So then we can design B sub K, right?

00:43:53 That can satisfy the second condition, right?

00:43:57 This is the so-called BFGS method, right?

00:44:03 So you must have heard of L minus, sorry, LBFGS, where L stands for limited memory.

00:44:09 And the BFGS here is, again, you know, initials of four great scientists, right?

00:44:16 Anyone knows their names?

00:44:19 Pardon me?

00:44:24 Huh?

00:44:25 I think that's a guess.

00:44:29 G, I don't think so, I don't think so.

00:44:36 Anyway, I mean, if you're curious about it, I think there's Void, there's Fletcher, G is a Goldstein, I must be wrong, S is channel.

00:44:47 So these are the initials of four scientists.

00:44:50 So they designed this update rule for B sub K, so that it's satisfying the second condition, but don't have to use cubic or quadratic time and space complexity.

00:45:07 So that's what they do, okay?

00:45:08 So if you look at it, they actually keep using the last iterations, hash and estimate.

00:45:13 They keep using the last iterations, you know, gradient, right?

00:45:18 They calculate the sample difference in consecutive iterations, they calculate the gradient difference in consecutive iterations.

00:45:27 They use them, okay?

00:45:29 You can, even better if you can iteratively update some estimate of the inverse of the hash and directly.

00:45:36 That's even better, right?

00:45:37 Because, you know, in the end, you need the inverse, right?

00:45:40 So you can do that as well.

00:45:43 So, and then I put a square bracket here is that, you know, you can even make things even faster, right?

00:45:55 For instance, you could think of truncated Newton, right?

00:45:59 So the truncated Newton is, again, instead of approximating the Hessian or the inverse of the Hessian,

00:46:07 it's trying to approximate the Newton equation, right, when it's far from the minimum.

00:46:13 So if you are interested, I put a slice here and you want to look into it.

00:46:19 So very interesting things, okay?

00:46:24 So, now let's try to summarize them again.

00:46:28 As I said earlier, when we care about the performance of iterative methods for optimization,

00:46:35 we have practical concerns and we have the theoretical expectations,

00:46:40 where theoretical expectations are guiding our practical expectations, right?

00:46:47 So you may wonder, will my algorithm end up at the global optimum?

00:46:52 That's what convergence can tell you.

00:46:55 How many iterations?

00:46:56 That's the rate of convergence tell you.

00:46:58 What's the computational cost or running time per iteration?

00:47:02 That's what time complexity can tell you.

00:47:04 What's the memory footprint in each iteration?

00:47:07 That's what space complexity can tell you.

00:47:10 So you don't have to randomly design an algorithm and test or run them for a long time in HPRC

00:47:18 and still cannot get a conclusion, right?

00:47:20 Before proposing them, you should have already some kind of expectations based on the theory.

00:47:25 So that's what the theories are good at, okay?

00:47:30 And then let me again summarize these different methods in the theoretical expectations, right?

00:47:37 So as I said, Stipe's descent is slow, it's a linear convergence.

00:47:44 Newton is faster, it's a quadratic convergence.

00:47:48 Conjugated gradient and the quasi-Newton are both super-linear.

00:47:53 So one is starting from the steepest descent and adding a little bit more information.

00:47:58 One is starting from the Newtons and, you know, approximate the Hessian or its inverse instead of calculating exactly.

00:48:07 So due to that reason, when we look at the conjugate gradient, we said that the time and the data complexity is still order of n, but convergence rate is super-linear, okay?

00:48:19 For the quasi-Newton, when we approximate the Hessian or the inverse of the Hessian, the time complexity is now just the order of n squared

00:48:29 because we don't have to solve the inverse of the Hessian anymore.

00:48:32 We just use some updated rule to approximate the inverse of the Hessian, which involves a lot of vector or matrix multiplications, right?

00:48:42 The matrices are of size n by n, and vectors are of size n, right?

00:48:47 And the truncated Newton is even faster, which I didn't talk too much about.

00:48:51 The rate of convergence is quadratic, okay?

00:48:55 So that's why before having to train deep learning where before n is that huge that we're dealing now, when we talk about the large n, right?

00:49:07 We used to prefer using these quasi- or truncated Newtons, right?

00:49:12 If you have a memory concerns, then you probably go to conjugate gradients.

00:49:16 But anyway, let's try to put them together is that depending on the concerns you have, right?

00:49:24 If the complexity, we can see that the steepest descent is the lowest and the classic Newton is the highest, right?

00:49:33 But if you talk about convergence, steepest descent is also the slowest, where the quasi- and truncated Newtons

00:49:40 and the Newtons are increasingly faster and faster.

00:49:47 Any questions so far?

00:49:52 Any question?

00:49:54 Okay, so then again, there's this very interesting idea.

00:49:59 I said that this LBFGS must be something that you keep hearing.

00:50:04 LBFGS.

00:50:07 LBFGS is the limited memory version of the BFGS, okay?

00:50:12 So it's saying that, well, in the case of BFGS, you have a smart way of calculating beta, right?

00:50:18 And approximate the inverse of the Hessian, iteration after iteration.

00:50:23 But why do I need the inverse of the Hessian?

00:50:29 I need the inverse of the Hessian because I want to multiply it to the gradient and calculate the Newton's direction, right?

00:50:35 Then why don't we directly update this Newton's direction using the previous iterations?

00:50:44 Again, sample difference and gradient difference.

00:50:49 So that's what the limited memory BFGS is doing.

00:50:53 Then there are other kind of methods like sparse quasi-Newton, where this quasi-Newton is using a sparse version of B sub K.

00:51:01 So I think it's very important still nowadays.

00:51:07 I know that there's atom, there's a stochastic gradient for you to train deep learning models.

00:51:13 But why do I still find it so interesting to review these classical optimization algorithms, which are large scale in their world?

00:51:24 One of the reasons is that by looking at how these algorithms evolved in history, we actually learn a lot of things for our current problems.

00:51:36 Because you see that we can learn a lot of things about how we innovate, right?

00:51:41 So the second reason is that not just the innovation, you know, the way to innovate can be learned from these classical methods.

00:51:51 In fact, there are so much wisdom in these classical methods that nowadays, even in the world of deep learning, when you try to, if you are trying to design a better optimizer to train your, you know, to train your loss function over special architecture, right?

00:52:07 You still have to consider a lot of classical wisdom.

00:52:11 What really happens is that people just, you know, rejuvenate, excuse me, rejuvenate, right?

00:52:20 These classical wisdom or methods in the new world of deep learning, right?

00:52:28 So not only the innovative approaches can be learned, but also the innovative ideas can get, you know, reincarcerated in this new world of deep learning.

00:52:41 So these are my, my, why I think this lecture, you know, to me it's very interesting and I also hope that you see why we are talking about this.

00:52:54 They are not outdated at all in my understanding, not only for the innovative approach, but even for the innovative ideas.

00:53:05 A lot of the classical methods are now being rewritten into the deep learning models, okay?

00:53:12 So, so let me summarize this portion, right?

00:53:17 We talked about gradient-based algorithms and I think we look at that the theoretical expectations, convergence, convergence, rate, time, and space complexity,

00:53:29 and we look at two methods from these theoretical expectations perspectives, and we found that one is slow, simple but slow.

00:53:42 One is complicated and faster, and we wonder how we can make them a little bit more balanced so that they can be more suitable for large-scale optimization when n is large.

00:53:54 So we end up having the conjugate gradient that is, you know, increasing the convergence rate for gradient descent.

00:54:03 We also have quasi-Newton or truncated Newton that are not so complicated, which does not need the analytical or precise calculation of the inverse of the Hessian.

00:54:14 Instead, we approximate them using the previous samples, okay?

00:54:22 So, this summarize the gradient-based algorithms, okay?

00:54:29 Any questions so far?

00:54:32 Okay, so now let's continue to talk about the gradient-free algorithms, okay?

00:54:39 And so the gradient-based algorithms in the world of optimization, in the world of non-convex optimization,

00:54:49 is a little bit local, remember, it can remove the clashes and everything for you, right?

00:54:54 But in our case, if we need to talk about a large-scale search, so that you can fold a protein sequence to a structure,

00:55:05 that kind of large-scale search, then you need to consider these non-gradient algorithms.

00:55:14 Because the gradients are expensive, yet too local to be useful.

00:55:21 So, this is the motivation I'm going to talk about.

00:55:26 And one of the ways for this gradient-free non-local search algorithm is Markov-Cheny-Montihallo.

00:55:33 So, no matter what you do, you must have done MCMC to some extent, because it's a very powerful way to sample a random variable following a probability distribution.

00:55:45 And I want to talk about that and this Metropolis algorithm, okay?

00:55:50 And the idea is how you can construct a reversible and ergodic Markov chain, so that you can sample the protein structures.

00:56:00 And you may ask, well, what is the desired probability distribution to sample them?

00:56:05 Remember, last lecture, we talked about the principle, we talked about the fact that there is all this Gibbs-free energy, right?

00:56:13 Each protein structure X is corresponding to a Gibbs-free energy G, and the probability distribution of that X is following a Boltzmann distribution, right?

00:56:28 Exponential in this minus G divided by RT, right?

00:56:31 So that's called the Boltzmann distribution.

00:56:33 As I said, Boltzmann distribution is not just used in proteins or molecules, for sure.

00:56:39 You have seen its footprints in, what, for instance, restricted Boltzmann machines.

00:56:46 Or currently, if you're following what the energy-based machine learning or deep learning models, right?

00:56:53 Following what Yanlu Kun proposed before, you would also see the Boltzmann distribution again and again.

00:57:00 So, for those of you who have, okay, let's see.

00:57:06 All of you have taken stochastic processes, right?

00:57:14 Stochastic processes, Markov chain?

00:57:19 Everyone has taken it, Markov chain? No?

00:57:22 Okay, we'll review those concepts.

00:57:24 And then, you know, if you are interested in more, there is a book called Introduction to Probability Models.

00:57:30 Its electronic copies accessible through our library, just for search for this book name at library.tamu.edu.

00:57:37 The chapters 4.1 to 4.4 and 4.9 are corresponding to the contents I'm going to talk about, okay?

00:57:47 And also, for this more, like, optimization for protein structure thing, you can also look at the Thomas Schlick's book, Chapter 12, Section 5.

00:57:58 Okay?

00:57:59 Both are accessible.

00:58:00 Okay, I think I have time to introduce these ideas and Markov chain Monte Carlo first, okay?

00:58:08 So, again, we are in the midnight zone.

00:58:12 Remember, these gradient-based algorithms are useful for local searches.

00:58:18 For instance, if I want to remove some local Van der Waals clashes when atoms run into each other,

00:58:23 or I put two positively charged side chains too close to each other, right?

00:58:29 But I know that I cannot count on it for a global search, right?

00:58:36 So, in those cases, when the gradients are too local and too, you know, non-informative,

00:58:44 we probably need to look at the derivative-free, gradient-free algorithms.

00:58:49 And I also want to say that even though I talk so much about algorithms,

00:58:54 you also need to pay attention that the energy function is probably more important than the algorithm,

00:59:02 because the algorithm tells you that given the function, I can search faster with less resources or whatever, right?

00:59:10 But it's the function itself that defines whether the global optimum is meaningful,

00:59:16 like the native structure of the protein, right?

00:59:19 So that's also important.

00:59:21 A lot of what we are doing now using deep learning is actually to use deep learning models to learn those functions, right?

00:59:28 Okay, so we're going to talk about
