1/22
Looks like no tags are added yet.
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).
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.
Why the chain rule is useful
It breaks derivatives into simpler pieces, and most vector cases can be handled one dimension at a time.
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.
Convexity check for single-variable functions
f: R -> R is convex if its second derivative is always non-negative.
When is f(x) = ax^2 + bx + c convex?
f''(x) = 2a, so it is convex when a >= 0.
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).
Hessian (second derivative, multivariable)
A d x d matrix H with H_ij = d^2 f / (dx_i dx_j).
Convexity check for multivariable functions
f is convex if its Hessian is positive semi-definite everywhere.
Gradient and Hessian of f(x) = sum of x_i^2
Gradient = 2x. Hessian = 2I (diagonal). It is PSD, so f is convex.
Closure property of convex functions
The sum of two convex functions is convex.
Key property of convex functions for optimization
There is only one local minimum, and it is also the global minimum.
General supervised learning framework
Training data
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.
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.
Learning rate (eta)
Step size in gradient descent. Usually between 0 and 1 and may change across iterations.
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.
Effect of learning rate too small or too big
Too small: very little progress. Too big: overshoots the minimum.
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).
Local minimum issue
Gradient descent can get stuck in a local minimum when the loss is non-convex.
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.
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.
SGD vs. GD in running time
SGD usually converges faster in wall-clock time than full gradient descent.