Minimise functions of one and two variables, watch gradient descent and Newton's method on contour maps, see why large data sets need mini-batch (stochastic) gradient descent, and train a small classifier.
Type f(x) and a bracket [a, b] containing one minimum. Each step keeps the part that must contain the minimum.
Choose a function of x and y, a start, the method and the learning rate. The contour lines are levels of f; the path shows the iterates.
Why does machine learning use stochastic gradient descent? The classifier of Problem 3 is trained on N students generated from the same model. Both methods get the same compute budget, counted in gradients of single data points: one full-batch step costs N of them, one mini-batch step only B.
Try: (1) N = 1,000: both methods reach the minimum. (2) Raise N to 100,000 and 1,000,000 with the budget fixed: full-batch GD takes only 10 steps, then 1 step, while mini-batch SGD is unaffected by N. (3) B = 1 with η = 0.2 or 0.5: the path jitters around the minimum (noise floor); lower η or tick "decrease η". (4) B = 4096: smoother but fewer steps. Real training uses B = 32–512.
Golden section and Newton
Try this
Logistic regression
Try this
Full batch vs mini-batch
Try this
Q1 Why is the ratio 0.618 used in golden-section search?
With g=(5−1)/2, g2=1−g, so one interior point of the old bracket is exactly an interior point of the new one; only one new function value is needed per step.
Q2 Write the gradient-descent update and explain the learning rate.
xk+1=xk−η∇f(xk). η is the step size: too small gives slow progress, too large (above 2/λmax of the Hessian) makes the iteration oscillate or diverge.
Q3 How is gradient descent related to Euler's method?
It is Euler's method with step η for the ODE x′=−∇f(x) (gradient flow); its stability limit is the learning-rate limit.
Q4 Compare Newton's method and gradient descent for minimisation.
Newton uses second derivatives (the Hessian) and converges quadratically, exactly in one step for a quadratic, but each step costs an n×n solve; gradient descent uses only the gradient, steps are cheap, convergence is linear and slow when the problem is ill-conditioned.
Q5 What is the Gauss–Newton method?
For nonlinear least squares: linearise the model about the current parameters with the Jacobian J, solve the linear least-squares problem (JTJ)δ=JTr for the correction, update and repeat.