Tivadar Danka Profile picture
Jun 22 27 tweets 8 min read Read on X
In machine learning, we take gradient descent for granted.

We rarely question why it works.

What's usually told is the mountain-climbing analogue: to find the valley, step towards the steepest descent.

But why does this work so well? Read on. Image
Our journey is leading through

• differentiation, as the rate of change,
• the basics of differential equations,
• and equilibrium states.

Buckle up! Deep dive into the beautiful world of dynamical systems incoming. (Full post link at the end.)
First, let's talk about derivatives and their mechanical interpretation!

Suppose that the position of an object at time t is given by the function x(t), and for simplicity, assume that it is moving along a straight line — as the distance-time plot illustrates below. Image
By definition, its derivative at a given time is given by the limit of difference quotients. Image
What do the difference quotients represent?

The average speed on a given interval!

(Recall that speed is the ratio of distance and time.) Image
The average speed has a simple geometric interpretation.

If you replace the object's motion with a constant velocity motion moving at the average speed, you'll end up at the same place.

The average speed is just the slope of the line connecting the start and endpoints.
By moving the endpoint closer and closer to the starting point, we obtain the speed at the exact time.

Thus, the derivative describes speed. Similarly, the second derivative describes acceleration.

How is this relevant for gradient descent? Enter dynamical systems. Image
As it turns out, the trajectory of a moving object can be described by its derivatives!

This is Newton's second law of motion. Image
Newton's second law describes mechanics in terms of ordinary differential equations, that is, equations involving derivatives whose solutions are functions.

For instance, this is the differential equation describing a swinging pendulum, as given by Newton's second law. Image
The simplest possible example: exponential growth.

If x(t) is the size of a bacterial colony, x′(t) = x(t) describes unlimited growth.

Think about x′(t) as the rate at which the population grows: without limitations in space and nutrients, cells can replicate whenever possible. Image
There are multiple solutions, each determined by the initial value x(0).

Here are some of them plotted below. Image
In general, differential equations are formulated as initial value problems, where we are given

1) a differential equation,
2) and an initial value. Image
For instance, with the choice f(x) = x (1 - x), we obtain the famous logistic equation.

This models the population growth under a resource constraint.

If we assume that 1 is the capacity of our population, growth becomes more difficult as the size approaches this limit. Image
Here comes the essential part: by studying the sign of f(x) = x (1 - x), we can describe the behavior of solutions! Why?

Because f(x(t)) determines x'(t), and the sign of the derivative x'(t) determines the monotonicity of the solution x(t). Image
This is visualized by the so-called phase portrait.

(The arrows on the x-axis indicate the direction of the solutions' flow.) Image
Here are some of the solutions, confirming what the phase portrait tells us. Image
There are two very special solutions: the constant functions x(t) = 0 and x(t) = 1.

These are called equilibrium points/solutions, and they are determined by the zeroes of f(x). Image
Why are these important?

Because the so-called stable equilibrium points attract the nearby solutions.

Again, check the stable equilibrium x₀ = 1 in the case of the logistic equation. Image
Let's talk about finding the solutions.

As differential equations are often not possible to solve explicitly, we resort to numerical methods.

The simplest one is replacing the derivative with finite differences to discretize the solution. Image
This means that if the step size h is small enough, the function f and the initial value x(0) can be used to approximate x(h). Image
Thus, by defining the recursive sequence below, we obtain a discretized solution.

This is called Euler's method. Image
The smaller the step size, the better the approximation.

Here are some of the discretized solutions for the logistic equation. Image
If the discretized solution looks familiar, it's not an accident.

If f is the derivative of some F, then this is gradient ascent, the algorithm that is used to maximize F.

In the case of the logistic equation, F takes the form of a simple third-degree polynomial. Image
We can easily obtain gradient descent: by maximizing -F, we minimize F.

Thus, gradient descent works because dynamical systems move towards stable equilibria.

(Of course, there are lots of nuances here, but this is the general idea.)
I have published an extensive 2500+ word post about this topic, so check it out for detailed explanations.

Read the full post here (and subscribe to get more posts like this one every week):

thepalindrome.org/p/why-does-gra…
This is also a part of my Mathematics of Machine Learning book.

Tons of intuitive explanations and hands-on examples, all with a focus on machine learning.

Get it here: amazon.com/Mathematics-Ma…
If you have enjoyed this thread, share it with your friends, follow me, and subscribe to my newsletter!

Understanding mathematics is a superpower. I'll help you get there, step by step.

thepalindrome.org

• • •

Missing some Tweet in this thread? You can try to force a refresh
 

Keep Current with Tivadar Danka

Tivadar Danka Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @TivadarDanka

Jul 30
One of the coolest ideas in mathematics is the estimation of a shape's area by throwing random points at it.

Don't believe this works? Check out the animation below, where I show the method on the unit circle. (Whose area equals to π.)

Here is what's behind the magic:
Let's make this method precise!

The first step is to enclose our shape S in a square.

You can imagine this as a rectangular dartboard. Image
Now, we select random points from the board and count how many hit the target.

Again, you can imagine this as closing your eyes, doing a 360° spin, then launching a dart.

(Suppose that you always hit the board. Yes, I know. But in math, reality doesn't limit imagination.) Image
Read 14 tweets
Jul 29
What is common between the Fourier series and the Cartesian coordinate system?

More than you think: they are (almost) the same.

Let me explain why! Image
Let's start with the basics: the inner product.

In the Euclidean plane, it can be calculated using the "magnitude x magnitude x cosine" formula, also known as the geometric definition. Image
Now, let's project x to y!

With basic trigonometry, we can see that the inner product is related to the length of the projection. Image
Read 15 tweets
Jul 27
One of my favorite formulas is the closed-form of the geometric series.

I am amazed by its ubiquity: whether we are solving basic problems or pushing the boundaries of science, the geometric series often makes an appearance.

Here is how to derive it from first principles: Image
Let’s start with the basics: like any other series, the geometric series is the limit of its partial sums.

Our task is to find that limit. Image
There is an issue: the number of terms depends on N.

Thus, we can’t take the limit term by term. Image
Read 13 tweets
Jul 26
Matrices + the Gram-Schmidt process = magic.

This magic is called the QR decomposition, and it's behind the famous eigenvalue-finding QR algorithm.

Here is how it works: Image
In essence, the QR decomposition factors an arbitrary matrix into the product of an orthogonal and an upper triangular matrix.

(We’ll illustrate everything with the 3 x 3 case, but everything works as is in general as well.)
First, some notations:

Every matrix can be thought of as a sequence of column vectors.

Trust me, this simple observation is the foundation of many-many Eureka moments in mathematics. Image
Read 13 tweets
Jul 25
Summing numbers is more exciting than you think.

For instance, summing the same alternating sequence of 1s and (-1)s can either be zero or one, depending on how we group the terms. What's wrong?

I'll explain. Enter the beautiful world of infinite series. Image
Let’s go back to square one: the sum of infinitely many terms is called an infinite series. (Or series in short.)

Infinite series form the foundations of mathematics. Image
Do infinite series make sense? Sure.

Take a look at the geometric series: summing the positive powers of 1/2 adds up to one.

Here is a visual proof to convince you. Image
Read 24 tweets
Jul 24
I have spent at least 50% of my life studying, practicing, and teaching mathematics.

The most common misconceptions I encounter:

• Mathematics is useless
• You must be good with numbers
• You must be talented to do math

These are all wrong. Here's what math is really about: Image
Let's start with a story.

There’s a reason why the best ideas come during showers or walks. They allow the mind to wander freely, unchained from the restraints of focus.

One particular example is graph theory, born from the regular daily walks of the legendary Leonhard Euler.
Here is the map of Königsberg (now known as Kaliningrad, Russia), where these famous walks took place.

This part of the city is interrupted by several rivers and bridges.

(I cheated a little and drew the bridges that were there in Euler's time, but not now). Image
Read 17 tweets

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Don't want to be a Premium member but still want to support us?

Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal

Or Donate anonymously using crypto!

Ethereum

0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E copy

Bitcoin

3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi copy

Thank you for your support!

Follow Us!

:(