Gradients and Optimization

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/22

encourage image

There's no tags or description

Looks like no tags are added yet.

23 Terms

1
New cards

Derivative of f(x) = 1/2 (x - a)^2 with respect to x

df/dx = x - a. Use the chain rule with u = x - a (or expand it explicitly).

2
New cards

Gradient of f(w) = 1/2 (w^T x - y)^2 with respect to w

(w^T x - y) * x. It can be derived dimension by dimension: df/dw_j = (w^T x - y) * x_j.

3
New cards

Why the chain rule is useful

It breaks derivatives into simpler pieces, and most vector cases can be handled one dimension at a time.

4
New cards

Definition of a convex function

f is convex if for all x, y and t in [0,1]: f(tx + (1-t)y) <= t f(x) + (1-t) f(y). The chord lies above the function.

5
New cards

Convexity check for single-variable functions

f: R -> R is convex if its second derivative is always non-negative.

6
New cards

When is f(x) = ax^2 + bx + c convex?

f''(x) = 2a, so it is convex when a >= 0.

7
New cards

Gradient (first derivative, multivariable)

For f: R^d -> R, the gradient is the d x 1 vector of partial derivatives (df/dx_1, …, df/dx_d).

8
New cards

Hessian (second derivative, multivariable)

A d x d matrix H with H_ij = d^2 f / (dx_i dx_j).

9
New cards

Convexity check for multivariable functions

f is convex if its Hessian is positive semi-definite everywhere.

10
New cards

Gradient and Hessian of f(x) = sum of x_i^2

Gradient = 2x. Hessian = 2I (diagonal). It is PSD, so f is convex.

11
New cards

Closure property of convex functions

The sum of two convex functions is convex.

12
New cards

Key property of convex functions for optimization

There is only one local minimum, and it is also the global minimum.

13
New cards

General supervised learning framework

Training data

14
New cards

Local search for minimizing loss

Initialize w randomly. Repeat: find some w' close to w; if L(w') < L(w), move to w'. Stop when it converges.

15
New cards

Gradient descent algorithm

Initialize w(0) (random or all zeros), t = 0. While the gradient is not 0: w(t+1) = w(t) - eta(t) * grad L(w(t)); t = t + 1.

16
New cards

Learning rate (eta)

Step size in gradient descent. Usually between 0 and 1 and may change across iterations.

17
New cards

Rationale behind gradient descent

Differentiable implies local linearity. Taylor expansion: f(x + d) = f(x) + d * grad f(x) + O(d^2) for small d, so stepping against the gradient decreases the loss.

18
New cards

Effect of learning rate too small or too big

Too small: very little progress. Too big: overshoots the minimum.

19
New cards

Learning rate schedulers

Constant (fixed small value), linear decay, cosine (max rate times a cosine value from 1 to 0), adaptive (changes with loss or validation performance).

20
New cards

Local minimum issue

Gradient descent can get stuck in a local minimum when the loss is non-convex.

21
New cards

Why gradient descent can be slow

Every update uses the entire training set. The bottleneck is computing the full gradient, which is a sum over all n instances.

22
New cards

Stochastic gradient descent (SGD)

Estimate the gradient from a sampled batch of training data instead of all of it. In expectation it equals the full gradient. Batch size can be as small as 1.

23
New cards

SGD vs. GD in running time

SGD usually converges faster in wall-clock time than full gradient descent.