Visually Explained: Newton's Method in Optimization

Рет қаралды 96,800

Күн бұрын

We take a look at Newton's method, a powerful technique in Optimization. We explain the intuition behind it, and we list some of its pros and cons. No necessary background required beyond basic linear algebra and calculus.
00:00 Introduction
00:14 Unconstrained Optimization
01:18 Iterative Optimization
3:41 Numerical Example
6:00 Derivation of Newton's Method
7:48 Newton's Method for Solving Equations
8:33 The Good
9:31 The Bad
10:35 The Ugly

Пікірлер: 98

@quyenhuynh572 Жыл бұрын

I'm a visual learner and this video is exactly what I'm looking for! Great content!

@rmrumman4837 3 жыл бұрын

This is so high quality stuff! Thanks for the graphical explanation at the beginning!

@jyothishkumar3098 2 жыл бұрын

I'm here from yesterday's 3b1b video on Newton's method of finding roots, after wondering if there's any way to use it for minimizing a function. Mainly to see why we can't use it instead of Stochastic Gradiend Descent in Linear Regression. Turns out the Hessian of functions with many components can turn out to be large and computationally intensive, and also that if the second derivative is not a parabola, it can lead you far away from the minima. Still it was nice to see how the operation works in practice, and you mentioned the same points about Hessians too. Good job 😊👍

@wenyunie3575 3 жыл бұрын

Your explanation is awesome. Extension from root-finding scenario to minimum-point-finding problem was exactly my question.

@saqlainsajid4067 3 жыл бұрын

This is brilliant thank you, hope you give us more visual insight into calculus related things

@samiissaadi53 2 жыл бұрын

Crystal clear explanation, thank you!

@SonLeTyP9496 3 жыл бұрын

Hi Bachir, what an interesting series, very helpful. Cant wait to see next episode

@razmyhathy2398 Жыл бұрын

It is indeed a truly amazing explanation, and it helps me to understand Newton method visually.

@mattkriese7170 4 ай бұрын

Just finished calculus 1 and learning about Newton’s method brought me here. The visuals were fantastic and the explanation was clear. I’ll need to learn a lot more to grasp the entire concept, but it’s exciting to see topics taught like this for us visual learners. Subbed 😁

@fezkhanna6900 2 жыл бұрын

This was such an awesome explanation, so grateful thank you.

@benoitmialet9842 3 жыл бұрын

Brillant explanation, thank you so much.

@tuntstunt Жыл бұрын

your videos are so good i wish they were a thing when I took my course on continuous optimization. my professor could never. i wish you would keep making them though!!!

@minoh1543 3 жыл бұрын

Amazing explaination! This is very helful for understanding. Thanks a lot sir.

@filippocuscito4333 3 жыл бұрын

Amazing video. Looking forward to more.

@jfusion99 3 жыл бұрын

Amazingly presented, thank you.

@aanchaljain4610 3 ай бұрын

just amazing explanation!!

@farhanhyder6378 Жыл бұрын

Loved the graphical presentation

@AJ-et3vf Жыл бұрын

Great video. Thank you!

@mlharville 6 ай бұрын

Loved this - very helpful! I knew this a long time ago and forgot much of it, so this was an excellent refresher, accessible to many. (And this is coming from a Stanford / Caltech grad working in computer vision, machine learning, and related things.)

@mitratavakkoli2865 2 жыл бұрын

Amazing job! Thanks a lot!!

@adnon2604 2 ай бұрын

Amazing video! I could save a lot of time! Thank you very much.

@tomxiao Жыл бұрын

Thank you, brilliant stuff.

@mrtochiko2885 6 ай бұрын

very useful, thanks !

@kravacc7369 5 ай бұрын

Truly an amazing video!!

@rayankasam4784 5 ай бұрын

Loved the video

@aniketbhandare2847 2 жыл бұрын

It just needs more videos to get rocket growth !! Very Good Quality stuff ..

@swazza9999 2 жыл бұрын

Excellent video. I especially liked how you linked it back to the root finding version we learned in school. My one beef with this video is that that's an unfair depiction of Tuco.

@rajivgulati4298 2 жыл бұрын

Great video man. God bless you

@jungeunk 7 ай бұрын

What a concise and informative explanation!!! thank you SO MUCH!! I subscribe your channel from now!

@himanshuprasad9579 6 ай бұрын

thankyou . very helpful

@shimuk8 2 жыл бұрын

HOLYYYYY FKKK !!!! I really wish I came across your video much before I took the painful ways to learn all this… definitely a big recommendation for all the people I know who just started with optimisation courses. Great work !!!!!

@brandondean961 2 жыл бұрын

Great content

@capsbr2100 Жыл бұрын

Very nice video, complicated topic made easy to understand.

@LoL4476 2 жыл бұрын

Very good explanation

@sirelkir Жыл бұрын

Another problem is for a negative curvature, the method climbs uphill. E.g. ML Loss functions tend to have a lot of saddle points, which attract the method, so gradient descent is used, because it can find the direction down from the saddle

@thegoru0106 Жыл бұрын

Great explanation

@neelabhchoudhary2063 6 ай бұрын

holy cow this was super helpful

@fatihburakakcay5026 2 жыл бұрын

Again amazing

@jahn4517 2 жыл бұрын

WoW! This is amasing work man, thank you.

@VisuallyExplained 2 жыл бұрын

Thank you for your amazing comment :-)

@bradhatch8302 2 жыл бұрын

What the what?! Even I understood this. Killer tutorial!

@VisuallyExplained 2 жыл бұрын

Yayy!

@saturapt3229 Жыл бұрын

Tyvm sir

@vigneshbalaji21 Жыл бұрын

Nice explanation

@1239719 2 жыл бұрын

oh man is this gold

@deutsch_lernen_mit_kindern 3 жыл бұрын

amazing

@hosseinshahbazi3655 2 жыл бұрын

Excellent, Please explain LBFGS

@aayushjariwala6256 2 жыл бұрын

It's rare when less viewed video gives best explanation. Your presentations are almost like 3Blue1Brown or Khan academy! Don't know why this video has this less view!!

@igbana Жыл бұрын

This guy knowwwwsssss🔥🔥🙌🙌I love 3blue1brown

@tuongnguyen9391 3 жыл бұрын

Hey can you do a sum of square, dsos optimization tutorial for post graduate student.

@shourabhpayal1198 2 жыл бұрын

Good job. I am subscribing !

@VisuallyExplained 2 жыл бұрын

Awesome, thank you!

@weisongwen3042 9 ай бұрын

Nice videos! May i know what tools do you use to make this figures?

@ha15224 Жыл бұрын

thank you for this amazing visualization. Is it also possible to find roots of a multivariable vector fuction (f: R^n -> R^m)? The resources I found solved this by using the jacobi matrix such that x_{k+1} = x_{k} - J^{-1} f, where J^{-1} is the inverse or the pseudoinverse. Is this method referred to as the newton method for a vector function or is it a completely different method? Any help and reference to resources would be greatly appreciated.

@ivanstepanovftw 6 ай бұрын

More!

@multiverse6968 2 жыл бұрын

lovely explanation 🤩🤩🤩🤩🤩🤩

@VisuallyExplained 2 жыл бұрын

Thanks a lot 😊

@geze2004 2 жыл бұрын

This is great. What is the plotting tool you are using?

@VisuallyExplained 2 жыл бұрын

Thank! For this video I used the excellent library manim: github.com/3b1b/manim

@igbana Жыл бұрын

The first statement you made explained half of my confusions 😩🤲

@JosephZhang-s2d 2 күн бұрын

@Visually Explained, could you help me understand @8:26, why the Newton method can be written from xk - grad^2(f(xk))^-1 * grad(f(xk)) to xk- g(x)/ grad(g(x)) ?

@TheTessatje123 Жыл бұрын

Is my intuition correct (7:21) if the curvature is high you take a small step and vice-versa?

@bl4ckr4bbit 2 күн бұрын

Do you have a video for quasi newton?

@akshayavenkataramanan8121 Жыл бұрын

how come by subtracting the multiple of the slope from the current iterate, we find the minimum point?

@knobberschrabser424 Жыл бұрын

You run into another problem with this method when you evaluate the Hessian at a point where it's not positive-definite. Then you're suddenly calculating a saddle point or even a maximum of the approximation which might lead you farther and farther away from the desired minimum of f(x).

@lalonalel 2 жыл бұрын

can someone please tell me whats the algebra needed for getting the newton method from the taylor series stated in 6:58. thank you in advance

@VisuallyExplained 2 жыл бұрын

I have explained this in another comment. Let me paste it here: "Sure. Consider the quadratic approximation f(x) ~ f(xk) + f'(xk) (x - xk) + f''(xk) (x-xk)^2 at the bottom of the screen at 7:06. To minimize the right hand side, we can take the derivative with respect to x and set it to zero (i.e., f'(xk) + f''(xk) (x - xk) = 0). If you solve for x, you get x = xk - 1 / f''(xk) * f'(xk)." Hope this answers your question.

@lalonalel 2 жыл бұрын

@@VisuallyExplained thank you it really helped me!

@amanutkarsh724 Жыл бұрын

holy good.

@bryanthien3151 3 жыл бұрын

Hi, can you please explain how do you convert alpha into 1 over second derivative of xk at 7:06? Thank you!

@VisuallyExplained 3 жыл бұрын

Sure. Consider the quadratic approximation f(x) ~ f(xk) + f'(xk) (x - xk) + 1/2 f''(xk) (x-xk)^2 at the bottom of the screen at 7:06. To minimize the right hand side, we can take the derivative with respect to x and set it to zero (i.e., f'(xk) + f''(xk) (x - xk) = 0). If you solve for x, you get x = xk - 1 / f''(xk) * f'(xk).

@bryanthien3151 3 жыл бұрын

@@VisuallyExplained Got it. Thank you so much for the explanation! :)

@prub4146 3 жыл бұрын

@@VisuallyExplained I appreciate your answer and video explanation. I have one confusion. Why do we want to take the derivative in the RHS? In other words, why did we decide to take the minimizer of the quadratic equation as the next step?

@VisuallyExplained 3 жыл бұрын

@@prub4146 What we are really trying to do is minimize the LHS (i.e., the function f), but it is often hard to do that directly. Instead, we approximate f by a quadratic function (the one in the RHS), and we minimize that quadratic instead. (The minimizer of a quadratic function admits a simple analytical formula, which we find by taking the derivative.) The hope is that the quadratic function is a good enough approximation that its minimum and the minimum of f are close to each other. Let me know if this explanation is clear enough, otherwise I can expand a bit more.

@prub4146 3 жыл бұрын

@@VisuallyExplained Thank you for the explanation. Thanks

@sidhartsatapathy1863 2 ай бұрын

sir do you use "MANIM" libray of python to create these beautiful animations in your great videos ?

@NithinSaiSunkavalli 4 ай бұрын

I didnt understand how you changed alpha to 1/f''(x) at 7:00

@hyperduality2838 Жыл бұрын

Iterative optimization towards a target or goal is a syntropic process -- teleological. Convergence (syntropy) is dual to divergence (entropy) -- the 4th law of thermodynamics! Teleological physics (syntropy) is dual to non teleological physics (entropy). Synchronic lines/points are dual to enchronic lines/points. Points are dual to lines -- the principle of duality in geometry. "Always two there are" -- Yoda. Concepts are dual to percepts -- the mind duality of Immanuel Kant. Mathematicians create new concepts all the time from their perceptions or observations.

@HasdaRocks 3 жыл бұрын

you reading out the whole things made things confusing. Can you explain what did you meant by pick a direction "IE" @1:51 ? Or did you mean i.e. an abbreviation for 'that is'. Hope you don't read next time " = " as double dash.

@mohammadjalali4183 10 ай бұрын

where we can see quasi-newton video??

@totalynotfunnyguy6581 Жыл бұрын

The first iteration gives me 1.25 not 1.7, is this a mistake on the video or am I doing something wrong? x_(k+1)= x-(1/(6(x)))(3(x^2)-3) Evaluating the with the 2 x_(k+1)= 2-(1/(6(2)))(3(2^2)-3)=1.25

@yassinesafraoui 3 жыл бұрын

I'm curious to know where are you from, my guesses are egypt and Morocco

@VisuallyExplained 3 жыл бұрын

Morocco. Was it that obvious? :-)

@pietheijn-vo1gt Жыл бұрын

Hello, great video. I am currently following a course on non-linear optimization and I would like to make videos like this for my own problems. I think you used manim for this video, is this code available somewhere that I can take a look? thanks